Abstract
This study provides the first rigorous theoretical guarantees for the adversarial robustness of random deep neural networks. By leveraging the equivalence between infinite-width networks and Gaussian Processes, we demonstrate that the distance to a classification boundary scales as $1/\sqrt{n}$ relative to the input norm. This confirms that adversarial vulnerability is an inherent geometric consequence of high-dimensional input spaces rather than a mere artifact of training.
Introduction
Deep neural networks (DNNs) are notoriously sensitive to adversarial examples—tiny, often imperceptible perturbations to an input that cause the model to misclassify it. While empirical research has found many ways to generate these attacks and some ways to defend against them, a fundamental theoretical question remained: Is adversarial vulnerability an avoidable "bug" of training, or an unavoidable feature of high-dimensional geometry?
Previous geometric theories suggested that if a classifier has a non-zero error rate, adversarial examples must exist within a distance of $O(1/\sqrt{n})$ from the input (where $n$ is the dimension). However, proving this specifically for the complex, non-linear architectures of DNNs was an open challenge. This paper fills that gap by providing a probabilistic robustness guarantee for random DNNs.
Theoretical Framework
The authors bridge the gap between deep learning and classical probability theory using two main pillars:
- Gaussian Process (GP) Equivalence: Recent theoretical advances have shown that as the hidden layers of a random DNN become infinitely wide, the network's output converges to a Gaussian Process. This allows the authors to treat the DNN as a smooth random function with well-defined statistical properties.
- Concentration of Measure: To find the distance to the classification boundary (where the network output $\phi(x) = 0$), the authors use the Borell-TIS inequality and Dudley’s theorem. These tools provide upper bounds on the maximum deviation of a Gaussian process over a specific region (like an $\ell^1$ ball), allowing them to calculate the probability that a classification boundary exists within a certain radius of a given input.
The theory covers a wide range of modern architectures, including fully connected layers, convolutional layers (CNNs), skip connections (ResNets), and pooling.
Empirical Validation and Scaling Laws
The authors validated their theoretical scaling laws using synthetic random data, MNIST, and CIFAR10. The experimental results provide a striking confirmation of the theory across different norms. Specifically, the $\ell^1$ distance scales as $\sqrt{n}$, the $\ell^2$ distance remains constant ($O(1)$), and the $\ell^\infty$ distance scales as $1/\sqrt{n}$.
Crucially, when looking at relative distance (the size of the perturbation divided by the norm of the input), the authors show that it scales as $1/\sqrt{n}$ for all norms. This means as the resolution of an image increases, it becomes mathematically "easier" to find an adversarial example.
Key Insights and Discussion
- Robustness is Architectural: The bounds depend on the ratio between the number of output pixels and input pixels. Architectures that preserve more spatial information tend to be more robust.
- Training vs. Randomness: Surprisingly, the authors find that training a network doesn't change the order of magnitude of its adversarial distance. While training might shift the boundary slightly, the $1/\sqrt{n}$ scaling law remains a dominant factor.
- Geometric Inevitability: The results imply that adversarial examples are not necessarily a sign of a "broken" model, but rather a reflection of the fact that in high dimensions, almost every point is extremely close to a decision boundary.
Limitations and Future Work
While the infinite-width assumption is central to the proof, experiments show the results hold for practical widths (starting around $n \approx 100$). Future work will aim to extend these rigorous guarantees to multi-class problems and study robustness against non-additive perturbations, such as rotations or geometric deformations of the input image.
Summary updated