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:

\[ F_M(x) = F_0(x) + \nu \sum_{m=1}^{M} h_m(x) \]

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:

\[ r_i^{(m)} = -\frac{\partial L\big(y_i, F(x_i)\big)}{\partial F(x_i)}\bigg|_{F = F_{m-1}} \]

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)])

	Sells itself on
XGBoost	regularized objective, robustness, huge ecosystem
LightGBM	histogram binning + leaf-wise growth → fastest on large data
CatBoost	native categorical features (ordered target encoding), great defaults

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?

	Random Forest	Gradient Boosting
Trees built	independently, in parallel	sequentially, each fixing the rest
Attacks	variance	bias (variance via shrinkage/subsampling)
More trees	never hurts	overfits — use early stopping
Tuning effort	minimal	moderate — and it pays
Typical tabular accuracy	very good	state of the art (tuned)

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.

Watch the residual shrink

The whole idea fits in one loop: start with the mean, look at what is still wrong, fit a weak learner to that, add a fraction of it, repeat. The bottom panel below is the residual — and the green step function is the stump about to be fitted to it.

Two experiments make the learning rate concrete.

Set ν = 1 with 6 stumps, then ν = 0.15 with 40. Both reach a similar fit, but the second got there in small, hedged steps. Shrinkage is not a slowdown to be tuned away — it is what lets the ensemble correct its own overshoot, and it is why learning_rate and n_estimators must be tuned together: halving one roughly doubles the other.

Then set ν = 1 and push the stumps to 60. The blue curve starts bending toward individual points. The training mean squared error (MSE) keeps falling the whole time — which is precisely why it cannot be the stopping signal. Early stopping watches a validation curve, and that one turns back up.

Class materials

Class notebook (in Portuguese)

Hands-on notebook used in class — Aula 21 — Gradient Boosting: open in Colab

References

Freund, Y.; Schapire, R. "A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting." JCSS 55 (1997). DOI
Friedman, J. H. "Greedy Function Approximation: A Gradient Boosting Machine." Annals of Statistics 29 (2001). DOI
Chen, T.; Guestrin, C. "XGBoost: A Scalable Tree Boosting System." KDD (2016). DOI

The full course bibliography is on the references page.