cs.CRJun 17, 2025

Private Continual Counting of Unbounded Streams

Authors: Ben Jacobsen, Kassem Fawaz

Organizations: Department of Computer Sciences University of Wisconsin — Madison · Department of Electrical and Computer Engineering University of Wisconsin — Madison

Abstract

We study the problem of differentially private continual counting in the unbounded setting where the input size nn is not known in advance. Current state-of-the-art algorithms based on optimal instantiations of the matrix mechanism cannot be directly applied here because their privacy guarantees only hold when key parameters are tuned to nn. Using the common `doubling trick' avoids knowledge of nn but leads to suboptimal and non-smooth error. We solve this problem by introducing novel matrix factorizations based on logarithmic perturbations of the function 11−z\frac{1}{\sqrt{1-z}} studied in prior works, which may be of independent interest. The resulting algorithm has smooth error, and for any α>0α> 0 and t≤nt\leq n, it is able to privately estimate the sum of the first tt data points with O(log⁡2(t)(log⁡log⁡t)1+2α)O(\log^{2}(t)(\log\log t)^{1+2α}) variance. It requires O(t)O(t) space and amortized O(log⁡t)O(\log t) time per round, compared to O(log⁡(n)log⁡(t))O(\log(n)\log(t)) variance, O(n)O(n) space and O(nlog⁡n)O(n \log n) pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al. Empirically, we find that our algorithm's performance is also comparable to theirs in absolute terms: with optimized parameters, our variance is less than 2×2\times theirs for tt as large as 2322^{32}.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Jul 1, 2026

The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting

Private continual counting is a fundamental problem in differential privacy: given a binary stream of length nn, where each 11 corresponds to the contribution of one individual, the goal is to release all running counts while protecting the privacy of each individual. For fixed privacy parameters, the standard binary tree mechanism achieves expected ℓ∞\ell_\infty error O(log⁡3/2n)O(\log^{3/2} n) under approximate differential privacy and O(log⁡2n)O(\log^2 n) under pure differential privacy. Whether these dependences on the stream length are necessary has remained a central open problem. For fixed ε∈(0,1)\varepsilon\in(0,1), we prove a lower bound of Ω(log⁡3/2n)Ω(\log^{3/2} n) under approximate DP with sufficiently small fixed δ>0δ>0, and a lower bound of Ω(log⁡2n)Ω(\log^2 n) under pure DP. These bounds establish the optimality of the binary tree mechanism in both settings. The bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. Both proofs use the same decomposition and accumulation of residual noise along a tree. As a consequence of the approximate-DP bound, we also obtain a largest-possible separation between hereditary discrepancy and private ℓ∞\ell_\infty error for linear queries, showing that the known general upper bound in terms of hereditary discrepancy has the optimal dependence on the number of queries.
Sep 22, 2026

An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting

The goal of this note is to give a detailed proof, to the best of our understanding, of the recent presentation by Harrison and Leeman (arXiv:2609.17650v01 and arXiv:2609.17650v02) of the proof by Astra on the lower bound for differentially private continual counting. We believe a more natural and easy proof is possible and hope that this note will help in that effort. Prior to the initial preprint by Harrison and Leeman (arXiv:2609.17650v01), Bairaktari and Larsen (arXiv:2607.00876) gave an elegant proof to show a lower bound of Ω(log⁡3/2(n))Ω(\log^{3/2}(n)) for both pure and approximate-DP continual counting, and in personal communication had informed us that they have a proof of optimal Ω(log⁡2(n))Ω(\log^{2}(n)) for pure-differential private continual counting as well. They have subsequently published their Ω(log⁡2(n))Ω(\log^{2}(n)) bound, which is now a joint work of Bairaktari, Dahl, and Larsen (arXiv:2607.00876v3). Their new result is an elegant extension of their technique for approximate-differential privacy. Although the two proofs are technically different, the Astra argument uses related tree geometry introduced in Bairaktari and Larsen.
Oct 22, 2026

Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy

We study learning a discrete distribution under person-level differential privacy in the batched setting. Given nn users, each contributing mm i.i.d. samples from an unknown distribution μμ over [k][k], we seek an estimate of μμ with total-variation error αα. We give polynomial-time algorithms under both pure and approximate differential privacy. Under pure (ε,0)(\varepsilon,0)-DP, we achieve n=O~(k/(α2m)+k/(αmε)+k/ε)n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k/\varepsilon), the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors. Under approximate (ε,δ)(\varepsilon,δ)-DP, we achieve n=O~(k/(α2m)+k/(αmε)+k+log⁡(1/δ)/ε)n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k+\log(1/δ)/\varepsilon). At δ=2−Θ(k)δ=2^{-Θ(k)}, this is O~(k)\widetilde O(k) for fixed α,ε,mα,\varepsilon,m and failure probability. Our algorithms use a new degree-6 sum-of-squares estimator for learning from untrusted batches. Its key ingredient is a trace-bounded diagonal majorizer for the difference between the empirical covariance of the repaired batch averages and the multinomial covariance predicted by their mean. We prove that clean data admit this certificate through semidefinite-programming duality and a new application of the stronger symmetric form of Grothendieck's inequality due to Friedland and Lim. The certificate preserves the mean-dependent variance of multinomial batch averages, yielding the near-optimal robust rate O(ηlog⁡(1/η)/m)O(η\sqrt{\log(1/η)/m}) and providing the score required by the privacy reduction. We also prove a statistical query lower bound ruling out a uniformly smaller order of error under fixed polynomial SQ resource bounds.