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

arXiv: https://arxiv.org/abs/2403.00028 · HTML: https://mlsanity.com/paper/2403.00028/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 28 Feb 2024.

## Builds on (most cited first, 12 of 12)

- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (2015)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [Robust Mediators in Large Games](https://mlsanity.com/paper/1512.02698/) (2015)
- [On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective](https://mlsanity.com/paper/2402.16778/) (2024)
- [Do you pay for Privacy in Online learning?](https://mlsanity.com/paper/2210.04817/) (2022)
- [Differentially Private Weighted Sampling](https://mlsanity.com/paper/2010.13048/) (2020)
- [The Target-Charging Technique for Privacy Accounting across Interactive Computations](https://mlsanity.com/paper/2302.11044/) (2023)

## Built on by (most cited first, 12 of 12)

- [Streaming Private Continual Counting via Binning](https://mlsanity.com/paper/2412.07093/) (2024)
- [The Limits of Differential Privacy in Online Learning](https://mlsanity.com/paper/2411.05483/) (2024)
- [Protecting the Undeleted in Machine Unlearning](https://mlsanity.com/paper/2602.16697/) (2026)
- [Binned Group Algebra Factorization for Differentially Private Continual Counting](https://mlsanity.com/paper/2504.04398/) (2025)
- [Private Learning of Littlestone Classes, Revisited](https://mlsanity.com/paper/2510.00076/) (2025)
- [Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings](https://mlsanity.com/paper/2510.00574/) (2025)
- [Privately Learning Decision Lists and a Differentially Private Winnow](https://mlsanity.com/paper/2602.07370/) (2026)
- [The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting](https://mlsanity.com/paper/2607.00876/) (2026)
- [Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacy](https://mlsanity.com/paper/2601.22320/) (2026)
- [Continual Learning With Participation Privacy: An Auditable Buffering-Aggregation Recipe](https://mlsanity.com/paper/2607.07209/) (2026)
- [Plausible Deniability Guarantees for Whistleblowers](https://mlsanity.com/paper/2607.13928/) (2026)
- [Machine Unlearning as Private Retroactive Algorithms](https://mlsanity.com/paper/2609.05329/) (2026)

## Abstract (arXiv)

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.