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
Fluent English is not evidence of ASL understanding: lessons from building a video translator
0dev.to

Audit Trails and Explainability for Agentic AI in Code Events
0dev.to
By 3 p.m. the daily high was already final on 78% of days. In Madrid, 32% (49 airports, one year)
0dev.to

This smell startup says its AI nose is as good as a human’s
0MIT Technology Review

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