Abstract
Starting with Gilmer et al. (2018), several works have demonstrated the inevitability of adversarial examples based on different assumptions about the underlying input probability space. It remains unclear, however, whether these results apply to natural image distributions. In this work, we assume the underlying data distribution is captured by some conditional generative model, and prove intrinsic robustness bounds for a general class of classifiers, which solves an open problem in Fawzi et al. (2018). Building upon the state-of-the-art conditional generative models, we study the intrinsic robustness of two common image benchmarks under L2 perturbations, and show the existence of a large gap between the robustness limits implied by our theory and the adversarial robustness achieved by current state-of-the-art robust models.
Introduction
Deep neural networks are notoriously fragile; tiny, imperceptible "adversarial perturbations" can flip a model's prediction from a "bus" to an "ostrich." Earlier theoretical work suggested this fragility might be a fundamental property of high-dimensional space—essentially, that in high dimensions, almost every point is "close" to a classification boundary. However, these theories often relied on simplified assumptions, like data being uniformly distributed on a high-dimensional sphere.
This paper asks whether this "inevitability" actually applies to natural images. Natural images don't fill the entire pixel space; they lie on a lower-dimensional "manifold." This work aims to find the intrinsic robustness—the best possible robustness any classifier could achieve—for these specific image manifolds.
Methodology
The authors bridge the gap between abstract theory and real-world data using Conditional Generative Models (GANs).
- Theoretical Framework: New lower bounds for adversarial risk are derived by applying the Gaussian Isoperimetric Inequality to the latent space of a generative model. The "smoothness" of the generator (its local Lipschitz constant) is connected to the robustness of the images it produces.
- Local Lipschitz Estimation: Since calculating the exact smoothness of a deep generator is nearly impossible, a sample-based algorithm was developed to estimate it, providing a practical way to bound the robustness of complex distributions like ImageNet.
- In-Distribution Attacks: A novel optimization method finds adversarial examples that stay on the image manifold. Instead of just changing pixels, the search is conducted in the GAN's latent space to find a "fake" image that looks real but fools the classifier.
Experimental Setup
The study evaluates robustness on two major benchmarks, modeled via state-of-the-art GANs:
- MNIST: Modeled using an ACGAN (Auxiliary Classifier GAN).
- ImageNet: A 10-class subset (ImageNet10) modeled using BigGAN.
Analysis of the Robustness Gap
A key insight is that the manifold matters. Previous "impossibility" results were too pessimistic because they didn't account for the fact that images live on low-dimensional manifolds. When data is restricted to these manifolds, the theoretical "limit" of robustness becomes much higher.
There is a massive "performance gap" between these theoretical limits and current empirical results. This suggests that the "inevitability of adversarial examples" is not a valid excuse for current model failures; we simply haven't found the right way to train robust models yet.
Key Results
The paper provides a striking comparison between theoretical limits and actual model performance. As the perturbation strength ($\epsilon$) increases, the gap between what is mathematically possible and what our models actually do becomes even wider.
| Dataset | Perturbation ($\ell_2$ distance) | Theoretical Max Robustness | SOTA Model Robustness (TRADES) |
|---|---|---|---|
| MNIST | $\epsilon = 3.0$ | 97.2% | 57.7% |
| ImageNet10 | $\epsilon = 2.0$ | 81.8% | 49.1% |
| ImageNet10 | $\epsilon = 3.0$ | 80.0% | 27.8% |
Conclusion
While current models are vulnerable, this research shows we are far from the theoretical ceiling of robustness. Future work should focus on closing this gap, perhaps by developing new training objectives that respect the data manifold or finding more precise ways to measure concentration of measure on non-smooth manifolds. The results depend on GAN fidelity and Lipschitz estimation accuracy, but the overall trend strongly suggests that significantly more robust models are possible.
Summary updated