Early Stopping

The validation curve

Picture a student preparing for an exam with practice papers. The marks climb while revision helps, then they stop climbing. Later they fall, because the student has started to memorize old answers rather than learn the subject. Early stopping works the same way for a neural network. It keeps the parameters that scored best on a held-out validation set, and it stops training once that score has stopped improving.

The book describes the pattern in Figure 7.3: the training error falls steadily, while the validation error reaches a lowest point and then turns back up. The book says this happens very reliably in large models with enough capacity to overfit. The curves in this page are a synthetic illustration written for it, not measurements from a real network.

The book states the procedure as Algorithm 7.1. Let be the number of steps between evaluations. Let be the patience, the number of times to see worsening validation error before giving up. The algorithm keeps the best validation error and the step where it occurred, . When a new validation error beats the best, it copies the parameters, . When the patience runs out, it returns that copy and not the latest parameters.

Predict first. On this curve, where does the validation error reach its lowest point?

The patience sets how long the algorithm waits. A patience of one stops at the first worsening check, which can be too early when the curve wiggles. The book's main point is that the training time is itself a hyperparameter, and one run of this algorithm tests many values of it.

The book names the cost. It is the validation evaluation during training, which takes time. The book suggests running it on a separate machine, or using a smaller validation set, or checking less often.

Retraining on all the data

Early stopping needs a validation set, so some training data is held back from the first round. The book gives two ways to use every example in a second round. Algorithm 7.2 starts again from fresh parameters and trains on everything for the number of steps that early stopping chose. Algorithm 7.3 keeps the parameters from the first round and continues on everything until the validation objective falls to the value that the training objective had when early stopping halted.

The book notes that Algorithm 7.2 has an awkward choice. It is not clear whether to retrain for the same number of parameter updates or for the same number of passes through the data. The book also warns that Algorithm 7.3 is not guaranteed to finish, because the validation objective may never reach the target. The book writes the target as . This page uses for it, so it does not clash with the step size.

(This count is added here and is not printed in the book.) Let be the number of labeled examples and the batch size. One pass over all the examples takes / updates. If a fraction is held back, the first round trains on examples, so its passes take fewer updates. The ratio is the same whatever the batch size:

Predict first. With 20% of the data held back, how many more updates per pass does the second round take?

The demo uses 1000 labeled examples. Each line of the algorithm is shown with its reason, and the readout gives the update counts for the chosen share and batch size.

Training time as a limit on the path

Why does stopping early act like a penalty? The book's first answer is a picture (Figure 7.4). Early stopping keeps the parameters in a small region around their starting point . Each step moves them a limited distance, so after steps they cannot have traveled far from the start. The book calls the product of the number of steps and the step size a measure of effective capacity. It says that the number of steps behaves as if it were the reciprocal of the weight decay coefficient.

To analyze this, the book uses a quadratic approximation of the cost near its best weights , with the Hessian at that point. A minimum has a positive semidefinite Hessian, so the approximation is

The gradient of this approximation is equation 7.34. It is the Hessian times the distance from the optimum.

Gradient descent with step size moves the parameters against this gradient. Equation 7.35 is the update, and equation 7.36 is the same update after the gradient is substituted.

Start the parameters at zero, so = 0. Subtracting from both sides of equation 7.36 gives equation 7.37: each step multiplies the distance to the optimum by the matrix in brackets.

Write as , with the eigenvectors in the columns of and the curvatures on the diagonal of . Substituting this into equation 7.37 gives equation 7.38. Multiplying both sides by gives equation 7.39.

After steps, each eigen-direction has reached a fraction of its optimum. Equation 7.40 states this in the rotated coordinates.

A direction with a large curvature is reached quickly. A flat direction with a small curvature takes many steps. The condition keeps every step stable, which is why the step size must be small compared with the curvature.

Predict first. Start from zero and follow gradient descent. Which direction reaches its optimum first?

The bars compare two things. The teal bar is how far early stopping has moved the parameters in each direction. The violet bar is how far an L2 penalty would move them, with its coefficient set to . The two agree closely only when the curvature is small compared with that coefficient.

Matching L2 regularization and the summary

The book then compares the end of the path with L2 regularization on the same quadratic. In the rotated coordinates, the L2 solution (equation 7.13 in the book) is given by equations 7.41 and 7.42.

Equations 7.40 and 7.42 agree when the step count, the step size and the coefficient satisfy equation 7.43.

The series expansion of log(1 + x) lets the book conclude that, when every is small, with and , the two are related by equations 7.44 and 7.45. These are the book's assumptions, and the match holds only approximately outside them.

The number of steps therefore plays a role inversely proportional to the L2 coefficient, and the reciprocal of plays the role of the weight decay coefficient. The book also notes that a direction with high curvature is regularized less and learns early.

The book's further point is that early stopping does more than limit the path. It monitors the validation error, so it stops the path at a good point. The final sentence of the section makes the comparison with weight decay: early stopping chooses the amount of regularization automatically, while weight decay needs many experiments with its coefficient.

The figure uses the same axis-aligned Hessian as the book's picture. The dashed path is the trajectory of gradient descent from zero, and the teal point is the L2 solution with the coefficient you set. Try to bring the two points together.

• Early stopping returns the parameters from the step with the lowest validation error, once the patience runs out.
• The training time behaves as a hyperparameter, and a single run of the algorithm tests many values of it.
• A second round on all the data can retrain from fresh parameters for the same number of steps, or continue until the validation objective reaches the stopping target.
• In a quadratic model, gradient descent from zero learns high-curvature directions first, so the number of steps limits the effective capacity.
• For small curvatures, the number of steps is about the reciprocal of the step size times the L2 coefficient, so early stopping approximates L2 regularization.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 7.8 (pages 246–252), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.