Timezone: »

 
A Universal Law of Robustness via Isoperimetry
Sebastien Bubeck · Mark Sellke

Sat Jul 24 02:50 PM -- 03:05 PM (PDT) @
in Over-parameterization: Pitfalls and Opportunities »
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 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 (or a mixture thereof). In the case of two-layer neural networks and Gaussian covariates, this law was conjectured in prior work by Bubeck, Li and Nagaraj.

Author Information

Sebastien Bubeck (Microsoft Research)
Mark Sellke

More from the Same Authors