# Exact expressions for double descent and implicit regularization via surrogate random design

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2019.

## Built on by (most cited first, 30 of 35)

- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Noisy Recurrent Neural Networks](https://mlsanity.com/paper/2102.04877/) (2021)
- [Taxonomizing local versus global structure in neural network loss landscapes](https://mlsanity.com/paper/2107.11228/) (2021)
- [Towards an Understanding of Benign Overfitting in Neural Networks](https://mlsanity.com/paper/2106.03212/) (2021)
- [Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions](https://mlsanity.com/paper/2206.07252/) (2022)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model](https://mlsanity.com/paper/2110.11805/) (2021)
- [The Interpolating Information Criterion for Overparameterized Models](https://mlsanity.com/paper/2307.07785/) (2023)
- [Monotonicity and Double Descent in Uncertainty Estimation with Gaussian Processes](https://mlsanity.com/paper/2210.07612/) (2022)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Eigenspectrum Analysis of Neural Networks without Aspect Ratio Bias](https://mlsanity.com/paper/2506.06280/) (2025)
- [Deep Learning Through A Telescoping Lens: A Simple Model Provides Empirical Insights On Grokking, Gradient Boosting & Beyond](https://mlsanity.com/paper/2411.00247/) (2024)
- [Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization](https://mlsanity.com/paper/2403.07264/) (2024)
- [On the Role of Optimization in Double Descent: A Least Squares Study](https://mlsanity.com/paper/2107.12685/) (2021)
- [Random matrices in service of ML footprint: ternary random features with no performance loss](https://mlsanity.com/paper/2110.01899/) (2021)
- [Bias-variance decomposition of overparameterized regression with random linear features](https://mlsanity.com/paper/2203.05443/) (2022)
- [On the Double Descent of Random Features Models Trained with SGD](https://mlsanity.com/paper/2110.06910/) (2021)
- [A PAC-Bayesian Perspective on the Interpolating Information Criterion](https://mlsanity.com/paper/2311.07013/) (2023)
- [The Geometry of Over-parameterized Regression and Adversarial Perturbations](https://mlsanity.com/paper/2103.14108/) (2021)
- [On Optimal Early Stopping: Over-informative versus Under-informative Parametrization](https://mlsanity.com/paper/2202.09885/) (2022)
- [Hardness of Maximum Likelihood Learning of DPPs](https://mlsanity.com/paper/2205.12377/) (2022)
- [Least Squares Regression Can Exhibit Under-Parameterized Double Descent](https://mlsanity.com/paper/2305.14689/) (2023)
- [Investigating the Impact of Model Width and Density on Generalization in Presence of Label Noise](https://mlsanity.com/paper/2208.08003/) (2022)
- [Does Double Descent Occur in Self-Supervised Learning?](https://mlsanity.com/paper/2307.07872/) (2023)
- ["Lossless" Compression of Deep Neural Networks: A High-dimensional Neural Tangent Kernel Approach](https://mlsanity.com/paper/2403.00258/) (2024)
- [A Model Zoo on Phase Transitions in Neural Networks](https://mlsanity.com/paper/2504.18072/) (2025)
- [Generalization for Least Squares Regression With Simple Spiked Covariances](https://mlsanity.com/paper/2410.13991/) (2024)
- [Stochastic Perturbations of Tabular Features for Non-Deterministic Inference with Automunge](https://mlsanity.com/paper/2202.09248/) (2022)
- [Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent](https://mlsanity.com/paper/2205.00058/) (2022)
- [The Directional Bias Helps Stochastic Gradient Descent to Generalize in Kernel Regression Models](https://mlsanity.com/paper/2205.00061/) (2022)

## Abstract (arXiv)

Double descent refers to the phase transition that is exhibited by the generalization error of unregularized learning models when varying the ratio between the number of parameters and the number of training samples. The recent success of highly over-parameterized machine learning models such as deep neural networks has motivated a theoretical analysis of the double descent phenomenon in classical models such as linear regression which can also generalize well in the over-parameterized regime. We provide the first exact non-asymptotic expressions for double descent of the minimum norm linear estimator. Our approach involves constructing a special determinantal point process which we call surrogate random design, to replace the standard i.i.d. design of the training sample. This surrogate design admits exact expressions for the mean squared error of the estimator while preserving the key properties of the standard design. We also establish an exact implicit regularization result for over-parameterized training samples. In particular, we show that, for the surrogate design, the implicit bias of the unregularized minimum norm estimator precisely corresponds to solving a ridge-regularized least squares problem on the population distribution. In our analysis we introduce a new mathematical tool of independent interest: the class of random matrices for which determinant commutes with expectation.