Gradient boosting

The idea

Boosting builds a strong model as a running sum of weak ones, each new term fitted to what the sum so far still gets wrong:

$F_m(x) = F_{m-1}(x) + \nu \, h_m(x)$

The magic is what $h_m$ is trained on. Gradient boosting treats the $n$ current predictions $F_{m-1}(x_i)$ as free parameters and asks: in which direction should each prediction move to decrease the loss fastest? That direction is the negative gradient — the pseudo-residuals:

$r_i^{(m)} = -\left.\frac{\partial L\big(y_i, F(x_i)\big)}{\partial F(x_i)}\right|_{F = F_{m-1}}$

A small tree $h_m$ is then fit to the pairs $(x_i, r_i^{(m)})$ — a projection of the ideal descent direction onto the tree function class — and added with step size $\nu$. This is gradient descent in function space. For squared error the gradient is literally the residual $y_i - F_{m-1}(x_i)$; for log loss it is $y_i - p_i$; for MAE it is $\text{sign}(y_i - F_{m-1}(x_i))$. Swap the loss, keep the machinery — that generality is why the same library does regression, classification, and ranking.

Why this reduces bias (and bagging cannot). Bagging averages parallel copies of the same low-bias model: noise cancels, but shared systematic error survives averaging perfectly intact. Boosting starts from a high-bias model and sequentially extends it — every round adds capacity aimed at the current error. With a learner that approximates a descent direction and a suitable step size, training loss generally falls and bias can shrink; neither is guaranteed for an arbitrary fitted tree or step. The mirror image: because later trees chase whatever error remains, enough rounds will start fitting noise — variance rises, test loss traces a U against rounds, and early stopping is not optional hygiene but part of the algorithm.

Hence the trademark settings, all of them variance guards on a bias-killing machine: shallow trees (depth 3-8; depth also caps interaction order), shrinkage $\nu \in [0.01, 0.1]$ (many small steps correct each other; halve $\nu$, roughly double the rounds), row/column subsampling (stochastic gradient boosting — implicit bagging inside the loop), and penalized leaf weights in the modern implementations (XGBoost adds $\gamma \cdot \text{leaves} + \tfrac{\lambda}{2}\|w\|^2$ to the objective and uses second-order gradients to fit each tree).

Worked example

Four points, squared-error loss, trees replaced by a single split at $x \le 2$ for legibility:

Round 0. $F_0 = \bar{y} = 16$ for everyone. Residuals: $(-6, -4, +4, +6)$. MSE $= (36+16+16+36)/4 = 26$.

Round 1. Fit a stump to the residuals: left leaf ($x \le 2$) predicts the mean residual $-5$; right leaf predicts $+5$. With $\nu = 0.5$:

$F_1 = 16 + 0.5 \times (\pm 5) = (13.5,\; 13.5,\; 18.5,\; 18.5)$

New residuals: $(-3.5, -1.5, +1.5, +3.5)$. MSE $= 29/4 = 7.25$.

Round 2. Stump on the new residuals: leaf means $-2.5$ and $+2.5$.

$F_2 = (12.25,\; 12.25,\; 19.75,\; 19.75)$

Residuals: $(-2.25, -0.25, +0.25, +2.25)$. MSE $\approx 2.56$.

Two things to notice. The group-level error halves every round — the leaf-mean residual is $\pm 5 \times (1-\nu)^m$ — so the systematic gap between the two groups (pure bias at round 0) decays geometrically: shrinkage slows the descent but never stops it. And what remains inside each leaf ($\pm$ a couple of points) is exactly what further identical splits cannot fix — later rounds would need finer splits, and on real noisy data those finer splits are where overfitting begins.

Cheat sheet

Algorithm: $F_0 = \arg\min_c \sum L(y_i, c)$; repeat: $r_i = -\partial L/\partial F(x_i)$, fit tree $h_m$ to $r$, $F_m = F_{m-1} + \nu h_m$; stop by validation loss.

Pseudo-residuals by loss: squared error → $y - F$; log loss → $y - p$; MAE → $\text{sign}(y - F)$; that swap is the whole generalization.

• Bagging = parallel + deep trees + averaging ⇒ variance down, bias flat. Boosting = sequential + shallow trees + additive corrections ⇒ bias down, variance creeps up with rounds.
• Forest error flattens with more trees; boosting test error is U-shaped in rounds ⇒ early stopping mandatory.
• $\nu$ and rounds trade off almost linearly; tune them as a pair.
• Boosting is sequential ⇒ does not parallelize across trees (libraries parallelize within a tree's split search instead).
• Sensitive to label noise/outliers with squared or exponential loss — use Huber/MAE or subsampling.
• XGBoost vs classic GBM: second-order Taylor fit per tree, regularized objective, sparsity-aware splits; LightGBM: histogram splits + leaf-wise growth (faster, watch overfitting on small data).
• No feature scaling needed (still trees). Probabilities usually need calibration.