A Continuous-Time View of Early Stopping for Least Squares Regression

Alnur Ali, J. Zico Kolter, Ryan J. Tibshirani

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, where the iterates follow a path called gradient flow. We compare the risk of gradient flow at time $t$ to that of ridge regression with tuning parameter $\lambda = 1/t$. Our main result is that for any least squares problem, the risk of gradient flow is never more than 1.69 times the risk of ridge regression along the entire path.

Introduction

In modern machine learning, algorithms often produce "regularized" solutions that generalize well without explicit penalties on model complexity. This phenomenon, known as implicit regularization, is exemplified by early stopping: halting gradient descent before it reaches the training loss minimum to prevent overfitting. While practitioners have long observed that early stopping behaves similarly to ridge ($L_2$) regularization, the precise mathematical relationship has remained elusive, particularly across the entire optimization trajectory and in high-dimensional settings where the number of features $p$ may exceed the number of samples $n$.

This paper provides a rigorous theoretical bridge between early-stopped gradient descent and ridge regression. By analyzing "gradient flow"—gradient descent with infinitesimal step sizes—the authors quantify the proximity of these two paths, providing a strong theoretical justification for early stopping as a form of implicit regularization.

Methods

The authors employ a continuous-time perspective, analyzing gradient flow as the solution to the differential equation defined by the gradient of the least squares loss.

Spectral Calibration and Shrinkage

The comparison is facilitated by setting the gradient flow time parameter $t$ to be the reciprocal of the ridge tuning parameter $\lambda$ ($t = 1/\lambda$). Using Singular Value Decomposition (SVD), both estimators are decomposed into spectral filters that shrink low-variance directions. While ridge uses linear shrinkage, gradient flow employs exponential shrinkage.

Comparison of Risk Surfaces for Ridge and Gradient Flow

Risk Analysis and Asymptotic Theory

The study derives closed-form expressions for estimation and prediction risk. To analyze high-dimensional behavior where $n, p \to \infty$, the authors utilize the Marchenko-Pastur law from random matrix theory. These theoretical derivations are validated using synthetic datasets with various feature distributions (Gaussian, Student-t, Bernoulli) and covariance structures.

Key Results

The most significant finding is a universal constant: for any least squares problem, the estimation risk of gradient flow at time $t$ is at most $\approx 1.6862$ times the risk of ridge regression at $\lambda = 1/t$. This bound holds regardless of the data matrix $X$.

Optimality and Admissibility

When both methods are optimally tuned, the "Bayes risk" ratio decreases to approximately 1.2147. Furthermore, the authors demonstrate that gradient flow is an admissible Bayes estimator under a specific time-varying prior, suggesting it cannot be strictly improved upon without altering fundamental assumptions.

Asymptotic Accuracy and $L_2$ Calibration

Numerical experiments confirm that the derived asymptotic formulae are highly accurate even for finite samples. Interestingly, while $t=1/\lambda$ is the standard theoretical calibration, the authors found that calibrating the paths such that the $L_2$ norm of the weights $\|\beta\|_2$ is identical results in nearly indistinguishable risk curves.

Risk comparison under standard calibration (top) and L2 norm calibration (bottom).

Discussion

While this work provides a strong theoretical foundation for early stopping in least squares regression, several avenues for future research remain. The current analysis is restricted to linear models and full-batch gradient flow. Modern deep learning involves non-linearities and stochasticity (SGD), which likely introduces additional layers of implicit regularization. Future work could extend this continuous-time framework to logistic regression and further investigate the remarkable tightness of the $L_2$-norm calibration.

Summary updated

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 inf...
BibTeX
@inproceedings{ali2019continuous,
  author = {Alnur Ali and J. Zico Kolter and Ryan J. Tibshirani},
  title = {{A Continuous-Time View of Early Stopping for Least Squares Regression}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=3j7_T6Txmd8},
}
Figure