Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization
2026-07-09 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a problem called continual counting with strong privacy guarantees (pure differential privacy). They improve how accurately one can track counts over time by using a new matrix factorization method instead of previous tree-based methods. Their approach finds better low-dimensional representations and scales them up, resulting in less error. They also prove that for a certain type of matrix factorization with only 0/1 entries (including older tree methods), the error cannot be improved beyond their bounds. However, it remains unknown if these lower bounds hold for more general methods.
continual countingpure differential privacymaximum squared errormean squared errormatrix factorizationk-ary tree mechanismgradient-based optimizationlower boundalgorithmic implementation
Authors
Pavel Arkhipov, Nikita P. Kalinin
Abstract
Continual counting under pure differential privacy is one of the simplest and most well-studied problems in the continual observation model. Nevertheless, an asymptotic gap remains between the best known upper and lower bounds for maximum squared error and mean squared error: the upper bound is $O(ε^{-2}\log^3 n)$, while the lower bound is $Ω(ε^{-2}\log^2 n)$, for both error metrics. The best known constant in the upper bound is achieved by the $k$-ary tree mechanism with the subtraction trick, due to Andersson, Pagh, Steiner, and Torkamani (FORC 2025). In this work, we improve the leading constant in the maximum squared error and the mean squared error. Our approach uses a general matrix factorization mechanism, yielding an improved bound for pure-DP continual counting that does not rely on a tree-based construction. The mechanism starts from a good-quality low-dimensional factorization, obtained via gradient-based optimization, and gives an explicit matrix construction that lifts this factorization to arbitrarily large dimensions, further improving its error guarantees. We offer an efficient algorithmic implementation of our mechanism. On the lower-bound side, we prove an $Ω(ε^{-2}\log^3 n)$ lower bound for the class of factorizations whose matrices have entries in $\{0,1\}$, matching the upper-bound asymptotics for this class. This class includes the binary tree mechanism and $k$-ary tree mechanisms without the subtraction trick. Extending this lower bound to arbitrary matrix factorizations, and beyond the matrix mechanism altogether, remains an open problem.