arXiv preprint ·
Tight Lower Bounds for Differentially Private Continual Counting
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its asymptotic optimality under pure differential privacy has remained unresolved since its introduction. We resolve this question. For fixed $0 < \varepsilon \le 1$, we prove asymptotically tight lower bounds of $Ω(\log^2 n)$ for worst-case expected $\ell_\infty$ error and $Ω(\log^3 n)$ for mean and maximum per-coordinate expected squared error. These bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. The same lower bounds hold under approximate differential privacy whenever $δ\le n^{-c}$, for any fixed $c>0$. Our lower bounds match the Binary Tree Mechanism instantiated with Laplace noise, establishing its asymptotic optimality under both pure differential privacy and approximate differential privacy in the standard regime of $δ\ll1/n$. Our proof uses a single hard distribution with a bounded exponential score on a tree. A simple modification of the score allows the same framework to establish tight lower bounds for all three error measures.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models
A quantitative tree-likeness bound from average hyperbolicity
A deterministic $(2 + \varepsilon)$-approximation for directed feedback vertex sets in tournaments
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.