Continual counting with gradual privacy expiration

conference paper Continual counting with gradual privacy expiration Advances in Neural Information Processing Systems published yes Joel Daniel Andersson author Monika H Henzinger author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530 Rasmus Pagh author Teresa Anna Steiner author Jalaj Upadhyay author MoHe department NeurIPS: Neural Information Processing Systems The design and evaluation of modern fully dynamic data structures project Efficient algorithms project Static and Dynamic Hierarchical Graph Decompositions project Fast Algorithms for a Reactive Network Layer project 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. Neural Information Processing Systems Foundation2024Vancouver, Canada eng 38th Conference on Neural Information Processing Systems 1049-5258 2406.03802 37 Andersson, J. D., Henzinger, M., Pagh, R., Steiner, T. A., & Upadhyay, J. (2024). Continual counting with gradual privacy expiration. In 38th Conference on Neural Information Processing Systems (Vol. 37). Vancouver, Canada: Neural Information Processing Systems Foundation. Andersson, Joel Daniel, et al. “Continual Counting with Gradual Privacy Expiration.” 38th Conference on Neural Information Processing Systems, vol. 37, Neural Information Processing Systems Foundation, 2024. Andersson, Joel Daniel, Monika Henzinger, Rasmus Pagh, Teresa Anna Steiner, and Jalaj Upadhyay. “Continual Counting with Gradual Privacy Expiration.” In 38th Conference on Neural Information Processing Systems, Vol. 37. Neural Information Processing Systems Foundation, 2024. J.D. Andersson, M. Henzinger, R. Pagh, T.A. Steiner, J. Upadhyay, in:, 38th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2024. Andersson JD, Henzinger M, Pagh R, Steiner TA, Upadhyay J. Continual counting with gradual privacy expiration. In: 38th Conference on Neural Information Processing Systems. Vol 37. Neural Information Processing Systems Foundation; 2024. J. D. Andersson, M. Henzinger, R. Pagh, T. A. Steiner, and J. Upadhyay, “Continual counting with gradual privacy expiration,” in 38th Conference on Neural Information Processing Systems, Vancouver, Canada, 2024, vol. 37. Andersson JD, Henzinger M, Pagh R, Steiner TA, Upadhyay J. 2024. Continual counting with gradual privacy expiration. 38th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 37. 195122025-04-06T22:01:32Z2025-05-14T11:33:22Z