The Mathematics Behind Gradient Boosting and Ensembles

A single decision tree is a mediocre model. Grown deep it memorises the training set, grown shallow it barely says anything, and either way its predictions swing wildly when the data shifts by a few rows. Yet ensembles of exactly these trees win competition after competition and sit at the centre of most tabular machine learning done in industry. Something in the combination rescues the parts.

The rescue is mathematical, and it comes in two distinct flavours that are often confused. Bagging and random forests average many models to shrink variance. Boosting adds many models in sequence to shrink bias. Those are different theorems with different formulas, and the difference explains everything downstream: why a random forest cannot really overfit by adding trees while a boosted model can, why forests randomise features but boosters do not, and why XGBoost’s objective function contains terms a plain gradient booster never had. This article derives all of it.

The bias-variance decomposition

Everything begins with an identity about squared error. Suppose the truth is $y = f(x) + \epsilon$ where the noise has mean zero and variance $\sigma^2$, and we fit a model $\hat{f}$ on a random training set. The expected squared error at a point x decomposes into three pieces:

The three terms are the whole map. Bias is how far the model’s average prediction sits from the truth, and it measures systematic wrongness. Variance is how much the prediction jumps around as the training data changes, and it measures instability. The noise term is the floor: no model can beat it.

A deep decision tree occupies a specific corner of this decomposition. It is nearly unbiased, because with enough splits it can approximate almost any function, but its variance is enormous, because tiny changes in the data change which split is chosen at the top and cascade through everything below. A shallow tree is the mirror image, stable but systematically wrong. Ensembles are strategies for attacking one term while leaving the other alone, and the two families attack different terms.

Why averaging works, and its hard limit

Take B models, each with variance $\sigma^2$, and average them. If they were independent, the variance of the average would be:

which goes to zero as B grows. Meanwhile the bias is unchanged, since the average of B copies of an unbiased estimator is still unbiased. That is the entire promise of bagging: keep the deep tree’s low bias, delete its variance by averaging.

Independence, however, is a fiction. Bootstrap samples overlap heavily, so the trees are correlated. With pairwise correlation $\rho$ between models, the correct expression is:

Now look at what happens as $B \to \infty$. The second term vanishes, but the first does not:

This limit is the most consequential formula in ensemble learning. Adding trees to a random forest buys you progress only on the second term, and once that term is small, further trees do nothing at all. The floor is set by $\rho$, the correlation between the trees, and no amount of computation lowers it.

The formula also explains a design choice that otherwise looks arbitrary. If $\rho$ is the binding constraint, then the way to improve a forest is not more trees but less correlated trees. This is exactly what random forests do beyond bagging: at every split, only a random subset of features is considered. If one feature is strongly predictive, plain bagged trees would all split on it first and be highly correlated; forcing most trees to ignore it at any given split decorrelates them, lowering $\rho$ and lowering the asymptotic variance. The cost is a small rise in each individual tree’s bias, and the trade is usually worth it. The max_features hyperparameter is a direct dial on $\rho$ in the formula above.

One corollary is worth stating plainly, because it contradicts a common intuition. Adding trees to a random forest cannot cause overfitting. More terms in the average drive the $\frac{1-\rho}{B}\sigma^2$ term down monotonically and leave bias untouched, so the curve flattens rather than turning upward. Boosting, as we are about to see, has no such protection.

Boosting: attacking bias instead

Boosting builds an additive model, one term at a time:

Each $h_m$ is a weak learner, typically a shallow tree, and $\nu$ is a shrinkage factor we will return to. The models are not averaged and not independent. Each one is fitted after the last, with full knowledge of what the ensemble so far gets wrong.

The training procedure is forward stage wise: having built $F_{m-1}$, choose the next term to minimise the loss of the updated ensemble:

Because each new learner targets the remaining error rather than re-estimating the whole function, boosting drives down bias. A stump has terrible bias alone, but a thousand stumps in sequence approximate a rich function. The variance term, however, is no longer protected: keep adding terms and $F_M$ eventually fits the noise. Boosting has an optimal M and overshooting it degrades test performance, which is why early stopping belongs to boosting and not to forests.

Residual fitting is gradient descent in disguise

Take squared error loss and work out what the stagewise problem asks for. With:

the derivative with respect to the current prediction is:

so the negative gradient is exactly the residual:

This is the identity that names the whole field. The folklore instruction, “fit the next tree to the residuals”, is not a heuristic at all: for squared loss, the residual is the negative gradient of the loss with respect to the model’s output. Boosting is gradient descent, performed in function space rather than parameter space, where each step is a tree pointing in the descent direction and $\nu$ is the learning rate.

Once that is clear, the generalisation is immediate. Squared loss is not special, so define the pseudo-residual for any differentiable loss:

and fit $h_m$ to those values. Log loss gives pseudo-residuals of the form $y_i – p_i$, the difference between the label and the predicted probability, and absolute loss gives the sign of the residual, which is why it resists outliers. One algorithm, any loss with a gradient. This is gradient boosting.

The shrinkage factor $\nu$ now has a clear reading as a step size. Small steps make slower but more careful progress, and the empirical rule that low learning rates need many trees is just the statement that reaching a fixed distance in smaller steps requires more of them. The two hyperparameters trade against each other because $\nu M$ is roughly what determines how far the ensemble travels.

XGBoost: second-order steps and a regularised objective

XGBoost changes two things, and both are visible in its objective. First it adds an explicit penalty on model complexity; second it uses second derivatives rather than first. The objective at iteration t is:

with the regularisation term defined over the tree’s structure:

Here T is the number of leaves and $w_j$ is the value predicted at leaf j. The $\gamma T$ term charges rent per leaf, and the $\lambda$ term is an L2 penalty shrinking the leaf values, so complexity is priced inside the objective rather than controlled from outside by hand-set depth limits alone.

Now approximate the loss with a second-order Taylor expansion around the current prediction. Writing $g_i$ and $h_i$ for the first and second derivatives:

the objective becomes, after dropping the constant term that does not involve $f_t$:

Every point in a given leaf receives the same prediction, so group the sums by leaf. Writing $I_j$ for the set of points landing in leaf j, and defining the leaf’s gradient and Hessian sums:

the objective collapses into one term per leaf:

This is a quadratic in each $w_j$, independent across leaves, so it can be minimised exactly. Differentiating and solving gives the optimal leaf value in closed form:

Substituting back gives the best achievable objective for a given tree structure:

The leaf formula rewards inspection. The numerator is the accumulated gradient, meaning how wrong the ensemble is on these points and in which direction. The denominator is the accumulated curvature plus $\lambda$, and it acts as a confidence measure: leaves holding few points, or points where the loss is flat, get small denominators before $\lambda$ arrives and would otherwise produce wild leaf values. Adding $\lambda$ shrinks exactly those unreliable leaves hardest while barely touching leaves backed by plenty of data. That is regularisation with a mechanism, not a fudge factor.

The gain formula and why pruning is automatic

The expression for $\mathcal{L}^{(t)*}$ is a score for a tree structure, which turns split selection into arithmetic. Consider splitting a leaf into left and right children. The improvement in the objective is the score of the two new leaves minus the score of the original, plus the cost of the extra leaf:

XGBoost evaluates this for every candidate split and takes the best. The final $-\gamma$ is doing something elegant: if the structural improvement is smaller than the price of a new leaf, the gain is negative and the split is refused. Pruning is not a separate post-processing pass that trims a grown tree; it is a consequence of the objective, applied at the moment each split is considered. The gamma hyperparameter is the minimum improvement you insist on before paying for more complexity.

Finally, check what happens with squared error, where $g_i = \hat{y}_i – y_i$ and $h_i = 1$. The leaf value becomes:

which is the mean residual in the leaf, shrunk toward zero by $\lambda$. Plain gradient boosting emerges as the special case, and XGBoost is its second-order, regularised generalisation. The two algorithms are one algorithm at different levels of refinement.

What the mathematics tells you to do

The practical rules follow from the derivations rather than from experience alone. Do not tune the number of trees in a random forest as if it were a regularisation dial, because $\rho\sigma^2$ is the floor and extra trees only shave the vanishing term; tune max_features instead, since that is the parameter that moves $\rho$. Do watch the number of trees in a booster and stop early, because boosting attacks bias with no variance protection and will eventually fit noise. Expect a low learning rate to require more rounds, since $\nu$ is a step size and the ensemble must still travel the same distance. Read lambda as shrinkage that bites hardest on leaves with little evidence behind them, and gamma as the toll charged per leaf that makes weak splits refuse themselves.

The larger lesson is that “ensemble” names two opposite strategies wearing similar clothes. Bagging averages independent-ish models to kill variance and leaves bias where it found it. Boosting chains dependent models to kill bias and must be restrained before variance returns. Knowing which term your ensemble is attacking tells you which hyperparameters can possibly help, and that is the difference between tuning with a map and tuning by guesswork.

See you soon.