Generalized No Free Lunch Theorem for Adversarial Robustness

Elvis DohmatobICML 2019 · OpenReview

Introduction

Machine learning models are notoriously fragile: small, often imperceptible changes to an input—known as adversarial perturbations—can cause a model to completely flip its prediction. Researchers have long debated whether this vulnerability is a flaw in how we train models or an inherent property of the data itself.

This paper tackles the fundamental limits of robustness, asking: Under what conditions is it mathematically impossible to build a robust classifier? While previous work demonstrated this impossibility for specific "toy" examples, this research proves a generalized "Strong No Free Lunch" theorem. It shows that for a wide class of data distributions, any classifier with even a small amount of standard error is mathematically destined to be vulnerable to adversarial attacks. Once a perturbation exceeds the "natural noise level" of the data, a classifier's accuracy will inevitably collapse due to the fundamental geometric properties of high-dimensional spaces.

Theoretical Framework: Geometry and Optimal Transport

To derive universal lower bounds on adversarial vulnerability, the author employs tools from geometric probability and optimal transport theory.

The key technical contribution is linking adversarial robustness to the concentration of measure phenomenon. Specifically, the paper leverages:

  • Talagrand’s $W_2$ transportation-cost inequality ($T_2$): A condition satisfied by "well-behaved" distributions, such as log-concave distributions (like Gaussians) or distributions on manifolds with positive curvature.
  • Marton’s Blowup Lemma: A mathematical tool describing how a small set—in this case, the classifier's error set—"blows up" to cover almost the entire probability space when slightly enlarged.
Illustration of the Blowup Lemma, where a set B expands to a larger set B^epsilon.

By combining these concepts, the author proves that if a classifier has a non-zero standard error, that error set is geometrically "close" to almost every point in the dataset. An attacker only needs to move a data point a small distance to land it inside that pre-existing error set.

Key Insights and Empirical Validation

The paper validates its theoretical findings using simulated data (a high-dimensional Gaussian mixture model with $p = 1000$ features) and the MNIST handwritten digit dataset.

The "Phase Transition" of Robustness

A central finding is that robustness doesn't degrade linearly. There is a "critical value" of perturbation ($\epsilon$). Below this value, the model remains relatively robust. However, once the perturbation exceeds this threshold—which is related to the natural noise $\sigma$ and the dimension $p$—accuracy drops exponentially fast to chance levels.

Empirical validation showing the phase transition in adversarial accuracy as perturbation increases.

In experiments on MNIST and simulated data, the adversarial accuracy curves perfectly match theoretical predictions. As $\epsilon$ increases, there is a clear "knee" in the curve where the model's performance collapses.

Robustness as a Complexity Measure

The paper suggests that adversarial vulnerability isn't just a "bug" to be fixed, but a measure of the problem's inherent complexity. If your data is highly concentrated (which high-dimensional data often is), robustness is mathematically at odds with high accuracy. The theorem applies broadly to any $L_q$ norm attack (including popular $L_\infty$ and $L_2$ attacks) and extends to data living on curved manifolds, unifying several previous specific results into one framework.

Furthermore, the paper provides a concrete formula for the average distance from a correctly classified point to the nearest misclassified point, showing it is upper-bounded by a value proportional to the natural noise level. For $L_\infty$ attacks in $p$-dimensional space, the critical perturbation level scales as $O(1/\sqrt{p})$. As the number of features increases, the amount of change needed to fool the model becomes vanishingly small.

Limitations and Future Work

  • Curvature Assumptions: The theoretical results rely on the data satisfying certain "curvature conditions" (like log-concavity). While many distributions fit this, it remains unclear how strictly these hold for extremely complex, real-world data distributions like natural images.
  • Simple Attack Models: The paper focuses on additive perturbations (moving points in a metric space). It does not account for more complex "semantic" attacks, such as small rotations, deformations, or changes in lighting that don't fit neatly into a standard norm-based threat model.
  • Future Directions: The author suggests exploring more complex threat models and investigating whether the "modulus of concentration" of a distribution could be used as a formal metric to rank the inherent adversarial difficulty of different machine learning tasks.

Summary updated

Abstract

This manuscript presents some new impossibility results on adversarial robustness in machine learning, a very important yet largely open problem. We show that if conditioned on a class label the da...
BibTeX
@inproceedings{dohmatob2019generalized,
  author = {Elvis Dohmatob},
  title = {{Generalized No Free Lunch Theorem for Adversarial Robustness}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=HybQ5jZuZB},
}
Figure