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.
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.
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