# Continual Counting with Gradual Privacy Expiration

arXiv: https://arxiv.org/abs/2406.03802 · HTML: https://mlsanity.com/paper/2406.03802/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2024.

## Built on by (most cited first, 2 of 2)

- [Private Continual Counting of Unbounded Streams](https://mlsanity.com/paper/2506.15018/) (2025)
- [The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting](https://mlsanity.com/paper/2607.00876/) (2026)

## Abstract (arXiv)

Differential privacy with gradual expiration models the setting where data items arrive in a stream and at a given time t the privacy loss guaranteed for a data item seen at time (t-d) is ε g(d), where g is a monotonically non-decreasing function. We study the fundamental textitcontinual (binary) counting problem where each data item consists of a bit, and the algorithm needs to output at each time step the sum of all the bits streamed so far. For a stream of length T and privacy textitwithout expiration continual counting is possible with maximum (over all time steps) additive error O(log2(T)/varepsilon) and the best known lower bound is Omega(log(T)/varepsilon); closing this gap is a challenging open problem. We show that the situation is very different for privacy with gradual expiration by giving upper and lower bounds for a large set of expiration functions g. Specifically, our algorithm achieves an additive error of  O(log(T)/ε) for a large set of privacy expiration functions. We also give a lower bound that shows that if C is the additive error of any ε-DP algorithm for this problem, then the product of C and the privacy expiration function after 2C steps must be Omega(log(T)/ε). Our algorithm matches this lower bound as its additive error is O(log(T)/ε), even when g(2C) = O(1). Our empirical evaluation shows that we achieve a slowly growing privacy loss with significantly smaller empirical privacy loss for large values of d than a natural baseline algorithm.