# Adversarial Examples in Multi-Layer Random ReLU Networks

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 16 references that are in the map.
- First posted on arXiv 23 Jun 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)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [Detecting Adversarial Samples from Artifacts](https://mlsanity.com/paper/1703.00410/) (2017)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Adversarial Robustness through Local Linearization](https://mlsanity.com/paper/1907.02610/) (2019)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance](https://mlsanity.com/paper/1901.10861/) (2019)
- [A single gradient step finds adversarial examples on random two-layers neural networks](https://mlsanity.com/paper/2104.03863/) (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)
- [Gradient Methods Provably Converge to Non-Robust Networks](https://mlsanity.com/paper/2202.04347/) (2022)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks](https://mlsanity.com/paper/2303.01456/) (2023)
- [Overparameterized Linear Regression under Adversarial Attacks](https://mlsanity.com/paper/2204.06274/) (2022)
- [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)
- [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)
- [Nash Equilibria and Pitfalls of Adversarial Training in Adversarial Robustness Games](https://mlsanity.com/paper/2210.12606/) (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)
- [Origins of Low-dimensional Adversarial Perturbations](https://mlsanity.com/paper/2203.13779/) (2022)
- [On Trace of PGD-Like Adversarial Attacks](https://mlsanity.com/paper/2205.09586/) (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)
- [Feature compression is the root cause of adversarial fragility in neural network classifiers](https://mlsanity.com/paper/2406.16200/) (2024)
- [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)
- [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)
- [Most Convolutional Networks Suffer from Small Adversarial Perturbations](https://mlsanity.com/paper/2602.03415/) (2026)

## Abstract (arXiv)

We consider the phenomenon of adversarial examples in ReLU networks with independent gaussian parameters. For networks of constant depth and with a large range of widths (for instance, it suffices if the width of each layer is polynomial in that of any other layer), small perturbations of input vectors lead to large changes of outputs. This generalizes results of Daniely and Schacham (2020) for networks of rapidly decreasing width and of Bubeck et al (2021) for two-layer networks. The proof shows that adversarial examples arise in these networks because the functions that they compute are very close to linear. Bottleneck layers in the network play a key role: the minimal width up to some point in the network determines scales and sensitivities of mappings computed up to that point. The main result is for networks with constant depth, but we also show that some constraint on depth is necessary for a result of this kind, because there are suitably deep networks that, with constant probability, compute a function that is close to constant.