PaperlayerView exact revision on arXiv

Source-linked AI summary

A Framework for Adversarially Robust Streaming Algorithms

Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev

arXiv:2003.14265v3cs.DScs.CR

TL;DR

Many central streaming problems need randomized algorithms for efficiency, yet standard randomized guarantees do not cover streams chosen adaptively from observed outputs. The paper develops two generic robustification frameworks and gives robust algorithms for important streaming tasks, with space near the best non-robust algorithms.

  • Problem

    Many central streaming problems lack sublinear-space deterministic algorithms, while standard randomized algorithms assume the stream is fixed independently of their randomness and may not remain reliable against adaptive stream choices.

    Source: §1 · pp. 1–2

  • Method

    The paper develops two robustification frameworks that transform non-robust streaming algorithms, with space depending on how often the target function changes substantially along the stream.

    Source: §1.1 · p. 4

  • Results

    The paper gives adversarially robust algorithms for distinct elements, Fp moments, heavy hitters, entropy, and other problems, with space matching the best known non-robust algorithms up to a small multiplicative factor.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The frameworks apply when target functions do not change drastically too often, with the resulting space depending on the stream's flip-number.

    Source: §1.1 · p. 4

    For heavy hitters, the paper uses the simpler L2 guarantee rather than the stronger tail guarantee.

    Source: §6 · p. 22

Abstract

from arXiv · show

We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms; on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. In this work, we show that the answer is positive for various important streaming problems in the insertion-only model, including distinct elements and more generally $F_p$-estimation, $F_p$-heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust $(1+\varepsilon)$-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a $\text{poly}(\log n, 1/\varepsilon)$ multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a non-robust streaming algorithm into a robust one in various scenarios.

1 Introduction

The introduction examines adversarially robust streaming algorithms for streams that adapt to algorithm outputs, including generic techniques for converting static algorithms into robust ones. It covers L2 heavy hitters, entropy estimation, Fp estimation on bounded-deletion streams, related work, and open questions.

1.1 Our Results

  • The paper gives robust algorithms for fundamental insertion-only problems, including distinct elements, Fp estimation, heavy hitters, and entropy estimation, with space close to the best static randomized algorithms.It also gives algorithms handling a bounded number of deletions and demonstrates strong adaptive non-robustness of the AMS sketch for F2 estimation.Source: §1.1 · p. 3
  • Two robustification frameworks exploit limited function changes: sketch switching uses multiple algorithm instances, while computation paths uses one low-error instance and a union bound over rounded output paths.Their efficiency is incomparable: sketch switching benefits from strong-tracking algorithms, while computation paths benefits from low dependence on failure probability δ.Source: §1.1 · p. 4
  • Robust F0 estimation via sketch switching has complexity only a Θ(1 ε log ε−1) factor above the optimal static algorithm [B la18].A separate computation-paths approach yields an extremely fast-update-time variant using a new static algorithm with low dependence on δ.Source: §1.1 · p. 5
  • Under an exponentially secure pseudorandom-function assumption, robust F0 tracking uses O(ε−2(log 1/ε + log log n) + log n) bits in the random-oracle model, with success probability 3/4.For a polynomial-time adversary, the random oracle can be replaced by a concrete function, yielding O(ε−2(log 1/ε + log log n) + c log n) memory.Source: §1.1 · pp. 5–6
  • For insertion-only streams and 0 < p ≤2, robust Fp estimation uses O(ε−3 log n log ε−1(log ε−1 + log δ−1 + log log n)) bits and succeeds at every step with probability 1 −δ.For very small δ, the computation-paths method provides an alternative; the sketch-switching bound is within a Θ(ε−1 log ε−1) factor of the best static algorithm [BDN17].Source: §1.1 · p. 6
  • For turnstile streams with Fp flip number at most λ, the robust algorithm uses O(ε−2λ log2 n) space; for insertion-only p > 2, the paper also gives a robust algorithm with space optimal up to a small multiplicative factor.The turnstile guarantee succeeds with probability 1 −n−Cλ for any constant C > 0.Source: §1.1 · pp. 6–7
  • An adaptive adversary can make the AMS sketch’s F2 estimate fail a (1 ± 1/2) approximation with probability 99/100 after only O(t) updates [AMS99].This attack works for an insertion-only adversary when 1 ≤t ≤n/c for a constant c > 1.Source: §1.1 · p. 7

Heavy Hitters.

  • The heavy-hitters task returns all coordinates with |fi| ≥τ and excludes those with |fj| < τ/2; the Lp guarantee sets τ = ε∥f∥p.The introduction notes that deterministic insertion-only algorithms require Ω(√n) space for L2 heavy hitters, motivating randomized robust methods [KPW21].Source: Heavy Hitters · p. 7
  • Sketch switching yields adversarially robust L2 heavy hitters tracking, using only an O(ε^-1 log ε^-1) space factor over the best known static algorithm [BCI+17].The adversary sees the estimated set S at every step.Source: Heavy Hitters · p. 7

Entropy Estimation.

  • Theorem 1.10 gives adversarially robust ε-additive Shannon-entropy estimation in insertion-only streams using O(ε^-4 log^4 n(log log n + log ε^-1)) bits in the random-oracle model and O(ε^-4 log^6 n(log log n + log ε^-1)) in the general insertion-only model.The analysis uses exponential α-Renyi entropy, which closely approximates Shannon entropy and cannot rapidly change too often within the stream.Source: Entropy Estimation · p. 8

Bounded Deletion Streams.

  • For α-bounded-deletion streams, robust Fp estimation for p ∈ [1,2] uses O(αε^-(2+p) log^3 n) space and succeeds at every step with probability 1−n^-C.The approach uses the small flip number of bounded-deletion streams together with sketch switching.Source: Bounded Deletion Streams · p. 8

1.2 Other Previous Work

  • Prior work motivated adversarial robustness by settings where sketch queries depend on prior outputs and randomness, including privacy-sensitive datasets.Other cited work studies adversarial query risks, turnstile lower bounds, and settings incomparable to centralized streaming.Source: §1.2 · pp. 8–9

1.3 Subsequent Work and Open Questions

  • Follow-up work improved robustification space bounds, while open questions include the large gap between static and robust turnstile Fp estimation and whether such a separation exists [HKM+20].The section also notes robust-for-free techniques, extensions to vector outputs, and a graph-coloring separation and robust algorithms [BHM+21, CGS21].Source: §1.3 · pp. 9–10

2 Preliminaries

This section establishes streaming notation and the tracking guarantee used in the paper. It also previews the paper’s later methods and results.

2 Preliminaries

  • A stream is a sequence of updates whose frequency vector records cumulative updates per item; insertion-only streams restrict updates to positive values.The preliminaries also define F_p moments, with F_0 equal to the number of nonzero coordinates, and state bounds on intermediate frequencies.Source: §2 · p. 10

2.1 Tracking Algorithms

  • Strong tracking requires an estimate at every stream step, while weak tracking permits error scaled to the maximum function value over the stream.The paper uses strong tracking; cited static algorithms provide strong tracking for F_p moments and F_0 in insertion-only streams.Source: §2.1 · p. 11

2.2 Roadmap

  • The roadmap covers robustification techniques, insertion-only moment and distinct-elements estimation, L2 heavy hitters, entropy, bounded-deletion moments, an AMS-sketch attack, and cryptographic distinct-elements estimation.The cryptographic distinct-elements result is listed as optimal-space estimation under cryptographic assumptions.Source: §2.2 · p. 11

3 Tools for Robustness

The section introduces flip number as a measure of how often a streaming function changes substantially, then uses it to bound two generic transformations from static tracking algorithms to adversarially robust ones. These transformations trade off multiple algorithm instances against a single instance with a smaller failure probability.

3.1 Flip Number

  • A monotone function bounded between T^-1 and T on positive frequency vectors has insertion-only ε-flip number O(ε^-1 log T).The flip number depends on the stream model; the section also gives bounds for F_p moments and cascaded norms.Source: §3.1 · p. 13

3.2 The Sketch Switching Technique

  • Sketch switching maintains multiple strong-tracking instances and changes the exposed estimate only when it no longer approximates the active instance closely.The required number of instances is controlled by the problem’s flip number.Source: §3.2 · p. 14
  • For an algorithm with fixed-stream strong tracking and space L(ε, δ), sketch switching gives robust (1+ε)-approximation using O(L(ε/8, δ/λ)·λ) space, where λ is the ε/8-flip number.The guarantee holds at every stream step with success probability 1−δ.Source: §3.2 · p. 14

3.3 The Bounded Computation Paths Technique

  • The computation-paths technique runs one algorithm instance with very small failure probability and rounds its outputs, then union-bounds over the possible rounded output paths.It yields robust (1+ε)-approximation with the static algorithm’s space and time at ε/8 and δ0; δ0 is chosen using the number of possible paths.Source: §3.3 · p. 16

4 Fp-Estimation

The section applies the robustness framework to F_p estimation, using sketch switching or computation paths according to the parameter and failure-probability regime. It gives robust guarantees for insertion-only streams and, for bounded-flip turnstile streams, a space bound dependent on the flip number.

4 Fp-Estimation

  • For 0 < p ≤ 2, sketch switching gives adversarially robust (1±ε) F_p estimates at every step of insertion-only streams with success probability 1−δ.The construction uses strong tracking and an optimized restart strategy for sketches.Source: §4 · p. 17
  • For sufficiently small δ and 0 < p ≤ 2, computation paths also provide robust insertion-only F_p estimation by applying the framework to a static F_p algorithm.The theorem’s parameter range and full space expression are not present in the supplied theorem passages.Source: §4 · p. 18
  • For turnstile streams with F_p flip number at most λ, robust estimation for 0 < p ≤ 2 uses O(ε^-2λ log^2 n) space with failure probability n^-Cλ.The guarantee applies at every time step and holds for any constant C > 0.Source: §4 · p. 18
  • For constant p > 2, computation paths give robust insertion-only F_p estimation with failure probability 1−n^-(c log n)/ε and the stated space bound.The space bound is O(n^(1−2/p)(ε^-3 log^2 n + ε^-6/p(log^2 n)^(2/p) log n)).Source: §4 · p. 18

5 Distinct Elements Estimation

The section applies sketch switching to adversarially robust distinct-elements estimation on insertion-only streams. It also combines computation paths with an algorithm whose failure-probability dependence is small to obtain a robust variant with very fast update time.

5 Distinct Elements Estimation

  • Sketch switching gives a (1±ε) estimate of distinct elements at every step of an adversarial insertion-only stream with success probability at least 1−δ.The stated space is O(log ε^-1·ε^-2 + log n) bits.Source: §5 · p. 19

5.1 Fast Distinct Elements Estimation

  • The underlying fast estimator achieves a (1±ε) estimate of distinct elements on insertion-only streams with probability 1−δ.The robust theorem reports space O(ε^-2 log n(log log n + log δ^-1)); its update-time expression is incomplete in the supplied passage.Source: §5.1 · pp. 19, 21
  • The fast robust variant combines computation paths with an insertion-only estimator whose runtime depends on δ^-1 roughly as log^2 log δ^-1.This avoids the usual log δ^-1 update-time blow-up from independent repetitions and a median.Source: §5.1 · pp. 19, 21

6 Heavy Hitters

This section obtains adversarially robust L2 point queries and heavy hitters for insertion-only streams. It uses scheduled estimates and restarted sketches to limit how often randomness is exposed while controlling space.

6 Heavy Hitters

  • An ε-correct point-query estimate combined with F2 tracking yields L2 heavy hitters by thresholding coordinates against the estimated norm.The section treats point queries as the stronger property underlying the heavy-hitters guarantee.Source: §6 · p. 22
  • Sketch switching hides randomness by publishing a new estimate only when necessary, and the section applies this idea to robust point queries.The retained estimate remains useful while the frequency vector changes by a bounded amount.Source: §6 · p. 22
  • The algorithm solves adversarial insertion-only L2 point queries and O(ε)-heavy hitters with O(ε^-3 log^2 n log ε^-1) bits of space.The theorem allows failure probability n^-C for any constant C > 1.Source: §6 · p. 22
  • The algorithm schedules Θ(ε^-1 log n) update times and reuses O(ε^-1 log ε^-1) restarted point-query copies to reduce space.Insertion-only monotonicity lets each estimate remain accurate between scheduled times; restarting bounds the missed prefix's contribution.Source: §6 · pp. 22–24
  • The section uses the simpler L2 heavy-hitters guarantee, although a tail guarantee that excludes the largest 1/ε^2 coordinates from the error is possible.The L2 guarantee includes their contribution to the error.Source: §6 · p. 22

7 Entropy Estimation

This section gives adversarially robust additive Shannon entropy estimators for insertion-only streams. It bounds entropy's flip number and applies a generic transformation to non-adversarial estimators.

7 Entropy Estimation

  • The analysis bounds entropy's flip number by relating changes in g(x) = 2H(x) to multiplicative growth of monotone L1 and Lβ norms.A change by a factor 1 ± ε requires one of these norms to grow by a factor 1 + Ω(τ).Source: §7 · pp. 24–25
  • An ε-additive approximation of Shannon entropy corresponds to a (1 ± ε) multiplicative approximation of g(x) = 2H(x).The section uses this equivalence to work with multiplicative approximation in its flip-number analysis.Source: §7 · p. 24
  • Theorem 7.4 gives adversarially robust ε-additive entropy estimation in insertion-only streams, with separate space bounds for random-oracle and general models.The general insertion-only bound is stated as O(ε^-4 log^6 n(log log n + log ε^-1)) bits; the random-oracle bound is O(ε^-4 log^4 n(log log n + log ε^-1)) bits.Source: §7 · p. 24
  • The entropy estimator applies the generic robust transformation to non-adversarial entropy algorithms, using the entropy flip-number bound.For tracking, the proof sets the component algorithms' failure probability below 1/m.Source: §7 · p. 25

8 Bounded Deletion Streams

This section extends robust streaming algorithms to α-bounded deletion streams, where deletions are limited relative to the absolute-update stream. Bounded norm flip numbers support robust Fp estimation.

8 Bounded Deletion Streams

  • An α-bounded deletion stream keeps the Fp moment at least a 1/α fraction of the moment of the stream formed from absolute-valued updates.The model assumes unit updates; integral updates can be duplicated without loss of space complexity.Source: §8 · p. 25
  • Lp norms have bounded flip number in this model, a property used to build adversarially robust algorithms.The section derives the bound by comparing the stream with its insertion-only absolute-update stream.Source: §8 · p. 26
  • The Fp estimator combines a turnstile algorithm with the computation-path technique and the bounded-deletion flip-number bound.The same approach can yield robust heavy hitters once F2 estimation is available, with space larger by an αε log n factor than Theorem 6.5's bound.Source: §8 · p. 26
  • For p ∈ [1, 2], robust Fp estimation on α-bounded deletion streams uses O(αε^-(2+p) log^3 n) space and succeeds with probability 1 − n^-C.The algorithm returns a (1 ± ε) estimate of the Fp moment at each time step.Source: §8 · p. 26

9 Adversarial Attack Against the AMS Sketch

This section demonstrates that an adaptive adversary can defeat an AMS sketch even on insertion-only streams. The attack uses the sketch's published estimate to choose updates online.

9 Adversarial Attack Against the AMS Sketch

  • For an AMS sketch with r/ε^2 rows, the adversary needs only O(r) adaptive updates to force an incorrect estimate.The attack gives an even stronger guarantee than merely failing the stated approximation threshold.Source: §9 · p. 27
  • The adversary chooses to insert an item once or twice based on whether the proposed insertion raises the published estimate by more than, less than, or exactly 1.When the increase equals 1, it chooses randomly between the two update sizes.Source: §9 · p. 27
  • With probability 9/10, an adaptive adversary defeats a t-row AMS sketch after m = O(t) updates, making its estimate fail a (1 ± 1/2) approximation.The theorem assumes 1 ≤ t < n/c for a constant c.Source: §9 · pp. 27–28
  • The attack described here assumes a fully independent AMS sketch, although the sketch also works with only 4-wise independent entries.The passage specifically frames the attack against the fully independent version.Source: §9 · p. 27

10 Optimal Distinct Elements via Cryptographic Assumptions

The section gives adversarially robust F0 tracking algorithms under cryptographic assumptions, including a random-oracle result and a concrete pseudorandom-function implementation for bounded-time adversaries. The transformation also applies to streaming algorithms that leave their state unchanged on duplicate elements.

10 Optimal Distinct Elements via Cryptographic Assumptions

  • The transformation applies to algorithms that leave their state unchanged on previously seen elements, including the F0 tracking algorithm of [B la18].The paper describes this application as black-box.Source: §10 · p. 29
  • A random oracle gives the algorithm access to a truly random function without storing it, while the concrete implementation stores only a small secret key.The paper notes that heuristic functions such as SHA-256 can behave like random functions in practice, as far as can be determined.Source: §10 · p. 29
  • O(ε−2(log 1/ε + log log n) + log n) bits suffice for adversarial F0 tracking in the random oracle model, with success probability 3/4.The bound is the same as the cited optimal tracking algorithm's space bound.Source: §10 · p. 29
  • With an exponentially secure pseudorandom function, bounded-time adversaries running in time n^c permit a concrete implementation using O(ε−2(log 1/ε + log log n) + c log n) bits.Here c is fixed; the random oracle is replaced by a concrete function.Source: §10 · p. 29
  • The random-oracle construction applies a random permutation to each stream element before feeding it to the tracking algorithm, preserving the number of distinct elements.The proof argues that the transformed stream's states have the same distributions as a fixed sequence of distinct elements.Source: §10 · pp. 29–30
Loading 2003.14265v3…