# A Universal Trade-off Between the Model Size, Test Loss, and Training Loss of Linear Predictors

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 32 references that are in the map.
- First posted on arXiv 23 Jul 2022.

## Builds on (most cited first, 26 of 26)

- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [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)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [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)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?](https://mlsanity.com/paper/2012.06421/) (2020)
- [The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization](https://mlsanity.com/paper/2008.06786/) (2020)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Towards an Understanding of Benign Overfitting in Neural Networks](https://mlsanity.com/paper/2106.03212/) (2021)
- [Foolish Crowds Support Benign Overfitting](https://mlsanity.com/paper/2110.02914/) (2021)
- [Memorize to Generalize: on the Necessity of Interpolation in High Dimensional Linear Regression](https://mlsanity.com/paper/2202.09889/) (2022)
- [On the Universality of the Double Descent Peak in Ridgeless Regression](https://mlsanity.com/paper/2010.01851/) (2020)
- [Benign overfitting and adaptive nonparametric regression](https://mlsanity.com/paper/2206.13347/) (2022)

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

- [Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension](https://mlsanity.com/paper/2305.14077/) (2023)
- [More is Better in Modern Machine Learning: when Infinite Overparameterization is Optimal and Overfitting is Obligatory](https://mlsanity.com/paper/2311.14646/) (2023)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization](https://mlsanity.com/paper/2403.07264/) (2024)
- [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024)
- [Feature maps for the Laplacian kernel and its generalizations](https://mlsanity.com/paper/2502.15575/) (2025)
- [The Price of Robustness: Stable Classifiers Need Overparameterization](https://mlsanity.com/paper/2603.02806/) (2026)

## Abstract (arXiv)

In this work we establish an algorithm and distribution independent non-asymptotic trade-off between the model size, excess test loss, and training loss of linear predictors. Specifically, we show that models that perform well on the test data (have low excess loss) are either "classical" -- have training loss close to the noise level, or are "modern" -- have a much larger number of parameters compared to the minimum needed to fit the training data exactly. We also provide a more precise asymptotic analysis when the limiting spectral distribution of the whitened features is Marchenko-Pastur. Remarkably, while the Marchenko-Pastur analysis is far more precise near the interpolation peak, where the number of parameters is just enough to fit the training data, it coincides exactly with the distribution independent bound as the level of overparametrization increases.