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

Elena Gribelyuk; Honghao Lin; David P. Woodruff; Huacheng Yu; Samson Zhou

paper

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

arXiv:2607.06312

Abstract

We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While recent work achieved a robust $(1 + I^µ)$ -approximation for the second moment $F_{2}$ in polylogarithmic space, achieving high accuracy for other frequency moments remained a major open question; for $p \in [0, 2)$ , including the fundamental distinct elements problem ( $F_{0}$ ), only constant-factor approximations were known in sublinear space. We close this gap, showing that $(1 + I^µ)$ -approximate robustness can be achieved in polylogarithmic space for all $p \in [0, 2]$ . Our approach generalizes the estimator-corrector-learner framework to non-Hilbert spaces by dynamically maintaining implicit isometric embeddings into $L_{2}$ and performing regularized kernel ridge regression over adaptively discovered hard queries, yielding the first insertion-deletion algorithms that approximate: (1) the $p$ -th frequency moment $F_{p}$ up to a $(1 + I^µ)$ -factor in poly $(1/ I^µ, lo g n)$ space for all $p \in [0, 2]$ , including the support size $F_{0}$ , (2) metric and information-theoretic quantities, including the Earth Mover Distance (EMD) and $k$ -median clustering cost over $[I^]^{d}$ up to an $O (d lo g I^)$ -factor, and the Shannon entropy up to an $I^µ$ -additive error, and (3) non-normed symmetric losses defined by Bernstein functions up to a $(1 + I^µ)$ -factor. For the $F_{p}$ moments, our algorithm is optimal up to poly $(1/ I^µ, lo g n)$ factors. Furthermore, we establish a weak equivalence between classical oblivious sketching and adversarial robustness. We prove that for any sub-multiplicative norm, the existence of an efficient classical linear sketch is equivalent to the existence of an efficient robust turnstile algorithm, up to polynomial factors, formalizing $L_{1}$ embeddability as the fundamental mechanism governing both models.

FOCS 2026