Skirting Additive Error Barriers for Private Turnstile Streams

Source: arXiv:2602.10360 · Published 2026-02-10 · By Anders Aamand, Justin Y. Chen, Sandeep Silwal

TL;DR

This paper studies private continual release in turnstile streams for two core statistics: the number of distinct elements and the second frequency moment F2. The motivating gap is that prior purely additive-error lower bounds are polynomial in the stream length T — notably an Ω(T^1/4) additive lower bound for distinct elements from Jain et al. (NeurIPS 2023), and an Ω(T) sensitivity lower bound for F2 — while the best-known upper bounds were also polynomial in T. The authors ask whether these barriers are artifacts of insisting on purely additive error.

Their main message is that the barriers can be bypassed if the algorithm is allowed mixed multiplicative + additive error. For distinct elements, they give event-level DP continual-release algorithms with polylog(T) multiplicative and polylog(T) additive error, using only polylogarithmic space. For F2, they similarly obtain 1+o(1) multiplicative error with polylog(T) additive error and polylogarithmic space. The conceptual move is to reduce the target statistic to a family of private continual counting problems over hashed buckets / reduced domains, so that the private counter noise becomes acceptable once the estimator is allowed to tolerate multiplicative slack.

Key findings

• Distinct elements: Theorem 3.1 gives an event-level (ε,δ)-DP continual-release algorithm with error (O(log^2 T / √ρ), O(log^2 T / √ρ)) under zCDP parameter ρ, and the paper states this is polylogarithmic multiplicative and additive error with probability 1-1/poly(T).
• Distinct elements space: Theorem 3.1 uses O(log n · log^2 T) space; the authors emphasize this is polylogarithmic, versus prior approaches that used polynomial space.
• Distinct elements general turnstile: Theorem 4.1 extends the mixed-error guarantee to general turnstile streams, with error (O(log^10 T), O(log^10 T)) and poly(T) space, again under event-level privacy.
• F2: Theorem 5.1 gives event-level DP continual F2 estimation with error (1+η, polylog(T,η,δ)/(ε^2 η^3)) and space polylog(T)/η^2.
• F2 improves over prior insertion-only work: compared with [EMM+23], which had (1+η, ˜O_η(log^7 T)) error and O(log^2 T/η^2) space in insertion-only streams, this paper extends to turnstile streams while improving the additive polylog exponent to ˜O_η(log^4 T).
• The paper explicitly notes that the best known purely additive error for distinct elements before this work was ˜O(T^1/3) [CEM+25], while the event-level lower bound is ˜Ω(T^1/4) [JKR+23]; their mixed-error result is non-trivial whenever the true distinct count is at most ˜O(T^1/3).
• Theorem 4.2 shows a reduction: if one had a DP continual distinct-elements algorithm with purely additive error n^0.99, then one could convert it into a (1+η)-multiplicative algorithm with poly(log T,1/η,1/ε,log(1/δ)) additive error.
• For distinct elements, the paper’s own min-hash-based strict-turnstile algorithm is limited by the possibility that a bucket’s mass comes from one heavy element or many singleton elements, which is why the multiplicative error is O(polylog T) rather than constant.

Threat model

The adversary is a non-adaptive stream chooser who can select a length-T turnstile sequence of updates, but cannot see or react to the algorithm’s internal randomness. Privacy is event-level: neighboring inputs differ in exactly one update. The algorithm must release a full prefix-by-prefix transcript while hiding the contribution of any single update. The paper does not model adaptive adversaries or malicious side information beyond standard DP.

Methodology — deep read

The threat model is event-level differential privacy for continual release over a fixed-length stream of T updates from a universe [n]. Neighboring datasets differ in exactly one update (a_i,s_i), while the stream itself is chosen non-adaptively, independent of the algorithm’s randomness. The algorithms must output an estimate after every timestep and guarantee that the entire released transcript is private. The paper also distinguishes strict turnstile streams, where frequencies never go negative, from general turnstile streams, where they can. The two main targets are the number of distinct nonzero-frequency items, ||x_t||_0, and the second frequency moment F2 = sum_j x_t[j]^2.

The data model is standard streaming notation: an update sequence (a_1,s_1),...,(a_T,s_T) with a_i in [n] and s_i in {-1,0,1}. For distinct elements, the stream statistic is the number of coordinates with nonzero frequency at time t; for F2, it is the squared ℓ2 norm of the frequency vector. The paper assumes n and T are known up to constant factors and, for convenience, takes n = poly(T). There is no empirical dataset here; the “data” are worst-case streams. Reproducibility is therefore algorithmic rather than experimental: the paper provides algorithms, theorem statements, and proofs, but no trained models, no benchmark suite, and no code release is mentioned in the provided text.

The core algorithmic idea for distinct elements is a private version of min-hash / trailing-zero bucketing. A pairwise-independent hash h:[n]→[n] is sampled, and each item is assigned to a bucket k = lsb(h(a)), the index of the least significant non-zero bit of its hash. For a set of D distinct items, bucket occupancy grows geometrically in expectation with k, so the largest non-empty bucket index reveals log D in the non-private setting. Because exact bucket counts would leak privacy, the authors maintain a private continual counter C[k] for every bucket k using the Gaussian binary tree mechanism (Theorem 2.1), which gives ρ-zCDP and O(log^{1.5} T / √ρ) additive error with high probability. The first strict-turnstile algorithm (Algorithm 1) simply finds the largest bucket whose private count exceeds a threshold τ set to the high-probability counter noise level, then outputs 2^ℓ. To reduce variance, Algorithm 2 runs m = Θ(log T) independent copies and returns the median. This yields the stated O(log^2 T / √ρ) multiplicative and additive errors. A concrete example: if the true distinct count is around 2^20, the algorithm expects the highest occupied bucket near index 20; because the private counters are noisy, it instead looks for the highest bucket whose estimated count is above the noise floor. If bucket 20 is obscured but bucket 18 is clearly above threshold, the output 2^18 is within the polylog multiplicative factor. The analysis explicitly notes the failure mode: a bucket count above threshold might arise either from many low-frequency items or from one heavy element, which is why the method cannot reach constant multiplicative error.

For general turnstile distinct elements, the paper switches to a domain-reduction strategy. Instead of trying to identify the max occupied bucket, it hashes the universe down to a smaller domain in which collisions become informative, and then uses private continual counting to detect those collisions. The reduced domain size acts as a proxy for the number of distinct elements. This version is less space-efficient and has weaker polylog factors (Theorem 4.1 gives O(log^10 T) multiplicative and additive error and poly(T) space), but it applies to general turnstile streams. Section 4 also proves Theorem 4.2, a reduction showing that any algorithm with purely additive error substantially below n can be transformed into one with (1+η) multiplicative error and polylog additive error. This is not an implementation detail so much as a structural statement: it formalizes that once you can beat the trivial additive scale n, multiplicative approximation can be recovered via hashing/domain reduction.

For F2 estimation, the method is qualitatively similar but uses a Johnson–Lindenstrauss (JL) reduction. The frequency vector x_t is projected with a random Rademacher matrix A of dimension m×n, with m chosen to preserve ||x_t||_2^2 up to a (1±α) factor. The algorithm then privately tracks the reduced coordinates with continual counters and reconstructs an estimate of F2 from the projected norm. The paper proves that allowing a small multiplicative slack 1+η lets the additive error drop from the trivial Ω(T) sensitivity barrier to polylogarithmic in T, with dependence polylog(T,η,δ)/(ε^2 η^3) and space polylog(T)/η^2. The proof relies on the fact that the reduced representation is small enough that continual counting noise can be absorbed into the multiplicative tolerance.

Evaluation is entirely theoretical. The metrics are mixed error pairs (α,β), interpreted as Y_t/p - r ≤ Ŷ_t ≤ qY_t + s with pq=α and r+s=β, holding for all t with probability at least 1-γ. The main baselines are prior continual-release algorithms and lower bounds from [JKR+23], [CEM+25], and [EMM+23]. For distinct elements, the paper compares against the best-known purely additive upper bound ˜O(T^1/3) and the event-level lower bound ˜Ω(T^1/4), and notes that their mixed-error guarantee is better whenever the true distinct count is at most ˜O(T^1/3). For F2, they compare against [EMM+23], which only handled insertion-only streams. The paper also points out that in the sublinear-space regime, multiplicative error is unavoidable even without privacy, reinforcing that their use of multiplicative slack is not an artifact of privacy alone.

Technical innovations

• A private continual-release distinct-elements estimator based on min-hash style trailing-zero bucketing plus one private counter per bucket, turning a hard direct estimation problem into a collection of private counting problems.
• A second distinct-elements algorithm for general turnstile streams via hash-based domain reduction and collision detection, yielding polylogarithmic mixed error under event-level DP.
• A mixed-error perspective formalized as (α,β) continual estimation, used to bypass purely additive lower bounds that apply even when constant multiplicative error is not ruled out.
• A turnstile F2 estimator that combines a Johnson–Lindenstrauss projection with private continual counting to achieve 1+o(1) multiplicative error and polylog additive error.

Baselines vs proposed

• [JKR+23] distinct elements lower bound: additive error = Ω(T^1/4) vs proposed: O(log^2 T / √ρ) additive and multiplicative error of the same order under Theorem 3.1
• [CEM+25] distinct elements upper bound: error = (1+η, ˜O_η(T^1/3)) vs proposed: (O(log^2 T / √ρ), O(log^2 T / √ρ)) for strict turnstile and (O(log^10 T), O(log^10 T)) for general turnstile
• [EMM+23] F2 insertion-only: error = (1+η, ˜O_η(log^7 T)) and space = O(log^2 T/η^2) vs proposed: (1+η, polylog(T,η,δ)/(ε^2 η^3)) and space = polylog(T)/η^2
• [JRSS23] recomputation-based turnstile distinct elements: error = (1, ˜O(T^1/3)) with linear space vs proposed: mixed-error polylog bounds with polylogarithmic space in the strict-turnstile algorithm
• [JKR+23] event-level distinct lower bound: additive error = ˜Ω(T^1/4) vs proposed: mixed multiplicative/additive polylog bounds

Limitations

• The best distinct-elements guarantee for general turnstile streams is still fairly weak in constants/exponents: Theorem 4.1 has O(log^10 T) multiplicative and additive error and poly(T) space, so the cleanest result is only for strict turnstile streams.
• The min-hash-style algorithm is restricted to strict turnstile streams; deletions that create negative frequencies break the direct bucket interpretation.
• The authors do not achieve constant multiplicative error for distinct elements; they explicitly identify a barrier where buckets cannot distinguish one heavy item from many singleton items.
• All results are worst-case theoretical guarantees with non-adaptive adversaries; there is no empirical validation, and no discussion of implementation stability under practical adversaries.
• The paper’s guarantees depend on the exact privacy accounting via zCDP-to-(ε,δ)-DP translation and on high-probability bounds for private counters; constants and practical utility are not characterized.
• The F2 result is asymptotic and theoretical; while it improves on prior work in the turnstile setting, the additive dependence polylog(T,η,δ)/(ε^2 η^3) could still be large for small η.

Open questions / follow-ons

• Can one obtain constant multiplicative error for distinct elements in private continual release without paying polynomial additive error or polynomial space?
• What is the correct quantitative tradeoff between multiplicative error 1+η and additive error for distinct elements and F2, especially the dependence on η?
• Can the reduction in Theorem 4.2 be sharpened to turn any o(n) purely additive algorithm into a near-constant multiplicative one with better space or better dependence on η?
• Can lower-bound techniques from concurrent work such as [AHSS25] be extended to pin down mixed-error tradeoffs for turnstile streams?

Why it matters for bot defense

For bot-defense practitioners, this paper is mainly relevant as a study in how privacy constraints interact with online measurement under continual release. The technical lesson is that once you must publish frequent noisy estimates, the choice of error model matters: a system that tolerates multiplicative slack can sometimes use much smaller additive noise and much less memory than one insisting on pure additive accuracy. In CAPTCHA or bot-detection telemetry, this suggests that if you are tracking evolving counts, distinct-user-like coverage, or second-moment-type concentration signals under privacy constraints, it may be better to redesign the estimator around thresholds, hashing, or reduced domains rather than try to privately release exact-ish counts directly. The paper also highlights a practical limitation: mixed-error methods can be very good when the statistic is not tiny, but they degrade when the true signal sits near the additive noise floor. So a defender would need to decide whether the signal of interest is usually “large enough” for multiplicative approximation to be meaningful, or whether exact low-count sensitivity is the real bottleneck.

Cite

@article{arxiv2602_10360,
  title={ Skirting Additive Error Barriers for Private Turnstile Streams },
  author={ Anders Aamand and Justin Y. Chen and Sandeep Silwal },
  journal={arXiv preprint arXiv:2602.10360},
  year={ 2026 },
  url={https://arxiv.org/abs/2602.10360}
}

Read the full paper

• arXiv:2602.10360 (abstract)
• arXiv:2602.10360 (PDF)