mlsanityData to 14 Oct 2026

On the Robustness of CountSketch to Adaptive Inputs

arXiv 2202.13736 ↗First posted 28 Feb 2022cs.DS cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

CountSketch is a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized linear measurements. The sketch supports recovering ℓ2-heavy hitters of a vector (entries with v[i]2 ≥ frac1k|boldsymbolv|22). We study the robustness of the sketch in adaptive settings where input vectors may depend on the output from prior inputs. Adaptive settings arise in processes with feedback or with adversarial attacks. We show that the classic estimator is not robust, and can be attacked with a number of queries of the order of the sketch size. We propose a robust estimator (for a slightly modified sketch) that allows for quadratic number of queries in the sketch size, which is an improvement factor of √k (for k heavy hitters) over prior work.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 31 of its 54 references that are in the map. First posted on arXiv 28 Feb 2022.

Builds on

31 of 54 references.

References · 31

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2013Intriguing properties of neural networkscited by 5,155
  3. 2016Practical Black-Box Attacks against Machine Learningcited by 903
  4. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 179
  5. 2021Adaptive Machine Unlearningcited by 176
  6. 2015Compressing Neural Networks with the Hashing Trickcited by 150
  7. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 103
  8. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  9. 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 63
  10. 2015Differentially Private Release and Learning of Threshold Functionscited by 60
  11. 2014Preventing False Discovery in Interactive Data Analysis is Hardcited by 34
  12. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 31
19 more
  1. 2017Generalization for Adaptively-chosen Estimators via Stable Mediancited by 26
  2. 2015Compressing Convolutional Neural Networkscited by 25
  3. 2020A Framework for Adversarially Robust Streaming Algorithmscited by 21
  4. 2020Adversarially Robust Streaming Algorithms via Differential Privacycited by 21
  5. 2019Compressing Gradient Optimizers via Count-Sketchescited by 17
  6. 2021Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Boundscited by 17
  7. 2020Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimatorscited by 16
  8. 2018MISSION: Ultra Large-Scale Feature Selection using Count-Sketchescited by 11
  9. 2016Heavy hitters via cluster-preserving clusteringcited by 10
  10. 2021A Framework for Adversarial Streaming via Differential Privacy and Difference Estimatorscited by 9
  11. 2022Adaptive Data Analysis with Correlated Observationscited by 9
  12. 2020The Sparse Vector Technique, Revisitedcited by 8
  13. 2021Adversarially Robust Streaming via Dense--Sparse Trade-offscited by 7
  14. 2019Rounding Dynamic Matchings Against an Adaptive Adversarycited by 6
  15. 2019Minimum Cut in O(mlog2 n) Timecited by 4
  16. 2021A Simple Proof of a New Set Disjointness with Applications to Data Streamscited by 4
  17. 2020Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simplercited by 3
  18. 2020Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversarycited by 3
  19. 2020WOR and p's: Sketches for ℓp-Sampling Without Replacementcited by 3

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 3; 2024: 0; 2025: 1.

5 papers.

  1. 2023Streaming Algorithms for Learning with Experts: Deterministic Versus Robustcited by 3
  2. 2022Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputscited by 2
  3. 2023Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Modelcited by 0
  4. 2023Adversarially Robust Distributed Count Tracking via Partial Differential Privacycited by 0
  5. 2025The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ2 Norm Estimationcited by 0