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

Abstract

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.

arXiv commentMinor typo corrections and clarifications; moved the proofs into the appendix

References in corpus (22)

• Benign Overfitting in Linear Regression
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Scaling description of generalization with number of parameters in deep learning
• Randomized algorithms for matrices and data
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning
• Implicit Regularization in Deep Learning
• Fast Randomized Kernel Methods With Statistical Guarantees
• Leveraged volume sampling for linear regression
• Understanding overfitting peaks in generalization error: Analytical risk curves for $l_2$ and $l_1$ penalized interpolation
• Fast determinantal point processes via distortion-free intermediate sampling
• Unbiased estimates for linear regression via volume sampling
• Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization
• Subsampling for Ridge Regression via Regularized Volume Sampling
• The Implicit Regularization of Ordinary Least Squares Ensembles
• Correcting the bias in least squares regression with volume-rescaled sampling
• Implicit Regularization in Over-parameterized Neural Networks
• Distributed estimation of the inverse Hessian by determinantal averaging
• Unbiased estimators for random design regression
• Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression
• Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling
• Bayesian experimental design using regularized determinantal point processes

Cited by in corpus (18)

• Benign overfitting in ridge regression
• Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models
• Optimal Regularization Can Mitigate Double Descent
• More Data Can Hurt for Linear Regression: Sample-wise Double Descent
• What causes the test error? Going beyond bias-variance via ANOVA
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent
• On the Optimal Weighted ${\ell }_2$ Regularization in Overparameterized Linear Regression
• Failures of model-dependent generalization bounds for least-norm interpolation
• Kernel regression in high dimensions: Refined analysis beyond double descent
• Towards an Understanding of Benign Overfitting in Neural Networks
• Provable More Data Hurt in High Dimensional Least Squares Estimator
• Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent
• On the mean projection theorem for determinantal point processes
• Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
• The Directional Bias Helps Stochastic Gradient Descent to Generalize in Kernel Regression Models
• Good Classifiers are Abundant in the Interpolating Regime
• Avoiding Kernel Fixed Points: Computing with ELU and GELU Infinite Networks
• Precise expressions for random projections: Low-rank approximation and randomized Newton