A Unifying Framework for Differentially Private Sums under Continual Observation
Monika Rauch Henzinger, Jalaj Upadhyay, Sarvagya Upadhyay · Society for Industrial and Applied Mathematics eBooks · 2024
We study the problem of maintaining a differentially private decaying sum under continual observation. We give a unifying framework and an efficient algorithm for this problem for any sufficiently smooth function. Our algorithm is the first differentially private algorithm that does not have a multiplicative error for polynomially decaying weights. Our algorithm improves on all prior works on differentially private decaying sums under continual observation and recovers exactly the additive error for the special case of continual counting from Henzinger et al. (SODA 2023) as a corollary.