Tight Lower Bounds for Differentially Private Continual Counting Charlie Harrison Google
Ethan Leeman Google Research
arXiv:2609.17650v1 [cs.DS] 15 Sep 2026
September 17, 2026
Abstract 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 < ε ≤ 1, we prove asymptotically tight lower bounds of Ω(log2 n) for worst-case expected ℓ∞ error and Ω(log3 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 δ ≤ 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 δ ≪ 1/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
Differential privacy (DP) [DMNS06] provides rigorous privacy guarantees for randomized data analysis. We study the problem of private continual counting [DNPR10, CSS11]. Given a private bitstream x ∈ {0, 1}n , the mechanism must continually release estimates of all prefix sums (An x)t = Pt n×n is the lower-triangular all-ones matrix. We consider this problem i=1 xi , where An ∈ {0, 1} under both ℓ∞ and squared error notions. We begin with the former: α∞ (M ) = max n EM [∥M (x) − An x∥∞ ]. x∈{0,1}
The private continual counting problem has a rich history. It was introduced concurrently by Dwork et al. [DNPR10] and Chan, Shi, and Song [CSS11], who independently proposed the celebrated 1 O(log2 n) error Binary Tree Mechanism (BTM). When instantiated with Laplace noise it satisfies p 3/2 under pure ε-DP, while its Gaussian analogue can achieve O(log (n) log(1/δ)) error under approximate (ε, δ)-DP. Dwork et al. also established an initial Ω(log n) lower bound for α∞ under pure DP. This lower bound was state of the art until the recent breakthrough of Bairaktari and Larsen [BL26], who proved an unrestricted Ω(log3/2 n) lower bound under both privacy regimes. When δ = Θ(1) is sufficiently small, their work settles the complexity of continual counting for α∞ . However, for pure 1
In this section we suppress dependence on ε for sake of presentation.
1
√ DP and for standard regimes of approximate DP where δ ≤ n−Ω(1) , a log n gap has remained open. Beyond ℓ∞ error, continual counting is also studied under squared error notions "
MeanSE(M ) = max n EM x∈{0,1}
n 1X (M (x)t − (An x)t )2 , n t=1
#
h
i
MaxSE(M ) = max n max EM (M (x)t − (An x)t )2 . x∈{0,1} t∈[n]
MeanSE is of particular importance in machine learning, where continual counting is used as a foundational privacy primitive (e.g., [KMS+ 21]). Note that MaxSE ≥ MeanSE, so any lower bounds on MeanSE automatically transfer. BTM satisfies O(log3 n) error for either metric when instantiated with Laplace noise. Under approximate DP, tight bounds of Θ(log2 n) were given by Henzinger, Upadhyay, and Upadhyay [HUU23] under MeanSE for arbitrary mechanisms when δ is fixed. Their upper bound uses a Gaussian instantiation of the matrix-mechanism framework [LHR+ 10], and follow-up work improved additive constants in their factorization bounds, without changing their asymptotic order [HU25, HKU26]. The Ω(log2 n) lower bound also applies to pure DP, leaving a log n gap relative to the O(log3 n) upper bound. Recent work has investigated this gap within the restricted class of Laplace-based matrix mechanisms whose bounds can be reduced to studying properties of matrix factorization costs. Tight results are known for binary factorizations [AK26] and, up to polyloglog factors, for MaxSE under arbitrary real factorizations [LMW26, BKM+ 26]. Bhowmik and Hasan [BH26] obtained tight Θ(log3 n) bounds for both MeanSE and MaxSE in this class, resolving the matrix mechanism restricted class but leaving the unrestricted-mechanism question open where a log n gap persists. Lastly, [FHU22] provide a lower bound for the worst-case expected squared ℓ∞ error B∞ (M ) = maxx∈{0,1}n EM [∥M (x) − An x∥2∞ ] for data-independent mechanisms. Jensen’s inequality yields 2 (M ) so our lower bounds on α B∞ (M ) ≥ α∞ ∞ immediately yield lower bounds on B∞ over all mechanisms. We omit a separate discussion of this metric for sake of brevity.
1.1
Our contributions
√ Under both pure DP and approximate DP with δ = n−Ω(1) , we close the log n gap for continual counting under α∞ , as well as the log n gap for MeanSE (and hence MaxSE). Both lower bounds hold for arbitrary mechanisms. Theorem 1. Let 0 < ε ≤ 1. Then there exist absolute constants c, C0 , C1 > 0 such that if nε ≥ C0 and ε/δ ≥ C1 and M an (ε, δ)-DP mechanism for binary prefix sums, then log(nε) ε α∞ (M ) ≥ c min log(nε), log . ε δ log(nε) ε MaxSE(M ) ≥ MeanSE(M ) ≥ c min2 log(nε), log . 2 ε δ
With log(ε/0) = +∞, this gives the pure-DP bound Ω(log2 (nε)/ε) and Ω(log3 (nε)/ε2 ), respectively.
2
While previous work resolved the fixed δ = Θ(1) regime, arguably the δ = n−Ω(1) regime is more natural. Indeed, in the DP literature, it is commonly recommended to set δ ≪ 1/n [DR14, Vad17, NDLH25], to limit the risk of catastrophic privacy failure.2 In this regime, our lower bounds establish that BTM instantiated with Laplace noise is asymptotically optimal under all three error notions, even under approximate DP. This aligns with the observations of [APST25], whose improved pure-DP mechanism achieves a smaller mean squared error bound than the Gaussian matrix mechanism of [HUU23] for sufficiently small δ. Our bounds hold even in the easier offline setting [CLN+ 24] where the entire stream is known in advance, and therefore also apply to the online setting. Regime of δ δ=0 δ ≤ n−Ω(1) δ = Θ(1)
α∞ Θ(log2 n) Θ(log2 n) Θ(log3/2 n)
Ref Theorem 1 Theorem 1 [BL26]
MeanSE/MaxSE Θ(log3 n) Θ(log3 n) Θ(log2 n)
Ref Theorem 1 Theorem 1 [HUU23]
Table 1: Tight bounds for α∞ , MaxSE, and MeanSE across various regimes of δ for arbitrary mechanisms assuming 0 < ε ≤ 1 is fixed. The δ = Θ(1) regime applies to a small enough fixed δ in order to satisfy assumptions in [BL26, Theorem 1] or [HUU23, Theorem 4]. Previously only the δ = Θ(1) case was completely characterized, and we complete the understanding for 0 ≤ δ ≤ n−Ω(1) . Note there are still open gaps in the n−o(1) ≤ δ = o(1) regime. √ Note that while our lower bounds in this region improve the state of the art when log(1/δ) = ω( log n) for all error notions, we do not prove tightness. Our technique. Our approach uses a similar tree geometry to that of [BL26]. Here we construct a 4-ary tree T and a heuristic for labeling half the edges as more or less likely to contain differing examples based on numerical probes of the 4 children. We relate how well these edge labelings reveal the placement of the differing examples to both the accuracy of the mechanism and its privacy claims: an accurate mechanism will have probes that rarely mislabel edges, while privacy bounds how well those edges can be labeled. Specifically, the labeled edges give rise to a scoring function, whose expectation can be directly compared to both the expected error as well as the privacy parameters. For δ ≤ n−a , with fixed a > 0, this permits nontrivial group-privacy comparisons between streams differing in Θ(log n) bits, exploiting the stronger privacy guarantees in this regime beyond what the moment constraints of [BL26] capture.
2
Preliminaries
All unadorned logarithms are natural. We write [d] := {1, . . . , d} and 1 ∈ Rd as the all-ones vector. For a vector v ∈ Rd and t ∈ [d], write v[t] := (v1 , . . . , vt ) ∈ Rt for the restriction of v to its first t coordinates. Privacy. We begin by formalizing the privacy notion specific to our setting and stating a useful group privacy lemma. 2 The aptly named “catastrophe mechanism” releases the raw data of a single person at random, yet it trivially achieves (0, 1/n)-DP.
3
Definition 2 ([DR14]). A randomized mechanism M : {0, 1}n → Y satisfies (ε, δ)-differential privacy (DP) if Pr(M (x) ∈ S) ≤ eε Pr(M (x′ ) ∈ S) + δ for all x, x′ ∈ {0, 1}n with Hamming distance dH (x, x′ ) ≤ 1 and all measurable S ⊆ Y. When δ = 0, M satisfies pure ε-DP. Lemma 3 (Group privacy). If M is (ε, δ)-DP, then for any x, x′ ∈ {0, 1}n with dH (x, x′ ) ≤ k and any measurable test function f : Y → [0, 1], E[f (M (x))] ≤ ekε E[f (M (x′ ))] + δ
ekε − 1 . eε − 1
kε
−1 We sometimes write δk = δ eeε −1 for brevity.
Proof. For indicator tests f = 1S , the claim follows by standard induction over a k-step neighboring path in {0, 1}n . For general f : Y → [0, 1], layer-cake representation gives E[f (M (x))] = R1 0 Pr(f (M (x)) > t) dt. Applying the indicator bound to the level sets St = {y ∈ Y : f (y) > t} and integrating over t ∈ [0, 1] yields the claim. Probe and potential functions. For v ∈ Rd and non-empty u ⊆ [d], a probe assigns a representative value to the coordinates (vi )i∈u , while its associated potential measures their spread. We use two probe–potential pairs: {mean, variance} and {midrange, range}. Probe 1 mean = µu (v) = |u|
Use-case
Potential 1 Vu (v) = |u|
P
i∈u vi
mid = cu (v) = 21 (maxi∈u vi + mini∈u vi )
2 i∈u (vi − µu (v))
P
ru (v) = maxi∈u vi − mini∈u vi
MeanSE bounds α∞ bounds
Both potentials are nonnegative. Both probes are translation equivariant, while their potentials are translation invariant: for either pair (ϕ, P ) ∈ {(µ, V ), (c, r)} and any a ∈ R, ϕu (v + a1) = ϕu (v) + a,
Pu (v + a1) = Pu (v).
We will use the following lemmas relating probes with their associated potentials. Lemma 4 (Midrange stability). For any v ∈ Rd and non-empty u′ ⊆ u ⊆ [d], ru (v) − ru′ (v) . 2 Proof. From u′ ⊆ u, we have mini∈u vi ≤ mini∈u′ vi and maxi∈u′ vi ≤ maxi∈u vi . Now suppressing the argument v, this can be written as: |cu′ (v) − cu (v)| ≤
[cu′ − ru′ /2, cu′ + ru′ /2] ⊆ [cu − ru /2, cu + ru /2]. Comparing either of the endpoints gives |cu′ − cu | ≤ (ru − ru′ )/2. Lemma 5 (Law of total variance). Let v ∈ Rd , and let u1 , . . . , uB partition a non-empty set u ⊆ [d] into non-empty parts. Writing wi = |ui |/|u|, we have Vu (v) −
B X i=1
wi Vui (v) =
B X
2
wi µui (v) − µu (v) .
i=1
Proof. For j ∈ ui , expand vj − µu (v) = (vj − µui (v)) + (µui (v) − µu (v)). Summing squares over each P part eliminates the cross terms, since j∈ui (vj − µui (v)) = 0. Dividing by |u| gives the identity. 4
3
Our lower bounds
3.1
Proof overview
Our dataset instances are defined on an active prefix of length q = k4H ≤ n (with coordinates beyond q padded with zeros), partitioned into m = 4H blocks of size k, with each k-block corresponding to a leaf of a complete 4-ary tree of height H. To construct the instance, sample X ∼ Uniform({0, 1}m ), apply Ek which repeats each bit k times. Comparison inputs are formed by choosing an independent uniform leaf J and flipping its bit, giving X ′ = X ⊕ eJ and Ek (X ′ ). The central quantity in our proof is the expected score E[S(J, Y )] of the target leaf J, evaluated (W −An E (X ′ ))
k [q] on the shifted residual Y = , where W = M (Ek (X)). Crucially, Y compares the k mechanism output on the original stream X against the exact prefix sums of the flipped stream X ′ . Because the mechanism answered queries for X but Y subtracts X ′ , the residual decomposes into the mechanism’s normalized error plus an exact signed step signal of magnitude ±1 whose transition lies inside block J. Our scoring function S observes all levels in the hierarchy and is designed to apply a penalty whenever this signed step is not observed. At each internal node u, we label its children {u0 , u1 , u2 , u3 } from left to right. We then mark the edge to exactly one even and one odd child as “favored” to include J. For example, for the odd child we observe a threshold on the probe function |ϕu2 − ϕu0 | to determine whether to favor u1 vs. u3 . If the probe difference is small (< 1/2), it is unlikely that J is in the node between those probes. Using opposite-parity probes ensures that the comparison relevant to the path-to-J edge avoids the changed block J itself and sees either no shift or a signed unit shift. Our score is defined as S = e−τ N where N counts non-favored edges on the path to J. The lower bound then proceeds by sandwiching E[S(J, Y )] from both sides:
• Accuracy lower bound (Lemma 6): Because Y contains the step signal, the decoder scores J highly unless the mechanism makes large errors. We charge mistakes to a telescoping potential and apply Jensen’s inequality to obtain E[S(J, Y )] ≥ e−O(τ ·Error) . • Privacy upper bound (Lemma 7): By group privacy, replacing the mechanism input Ek (X) with the flipped input Ek (X ′ ) bounds E[S(J, Y )] ≤ ekε E[S(J, Y ′ )] + δk , where Y ′ = (M (Ek (X ′ )) − An Ek (X ′ ))[q] /k. In this reference run, Y ′ has zero step signal. Furthermore, since X ′ is statistically independent of J, Y ′ carries no information about J, forcing N (J, Y ′ ) ∼ Binomial(H, 1/2) and yielding the exponentially small score E[S(J, Y ′ )] = ((1 + e−τ )/2)H . Balancing the accuracy lower bound against the privacy upper bound forces the mechanism error to be large, establishing the tight lower bounds. The same recipe works for α∞ as well as MeanSE. The only difference is which probe and potential functions are used. Intuition: a betting game. We can think of a player participating in a betting game over the shifted instance, where their winnings are proportional to their bet on the target leaf J. The goal of the player is to maximize the expected payoff. The player’s strategy is to use probes to direct larger bets toward leaves that are more likely to contain J. As they descend down the tree, they divide the pot proportionally where favored edges get weight 1 and non-favored edges get weight e−τ . τ > 0 is a fixed parameter that indicates how much the player trusts the probes, directing larger bets along the favored edges. This fixes a (possibly non-optimal) player who bets proportional to the score S(i, Y ) on the ith leaf. Their expected payoff is then proportional to E[S(J, Y )], the score on the 5
target leaf. Their expected winnings are bounded from below by the accuracy claim and bounded from above by the privacy claim. nonfavored: e−τ
favored: 1
depth
true path
[m]
0 u0
1
probe: +0
u1
u2
u3
probe: +s
2 H=3
j
S(j, y) = e−τ N (j,y) , where N (j, y) counts nonfavored path edges.
Figure 1: Whole-tree decoder (H = 3 shown). Each internal node favors one child per parity. Our privacy and accuracy bounds are obtained from analyzing the expected score of J against a residual which includes the signed shift.
3.2
Tree setup and definitions
Let m, k, n be positive integers such that q := km ≤ n, where m = 4H for an integer H ≥ 1. We define the following components: • Expansion operator: Ek : {0, 1}m → {0, 1}n repeats each bit k times and applies padding3 when q < n: ( x⌈t/k⌉ if 1 ≤ t ≤ q, (Ek (x))t = 0 if q < t ≤ n. • The 4-ary tree T : The complete tree of height H. The root represents the full block index set [m]. Each internal node u corresponds to a block range [a, b] ⊆ [m] of length L = b − a + 1 (a power of 4), with four children partitioning [a, b] into quarters: u0 = [a, a + L/4 − 1],
u1 = [a + L/4, a + 2L/4 − 1],
u2 = [a + 2L/4, a + 3L/4 − 1],
u3 = [a + 3L/4, b].
Each leaf j ∈ [m] corresponds to the j-th coordinate block Ij = {(j − 1)k + 1, . . . , jk}. More S generally, each node u = [a, b] is associated with the stream coordinate interval Iu = bj=a Ij = {(a − 1)k + 1, . . . , bk} ⊆ [q]. For any vector y ∈ Rq , we write probe functions ϕ and potential functions P as ϕu (y) := ϕIu (y) and Pu (y) := PIu (y). • Favored edges: At each internal node u ∈ Tint , the decoder selects an even child eϕu (y) ∈ {u0 , u2 } and an odd child oϕu (y) ∈ {u1 , u3 } via the cross-parity rule: (
eϕu (y) =
u2 u0
if |ϕu1 (y) − ϕu3 (y)| ≥ 1/2, if |ϕu1 (y) − ϕu3 (y)| < 1/2,
3
(
oϕu (y) =
u1 u3
if |ϕu0 (y) − ϕu2 (y)| ≥ 1/2, if |ϕu0 (y) − ϕu2 (y)| < 1/2.
This padding minimally affects our analysis. Our tree lemmas operate only on the elements covered by the tree, and the proof of Theorem 1 only needs q ≥ n/4 for the MeanSE analysis.
6
The set of favored edges across the entire tree is ϕ Efav (y) =
[ n
o
(u, eϕu (y)), (u, oϕu (y)) .
u∈Tint
• Non-favored edge count and score: Let path(j) denote the set of H parent-child pairs on the unique path from the root to leaf j. The number of non-favored edges along this path and the resulting score are ϕ Nϕ (j, y) = |path(j) \ Efav (y)|,
3.3
Sϕ (j, y) = e−τ Nϕ (j,y) .
Tree lemmas
Lemma 6 (Accuracy lower bound). Let n, H, k be positive integers with q = k4H ≤ n, and let m = 4H . Sample X ∼ Uniform({0, 1}m ) and J ∼ Uniform([m]), and set X ′ = X ⊕ eJ . Let M : {0, 1}n → Rn be a mechanism, let W = M (Ek (X)), and define the shifted residual Y = (W −An Ek (X ′ ))[q] . Then for any τ > 0, k
EX,J,M [Smid (J, Y )] ≥ EX,M [e−4τ R/k ], 2
EX,J,M [Smean (J, Y )] ≥ EX,M [e−16τ Q/k ], where R = ∥W − An Ek (X)∥∞ and Q = 1q
2 t≤q (W − An Ek (X))t .
P
Proof. Fix X, W and write the normalized (non-shifted) error Z=
(W − An Ek (X))[q] . k
The vector Y − Z is zero on blocks before J and equals s = 2XJ − 1 ∈ {−1, 1} on blocks after J. The probes used to select the edge toward J avoid block J itself. Define pϕu = Pr(the edge from u toward J is non-favored | J ∈ u, X, W ). J
Set d02 = ϕu2 (Z) − ϕu0 (Z) and d13 = ϕu3 (Z) − ϕu1 (Z). Conditioned on J ∈ u, the target index J falls into each child ui (i ∈ {0, 1, 2, 3}) with probability 1/4. When J ∈ u0 or J ∈ u3 , the shift s is identical across the two probed children, yielding an error if and only if the unshifted difference is large, i.e. |d| ≥ 1/2. When J ∈ u1 or J ∈ u2 , the shift creates an offset of magnitude |s| = 1, so a decision error requires |d + s| < 1/2, which implies |d| ≥ 1/2. Averaging over all four children gives pϕu =
3 1 1 1X Pr(error | J ∈ ui , X, W ) ≤ 1{|d02 |≥1/2} + 1{|d13 |≥1/2} . 4 i=0 2 2
For midranges, we use 12 1{|d|≥1/2} ≤ |d| for any d ∈ {d02 , d13 } to get pmid ≤ |cu2 (Z) − cu0 (Z)| + |cu3 (Z) − cu1 (Z)| u ≤
3 X
|cui (Z) − cu (Z)|
triangle inequality
i=0
7
3 1X ≤ 2 ru (Z) − ru (Z) . 4 i=0 i
!
Lemma 4
(1)
For means, we use 12 1{|d|≥1/2} ≤ 2d2 and (a − b)2 ≤ 2(a − c)2 + 2(b − c)2 with c = µu (Z) to yield pmean ≤4 u
3 X
(µui (Z) − µu (Z))2
Lemma 5
=
i=0
3 1X 16 Vu (Z) − Vu (Z) . 4 i=0 i
!
(2)
Let Cϕ = 2 if ϕ = mid and 16 if ϕ = mean. Since a node u is visited by J with probability |u|/m, the expected number of non-favored edges on J is given by (for either potential P ∈ {r, V }), EJ [Nϕ (J, Y ) | X, W ] =
X |u| pϕ
m
u∈Tint
u
3 X |u| |ui | Pu (Z) − Pu (Z) m m i i=0
!
≤ Cϕ
X u∈Tint
X |ℓ|
= Cϕ P[q] (Z) −
ℓ leaf
m
Equations (1) and (2)
!
Pℓ (Z)
telescoping sum
≤ Cϕ P[q] (Z)
since Pℓ (Z) ≥ 0
Q 1 2 Finally, r[q] (Z) ≤ 2∥Z∥∞ ≤ 2R t≤q Zt = k2 . Conditional Jensen gives k and V[q] (Z) ≤ q EJ [e−τ Nϕ | X, W ] ≥ e−τ EJ [Nϕ |X,W ] , and averaging over X and mechanism randomness M completes the proof.
P
Lemma 7 (Privacy upper bound). Let n, H, k be positive integers with k4H ≤ n, and M : {0, 1}n → Rn be an (ε, δ)-differentially private mechanism. Under the same distributions for X, J, and the residual Y defined in Lemma 6, we have for any τ > 0 and ϕ ∈ {mean, mid}: EX,J,M [Sϕ (J, Y )] ≤ e
1 + e−τ 2
kε
!H
+δ
ekε − 1 . eε − 1 (W ′ −An E (X ′ ))
k [q] . For fixed X = Proof. Let W ′ be a fresh run of M (Ek (X ′ )) with residual Y ′ = k ′ x, J = j, the encoded inputs Ek (x), Ek (x ) differ in k coordinates. Apply Lemma 3 to the fixed
bounded test w 7→ Sϕ (j,
(w−An Ek (x′ ))[q] ), then average over X, J: k ′
1 + e−τ 2
EX,J,M [Sϕ (J, Y )] ≤ e EX,J,M [Sϕ (J, Y )] + δk = e kε
kε
!H
+ δk .
For the equality, since X ′ and the mechanism randomness are jointly independent of J, the reference residual Y ′ is independent of J. Conditioned on any realization Y ′ = y, the target leaf J ∼ Uniform([m]) descends into each child with probability 1/4 at every step. Because exactly two children are favored at each node (for either choice of ϕ), the non-favored edge indicators at each level are independent Bernoulli(1/2) variables, so Nϕ (J, y) ∼ Binomial(H, 1/2) and h
EJ [Sϕ (J, y)] = EJ e
−τ Nϕ (J,y)
i
=
H X H i=0
! 1 H
i
Taking the expectation over Y ′ yields EX,J,M [Sϕ (J, Y ′ )] = 8
2
e
−τ i
1+e−τ 2
=
H
.
1 + e−τ 2
!H
.
3.4
Main result
Finally, we prove our main theorem by selecting probe rule ϕ = mid for α∞ and ϕ = mean for MeanSE. Proof of Theorem 1. Set h = ⌊log16 (nε)⌋, u = min{h, log(ε/δ)}, k = H = ⌊log4 (n/k)⌋ ,
q = k4H ,
u 8ε
, and let
τ = u/H.
We use the convention log(ε/0) = +∞. The assumptions imply h ≥ u ≥ 12 and u u ≤k≤ . 16ε 8ε h
h
16 Moreover, k4h ≤ h4 8ε ≤ ε ≤ n, so H ≥ h ≥ u, and hence 0 < τ ≤ 1. By the definition of H, we also have n/4 < q ≤ n. For 0 ≤ t ≤ 1, the elementary inequality e−t ≤ 1 − t/2 gives
1 + (1 − t/2) t 1 + e−t ≤ = 1 − ≤ e−t/4 . 2 2 4 Thus Lemma 7, together with eε − 1 ≥ ε, kε ≤ u/8, and δ/ε ≤ e−u , yields for either probe
EX,J,M [Sϕ (J, Y )] ≤ ekε e−Hτ /4 +
δ ε
≤ eu/8 e−u/4 + e−u ≤ 2e−u/8 ≤ e−u/16 , where the last inequality uses u ≥ 12 > 16 log 2. We combine this bound with Lemma 6. Using the definitions of R, Q defined there, we have EX,M [e−4τ R/k ] ≤ EX,J,M [Smid (J, Y )] ≤ e−u/16 , 2
EX,M [e−16τ Q/k ] ≤ EX,J,M [Smean (J, Y )] ≤ e−u/16 .
(3)
Applying Jensen’s inequality to each expression and using u = τ H, we obtain EX,M [R] ≥
kH , 64
EX,M [Q] ≥
k2 H . 256
Consequently, α∞ (M ) ≥ EX,M [R] ≥
kH log(nε) ε ≥c min log(nε), log 64 ε δ
.
for c > 0 sufficiently small. Since the full-stream mean squared error is at least q/n times the mean squared error on the active prefix, and our construction guarantees q ≥ n/4, we have q 1 k2 H log(nε) ε MeanSE(M ) ≥ EX,M [Q] ≥ · ≥c min2 log(nε), log 2 n 4 256 ε δ
again for c > 0 sufficiently small. The MaxSE bound follows from MaxSE ≥ MeanSE. 9
,
Our last result is a consequence of using Markov’s inequality on our exponential-moment inequalities in Equation (3) to achieve high probability lower bounds. Corollary 8 (High-probability lower bounds). Under the assumptions of Theorem 1, every (ε, δ)-DP mechanism M admits an input x such that, with probability at least 1 − 2e−u/32 , ∥M (x) − An x∥∞ >
1 k2 H ∥M (x) − An x∥22 > , n 2048
kH , 128
where u, k, H are as in its proof. For fixed ε, c > 0 and δ ≤ n−c , these give Ω(log2 n) and Ω(log3 n) orders with failure probability n−Ω(1) . Proof. Use X, W, R, Q from the proof of Theorem 1. Since τ H = u, Markov’s inequality, a union bound, and (3) give "
Pr
X,M
k2 H kH or Q ≤ R≤ 128 512
#
2
≤ eu/32 EX,M [e−4τ R/k ] + EX,M [e−16τ Q/k ] ≤ 2e−u/32 .
Moreover, q > n/4 implies
1 q 1 ∥W − An Ek (X)∥22 ≥ Q ≥ Q. n n 4
Thus both claimed error lower bounds hold simultaneously with probability at least 1 − 2e−u/32 over X and the mechanism’s randomness. Therefore a fixed input x exists with the same guarantee. For fixed ε, c > 0 and δ ≤ n−c , we have u, k, H = Θ(log n), giving the claimed asymptotic orders and failure probability.
4
Conclusion
Our work addresses private continual counting under pure DP and approximate DP in the small δ ≤ n−Ω(1) regime. We analyze both ℓ∞ error, as well as mean squared error and max per-coordinate squared error. For fixed 0 < ε ≤ 1, we prove tight lower bounds for these settings, allowing us to more fully characterize the private continual counting problem in terms of its dependence on n. It remains to close the gap in the regime of n−o(1) ≤ δ = o(1), where the achievable upper bound is given by the Gaussian BTM. Here the best lower bounds come from a combination of Theorem 1 and [BL26] and [HUU23] for α∞ and MeanSE, respectively. AI Disclosure. We used a combination of ChatGPT 6 Astra and Gemini 3.8 Flash to help discover key proof ingredients and aid in drafting, reviewing and editing. These tools were used interactively starting from the solution [BL26]. The human authors spent significant time making the argument as concise and clean as possible. The authors verified the correctness and originality of this work in the context of the rest of the literature.
10
References [AK26]
Pavel Arkhipov and Nikita P Kalinin. Improved error bounds for pure differentially private continual counting via matrix factorization. arXiv preprint arXiv:2607.08963, 2026.
[APST25] Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner, and Sahel Torkamani. Count on Your Elders: Laplace vs Gaussian Noise. In Mark Bun, editor, 6th Symposium on Foundations of Responsible Computing (FORC 2025), volume 329 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:24, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [BH26]
Awnon Bhowmik and Mahmudul Hasan. Costs of arbitrary real matrix factorizations for pure-dp continual counting. arXiv preprint arXiv:2607.28703, 2026.
[BKM+ 26] Jan Bulánek, Ravi Kumar, Raghu Meka, Jelani Nelson, and Tamas Sarlos. A matrix factorization approach in turnstile streaming. arXiv preprint arXiv:2607.28819, 2026. [BL26]
Konstantina Bairaktari and Kasper Green Larsen. The binary tree mechanism is optimal for approximate differentially private continual counting. arXiv preprint arXiv:2607.00876, 2026.
[CLN+ 24] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Lower bounds for differential privacy under continual observation and online threshold queries. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1200–1222. PMLR, 30 Jun–03 Jul 2024. [CSS11]
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3), November 2011.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, page 265–284, 2006. [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, page 715–724, New York, NY, USA, 2010. Association for Computing Machinery. [DR14]
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3–4):211–407, August 2014.
[FHU22]
Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained complexity of differentially private continual observation. arXiv preprint arXiv:2202.11205, 2022.
[HKU26]
Monika Henzinger, Nikita Kalinin, and Jalaj Upadhyay. Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting. In Huijia (Rachel) Lin, editor, 7th Symposium on Foundations of Responsible Computing (FORC 2026), volume 368 of Leibniz International Proceedings in Informatics 11
(LIPIcs), pages 5:1–5:1, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [HU25]
Monika Henzinger and Jalaj Upadhyay. Improved differentially private continual observation using group algebra. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2951–2970. SIAM, 2025.
[HUU23]
Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. In Proceedings of the 2023 Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 5003–5039. SIAM, 2023.
[KMS+ 21] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In International conference on machine learning, pages 5213–5225. PMLR, 2021. [LHR+ 10] Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’10, page 123–134, New York, NY, USA, 2010. Association for Computing Machinery. [LMW26] Honghao Lin, Vahab Mirrokni, and David P Woodruff. A near-optimal lower bound for prefix-matrix factorizations. arXiv preprint arXiv:2608.08238, 2026. [NDLH25] Joseph P Near, David Darais, Naomi Lefkovitz, and Gary S Howarth. Guidelines for evaluating differential privacy guarantees. Technical report, National Institute of Standards and Technology, Gaithersburg, MD, March 2025. [Vad17]
Salil Vadhan. The Complexity of Differential Privacy, pages 347–450. Springer, Yehuda Lindell, ed., 2017.
12