Gradient Boosting as Gradient Descent in Function Space

Boosting builds a model as a sum of weak learners, added one at a time, each fitted to what the current sum gets wrong. The construction looks like an algorithm rather than an optimization, but it is an optimization: a steepest-descent search in the space of functions, where the gradient is evaluated at the training points and the descent direction is approximated by a small tree.

That framing is what makes boosting work with any differentiable loss. Once the residuals are understood as negative gradients, the same loop serves squared error, logistic loss, Poisson deviance, and ranking objectives, with no change to the ensemble machinery.

An additive model, fitted stagewise

The model has the form

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

where each $h_m$ is a small regression tree, $\nu \in (0,1]$ is a shrinkage factor, and $F_0$ is a constant chosen to minimize the loss with no trees at all: the mean of the target for squared error, the log-odds of the base rate for logistic loss.

The sum is not fitted jointly. At stage $m$ the previous $m-1$ terms are frozen, and only $h_m$ is chosen. This forward stagewise strategy is greedy, and it is the reason boosting is sequential: tree $m$ depends on the residuals left by trees $1$ through $m-1$, so the members cannot be trained independently the way bagged trees can.

Freezing earlier terms has a consequence that is easy to miss. A tree added at stage 50 cannot go back and change what the tree at stage 3 did, so the fit is a path, not a global optimum. Different random seeds and different column orders lead to different paths with similar loss. Boosting has no unique solution even for a fixed number of rounds and a fixed loss.

The negative gradient is the target

Write the loss for a single training point as $L(y_i, F(x_i))$, treating the model’s prediction at that point as a free parameter. The derivative

$$ g_{im} = \left. \frac{\partial L(y_i, F)}{\partial F} \right|{F = F{m-1}(x_i)} $$

is the direction in which the prediction at $x_i$ should move to reduce loss. The vector of these derivatives over the training set is the negative gradient, and it plays the role that the residual plays in least squares.

For squared error, $L = \tfrac12 (y - F)^2$, so $g = F - y$ and the negative gradient is exactly the residual $y - F$. This is the historical origin of the name. For logistic loss with $p = \sigma(F)$, the derivative is $p - y$, so the target for the next tree is the difference between predicted probability and label, which is bounded in $[-1, 1]$ rather than growing without limit. For Poisson deviance with a log link, the derivative is $\mu - y$ for mean $\mu = e^{F}$.

The magnitude of the gradient tells the algorithm where it is most wrong. Under squared error that is simply the size of the residual; under logistic loss it is largest for confidently wrong predictions, which is why boosting on log loss concentrates on the hard cases.

A tree as an approximate descent direction

Steepest descent would move the predictions along $-g$ by some step length. Here the prediction is not a free vector: it must be produced by a function from the tree class. So the algorithm solves, at each stage,

$$ h_m = \arg\min_{h \in \mathcal{H}} \sum_i \left( -g_{im} - h(x_i) \right)^2 $$

that is, it fits a regression tree to the negative gradient by least squares. The tree is a constrained approximation to the descent direction, and the constraint is what regularizes the fit: a tree of depth $d$ can express at most $2^d$ distinct values, so the step lives in a low-dimensional subspace of function space regardless of $n$.

def boost(X, y, loss_grad, n_rounds=300, lr=0.1, depth=3):
    F = [0.0] * len(y)                      # start from the loss-optimal constant
    trees = []
    for _ in range(n_rounds):
        g = [loss_grad(y[i], F[i]) for i in range(len(y))]
        h = fit_regression_tree(X, g, max_depth=depth)   # least squares on -g
        trees.append(h)
        F = [F[i] + lr * h.predict(X[i]) for i in range(len(y))]
    return trees

The leaf values deserve attention. Fitting the tree to gradients by least squares gives, at each leaf, the mean gradient in that leaf. That mean is not necessarily the best constant for the original loss. A single Newton step per leaf fixes this: set the leaf value to the minimizer of the summed loss over the samples in the leaf, which for squared error is the mean residual and for logistic loss is a log-odds ratio computed from the leaf’s positive and negative weights. This is the difference between gradient boosting and its second-order variant, and it is where the leaf values in the regularized split gain come from.

Shrinkage and the number of rounds

Two parameters control capacity, and they are coupled. The shrinkage $\nu$ multiplies each tree’s contribution, so a smaller $\nu$ means each stage moves less far and more stages are needed. Typical values are 0.1 with hundreds of rounds, or 0.01 to 0.05 with thousands; the product $\nu M$ is a rough stand-in for total movement, though the two are not interchangeable.

Small $\nu$ with large $M$ usually generalizes better than large $\nu$ with small $M$ at equal training loss. The mechanism is that many small steps average over more distinct trees, and each tree is fitted to a slightly different residual field, which introduces diversity between members in a way that resembles bagging. This is variance reduction layered on top of the bias reduction that boosting performs, and it is why the “multiple additive regression trees” formulation is not simply a slow version of the same fit.

The round count is normally chosen by early stopping on a validation set rather than by a fixed rule. Training loss decreases monotonically under shrinkage, so it carries no information about when to stop; validation loss typically falls and then rises, and the rise is the point at which the ensemble starts fitting label noise.

Subsampling rows at each stage, the stochastic variant, changes the picture again. Each tree sees a fraction of the training rows, drawn without replacement, so consecutive trees are fitted to different gradient estimates and the ensemble gains the diversity that bagging provides, while the gradients keep the fit focused on current errors. The combination is the standard configuration for large problems.

Where the sequential fit breaks

Boosting has failure modes that bagging does not share, and most of them come from the fact that later trees are fitted to the errors of earlier ones.

Label noise is amplified. A mislabeled point produces a large, persistent gradient at every stage, so successive trees keep fitting it. The model spends capacity on an unlearnable target and, in the worst case, ends with a confidently wrong prediction where a single tree would have hedged. Losses with a bounded gradient mitigate this by capping the influence of large residuals, at the cost of a non-smooth objective and a different leaf-value calculation.

Overfitting is silent. Because training loss always improves, a model trained too long looks better by every in-sample measure. The only reliable signal is held-out performance, which makes a validation split mandatory rather than advisory.

Trees must be shallow. Depth controls interaction order: a tree of depth $d$ can involve at most $d$ features along any path, so depth 1 (stumps) captures main effects only, depth 2 captures pairwise interactions, and deeper trees capture higher-order structure. Deep boosted trees overfit faster than deep bagged trees, because each one is fitted to the current residual field rather than to the raw target. Depths of 3 to 8 are the usual range, and the choice is a statement about how much interaction the problem has.

Nothing is parallel across the ensemble. Each round depends on the previous prediction vector, so boosting parallelizes across features and rows within a split search, not across trees. The split search itself is the same sorted scan described in the CART threshold scan, which is why histogram binning matters more for boosting than for forests: it is the only lever that reduces the per-round cost substantially.

Probabilities need separate calibration. Boosted classifiers trained on log loss tend to be overconfident on out-of-sample data, and the raw score is not a probability in the frequentist sense. The usual remedy is a monotone post-hoc fit on held-out scores, which is a separate model with its own assumptions.