Early stopping

Intuition

Train a model with enough capacity for long enough and its training loss keeps falling, right past the point where it has stopped learning anything general. Held-out loss does not follow it down. It falls, flattens, and turns back up.

Early stopping is the decision to quit at the turn. That is all it is, and it is probably the most commonly used form of regularization in deep learning

— not because it is clever, but because the information needed to apply it arrives for free during training.

Formal definition

Rather than constraining the weights, constrain how many epochs are spent adjusting them: it is "a classic technique for regularizing deep neural networks" where "rather than directly constraining the values of the weights, one constrains the number of epochs of training" [1, §5.5.3].

The usual implementation monitors validation error each epoch "and to cut off training when the validation error has not decreased by more than some small amount ε for some number of epochs. This is sometimes called a patience criterion" [1, §5.5.3].

Two parts, and they are separable: when to halt, and which weights to keep. The second is the one that gets dropped, and the worked example prices it.

How it works

Why the held-out curve turns at all, under label noise, is known: networks "tend to fit cleanly labeled data first and only subsequently to interpolate the mislabeled data" [1, §5.5.3]. Stopping at the turn keeps the part that generalised and skips the part that memorised.

The reason it is everywhere, though, is arithmetic rather than theory. Treated as a hyperparameter, the number of training steps is unlike every other one: a single run of training passes through every candidate value on its way to the end [2, §7.8], so tuning it costs one run rather than one run per value.

Where it's used

Wherever training is iterative and a held-out split exists — which is nearly everywhere in deep learning, and in boosting too, where the number of rounds plays exactly the same role as the number of epochs: scikit-learn's gradient boosting can set aside a validation fraction and stop "when validation score is not improving" [4, n_iter_no_change].

It doubles as a budget control. "Another benefit of early stopping is the time saved" [1, §5.5.3], which on large models is measured in days of hardware.

Why & when

Use it by default. The worked example below shows the cost of not using it is an order of magnitude larger than the cost of configuring it badly, so there is little to deliberate about.

Configure it with a patience of roughly ten epochs, keep a copy of the best weights, and be aware of what it spends: it consumes a validation split, and the split that chose your stopping point cannot also be the split you report.

Worked example

All in scripts/earlystopping.py. A small network, 400 training examples with a fifth of the labels flipped, 300 epochs, 24 runs. Each run's curves are recorded once and every rule is then applied to the same recorded curves, so two rules that disagree disagree because of the rule.

  24 runs, 300 epochs, 20% of training labels flipped
   epoch     train   validation      test
       1    0.6446       0.6500    0.6467
      10    0.5012       0.5076    0.5010
      25    0.3684       0.5083    0.5023
      50    0.1246       0.5739    0.5690
     100    0.0247       0.6995    0.6866
     200    0.0072       0.8055    0.7883
     300    0.0040       0.8584    0.8397

    validation bottoms out at epoch 17 and rises by
    0.3560 by the end. Training loss never stops falling:
    0.6446 to 0.0040. Only the held-out curve turns.

Which rule, and what it costs

The rule people describe is "stop when validation error goes up". The rule worth using has patience.

def apply_rule(curve, patience, min_delta=0.0):
    """Return (stop_epoch, best_epoch) for a patience rule run on one curve."""
    best, best_e, waited = np.inf, 0, 0
    for e, v in enumerate(curve):
        if v < best - min_delta:
            best, best_e, waited = v, e, 0
        else:
            waited += 1
            if waited > patience:
                return e, best_e
    return len(curve) - 1, best_e

  every rule applied to the same recorded curves
                      rule   epochs used   test loss   vs oracle
    no stopping, keep last           300      0.8397     +0.3498
    stop on any rise (p=0)            11      0.5006     +0.0107
                patience 5            21      0.4945     +0.0047
               patience 10            29      0.4934     +0.0036
               patience 25            44      0.4934     +0.0036
               patience 50            69      0.4934     +0.0036
     oracle (unattainable)            17      0.4899     +0.0000

    The size of the first gap is the point: not stopping costs more than
    every choice about how to stop, by an order of magnitude. Patience
    then buys a further threefold narrowing, because validation loss
    jitters between epochs, and a rule with no patience fires on jitter.
    Past patience 10 nothing changes except the electricity bill.

Halting is not the same as restoring

A patience rule stops some epochs after the best one, by construction — that is what the waiting is. So the weights in memory when it fires are not the weights you want.

  halting early and restoring the best weights are two different things
  patience   restore best   keep last   cost of not restoring
         5         0.4945      0.5020                 +0.0075
        10         0.4934      0.5095                 +0.0161
        25         0.4934      0.5445                 +0.0511
        50         0.4934      0.6195                 +0.1260

    Stopping hands you whichever epoch ran out of patience, which is by
    construction worse than the best epoch it already saw. The more
    patience you allow, the more that costs: at patience 50, halting
    alone still leaves 0.1296 of the gap to the oracle, and keeping
    a copy of the best parameters removes 0.1260 of it.

The hyperparameter you get for free

  what it costs to tune the number of epochs, against anything else
                                     candidates tried   training runs
         number of epochs, one run                300               1
          any other hyperparameter                300             300

    Tuning the stopping point to the same resolution as a learning rate
    costs 300 runs for the learning rate and 1 for the stopping point,
    because a run passes through every candidate on its way to the end.
    The overhead is one forward pass over 150 held-out rows per epoch,
    against a backward pass over 400 training rows.

    And it is accurate: the epoch validation picks is +0.0036 worse than
    the epoch the test set would have picked. Choosing among 300 epochs
    is not choosing among 300 independent models -- neighbouring epochs
    are nearly the same model, so there is little to overfit to.
    The validation set is still spent, though. It chose the model, so it
    cannot also be the number you report.

Pitfalls

Stopping on the first rise. Held-out loss jitters between epochs, and a rule with no patience fires on the jitter — above, it halts at epoch 11 when the minimum is at 17. Patience is not a refinement; it is the rule.

Halting without restoring. The measured cost grows with patience, because patience is exactly the distance between where you stop and where you should have. At patience 50 it throws away almost everything the stopping bought.

Reporting the validation number. The stopping epoch was chosen on that split, which makes early stopping "a very efficient hyperparameter selection algorithm" [2, §7.8] — and a hyperparameter selected on a split spends it. Quote the result on data that had no say in it. See cross-validation for the general form of the problem.

Assuming the curve has one turn. The rule above takes the first minimum that survives the patience window. A curve that descends again later will be missed, which is a reason to plot the curve rather than only read the number the rule returned.

Forgetting it interacts with the learning rate. A schedule that decays the learning rate produces a fresh drop in held-out loss at each decay, so a patience tuned against a constant rate can fire during the plateau just before one. A piecewise-constant schedule is built that way on purpose: it lets optimisation reach a plateau, and "then (and only then)" lowers the rate [3, §12.11.3.2]. See learning rate.