A Continuous-Time View of Early Stopping for Least Squares

Abstract

We study the statistical properties of the iterates generated by gradient descent, applied to the fundamental problem of least squares regression. We take a continuous-time view, i.e., consider infinitesimal step sizes in gradient descent, in which case the iterates form a trajectory called gradient flow. Our primary focus is to compare the risk of gradient flow to that of ridge regression. Under the calibration $t=1/\lambda$---where $t$ is the time parameter in gradient flow, and $\lambda$ the tuning parameter in ridge regression---we prove that the risk of gradient flow is no less than 1.69 times that of ridge, along the entire path (for all $t\ge 0$). This holds in finite samples with very weak assumptions on the data model (in particular, with no assumptions on the features $X$). We prove that the same relative risk bound holds for prediction risk, in an average sense over the underlying signal ${\beta }_0$. Finally, we examine limiting risk expressions (under standard Marchenko-Pastur asymptotics), and give supporting numerical experiments.

References in corpus (3)

• Characterizing Implicit Bias in Terms of Optimization Geometry
• Random design analysis of ridge regression
• Efficient Computation of Limit Spectra of Sample Covariance Matrices

Cited by in corpus (11)

• Overfitting in adversarially robust deep learning
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models
• On the Optimal Weighted ${\ell }_2$ Regularization in Overparameterized Linear Regression
• When Does Preconditioning Help or Hurt Generalization?
• Regularization in High-Dimensional Regression and Classification via Random Matrix Theory
• Implicit Regularization and Convergence for Weight Normalization
• RATT: Leveraging Unlabeled Data to Guarantee Generalization
• A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval
• An algorithmic view of ${\ell }_2$ regularization and some path-following algorithms
• Early stopping and polynomial smoothing in regression with reproducing kernels