What is early stopping in an iteratively fitted model, and why does it act as regularization?

### The setting Some models are not solved in one shot; they are *approached*. Gradient descent on a logistic regression for ad click-through, for example, starts from a parameter vector of zeros and produces a sequence of parameter vectors `w_0, w_1, w_2, ...`, each one a slightly better fit to the training rows than the last. Early stopping is the decision to treat the index `t` in that sequence as a hyperparameter — chosen on data the optimizer never touches — instead of running until the training loss flattens. ### The two curves Score every iterate on two sets and you get two very different pictures. - **Training loss** falls monotonically (up to optimizer noise). It has to: that is the quantity the updates are minimising. It therefore carries no information about when to stop. - **Validation loss**, computed on a held-out slice that never enters a gradient, typically falls steeply, flattens, and then drifts upward. The upward drift is the fit starting to reproduce quirks of the training rows — coincidences of that particular sample — which do not repeat in the held-out slice. The best place to stop is near the bottom of the validation curve. Early stopping is the machinery for finding it without knowing in advance where it is. ### The loop A practical early-stopping loop keeps three pieces of state: the best validation score seen so far, the iterate that produced it, and a counter of consecutive checks since that best. 1. Run one pass (or a fixed block of iterations). 2. Evaluate the monitored metric on the validation slice. 3. If it improved on the best so far, record the new best, snapshot the parameters, reset the counter to zero. 4. Otherwise increment the counter; if it reaches `patience`, halt. 5. On halting, **restore the snapshot** — the best iterate — rather than shipping the parameters the optimizer happened to hold when the counter ran out. That last step is the one candidates skip, and it matters exactly as much as the stopping rule: with patience 10, the parameters at the moment of halting are by construction ten checks *worse* than the best you saw. Restoring is free — you already paid for the snapshot — so there is no reason to ship the tail of the run. Note also what early stopping is *not*: a fixed iteration cap. Capping the run at 500 passes because that is what fits in the training window is a compute budget, not early stopping. Early stopping is data-driven; the halt point moves when the data or the learning rate moves. ### Why halting early is regularization Regularization means reducing the variance of a fitted model — how much it would change if you redrew the training sample — usually at the cost of a little bias. A penalty term does this by making large coefficients expensive. Early stopping does it by never letting the optimizer *reach* the coefficients that overfit. The mechanism is that gradient descent from a small starting point learns in a useful order. The directions in the data that carry strong, repeated signal generate large gradients and are fitted within the first few passes. The directions that exist only because of sampling noise generate small gradients and are approached slowly. Stop at iteration `t` and the strong structure is essentially fully fitted while the weak, noise-driven structure is still near its starting value of zero. The result is a shrunken fit — very close to what an explicit squared penalty would have produced — with no extra term in the loss and no separate refit per penalty strength. This is why early stopping sits under *penalty-free* variance control: the iteration count is a capacity knob, and the run itself sweeps the whole path from heavily regularized (few iterations) to unregularized (convergence). ### What to monitor, and the honesty problem The monitored quantity should be the one you actually care about, evaluated on rows the gradient never sees. Validation log-loss every pass is the common default because it is cheap, smooth and defined for every iterate. A business-facing metric — say, revenue captured at a fixed impression budget — is more faithful but is often noisier and more expensive, so it is checked less often. Whatever you monitor, remember that the validation score at the stopped iterate is a *minimum over many checks*, so it is optimistically biased as an estimate of future performance. Early stopping consumes the validation slice as a tuning set. If you need a trustworthy number to report, keep a third split that took no part in the halt decision. ### When it disappoints Early stopping needs a validation slice, and on small data that slice is both expensive (rows withheld from training) and noisy (a stopping point chosen on 300 rows can be nearly arbitrary). There, choosing the iteration count by cross-validation — averaging the best iterate across folds, then refitting on everything for that many iterations — is the safer route. And if the validation curve never turns upward, the fit is not overfitting at this capacity; early stopping simply has nothing to do, and stopping anyway just gives up accuracy.