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.
Introduction
Since the discovery of adversarial examples in 2014, the susceptibility of deep neural networks to tiny, imperceptible perturbations has remained a central challenge in machine learning. A prominent hypothesis, introduced by Goodfellow et al. (2015), suggests that this vulnerability stems from the "excessive linearity" of neural networks in high-dimensional spaces. While empirically supported, providing a rigorous mathematical foundation for this phenomenon has proven difficult.
Recent work by Daniely and Schacham established that gradient descent can find adversarial examples in "undercomplete" random two-layer ReLU networks—those where the number of neurons $k$ is significantly smaller than the input dimension $d$. However, modern architectures are typically "overcomplete" ($k > d$). This research bridges the gap, demonstrating that the linearity and subsequent vulnerability persist even when the network width vastly exceeds the input dimension.
Theoretical Framework
The study focuses on a 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:
- $x \in \mathbb{R}^d$ is the input, sampled from a sphere of radius $\sqrt{d}$.
- $w_\ell \in \mathbb{R}^d$ are weights drawn from a standard Gaussian distribution.
- $a_\ell \in \{-1, 1\}$ are random signs.
- $\psi$ is the activation function (e.g., ReLU or a smooth alternative).
The goal is to determine if a single step of the Fast Gradient Sign Method (FGSM) or a simple gradient step can flip the sign of $f(x)$ with high probability.
The "Mostly Linear" Landscape
The core insight of this work is the characterization of the function's landscape in high dimensions. By employing concentration inequalities (specifically Bernstein’s inequality), the authors show that at a "mesoscopic" scale—perturbations that are small but not infinitesimal—the function's curvature (Hessian) is negligible compared to its gradient.
Specifically, as the dimension $d$ increases, the norm of the Hessian vanishes at a rate of $O(1/\sqrt{d})$, while the gradient norm remains $O(1)$. This implies that in high-dimensional spaces, random networks behave almost linearly over surprisingly large regions.
For non-smooth activations like ReLU, the authors introduce a "microscopic" analysis. They demonstrate that during a small gradient step, only a negligible fraction of neurons change their activation state (i.e., cross the zero-threshold). This allows the linear approximation to hold even in the absence of traditional smoothness.
Key Results
The paper presents two primary theorems confirming the effectiveness of a single gradient step:
- Theorem 1 (Smooth Activations): For smooth, Lipschitz activations, if the width $k$ is at least logarithmic in $1/\gamma$ and $d$ is sufficiently large, a single gradient step flips the sign of the output with probability at least $1-\gamma$.
- Theorem 2 (ReLU): The same result holds for ReLU networks in the overcomplete regime ($d \ll k$), provided the width $k$ does not grow faster than $\exp(d^{0.24})$.
Experimental simulations validate these findings, showing that the step size $\eta$ required to flip a prediction remains roughly constant regardless of width $k$ or dimension $d$. Furthermore, these experiments suggest the phenomenon generalizes to deeper architectures (up to $L=6$ layers).
Discussion and Limitations
While this work provides a strong theoretical basis for adversarial vulnerability, several open questions remain:
- The Ultra-Wide Regime: The current proofs hold for subexponential widths. If the number of neurons is truly astronomical ($k = \exp(\Omega(d))$), the network behaves like a Gaussian Process, and the landscape may become more complex.
- Trained vs. Random Networks: The analysis focuses on random initializations. While training starts here, the optimization process on real-world data might alter the landscape, potentially exacerbating or mitigating this inherent linearity.
- Depth: Formal proofs are currently limited to two-layer networks. Extending these results to deep networks remains a critical path for future research.
Summary updated