A single gradient step finds adversarial examples on random two-layers neural networks

Sébastien Bubeck, Yeshwanth Cherapanamjeri, Gauthier Gidel, Remi Tachet des Combes

Adversarial examples—tiny, often imperceptible perturbations that trick a neural network into making a wrong prediction—have long been a fundamental challenge in deep learning. While it is tempting to blame the training process or specific datasets for this fragility, recent research suggests the problem might be structural. In "A single gradient step finds adversarial examples on random two-layers neural networks," Bubeck et al. prove that for random two-layer networks, complex attacks are unnecessary: a single gradient step is sufficient to break them. Crucially, this work extends previous findings to "overcomplete" networks, demonstrating that inherent linearity at a specific scale makes these models fundamentally vulnerable.

The Linearity Hypothesis and the Overcomplete Gap

The "Linearity Hypothesis," popularized by Goodfellow et al. (2015), posits that adversarial examples exist because neural networks behave too linearly in high-dimensional spaces. While empirically observed, theoretical proofs have historically been limited.

A foundational study by Daniely and Schacham (2020) proved that gradient descent could find adversarial examples in random "undercomplete" networks—where the number of neurons ($k$) is much smaller than the input dimension ($d$). However, modern neural networks are overwhelmingly "overcomplete" ($k > d$). Bubeck et al. bridge this gap, investigating whether this vulnerability persists as networks grow wider and whether a single, simple gradient step is truly enough to alter the model's prediction.

Mathematical Framework and Network Setup

The authors analyze a standard random two-layer neural network model defined as: $$f(x) = \frac{1}{\sqrt{k}} \sum_{\ell=1}^{k} a_\ell \psi(w_\ell \cdot x)$$ where the weights $w_\ell$ are drawn from a Gaussian distribution and the coefficients $a_\ell$ are random signs.

The core of their methodology relies on rigorous mathematical analysis using concentration of measure (specifically Bernstein’s inequality) to bound the function's value, its gradient, and its Hessian. The analysis is split into two primary scenarios:

  1. Smooth Activations: Where the activation function $\psi$ is Lipschitz with a Lipschitz derivative.
  2. ReLU Activations: Which are non-smooth and require a delicate "microscopic" analysis due to discontinuous gradients.

The attack studied is the simplest possible: a perturbation $\delta = \eta \nabla f(x)$, representing a single step in the direction of the gradient, akin to the Fast Gradient Sign Method (FGSM).

Key Insights: The Mesoscopic Scale and Universal Fragility

Through their analysis, the authors uncover several critical insights about the geometry of random networks:

  • The Mesoscopic Scale: The authors identify a critical "mesoscopic" scale for perturbations. If the input $x$ has a norm of $\sqrt{d}$, a perturbation $\delta$ with a norm of $O(1)$ is large enough to change the function's sign, yet small enough that the network still behaves almost linearly.
  • Overcompleteness Offers No Shield: Even when the number of neurons $k$ is significantly larger than the dimension $d$ (up to a subexponential width, $k \ll \exp(d)$), the network remains vulnerable. This mathematically debunks the intuition that simply adding more random neurons provides robustness.
  • Universal Fragility in ReLU: For ReLU networks, the required perturbation does not necessarily need to depend on the specific input $x$. A step in a "universal" direction—such as the sum of the weights—can often flip the sign for many different inputs simultaneously.
  • Theoretical Confirmation of FGSM: This work provides a solid theoretical foundation for why the Fast Gradient Sign Method is so effective: at the right scale, these complex non-linear functions are effectively linear.

Main Results and Empirical Validation

The paper formalizes these insights into two main theorems. For smooth activations, if $k$ is large and $d$ is sufficiently large relative to $k$, a single gradient step finds an adversarial example with high probability. A similar result holds for ReLU networks, albeit with tighter constraints on $k$ and $d$ across "Large Width" and "Small Width" regimes.

To validate their theory, the authors conducted numerical simulations on synthetic random networks, sampling weights and inputs from Gaussian distributions. Their experiments revealed that for networks with $d, k > 50$, 100% of samples were successfully flipped using a single gradient step. Notably, this empirical vulnerability held true even as network depth was increased up to 6 layers.

Limitations and Future Directions

While foundational, the study focuses exclusively on random networks. This characterizes the "initial state" of a model but does not account for how the geometry of the loss landscape evolves during training. Furthermore, while experiments suggest the vulnerability generalizes to deeper architectures, the formal proofs are restricted to two-layer networks. Finally, the results apply to subexponential widths; the "ultra-wide" regime where $k \approx \exp(d)$ (approaching the Gaussian Process limit) remains an open path for future study.

Ultimately, this paper serves as a stark warning: adversarial vulnerability is not merely a quirk of training data or optimization flaws. It is a mathematical property baked into the very structure of random high-dimensional neural architectures.

Summary updated

Abstract

Daniely and Schacham recently showed that gradient descent finds adversarial examples on random undercomplete two-layers ReLU neural networks. The term “undercomplete” refers to the fact that their proof only holds when the number of neurons is a vanishing fraction of the ambient dimension. We extend their result to the overcomplete case, where the number of neurons is larger than the dimension (yet also subexponential in the dimension). In fact we prove that a single step of gradient descent suffices. We also show this result for any subexponential width random neural network with smooth activation function.
BibTeX
@inproceedings{bubeck2021single,
  author = {Sébastien Bubeck and Yeshwanth Cherapanamjeri and Gauthier Gidel and Remi Tachet des Combes},
  title = {{A single gradient step finds adversarial examples on random two-layers neural networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=rpAKGC_fSR},
}
Figure