Research map / Learning theory and algorithms / Matrix and tensor methods
Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Improves the dense-sparse tradeoff for adversarially robust L_p heavy-hitters and L_p (F_p) estimation on turnstile streams using deterministic heavy-hitters, differential-privacy sketch ensembles, and a residual-moment estimator.
Problem
Adversarially robust L_p estimation and L_p heavy-hitters on turnstile streams, where prior dense-sparse techniques required about m^{p/(2p+1)} space and it was unknown whether this was a fundamental barrier.
Approach
Use a deterministic turnstile heavy-hitter algorithm (DetHH) for small universes and an ensemble of robust CountSketch instances (via differential privacy) for large universes, plus a subsampling-based residual F_p estimator independent of the tail size, so the flip number of the residual vector (rather than the full vector) governs space.
Key results
- Robust L_p heavy-hitters in tilde-O(eps^-2.5 m^{(2p-2)/(4p-3)}) bits, polylog space at p=1, versus m^{p/(2p+1)} from prior dense-sparse framework.
- Robust L_p estimation on turnstile streams in tilde-O(m^c) space with c=(24p^2-23p+4)/((4p-3)(12p+3)); for p=1.5 this gives m^{47/126}≈m^{0.373} versus m^{0.375} previously.
- On CAIDA, the residual flip number is smaller than the full-vector flip number by a ratio of 1.002 to 1.75 depending on parameters.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Track Lp heavy hitters using the proposed robust heavy-hitter algorithm | Adversarial turnstile Lp estimation · Adversarial streams, p∈[1,2) | space exponent: m^{p/(2p+1)} -> m^{(2p-2)/(4p-3)} | Helped |
| Combine heavy-hitter tracking with residual moment estimation | Adversarial turnstile Lp estimation · Adversarial streams, p∈(1,2) | space exponent: m^{3/8}=m^{0.375} -> m^{47/126}≈m^{0.373} | Helped |
| Track and remove the heavy coordinates when measuring flip number | Adversarially robust streaming algorithms · CAIDA sender IP traffic | flip number: 1.24 to 1.31 | Helped |
| Track and remove the heavy coordinates when measuring flip number | Adversarially robust streaming algorithms · CAIDA sender IP traffic, α=4^{-1} to α=4^{-10} | full-vector to residual flip-number ratio: 1.002 ... 1.6 | Helped |
| Track and remove the heavy coordinates when measuring flip number | Adversarially robust streaming algorithms · CAIDA sender IP traffic, ε=10^{-1} to ε=10^{-5} | full-vector to residual flip-number ratio: 1.17 ... 1.75 | Helped |
Surprising findings
- For p=1, robust L_p heavy-hitters need only polylogarithmic space, compared with m^{1/3} from the prior dense-sparse framework.
Limitations
- The improvement in the L_p estimation exponent is mild (e.g., 0.373 vs 0.375 at p=1.5).
- Residual estimation only gives additive error relative to a tail with (1-eps)k truncation (bicriteria guarantee).
- The experiments use a single real dataset and a non-adaptive setting.
Experimental setup
Datasets: CAIDA traffic traces (equinix-nyc, ~3 million events, 12 minutes)
Benchmarks: CAIDA
Metrics: flip number of full vector vs residual vector space exponent of m
Baselines: Ben-Eliezer, Eden, Onak 2022 dense-sparse framework sketch switching computation paths DetHH
Builds on: dense-sparse tradeoff (Ben-Eliezer, Eden, Onak 2022) differential privacy adversarial robustness CountSketch sketch switching
Closest papers by meaning
- Fast White-Box Adversarial Streaming Without a Random Oracle (ICML 2024 · similarity 0.87)
- RAMP: Boosting Adversarial Robustness Against Multiple $l_p$ Perturbations for Universal Robustness (NeurIPS 2024 · similarity 0.85)
- Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD (NeurIPS 2024 · similarity 0.85)
- A Subquadratic Time Algorithm for Robust Sparse Mean Estimation (ICML 2024 · similarity 0.84)
- ROME is Forged in Adversity: Robust Distilled Datasets via Information Bottleneck (ICML 2025 · similarity 0.84)
- Out of Thin Air: Exploring Data-Free Adversarial Robustness Distillation (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.