Early Stopping and Learning Curves

In Lesson 3 you saw the validation error of a booster make a U: too few trees and it underfits, too many and it overfits. That U is the single most useful picture in boosting, and this lesson is about reading it.

Sam runs a chain of bike-rental kiosks and wants to predict each day's rentals from the daily high temperature. A booster keeps stacking small trees, fitting the training days a little better with every round, forever. So the real question is not "is more trees better." It is when do you stop? Set the number of trees too high by hand and you overfit; too low and you leave demand unlearned.

By the end of this lesson you will be able to:

• Read a learning curve and say what the training curve and the validation curve each tell you
• Diagnose overfitting, underfitting, or a healthy fit from the curve's shape, and pick the fix
• State the early-stopping rule (the validation minimum, plus a patience window) and why patience beats stopping at the first uptick
• Use early stopping in R to set the number of trees for free, with no grid search

Prerequisites: Lesson 1 (Gradient Boosting from Scratch: residuals, the learning rate, shallow trees in sequence) and Lesson 3 (The Hyperparameters That Matter: the four knobs and the validation U). You can run R and you know what a training/validation split is and what RMSE measures.

The learning curve, read properly

A learning curve plots two numbers against the boosting round: the error on the training days (the days the model fits) and the error on a held-out validation set (days it never trains on). We measure error with RMSE, the root-mean-square of the prediction misses, in the same units as rentals.

Here is the asymmetry that makes the curve so useful. Every new tree is fit to correct what the current model still gets wrong on the training days, so the training curve falls a little more every single round and never turns back up. The validation curve has no such guarantee: it falls while the trees are still learning real, repeatable demand, bottoms out, then climbs once later trees start fitting the random noise in the training days. The lowest point of the validation curve is the model you want.

Write the booster as the additive model from Lesson 3,

\[ F_M(x) = F_0(x) + \nu \sum_{m=1}^{M} h_m(x), \]

where \(F_0(x)\) is the starting guess (the mean rentals), \(h_m\) is the \(m\)-th tree, \(\nu\) is the learning rate, and \(M\) is the number of trees. Reading the curve picks \(M\): the best number of trees is the round where validation error is smallest,

\[ M^\star = \arg\min_{m}\; \mathcal{L}_{\text{val}}(m), \]

where \(\mathcal{L}_{\text{val}}(m)\) is the validation RMSE after \(m\) rounds and \(\arg\min\) means "the round \(m\) that makes it smallest."

Drag the slider below to choose where to stop. Watch the orange training curve slide down without end while the validation curve makes its U, and read the verdict: stopped too early, stopped too late, or right at the sweet spot. That slider, done automatically, is early stopping.