PaperlayerView exact revision on arXiv

Source-linked AI summary

An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting

Jalaj Upadhyay

arXiv:2609.28528v1cs.CRcs.DScs.LG

TL;DR

Continual counting asks for accurate prefix sums while differential privacy limits what outputs reveal about neighboring streams. This note gives a detailed, rigorous exposition of Harrison and Leeman’s presentation of Astra’s lower-bound proof. It combines accuracy and privacy bounds on a score to derive the claimed lower bound.

  • Problem

    The proof addresses how to lower-bound continual-counting accuracy when differential privacy must keep outputs from distinguishing neighboring streams.

    Source: §2 · p. 2

  • Method

    The note explains a hidden-location hard instance, a local decoder, probe–potential pairs, and an exponential score used in Astra’s proof.

    Source: §1 · p. 2

  • Results

    Combining the score’s accuracy and privacy bounds with k = Θ(log(n/ε)) and H = Θ(log(n)) yields the claimed lower bound.

    Source: High Level Proof Overview · p. 4

  • Takeaways & Limitations

    The authors aim to make the proof self-contained and rigorous, including proofs of claims left unproved in the original preprint.

    Source: §1 · p. 2

    The authors leave unclear whether a tree arity that is not a power of two would be useful in this proof.

    Source: §7 · p. 21

Abstract

from arXiv · show

The goal of this note is to give a detailed proof, to the best of our understanding, of the recent presentation by Harrison and Leeman (arXiv:2609.17650v01 and arXiv:2609.17650v02) of the proof by Astra on the lower bound for differentially private continual counting. We believe a more natural and easy proof is possible and hope that this note will help in that effort. Prior to the initial preprint by Harrison and Leeman (arXiv:2609.17650v01), Bairaktari and Larsen (arXiv:2607.00876) gave an elegant proof to show a lower bound of $\Omega(\log^{3/2}(n))$ for both pure and approximate-DP continual counting, and in personal communication had informed us that they have a proof of optimal $\Omega(\log^{2}(n))$ for pure-differential private continual counting as well. They have subsequently published their $\Omega(\log^{2}(n))$ bound, which is now a joint work of Bairaktari, Dahl, and Larsen (arXiv:2607.00876v3). Their new result is an elegant extension of their technique for approximate-differential privacy. Although the two proofs are technically different, the Astra argument uses related tree geometry introduced in Bairaktari and Larsen.

1. Introduction

This note presents a rigorous, self-contained exposition of Harrison and Leeman’s presentation of a proof by ChatGPT 6 Astra for a lower bound on continual-counting error. It retains their notation for continuity and states the prefix-sum approximation problem.

1. Introduction

  • The note aims to make the proof accessible and rigorous, filling in claims left unproved in the preprint and reproducing three attributed proofs verbatim.The authors describe the work as an exposition, not a claim of intellectual merit.Source: §1 · p. 2
  • The note follows the notation of Harrison and Leeman, alongside the vector and matrix notation of Pillutla et al. [6].It also uses (a)+ = max{a, 0} for real a.Source: Notations · p. 2

Notations.

  • The mechanism maps a binary stream to an approximation of its prefix-sum vector.The stated problem is to study M: {0, 1}^n → R^n approximating A_nx.Source: Notations · p. 2

2. Proof overview and the roles of the main objects

The proof organizes a hidden-location hard instance, a local decoder, probe–potential pairs, and an exponential score. The score is bounded using accuracy and privacy arguments to obtain the claimed lower bound.

2. Proof overview and the roles of the main objects

  • A uniformly random bit vector X ∈ {0, 1}^m and independent uniformly random index J ∈ [m] define X′ = X ⊕ eJ; repeating each bit k times yields expanded streams differing exactly on the J-th coordinate block, and the adversary seeks J.Source: §2 · pp. 2–3
  • The local decoder labels one even and one odd outgoing edge as favored by comparing probes, short summaries of residuals on selected child intervals.Its goal is to identify which child of each parity is more likely to contain J.Source: §2 · p. 3
  • Probe–potential pairs connect local decoder mistakes to global error: potential decreases telescope over the tree, bounding path mistakes by root potential and then mechanism error.The score records partial success at each tree level and is selected to relate achievable accuracy to privacy loss.Source: §2 · p. 3

High Level Proof Overview.

  • The proof uses a score function and normalized and shifted residuals to connect the mechanism’s output to its accuracy and privacy bounds.The supplied overview identifies these objects but does not give their full equations here.Source: §2 · p. 3, High Level Proof Overview · p. 4
  • The proof combines accuracy and privacy bounds on an exponential score, then sets k = Θ(log(n/ε)) and H = Θ(log(n)) to obtain the claimed lower bound.The note says the two bounds are combined after applying Jensen’s inequality.Source: High Level Proof Overview · p. 4
  • The authors identify the score function, rather than the probe and potential, as the proof’s most innovative ingredient.They describe the probe and potential as natural choices for the corresponding error metrics.Source: High Level Proof Overview · p. 4

3. Preliminaries

The preliminaries set up the hard instance and tree-based decoder used in the proof. Probe–potential pairs, cross-parity comparisons, and an exponential score connect local decisions to accuracy and privacy.

3.1. Differential privacy.

  • Group privacy handles the expanded neighboring streams, which differ in k coordinates after one input bit is repeated across a block.Neighboring streams have Hamming distance one; the expansion raises the distance to k.Source: §3.1 · pp. 5–6

3.2. The hard instance and the shifted residual.

  • The hard instance flips a uniformly random bit at hidden index J and expands it into a block; the resulting residual is normalized error plus a ramp on I_J and a unit step afterward.The expanded streams differ exactly on I_J, with Hamming distance k.Source: §3.2 · pp. 6–7

3.3. The 4-ary tree.

  • A complete ordered 4-ary tree partitions the leaf indices into contiguous intervals, with each child corresponding to a stream-coordinate interval.If J lies in one child, its transition block lies within that child and outside the other three.Source: §3.3 · p. 8

3.4. Probe and potential functions.

  • The midrange–range pair supports the MaxSE bound, while the mean–variance pair supports the MeanSE bound.The proof uses probe functions for local decisions and corresponding potentials to relate shifted residuals to mechanism error.Source: §3.4 · p. 9

3.5. Decoder and Cross-parity rule.

  • Cross-parity chooses one favored child of each parity by probing opposite-parity children, so a path decision avoids probing the child containing J’s transition block.The probed intervals see only constant portions of the added signal, avoiding ramp contamination.Source: §3.5 · pp. 10–11

3.6. Why 4-ary tree?

  • The 4-ary structure supplies opposite-parity child pairs for comparisons and exactly two favored edges per node, yielding independent Bernoulli(1/2) non-favored path edges in the reference experiment.The authors note that this avoids the more complex two-level grandchild conditioning argument and linear-measurement privacy attack used in BL26, though the ramp contamination makes the proof more intricate.Source: §3.6 · p. 11

3.7. The exponential scoring function.

  • The exponential score for a leaf is multiplied by e^-τ for each non-favored edge on its root-to-leaf path.It equals 1 when every edge on that path is favored.Source: §3.7 · pp. 11–12

4. Accuracy lower bound

This section gives a detailed proof of the accuracy lower bound, making explicit how probe comparisons yield local errors and how potential decreases bound them.

4. Accuracy lower bound

  • For probes on intervals disjoint from the flipped block, translation equivariance makes the probe unchanged before the block and shifted by s after it.The proof spells out the disjointness and translation-equivariance steps used in Claim 17.Source: §4 · pp. 12–13
  • Lemma 16 states an accuracy lower bound under the Section 3.2 distributions for every τ > 0.The supplied statement does not include the bound's formula.Source: §4 · p. 12
  • Across the four equally likely positions of J within a node, a local error requires |d02| ≥ 1/2 or |d13| ≥ 1/2, with each condition receiving weight 1/2.Each threshold governs two of the four cases.Source: §4 · pp. 13–14
  • For the midrange potential, triangle inequality and midrange stability bound each probe difference by decreases in the parent and child potentials.The proof combines the two difference bounds with weight 1/2 each.Source: §4 · p. 14
  • For the mean potential, the proof bounds squared probe differences using the parallelogram inequality and the law of total variance.The bounds are summarized for both potentials with their respective leading constants.Source: §4 · pp. 14–15
  • Weighting each node by its probability of containing J makes internal-node potential terms cancel, leaving only root and leaf terms.Nonnegative leaf potentials then simplify the sum.Source: §4 · p. 15
  • Jensen's inequality and averaging over X and mechanism randomness complete the proof of the accuracy lower-bound lemma.The proof applies convexity to the exponential function before averaging.Source: §4 · p. 15

5. Privacy Upper Bound

This section proves a privacy upper bound by applying group privacy to expanded streams and establishing the independence needed to analyze the reference experiment's tree-path score.

5. Privacy Upper Bound

  • The proof makes explicit two steps implicit in the original preprint: uniformity of X′ and independence of non-favored edges along the tree path.These steps are established in Claims 23 and 24.Source: §5 · p. 16
  • Lemma 22 gives a privacy upper bound when M is (ε, δ)-DP, for every τ > 0 and either the midrange or mean probe.The supplied statement does not include the bound's formula.Source: §5 · p. 16
  • Flipping coordinate J changes k coordinates after block expansion, so group privacy compares the mechanism's outputs on the two expanded streams.The proof applies group privacy to a measurable score function and then averages over X and J.Source: §5 · p. 16
  • Because X′ is uniform and independent of J, and mechanism randomness is independent of (X, J), J is independent of the reference output Y′.Y′ is a deterministic function of X′ and mechanism randomness.Source: §5 · p. 17
  • Conditioned on Y′, the non-favored-edge indicators are independent Bernoulli(1/2) variables along the path in the fully balanced 4-ary tree.Uniform child choices give conditional probability 1/2 at every level, and the base-4 digits of J are independent across levels.Source: §5 · pp. 17–18
  • Averaging the score comparison and substituting the reference-experiment bound yields the claimed result with δk = δ(ekε − 1)/(eε − 1).The score bound is independent of the conditioned value y′.Source: §5 · p. 18

6. Proof of the lower bound

The proof bounds an exponential score from above using privacy and from below using accuracy, then applies Jensen’s inequality to derive error lower bounds. The argument also transfers the MeanSE bound to MaxSE and notes that the high-probability derivation is omitted.

6. Proof of the lower bound

  • The parameter choices use ℓ = min{⌊log_16(nε)⌋, log(ε/δ)} and k between ℓ/(16ε) and ℓ/(8ε), with nε sufficiently large.The stated assumption ensures h ≥ 12 and hence ℓ ≥ 12.Source: §6 · p. 18
  • The proof bounds the score expectation using the tree depth and group-privacy cost, with q between n/4 and n.It uses δ/ε ≤ e^-ℓ and kε ≤ ℓ/8 to control the additive group-privacy cost.Source: §6 · pp. 18–19
  • Combining the estimates gives E[Sϕ(J, Y)] ≤ e^-ℓ/16, completing the proof of the privacy upper bound used in the lower-bound argument.The proof then compares this score bound with a lower bound from accuracy.Source: §6 · p. 19
  • Jensen’s inequality converts the score bound into lower bounds on MaxSE and squared error by applying it to the corresponding error variables.The proof uses c = 4τ/k for MaxSE and c = 16τ/k^2 for squared error.Source: §6 · p. 19
  • Averaging over the encoded input distribution lower-bounds the worst-case error, and nonnegative squared errors give the MeanSE bound from the aggregate estimate.The embedding is injective, and the proof uses q ≥ n/4 in the aggregate squared-error step.Source: §6 · pp. 19–20
  • MaxSE inherits the MeanSE lower bound because the maximum squared coordinate error is at least its average; the high-probability derivation is omitted here.The note says the preprint obtains its high-probability bound by standard Markov’s inequality and omits the details.Source: §6 · p. 20

7. Further Discussion

The discussion examines why the proof uses a 4-ary tree, cross-parity probes, an exponential score, and a probe–potential pair. It identifies unresolved alternatives while explaining how these choices support the argument.

7. Further Discussion

  • Non-power-of-two arities lack the clean symmetric-random-walk representation; whether 4-ary trees are necessary remains open.The discussion mentions 3-ary and 19-ary alternatives but says their usefulness in this proof is unclear.Source: §7 · p. 21
  • Cross-parity probes avoid the target child, preventing exposure of the ramp that would break translation equivariance and the reduction to normalized error.The note identifies this as the point where residual decomposition, tree geometry, and translation equivariance interact.Source: §7 · p. 21
  • The exponential score’s reference expectation decays exponentially, allowing that decay to dominate privacy cost while preserving a Jensen lower bound on local mistakes.A linear score has expectation of order H, which becomes too costly after multiplication by e^(kε).Source: §7 · p. 21
  • The probe–potential pair handles metric-specific mistake changes: lost range controls nested midranges, while total variance controls differences of child means.This modularity supports using one hard distribution and privacy argument for both MaxSE and MeanSE lower bounds.Source: §7 · p. 21
Loading 2609.28528v1…