# A law of robustness for two-layers neural networks

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2020.

## Built on by (most cited first, 30 of 55)

- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [LipsFormer: Introducing Lipschitz Continuity to Vision Transformers](https://mlsanity.com/paper/2304.09856/) (2023)
- [Temporal Domain Generalization with Drift-Aware Dynamic Neural Networks](https://mlsanity.com/paper/2205.10664/) (2022)
- [Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power](https://mlsanity.com/paper/2205.13863/) (2022)
- [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)
- [Data Augmentation as Feature Manipulation](https://mlsanity.com/paper/2203.01572/) (2022)
- [Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization)](https://mlsanity.com/paper/2209.07263/) (2022)
- [A Theory for Knowledge Transfer in Continual Learning](https://mlsanity.com/paper/2208.06931/) (2022)
- [Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernels](https://mlsanity.com/paper/2302.01629/) (2023)
- [Adversarial Training Can Provably Improve Robustness: Theoretical Analysis of Feature Learning Process Under Structured Data](https://mlsanity.com/paper/2410.08503/) (2024)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [On the (Non-)Robustness of Two-Layer Neural Networks in Different Learning Regimes](https://mlsanity.com/paper/2203.11864/) (2022)
- [The Sample Complexity of One-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.06233/) (2022)
- [Benign Overfitting in Deep Neural Networks under Lazy Training](https://mlsanity.com/paper/2305.19377/) (2023)
- [Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes](https://mlsanity.com/paper/2106.02630/) (2021)
- [A Law of Robustness beyond Isoperimetry](https://mlsanity.com/paper/2202.11592/) (2022)
- [Theoretical Analysis of Robust Overfitting for Wide DNNs: An NTK Approach](https://mlsanity.com/paper/2310.06112/) (2023)
- [The Surprising Harmfulness of Benign Overfitting for Adversarial Robustness](https://mlsanity.com/paper/2401.12236/) (2024)
- [A law of adversarial risk, interpolation, and label noise](https://mlsanity.com/paper/2207.03933/) (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)
- [No Free Prune: Information-Theoretic Barriers to Pruning at Initialization](https://mlsanity.com/paper/2402.01089/) (2024)
- [Revisiting the Adversarial Robustness-Accuracy Tradeoff in Robot Learning](https://mlsanity.com/paper/2204.07373/) (2022)
- [Intrinsic dimensionality and generalization properties of the R-norm inductive bias](https://mlsanity.com/paper/2206.05317/) (2022)
- [Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization](https://mlsanity.com/paper/2102.04259/) (2021)
- [Origins of Low-dimensional Adversarial Perturbations](https://mlsanity.com/paper/2203.13779/) (2022)
- [Optimal Activation Functions for the Random Features Regression Model](https://mlsanity.com/paper/2206.01332/) (2022)
- [Learning Globally Smooth Functions on Manifolds](https://mlsanity.com/paper/2210.00301/) (2022)

## Abstract (arXiv)

We initiate the study of the inherent tradeoffs between the size of a neural network and its robustness, as measured by its Lipschitz constant. We make a precise conjecture that, for any Lipschitz activation function and for most datasets, any two-layers neural network with k neurons that perfectly fit the data must have its Lipschitz constant larger (up to a constant) than √n/k where n is the number of datapoints. In particular, this conjecture implies that overparametrization is necessary for robustness, since it means that one needs roughly one neuron per datapoint to ensure a O(1)-Lipschitz network, while mere data fitting of d-dimensional data requires only one neuron per d datapoints. We prove a weaker version of this conjecture when the Lipschitz constant is replaced by an upper bound on it based on the spectral norm of the weight matrix. We also prove the conjecture in the high-dimensional regime n ≈ d (which we also refer to as the undercomplete case, since only k ≤ d is relevant here). Finally we prove the conjecture for polynomial activation functions of degree p when n ≈ dp. We complement these findings with experimental evidence supporting the conjecture.