Early Stopping And The Bias-Variance Tradeoff

Why the Number of Boosting Rounds Matters

Boosting builds a predictor in stages. At round $m$, the current predictor is $f_m$; each new update can reduce the training loss, but continued fitting can also make the predictor more sensitive to the training sample. The round number is therefore not merely a computational setting. It controls how far the algorithm travels along a sequence of increasingly fitted models.

Early stopping uses a validation set to choose a finite point on this sequence. It can regularize the final predictor even when the fitting procedure has no explicit penalty parameter: stopping sooner limits the updates the model can accumulate. This is a property of the fitted path, not a guarantee that every validation curve has a smooth U-shape or that stopping will always improve test performance.

Definition: Let $f_m$ be the predictor after $m$ boosting rounds, with $f_0$ the initial predictor. For a loss function $\ell$, the training loss is the average loss on the observations used to fit the sequence. The validation loss is the average loss on a separate validation sample. Given a prespecified set of candidate rounds $\mathcal M$, early stopping chooses a round minimizing validation loss: $$ \hat m \in \operatorname*{arg\,min}_{m\in\mathcal M}\widehat R_{\mathrm{val}}(f_m). $$ If there is a tie, a tie-breaking rule, such as choosing the smallest minimizing round, must be specified.

Training loss and validation loss answer different questions. Training loss describes fit to the data used to construct the path. Validation loss estimates performance on new observations, but it is noisy because the validation sample is finite. The chosen round depends on both the underlying prediction path and that validation noise.

Early Stopping and the Bias-Variance Tradeoff

For squared-error prediction, the bias-variance decomposition makes the tradeoff precise at a fixed predictor input $x$. Suppose a new response satisfies $Y=f^*(x)+\varepsilon$, where $E[\varepsilon\mid x]=0$, $\operatorname{Var}(\varepsilon\mid x)=\sigma^2(x)<\infty$, and the test noise is independent of the training data $D$. The fitted value $\hat f_D(x)$ varies with $D$.

Theorem (pointwise bias-variance decomposition): Under the preceding conditions, if $E_D[\hat f_D(x)^2]<\infty$, then $$ E_{D,\varepsilon}\!\left[(Y-\hat f_D(x))^2\mid x\right] = \left(E_D[\hat f_D(x)]-f^*(x)\right)^2 +\operatorname{Var}_D(\hat f_D(x)) +\sigma^2(x). $$

Proof. Write $Y-\hat f_D(x)=\varepsilon-(\hat f_D(x)-f^*(x))$. Squaring and taking conditional expectations gives $$ E[\varepsilon^2\mid x]+E_D[(\hat f_D(x)-f^*(x))^2] -2E[\varepsilon(\hat f_D(x)-f^*(x))\mid x]. $$ Independence of test noise and $D$, together with $E[\varepsilon\mid x]=0$, makes the cross term zero. Also $E[\varepsilon^2\mid x]=\sigma^2(x)$. For $Z=\hat f_D(x)$, expand around $E_D[Z]$: $$ E_D[(Z-f^*(x))^2] =\operatorname{Var}_D(Z)+(E_D[Z]-f^*(x))^2. $$ Combining these equalities proves the result. $\square$

Along a boosting path, adding rounds often decreases approximation bias: the mean fitted value can move closer to the target. But the fitted value may become more variable across training samples as additional structure is learned. Early stopping balances these two components; it does not directly minimize either one in isolation. The balance depends on the data, loss, weak learners, and update size.

A Quadratic View of the Regularization Effect

A transparent derivation is available for gradient descent on a squared-error objective. This is an exact model for linear gradient descent and a useful analogy for stagewise fitting. Let $X$ be a fixed design matrix and $y$ the response vector, and define $$ Q(\beta)=\frac{1}{2n}\|y-X\beta\|^2,\qquad A=\frac{X^\mathsf{T}X}{n},\qquad c=\frac{X^\mathsf{T}y}{n}. $$ Starting from $\beta_0=0$, full-gradient updates with step size $\eta$ are $\beta_{m+1}=\beta_m+\eta(c-A\beta_m)$. Assume $A$ is positive semidefinite and $0<\eta\le 1/\lambda_{\max}(A)$ when $A$ has positive eigenvalues.

Theorem (spectral shrinkage along the quadratic gradient path): Let $u_j$ be an orthonormal eigenvector of $A$ with eigenvalue $\lambda_j>0$, and write $c_j=u_j^\mathsf{T}c$. Then the coefficient of $\beta_m$ along $u_j$ is $$ u_j^\mathsf{T}\beta_m = \frac{1-(1-\eta\lambda_j)^m}{\lambda_j}\,c_j. $$

Derivation. Project the update onto $u_j$. If $b_{m,j}=u_j^\mathsf{T}\beta_m$, then $u_j^\mathsf{T}A\beta_m=\lambda_j b_{m,j}$ and $u_j^\mathsf{T}c=c_j$. Thus $$ b_{m+1,j}=(1-\eta\lambda_j)b_{m,j}+\eta c_j,\qquad b_{0,j}=0. $$ The proposed expression holds at $m=0$. If it holds at $m$, substitution gives $$ b_{m+1,j} =(1-\eta\lambda_j)\frac{1-(1-\eta\lambda_j)^m}{\lambda_j}c_j+\eta c_j =\frac{1-(1-\eta\lambda_j)^{m+1}}{\lambda_j}c_j. $$ Induction proves the formula. Under the stated step-size condition, $0\le 1-\eta\lambda_j<1$, so the multiplier $1-(1-\eta\lambda_j)^m$ increases from zero toward one. For a small eigenvalue $\lambda_j$, it grows more slowly. Early stopping therefore shrinks directions with small eigenvalues more strongly than directions with large eigenvalues. This is an implicit, direction-dependent regularization effect. $\square$

Boosting with trees or other weak learners is not generally this exact linear iteration: its updates can be data-adaptive and its path need not have a spectral representation. The derivation establishes the mechanism in a quadratic setting, not a universal formula for every boosting algorithm. In practice, the validation curve is used to assess the actual path.

Worked Example: Comparing Two Learner Paths

Consider a one-dimensional illustration in which $g_m$ is the amount of a target signal fitted by round $m$, with $g_0=0$ and $$ g_m=1-(1-\rho)^m,\qquad \rho=\eta q. $$ Here $q$ controls the rate of progress for this illustration. Suppose the expected prediction risk is $R(g)=4(1-g)^2+qg^2$: the first term represents squared bias and the second is a variance contribution. This is a deliberately specified toy risk model, not a general boosting risk formula. Use the same nominal learning rate $\eta=0.5$ for learners with $q=0.5$ and $q=0.25$.

For $q=0.5$, $\rho=0.25$. At four rounds, $$ g_4=1-0.75^4=1-0.31640625=0.68359375, $$ so $$ R(g_4)=4(0.31640625)^2+0.5(0.68359375)^2 =0.6341018677\ \text{(approximately)}. $$ At eight rounds, $0.75^8=0.1001129150390625$, so $g_8=0.8998870849609375$, and $$ R(g_8)=4(0.1001129150390625)^2 +0.5(0.8998870849609375)^2 \approx 0.4449888. $$

For $q=0.25$, $\rho=0.125$. At four rounds, $$ g_4=1-0.875^4=0.413818359375, $$ and direct substitution gives $$ R(g_4)=4(0.586181640625)^2+0.25(0.413818359375)^2 \approx 1.4172471. $$ At sixteen rounds, $0.875^{16}\approx0.1180671$, hence $g_{16}\approx0.8819329$, and $$ R(g_{16})=4(0.1180671)^2+0.25(0.8819329)^2 \approx 0.2502108. $$

The weaker-progress path is much less fitted at four rounds, but catches up with more rounds and has a smaller variance contribution in this specified model. The risk-minimizing signal level satisfies $-8(1-g)+2qg=0$, giving $g=4/(4+q)$; stopping is useful because the path can pass that balance point. The example shows why equal round counts need not be comparable across learners.

Learning Rate Changes the Stopping Scale

Shrinkage, introduced in the earlier material on step-size regularization, makes each update smaller. Consequently, a smaller learning rate usually requires more rounds to travel a comparable distance along a similar path. The useful stopping round is therefore not an intrinsic property of the data alone: it depends on the step size and on how the weak learner responds to the current residuals.

Worked Example: A Smaller Step Requires More Rounds

Suppose the same scalar path follows $g_m=1-(1-\eta)^m$, with target value one. Let its prediction risk be $R(g)=(1-g)^2+0.2g^2$. Differentiating gives $R'(g)=-2(1-g)+0.4g$, so the risk is minimized at $g=1/1.2=5/6$.

With $\eta=0.4$, after four rounds $g_4=1-0.6^4=0.8704$. Its risk is $$ R(g_4)=(0.1296)^2+0.2(0.8704)^2 =0.01679616+0.151519232 =0.168315392. $$ This value is close to the optimum signal level $5/6$. With $\eta=0.1$, after four rounds $g_4=1-0.9^4=0.3439$, giving $$ R(g_4)=(0.6561)^2+0.2(0.3439)^2 =0.43046721+0.023653442 =0.454120652. $$

For the smaller step, round 17 gives $g_{17}=1-0.9^{17}\approx0.8332282$, close to $5/6$. Thus round 4 for the larger step and round 17 for the smaller step reach similar fitted levels. These numbers illustrate the shift in stopping scale; they do not imply that multiplying the number of rounds by a fixed factor always compensates for a learning-rate change in a nonlinear boosting model.

Using Validation Curves Carefully

A practical procedure fixes the candidate range of rounds, records training and validation loss at those rounds, and selects a minimizing validation round. The training curve helps diagnose optimization: a steadily falling training loss alongside rising validation loss is consistent with overfitting along the path. A flat validation curve suggests that several rounds may perform similarly; choosing the earliest round within a prespecified tolerance can reduce computation and sensitivity to small validation fluctuations.

Validation selection itself introduces noise. Even if the validation loss at each fixed round is unbiased for that round's prediction risk, the minimum over many noisy estimates tends to be optimistic. This is one reason a final performance estimate should not be reported on the same validation data used to choose the round.

Worked Example: Why the Minimum Validation Loss Is Optimistic

Suppose there are two candidate rounds, each with true risk 1. Let their validation-loss estimates be $\widehat R_1=1+Z$ and $\widehat R_2=1-Z$, where $Z$ equals $0.2$ or $-0.2$, each with probability $1/2$. Then $E[\widehat R_1]=E[\widehat R_2]=1$, so each estimate is unbiased for its candidate's risk.

But when we select the smaller observed loss, $$ \min(\widehat R_1,\widehat R_2)=1-|Z|=0.8 $$ in either case. Therefore $E[\min(\widehat R_1,\widehat R_2)]=0.8$, which is below the true risk 1 of both candidates. More generally, for any fixed candidate $k$, $\min_m\widehat R_m\le\widehat R_k$; taking expectations shows $E[\min_m\widehat R_m]\le R_k$. This holds for every $k$, so the expected selected minimum is no greater than the smallest candidate risk. The selected validation value is not, by itself, an unbiased estimate of the selected model's risk.

Common Mistake

A common mistake is to treat the round with the smallest observed validation loss as the round with definitively best test performance. The validation minimum is a selection based on noisy data, and its apparent advantage can partly reflect chance. Another mistake is to compare round counts across learning rates as if “round 20” represented the same amount of fitting in both models. Smaller updates generally move more slowly, and different weak learners can change both progress and variability.

Use validation loss to make a disciplined choice, not to claim certainty. Keep the validation set separate from model fitting, specify the candidate rounds and tie rule, and use independent test data or an appropriate resampling procedure when an external performance estimate is needed. Early stopping is regularization through restriction of the fitted path; how much regularization a particular round provides depends on the path itself.

Key takeaway: Training loss tracks fit to the training data; validation loss guides the stopping choice. More rounds can reduce bias while increasing variance, and both weak-learner behavior and learning rate alter where that balance occurs.

Check Your Understanding

Use the definitions and derivations above to answer the following.

Why can training loss decrease while validation loss increases?
State the three terms in the pointwise bias-variance decomposition and identify which one is irreducible test noise.
In the quadratic gradient path, why are small-eigenvalue directions more strongly shrunk at a fixed finite round?
Why should a smaller learning rate generally be paired with a search over later stopping rounds?
Explain why the minimum observed validation loss can be optimistic even when each candidate validation estimate is unbiased.