2024-06-30-cohen24b.md

title	section	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries	Original Papers	One of the most basic problems for studying the “price of privacy over time” is the so called {\em private counter problem}, introduced by Dwork et al. (2010) and Chan et al. (2011). In this problem, we aim to track the number of {\em events} that occur over time, while hiding the existence of every single event. More specifically, in every time step $t\in[T]$ we learn (in an online fashion) that $\Delta_t\geq 0$ new events have occurred, and must respond with an estimate $n_t\approx\sum_{j=1}^t \Delta_j$. The privacy requirement is that {\em all of the outputs together}, across all time steps, satisfy {\em 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 $O\left(\log(T)+\log^2(n)\right)$, and Henzinger et al. (2023) showed a lower bound of $\Omega\left( \min\{\log n, \log T\} \right)$. We show a new lower bound of $\Omega\left(\min\{n,\log T\}\right)$, which is tight w.r.t. the dependence on $T$, and is tight in the sparse case where $\log^2 n=O(\log T)$. Our lower bound has the following implications: \begin{itemize} \item We show that our lower bound extends to the {\em 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). \item 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. \item 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 {\em private online prediction}. \end{itemize}	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	cohen24b	0	Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries	1200	1222	1200-1222	1200	false	Cohen, Edith and Lyu, Xin and Nelson, Jelani and Sarl\'{o}s, Tam\'{a}s and Stemmer, Uri	given family Edith Cohen given family Xin Lyu given family Jelani Nelson given family Tamás Sarlós given family Uri Stemmer	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/cohen24b/cohen24b.pdf