AI & ML
Tight Lower Bounds for Differentially Private Continual Counting
arXiv cs.CR0 views
arXiv:2609.17650v3 Announce Type: replace-cross Abstract: The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its complete asymptotic optimality under differential privacy has remained unresolved since its introduction. We resolve this question. For $0 \leq \varepsilon \leq 1$, we prove asymptotically tight lower bounds for $\ell_\infty$, mean squared, and maximum per-coordinate expected squared error simultaneously under all regimes of $0 \leq \delta \leq 1/4$. These bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. Our lower bounds match the (blocked) Binary Tree Mechanism instantiated with the best of Laplace or Gaussian noise, establishing its asymptotic optimality. Our proof uses a single hard distribution where elements are ``tagged'' as potentially being the target flipped element via a score evaluated down a tree. A simple modification of the score allows the same framework to establish tight lower bounds for all three error measures.
Source:https://arxiv.org/abs/2609.17650PreviousStatistical Adversaries: Natural Backdoor-like Adversarial Features in Clean Vision DatasetsNextVariance-adaptive confidence regions for fixed-benchmark binomial mixtures, with application to LLM evaluation
Related posts

Debugging Claude Fable 5.2 Code Art: Truncated SVG, Broken Canvas, Working Render
0dev.to
Hydra · Coeziune OM–IA — the complete DOI registry (2026-11-18): 76 published works
0dev.to OpenSource
Your Rust Code Sets an Environment Variable and the 2024 Edition Calls That Unsafe
0dev.to Rust
Your Go Function Returned a Nil Error and the Caller Saw an Error Anyway
0dev.to Go
Kengele: an alarm for when an activist goes missing, that nobody can switch off
0dev.to Go
How OpenAI scales PostgreSQL to 800 million users
0dev.to Database