Show that early stopping on gradient descent for a linear model behaves like an L2 penalty. Give the correspondence between the number of steps, the learning rate, and the effective ridge parameter in the eigenbasis of X^T X.

Show that early stopping on gradient descent for a linear model behaves like an L2 penalty. Give the correspondence between the number of steps, the learning rate, and the effective ridge parameter in the eigenbasis of X^T X.

Approach: Diagonalise X^T X, solve the gradient descent recursion coordinate by coordinate, and compare the resulting shrinkage factor with the ridge one.

Stopping after t steps at learning rate eta is ridge with an effective penalty of lambda approximately 1/(eta*t), so more steps mean a weaker penalty. Along an eigenvector with eigenvalue d, t steps of gradient descent from zero initialisation retain a fraction (1 - (1 - eta*d)^t) of the least squares coefficient, and that factor matches the ridge shrinkage d/(d + lambda) at exactly that lambda. In the eigenbasis the recursion decouples into b_i^{(t)} = b_i^{ols} (1 - (1 - eta*d_i)^t), so directions with large eigenvalues converge within a few steps while small-eigenvalue directions are still near zero. For small eta*d_i the factor is approximately 1 - e^{-eta*d_i*t}, which is close to eta*d_i*t/(1 + eta*d_i*t), the ridge form whose penalty is one over eta times t. Early stopping is therefore a form of implicit regularization, and the practical consequence is that step count, learning rate and penalty strength are one knob rather than three, so tuning all of them independently on the same validation set inflates the number of configurations searched and the selection bias with it. It also explains why early stopping helps most on an ill-conditioned design: the poorly determined directions are exactly the ones left unfitted. The equivalence is exact only for a quadratic loss, and for a network it holds approximately in a linearised regime.

Follow-up: What is the largest stable learning rate in terms of the top eigenvalue, and what happens to the small-eigenvalue directions if you set eta just under that limit?

Key concepts: early stopping, implicit regularization, effective penalty, eigenbasis, learning rate.