Gradient Boosting

If random forests average independent trees to cut variance, boosting does the opposite: build trees sequentially, each one correcting the errors of the ensemble so far. The idea began with AdaBoost (Freund & Schapire, 1997 — reweight misclassified points); Friedman (2001) generalized it into gradient boosting, and its engineered descendants — XGBoost (2016), LightGBM (2017), CatBoost (2018) — have dominated tabular ML competitions and industry ever since.

Boosting as gradient descent on functions

Fit a model in \(M\) additive stages:

where each \(h_m\) is a small tree and \(\nu\) is the learning rate. The key insight: choose each \(h_m\) to point in the direction that most decreases the loss — exactly like gradient descent, but the "parameters" are the model's predictions themselves. Each stage fits the new tree to the pseudo-residuals:

For squared error, \(r_i = y_i - F_{m-1}(x_i)\) — literally the residuals: each tree learns what the ensemble still gets wrong. Swapping the loss retargets the same machinery: log-loss → classification, quantile loss → quantile regression, ranking losses → search engines.

F₀ = argmin_c Σ L(yᵢ, c)                      # e.g. the mean / log-odds
for m in 1..M:
    rᵢ = −∂L(yᵢ, F(xᵢ))/∂F(xᵢ)               # pseudo-residuals
    fit small tree h_m to (X, r)               # depth 2–6
    F_m = F_{m−1} + ν · h_m                    # small step

Watch the ensemble assemble a sine wave from depth-2 trees, stage by stage:

One tree is a crude staircase; 5 trees sketch the shape; 50 fit it well; 300 begin chasing individual noisy points. Boosting attacks bias stage by stage — but keeps going into the noise if unchecked, so unlike a random forest, more trees CAN overfit.

The regularization toolkit

Boosting's power demands brakes — several, used together:

• Learning rate \(\nu\) (0.01–0.3): shrink each tree's contribution. Small \(\nu\) + many trees generalizes better than large \(\nu\) + few — the standard trade;
• Tree size: depth 2–6. Depth also caps the interaction order the model can express (depth-2 trees = pairwise interactions);
• Early stopping: monitor validation loss and stop adding trees when it stops improving — choosing \(M\) automatically;
• Subsampling: each tree sees a random fraction of rows (stochastic gradient boosting) and/or columns — borrowing the forest's decorrelation trick;
• XGBoost's addition: explicit penalty \(\Omega(h) = \gamma T + \frac{\lambda}{2}\lVert w \rVert^2\) on each tree's leaf count and leaf values, plus second-order (Newton) steps — regularization formalized inside the booster.

The modern libraries

# scikit-learn's fast implementation (LightGBM-style histograms)
from sklearn.ensemble import HistGradientBoostingClassifier
model = HistGradientBoostingClassifier(
    learning_rate=0.1, max_iter=500,
    early_stopping=True, validation_fraction=0.1,
)
model.fit(X_train, y_train)     # native missing-value support, no scaling

# XGBoost
import xgboost as xgb
model = xgb.XGBClassifier(n_estimators=1000, learning_rate=0.05,
                          max_depth=5, subsample=0.8, colsample_bytree=0.8,
                          early_stopping_rounds=50)
model.fit(X_train, y_train, eval_set=[(X_val, y_val)])

All handle missing values natively and need no feature scaling (tree lineage). Tune with randomized search or Optuna — key knobs: learning_rate, n_estimators (via early stopping), max_depth/num_leaves, subsample, colsample_bytree, reg_lambda.

Forest or boosting?

On tabular data, tuned gradient boosting still routinely beats deep learning (Grinsztajn et al., 2022) — the reigning champion where features are structured. When you hear "we use ML for credit scoring / churn / pricing", the model is very often an XGBoost-family booster. For images, audio, and text, neural networks take over — the story of Part VI.

Class materials

Quiz