Early Stopping

Consider training a model by minimizing a training loss $J_{\text{train}}(\theta)$ via gradient descent or a variant such as SGD. As training proceeds, $J_{\text{train}}$ decreases monotonically (on average), but the population risk — approximated by a held-out validation loss $J_{\text{val}}(\theta)$ — typically decreases at first and then starts to increase, because the model begins to fit noise specific to the training set. This divergence between training and validation curves is the signature of overfitting, covered in Overfitting and Regularization Strategies. Early stopping is the strategy of monitoring $J_{\text{val}}$ throughout training and halting at (or restoring to) the parameter values from the iteration where $J_{\text{val}}$ was lowest. Formally, if $\theta_t$ denotes parameters after $t$ update steps, early stopping selects

and returns $\theta_{t^*}$ as the final model, instead of $\theta_T$ (the fully converged, or budget-exhausted, parameters). Because checking validation loss at every single gradient step is expensive and noisy, in practice validation is evaluated every $k$ steps or once per epoch, and a patience parameter $p$ tolerates $p$ consecutive non-improving evaluations before actually terminating training — this guards against stopping on a single unlucky validation dip. The key conceptual move is treating the number of training iterations as an implicit capacity control knob, analogous to the regularization strength $\lambda$ in L2 regularization. A model partway through training has parameters that are still influenced by their initialization (commonly small, near zero) and by only a limited number of gradient updates; this restricts how far $\theta$ can travel from $\theta_0$, which restricts the effective function class the model can express. Stopping early is therefore a form of implicit regularization: it does not modify the loss function or add an explicit penalty term, yet it constrains the effective hypothesis space in a way that is mathematically related to explicit L2 penalties, as shown rigorously for linear regression under gradient descent (see Complexity & Correctness below).

The mechanism has four ingredients: a validation set disjoint from the training set, an evaluation schedule, a patience budget, and a checkpointing rule that remembers the best model seen so far.

Step-by-step: 1. Split data into training and validation sets (and a separate test set, untouched until final reporting). 2. Initialize parameters $\theta_0$, best validation score $v^* = +\infty$, best parameters $\theta^* = \theta_0$, and a stale counter $c = 0$. 3. For each epoch (or every $k$ steps): a. Run one epoch of the optimizer (SGD, Adam, etc.) over the training set, updating $\theta$. b. Compute validation loss $v = J_{\text{val}}(\theta)$. c. If $v < v^* - \delta$ (improvement beyond a small tolerance $\delta$), update $v^* \leftarrow v$, $\theta^* \leftarrow \theta$ (checkpoint), and reset $c \leftarrow 0$. d. Else, increment $c \leftarrow c + 1$. e. If $c \geq p$ (patience exhausted), stop training. 4. Return $\theta^*$, the parameters from the best-observed validation checkpoint — not the final-epoch parameters. The tolerance $\delta$ prevents the patience counter from resetting on negligible numerical fluctuations that are not real improvement. The patience $p$ trades responsiveness against robustness to noisy validation curves: $p=0$ stops at the very first uptick (fast, but easily fooled by noise); large $p$ rides out longer plateaus and temporary regressions at the cost of extra compute, converging back toward "train until the fixed budget $T$" as $p \to \infty$. ``` function EARLY_STOPPING_TRAIN(model, train_data, val_data, patience p, tolerance δ, max_epochs T): θ ← INITIALIZE_PARAMETERS(model) v_best ← +∞ θ_best ← θ stale ← 0 epoch ← 0 while epoch < T and stale < p: θ ← RUN_ONE_EPOCH(model, θ, train_data) # one pass of SGD/Adam updates v ← EVALUATE_LOSS(model, θ, val_data) # forward pass only, no gradient update if v < v_best - δ: v_best ← v θ_best ← COPY(θ) # checkpoint the improving model stale ← 0 else: stale ← stale + 1 epoch ← epoch + 1 return θ_best, v_best, epoch ``` Edge cases the pseudocode must handle correctly:

• No improvement ever occurs (validation loss increases from epoch 0): the loop still runs at

least until `stale = p`, and `θ_best` correctly remains the initial parameters — a degenerate but valid outcome (the best model is "barely trained").

• Budget exhausted before patience (`epoch = T` reached first): training stops due to the

`epoch < T` condition, and `θ_best` is still whatever the best checkpoint was, even if that was the very last epoch.

• Validation loss is flat (ties within $\delta$): treated as non-improvement, so `stale`

increments — this avoids infinite training on numerical noise around a plateau.

Time complexity. Early stopping adds one forward pass over the validation set per evaluation interval. If validation runs every epoch, and the validation set has $n_{\text{val}}$ examples while each epoch of training touches $n_{\text{train}}$ examples, the overhead per epoch is $O(n_{\text{val}})$ against a training cost of $O(n_{\text{train}})$ — typically negligible since validation sets are much smaller and require no backward pass. The real complexity benefit is that early stopping saves time and compute: instead of training for a fixed, possibly wasteful budget $T_{\max}$, training halts at $t^* + p \ll T_{\max}$ epochs whenever overfitting sets in early, so wall-clock cost scales with the actual point of diminishing returns rather than a worst-case guess.

Space complexity. Maintaining $\theta_{\text{best}}$ requires one extra copy of the full parameter set, i.e. $O(|\theta|)$ additional memory — the same order as the model itself, doubling parameter storage during training (though optimizer state, e.g. Adam's moment buffers, need not be checkpointed if only inference-time weights are needed later).

Correctness / why it regularizes. The claim to justify is not "the algorithm halts" (trivially true given finite patience and budget) but "halting at the validation minimum improves generalization relative to training to convergence." This is best understood through the classical result for linear regression trained by gradient descent with squared loss. Consider $J(\theta) = \frac{1}{2}\lVert y - X\theta \rVert^2$ with the Hessian $H = X^\top X$, eigendecomposed as $H = Q \Lambda Q^\top$. Gradient descent with learning rate $\epsilon$, initialized at $\theta_0 = 0$, after $t$ steps satisfies (in the rotated coordinate system $\tilde\theta = Q^\top \theta$):

where $\theta_*$ is the least-squares minimizer and $\lambda_i$ is the $i$-th eigenvalue of $H$. Compare this to the closed-form solution of L2-regularized (ridge) regression with penalty $\alpha$:

Both expressions are shrinkage factors applied to $\tilde\theta_*^{(i)}$ per eigen-direction, and setting

makes the two shrinkage factors approximately equal for each $i$. In words: training for $t$ gradient steps shrinks parameter components along low-curvature directions ($\lambda_i$ small) much less than along high-curvature directions, exactly mirroring how ridge regression shrinks low-curvature components less. Early stopping at iteration $t$ behaves like L2 regularization with strength $\alpha \approx 1/(\epsilon t)$. This gives a precise, non-hand-wavy sense in which stopping early constrains effective capacity the same way an explicit penalty does — smaller $t$ means larger effective $\alpha$, i.e. stronger regularization, connecting directly back to Weight Decay and L2 Regularization. For general non-convex deep networks this exact algebra does not hold, but the qualitative mechanism transfers: gradient descent from a small initialization first fits the directions of the loss surface that reduce loss fastest (typically corresponding to simpler, lower-complexity functions, per the empirical and theoretical "spectral bias"/implicit-bias literature), and only later starts fitting high-frequency, sample-specific noise. Stopping before that later phase caps model complexity without ever writing down an explicit penalty term.

Honest tradeoffs.

• Early stopping is a regularizer whose strength is controlled indirectly (through $t^*$,

itself determined by noisy validation measurements), unlike weight decay's directly-set $\alpha$.

• It requires holding out validation data, reducing the effective training set size — a cost

explicit regularizers do not impose.

• The validation loss is a noisy estimator of true generalization; small validation sets or high

variance in mini-batch training can produce spurious local minima in the validation curve, causing premature or delayed stopping (addressed empirically by the patience parameter, but not eliminated by it).

• It composes with, rather than replaces, other regularizers (dropout, weight decay, data

augmentation); in practice they are typically combined.

Suppose we train a small neural network for up to $T = 12$ epochs, evaluating validation loss every epoch, with patience $p = 3$ and tolerance $\delta = 0.002$.

Training halts after epoch 9 because `stale` reaches the patience limit $p=3$ (non-improving epochs 7, 8, 9). The returned model is the checkpoint from epoch 6, with validation loss $0.49$, even though training continued for three more epochs and training loss kept dropping to $0.05$. Note epoch 5 is a case where naive stopping with $p=0$ (no patience at all) would have halted right after the very first uptick at epoch 5, returning the epoch-4 checkpoint (val loss $0.505$) and missing the better epoch-6 checkpoint (val loss $0.49$) entirely — this is exactly why patience exists: the epoch-5 blip was noise, not the true onset of overfitting. This also illustrates the tolerance $\delta$: at epoch 4, validation loss $0.505$ is compared against $v^* - \delta = 0.52 - 0.002 = 0.518$; since $0.505 < 0.518$, this counts as a genuine improvement and resets `stale`, rather than being dismissed as noise.

Early stopping's regularization interpretation was formalized as neural networks and statistical learning theory matured together in the late 1980s and 1990s, growing out of much older ideas in numerical optimization and statistics about iterative methods as implicit regularizers (related to the Landweber iteration in inverse problems). The person most associated with sharpening the modern deep-learning framing of "training set/validation set/regularization" as an integrated picture is Yoshua Bengio, whose group's writing and teaching helped standardize early stopping as a default component of the deep learning training pipeline.

Early stopping is a default feature in production machine learning frameworks (PyTorch Lightning callbacks, Keras `EarlyStopping`, XGBoost/LightGBM's `early_stopping_rounds`), because it lets practitioners set a generous compute budget and trust the framework to halt at the right point rather than hand-tuning epoch counts per dataset. In large-scale industrial training — recommender systems, ad click-through prediction, speech recognition — validation-based stopping saves substantial compute cost by avoiding unnecessary extra epochs once a model has plateaued, which matters enormously when a single training run can cost thousands of GPU-hours. It is also central to AutoML and neural architecture search pipelines, where early stopping (and its cousin, learning-curve-based early termination of unpromising configurations) prunes the search space efficiently. Because the number of training epochs is itself a tunable knob, early stopping is a natural bridge into the broader discipline of Hyperparameter Tuning, where it is often used inside larger search loops (e.g., early-stopping bad trials in Bayesian optimization or successive halving/Hyperband) to save compute across many candidate configurations, not just within one.

Ask the tutor: How should I choose the patience value and evaluation frequency for a specific dataset and training budget?