Second-Order Boosting and the Regularized Split Gain

First-order boosting, as described in gradient boosting, fits each tree to the negative gradient and picks leaf values by a line search. That leaves two things on the table: the curvature of the loss, which says how far a step can be taken before the linear approximation stops being useful, and any explicit control over the size of the trees being added. Folding both into the objective produces an algorithm whose split criterion is computed from two sums per node and whose leaf values are exact minimizers of a local quadratic.

The formulation also attaches a number to every candidate split, which turns pruning, minimum child size, and complexity control into terms of the same expression rather than separate stopping rules.

The objective, with complexity inside it

At stage $m$ the ensemble prediction is $\hat y_i = F_{m-1}(x_i) + f_m(x_i)$, and the quantity being minimized is the training loss plus a penalty on the new tree alone:

$$ \mathcal{L} = \sum_i l(y_i, \hat y_i) + \Omega(f_m), \qquad \Omega(f) = \gamma T + \tfrac{1}{2}\lambda \sum_{j=1}^{T} w_j^2 $$

Here $T$ is the number of leaves, $w_j$ is the value assigned by leaf $j$, $\gamma$ is a fixed cost per leaf, and $\lambda$ penalizes large leaf values. The penalty is applied only to the current tree because the earlier ones are frozen; their contribution is a constant with respect to $f_m$.

$\gamma$ and $\lambda$ do different jobs, and confusing them is a common source of misconfiguration. $\gamma$ is a threshold on gain: a split must improve the objective by more than $\gamma$ to be worth making, which prunes the tree during growth by an amount that scales with the tree’s size rather than with the data’s. $\lambda$ shrinks leaf values toward zero and also appears in the denominator of the leaf formula, so it damps the effect of nodes supported by few samples. Neither is a substitute for the learning rate, which controls the global step and sits outside the objective entirely.

Expanding to second order

Substituting the quadratic Taylor expansion of the loss around the current prediction,

$$ l(y_i, \hat y_i + f(x_i)) \approx l(y_i, \hat y_i) + g_i f(x_i) + \tfrac{1}{2} h_i f(x_i)^2 $$

with $g_i = \partial_{\hat y} l$ and $h_i = \partial^2_{\hat y} l$ evaluated at $\hat y_i$. Dropping the constant term leaves

$$ \tilde{\mathcal{L}} = \sum_i \left[ g_i f(x_i) + \tfrac{1}{2} h_i f(x_i)^2 \right] + \gamma T

• \tfrac{1}{2}\lambda \sum_j w_j^2 $$

Since $f(x_i)$ is constant within a leaf, group the sums by leaf. For leaf $j$, with $G_j = \sum_{i \in j} g_i$ and $H_j = \sum_{i \in j} h_i$, the contribution is $G_j w_j + \tfrac12 (H_j + \lambda) w_j^2 + \gamma$. This is a one-dimensional quadratic in $w_j$, and its minimizer is

$$ w_j^* = -\frac{G_j}{H_j + \lambda} $$

Substituting back gives the objective’s optimal value for a fixed tree structure:

$$ \tilde{\mathcal{L}}^* = -\frac{1}{2}\sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T $$

Everything on the right is a function of two accumulated quantities per leaf. No line search, no per-leaf iterative fit, and no reference to the loss beyond its first two derivatives at the current prediction.

The gain of a split

Comparing the parent’s optimal value with the sum of the children’s gives the improvement from splitting node $P$ into $L$ and $R$:

$$ \text{gain} = \frac{1}{2}\left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda}

• \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma $$

The expression is evaluated in $O(1)$ per candidate threshold once the prefix sums of $g$ and $h$ along the sorted feature values are available, so the scan costs the same as before plus one extra floating point accumulation per step.

def split_gain(gl, hl, gr, hr, lam, gamma):
    parent = (gl + gr) ** 2 / (hl + hr + lam)
    children = gl ** 2 / (hl + lam) + gr ** 2 / (hr + lam)
    return 0.5 * (children - parent) - gamma

Three properties fall out of the algebra.

Splits with zero total gradient are worthless. If $G_L = G_R = 0$ the gain is negative, whatever the sample counts. A split that separates two groups whose gradients cancel contributes nothing, because no leaf value can reduce the objective. This is stricter than an impurity criterion, which would still reward the purity increase.

Splits are compared in loss units, not in purity units. The gain is a reduction in the regularized objective, so it is directly comparable to the leaf cost $\gamma$ and to gains at other nodes. A threshold tuned on “gain must exceed 100” is meaningful within a fixed loss and scaling of the target; change the loss from squared error to logistic and the same number means something else.

The penalty is subtracted per split, not per tree. A deep path pays $\gamma$ at each internal node, so $\gamma$ grows in influence with depth even when $\lambda$ is fixed. Setting $\gamma$ high therefore produces shallow trees without needing an explicit depth limit, which is how some implementations replace the depth cap with a gain threshold.

What the hessian changes in practice

For squared error, $g = \hat y - y$ and $h = 1$ for every sample, so the denominators are just sample counts (plus $\lambda$) and the gain reduces to the between-group sum of squares divided by the counts. Second-order boosting on squared error is therefore the same split criterion as a regression tree, which is a useful sanity check on the formula.

For logistic loss with $p = \sigma(\hat y)$, $g = p - y$ and $h = p(1-p)$. The hessian is largest for predictions near 0.5 and vanishes as the prediction saturates. Two effects follow. Samples the model already classifies confidently contribute almost nothing to $H$, so they stop influencing split choice even if their gradient is nonzero. And a leaf made only of saturated samples has $H \approx 0$, making $w^* = -G/H$ enormous; $\lambda$ is what prevents that division from exploding, which is the real reason it is not optional in practice.

The hessian also supplies the scale for the step. Under squared error the Newton leaf value is the mean gradient divided by the count, which is exactly the least-squares optimum. Under logistic loss it is a log-odds update that accounts for how much the current probability can still move, so leaves stop being pulled by samples that are already on the correct side.

import math

def logloss_gh(y, f):
    p = 1.0 / (1.0 + math.exp(-f))
    return p - y, p * (1.0 - p)      # gradient, hessian

The approximation is only valid near the current prediction. A leaf weight that moves $\hat y$ by a large amount invalidates the quadratic expansion, which is why shrinkage is applied to the tree’s contribution after the leaf values have been computed from exact derivatives: the objective decides the direction and magnitude, and the learning rate decides how much of it to trust. With a learning rate of 0.1, the effective step is a tenth of the Newton step, which keeps the expansion honest at the cost of more rounds.

Boundary conditions

A child with $H_j + \lambda = 0$ is degenerate, and implementations require a minimum sum of hessians per child so that a split cannot isolate a handful of saturated samples. The threshold is in hessian units, so under log loss it behaves like a weighted sample count: a node of near-certain predictions counts for almost nothing even if it holds many rows.

Non-smooth losses break the expansion outright. Absolute error has a constant gradient sign and zero curvature almost everywhere, so the second derivative carries no information and the formula degenerates; such losses are handled either with a different leaf-value rule or by smoothing. Ranking and survival objectives with censoring need their own $g$ and $h$ derived per observation, and an incorrect derivation produces a model that trains smoothly and predicts badly.

Multiclass problems fit one tree per class per round, each with its own $g$ and $h$ from the softmax Jacobian, and the per-class penalties are applied independently. The split structure differs between classes, which is why multiclass boosted models are not simply a vector-valued tree.

The most expensive part of the computation is unchanged by any of this: the per-feature sorted scan over $n$ rows. Binning the features makes the scan proportional to the number of bins instead of the number of distinct values, and it is the reason histogram split finding is the standard implementation choice for large boosted ensembles.