# On the Robustness of CountSketch to Adaptive Inputs

arXiv: https://arxiv.org/abs/2202.13736 · HTML: https://mlsanity.com/paper/2202.13736/

## 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 (most cited first, 30 of 31)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [FetchSGD: Communication-Efficient Federated Learning with Sketching](https://mlsanity.com/paper/2007.07682/) (2020)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [Compressing Neural Networks with the Hashing Trick](https://mlsanity.com/paper/1504.04788/) (2015)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Preventing False Discovery in Interactive Data Analysis is Hard](https://mlsanity.com/paper/1408.1655/) (2014)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [Generalization for Adaptively-chosen Estimators via Stable Median](https://mlsanity.com/paper/1706.05069/) (2017)
- [Compressing Convolutional Neural Networks](https://mlsanity.com/paper/1506.04449/) (2015)
- [A Framework for Adversarially Robust Streaming Algorithms](https://mlsanity.com/paper/2003.14265/) (2020)
- [Adversarially Robust Streaming Algorithms via Differential Privacy](https://mlsanity.com/paper/2004.05975/) (2020)
- [Compressing Gradient Optimizers via Count-Sketches](https://mlsanity.com/paper/1902.00179/) (2019)
- [Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds](https://mlsanity.com/paper/2111.03980/) (2021)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [MISSION: Ultra Large-Scale Feature Selection using Count-Sketches](https://mlsanity.com/paper/1806.04310/) (2018)
- [Heavy hitters via cluster-preserving clustering](https://mlsanity.com/paper/1604.01357/) (2016)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [The Sparse Vector Technique, Revisited](https://mlsanity.com/paper/2010.00917/) (2020)
- [Adversarially Robust Streaming via Dense--Sparse Trade-offs](https://mlsanity.com/paper/2109.03785/) (2021)
- [Rounding Dynamic Matchings Against an Adaptive Adversary](https://mlsanity.com/paper/1911.05545/) (2019)
- [Minimum Cut in O(mlog2 n) Time](https://mlsanity.com/paper/1911.01145/) (2019)
- [A Simple Proof of a New Set Disjointness with Applications to Data Streams](https://mlsanity.com/paper/2105.11338/) (2021)
- [Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler](https://mlsanity.com/paper/2001.10809/) (2020)
- [Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary](https://mlsanity.com/paper/2001.10821/) (2020)

## Built on by (most cited first, 5 of 5)

- [Streaming Algorithms for Learning with Experts: Deterministic Versus Robust](https://mlsanity.com/paper/2303.01709/) (2023)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)
- [Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model](https://mlsanity.com/paper/2301.09203/) (2023)
- [Adversarially Robust Distributed Count Tracking via Partial Differential Privacy](https://mlsanity.com/paper/2311.00346/) (2023)
- [The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ2 Norm Estimation](https://mlsanity.com/paper/2507.16345/) (2025)

## 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.