# Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 63 references that are in the map.
- First posted on arXiv 12 Mar 2024.

## Builds on (most cited first, 30 of 34)

- [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)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2002.02561/) (2020)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [To understand deep learning we need to understand kernel learning](https://mlsanity.com/paper/1802.01396/) (2018)
- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [Optimal Regularization Can Mitigate Double Descent](https://mlsanity.com/paper/2003.01897/) (2020)
- [Traditional and Heavy-Tailed Self Regularization in Neural Network Models](https://mlsanity.com/paper/1901.08276/) (2019)
- [On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regression](https://mlsanity.com/paper/2006.05800/) (2020)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalize](https://mlsanity.com/paper/2203.06176/) (2022)
- [Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks](https://mlsanity.com/paper/1910.01663/) (2019)
- [Implicit Regularization of Random Feature Models](https://mlsanity.com/paper/2002.08404/) (2020)
- [Kernel Alignment Risk Estimator: Risk Prediction from Training Data](https://mlsanity.com/paper/2006.09796/) (2020)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Dimension free ridge regression](https://mlsanity.com/paper/2210.08571/) (2022)
- [Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model](https://mlsanity.com/paper/2006.08212/) (2020)
- [Exact expressions for double descent and implicit regularization via surrogate random design](https://mlsanity.com/paper/1912.04533/) (2019)
- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [Early-stopped neural networks are consistent](https://mlsanity.com/paper/2106.05932/) (2021)
- [Spectral Evolution and Invariance in Linear-width Neural Networks](https://mlsanity.com/paper/2211.06506/) (2022)
- [The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2110.03922/) (2021)
- [Characterizing the Spectrum of the NTK via a Power Series Expansion](https://mlsanity.com/paper/2211.07844/) (2022)
- [Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis](https://mlsanity.com/paper/2006.04299/) (2020)
- [Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions](https://mlsanity.com/paper/2202.00992/) (2022)

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

- [On Regularization via Early Stopping for Least Squares Regression](https://mlsanity.com/paper/2406.04425/) (2024)
- [Model Balancing Helps Low-data Training and Fine-tuning](https://mlsanity.com/paper/2410.12178/) (2024)
- [Low Rank Gradients and Where to Find Them](https://mlsanity.com/paper/2510.01303/) (2025)
- [Generalization for Least Squares Regression With Simple Spiked Covariances](https://mlsanity.com/paper/2410.13991/) (2024)
- [Error dynamics of mini-batch gradient descent with random reshuffling for least squares regression](https://mlsanity.com/paper/2406.03696/) (2024)
- [A Ridge Too Far: Correcting Over-Shrinkage via Negative Regularization](https://mlsanity.com/paper/2508.17412/) (2025)
- [Matricial Free Energy as a Gaussianizing Regularizer: Enhancing Autoencoders for Gaussian Code Generation](https://mlsanity.com/paper/2510.17120/) (2025)
- [The Fourth Quadrant: A Stylized View of Benign Misfitting](https://mlsanity.com/paper/2608.01032/) (2026)

## Abstract (arXiv)

We study the generalization capability of nearly-interpolating linear regressors: boldsymbolβ's whose training error τ is positive but small, i.e., below the noise floor. Under a random matrix theoretic assumption on the data distribution and an eigendecay assumption on the data covariance matrix boldsymbolSigma, we demonstrate that any near-interpolator exhibits rapid norm growth: for τ fixed, boldsymbolβ has squared ℓ2-norm mathbbE[|boldsymbolβ|22] = Omega(nα) where n is the number of samples and α >1 is the exponent of the eigendecay, i.e., λi(boldsymbolSigma) ~ i-α. This implies that existing data-independent norm-based bounds are necessarily loose. On the other hand, in the same regime we precisely characterize the asymptotic trade-off between interpolation and generalization. Our characterization reveals that larger norm scaling exponents α correspond to worse trade-offs between interpolation and generalization. We verify empirically that a similar phenomenon holds for nearly-interpolating shallow neural networks.