Line Search And Leafwise Updates In Gradient Boosting

One Tree, Two Ways to Choose an Update

In gradient boosting, a fitted tree suggests a direction in which to change the current predictions. Choosing the size of that change is a separate step. One option is a global line search: multiply the tree’s predictions by one scalar and choose that scalar to minimize the loss. Another is to give each terminal node its own coefficient, minimizing the loss separately within each node. These choices agree in some settings, but need not agree when a single coefficient is required to serve observations with different residual patterns.

The distinction matters because fitting a tree to pseudo-residuals identifies a partition and a direction, not necessarily the best loss-minimizing value to assign at each terminal node. The calculations below hold the current model and the tree partition fixed. They ask how to optimize the update coefficients for the chosen loss.

Definition: Let the training data be $(x_i,y_i)$, $i=1,\ldots,n$, let $F_i$ be the current model score at $x_i$, and let $L(y,F)$ be a loss. For a fixed tree direction $h$, a global line-search coefficient is a minimizer, when it exists, of $$ \gamma \longmapsto \sum_{i=1}^n L(y_i,F_i+\gamma h(x_i)). $$ If a tree has terminal regions $R_1,\ldots,R_J$, a leafwise update chooses separate coefficients $\gamma_1,\ldots,\gamma_J$ to minimize $$ \sum_{j=1}^J \sum_{i:x_i\in R_j} L(y_i,F_i+\gamma_j). $$ The regions are taken to be disjoint and to cover the training observations.

A line search scales the already specified direction $h$ by one number. A leafwise update instead uses the terminal-region indicators as separate directions: the update for an observation in $R_j$ is $\gamma_j$. If the tree direction has leaf values other than one, a global scaling constrains all leaf changes to be proportional to those values; independently optimized leaf coefficients generally remove that constraint.

Squared-Error Loss: Explicit Solutions

Use the half-squared-error loss $L(y,F)=\tfrac12(y-F)^2$, and write the current residual as $r_i=y_i-F_i$. For a fixed direction $h$, the objective along the line is a quadratic:

Q(\gamma)=\frac12\sum_{i=1}^n(r_i-\gamma h(x_i))^2.

When at least one $h(x_i)$ is nonzero, this quadratic has a unique minimizer. For leafwise updates, take the direction within each region to be a constant change of one per unit coefficient. Each leaf then has its own residual mean as its optimal coefficient.

Worked Example: A Global Squared-Error Line Search

Suppose the residuals are $r=(2,1,-1)$, and a fitted tree direction takes values $h=(1,2,1)$ on the three observations. Find the global line-search coefficient and the minimized loss.

The numerator in the line-search formula is $$ \sum_{i=1}^3 r_i h_i=(2)(1)+(1)(2)+(-1)(1)=3, $$ and the denominator is $$ \sum_{i=1}^3 h_i^2=1^2+2^2+1^2=6. $$ Thus $\hat\gamma=3/6=1/2$. The updated residuals are $r_i-\hat\gamma h_i$, namely $3/2,0,-3/2$. The minimized half-squared-error is therefore $$ \frac12\left((3/2)^2+0^2+(-3/2)^2\right)=\frac94. $$ For comparison, the loss before the update was $\tfrac12(2^2+1^2+(-1)^2)=3$, so the line search reduces it.

Theorem: For half-squared-error loss and a fixed direction $h$, if $\sum_i h(x_i)^2>0$, the unique global line-search minimizer is $$ \hat\gamma=\frac{\sum_{i=1}^n h(x_i)r_i}{\sum_{i=1}^n h(x_i)^2}. $$ For terminal regions $R_j$, if $n_j=\#\{i:x_i\in R_j\}>0$, the unique leafwise minimizer is $$ \hat\gamma_j=\frac{1}{n_j}\sum_{i:x_i\in R_j}r_i. $$

Proof. Expand the global objective: $$ Q(\gamma)=\frac12\sum_i r_i^2-\gamma\sum_i h(x_i)r_i+\frac{\gamma^2}{2}\sum_i h(x_i)^2. $$ Its derivative is $-\sum_i h(x_i)r_i+\gamma\sum_i h(x_i)^2$, and its second derivative is $\sum_i h(x_i)^2>0$. Setting the first derivative to zero gives the stated unique minimizer. For one terminal region, the objective in its coefficient is $\tfrac12\sum_{i:x_i\in R_j}(r_i-\gamma_j)^2$. Its derivative is $-\sum_{i:x_i\in R_j}r_i+n_j\gamma_j$, and its second derivative is $n_j>0$. Setting the derivative to zero gives the residual mean. Since the leafwise objective is a sum of terms involving separate coefficients, minimizing each term minimizes the full objective. $\square$

Worked Example: Leafwise Updates Can Improve on One Shared Step

Consider four observations divided between two leaves. The residuals in the first leaf are $2,0$; those in the second are $-1,-3$. Find both leafwise coefficients, then compare their loss with the best single constant update applied to all four observations.

The residual mean in the first leaf is $(2+0)/2=1$, and in the second it is $(-1-3)/2=-2$. Thus the leafwise update is $(1,-2)$. The updated residuals are $1,-1$ in each leaf, so the total half-squared-error is $$ \frac12(1^2+(-1)^2+1^2+(-1)^2)=2. $$ A single constant update has coefficient equal to the mean of all four residuals: $$ \hat\gamma=\frac{2+0-1-3}{4}=-\frac12. $$ The resulting residuals are $5/2,1/2,-1/2,-5/2$, giving loss $$ \frac12\left((5/2)^2+(1/2)^2+(-1/2)^2+(-5/2)^2\right)=\frac{13}{2}. $$ The leafwise update achieves lower loss because it can move the two regions in opposite directions. The shared coefficient cannot do so.

Logistic Loss: Exact Leafwise Coefficients

For binary outcomes $y_i\in\{0,1\}$, let $F_i$ be the current logit score and define $p_i=\sigma(F_i)=1/(1+\exp(-F_i))$. The logistic loss for one observation is $$ L(y_i,F_i)=\log(1+\exp(F_i))-y_iF_i. $$ Its derivative with respect to the score is $\sigma(F_i)-y_i$. For a leafwise coefficient $\gamma_j$, the score is shifted to $F_i+\gamma_j$ for observations in that leaf. The exact coefficient therefore solves a nonlinear score equation; in general it does not have a closed-form expression when the current scores vary across observations.

Theorem: In a nonempty terminal region $R_j$, the logistic-loss leafwise objective has a unique finite minimizer if the region contains at least one observation with $y_i=1$ and at least one with $y_i=0$. That minimizer is the unique solution of $$ \sum_{i:x_i\in R_j}\left(\sigma(F_i+\gamma_j)-y_i\right)=0. $$ If all labels in the region are 1, the objective decreases toward its infimum as $\gamma_j\to+\infty$; if all labels are 0, it decreases toward its infimum as $\gamma_j\to-\infty$. In either pure-label case there is no finite minimizer.

Proof. Write $g(\gamma)=\sum_{i:x_i\in R_j}[\sigma(F_i+\gamma)-y_i]$, the derivative of the leaf objective. Its derivative is $$ g'(\gamma)=\sum_{i:x_i\in R_j}\sigma(F_i+\gamma)\bigl(1-\sigma(F_i+\gamma)\bigr)>0 $$ for every finite $\gamma$, since the region is nonempty and each logistic probability is strictly between zero and one. Thus $g$ is strictly increasing. As $\gamma\to-\infty$, every probability tends to zero, so $g(\gamma)\to-\sum_{i:x_i\in R_j}y_i$, the negative of the number of positive labels. As $\gamma\to+\infty$, every probability tends to one, so $g(\gamma)\to\sum_{i:x_i\in R_j}(1-y_i)$, the number of negative labels. If both counts are positive, these limits have opposite signs. Continuity and the intermediate value theorem give a root, and strict increase makes it unique. The objective is strictly convex because its second derivative is $g'(\gamma)>0$, so that root is the unique minimizer. If all labels are 1, then $g(\gamma)<0$ at every finite $\gamma$; if all labels are 0, then $g(\gamma)>0$ at every finite $\gamma$. In each case the objective has no finite stationary point and decreases toward its infimum in the stated direction. $\square$

Worked Example: Exact Logistic Updates in Two Leaves

Suppose every current score is zero. A tree has two leaves, each containing four observations. In the first leaf there are three positive labels and one negative label; in the second there is one positive label and three negative labels. Calculate the exact leafwise updates and compare them with a single global shift applied to both leaves.

In the first leaf, all four updated scores equal $\gamma_1$. The score equation is $4\sigma(\gamma_1)-3=0$, so $\sigma(\gamma_1)=3/4$ and $$ \hat\gamma_1=\log\left(\frac{3/4}{1-3/4}\right)=\log 3. $$ In the second leaf, the equation is $4\sigma(\gamma_2)-1=0$, giving $\sigma(\gamma_2)=1/4$ and $\hat\gamma_2=-\log 3$.

If instead one shift $\gamma$ is shared by all eight observations, its score equation is $8\sigma(\gamma)-4=0$, so $\hat\gamma=0$. The global shift cannot represent the different class proportions in the two leaves. The loss comparison confirms the improvement: at zero scores the total loss is $8\log 2=\log 256$. After the leafwise updates, each leaf has loss $$ -3\log(3/4)-\log(1/4)=\log(256/27), $$ so the total is $2\log(256/27)=\log(256^2/27^2)$, which is less than $\log 256$. Indeed $256^2/27^2<256$, because $256<27^2=729$. The shared update leaves the scores at zero and does not change the loss.

Newton Updates When the Logistic Equation Is Not Explicit

With unequal current scores inside a leaf, the exact logistic score equation typically must be solved numerically. A common local calculation is a Newton step. If the current leaf coefficient is $\gamma$, define $$ g(\gamma)=\sum_{i:x_i\in R_j}\left(\sigma(F_i+\gamma)-y_i\right),\qquad H(\gamma)=\sum_{i:x_i\in R_j}\sigma(F_i+\gamma)\left(1-\sigma(F_i+\gamma)\right). $$ Since $g'(\gamma)=H(\gamma)>0$, the Newton update is $\gamma_{\mathrm{new}}=\gamma-g(\gamma)/H(\gamma)$. This is an iteration toward the exact minimizer, not generally the exact minimizer itself.

Worked Example: One Newton Step for a Logistic Leaf

A leaf contains three observations, all with current score zero, and labels $1,1,0$. Starting from $\gamma=0$, calculate one Newton update and compare it with the exact coefficient.

At $\gamma=0$, every predicted probability is $1/2$. Therefore $$ g(0)=\left(\frac12-1\right)+\left(\frac12-1\right)+\left(\frac12-0\right)=-\frac12, \qquad H(0)=3\left(\frac12\cdot\frac12\right)=\frac34. $$ The Newton update is $$ \gamma_{\mathrm{new}}=0-\frac{-1/2}{3/4}=\frac23. $$ The exact score equation is $3\sigma(\gamma)-2=0$, so the exact coefficient is $\log 2\approx0.69315$. After the Newton step, $\sigma(2/3)\approx0.66076$, so the score equation’s left side is $3(0.66076)-2\approx-0.01773$, not zero. A further Newton correction is approximately $0.01773/0.6725\approx0.02636$, bringing the coefficient to about $0.69303$, close to $\log 2$. The first step is useful, but it should not be mistaken for the exact line-search solution.

Interpretation and a Common Pitfall

The global and leafwise calculations answer different optimization questions. A global line search is appropriate when the update must remain a scalar multiple of one specified direction. Leafwise optimization instead gives each terminal region an independent coefficient and minimizes the training loss over that larger set of updates. For squared-error loss, the global coefficient is a direction-weighted residual average, while the leaf coefficients are residual means. For logistic loss, the global derivative includes the direction values $h(x_i)$; the leafwise equation sums the score derivatives within each region.

Common mistake: use the global coefficient as if it were optimal in every leaf. A single line search only minimizes over updates of the form $\gamma h$; it does not optimize the $J$ independent leaf coefficients.
Correction: Specify the allowed update first. If terminal nodes may move independently, minimize the loss separately within each node. The resulting loss cannot exceed the best loss under a more restricted global update, because the global update is one feasible choice only when its leaf changes are allowed by the leafwise parameterization.
Common mistake: treat a logistic Newton step as an exact coefficient. Newton’s method uses a local quadratic approximation and may require repeated iterations.
Correction: The exact logistic leaf coefficient solves the score equation. Check the derivative at the proposed value, and remember that pure-label leaves have no finite exact minimizer without additional constraints or regularization.

Key takeaway: A tree’s partition and direction do not by themselves determine how its update coefficients should be chosen. Global line search uses one scalar; leafwise optimization uses one coefficient per terminal region. Squared-error updates have closed forms, while logistic leaf updates are defined by a score equation and are often computed numerically.

Check Your Understanding

Use the definitions and derivations above to answer these questions.

For squared-error loss, what condition on the tree direction ensures that the global line-search coefficient is unique?
Why can separate terminal-node coefficients reduce squared-error loss when one global coefficient cannot?
Write the score equation for the exact logistic update in a leaf containing observations with unequal current scores.
What condition on the labels in a logistic leaf guarantees a unique finite minimizer?
Explain why a Newton update for a logistic leaf is not necessarily the exact leafwise minimizer.