# The Adversarial Robustness of Sampling

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2019.

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

- [Data Distillation: A Survey](https://mlsanity.com/paper/2301.04272/) (2023)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [ReliabilityRAG: Effective and Provably Robust Defense for RAG-based Web-Search](https://mlsanity.com/paper/2509.23519/) (2025)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Online Selective Classification with Limited Feedback](https://mlsanity.com/paper/2110.14243/) (2021)
- [Uniform Approximations for Randomized Hadamard Transforms with Applications](https://mlsanity.com/paper/2203.01599/) (2022)
- [Sequential Manipulation Against Rank Aggregation: Theory and Algorithm](https://mlsanity.com/paper/2407.01916/) (2024)
- [TAET: Two-Stage Adversarial Equalization Training on Long-Tailed Distributions](https://mlsanity.com/paper/2503.01924/) (2025)
- [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024)
- [Provable Robustness for Streaming Models with a Sliding Window](https://mlsanity.com/paper/2303.16308/) (2023)
- [Universal Deoxidation of Semiconductor Substrates Assisted by Machine-Learning and Real-Time-Feedback-Control](https://mlsanity.com/paper/2312.01662/) (2023)
- [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)
- [Robust Streaming, Sampling, and a Perspective on Online Learning](https://mlsanity.com/paper/2312.01634/) (2023)
- [Fast White-Box Adversarial Streaming Without a Random Oracle](https://mlsanity.com/paper/2406.06808/) (2024)
- [Minimizing Human Intervention in Online Classification](https://mlsanity.com/paper/2510.23557/) (2025)

## Abstract (arXiv)

Random sampling is a fundamental primitive in modern algorithms, statistics, and machine learning, used as a generic method to obtain a small yet "representative" subset of the data. In this work, we investigate the robustness of sampling against adaptive adversarial attacks in a streaming setting: An adversary sends a stream of elements from a universe U to a sampling algorithm (e.g., Bernoulli sampling or reservoir sampling), with the goal of making the sample "very unrepresentative" of the underlying data stream. The adversary is fully adaptive in the sense that it knows the exact content of the sample at any given point along the stream, and can choose which element to send next accordingly, in an online manner. Well-known results in the static setting indicate that if the full stream is chosen in advance (non-adaptively), then a random sample of size Omega(d / varepsilon2) is an varepsilon-approximation of the full data with good probability, where d is the VC-dimension of the underlying set system (U,R). Does this sample size suffice for robustness against an adaptive adversary? The simplistic answer is negative: We demonstrate a set system where a constant sample size (corresponding to VC-dimension 1) suffices in the static setting, yet an adaptive adversary can make the sample very unrepresentative, as long as the sample size is (strongly) sublinear in the stream length, using a simple and easy-to-implement attack. However, this attack is "theoretical only", requiring the set system size to (essentially) be exponential in the stream length. This is not a coincidence: We show that to make Bernoulli or reservoir sampling robust against adaptive adversaries, the modification required is solely to replace the VC-dimension term d in the sample size with the cardinality term log |R|. This nearly matches the bound imposed by the attack.