Abstract
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 Lévy families that include many natural distributions. In this special case, our attacks only need to perturb the test instance by at most $O(\sqrt{n})$ to make it misclassified, where $n$ is the data dimension. Using our general result about Lévy instance spaces, we first recover as special case some of the previously proved results about the existence of adversarial examples. However, many more Lévy 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(\sqrt{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 $\approx 1$ by substituting only $\tilde{O}(\sqrt{m})$ of the examples with other (still correctly labeled) examples.
Introduction
Despite the rapid advancement of deep learning, machine learning models remain stubbornly vulnerable to adversarial examples—small, often imperceptible changes to input data that cause a model to misclassify. While significant research has focused on developing empirical defenses, the persistence of these vulnerabilities suggests a deeper, perhaps fundamental, cause.
This paper investigates whether adversarial vulnerability is a flaw in current training techniques or an inherent property of high-dimensional data. By bridging the gap between two distinct threat models—evasion attacks (perturbing test data) and poisoning attacks (tampering with training data)—the authors demonstrate that both are consequences of a mathematical phenomenon known as the "concentration of measure."
The Geometry of Vulnerability: Concentration of Measure
The core of the paper's argument rests on Concentration of Measure. In high-dimensional metric probability spaces, this phenomenon states that most of the probability mass is concentrated very close to any set that has a non-negligible amount of mass.
In the context of machine learning, if a classifier has even a small initial error rate $\epsilon$, the set of "misclassified points" has mass $\epsilon$. In a concentrated space, almost every point in the entire space lies within a very small distance of this error set. Consequently, an adversary does not need to find a "broken" part of the model; they simply need to nudge a correctly classified point a tiny distance to land it in the naturally occurring error region.
Lévy Families and the $1/\sqrt{n}$ Rule
The authors apply this concept to "normal Lévy families," a broad class of distributions where concentration is particularly strong. These include:
- The $n$-sphere (with uniform distribution).
- Isotropic $n$-Gaussian distributions.
- The Boolean Hypercube (under Hamming distance).
- Product distributions (where features are independent).
For these distributions, the authors prove that an attacker only needs to perturb an instance by a distance of $O(1/\sqrt{n})$ to reach an error region. This provides a unified theoretical framework explaining why adversarial examples are so prevalent across different types of high-dimensional data.
Evasion Attacks: Inevitable Risk
In Theorem 3.2, the authors formalize the risk of evasion. They show that if a classifier's initial error $\epsilon$ is slightly larger than the space's concentration function $\alpha(b)$, an adversary can increase the risk to over $1/2$ using a perturbation budget of $b$. With only a slightly larger budget, the risk can be pushed to nearly $1$. This suggests that for any imperfect classifier operating in a concentrated space, adversarial examples are not just possible—they are mathematically guaranteed to exist in close proximity to almost all inputs.
Poisoning Attacks: Efficiency in Product Spaces
The paper extends this geometric intuition to the training phase. By treating an entire training set of size $m$ as a single point in a high-dimensional product space, the authors analyze the impact of poisoning.
Theorem 4.3 demonstrates that poisoning is "devastatingly" efficient. For any deterministic learner, an adversary can increase the probability of a "bad property" (such as the model failing on a specific test case or losing overall confidence) from a negligible probability to nearly $100\%$. This is achieved by substituting only a sublinear fraction—specifically $O(\sqrt{m})$—of the training examples with other correctly labeled examples. This result highlights that even "clean-label" poisoning, where the adversary cannot change the labels of the data, can be extremely effective due to the underlying geometry of the training sample space.
Discussion and Limitations
While the paper establishes a rigorous theoretical "curse" for robust learning, it also notes several nuances:
- Existence vs. Search: The proofs demonstrate that adversarial examples exist and are "close," but they do not necessarily provide the specific algorithm to find them. However, the existence of such points is the necessary precondition for the success of practical attacks like PGD or FGSM.
- The Metric Gap: The definition of "closeness" depends on the chosen metric (e.g., Euclidean or Hamming distance). The authors acknowledge that the mathematical metrics used in the proofs may not perfectly align with human perception, which is the ultimate benchmark for "imperceptible" perturbations in fields like computer vision.
- Real-World Manifolds: A critical question for future work is whether real-world data, such as natural images, actually resides on concentrated manifolds. The authors suggest that if the latent spaces of generative models (like GANs or VAEs) exhibit these concentration properties, then the "curse" likely applies to those domains as well.
Conclusion
This work shifts the perspective on adversarial robustness from a purely algorithmic challenge to a geometric one. By showing that evasion and poisoning attacks are two sides of the same "concentration" coin, the authors provide a sobering conclusion: in high-dimensional spaces, vulnerability may be an inescapable tax on any classifier that is not perfectly accurate.
Summary updated