Private Continual Counting of Unbounded Streams
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 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 . Using the common `doubling trick' avoids knowledge of but leads to suboptimal and non-smooth error. We solve this problem by introducing novel matrix factorizations based on logarithmic perturbations of the function studied in prior works, which may be of independent interest. The resulting algorithm has smooth error, and for any and , it is able to privately estimate the sum of the first data points with variance. It requires space and amortized time per round, compared to variance, space and 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 theirs for as large as .
Figures & tables
| Mechanism | Time for outputs | Space | Smooth | Unbounded | |
| Binary [ Chan et al., 2011 , Jain et al., 2012 ] * | No | No | |||
| Hybrid Binary [ Chan et al., 2011 ] * | No | Yes | |||
| Smooth Binary [ Andersson and Pagh, 2023 ] | Yes | No | |||
| Sqrt Matrix [ Henzinger et al., 2023 , Fichtenberger et al., 2023 ] | Yes | No | |||
| Algorithm 1 | Yes | Yes | |||
| Hybrid Matrix | No | Yes |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Differential Privacy
Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.
See all 309 papers