# A Law of Robustness for Weight-bounded Neural Networks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 41 references that are in the map.
- First posted on arXiv 16 Feb 2021.

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

- [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)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Adversarial Examples Are Not Bugs, They Are Features](https://mlsanity.com/paper/1905.02175/) (2019)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Adversarial Training Can Hurt Generalization](https://mlsanity.com/paper/1906.06032/) (2019)
- [Feature Purification: How Adversarial Training Performs Robust Deep Learning](https://mlsanity.com/paper/2005.10190/) (2020)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation](https://mlsanity.com/paper/1905.03684/) (2019)
- [Convergence of Adversarial Training in Overparametrized Neural Networks](https://mlsanity.com/paper/1906.07916/) (2019)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [On the Discrimination-Generalization Tradeoff in GANs](https://mlsanity.com/paper/1711.02771/) (2017)
- [Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality](https://mlsanity.com/paper/2002.06668/) (2020)
- [Distributional Robustness with IPMs and links to Regularization and GANs](https://mlsanity.com/paper/2006.04349/) (2020)
- [Computational Limitations in Robust Classification and Win-Win Results](https://mlsanity.com/paper/1902.01086/) (2019)

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

- [Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes](https://mlsanity.com/paper/2106.02630/) (2021)
- [Does Order Matter : Connecting The Law of Robustness to Robust Generalization](https://mlsanity.com/paper/2602.20971/) (2026)

## Abstract (arXiv)

Robustness of deep neural networks against adversarial perturbations is a pressing concern motivated by recent findings showing the pervasive nature of such vulnerabilities. One method of characterizing the robustness of a neural network model is through its Lipschitz constant, which forms a robustness certificate. A natural question to ask is, for a fixed model class (such as neural networks) and a dataset of size n, what is the smallest achievable Lipschitz constant among all models that fit the dataset? Recently, (Bubeck et al., 2020) conjectured that when using two-layer networks with k neurons to fit a generic dataset, the smallest Lipschitz constant is Omega(√fracnk). This implies that one would require one neuron per data point to robustly fit the data. In this work we derive a lower bound on the Lipschitz constant for any arbitrary model class with bounded Rademacher complexity. Our result coincides with that conjectured in (Bubeck et al., 2020) for two-layer networks under the assumption of bounded weights. However, due to our result's generality, we also derive bounds for multi-layer neural networks, discovering that one requires log n constant-sized layers to robustly fit the data. Thus, our work establishes a law of robustness for weight bounded neural networks and provides formal evidence on the necessity of over-parametrization in deep learning.