# Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 17 Jun 2021.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [A Model of Double Descent for High-dimensional Binary Linear Classification](https://mlsanity.com/paper/1911.05822/) (2019)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors](https://mlsanity.com/paper/1912.04265/) (2019)
- [A framework to characterize performance of LASSO algorithms](https://mlsanity.com/paper/1303.7291/) (2013)
- [Failures of model-dependent generalization bounds for least-norm interpolation](https://mlsanity.com/paper/2010.08479/) (2020)
- [On Uniform Convergence and Low-Norm Interpolation Learning](https://mlsanity.com/paper/2006.05942/) (2020)
- [Universality laws for randomized dimension reduction, with applications](https://mlsanity.com/paper/1511.09433/) (2015)
- [On the robustness of minimum norm interpolators and regularized empirical risk minimizers](https://mlsanity.com/paper/2012.00807/) (2020)
- [Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models](https://mlsanity.com/paper/2103.04554/) (2021)
- [Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degree](https://mlsanity.com/paper/2002.00492/) (2020)

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

- [The Lazy Neuron Phenomenon: On Emergence of Activation Sparsity in Transformers](https://mlsanity.com/paper/2210.06313/) (2022)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Towards Last-layer Retraining for Group Robustness with Fewer Annotations](https://mlsanity.com/paper/2309.08534/) (2023)
- [Predicting Out-of-Distribution Error with the Projection Norm](https://mlsanity.com/paper/2202.05834/) (2022)
- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022)
- [Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting](https://mlsanity.com/paper/2207.06569/) (2022)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [Foolish Crowds Support Benign Overfitting](https://mlsanity.com/paper/2110.02914/) (2021)
- [Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias](https://mlsanity.com/paper/2203.03597/) (2022)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks](https://mlsanity.com/paper/2108.11489/) (2021)
- [A PAC-Bayesian Generalization Bound for Equivariant Networks](https://mlsanity.com/paper/2210.13150/) (2022)
- [Regularization properties of adversarially-trained linear regression](https://mlsanity.com/paper/2310.10807/) (2023)
- [More is Better in Modern Machine Learning: when Infinite Overparameterization is Optimal and Overfitting is Obligatory](https://mlsanity.com/paper/2311.14646/) (2023)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [Tight bounds for minimum l1-norm interpolation of noisy data](https://mlsanity.com/paper/2111.05987/) (2021)
- [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [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)
- [Deep Linear Networks can Benignly Overfit when Shallow Ones Do](https://mlsanity.com/paper/2209.09315/) (2022)
- [Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron](https://mlsanity.com/paper/2303.02255/) (2023)
- [Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization](https://mlsanity.com/paper/2403.07264/) (2024)
- [A Universal Trade-off Between the Model Size, Test Loss, and Training Loss of Linear Predictors](https://mlsanity.com/paper/2207.11621/) (2022)
- [Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?](https://mlsanity.com/paper/2306.09955/) (2023)
- [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024)

## Abstract (arXiv)

We consider interpolation learning in high-dimensional linear regression with Gaussian data, and prove a generic uniform convergence guarantee on the generalization error of interpolators in an arbitrary hypothesis class in terms of the class's Gaussian width. Applying the generic bound to Euclidean norm balls recovers the consistency result of Bartlett et al. (2020) for minimum-norm interpolators, and confirms a prediction of Zhou et al. (2020) for near-minimal-norm interpolators in the special case of Gaussian data. We demonstrate the generality of the bound by applying it to the simplex, obtaining a novel consistency result for minimum l1-norm interpolators (basis pursuit). Our results show how norm-based generalization bounds can explain and be used to analyze benign overfitting, at least in some settings.