Gradient Boosting From The Loss Gradient

From Additive Updates to a Loss Gradient

Boosting builds a prediction function in stages. At a given stage, the current model has fitted values \(F_i\) for training observations \(i=1,\ldots,n\). The next learner contributes an update to those fitted values. The key question is how to choose that update so that it decreases the objective being minimized.

A decision tree cannot usually follow an arbitrary direction in the \(n\)-dimensional space of fitted values. Instead, gradient boosting uses the tree to approximate a direction that decreases the loss. The gradient identifies the direction of steepest local increase; its negative points toward local decrease. Under squared-error loss, that negative gradient is exactly the vector of residuals. This gives a precise explanation for why squared-error boosting can be carried out by fitting trees to residuals.

A candidate learner \(h\) supplies fitted updates \(h_i=h(x_i)\). The proposed stagewise update is \(F_i\leftarrow F_i+\gamma h_i\), where \(\gamma\) is a step size. The tree is useful when its values point in a loss-reducing direction, even if they do not match the negative gradient exactly.

Why the Negative Gradient Is a Descent Direction

Consider a small move from the current fitted-value vector \(F\) in the direction \(h\). Differentiability gives the first-order Taylor approximation $$ L(F+\gamma h)\approx L(F)+\gamma \nabla L(F)^{\mathsf T}h. $$ For a positive, sufficiently small \(\gamma\), the linear term predicts a decrease when \(\nabla L(F)^{\mathsf T}h<0\). If \(h\) were the exact negative gradient, then \(\nabla L(F)^{\mathsf T}h=-\|\nabla L(F)\|^2\), which is negative unless the gradient is zero. A tree is a restricted function, so the fitted direction is an approximation; it should still have a negative inner product with the gradient to be locally helpful.

In practice, the tree is fitted to the negative-gradient values \(g_i\), using the training predictors \(x_i\). For example, a squared-error regression tree chooses splits and terminal-node predictions that approximate those targets. The result \(h_i\) is then used as a candidate model update. The fit and the step size are distinct: the tree determines the shape of the update, while a line search can determine how far to move in that direction.

Squared Error Gives Residual Fitting

Use the half-squared-error convention $$ L(F)=\frac{1}{2}\sum_{i=1}^{n}(y_i-F_i)^2. $$ The factor \(1/2\) is convenient because it cancels the \(2\) produced by differentiation. Let \(r_i=y_i-F_i\) be the current residual. Differentiating each observation’s loss with respect to its fitted value gives $$ \frac{\partial}{\partial F_i}\left\{\frac{1}{2}(y_i-F_i)^2\right\}=-(y_i-F_i)=-r_i. $$ Therefore \(g_i=-\partial L/\partial F_i=r_i\). The negative-gradient targets are the residuals, so fitting a regression tree to those targets is precisely residual fitting.

For a proposed update \(F_i+\gamma h_i\), the new residual is \(r_i-\gamma h_i\). The loss along the update is a quadratic function of \(\gamma\): $$ L(\gamma)=\frac{1}{2}\sum_{i=1}^{n}(r_i-\gamma h_i)^2. $$ Differentiating this expression and setting the derivative equal to zero gives the exact line-search step, provided the direction is not identically zero.

This is the least-squares projection of the residual vector onto the proposed update vector. At the minimizing step, the updated residual is orthogonal to the direction \(h\), because $$ \sum_{i=1}^{n}(r_i-\gamma^*h_i)h_i=0. $$ If \(\sum_i h_i^2=0\), then all \(h_i=0\), so the proposed direction makes no change and the displayed ratio is undefined. If the numerator is nonpositive, an unconstrained line search does not yield a positive step in this direction; a boosting procedure seeking a nonnegative update should reject or otherwise handle that direction.

The same calculation verifies the loss reduction. Writing \(A=\sum_i r_i h_i\) and \(B=\sum_i h_i^2>0\), expansion yields \(L(\gamma)=L(0)-\gamma A+\frac{1}{2}\gamma^2B\). When \(A>0\), substituting \(\gamma^*=A/B\) gives a reduction of \(A^2/(2B)\). Thus the exact squared-error line search does not merely point toward improvement: for a positively aligned direction, it quantifies the improvement.

Tree Leaves and Their Update Values

A regression tree with terminal regions \(R_1,\ldots,R_J\) assigns one constant update to every observation in a region. If the tree is fitted to squared-error targets \(r_i\), the least-squares prediction in a leaf is the mean residual in that leaf. This follows because, for a constant \(c\), the sum \(\sum_{i\in R_j}(r_i-c)^2\) is minimized at the sample mean of the \(r_i\) values in that region.

After the tree is fitted, the line search can still scale all its leaf values together. Consequently, the tree’s leaf means need not themselves be the final changes to the model. In particular, a tree fitted to residuals can be followed by an exact multiplier \(\gamma^*\), and a further shrinkage factor can deliberately make the stagewise update smaller.

Line Search, Shrinkage, and a Frequent Trap

The multiplier \(\gamma^*\) is the exact minimizer along the specified direction \(h\) for the stated loss. Shrinkage is a separate modeling choice: with a factor \(0<\nu\leq1\), a procedure may instead update by \(\nu\gamma^*h\). For squared error, this is a shorter step than the exact line-search step when \(\nu<1\). It is not correct to describe \(\nu\) as if it were part of the numerator or denominator in the line-search formula.

A common exam error is to use the residual sum where the line-search numerator requires a residual–direction inner product. Suppose four observations have residuals summing to \(8\), and the proposed tree direction is \(h_i=2\) for all four observations. Then $$ \sum_i r_i h_i=2\sum_i r_i=2(8)=16, \qquad \sum_i h_i^2=4(2^2)=16. $$ So \(\gamma^*=16/16=1\). Dividing \(8\) by \(16\) would incorrectly give \(1/2\): it omits the factor of \(2\) in the numerator. As a direct check, the update subtracts \(2\) from each residual, and the residual sum decreases by \(4(2)=8\), as expected.