Adversarial robustness guarantees for random deep neural networks

Giacomo De Palma, Bobak Toussi Kiani, Seth Lloyd

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:

  1. 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.
  2. 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}$.

Scaling of median adversarial distances for random untrained ResNets across $\ell^1, \ell^2,$ and $\ell^\infty$ norms.

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.

Median relative distance scales as $O(1/\sqrt{n})$ for all norms, confirming the universal vulnerability of high-dimensional inputs.

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

Abstract

The reliability of deep learning algorithms is fundamentally challenged by the existence of adversarial examples, which are incorrectly classified inputs that are extremely close to a correctly classified input. We explore the properties of adversarial examples for deep neural networks with random weights and biases, and prove that for any $p\ge1$, the $\ell^p$ distance of any given input from the classification boundary scales as one over the square root of the dimension of the input times the $\ell^p$ norm of the input. The results are based on the recently proved equivalence between Gaussian processes and deep neural networks in the limit of infinite width of the hidden layers, and are validated with experiments on both random deep neural networks and deep neural networks trained on the MNIST and CIFAR10 datasets. The results constitute a fundamental advance in the theoretical understanding of adversarial examples, and open the way to a thorough theoretical characterization of the relation between network architecture and robustness to adversarial perturbations.
BibTeX
@inproceedings{palma2021adversarial,
  author = {Giacomo De Palma and Bobak Toussi Kiani and Seth Lloyd},
  title = {{Adversarial robustness guarantees for random deep neural networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=LMvrl_RL8O},
}
Figure