Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams

Source: arXiv:2607.06312 · Published 2026-07-07 · By Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou

TL;DR

This paper addresses a critical open problem in adversarially robust streaming algorithms for frequency moments estimation in the insertion-deletion (turnstile) model when updates can be chosen adaptively based on previous algorithm outputs. Prior works achieved accurate adversarially robust approximations only for the second frequency moment F2 with polylogarithmic space, while for other moments p in [0,2) (including the fundamental distinct elements problem F0), only constant-factor approximations were known in sublinear space. This work closes that gap by developing the first algorithms achieving (1+ε)-approximate adversarial robustness for all p in [0,2], including F0, with polylogarithmic space complexity. The techniques generalize the estimator-corrector-learner framework to non-Hilbert spaces by implicitly embedding inputs into L2, then running regularized kernel ridge regression over adaptively discovered "hard" queries, enabling efficient recursive estimation despite the lack of Euclidean structure for p ≠ 2. Beyond frequency moments, the approach extends to metric and information-theoretic quantities such as Earth Mover Distance, k-median clustering cost, and Shannon entropy. Additionally, the authors prove a novel weak equivalence theorem showing that efficient classical linear sketches exist if and only if efficient adversarially robust turnstile algorithms exist for any sub-multiplicative norm, up to polynomial factors, highlighting L1 embeddability as the fundamental geometry bridging classical sketching and robust adaptive streaming. The results significantly advance understanding of adversarial robustness in streaming and establish nearly optimal space complexity bounds matching classical non-adaptive streaming up to polynomial factors.

Key findings

• Achieves (1+ε)-approximate adversarially robust algorithms for all frequency moments Fp with p in [0,2], including F0, using poly(1/ε, log n) bits of space (Theorem 1.2).
• First adversarially robust polylogarithmic-space algorithm for the distinct elements problem (F0) with (1+ε)-multiplicative approximation.
• Extends the estimator-corrector-learner framework to non-Hilbert spaces by implicit isometric embedding into L2 and regularized kernel ridge regression over adaptively chosen queries.
• Demonstrates that approximate Earth Mover Distance (EMD) and k-median clustering cost over [Δ]^d can be estimated adversarially robustly within O(d log Δ)-factor approximation using poly(d, log(mΔ)) space.
• Provides adversarially robust algorithms for ε-additive approximation of Shannon entropy in insertion-deletion streams using poly(1/ε, log n) space (Theorem 1.6).
• Proves a weak equivalence theorem (Theorem 1.3) showing that the existence of efficient classical linear sketches for any sub-multiplicative norm implies the existence of efficient adversarially robust turnstile streaming algorithms and vice versa, up to polynomial factors.
• Shows that L1 embeddability is the fundamental geometric property underlying both classical oblivious sketching and adversarially robust streaming models.
• The robust algorithm’s space complexity matches classical non-adaptive streaming lower/upper bounds up to polynomial factors.

Threat model

The adversary can adaptively choose each update in the insertion-deletion stream based on all previous outputs and updates from the streaming algorithm, aiming to cause estimation errors or force the algorithm to consume large space. The adversary cannot break the algorithm’s internal randomness or force exponential space blowup beyond polynomial factors. The goal is to maintain accurate (1+ε)-approximate estimations at every step despite this fully adaptive adversary.

Methodology — deep read

1. Threat Model & Assumptions: The adversary is fully adaptive and can choose each stream update based on all previous algorithm outputs and updates. The model considered is the insertion-deletion (turnstile) streaming model where the frequency vector x evolves by increments and decrements. The algorithm must maintain accurate (1+ε)-approximate estimates of frequency moments Fp at every step with high probability, despite the adaptivity.

2. Data & Setting: The input is a stream of length m = poly(n), with each update (a_t, Δ_t) modifying coordinate a_t of the frequency vector x by Δ_t. The universe size is n. The algorithms maintain data structures in poly(1/ε, log n) bits of space.

3. Architecture & Algorithmic Framework: The approach generalizes the estimator-corrector-learner paradigm previously developed for L2 (F2) estimation. This framework decomposes the frequency vector x as a sum of prefix and suffix vectors z and q, and maintains guesses z' for z that get updated when estimator outputs are inaccurate.

   • To handle p ≠ 2, the algorithm employs implicit isometric embeddings f mapping vectors under the L_p norm into a Hilbert space (L2). Specifically, for any vectors u, v, ||u - v||_p^p = ||f(u) - f(v)||_2^2.
   • Estimation of ||z - q||_p^p reduces to estimating squared L2 distances in the embedded space.
   • Updates to the guess vector correspond to projections onto the span of embedded "hard" queries where estimation errors occur.
   • Because the embedding is nonlinear and infinite-dimensional, the algorithm never explicitly materializes f(z) or f(q), but instead uses kernel methods (regularized kernel ridge regression) to work implicitly using inner product estimates obtained from F_p sketches.

4. Training Regime & Implementation Details: The algorithm maintains multiple F_p sketches to estimate norms and inner products of inputs and query differences. It uses a regularization parameter ν to keep the regression well-conditioned and bounds coefficients to control additive error. The overall estimator combines a hierarchy of additive-error algorithms at multiple scales to achieve a multiplicative (1+ε)-approximation uniformly over the stream.

5. Evaluation Protocol: Guarantees are proved theoretically with high probability over algorithm randomness. The estimator is shown to converge after O(1/ε^2 log n) updates to the guess vector. Space usage is poly(1/ε, log n) for streams of length poly(n). Results are compared to known classical streaming lower and upper bounds to establish near-optimality. The weak equivalence theorem between sketching and robustness is proved by reductions.

6. Reproducibility & Artifacts: The paper does not report publicly released code or weights as the focus is on theoretical algorithms and proofs. The techniques build on prior frameworks and kernel embedding theory. The underlying sketches (AMS-type) and kernel methods are classical. The embedding dimension can be high or infinite, but the method works by implicit computations.

A Concrete Example: For frequency moment p in [0,2), given an adaptive turnstile stream, the algorithm maintains multiple F_p sketches for different prefix and suffix differences. When the estimator outputs a value for ||z - q||_p^p that is inaccurate beyond a threshold, it triggers a learner update using kernel ridge regression over the embeddings of the previous ’hard’ queries to find a better projection v approximating f(z). By recursively estimating the norm ||v - f(q)||_2^2 using the same process and controlling errors with regularization and bounded coefficients, the algorithm achieves accurate approximation despite adaptivity and nonlinearity of embeddings. This improves over prior work which could only handle p=2 robustly or provide constant-factor approximations for p≠2.

Technical innovations

• Generalization of the estimator-corrector-learner framework from L2 to all Lp norms with p in [0,2) via implicit isometric embedding into L2.
• Use of regularized kernel ridge regression over adaptively discovered hard queries to simulate projections in the embedded Hilbert space without explicit vector materialization.
• A novel recursive estimator decomposition that breaks down the Lp norm approximation into estimations using Fp sketches and inner products in the embedded space.
• The weak equivalence theorem formally linking classical oblivious linear sketching and adversarially robust streaming algorithms via L1 embeddability, providing a unifying framework relating robustness and sketching.

Baselines vs proposed

• Prior adversarially robust F2 approximation algorithms: poly(1/ε, log n) space (known) vs. proposed for p ≠ 2: also poly(1/ε, log n) space with (1+ε)-approximation
• Prior F0 (distinct elements) adversarially robust algorithms: constant-factor approximation in sublinear space vs. proposed: (1+ε)-approximation in polylogarithmic space
• Classical non-adaptive streaming Fp moment estimation: Θ(1/ε^2 log n) bits space bounds vs. proposed adversarial robust algorithms: matching poly(1/ε, log n) bits space up to polynomial factors
• Earth Mover Distance approximations: non-robust approximations known with O(d log Δ) distortion vs. proposed robust algorithm: O(d log Δ)-approximation in poly(d, log(mΔ)) space
• Shannon entropy estimation: classical sublinear algorithms with ε-additive error vs. proposed: adversarially robust ε-additive error with poly(1/ε, log n) space

Limitations

• The embedding f(·) into L2 is implicit and may have very high or infinite dimension, complicating practical implementations.
• The algorithm’s polynomial factors in 1/ε and log n may be large, potentially limiting efficiency for very small ε or very large n.
• No empirical evaluation or performance benchmarks are provided, making it unclear how the method performs in practice.
• The adversarial model assumes fully adaptive adversaries but does not consider additional constraints or side-channel attacks.
• The equivalence theorem is 'weak' and holds up to polynomial factors, so practical transformations between robust sketches and classical sketches may not preserve optimal constants.
• The approach relies on norm bounds and assumptions that the frequency vectors stay within polynomial bounds, which may not hold in some streams.

Open questions / follow-ons

• Can the proposed framework be extended beyond p in [0,2] to achieve robust approximations for frequency moments with p>2 under adaptive updates?
• Can practical implementations and empirical evaluations validate the efficiency and accuracy of the implicit kernel embedding approach in real-world data streams?
• Are there stronger equivalence results linking robustness and sketching beyond polynomial loss, yielding tighter theoretical or practical reductions?
• How do the techniques generalize to other complex streaming problems involving structured data or graph streams under adversarial adaptivity?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, this work provides fundamental insight into the limits and possibilities of adversarial robustness for streaming data and sketch-based algorithms under adaptive attacks. Frequency moment estimation and distinct elements computation are closely related to counting and detection tasks in network traffic monitoring and bot activity analysis. The paper demonstrates that strong robustness guarantees with near-classical space efficiency are achievable even when inputs adapt to past outputs, which parallels the adaptive nature of attackers probing defenses. Additionally, the equivalence theorem clarifies when classical sketching techniques can be safely leveraged in adversarial environments and when new robust methods are required. These results can guide principled design of robust subsampling, counting, and state summarization components deployed in CAPTCHA rate limiting or bot traffic signature discovery, where adversaries continuously adapt queries. However, practical adoption would require implementing the implicit embeddings and kernel regression efficiently and evaluating overheads against deployed traffic scales.

Cite

@article{arxiv2607_06312,
  title={ Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams },
  author={ Elena Gribelyuk and Honghao Lin and David P. Woodruff and Huacheng Yu and Samson Zhou },
  journal={arXiv preprint arXiv:2607.06312},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.06312}
}

Read the full paper

• arXiv:2607.06312 (abstract)
• arXiv:2607.06312 (PDF)