Gradient Boosting as Functional Gradient Descent

Ordinary gradient descent updates a parameter vector: \(\theta \leftarrow \theta - \eta \nabla_\theta L\). Gradient boosting updates a function: \(F \leftarrow F - \eta \nabla_F L\). The difficulty is that you cannot store an arbitrary function, so the gradient is approximated by fitting a weak learner to it. That substitution is the entire algorithm, and Friedman's framing of it is why boosting stopped being a classification trick and became a general method for any differentiable loss (Friedman, 2001, Greedy Function Approximation: A Gradient Boosting Machine, Annals of Statistics 29(5)).

The algorithm, derived

The model is additive: \(F_M(x) = \sum_{m=0}^{M} \eta\, h_m(x)\). At stage \(m\), the loss \(L(y, F(x))\) is treated as a function of the current predictions, and the negative gradient evaluated at each training point gives the pseudo-residual

Fit a regression tree \(h_m\) to the pairs \((x_i, r_{im})\) by squared error, and add a shrunken version of it to the model. The tree is not fitting the target; it is fitting the direction the loss wants predictions to move.

For squared-error loss, \(r_{im} = y_i - F_{m-1}(x_i)\): literally the residual, which is why the pre-Friedman description of boosting as "fit the residuals" is the special case that named the field. For log loss, \(r_{im} = y_i - p_i\) with \(p_i = \sigma(F_{m-1}(x_i))\); for absolute error, \(r_{im} = \mathrm{sign}(y_i - F_{m-1}(x_i))\), which is why \(\ell_1\) boosting is robust to outliers with no other change. Swap the loss, get a new method.

XGBoost extends this to a second-order expansion, using both gradients \(g_i\) and Hessians \(h_i\) and adding an explicit penalty on tree complexity. The optimal weight for leaf \(j\) with instance set \(I_j\) becomes

and the corresponding gain formula is what the split finder maximises, with a \(\gamma\) term per additional leaf acting as pre-pruning (Chen and Guestrin, 2016, XGBoost, KDD, arXiv:1603.02754). Regularisation is inside the objective rather than bolted on.

Learning rate and the count of trees

The shrinkage \(\eta\) (typically 0.01 to 0.1) and the number of trees \(M\) trade off almost exactly: halving \(\eta\) roughly doubles the \(M\) needed for the same training loss. Small \(\eta\) with large \(M\) generalises better, because each step commits less and the ensemble averages over more, slightly different, directions.

This means only one of them should ever be tuned freely. Fix \(\eta\) at a small value you can afford, then choose \(M\) by early stopping on a validation set. Grid-searching both is spending compute to rediscover their inverse relationship.

The two dominant engineering variants

LightGBM replaces the exact split sweep with histogram binning of features into typically 255 bins, grows trees leaf-wise (always splitting the leaf with the highest gain, producing unbalanced deep trees) rather than level-wise, and adds gradient-based one-side sampling and exclusive feature bundling. The paper reports training speedups over conventional GBDT of more than 20x at comparable accuracy (Ke et al., 2017, NeurIPS). Leaf-wise growth overfits more readily on small data, which is what num_leaves exists to bound.

CatBoost targets a subtler problem: computing a categorical feature's target statistic from the same rows used to fit the tree leaks the label, producing a prediction shift. Ordered boosting uses a random permutation and estimates each example's statistics only from examples earlier in that permutation, which removes the leakage at the cost of maintaining several models (Prokhorenkova et al., 2018, NeurIPS, arXiv:1706.09516).

When it breaks

Boosting reduces bias, so it overfits where bagging did not. Each tree fits the current errors, including the noise in them. Without early stopping, training loss goes to zero and validation loss turns upward. A validation set is not optional the way it arguably is for a random forest with OOB scoring.

It is inherently sequential. Tree \(m\) needs the residuals from tree \(m-1\), so the ensemble cannot be parallelised across trees the way bagging can. Parallelism lives inside split finding, which is why histogram methods matter so much for wall-clock time.

Noisy labels are amplified. A mislabelled point produces a large pseudo-residual, attracts successive trees, and gets progressively memorised. Robust losses (Huber, absolute error) and subsampling each tree's rows both damp this; squared error does the opposite.

Deep trees defeat the mechanism. Boosting assumes weak learners. Depth 3 to 8 is the standard range; depth 20 makes each tree fit most of the signal at once, the ensemble stops correcting and starts averaging strong overfitted models, and both accuracy and training time degrade.