@inproceedings{19512,
  abstract     = {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 continual (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 without expiration
continual counting is possible with maximum (over all time steps) additive error
O(log2
(T)/ε) and the best known lower bound is Ω(log(T)/ε); 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 Ω(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.},
  author       = {Andersson, Joel Daniel and Henzinger, Monika H and Pagh, Rasmus and Steiner, Teresa Anna and Upadhyay, Jalaj},
  booktitle    = {38th Conference on Neural Information Processing Systems},
  issn         = {1049-5258},
  location     = {Vancouver, Canada},
  publisher    = {Neural Information Processing Systems Foundation},
  title        = {{Continual counting with gradual privacy expiration}},
  volume       = {37},
  year         = {2024},
}