# A Universal Law of Robustness via Isoperimetry

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

## Key facts

- Cited by 151 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 43 references that are in the map.
- First posted on arXiv 26 May 2021.

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

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Overfitting in adversarially robust deep learning](https://mlsanity.com/paper/2002.11569/) (2020)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [The Intrinsic Dimension of Images and Its Impact on Learning](https://mlsanity.com/paper/2104.08894/) (2021)
- [Unitary Evolution Recurrent Neural Networks](https://mlsanity.com/paper/1511.06464/) (2015)
- [Parseval Networks: Improving Robustness to Adversarial Examples](https://mlsanity.com/paper/1704.08847/) (2017)
- [Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examples](https://mlsanity.com/paper/2010.03593/) (2020)
- [Estimating the intrinsic dimension of datasets by a minimal neighborhood information](https://mlsanity.com/paper/1803.06992/) (2018)
- [Sensitivity and Generalization in Neural Networks: an Empirical Study](https://mlsanity.com/paper/1802.08760/) (2018)
- [Spectral Norm Regularization for Improving the Generalizability of Deep Learning](https://mlsanity.com/paper/1705.10941/) (2017)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Convergence of Adversarial Training in Overparametrized Neural Networks](https://mlsanity.com/paper/1906.07916/) (2019)
- [Efficient Orthogonal Parametrisation of Recurrent Neural Networks Using Householder Reflections](https://mlsanity.com/paper/1612.00188/) (2016)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [On Computation and Generalization of GANs with Spectrum Control](https://mlsanity.com/paper/1812.10912/) (2018)

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

- [Reproducible scaling laws for contrastive language-image learning](https://mlsanity.com/paper/2212.07143/) (2022)
- [Capabilities of GPT-4 on Medical Challenge Problems](https://mlsanity.com/paper/2303.13375/) (2023)
- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Understanding plasticity in neural networks](https://mlsanity.com/paper/2303.01486/) (2023)
- [Shortcut Learning of Large Language Models in Natural Language Understanding](https://mlsanity.com/paper/2208.11857/) (2022)
- [Direct Parameterization of Lipschitz-Bounded Deep Networks](https://mlsanity.com/paper/2301.11526/) (2023)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Robust and Efficient Medical Imaging with Self-Supervision](https://mlsanity.com/paper/2205.09723/) (2022)
- [Why neural networks find simple solutions: the many regularizers of geometric complexity](https://mlsanity.com/paper/2209.13083/) (2022)
- [A Law of Data Separation in Deep Learning](https://mlsanity.com/paper/2210.17020/) (2022)
- [LipsFormer: Introducing Lipschitz Continuity to Vision Transformers](https://mlsanity.com/paper/2304.09856/) (2023)
- [On the influence of over-parameterization in manifold based surrogates and deep neural operators](https://mlsanity.com/paper/2203.05071/) (2022)
- [On the Adversarial Robustness of Mixture of Experts](https://mlsanity.com/paper/2210.10253/) (2022)
- [Adversarial Examples in Multi-Layer Random ReLU Networks](https://mlsanity.com/paper/2106.12611/) (2021)
- [Some Fundamental Aspects about Lipschitz Continuity of Neural Networks](https://mlsanity.com/paper/2302.10886/) (2023)
- [Robust Reinforcement Learning from Corrupted Human Feedback](https://mlsanity.com/paper/2406.15568/) (2024)
- [SALTED: A Framework for SAlient Long-Tail Translation Error Detection](https://mlsanity.com/paper/2205.09988/) (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)
- [Parameterizing Activation Functions for Adversarial Robustness](https://mlsanity.com/paper/2110.05626/) (2021)
- [Overparameterized Linear Regression under Adversarial Attacks](https://mlsanity.com/paper/2204.06274/) (2022)
- [Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization)](https://mlsanity.com/paper/2209.07263/) (2022)
- [More is Better in Modern Machine Learning: when Infinite Overparameterization is Optimal and Overfitting is Obligatory](https://mlsanity.com/paper/2311.14646/) (2023)
- [Hardness of Learning Neural Networks under the Manifold Hypothesis](https://mlsanity.com/paper/2406.01461/) (2024)
- [Investigating Power laws in Deep Representation Learning](https://mlsanity.com/paper/2202.05808/) (2022)
- [DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization](https://mlsanity.com/paper/2202.01268/) (2022)
- [A Quantitative Geometric Approach to Neural-Network Smoothness](https://mlsanity.com/paper/2203.01212/) (2022)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Evolution of Neural Tangent Kernels under Benign and Adversarial Training](https://mlsanity.com/paper/2210.12030/) (2022)
- [Unlocking Deterministic Robustness Certification on ImageNet](https://mlsanity.com/paper/2301.12549/) (2023)

## Abstract (arXiv)

Classically, data interpolation with a parametrized model class is possible as long as the number of parameters is larger than the number of equations to be satisfied. A puzzling phenomenon in deep learning is that models are trained with many more parameters than what this classical theory would suggest. We propose a partial theoretical explanation for this phenomenon. We prove that for a broad class of data distributions and model classes, overparametrization is necessary if one wants to interpolate the data smoothly. Namely we show that smooth interpolation requires d times more parameters than mere interpolation, where d is the ambient data dimension. We prove this universal law of robustness for any smoothly parametrized function class with polynomial size weights, and any covariate distribution verifying isoperimetry. In the case of two-layers neural networks and Gaussian covariates, this law was conjectured in prior work by Bubeck, Li and Nagaraj. We also give an interpretation of our result as an improved generalization bound for model classes consisting of smooth functions.