Private Continual Counting of Unbounded Streams

We study the problem of differentially private continual counting in the unbounded setting where the input size n 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 n. Using the common `doubling trick' avoids knowledge of n but leads to suboptimal and non-smooth error. We solve this problem by introducing novel matrix factorizations based on logarithmic perturbations of the function frac1√1-z studied in prior works, which may be of independent interest. The resulting algorithm has smooth error, and for any α > 0 and t≤ n it is able to privately estimate the sum of the first t data points with O(log2+2α(t)) variance. It requires O(t) space and amortized O(log t) time per round, compared to O(log(n)log(t)) variance, O(n) space and O(n log n) pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al. (SODA 2023). Empirically, we find that our algorithm's performance is also comparable to theirs in absolute terms: our variance is less than 1.5× theirs for t as large as 224.