# On Uniform Convergence and Low-Norm Interpolation Learning

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

## Key facts

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

## Built on by (most cited first, 24 of 24)

- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Assessing Generalization of SGD via Disagreement](https://mlsanity.com/paper/2106.13799/) (2021)
- [Agreement-on-the-Line: Predicting the Performance of Neural Networks under Distribution Shift](https://mlsanity.com/paper/2206.13089/) (2022)
- [On Linear Stability of SGD and Input-Smoothness of Neural Networks](https://mlsanity.com/paper/2105.13462/) (2021)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Towards Last-layer Retraining for Group Robustness with Fewer Annotations](https://mlsanity.com/paper/2309.08534/) (2023)
- [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022)
- [Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias](https://mlsanity.com/paper/2203.03597/) (2022)
- [RATT: Leveraging Unlabeled Data to Guarantee Generalization](https://mlsanity.com/paper/2105.00303/) (2021)
- [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)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models](https://mlsanity.com/paper/2103.04554/) (2021)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)
- [Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron](https://mlsanity.com/paper/2303.02255/) (2023)
- [Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence](https://mlsanity.com/paper/2206.07892/) (2022)
- [An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression](https://mlsanity.com/paper/2306.13185/) (2023)
- [Implicit Regularization Leads to Benign Overfitting for Sparse Linear Regression](https://mlsanity.com/paper/2302.00257/) (2023)
- [Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression](https://mlsanity.com/paper/2202.06054/) (2022)
- [Transfer Learning for Benign Overfitting in High-Dimensional Linear Regression](https://mlsanity.com/paper/2510.15337/) (2025)
- [Optimal Implicit Bias in Linear Regression](https://mlsanity.com/paper/2506.17187/) (2025)
- [Assessing Model Generalization in Vicinity](https://mlsanity.com/paper/2406.09257/) (2024)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)

## 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.