Source-linked AI summary
Tight Lower Bounds for Differentially Private Continual Counting
Charlie Harrison, Ethan Leeman
TL;DR
The √log n gap for α∞ error and log n gap for MeanSE in continual counting remained open. The paper uses a tree-based score argument to close these gaps with lower bounds for arbitrary mechanisms under pure and small-δ approximate differential privacy.
Problem
A √log n gap under pure and standard approximate differential privacy regimes remained open for continual counting.
Source: §1 · p. 2Method
A bounded exponential score on a tree penalizes non-favored edges, and an accuracy lower bound is balanced against a privacy upper bound.
Source: §3.1 · p. 5Results
The work closes the √log n gap for α∞ and the log n gap for MeanSE, hence MaxSE, under pure and approximate DP; both lower bounds hold for arbitrary mechanisms.
Source: §1.1 · p. 2Takeaways & Limitations
The lower bounds more fully characterize dependence on n for continual counting under pure DP and approximate DP with small δ.
Source: §4 · p. 10The theorem's parameter assumptions require nε ≥ C0 and ε/δ ≥ C1.
Source: §3.4 · p. 9
Abstract
from arXiv · showhide
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 $\Omega(\log^2 n)$ for worst-case expected $\ell_\infty$ error and $\Omega(\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 $\delta\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 $\delta \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.
1 Introduction
Continual counting asks a mechanism to privately release estimates of every prefix sum of a bitstream. The paper closes lower-bound gaps for arbitrary mechanisms in the small-δ regime and establishes tightness for the Binary Tree Mechanism with Laplace noise.
1 Introduction
- Before this work, a √log n gap remained for ℓ∞ error and a log n gap for squared error in pure DP and standard approximate-DP regimes.For pure DP, the cited BTM upper bounds are O(log² n) for ℓ∞ error and O(log³ n) for squared error.Source: §1 · pp. 1–2
1.1 Our contributions
- For fixed ε, the work closes the ℓ∞ and squared-error gaps under pure DP and approximate DP with δ = n^-Ω(1), matching Laplace BTM bounds across all three error notions.The bounds also hold when the entire stream is known in advance, so they apply to online mechanisms as well.Source: §1.1 · pp. 2–3
- Theorem 1 gives pure-DP lower bounds Ω(log²(nε)/ε) and Ω(log³(nε)/ε²), respectively, under its stated assumptions.The paper studies worst-case expected ℓ∞ error, MeanSE, and MaxSE; MaxSE lower bounds follow from MeanSE lower bounds.Source: §1.1 · p. 2, §1 · p. 2
- Table 1 compares bounds for α∞, MaxSE, and MeanSE across δ regimes; the n^-o(1) ≤ δ = o(1) regime remains open.The paper notes that its lower bounds improve prior results in part of this regime but do not establish tightness.Source: Table 1 · p. 3
- The proof uses a 4-ary tree score that relates edge-labeling accuracy to mechanism error and privacy, with group-privacy comparisons for δ ≤ n^-a.Its construction probes children to label favored edges, then scores the path to the differing block.Source: §1.1 · p. 3
2 Preliminaries
The preliminaries define the privacy setting and introduce probe–potential pairs used to reason about accuracy. They also state group privacy and basic stability and variance tools.
2 Preliminaries
- (ε, δ)-DP bounds output-event probabilities on neighboring bitstreams, and pure ε-DP is the special case δ = 0.The definition uses streams at Hamming distance at most one.Source: §2 · p. 4
- Group privacy extends the DP comparison to streams differing in up to k bits and to bounded test functions.The proof uses induction along a neighboring path and layer-cake representation for general tests.Source: §2 · p. 4
- A probe represents selected coordinates, while its associated potential measures their spread; the paper uses mean–variance and midrange–range pairs.Both probes are translation equivariant, and both potentials are translation invariant.Source: §2 · p. 4
- Midrange stability bounds representative-value change by half the reduction in range, while the law of total variance decomposes spread across a partition.These lemmas provide tools for comparing probes and potentials across subsets.Source: §2 · p. 4
3 Our lower bounds
The proof bounds an exponential score on a tree from both accuracy and privacy, then balances the bounds to force error. For fixed ε and polynomially small δ, it yields logarithmic-order lower bounds across the stated error measures.
3.2 Tree setup and definitions
- The proof samples a uniform bit vector and target leaf, flips that leaf, and repeats each bit across a block in a 4-ary-tree instance.The active prefix has q=k4H coordinates, with any remaining stream coordinates padded with zeros.Source: §3.1 · p. 5, §3.2 · p. 6
3.1 Proof overview
- The shifted residual combines normalized mechanism error with a signed unit step whose transition lies inside the flipped block.The probes avoid the changed block itself, so their comparisons can reveal the step without probing that block.Source: §3.1 · p. 5, §3.3 · p. 7
3.2 Tree setup and definitions
- At each tree node, cross-parity probes select favored children; the score S=e^-τN discounts each non-favored edge on the target leaf’s path.N counts non-favored edges along the root-to-leaf path.Source: §3.1 · p. 5, §3.2 · pp. 6–7
3.3 Tree lemmas
- Accuracy lower-bounds the expected target score, while group privacy upper-bounds it using a reference residual with no step signal and an exponentially small baseline score.Balancing these bounds forces mechanism error to be large.Source: §3.1 · p. 5
3.4 Main result
- The main theorem uses the mid probe for α∞ and the mean probe for MeanSE, with tree parameters chosen to produce the stated error orders.The full-stream MeanSE bound uses an active prefix with q≥n/4; MaxSE follows from MaxSE≥MeanSE.Source: §3.4 · pp. 9–10
- For fixed ε and δ≤n^-c, the proof gives Ω(kH) α∞ error and Ω(k²H) MeanSE error, with k,H=Θ(log n) and MaxSE following from MeanSE.The resulting orders are Ω(log² n) for α∞ and Ω(log³ n) for MeanSE and MaxSE.Source: §3.4 · pp. 9–10
- Under Theorem 1's assumptions, every (ε,δ)-DP mechanism admits an input x for which both claimed error lower bounds hold simultaneously with probability at least 1−2e−u/32.For fixed ε, c > 0 and δ ≤ n^-c, u, k, H = Θ(log n), yielding the claimed asymptotic orders and failure probability.Source: §3.4 · p. 10
4 Conclusion
For fixed 0 < ε ≤ 1, the paper establishes tight lower bounds for private continual counting under pure DP and approximate DP when δ is small, while leaving an intermediate δ regime unresolved.
4 Conclusion
- For fixed 0 < ε ≤ 1, tight lower bounds cover ℓ∞ error, mean squared error, and maximum per-coordinate squared error under pure DP and approximate DP with small δ.The bounds more fully characterize continual counting in its dependence on n.Source: §4 · p. 10
- The regime n^-o(1) ≤ δ = o(1) remains unresolved, with the Gaussian Binary Tree Mechanism providing the achievable upper bound.The best lower bounds there combine results by Bairaktari and Larsen [BL26] for α∞ and Henzinger, Upadhyay, and Upadhyay for MeanSE.Source: §4 · p. 10
- The authors used ChatGPT 6 Astra and Gemini 3.8 Flash to help discover proof ingredients and draft, review, and edit the paper.They report that the tools were used interactively starting from Bairaktari and Larsen [BL26], and that the authors verified correctness and originality.Source: §4 · p. 11