mlsanityData to 7 Oct 2026

On Uniform Convergence and Low-Norm Interpolation Learning

arXiv 2006.05942 ↗First posted 10 Jun 2020stat.ML cs.LGcited by 24

Not on the map. Why?

Abstract (arXiv)

We consider an underdetermined noisy linear regression model where the minimum-norm interpolating predictor is known to be consistent, and ask: can uniform convergence in a norm ball, or at least (following Nagarajan and Kolter) the subset of a norm ball that the algorithm selects on a typical input set, explain this success? We show that uniformly bounding the difference between empirical and population errors cannot show any learning in the norm ball, and cannot show consistency for any set, even one depending on the exact algorithm and distribution. But we argue we can explain the consistency of the minimal-norm interpolator with a slightly weaker, yet standard, notion: uniform convergence of zero-error predictors in a norm ball. We use this to bound the generalization error of low- (but not minimal-) norm interpolating predictors.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). First posted on arXiv 10 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 6; 2023: 4; 2024: 2; 2025: 2; 2026: 1.

24 papers.

Sort:

  1. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 130
  2. 2021Assessing Generalization of SGD via Disagreementcited by 116
  3. 2022Agreement-on-the-Line: Predicting the Performance of Neural Networks under Distribution Shiftcited by 94
  4. 2021On Linear Stability of SGD and Input-Smoothness of Neural Networkscited by 61
  5. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  6. 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 54
  7. 2023Towards Last-layer Retraining for Group Robustness with Fewer Annotationscited by 54
  8. 2022The Implicit Bias of Benign Overfittingcited by 38
  9. 2022Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Biascited by 21
  10. 2021RATT: Leveraging Unlabeled Data to Guarantee Generalizationcited by 20
  11. 2021Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regressioncited by 17
  12. 2021Tight bounds for minimum l1-norm interpolation of noisy datacited by 16
12 more
  1. 2024Implicit Optimization Bias of Next-Token Prediction in Linear Modelscited by 14
  2. 2021Exact Gap between Generalization Error and Uniform Convergence in Random Feature Modelscited by 13
  3. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11
  4. 2023Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuroncited by 8
  5. 2022Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergencecited by 6
  6. 2023An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regressioncited by 5
  7. 2023Implicit Regularization Leads to Benign Overfitting for Sparse Linear Regressioncited by 4
  8. 2022Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regressioncited by 3
  9. 2025Transfer Learning for Benign Overfitting in High-Dimensional Linear Regressioncited by 2
  10. 2024Assessing Model Generalization in Vicinitycited by 0
  11. 2025Optimal Implicit Bias in Linear Regressioncited by 0
  12. 2026Understanding Generalization Requires Universal Inductioncited by 0