A Universal Trade-off Between the Model Size, Test Loss, and Training Loss of Linear Predictors
This provides a foundational theoretical insight into the behavior of linear models in overparameterized regimes, relevant for understanding modern machine learning practices.
The paper establishes a universal trade-off between model size, test loss, and training loss for linear predictors, showing that low test loss requires either training loss near the noise level or high overparameterization, with precise asymptotic analysis under Marchenko-Pastur distributions.
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.