The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

• URL: http://arxiv.org/abs/2607.00876v2
• Date: Thu, 02 Jul 2026 11:12:33 GMT
• Title: The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting
• Abstract summary: We show that every differentially private mechanism for continual counting must incur expected $ell_infty$ error $(log3/2 n)$.<n>We also obtain a largest-possible separation between hereditary discrepancy and private $ell_infty$ error for linear queries.
• Score: 18.604881105488513
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Private continual counting is a fundamental problem in differential privacy: given a binary stream of length $n$, where each $1$ corresponds to the contribution of one individual, the goal is to release all running counts while protecting the privacy of each individual. The standard algorithm is the binary tree mechanism, whose Gaussian-noise variant achieves expected $\ell_\infty$ error proportional to $\log^{3/2} n$ for approximate differential privacy. Whether this dependence on the stream length is necessary has remained a central open problem. In this work, we resolve the dependence on $n$ by proving that every differentially private mechanism for continual counting must incur expected $\ell_\infty$ error $Ω(\log^{3/2} n)$. This shows that the binary tree mechanism is asymptotically optimal in the approximate-DP setting. As a consequence, we also obtain a largest-possible separation between hereditary discrepancy and private $\ell_\infty$ error for linear queries, showing that the known general upper bound in terms of hereditary discrepancy has the optimal dependence on the number of queries.

Related papers

• Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy [1.8549313085249317]
  We study optimal design of $varepsilon$-locally differentially private mechanisms for binary hypothesis testing.<n>Our results make it possible to efficiently compute and characterize the exact optimum across the full privacy range, beyond privacy regimes.
  arXiv  Detail & Related papers  (2026-06-05T16:41:31Z)
• Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
  This paper introduces a novel proof technique based on a multi-player communication game.<n>We show that winning this communication game requires transmitting information proportional to the number of over-active users.<n>We show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.
  arXiv  Detail & Related papers  (2026-02-12T17:49:07Z)
• Tight Differentially Private PCA via Matrix Coherence [12.864472925970242]
  We show that a simple and efficient algorithm -- based on singular value decomposition and standard perturbation mechanisms -- returns a private rank-$r$ approximation.<n>Our estimator outperforms the state of the art -- significantly so in some regimes.<n>We conjecture that similar behavior holds for other structured models, including planted problems in graphs.
  arXiv  Detail & Related papers  (2025-10-30T16:47:26Z)
• Optimal Best Arm Identification under Differential Privacy [8.321992395325912]
  Best Arm Identification (BAI) algorithms are deployed in data-sensitive applications, such as adaptive clinical trials or user studies.<n>We study the problem of fixed-confidence BAI under global Differential Privacy (DP) for Bernoulli distributions.<n>Our algorithm outperforms existing $delta$correct and $epsilon$-global DP BAI algorithms for different values of $epsilon$.
  arXiv  Detail & Related papers  (2025-10-20T09:46:09Z)
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  We investigate the Generalized Gaussian mechanism, which samples the additive noise term $x$ with probability proportional to $e-frac| x |sigmabeta $ for some $beta geq 1$.<n>We show that privacy accounting for the GG Mechanism and its variants is independent, which substantially improves computational costs of privacy accounting.
  arXiv  Detail & Related papers  (2025-06-14T15:49:25Z)
• Approximate Differential Privacy of the $\ell_2$ Mechanism [52.61055173572399]
  We study the $ell$ mechanism for computing a $d$-dimensional statistic with bounded $ell$ sensitivity under approximate differential privacy.<n>Across a range of privacy parameters, we find that the $ell$ mechanism obtains lower error than the Laplace and Gaussian mechanisms.
  arXiv  Detail & Related papers  (2025-02-21T20:56:34Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  We introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm.<n>DaRRM is parameterized by a data-dependent noise function $gamma$, and enables efficient utility optimization over the class of all private algorithms.<n>We show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility.
  arXiv  Detail & Related papers  (2024-11-27T00:48:48Z)
• Near-Universally-Optimal Differentially Private Minimum Spanning Trees [0.0]
  We prove that a simple differentially private mechanism for approximately releasing the minimum spanning tree is near-optimal in the sense of universal optimality for the $ell_infty$ neighbor relation. We show that one may implement the exponential mechanism for MST in time, and that this results in universal near-optimality for both the $ell_infty$ and the $ell_infty$ neighbor relations.
  arXiv  Detail & Related papers  (2024-04-23T13:39:25Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  Differentially private computation often begins with a bound on some $d$-dimensional statistic's sensitivity. For pure differential privacy, the $K$-norm mechanism can improve on this approach using a norm tailored to the statistic's sensitivity space. This paper solves both problems for the simple statistics of sum, count, and vote.
  arXiv  Detail & Related papers  (2023-09-27T17:09:36Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.