Abstract
Adversarial vulnerability in machine learning is often attributed to the concentration of measure in high-dimensional spaces, suggesting that small perturbations inevitably lead to misclassification. This paper challenges this notion by providing tighter estimates of intrinsic robustness. By generalizing the Gaussian Isoperimetric Inequality to non-spherical Gaussians and arbitrary $\ell_p$-norms, and utilizing half-spaces for estimation, the authors demonstrate that datasets like CIFAR-10 and MNIST are significantly less concentrated than previously estimated. These findings suggest that current adversarial vulnerabilities are primarily modeling failures rather than inherent data limitations.
Introduction
In adversarial machine learning, even imperceptible perturbations can cause state-of-the-art models to fail. A popular theoretical explanation is concentration of measure: the idea that in high-dimensional spaces, most probability mass lies near the boundaries of any set. If true, an adversary needs only a tiny "nudge" to push data out of its correct classification region, making adversarial examples inevitable.
However, measuring this "intrinsic robustness"—the maximum possible robustness any classifier could achieve—is difficult. Previous attempts to find these lower bounds were loose. This paper aims to tighten these bounds to determine if data concentration is truly the bottleneck for robust machine learning.
Methods
The authors propose a two-pronged approach involving theoretical generalization and a new empirical algorithm.
Theoretical Generalization
The authors extend the Gaussian Isoperimetric Inequality. While the classic version applies to spherical Gaussians and $\ell_2$ (Euclidean) distance, this work generalizes it to non-spherical Gaussians and arbitrary $\ell_p$-norms (where $p \ge 2$), covering the common $\ell_\infty$ threat model used in adversarial research.
Half-Space Estimation
Based on their theoretical findings, the authors argue that half-spaces (regions defined by a single linear boundary) are optimal shapes for estimating concentration in Gaussian settings. Unlike previous methods that used complex collections of hyperrectangles or balls, half-spaces have a low VC-dimension, requiring an order of magnitude less data to converge to stable estimates.
The Algorithm
The proposed algorithm uses a heuristic search to find the "best" half-space for a dataset. It utilizes Principal Component Analysis (PCA) to identify directions of high variance and then "rotates" these directions toward the axes to find boundaries that expand slowly under $\ell_p$ distances. A closed-form solution for the $\ell_p$-distance from a point to a half-space makes this approach significantly more efficient than prior techniques.
Results
The method was evaluated on synthetic Gaussian data ($\mathcal{N}(0, I_{784})$) and standard image benchmarks: MNIST, CIFAR-10, Fashion-MNIST, and SVHN.
As shown in the table above, the proposed method consistently achieves lower adversarial risk estimates across all datasets and perturbation levels ($\epsilon$).
- CIFAR-10: For $\ell_\infty$ perturbations ($\epsilon = 8/255$), previous work estimated the intrinsic robustness limit at roughly 81.87% (18.13% risk). The half-space method improves this estimate to over 93.72% (6.28% risk).
- MNIST: The estimated intrinsic robustness for $\epsilon = 0.1$ reached nearly 99%, indicating that concentration is almost a non-factor for this dataset.
- Convergence Speed: On synthetic data, the half-space method reached within 0.01 of the true theoretical value with only 1,000 samples, whereas previous methods failed to produce non-trivial estimates even with larger sample sizes.
Discussion and Conclusion
The primary insight of this work is that the "robustness gap" is much larger than previously thought. The theoretical limit of robustness is significantly higher than the performance of current state-of-the-art models. This suggests that the current inability to build robust models is a modeling failure—a limitation of our training algorithms or architectures—rather than an inherent property of the data distributions themselves.
Limitations and Future Work
While the algorithm performs exceptionally well, it remains a heuristic. There is no mathematical guarantee that it finds the absolute optimal half-space for non-Gaussian, real-world data. Furthermore, while the paper proves that highly robust classifiers exist theoretically, it does not provide a method for training them. Future research could explore more complex, yet statistically efficient, shapes to further tighten these bounds and potentially bridge the gap between theoretical limits and practical performance.
Summary updated