The reliability of deep learning algorithms is fundamentally challenged by the existence of adversarial examples—inputs that appear identical to a human but cause a model to confidently misclassify them. While many empirical attacks and defenses have been developed since 2014, a fundamental theoretical question has remained: Is there a provable minimum distance an adversary must travel to fool a network?
Previous research suggested that in high-dimensional spaces, adversarial examples are inevitable if the classification error is non-zero, but these were often "upper bounds" showing an adversary can find a point. This paper tackles the "lower bound," providing a rigorous probabilistic guarantee that no adversarial example exists within a certain radius of a clean input for networks with random weights.
Ultimately, the authors establish a "universal scaling" law: for random deep neural networks, the distance to the nearest adversarial example scales as $1/\sqrt{n}$ relative to the input norm, where $n$ is the input dimension. This suggests that adversarial vulnerability is an inherent geometric property of high-dimensional spaces.
Theoretical Framework
The researchers bridge the gap between deep learning and classical probability theory using three main pillars:
- Gaussian Process (GP) Equivalence: They leverage the well-known proof that as the hidden layers of a neural network become infinitely wide, the network's output behaves like a Gaussian Process. This allows them to use the heavy machinery of stochastic process theory.
- Borell-TIS Inequality: This powerful probability tool is used to bound the maximum values of a Gaussian process. The authors use it to estimate the probability that the network's output will cross zero (the classification boundary) within a specific neighborhood of the input.
- Dudley’s Theorem: To handle the complexity of the input space, they use Dudley’s theorem to relate the "size" of the fluctuations in the network's output to the geometry of the input space, specifically using "covering numbers."
The beauty of this approach is its generality; it applies to fully connected networks, CNNs, ResNets (via skip connections), and various pooling layers.
Key Insights & The Scaling Law
The most significant takeaway from this work is the $1/\sqrt{n}$ Scaling Law. The minimum adversarial perturbation size is proportional to $1/\sqrt{n}$ times the norm of the input. As the dimension $n$ (e.g., the number of pixels) grows, the relative distance an adversary needs to move the input to flip the label shrinks, making high-dimensional inputs inherently more brittle.
Furthermore, the authors found that robustness is architecture-dependent. The bounds depend on the ratio between the number of pixels in the output layer versus the input layer. Architectures that do not aggressively downsample (like certain ResNets) might inherently favor better robustness.
Surprisingly, training does not change the order of magnitude of this vulnerability. While training a network on datasets like MNIST or CIFAR-10 changes the specific classification boundaries, it does not change the scaling of the adversarial distance. The fragility of the network remains fundamentally tied to the input dimension.
Experimental Validation
To validate their theoretical bounds, the authors performed adversarial attacks on synthetic random data, MNIST, and CIFAR-10. They compared the robustness of untrained (random) networks against trained networks to see if the theoretical scaling predicted for random networks still held after learning.
- Theoretical Bound: They proved that for any $\ell^p$ norm ($p \ge 1$), the distance to the boundary is at least $\tilde{\Omega}(1/\sqrt{n})$ times the norm of the input.
- Experimental Match: In experiments with residual networks, the median adversarial distance for $\ell^1$, $\ell^2$, and $\ell^\infty$ norms followed the predicted theoretical curves almost perfectly as the input dimension $n$ increased from 100 to 10,000.
- Relative Distance: The "relative distance" (perturbation size divided by input size) consistently scales as $1/\sqrt{n}$ across all tested norms.
Limitations and Future Work
While groundbreaking, the theory relies on the "infinite width" limit. Although experiments show the results hold for practical widths, the mathematical proofs are strictly for the limit. Additionally, the constants (prefactors) in their equations are not "sharp," meaning actual robustness might be slightly better than the conservative lower bound proved here.
Finally, while the theory covers random and Bayesian-trained networks, standard networks are trained with Stochastic Gradient Descent (SGD). The authors conjecture that the results extend to SGD, but a formal proof remains an open challenge. A promising future direction is studying robustness against perturbations that stay on the "data manifold" (like rotating an image) versus the "off-manifold" noise studied in this foundational work.
Summary updated