Newton Boosting and Second-Order Approximations

Plain gradient boosting fits each new tree to the direction the loss wants to move (the negative gradient) but has no sense of how far to move — it relies on a fixed or separately-tuned step size. Newton boosting, the approach behind XGBoost, also uses the curvature of the loss (how quickly the slope itself is changing) to size that step automatically, tree by tree, leaf by leaf.

The analogy: walking downhill with and without feeling the ground curve

Plain gradient descent is like walking downhill in fog, feeling only which way is steepest and taking a fixed-size step in that direction every time — on a gentle slope you undershoot, on a steep drop-off you might overshoot and stumble. Newton's method is like also feeling how quickly the slope itself is changing underfoot — if the ground is curving sharply, you know to take a smaller, more careful step; if it is nearly flat, you know you can stride further. That extra sense of curvature is the second derivative, and it lets you size each step correctly instead of guessing.

The maths: slope and curvature, per data point

For each training point, define the gradient $g_i = \partial L(y_i, \hat{y}_i)/\partial \hat{y}_i$ (how much the loss wants to move) and the Hessian $h_i = \partial^2 L(y_i, \hat{y}_i)/\partial \hat{y}_i^2$ (how quickly that want-to-move is itself changing). Newton boosting fits each new tree to approximately minimize

$$\sum_{i} \left[ g_i f(x_i) + \tfrac{1}{2} h_i f(x_i)^2 \right]$$

where $f(x_i)$ is the new tree's output for point $i$. In plain English: each point gets weighted by how curved the loss is around it, so points where the loss is very sensitive to small changes (high $h_i$) pull the fit harder, and the optimal value in a leaf is not just "the average gradient" but "the average gradient divided by the average curvature" —

$$w^{*}_{\text{leaf}} = -\frac{\sum_{i \in \text{leaf}} g_i}{\sum_{i \in \text{leaf}} h_i}$$

which is a direct, self-scaling step size baked into the tree-fitting itself, not a separately tuned learning rate.

Worked example 1: squared-error loss reduces to plain gradient boosting

For squared-error loss $L = \tfrac{1}{2}(y - \hat{y})^2$, the gradient is $g_i = \hat{y}_i - y_i$ and the Hessian is $h_i = 1$ (constant). Plugging into the leaf formula: $w^* = -\sum g_i / \sum 1 =$ the average residual — exactly what ordinary gradient boosting already does. Newton boosting only differs from plain gradient boosting when the Hessian is not constant, which happens for losses like log-loss (classification) or many custom objectives.

Worked example 2: log-loss, where curvature actually matters

For binary log-loss with predicted probability $p_i = \sigma(\hat{y}_i)$, the gradient is $g_i = p_i - y_i$ and the Hessian is $h_i = p_i(1-p_i)$. Take three points in a leaf with $p = 0.5, 0.9, 0.99$ and true labels $y = 1, 1, 1$. Gradients: $g = -0.5, -0.1, -0.01$. Hessians: $h = 0.25, 0.09, 0.0099$. Plain gradient boosting would treat all three residuals as directly comparable. Newton boosting computes $w^* = -(-0.5-0.1-0.01)/(0.25+0.09+0.0099) = 0.61/0.3499 \approx 1.74$ for the leaf — the confident point ($p=0.99$) has a tiny gradient and a tiny Hessian, so it barely influences the leaf value despite still being "wrong," while the uncertain point ($p=0.5$) dominates because both its gradient and its curvature are large. This is exactly the self-correcting sizing a fixed learning rate cannot replicate.

Try slowing or speeding the step size in the explorer above and watch it overshoot on steep curvature or crawl on flat curvature — that is exactly the miscalibration the Hessian term in Newton boosting corrects for automatically, tree by tree.

What this means in practice

This is why XGBoost, LightGBM, and CatBoost all require a loss function's gradient and Hessian to support a custom objective — the Hessian is not optional bookkeeping, it directly determines each leaf's fitted value. For losses with a constant or near-constant Hessian (like squared error), Newton boosting and plain gradient boosting behave almost identically; the gap opens up for classification losses and other curved objectives.