Why does early-stopped gradient descent shrink coefficients much like a ridge penalty?

### Two ways to shrink the same coefficients A ridge penalty adds `lambda * sum(w_j^2)` to a squared-error loss and pulls every coefficient toward zero, hardest where the data has least to say. Early stopping adds nothing to the loss; it just refuses to run the optimizer to convergence. The striking fact is that, in the cleanest case, these two produce nearly the same estimator — early stopping is a penalty you never wrote down. ### The clean case, stated exactly Take least squares fitted by full-batch gradient descent, started at `w = 0`, with a fixed learning rate `lr` small enough to converge. Rotate the problem into the eigen-directions of the input covariance matrix — the uncorrelated directions along which the predictors vary — and let `d_j` be the eigenvalue of direction `j`. Large `d_j` means the data varies a lot along that direction, so the least-squares coefficient there is well determined; small `d_j` means the data barely moves along it and the coefficient is mostly noise. In those coordinates the two estimators are simple multiples of the ordinary least-squares solution: ``` gradient descent, t steps: factor_j = 1 - (1 - lr * d_j)^t ridge, penalty lambda: factor_j = d_j / (d_j + lambda) ``` Read both factors at the extremes: - **Large `d_j`.** `(1 - lr*d_j)^t` decays fast, so the gradient-descent factor is close to 1 after a handful of steps. Ridge's `d_j / (d_j + lambda)` is also close to 1. Neither method shrinks the well-determined directions much. - **Small `d_j`.** `(1 - lr*d_j)^t` is approximately `1 - lr*d_j*t`, so the gradient-descent factor is approximately `lr * d_j * t` — near zero. Ridge's factor is approximately `d_j / lambda` — also near zero. Both crush the weakly-determined directions. The two shrinkage profiles have the same shape, and matching them gives the rule of thumb `lambda ≈ 1 / (lr * t)`. ### The direction that candidates get backwards More iterations means **less** regularization. Each step moves every factor closer to 1, i.e. closer to the unpenalised least-squares fit, which corresponds to a *smaller* lambda. Fewer iterations means heavier shrinkage, i.e. a *larger* lambda. Stating this the other way round is the single most common error on this topic, and it also makes the practical advice wrong: if a model is overfitting, you stop sooner, not later. ### Why the ordering happens at all The intuition behind the algebra is that gradient descent from zero learns the easy things first. The gradient along a direction is proportional to how much variation the data has along it, so high-variance, high-signal directions are traversed in a few steps while low-variance directions creep forward. Freeze the run at step `t` and you have a fit in which strong structure is complete and weak structure is still near its starting value — which is exactly the profile a squared penalty imposes. This is also why the whole regularization path comes free: one run passes through every effective lambda from very large (step 1) down to zero (convergence), where a penalty approach needs a separate fit per lambda. ### Where the equivalence stops being exact It is an exact statement only for this setting: squared loss, linear model, full-batch gradient descent, zero start. Several things weaken it. - **Shrinkage is toward the starting point, not toward zero.** Initialise at some non-zero vector and early stopping shrinks toward *that* vector. Sometimes that is what you want; it is not ridge. - **Other losses.** For logistic regression the correspondence is only approximate and local, because the curvature of the loss changes as the fit moves. The qualitative ordering — well-determined directions first — survives; the closed-form factors do not. - **Stochastic updates and adaptive step sizes** perturb the path, so the implied penalty is no longer a clean function of the step count. - **You cannot report the lambda.** With ridge you have a number you can log, hold fixed across retrains, and reason about. With early stopping the effective penalty depends on the learning rate, the step count, the initialisation and the data's eigen-spectrum, and it silently changes when any of them do. That is the real engineering cost of the cheaper method. ### Why interviewers ask it It is a differentiator, not a screener. Answering it well shows you understand regularization as *constraining which solutions the fit can reach*, rather than as a term you bolt onto a loss — and it explains why two knobs that look unrelated, penalty strength and run length, are often controlling the same thing.