Gradient boosting

Forests fixed trees by averaging independent mistakes. Boosting fixes them by making the mistakes sequential: each new tree is trained on what the ensemble so far got wrong. That sounds like a heuristic; the deep result of this lesson is that it is gradient descent — the same algorithm from the Optimization module, running not over a parameter vector but over the space of functions. Once you see that, every knob (learning rate, number of rounds, tree depth) maps onto optimization concepts you already own, and XGBoost’s famous objective becomes a Newton step with regularization rather than folklore.

Forward stagewise additive modeling

Build the model as a sum of $M$ small functions (here, shallow trees):

grown greedily: at round $m$, freeze everything built so far and add the one tree that most improves the loss,

For squared error the inner problem is transparent: $\ell = \tfrac12(y_i - F_{m-1}(x_i) - h(x_i))^2$ is minimized by fitting $h$ to the residuals $r_i = y_i - F_{m-1}(x_i)$. Boosting for regression is literally: fit a tree to what’s left over, add it, repeat.

The gradient-descent view

Friedman’s reframing: treat the vector of training predictions $F = (F(x_1), \ldots, F(x_n))$ as the “parameters.” Gradient descent on the total loss would update $F \leftarrow F - \nu\, g$ where $g_i = \partial \ell(y_i, F_i) / \partial F_i$. We cannot move each $F(x_i)$ independently — the update must be a function that generalizes to new $x$ — so we do the next best thing: fit a tree to the negative gradient and take a step along it. For squared error, $-g_i = y_i - F(x_i)$: the residuals are the negative gradient, and residual-fitting is revealed as steepest descent in function space. The recipe then generalizes to any differentiable loss by swapping the “pseudo-residuals”:

The optimization module’s vocabulary now prices every hyperparameter: $\nu$ is the learning rate; $M$ is the iteration count; and since each round reduces training loss essentially monotonically, boosting will overfit as $M \to \infty$ — unlike a forest, where more trees only average. Early stopping on validation loss is the regularizer, and the empirical law of the trade is that a smaller $\nu$ needs proportionally more rounds but buys a lower, flatter test-error valley (shrinkage = taking many cautious steps through function space instead of few greedy ones).

What XGBoost actually optimizes

Modern implementations sharpen the gradient view in three moves. Take a second-order Taylor expansion of the loss around the current prediction (with $g_i = \partial_F \ell$, $h_i = \partial^2_F \ell$), and add explicit tree regularization — $\gamma$ per leaf, $\tfrac\lambda2$ on leaf weights:

For a fixed tree structure with leaf sets $I_j$, this is a separate quadratic per leaf, solved in closed form:

Read the pieces: the leaf weight is a Newton step (gradient over curvature — the adaptive-methods lesson’s preconditioning instinct, per leaf), $\lambda$ shrinks it exactly as ridge shrinks coefficients, and $\gamma$ sets a hard bar a split’s gain must clear to justify existing — pre-pruning by objective, not heuristic. Splits are then chosen to maximize the gain in $\text{Obj}^\ast$, which is CART’s greedy search with a principled, loss-aware criterion. Everything else in the tool’s reputation — histogram-binned split finding, sparsity-aware defaults, column/row subsampling (bagging’s decorrelation trick, borrowed back) — is systems engineering on top of this objective. LightGBM and CatBoost differ in growth order (leaf-wise), binning, and categorical handling, not in the math above.

Using it like an adult

Boosting’s knobs interact, but the structure is now legible: capacity per round (depth 3–8; interactions need depth), step size ($\nu$ 0.02–0.1), steps ($M$: large, with early stopping doing the choosing), and stochastic decorrelation (subsample ~0.8). The honest comparison table for tabular work:

Boosted trees remain the first serious model to try on structured/tabular data in 2026 — deep learning claims the crown only where representation must be learned (images, text, audio). Both tree ensembles share the extrapolation blindness from last lesson; and boosting’s log-loss scores need the calibration check from lesson 3 before anyone treats them as probabilities.

import xgboost as xgb

model = xgb.XGBClassifier(
    n_estimators=2000, learning_rate=0.05, max_depth=5,
    subsample=0.8, colsample_bytree=0.8, reg_lambda=1.0,
    early_stopping_rounds=50, eval_metric="logloss",
)
model.fit(X_tr, y_tr, eval_set=[(X_va, y_va)], verbose=False)
print(model.best_iteration)        # M chosen by the validation curve, not by faith

Exercises