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 $\ell_2$ 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
Adversarial examples—tiny, imperceptible perturbations that cause a classifier to mispredict—have posed a significant challenge to deep learning for years. Previous theoretical research suggested that these vulnerabilities are "inevitable" based on the geometry of high-dimensional spaces. However, these theories often relied on abstract assumptions, such as data being uniformly distributed on a sphere, which do not necessarily reflect the properties of real-world images.
This work aims to determine the intrinsic robustness of actual image distributions. By identifying the "speed limit" of robustness—the maximum possible accuracy any classifier could achieve under a specific attack strength ($\epsilon$)—the authors investigate whether current model failures are due to mathematical necessity or limitations in training methodologies.
Methodology
The researchers bridged the gap between abstract theory and real data using Conditional Generative Models (CGMs). Their approach relies on two primary components:
- Manifold Assumption: Natural images are assumed to lie on a low-dimensional manifold captured by a generator $G$ that maps a simple latent space (e.g., a Gaussian distribution) to the image space.
- Theoretical Bound: By applying the Gaussian Isoperimetric Inequality to the latent space, they derived a lower bound on adversarial risk. The key variable in this bound is the local Lipschitz constant ($L$) of the generator, which quantifies how much the output image changes relative to a change in the latent input.
Lipschitz Estimation
Since calculating the exact Lipschitz constant for a deep network is NP-hard, the authors developed a sample-based approximation to estimate $L$ for trained GANs.
Additionally, the authors introduced a new optimization method for in-distribution attacks. This method finds adversarial examples that stay strictly on the image manifold, providing a more realistic measure of model vulnerability in real-world scenarios.
Experimental Setup
The study evaluated two primary benchmarks using state-of-the-art generative architectures:
- MNIST: Modeled using an ACGAN (Auxiliary Classifier GAN) to generate $28 \times 28$ digits.
- ImageNet10: A subset of 10 specific classes from ImageNet, modeled using BigGAN to generate $128 \times 128$ images (downsampled to $32 \times 32$ for computational efficiency).
Key Results and Insights
The authors compared their theoretical upper bounds on robustness against the empirical performance of state-of-the-art robust models using $\ell_2$ perturbations.
| Dataset | Perturbation ($\epsilon$) | Theoretical Bound (Max Rob.) | Best Empirical Model (TRADES) |
|---|---|---|---|
| MNIST | 2.0 | 97.8% | 81.8% |
| MNIST | 3.0 | 97.2% | 57.7% |
| ImageNet10 | 1.0 | 83.5% | 68.5% |
| ImageNet10 | 2.0 | 81.8% | 49.1% |
The Robustness Gap
The most striking insight is the significant "robustness gap." For instance, on ImageNet10 with $\epsilon=2.0$, there is a 32.7% gap between the theoretical limit and the performance of the best current models. This suggests that adversarial vulnerability is not an inherent property of the ImageNet distribution itself, but rather a limitation of current training algorithms.
Smoothness and Conditioning
The intrinsic robustness of a dataset is fundamentally tied to the "smoothness" of its generative process. Furthermore, analyzing classes individually (conditional) yields much tighter and more meaningful bounds than looking at the entire dataset at once, as within-class variation is typically smaller than between-class variation.
Discussion
While this work provides a new perspective on robustness, it has certain limitations:
- GAN Dependency: The derived bounds are dependent on the quality of the generative model. If the GAN fails to capture the full complexity of the real image manifold, the calculated intrinsic robustness might be overly optimistic.
- Lipschitz Underestimation: The sample-based approach for estimating $L$ provides a lower bound, which makes the robustness limit an upper bound. More rigorous estimation could refine these results.
The paper concludes that we are not yet limited by the "inevitability" of adversarial examples. Future work should focus on designing new training objectives or architectures—perhaps incorporating "in-distribution" training—to bridge the gap between current performance and theoretical limits.
Code for all experiments is available at https://github.com/xiaozhanguva/Intrinsic-Rob.
Summary updated