Stopping Early Is Almost Ridge: A Coordinate-Wise Proof That Gradient Descent's Risk Is Within a Factor 1.6859 of Ridge Regression, Checked on a Real Design With Condition Number 39,700

Training a model by gradient descent and stopping before convergence is the most common form of regularisation in machine learning, but it is usually justified by experience rather than by proof. For least squares the connection to ridge regression can be made exact. I show that gradient flow run for time t and ridge regression with penalty 1/t act on each eigen-direction of the design through the filters 1 − e⁻ˣ and x/(1+x), with x = t times the eigenvalue. From the inequality e⁻ˣ ≤ 1/(1+x), gradient flow has no more squared bias than ridge in every direction. Its variance is at most c² times ridge's, where c = max over x of (1 − e⁻ˣ)(1+x)/x = 1.29843 at x = 1.7933. Hence its estimation risk is never more than c² = 1.6859 times that of ridge with λ = 1/t, for any true coefficients, noise level or design. On the real design of the UCI Communities and Crime data (1,994 US communities, 99 complete predictors, eigenvalues of X′X/n from 0.00063 to 25.02), the worst ratio for a simulated truth is 1.3832 and the ratio of optimal risks is 1.0282. On the actual outcome, violent crime per head, across 50 random half splits, the best early-stopped fit has test error 1.0051 times that of the best ridge fit on average (range 0.9971–1.0153), and both beat ordinary least squares. The best stopping time is about 0.449 times the reciprocal of the best ridge penalty, not equal to it.