# The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2018.

## Built on by (most cited first, 30 of 46)

- [Robust Learning Meets Generative Models: Can Proxy Distributions Improve Adversarial Robustness?](https://mlsanity.com/paper/2104.09425/) (2021)
- [Property Inference From Poisoning](https://mlsanity.com/paper/2101.11073/) (2021)
- [The Dimpled Manifold Model of Adversarial Examples in Machine Learning](https://mlsanity.com/paper/2106.10151/) (2021)
- [Scaling Trends for Data Poisoning in LLMs](https://mlsanity.com/paper/2408.02946/) (2024)
- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [Universal Adversarial Examples and Perturbations for Quantum Classifiers](https://mlsanity.com/paper/2102.07788/) (2021)
- [Universal Adversarial Perturbations Through the Lens of Deep Steganography: Towards A Fourier Perspective](https://mlsanity.com/paper/2102.06479/) (2021)
- [Enhancing Quantum Adversarial Robustness by Randomized Encodings](https://mlsanity.com/paper/2212.02531/) (2022)
- [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021)
- [Trusted Artificial Intelligence: Towards Certification of Machine Learning Applications](https://mlsanity.com/paper/2103.16910/) (2021)
- [Learning and Certification under Instance-targeted Poisoning](https://mlsanity.com/paper/2105.08709/) (2021)
- [Adversarial Examples Are Not Bugs, They Are Superposition](https://mlsanity.com/paper/2508.17456/) (2025)
- [Lethal Dose Conjecture on Data Poisoning](https://mlsanity.com/paper/2208.03309/) (2022)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [On the (Non-)Robustness of Two-Layer Neural Networks in Different Learning Regimes](https://mlsanity.com/paper/2203.11864/) (2022)
- [Adversarial Examples Might be Avoidable: The Role of Data Concentration in Adversarial Robustness](https://mlsanity.com/paper/2309.16096/) (2023)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attacker](https://mlsanity.com/paper/2302.10722/) (2023)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [Improved Estimation of Concentration Under ℓp-Norm Distance Metrics Using Half Spaces](https://mlsanity.com/paper/2103.12913/) (2021)
- [Origins of Low-dimensional Adversarial Perturbations](https://mlsanity.com/paper/2203.13779/) (2022)
- [Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks](https://mlsanity.com/paper/2205.06127/) (2022)
- [Robust Linear Regression: Gradient-descent, Early-stopping, and Beyond](https://mlsanity.com/paper/2301.13486/) (2023)
- [Backdoor Learning for NLP: Recent Advances, Challenges, and Future Research Directions](https://mlsanity.com/paper/2302.06801/) (2023)
- [Hamming Similarity and Graph Laplacians for Class Partitioning and Adversarial Image Detection](https://mlsanity.com/paper/2305.01808/) (2023)
- [Understanding Intrinsic Robustness Using Label Uncertainty](https://mlsanity.com/paper/2107.03250/) (2021)
- [Feature-Filter: Detecting Adversarial Examples through Filtering off Recessive Features](https://mlsanity.com/paper/2107.09502/) (2021)
- [Robust Linear Regression: Phase-Transitions and Precise Tradeoffs for General Norms](https://mlsanity.com/paper/2308.00556/) (2023)
- [Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries](https://mlsanity.com/paper/2104.08382/) (2021)
- [Classification and Adversarial examples in an Overparameterized Linear Model: A Signal Processing Perspective](https://mlsanity.com/paper/2109.13215/) (2021)

## Abstract (arXiv)

Many modern machine learning classifiers are shown to be vulnerable to adversarial perturbations of the instances. Despite a massive amount of work focusing on making classifiers robust, the task seems quite challenging. In this work, through a theoretical study, we investigate the adversarial risk and robustness of classifiers and draw a connection to the well-known phenomenon of concentration of measure in metric measure spaces. We show that if the metric probability space of the test instance is concentrated, any classifier with some initial constant error is inherently vulnerable to adversarial perturbations. One class of concentrated metric probability spaces are the so-called Levy families that include many natural distributions. In this special case, our attacks only need to perturb the test instance by at most O(√ n) to make it misclassified, where n is the data dimension. Using our general result about Levy instance spaces, we first recover as special case some of the previously proved results about the existence of adversarial examples. However, many more Levy families are known (e.g., product distribution under the Hamming distance) for which we immediately obtain new attacks that find adversarial examples of distance O(√ n). Finally, we show that concentration of measure for product spaces implies the existence of forms of "poisoning" attacks in which the adversary tampers with the training data with the goal of degrading the classifier. In particular, we show that for any learning algorithm that uses m training examples, there is an adversary who can increase the probability of any "bad property" (e.g., failing on a particular test instance) that initially happens with non-negligible probability to ≈ 1 by substituting only tildeO(√ m) of the examples with other (still correctly labeled) examples.