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

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

Problem Statement
The paper addresses the fundamental problem of private continual counting. In this setting, an organization observes a binary stream $x \in \{0, 1\}^n$ of length $n$, where a '1' at time step $i$ indicates an event contributed by a single individual. The goal is to release the running counts (prefix sums) $Ax$ at every time step $i \in [n]$ while satisfying $(\epsilon, \delta)$-differential privacy (DP). Here, $A$ is the $n \times n$ lower triangular prefix-sum matrix. The primary metric for accuracy is the expected $\ell_\infty$ error, defined as $\mathbb{E}[\|M(x) - Ax\|_\infty]$, which represents the worst-case error over all time steps.

While the binary tree mechanism is the standard algorithm for this task, its optimality in the approximate DP setting ($\delta > 0$) has been an open question. Previous analyses showed the binary tree mechanism achieves an $\ell_\infty$ error of $O(\log^{3/2} n \cdot \sqrt{\log(1/\delta)}/\epsilon)$. However, the best known lower bound was only $\Omega(\log n / \epsilon)$ (specifically for the square root of the expected squared worst-case error), leaving a gap regarding whether the $\log^{3/2} n$ dependence on the stream length $n$ is necessary.

Methodology and Proof Overview
The authors prove that the binary tree mechanism is asymptotically optimal by establishing a matching lower bound of $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$. The proof proceeds through several key technical steps:

1. Reduction to Oblivious Mechanisms: Following prior work, the authors reduce the problem to analyzing oblivious mechanisms of the form $M(x) = Ax + z$, where $z$ is a noise vector independent of the input $x$. The goal becomes lower bounding $\mathbb{E}[\|z\|_\infty]$.
2. Tree Basis Decomposition: Instead of analyzing the noise directly in the standard basis, the authors decompose the noise vector $z$ into a basis induced by a perfect binary tree. Specifically, they define vectors $\chi_u$ corresponding to subtrees (indicators of leaves in a subtree). In this basis, the noise at any leaf $i$ is the sum of coefficients $b_u$ along the path from the root to leaf $i$. This transforms the problem of bounding the maximum coordinate error into bounding the accumulation of noise along root-to-leaf paths.
3. Noise Accumulation and Residual Uncertainty: The proof introduces the concept of "residual noise" $\sigma_u$. It argues that if the noise at a node $u$ can be predicted with high accuracy from the noise in its subtrees, privacy is violated. The authors define $\sigma_u$ as the expected absolute error in predicting the noise coefficient at a node given the noise in the subtrees below it. They show that the expected $\ell_\infty$ error is lower-bounded by a weighted sum of these residual uncertainties along random root-to-leaf paths.
4. Overcoming the "Prediction" Obstacle: A major challenge is that an adversary cannot directly observe the subtree noise to predict the current node's noise because the input $x$ is unknown. To bypass this, the authors employ a "grandchildren" strategy. They show that by restricting attention to specific subtrees and using three independent copies of the mechanism (leveraging composition properties of DP), an adversary can use a median-of-three trick to reduce the noise variance. This allows the construction of a derived mechanism where the adversary can compute linear measurements of the form $x_i \nu_i + q$, where $q$ has controlled variance.
5. Linear Measurements and Haar Wavelets: The final step constructs an adversary using linear measurements inspired by the Haar wavelet basis. By choosing orthogonal measurement vectors, the authors relate the sum of squared errors of the adversary's estimates to the $\ell_2$ norm of the residual noise. They demonstrate that if the residual noise $\sigma_u$ were small, the adversary could distinguish neighboring inputs with high probability, violating differential privacy. This forces the residual noise to be large, specifically $\sigma_u = \Omega(\sqrt{\log n} / \max\{\epsilon, \delta\})$.
6. Summation: Summing these residual uncertainties along the path yields the final $\Omega(\log^{3/2} n)$ lower bound.

Key Contributions and Results

• Optimality of the Binary Tree Mechanism: The paper proves that for approximate DP, any mechanism for continual counting must incur an expected $\ell_\infty$ error of $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$. This matches the upper bound of the binary tree mechanism (up to constant factors), resolving the open problem of whether the $\log^{3/2} n$ dependence is necessary.
• Tightening Pure DP Bounds: For pure DP ($\delta = 0$), the result tightens the gap between the known upper bound $O(\log^2 n / \epsilon)$ and the lower bound, showing a lower bound of $\Omega(\log^{3/2} n / \epsilon)$.
• Separation from Hereditary Discrepancy: As a corollary, the authors derive the largest possible separation between hereditary discrepancy and the error of private linear queries. They show that the general upper bound $err_{\epsilon, \delta}^\infty(A) = O(\log^{3/2} m \cdot \text{herdisc}_\infty(A))$ is tight in its dependence on the number of queries $m$, as the prefix-sum matrix has hereditary discrepancy 1 but requires $\Omega(\log^{3/2} n)$ error.

Significance
The paper claims to resolve a central open problem in differential privacy by proving that the binary tree mechanism is asymptotically optimal for continual counting in the approximate DP setting. The techniques developed, particularly the combination of tree-based noise decomposition, residual noise analysis, and the use of the median-of-three trick to handle linear measurement attacks, are presented as novel ideas that may find further applications in proving lower bounds for differential privacy. The result confirms that the current state-of-the-art algorithms cannot be significantly improved in terms of their dependence on the stream length $n$.