Stagewise Additive Updates

Why Boosting Updates One Tree at a Time

In an additive tree model, predictions are built by adding tree contributions. Stagewise fitting gives this construction a precise rule: at each stage, choose a tree update that makes the current model perform better according to a specified loss. The model is not rebuilt from scratch at every step; earlier contributions remain in place.

This matters in practice because the tree chosen at one stage depends on the predictions already made by the model. A stagewise sequence is therefore a path through a restricted set of models. Its successive training-loss reductions are useful to track, but they do not by themselves establish how well the model will predict new observations.

Definition: Let the training observations be $(x_i,y_i)$, for $i=1,\ldots,n$, and let $L(y,F(x))$ be a specified loss for outcome $y$ and prediction $F(x)$. A stagewise additive tree model starts with an initial predictor $F_0$. At stage $m$, it chooses a tree function $h_m$ and a scalar update size $\gamma_m$, then sets $$ F_m(x)=F_{m-1}(x)+\gamma_m h_m(x). $$ The update is selected to reduce the empirical loss $$ \mathcal{L}_m=\sum_{i=1}^{n}L\bigl(y_i,F_{m-1}(x_i)+\gamma_m h_m(x_i)\bigr). $$

A tree function assigns a value to each predictor vector $x$, often by dividing the predictor space into terminal regions. For a fixed tree structure, its predictions can vary across those regions. The scalar $\gamma_m$ controls the size and direction of the particular addition. Some implementations absorb that scalar into the tree's terminal values; keeping it separate makes the stagewise choice easier to describe.

The initial predictor is commonly a constant chosen to minimize the same training loss among constant predictions. For squared-error loss, that constant is the training mean of the outcomes; for absolute-error loss, it is a training median. The starting constant and subsequent updates must use a loss appropriate to the modeling task.

The Stagewise Selection Rule

At a given stage, the current predictor $F_{m-1}$ is fixed. The fitting procedure considers tree functions allowed by the model specification and update sizes allowed by the fitting method. It selects the pair that minimizes the resulting training loss. If the search finds no update with lower loss than the current model, adding a zero contribution preserves the current predictor.

(h_m,\gamma_m)\in\arg\min_{h\in\mathcal{H},\,\gamma\in\Gamma} \sum_{i=1}^{n}L\bigl(y_i,F_{m-1}(x_i)+\gamma h(x_i)\bigr).

Here $\mathcal{H}$ denotes the set of candidate tree functions, and $\Gamma$ denotes the allowed update sizes. In a continuous optimization, $\Gamma$ may include all real values; an illustrative hand calculation may instead restrict it to a short list. If the best pair is not unique, a specified tie-breaking rule is needed for a reproducible fit.

Choose the starting predictor.
Specify the loss and initialize $F_0$, often with a constant that minimizes the training loss among constants.

Evaluate possible additions.
For each candidate tree and update size, calculate the loss using the current predictions plus that candidate update.

Keep the best stagewise update.
Select the candidate with the smallest loss under the specified search, then add its contribution to the current predictor.

Repeat from the updated model.
At the next stage, evaluate candidate additions against $F_m$, not against the original starting predictor.

The selection rule has a direct justification. Suppose all current contributions are fixed, and the only permitted change is one new tree contribution. For any candidate $h$ and size $\gamma$, the resulting model has predictions $F_{m-1}(x_i)+\gamma h(x_i)$. Its empirical loss is therefore exactly the sum in the selection rule. Minimizing that sum selects the best model among the permitted one-step additions. This is a local, restricted comparison: it does not prove that the resulting model is globally optimal among all possible ensembles.

Worked Updates Under Different Losses

Worked Example: Choosing Two Squared-Error Updates

A hypothetical pricing analysis has three training outcomes $y=(1,3,5)$. Use squared-error loss $L(y,F)=(y-F)^2$, with no averaging or one-half multiplier. Begin with the constant $F_0=3$. At each stage, consider only the listed trees and $\gamma\in\{-0.5,0,0.5\}$. Find two updates.

Method. For each candidate, add $\gamma h(x_i)$ to the current prediction for every observation, then sum the three squared errors. This directly compares allowed updates; it does not assume that a new tree is fitted independently of the current model.

At the start the predictions are $(3,3,3)$, so the loss is $(1-3)^2+(3-3)^2+(5-3)^2=4+0+4=8$. First consider $h_A=(1,0,-1)$. With $\gamma=-0.5$, predictions become $(2.5,3,3.5)$, and loss is $2.25+0+2.25=4.5$. With $\gamma=0$, loss remains $8$. With $\gamma=0.5$, predictions are $(3.5,3,2.5)$, and loss is $6.25+0+6.25=12.5$.

Now consider $h_B=(0,1,-1)$. With $\gamma=-0.5$, predictions are $(3,2.5,3.5)$, giving loss $4+0.25+2.25=6.5$. With $\gamma=0$, loss is $8$. With $\gamma=0.5$, predictions are $(3,3.5,2.5)$, giving loss $4+0.25+6.25=10.5$. The smallest candidate loss is $4.5$, so choose $h_A$ and $\gamma_1=-0.5$. The updated predictor's training predictions are $(2.5,3,3.5)$.

At stage two, compare candidate $h_B=(0,1,-1)$ and $h_C=(-1,0,1)$ using those updated predictions. For $h_B$, the losses for $\gamma=-0.5,0,0.5$ are, respectively, $3.5$, $4.5$, and $6.5$: the corresponding predictions are $(2.5,2.5,4)$, $(2.5,3,3.5)$, and $(2.5,3.5,3)$. For $h_C$, they are $8$, $4.5$, and $2$: the corresponding predictions are $(3,3,3)$, $(2.5,3,3.5)$, and $(2,3,4)$.

Choose $h_C$ with $\gamma_2=0.5$. The final predictions are $(2,3,4)$, and the checked loss is $(1-2)^2+(3-3)^2+(5-4)^2=1+0+1=2$, lower than the stage-one loss $4.5$. The common mistake avoided here is evaluating stage two from the original predictions $(3,3,3)$, rather than from the stage-one predictions.

Worked Example: An Absolute-Error Update

A hypothetical portfolio contains three training records with outcomes $y=(10,14,18)$. Use absolute-error loss $L(y,F)=|y-F|$. The starting constant is $F_0=14$. Consider the trees $h_A=(1,0,-1)$ and $h_B=(0,1,-1)$, with candidate update sizes $\gamma\in\{-2,0,2\}$. Select the first update, then consider a second candidate $h_C=(0,0,1)$ with the same update sizes.

The initial loss is $|10-14|+|14-14|+|18-14|=4+0+4=8$. For $h_A$, $\gamma=-2$ gives predictions $(12,14,16)$ and loss $2+0+2=4$; $\gamma=0$ gives loss $8$; and $\gamma=2$ gives predictions $(16,14,12)$ and loss $6+0+6=12$. For $h_B$, $\gamma=-2$ gives predictions $(14,12,16)$ and loss $4+2+2=8$; $\gamma=0$ gives loss $8$; and $\gamma=2$ gives predictions $(14,16,12)$ and loss $4+2+6=12$. The first update is $h_A$ with $\gamma_1=-2$.

The current predictions are now $(12,14,16)$. For $h_C$, $\gamma=-2$ gives $(12,14,14)$ and loss $2+0+4=6$; $\gamma=0$ leaves the loss at $4$; and $\gamma=2$ gives $(12,14,18)$ and loss $2+0+0=2$. The second update is therefore $h_C$ with $\gamma_2=2$. The final loss checks as $2$. Absolute error is not squared error: applying a squared-error calculation here would select according to a different objective.

Worked Example: Comparing Binary Log-Loss Updates

A hypothetical two-record classification sample has labels $y=(1,0)$. The model outputs a score $F$, converted to an estimated probability $p=1/(1+e^{-F})$. Use binary log loss $L(y,F)=-y\ln(p)-(1-y)\ln(1-p)$. Start with scores $(0,0)$, and consider trees $h_A=(1,-1)$ and $h_B=(1,1)$, with update sizes $0$ or $0.5$. Then, for a second stage, compare $h_C=(1,-1)$ and $h_B$ using update sizes $0,0.25,0.5$.

At score zero, each estimated probability is $0.5$, so the initial total loss is $-\ln(0.5)-\ln(0.5)=1.3863$. For $h_A$ with $\gamma=0.5$, scores become $(0.5,-0.5)$. The probabilities are approximately $(0.6225,0.3775)$, so the two contributions are $-\ln(0.6225)=0.4741$ and $-\ln(1-0.3775)=0.4741$. Total loss is $0.9482$. For $h_B$ with $\gamma=0.5$, scores are $(0.5,0.5)$; the losses are $0.4741$ and $-\ln(0.3775)=0.9741$, totaling $1.4482$. The zero update leaves the loss at $1.3863$, so the first update is $h_A$ with $\gamma_1=0.5$.

For stage two, $h_C$ with $\gamma=0.25$ gives scores $(0.75,-0.75)$. The probabilities are approximately $(0.6792,0.3208)$, so each observation contributes approximately $0.3869$, for total loss $0.7737$. With $\gamma=0.5$, the scores are $(1,-1)$, with probabilities $(0.7311,0.2689)$; each contribution is approximately $0.3133$, for total loss $0.6265$. With $\gamma=0$, loss remains $0.9482$.

For comparison, $h_B$ with $\gamma=0.25$ gives scores $(0.75,-0.25)$, probabilities approximately $(0.6792,0.4378)$, and total loss $0.3869+0.5759=0.9628$. With $\gamma=0.5$, scores are $(1,0)$, giving loss $0.3133+0.6931=1.0064$. Therefore the second update is $h_C$ with $\gamma_2=0.5$. The final scores $(1,-1)$ have total loss $0.6265$, confirming the chosen update lowers the current loss. The common trap is judging a score update by how its numbers look: the relevant comparison is the log loss after converting scores to probabilities.

What Stagewise Fitting Does—and Does Not—Guarantee

At each stage, the selected update is best only among the candidates actually considered. A restricted tree depth, a restricted set of update sizes, or an imperfect search can change which update is selected. Moreover, the sequence is generally path dependent: a different earlier tree changes the current predictions and can change the best later tree. Stagewise selection does not revisit all earlier choices and jointly optimize every tree unless an additional fitting procedure explicitly does so.

A training-loss decrease is also not a guarantee of improved prediction on new data. The update rule compares the training observations used in its objective. Assessing performance on held-out data is a separate model-validation task. In particular, do not confuse selecting the lowest training-loss candidate at one stage with deciding how many stages should be retained.

Key takeaway: A stagewise additive update is chosen by evaluating the specified loss after adding a candidate tree contribution to the current model. Keep the current predictions, objective, candidate set, and update size aligned at every stage; the best local update is not automatically a globally best or best-generalizing model.

Check Your Understanding

For each problem, use the stated loss and candidate set; report the requested update or loss.

Current predictions are $(4,6)$, outcomes are $(5,5)$, and squared-error loss is the sum of squared errors. A candidate tree has outputs $h=(1,-1)$, with $\gamma\in\{-1,0,1\}$. Which update minimizes loss, and what is the resulting loss? (Answer: $\gamma=1$; loss $0$.)
Outcomes are $(2,7,9)$, the current constant prediction is $7$, and the loss is total absolute error. A candidate tree has outputs $(1,0,-1)$, with $\gamma\in\{-1,0,2\}$. Which update has the lowest loss, and what is that loss? (Answer: $\gamma=-1$; loss $5$.)
A binary sample has labels $(1,0)$ and current scores $(0.4,-0.4)$. Add $\gamma h$, where $h=(1,-1)$ and $\gamma=0.2$. Using $p=1/(1+e^{-F})$, calculate the resulting total binary log loss to four decimal places. (Answer: $0.8750$.)
At a stage, the current training loss is $12$. Candidate A gives losses $9$, $11$, and $12$ for its three allowed update sizes; candidate B gives $8$, $10$, and $13$. Which candidate update is selected under stagewise fitting, and what can be concluded about performance on new observations? (Answer: Select candidate B at the update size giving loss $8$; no conclusion about new-observation performance follows from this training-loss comparison alone.)

What You'll Learn