Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries

One of the most basic problems for studying the "price of privacy over time" is the so called private counter problem, introduced by Dwork et al. (2010) and Chan et al. (2010). In this problem, we aim to track the number of events that occur over time, while hiding the existence of every single event. More specifically, in every time step t∈[T] we learn (in an online fashion) that Deltat≥ 0 new events have occurred, and must respond with an estimate nt≈sumj=1t Deltaj. The privacy requirement is that all of the outputs together, across all time steps, satisfy event level differential privacy. The main question here is how our error needs to depend on the total number of time steps T and the total number of events n. Dwork et al. (2015) showed an upper bound of Oleft(log(T)+log2(n)right), and Henzinger et al. (2023) showed a lower bound of Omegaleft(minlog n, log Tright). We show a new lower bound of Omegaleft(minn,log Tright), which is tight w.r.t. the dependence on T, and is tight in the sparse case where log2 n=O(log T). Our lower bound has the following implications: bullet We show that our lower bound extends to the "online thresholds problem", where the goal is to privately answer many "quantile queries" when these queries are presented one-by-one. This resolves an open question of Bun et al. (2017). bullet Our lower bound implies, for the first time, a separation between the number of mistakes obtainable by a private online learner and a non-private online learner. This partially resolves a COLT'22 open question published by Sanyal and Ramponi. bullet Our lower bound also yields the first separation between the standard model of private online learning and a recently proposed relaxed variant of it, called private online prediction.