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

arXiv: https://arxiv.org/abs/2104.03863 · HTML: https://mlsanity.com/paper/2104.03863/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 20 references that are in the map.
- First posted on arXiv 8 Apr 2021.

## Builds on (most cited first, 12 of 12)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Universal adversarial perturbations](https://mlsanity.com/paper/1610.08401/) (2016)
- [Robustness via curvature regularization, and vice versa](https://mlsanity.com/paper/1811.09716/) (2018)
- [Adversarial Robustness through Local Linearization](https://mlsanity.com/paper/1907.02610/) (2019)
- [Feature Purification: How Adversarial Training Performs Robust Deep Learning](https://mlsanity.com/paper/2005.10190/) (2020)
- [A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance](https://mlsanity.com/paper/1901.10861/) (2019)
- [Non-asymptotic approximations of neural networks by Gaussian processes](https://mlsanity.com/paper/2102.08668/) (2021)
- [Most ReLU Networks Suffer from ℓ2 Adversarial Perturbations](https://mlsanity.com/paper/2010.14927/) (2020)

## Built on by (most cited first, 26 of 26)

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [On the Stability of Iterative Retraining of Generative Models on their own Data](https://mlsanity.com/paper/2310.00429/) (2023)
- [Gradient Methods Provably Converge to Non-Robust Networks](https://mlsanity.com/paper/2202.04347/) (2022)
- [Adversarial Examples in Multi-Layer Random ReLU Networks](https://mlsanity.com/paper/2106.12611/) (2021)
- [The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks](https://mlsanity.com/paper/2303.01456/) (2023)
- [Evolution of Neural Tangent Kernels under Benign and Adversarial Training](https://mlsanity.com/paper/2210.12030/) (2022)
- [Adversarial Examples in Random Neural Networks with General Activations](https://mlsanity.com/paper/2203.17209/) (2022)
- [Unveiling the Basin-Like Loss Landscape in Large Language Models](https://mlsanity.com/paper/2505.17646/) (2025)
- [Adversarial Training Can Provably Improve Robustness: Theoretical Analysis of Feature Learning Process Under Structured Data](https://mlsanity.com/paper/2410.08503/) (2024)
- [On the (Non-)Robustness of Two-Layer Neural Networks in Different Learning Regimes](https://mlsanity.com/paper/2203.11864/) (2022)
- [Adversarial Reprogramming Revisited](https://mlsanity.com/paper/2206.03466/) (2022)
- [Adversarial Examples Exist in Two-Layer ReLU Networks for Low Dimensional Linear Subspaces](https://mlsanity.com/paper/2303.00783/) (2023)
- [Adversarial Robustness is at Odds with Lazy Training](https://mlsanity.com/paper/2207.00411/) (2022)
- [How many dimensions are required to find an adversarial example?](https://mlsanity.com/paper/2303.14173/) (2023)
- [Effect of Ambient-Intrinsic Dimension Gap on Adversarial Vulnerability](https://mlsanity.com/paper/2403.03967/) (2024)
- [Origins of Low-dimensional Adversarial Perturbations](https://mlsanity.com/paper/2203.13779/) (2022)
- [Upper and lower bounds for the Lipschitz constant of random neural networks](https://mlsanity.com/paper/2311.01356/) (2023)
- [Adversarial Noises Are Linearly Separable for (Nearly) Random Neural Networks](https://mlsanity.com/paper/2206.04316/) (2022)
- [Blessings and Curses of Covariate Shifts: Adversarial Learning Dynamics, Directional Convergence, and Equilibria](https://mlsanity.com/paper/2212.02457/) (2022)
- [A generalizable framework for low-rank tensor completion with numerical priors](https://mlsanity.com/paper/2302.05881/) (2023)
- [MALT Powers Up Adversarial Attacks](https://mlsanity.com/paper/2407.02240/) (2024)
- [A Provable Energy-Guided Test-Time Defense Boosting Adversarial Robustness of Large Vision-Language Models](https://mlsanity.com/paper/2603.26984/) (2026)
- [mathscrH-Consistency Estimation Error of Surrogate Loss Minimizers](https://mlsanity.com/paper/2205.08017/) (2022)
- [A Linearly Convergent GAN Inversion-based Algorithm for Reverse Engineering of Deceptions](https://mlsanity.com/paper/2306.04756/) (2023)
- [Deep Neural Nets as Hamiltonians](https://mlsanity.com/paper/2503.23982/) (2025)
- [Existence of Adversarial Examples for Random Convolutional Networks via Isoperimetric Inequalities on mathbbso(d)](https://mlsanity.com/paper/2506.12613/) (2025)

## Abstract (arXiv)

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.