mlsanityData to 7 Oct 2026

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

arXiv 2403.07264 ↗First posted 12 Mar 2024stat.ML cs.LGcited by 7

Not on the map. Why?

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.

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

Builds on

34 of 63 references.

References · 34

  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. 2021Explaining Neural Scaling Lawscited by 353
  5. 2020Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networkscited by 200
  6. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  7. 2018To understand deep learning we need to understand kernel learningcited by 186
  8. 2020Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networkscited by 166
  9. 2020Benign overfitting in ridge regressioncited by 152
  10. 2021A Universal Law of Robustness via Isoperimetrycited by 150
  11. 2015High-Dimensional Asymptotics of Prediction: Ridge Regression and Classificationcited by 146
  12. 2020Optimal Regularization Can Mitigate Double Descentcited by 107
22 more
  1. 2019Traditional and Heavy-Tailed Self Regularization in Neural Network Modelscited by 104
  2. 2020On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regressioncited by 97
  3. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 95
  4. 2019Harnessing the Power of Infinitely Wide Deep Nets on Small-data Taskscited by 87
  5. 2022More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalizecited by 87
  6. 2020Implicit Regularization of Random Feature Modelscited by 54
  7. 2020Kernel Alignment Risk Estimator: Risk Prediction from Training Datacited by 54
  8. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  9. 2022Dimension free ridge regressioncited by 50
  10. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  11. 2019Exact expressions for double descent and implicit regularization via surrogate random designcited by 35
  12. 2021Early-stopped neural networks are consistentcited by 34
  13. 2021SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticalitycited by 33
  14. 2022Spectral Evolution and Invariance in Linear-width Neural Networkscited by 30
  15. 2021The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networkscited by 25
  16. 2022Characterizing the Spectrum of the NTK via a Power Series Expansioncited by 22
  17. 2020Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysiscited by 14
  18. 2022Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditionscited by 9
  19. 2022A Universal Trade-off Between the Model Size, Test Loss, and Training Loss of Linear Predictorscited by 7
  20. 2017Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networkscited by 6
  21. 2022Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networkscited by 5
  22. 2023Least Squares Regression Can Exhibit Under-Parameterized Double Descentcited by 4

Built on by

Cited by year

Citing papers per year: 2024: 4; 2025: 3.

7 papers.

  1. 2024Model Balancing Helps Low-data Training and Fine-tuningcited by 11
  2. 2024On Regularization via Early Stopping for Least Squares Regressioncited by 10
  3. 2025Low Rank Gradients and Where to Find Themcited by 4
  4. 2024Generalization for Least Squares Regression With Simple Spiked Covariancescited by 2
  5. 2024Error dynamics of mini-batch gradient descent with random reshuffling for least squares regressioncited by 0
  6. 2025A Ridge Too Far: Correcting Over-Shrinkage via Negative Regularizationcited by 0
  7. 2025Matricial Free Energy as a Gaussianizing Regularizer: Enhancing Autoencoders for Gaussian Code Generationcited by 0