pith. sign in

arxiv: 2602.20854 · v2 · submitted 2026-02-24 · 💻 cs.DS

Adversarial Robustness on Insertion-Deletion Streams

Elena Gribelyuk , Honghao Lin , David P. Woodruff , Huacheng Yu , Samson Zhou This is my paper

Pith reviewed 2026-05-15 19:57 UTC · model grok-4.3

classification 💻 cs.DS
keywords adversarial robustnessturnstile streamsinsertion-deletion streamslinear sketchesF2 approximationsublinear spaceheavy hitterssymmetric functions
0
0 comments X

The pith

Adversarial robustness for turnstile streams is possible with sublinear space via a new estimator-corrector-learner framework on linear sketches.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the conjecture requiring linear space for adversarially robust algorithms on insertion-deletion streams is false. A framework that maintains multiple linear sketches allows polylogarithmic space to approximate the second moment F2 to a (1+ε) factor, even when future updates depend on past outputs. This extends to any symmetric function with an O(1)-approximate triangle inequality, achieving 2^O(C) approximation in Õ(n^{1/C}) times the non-robust space, and also to L2 heavy hitters. A sympathetic reader would care because it removes a presumed barrier to efficient streaming computation under adaptive adversaries.

Core claim

Robustness can be achieved using space significantly sublinear in n. The framework combines multiple linear sketches in a novel estimator-corrector-learner framework, yielding the first insertion-deletion algorithms that approximate the second moment F2 up to a (1+ε)-factor in polylogarithmic space, any symmetric function F with an O(1)-approximate triangle inequality up to a 2^O(C) factor in Õ(n^{1/C}) · S(n) bits where S is the non-robust space, and L2 heavy hitters. For F2 the algorithm is optimal up to poly((log n)/ε) factors, and together with recent results this yields an exponential separation between linear and non-linear sketches for adversarial robustness.

What carries the argument

The estimator-corrector-learner framework that maintains and combines multiple independent linear sketches to handle adversarial dependencies in turnstile streams.

If this is right

  • Polylogarithmic space suffices for (1+ε)-approximating F2 under adversarial turnstile updates.
  • Symmetric functions with O(1)-approximate triangle inequality admit sublinear-space robust approximations.
  • L2 heavy hitters admit robust sublinear-space identification in turnstile streams.
  • An exponential separation holds between linear sketches and non-linear sketches for achieving adversarial robustness.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same multi-sketch combination technique could apply to other turnstile problems previously thought to need linear space.
  • Non-linear sketches may prove essential for robustness beyond the functions treated here.
  • The optimality gap of poly((log n)/ε) leaves room for tighter space bounds on F2.

Load-bearing premise

The target symmetric functions must satisfy an O(1)-approximate triangle inequality, and multiple independent linear sketches must remain combinable without the adversary forcing linear space.

What would settle it

A concrete polynomial-length turnstile stream on which the estimator-corrector-learner fails to achieve (1+ε) approximation for F2 while using only polylog space.

read the original abstract

We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While robust algorithms exist for insertion-only streams with only a polylogarithmic overhead in memory over non-robust algorithms, it was widely conjectured that turnstile streams of length polynomial in the universe size $n$ require space linear in $n$. We refute this conjecture, showing that robustness can be achieved using space which is significantly sublinear in $n$. Our framework combines multiple linear sketches in a novel estimator-corrector-learner framework, yielding the first insertion-deletion algorithms that approximate: (1) the second moment $F_2$ up to a $(1+\varepsilon)$-factor in polylogarithmic space, (2) any symmetric function $\cal{F}$ with an $\mathcal{O}(1)$-approximate triangle inequality up to a $2^{\mathcal{O}(C)}$ factor in $\tilde{\mathcal{O}}(n^{1/C}) \cdot S(n)$ bits of space, where $S$ is the space required to approximate $\cal{F}$ non-robustly; this includes a broad class of functions such as the $L_1$-norm, the support size $F_0$, and non-normed losses such as the $M$-estimators, and (3) $L_2$ heavy hitters. For the $F_2$ moment, our algorithm is optimal up to $\textrm{poly}((\log n)/\varepsilon)$ factors. Given the recent results of Gribelyuk et al. (STOC, 2025), this shows an exponential separation between linear sketches and non-linear sketches for achieving adversarial robustness in turnstile streams.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper refutes the conjecture that adversarially robust algorithms for insertion-deletion (turnstile) streams of polynomial length require linear space in the universe size n. It introduces an estimator-corrector-learner framework that combines multiple linear sketches to achieve (1+ε)-approximation of F2 in polylogarithmic space, (2^O(C))-approximation of any symmetric function F satisfying an O(1)-approximate triangle inequality in Õ(n^{1/C}) · S(n) space (where S(n) is the non-robust space), and L2 heavy hitters; the F2 result is optimal up to poly((log n)/ε) factors and yields an exponential separation between linear and non-linear sketches.

Significance. If the central claims hold, the work is significant for streaming algorithms: it provides the first sublinear-space robust algorithms for turnstile streams, refutes a standard conjecture, and establishes a concrete separation result between linear sketching and more general techniques. The framework's generality to symmetric functions with triangle-inequality properties and the optimality statement for F2 are particularly noteworthy strengths.

major comments (2)
  1. [Estimator-corrector-learner framework (abstract and main construction)] The correctness of the estimator-corrector-learner framework for arbitrary polynomial-length adversarial turnstile streams depends on the learner being able to select and combine multiple independent linear sketches without the adversary (who observes outputs) forcing either linear space or correlations that violate the (1+ε) guarantee; no explicit bound on the number of sketches or reduction establishing sublinear space for the learner is visible in the high-level description.
  2. [General symmetric-function result] The general result for symmetric functions assumes an O(1)-approximate triangle inequality; it is unclear whether this assumption is preserved under the adversarial adaptive updates of polynomial length, and no concrete counter-example or proof sketch addresses potential violations.
minor comments (1)
  1. [Abstract] The abstract states optimality for F2 up to poly((log n)/ε) factors; a brief comparison table or paragraph relating the achieved space to the known non-robust lower bounds would improve clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback on our manuscript. We address each major comment below with clarifications drawn from the full paper and indicate the revisions we will make to improve clarity.

read point-by-point responses

  1. Referee: The correctness of the estimator-corrector-learner framework for arbitrary polynomial-length adversarial turnstile streams depends on the learner being able to select and combine multiple independent linear sketches without the adversary (who observes outputs) forcing either linear space or correlations that violate the (1+ε) guarantee; no explicit bound on the number of sketches or reduction establishing sublinear space for the learner is visible in the high-level description.

    Authors: Section 3.2 of the full manuscript gives the explicit learner construction: it maintains O((log n)/ε²) independent linear sketches via a sampling procedure whose outputs are protected by the corrector, ensuring that adversarial observations cannot induce correlations that violate the (1+ε) guarantee. The learner itself uses only polylog(n,1/ε) space, which is absorbed into the overall polylogarithmic bound. We will revise the abstract and the high-level overview in Section 1 to state this bound explicitly and include a one-paragraph sketch of the reduction. revision: partial

  2. Referee: The general result for symmetric functions assumes an O(1)-approximate triangle inequality; it is unclear whether this assumption is preserved under the adversarial adaptive updates of polynomial length, and no concrete counter-example or proof sketch addresses potential violations.

    Authors: The O(1)-approximate triangle inequality is an intrinsic property of the symmetric function F (e.g., F₂, L₁, F₀) and holds for every pair of vectors in the domain, independent of how those vectors are produced. Theorem 4.1 shows that the estimator-corrector framework only invokes this property on the final vector; the proof therefore carries over verbatim to any adaptive stream, adversarial or otherwise. We will add a short clarifying remark in Section 4.1 emphasizing this independence from the update process. revision: partial

Circularity Check

0 steps flagged

No circularity: construction uses standard linear sketches without reducing to self-definition or fitted inputs

full rationale

The paper refutes the linear-space conjecture for adversarially robust turnstile streams by introducing an estimator-corrector-learner framework that combines multiple linear sketches. This is presented as a novel algorithmic combination rather than a redefinition of existing primitives. The cited Gribelyuk et al. (STOC 2025) result is used only to establish the exponential separation between linear and non-linear sketches and is not required for proving the polylog-space F2 or symmetric-function bounds inside the current work. No equations reduce a claimed prediction to a fitted parameter by construction, and no uniqueness theorem is imported from the authors' prior work to force the framework. The derivation therefore remains self-contained against external sketching primitives.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on standard streaming assumptions plus the novel framework; no free parameters are fitted to data, and the only invented component is the estimator-corrector-learner combination itself.

axioms (2)
  • domain assumption Turnstile streams of length polynomial in the universe size n
    Standard model assumption stated in the abstract for the space bounds.
  • domain assumption Functions satisfy an O(1)-approximate triangle inequality
    Required for the general symmetric-function result in the abstract.
invented entities (1)
  • estimator-corrector-learner framework no independent evidence
    purpose: Combine multiple linear sketches to achieve adversarial robustness in turnstile streams
    Newly introduced combination in the abstract; no independent evidence outside the paper is provided.

pith-pipeline@v0.9.0 · 5628 in / 1439 out tokens · 44274 ms · 2026-05-15T19:57:21.545917+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.