mlsanityData to 7 Oct 2026

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

arXiv 2106.09276 ↗First posted 17 Jun 2021stat.ML cs.LG math.STcited by 54

Not on the map. Why?

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.

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

Builds on

18 of 41 references.

References · 18

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2019Benign Overfitting in Linear Regressioncited by 544
  3. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  4. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  5. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  6. 2019Two models of double descent for weak featurescited by 194
  7. 2020Benign overfitting in ridge regressioncited by 152
  8. 2019Harmless interpolation of noisy data in regressioncited by 121
  9. 2019A Model of Double Descent for High-dimensional Binary Linear Classificationcited by 81
  10. 2014Learning without Concentrationcited by 50
  11. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  12. 2013A framework to characterize performance of LASSO algorithmscited by 38
6 more
  1. 2020Failures of model-dependent generalization bounds for least-norm interpolationcited by 26
  2. 2020On Uniform Convergence and Low-Norm Interpolation Learningcited by 24
  3. 2015Universality laws for randomized dimension reduction, with applicationscited by 21
  4. 2020On the robustness of minimum norm interpolators and regularized empirical risk minimizerscited by 18
  5. 2021Exact Gap between Generalization Error and Uniform Convergence in Random Feature Modelscited by 13
  6. 2020Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degreecited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 14; 2023: 15; 2024: 9; 2025: 6; 2026: 5.

54 papers.

Sort:

  1. 2022The Lazy Neuron Phenomenon: On Emergence of Activation Sparsity in Transformerscited by 121
  2. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  3. 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 54
  4. 2023Towards Last-layer Retraining for Group Robustness with Fewer Annotationscited by 54
  5. 2022Predicting Out-of-Distribution Error with the Projection Normcited by 50
  6. 2022The Implicit Bias of Benign Overfittingcited by 38
  7. 2022Benign, Tempered, or Catastrophic: A Taxonomy of Overfittingcited by 36
  8. 2025Implicit Bias of Spectral Descent and Muon on Multiclass Separable Datacited by 33
  9. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  10. 2021Foolish Crowds Support Benign Overfittingcited by 24
  11. 2022Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Biascited by 21
  12. 2023Six Lectures on Linearized Neural Networkscited by 19
38 more
  1. 2021The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networkscited by 18
  2. 2021Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regressioncited by 17
  3. 2022A PAC-Bayesian Generalization Bound for Equivariant Networkscited by 17
  4. 2023Regularization properties of adversarially-trained linear regressioncited by 17
  5. 2023More is Better in Modern Machine Learning: when Infinite Overparameterization is Optimal and Overfitting is Obligatorycited by 17
  6. 2021Tight bounds for minimum l1-norm interpolation of noisy datacited by 16
  7. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
  8. 2024Implicit Optimization Bias of Next-Token Prediction in Linear Modelscited by 14
  9. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11
  10. 2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
  11. 2022The Sample Complexity of One-Hidden-Layer Neural Networkscited by 10
  12. 2023Benign Overfitting in Deep Neural Networks under Lazy Trainingcited by 10
  13. 2022Deep Linear Networks can Benignly Overfit when Shallow Ones Docited by 8
  14. 2023Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuroncited by 8
  15. 2022A Universal Trade-off Between the Model Size, Test Loss, and Training Loss of Linear Predictorscited by 7
  16. 2023Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?cited by 7
  17. 2024Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalizationcited by 7
  18. 2024Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionalitycited by 7
  19. 2022Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergencecited by 6
  20. 2023Interpolation Learning With Minimum Description Lengthcited by 5
  21. 2023An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regressioncited by 5
  22. 2024Benign overfitting in leaky ReLU networks with moderate input dimensioncited by 5
  23. 2023Implicit Regularization Leads to Benign Overfitting for Sparse Linear Regressioncited by 4
  24. 2023Universality of max-margin classifierscited by 4
  25. 2024The Star Geometry of Critic-Based Regularizer Learningcited by 3
  26. 2025Beyond Benign Overfitting in Nadaraya-Watson Interpolatorscited by 2
  27. 2025Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classificationcited by 2
  28. 2025Transfer Learning for Benign Overfitting in High-Dimensional Linear Regressioncited by 2
  29. 2022Benign-Overfitting in Conditional Average Treatment Effect Prediction with Linear Regressioncited by 1
  30. 2024Probability Distribution Learning and Its Application in Deep Learningcited by 1
  31. 2024Implicit Regularization Paths of Weighted Neural Representationscited by 1
  32. 2025Closed-form ℓr norm scaling with data for overparameterized linear regression and diagonal linear networks under ℓp biascited by 1
  33. 2026Generalization in Nonlinear Least Squares via Learned Feature Geometrycited by 1
  34. 2022Tight bounds for maximum ℓ1-margin classifierscited by 0
  35. 2023Bayesian Analysis for Over-parameterized Linear Model via Effective Spectracited by 0
  36. 2024Bayesian Inference for Consistent Predictions in Overparameterized Nonlinear Regressioncited by 0
  37. 2024Benign Overfitting under Learning Rate Conditions for α Sub-exponential Inputcited by 0
  38. 2025Optimal Implicit Bias in Linear Regressioncited by 0

50 most cited of 54 All 54 (JSON)