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

CardsList
  1. The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting

    Jul 1, 2026Konstantina Bairaktari, Markus Engelund Dahl, Kasper Green LarsenDifferential Privacy

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

    Oct 22, 2026Gautam Kamath, Mahbod Majid, Ankur Moitra +2Robust StatisticsDifferential Privacy