XGBoost

Gradient boosting, plus a second-order objective and a regularized tree.

The model that won tabular Kaggle — built from three formulas.

What changes from plain boosting

Plain GBM: fit each tree to the negative gradient. First-order.
XGBoost adds two things:
- a second-order view — every sample carries a gradient g and a hessian h.
- a regularized tree — L2 penalty lambda on leaves, gamma per leaf.
Same additive shape, same shrinkage. Better step, self-pruning tree.

The data

A 1-D toy for the animation: 90 noisy points, 65 train / 25 val.

The math

Second-order Taylor objective at round t:

\mathcal{L}^{(t)} \approx \sum_{i} \left[ g_i\, f_t(x_i) + \tfrac{1}{2} h_i\, f_t(x_i)^2 \right] + \gamma T + \tfrac{1}{2}\lambda \sum_j w_j^2

Optimal leaf weight (the key formula):

w_j^{*} = -\frac{G_j}{H_j + \lambda}

Split gain, with the gamma toll for the extra leaf:

\text{Gain} = \frac{1}{2}\left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma

G, H are the gradient and hessian sums of a leaf's rows.

Watch it work

One boosting round per frame: the staircase snaps to the curve, the loss falls. 30 rounds, depth-2 trees, shrink 0.3. Train MSE → 0.038, val MSE → 0.110.

Why regularization matters

Test RMSE per round on real diabetes data, three values of lambda:

lambda = 0: overfits fast — best 53.07 by round 6, then climbs.
lambda = 1: goes lowest — 52.11 around round 11.
lambda = 30: over-regularized — floored at 55.44, never overfits, never wins.

Scratch vs. library

Ours tracks the real xgboost (59.50 vs 60.01 RMSE, predictions correlate 0.9978). Both second-order boosters beat plain gradient boosting (64.29) — twelve RMSE points.

Takeaways

Second-order step + regularized tree + shrinkage = three brakes on overfitting.
Best-in-class on tabular data with little tuning; handles missing values, no scaling.
Knobs that matter: learning rate + tree count, then max_depth, then lambda/gamma.
A random forest is enough when you don't need the last few percent; one tree when you need to read it.