Source-linked AI summary
A Universal Law of Robustness via Isoperimetry
Sébastien Bubeck, Mark Sellke
TL;DR
Deep learning models often use far more parameters than the number of interpolation equations, raising the question of whether this scale is necessary for robustness. The paper proves a broad isoperimetric lower bound for smoothly parametrized models: smooth interpolation in d dimensions requires about d times more parameters, with implications for robust generalization and real-data model sizes.
Problem
Classical interpolation needs roughly n parameters for n equations, but it is unclear why robust deep-learning models require substantially larger parametrizations.
Method
The paper proves a universal robustness law for smoothly parametrized function classes with polynomially bounded weights and covariate distributions satisfying isoperimetry.
Results
Smooth interpolation requires roughly nd parameters rather than n, and the bound is essentially tight for O(1)-Lipschitz interpolation with n(d + 1) parameters.
Takeaways & Limitations
The result places robust interpolation and robust model scale within a general parameter–Lipschitz tradeoff and suggests current ImageNet networks may be undersized for robust modeling.
Takeaways & Limitations
The theory does not prove the arbitrarily weighted two-layer conjecture and relies on polynomially bounded weights; empirical applications also involve mismatches between Lipschitz robustness and robust generalization error.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper argues that smoothly interpolating d-dimensional data generally requires roughly d times more parameters than merely fitting n equations. It formalizes this robustness–model-size tradeoff under broad distribution and parametrization assumptions, while discussing empirical implications and scope limits.
- The universal law of robustness: d times more parameters are necessary for smooth interpolation than for mere interpolation: roughly nd instead of n parameters.The result applies broadly to smoothly parametrized function classes with polynomially bounded parameter sizes and isoperimetric covariate distributions.
- The universal law of robustness: Robust interpolation is characterized by a tradeoff: an n-parameter model must be non-robust, whereas an O(1)-Lipschitz model requires approximately nd parameters.For distributions such as the uniform sphere, an O(1)-Lipschitz interpolant exists with high probability, and the construction uses n(d + 1) parameters.
- The universal law of robustness: n(d + 1) parameters suffice for robust interpolation, making the lower bound essentially tight when Lip(f) = O(1).Projecting inputs onto a subspace of dimension approximately p/n traces essentially the full model-size–robustness tradeoff curve.
- Scope and limitations: The theorem assumes squared-error regression, polynomially bounded weights, and ℓ2 Lipschitzness, so extensions to classification, unrestricted weights, and ℓ∞ robustness remain bounded or unresolved.The authors note that the two-layer conjecture with arbitrarily weighted networks is not fully proved, while polynomial weight control is necessary for three-layer networks.
- Empirical implications: 2 × 10^5–3 × 10^6 parameters produced smooth MNIST models below the noise level, compared with the predicted lower range nd = 10^6–10^7.This prediction is described as more accurate than the classical estimate of roughly 10^4 parameters, though the comparison has several caveats.
- Empirical implications: ImageNet estimates suggest 10^10–10^11 parameters for good robust models, exceeding the 10^8–10^9 parameters of current robustly trained networks.The estimate is speculative because effective dimension, noise, and the relationship between training error, Lipschitz robustness, and robust generalization error are uncertain.
2 A finite approach to the law of robustness
The paper shifts from counting interpolation equations to bounding how often smooth functions can fit noisy data. Under isoperimetry and positive conditional noise, fitting below the noise level is unlikely unless the function class is sufficiently large.
- Proof strategy: Isoperimetry implies that an individual smooth function has a small probability of fitting random labels, motivating a finite-class union bound.The proof focuses on the probability that a fixed function gives a good fit, then controls the probability that any function in a finite class does so.
- Main theorem: For finite classes, the fitting probability decreases with log(N), while discretizing a p-parameter family gives log(N) = ˜O(p).This connects finite-class concentration to the parameter-count lower bound for continuously parametrized models.
- Assumptions: Theorem 2 assumes a mixture of c-isoperimetric covariate distributions and strictly positive expected conditional output variance.The labels are decomposed into a target function and a mean-zero noise term, allowing concentration arguments to control correlation with noise.
- Proof strategy: The proof combines isoperimetric concentration with Hoeffding and Bernstein inequalities to bound the probability that functions fit below the noise level.The argument first shows that a good fit must correlate with the noise component, then applies concentration and a union bound over the finite class.
- Main theorem: Theorem 4 extends the lower bound to smoothly parametrized classes with p parameters, bounded parameter diameter, isoperimetric covariates, positive noise, and sufficiently large d.With high probability, the resulting inequality holds simultaneously for every function in the class; sparse parameterizations receive an improved bound.
3 Deep neural networks
The paper applies its robustness law to a broad class of multilayer neural networks parameterized by bounded weights and biases. The resulting bound preserves the nd scaling for constant-depth networks, with depth entering through network-size factors.
- Network class: The neural-network class allows layered architectures with fixed 1-Lipschitz nonlinearities, variable weights, scalar biases, and skip connections.The parametrization maps a p-dimensional vector to the network’s variable matrix entries and biases.
- Network class: Parameters are bounded by W, while Q measures the maximum number of network entries tied to one parameter and R bounds the input norm.These quantities control the parametrization’s Lipschitz behavior and enter the resulting robustness bound.
- Lipschitz control: Uniformly controlling B(w), an upper bound on the network’s input Lipschitz constant, also controls the parameter-to-function Lipschitz constant.The paper derives this through gradient bounds for the network output as a function of its parameters.
- Robustness law: For constant-depth neural networks, the law of robustness remains intact: smooth models with low training error require roughly nd parameters up to logarithmic factors.The bound hides logarithmic factors in W, p, R, Q, and δ.
- Depth dependence: The lower bound decreases with depth D, suggesting parameter allocation toward depth rather than width, although the role of depth remains unresolved.The authors note that proving tightness at large depth would require an exponential gap between the network Lipschitz constant and B(w), for which they know no example.
4 Generalization Perspective
The robustness law also yields a generalization perspective: isoperimetry can improve uniform convergence bounds for smooth-function classes beyond squared loss. The key complexity quantity measures correlation with random label noise.
- Complexity interpretation: Data-dependent Rademacher complexity measures a function class’s ability to correlate with random noise.The paper uses this quantity to connect the robustness argument with standard generalization machinery.
- Interpretation: The new feature is that isoperimetry of the covariates yields improved generalization guarantees for smooth-function classes.This generalization interpretation applies beyond the squared-loss analysis in the main text.
- Finite classes: For finite classes of bounded L-Lipschitz functions under mixtures of c-isoperimetric distributions, the paper gives an explicit bound on noise correlation.The finite-class result is the starting point for the generalization interpretation.
- General losses: Corollary 4.2 extends the uniform convergence result to any bounded loss that is 1-Lipschitz in its first argument.The bound holds with probability at least 1−δ in the setting of the preceding lemma.
- Continuous classes: An epsilon-net extends the argument from finite classes to continuously parametrized function classes.This transfers the finite-class generalization perspective to smooth parameterizations.
A Necessity of Polynomially Bounded Weights
The paper proves the robustness law for smoothly parametrized classes with polynomially bounded parameters, then shows that dropping this restriction permits counterexamples using highly expressive constructions.
- A Necessity of Polynomially Bounded Weights: Polynomially bounded parameters are required for the robustness law to hold for arbitrary smoothly parametrized function classes.The paper states that this restriction is necessary for bounded-depth neural networks.
- A Necessity of Polynomially Bounded Weights: A single parameter can encode all Lipschitz functions on a compact subset of R^d by brute-force enumeration, eliminating any parameter–Lipschitz tradeoff.This construction shows why unrestricted parameter magnitudes would make a general law impossible.
- A Necessity of Polynomially Bounded Weights: Theorem 5 constructs a continuous nonlinearity and offsets such that a family Φ_a is O(d^3/2)-Lipschitz while its parametrization a → Φ_a is 1-Lipschitz.The construction therefore provides a highly expressive, smoothly parametrized family with one scalar parameter.
- A Necessity of Polynomially Bounded Weights: The construction represents extended cell functions with two-layer networks and combines them through a specially chosen nonlinearity, yielding a three-layer network.The final-layer terms are matrix entries, so the representation in the appendix is formally three-layer.