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

Saeed Mahloujifar, Dimitrios I. Diochnos, Mohammad Mahmoody

Abstract

This paper explores the fundamental mathematical limitations of adversarial robustness in machine learning. By leveraging the "concentration of measure" phenomenon in high-dimensional geometry, the authors demonstrate that the vulnerability of models to evasion and poisoning attacks is often an inherent property of the data distribution itself. The research proves that for any classifier operating on concentrated data, even a marginal initial error rate allows an adversary to achieve near-total success with sublinear perturbations. These findings suggest that the ongoing arms race between adversarial attacks and defenses may be constrained by inescapable geometric realities.

Introduction

Modern machine learning models, particularly deep neural networks, exhibit a persistent vulnerability to adversarial perturbations. These vulnerabilities manifest in two primary forms: evasion attacks, where test-time inputs are subtly modified to induce misclassification, and poisoning attacks, where the training data is tampered with to degrade the resulting model's performance. While much research focuses on developing specific algorithmic defenses, this paper investigates a deeper theoretical question: Is robust learning mathematically possible given the geometry of high-dimensional data?

Instead of analyzing specific architectures, the authors utilize the framework of metric probability spaces to show that adversarial vulnerability is a "curse" stemming from the concentration of measure. This phenomenon implies that in high-dimensional spaces, almost all points are located extremely close to any subset that contains a significant portion of the probability mass.

The Geometry of Vulnerability: Concentration of Measure

The core of the paper’s argument rests on the behavior of Lévy families, a class of concentrated metric probability spaces that includes n-dimensional spheres, Gaussian distributions, and Boolean hypercubes. In these spaces, the "concentration function" dictates how quickly the volume of a subset's neighborhood grows as the neighborhood expands.

Mathematically, if a classifier has even a small baseline error rate (e.g., 1%), the "error region"—the subset of the input space where the classifier fails—possesses a boundary that effectively encompasses the entire distribution. Because the measure concentrates so heavily, a random sample from the distribution is likely to be only a tiny distance away from this error region. This geometric reality suggests that the existence of adversarial examples is not necessarily a flaw in training or architecture, but a byproduct of the data's dimensionality.

Evasion Attacks: Why the Error Region is Everywhere

The authors link the concentration function directly to adversarial risk, defined as the probability that an adversary can find a misclassified example within a specific distance $\epsilon$ of a clean input.

Key Insights on Evasion:

  • Universality: The vulnerability is model-agnostic. Any classifier, regardless of its complexity or training method, will be susceptible if the underlying data distribution is concentrated.
  • Low Cost of Evasion: For data drawn from normal Lévy families of dimension $n$, the authors prove (Theorems 3.2 and 3.7) that an attacker only needs to perturb an instance by a sublinear amount—typically $O(\sqrt{n})$ or $O(1/\sqrt{n})$—to increase the adversarial risk to nearly 100%.

In essence, if a model is not perfect, it is likely to be highly vulnerable everywhere.

Poisoning Attacks: The Fragility of Training Sets

The paper extends this geometric logic from the input space to the space of training datasets. By treating a training set of size $m$ as a single point in a product space (under Hamming distance), the authors show that the space of all possible training sets also exhibits concentration.

Key Results on Poisoning:

  • General Poisoning (Theorem 4.5): For any deterministic learning algorithm, an offline attacker can reduce the learner's confidence from near-certainty to near-zero by tampering with only $O(\sqrt{m})$ training examples.
  • Targeted Poisoning (Theorem 4.8): An attacker can force a model to misclassify a specific chosen test instance by swapping out a small fraction of the training data ($O(\sqrt{m})$) with other correctly labeled examples. This demonstrates that poisoning does not require "label flipping" or injecting outliers; it can be achieved by carefully selecting which valid data points the model sees.

Discussion and Limitations

While the theoretical bounds are rigorous, the authors acknowledge certain limitations regarding real-world application. The proofs assume that data follows well-behaved concentrated distributions like isotropic Gaussians. Natural data, such as images or text, often resides on lower-dimensional manifolds that may not exhibit the same concentration properties as the ambient high-dimensional space.

However, the implications remain significant. If generative models (like GANs or Diffusion models) can successfully map simple concentrated distributions (like Gaussian noise) to natural images, then the impossibility results proven here may extend to those image manifolds.

Conclusion

This work shifts the perspective on adversarial robustness from an algorithmic challenge to a geometric one. By proving that evasion and poisoning are "cheap" in concentrated spaces, the authors provide a sobering baseline for what defenses can realistically achieve. Future research must determine whether natural data manifolds provide enough "non-concentration" to allow for truly robust learning, or if we must accept a fundamental trade-off between accuracy and robustness in high dimensions.

Summary updated

BibTeX
@inproceedings{mahloujifar2019curse,
  author = {Saeed Mahloujifar and Dimitrios I. Diochnos and Mohammad Mahmoody},
  title = {{The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure}},
  booktitle = {AAAI},
  year = {2019},
  url = {https://openreview.net/forum?id=rXE--ZzeO6r},
}
Figure