Why XGBoost Uses Second-Order Taylor Approximation

XGBoost employs a second-order Taylor expansion of the loss function because it transforms the tree learning problem into a form where optimal leaf weights and split gains can be computed analytically in closed form. This Newton-type approach captures curvature information through the Hessian, enabling more informed updates than first-order gradient descent alone. The resulting objective becomes a quadratic function of leaf scores, parameterized entirely by the gradient $g_i$ and Hessian $h_i$ of each training instance—quantities that serve as sufficient statistics for the entire boosting step.

The Taylor Expansion in Optimization

For a twice-differentiable function $f$, the second-order Taylor expansion around point $x$ is:

$$f(x + \Delta x) \approx f(x) + f’(x)\Delta x + \frac{1}{2}f”(x)(\Delta x)^2$$

In numerical optimization, Newton’s method uses this quadratic approximation to find the step $\Delta x$ that minimizes the approximation directly:

$$\Delta x^* = -\frac{f’(x)}{f”(x)}$$

This contrasts with steepest descent, which uses only $f’(x)$ and a manually tuned learning rate. Newton’s method converges quadratically near the optimum under standard regularity conditions—a property first-order methods cannot match without line search or momentum heuristics.

Applying the Expansion to Gradient Boosting

In gradient boosting with trees, at iteration $t$ we have an ensemble prediction $\hat{y}_i^{(t-1)}$ for each instance $i$, and we seek to add a new tree $f_t$ to minimize:

$$\mathcal{L}^{(t)} = \sum_{i=1}^{n} L(y_i, \hat{y}_i^{(t-1)} + f_t(\mathbf{x}_i)) + \Omega(f_t)$$

The loss term is non-linear in $f_t(\mathbf{x}_i)$. Following Friedman et al. (2000), we expand $L$ around the current prediction $\hat{y}_i^{(t-1)}$, treating $f_t(\mathbf{x}_i)$ as the perturbation $\Delta x$:

$$L(y_i, \hat{y}_i^{(t-1)} + f_t(\mathbf{x}_i)) \approx L(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(\mathbf{x}_i) + \frac{1}{2}h_i [f_t(\mathbf{x}_i)]^2$$

where:

$$g_i = \frac{\partial L(y_i, \hat{y}_i)}{\partial \hat{y}i}\bigg|{\hat{y}_i=\hat{y}_i^{(t-1)}}$$

$$h_i = \frac{\partial^2 L(y_i, \hat{y}_i)}{\partial \hat{y}i^2}\bigg|{\hat{y}_i=\hat{y}_i^{(t-1)}}$$

The Simplified Objective at Step $t$

Removing the constant term $L(y_i, \hat{y}_i^{(t-1)})$ (which doesn’t depend on $f_t$), we obtain:

$$\tilde{\mathcal{L}}^{(t)} = \sum_{i=1}^{n}\left[g_i f_t(\mathbf{x}_i) + \frac{1}{2}h_i [f_t(\mathbf{x}_i)]^2\right] + \Omega(f_t)$$

This is the core objective that XGBoost minimizes at each boosting round, as described in the Chen & Guestrin (2016) XGBoost paper. The regularization term for a tree with $T$ leaves and leaf weight vector $\mathbf{w}$ is:

$$\Omega(f_t) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2$$

Gradients and Hessians as Sufficient Statistics

A crucial insight: once $g_i$ and $h_i$ are computed for each training instance, the original labels $y_i$ and predictions $\hat{y}_i^{(t-1)}$ are no longer needed. The entire learning problem for tree $f_t$ reduces to fitting a weighted quadratic objective where:

• Each instance contributes a linear term $g_i f_t(\mathbf{x}_i)$
• Each instance contributes a quadratic penalty $\frac{1}{2}h_i [f_t(\mathbf{x}_i)]^2$
• The Hessian $h_i$ acts as the weight of the quadratic term

For squared error loss $L = \frac{1}{2}(y - \hat{y})^2$, we have $g_i = \hat{y}_i^{(t-1)} - y_i$ (negative residual) and $h_i = 1$ (constant curvature). For logistic loss $L = y\log(1+e^{-\hat{y}}) + (1-y)\log(1+e^{\hat{y}})$, we get $g_i = \sigma(\hat{y}_i^{(t-1)}) - y_i$ and $h_i = \sigma(\hat{y}_i^{(t-1)})(1-\sigma(\hat{y}_i^{(t-1)}))$—a non-constant Hessian that varies with prediction confidence.

Comparison with First-Order Boosting

Traditional gradient boosting (first-order) approximates the objective as:

$$\tilde{\mathcal{L}}^{(t)}{\text{first}} = \sum{i=1}^{n} g_i f_t(\mathbf{x}_i) + \Omega(f_t)$$

Without the Hessian term, there’s no quadratic penalty on leaf scores. The tree must rely on a global learning rate $\eta$ to prevent overshooting, and leaf weights are fitted by line search or separate regression rather than analytically. XGBoost’s second-order formulation provides:

Faster convergence: Newton’s method uses local curvature to scale the step size automatically. In regions where the loss is flat (small $h_i$), larger steps are taken; where the loss is steep (large $h_i$), steps are naturally dampened. First-order methods apply a uniform learning rate regardless of local geometry.

Unified leaf weight computation: With the quadratic approximation, optimal leaf weights have a closed form (derived below). First-order methods require solving a separate optimization problem per leaf or using heuristics like the average gradient.

Principled regularization: The Hessian $h_i$ naturally weights each instance’s contribution to leaf scores. Instances with uncertain predictions (e.g., $p \approx 0.5$ in logistic regression, where $h_i \approx 0.25$) contribute moderate Hessians, while confident predictions ($p \approx 0$ or $p \approx 1$, where $h_i \approx 0$) are effectively downweighted. This connects to Fisher scoring in generalized linear models.

When Second-Order Makes a Large Difference

Classification with log loss exhibits significant variation in Hessian values across instances. Near the decision boundary ($p \approx 0.5$), the Hessian is large, indicating high curvature and sensitivity to prediction changes. Far from the boundary, the Hessian approaches zero, signaling that those instances are already well-classified. A first-order method would treat all instances equally, potentially wasting model capacity on already-correct instances. The second-order weighting naturally focuses the tree on boundary instances, often yielding faster convergence and better calibration with fewer trees.

Imbalanced classification amplifies this effect. With few positive examples, their gradients are large in magnitude but their Hessians may be small if they’re misclassified with high confidence. The second-order objective balances gradient magnitude with curvature, preventing the model from being dominated by numerous negative examples with moderate gradients.

When Second-Order Makes Less Difference

With squared error loss, $h_i = 1$ for all instances—the curvature is constant. The second-order objective reduces to:

$$\sum_{i=1}^{n}\left[g_i f_t(\mathbf{x}_i) + \frac{1}{2}[f_t(\mathbf{x}_i)]^2\right] + \Omega(f_t)$$

This is effectively equivalent to fitting residuals with an $L_2$ penalty. The Hessian provides no instance-specific information, so the advantage over first-order methods comes primarily from the analytical leaf weight formula rather than curvature adaptation. In practice, the gap between first-order and second-order boosting for regression is narrower than for classification.

Deriving the Optimal Leaf Weight

For a fixed tree structure with leaf $j$ containing instance set $I_j$, the contribution to the approximate objective is:

$$\tilde{\mathcal{L}}j = \sum{i \in I_j} \left[g_i w_j + \frac{1}{2}h_i w_j^2\right] + \frac{1}{2}\lambda w_j^2$$

$$= w_j \sum_{i \in I_j} g_i + \frac{1}{2}w_j^2 \left(\sum_{i \in I_j} h_i + \lambda\right)$$

Define $G_j = \sum_{i \in I_j} g_i$ and $H_j = \sum_{i \in I_j} h_i$. Then:

$$\tilde{\mathcal{L}}_j = G_j w_j + \frac{1}{2}(H_j + \lambda)w_j^2$$

This is a simple quadratic in $w_j$. Setting the derivative to zero:

$$\frac{\partial \tilde{\mathcal{L}}_j}{\partial w_j} = G_j + (H_j + \lambda)w_j = 0$$

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

Substituting back gives the optimal objective value for leaf $j$:

$$\tilde{\mathcal{L}}_j^* = -\frac{1}{2}\frac{G_j^2}{H_j + \lambda}$$

This closed-form solution is only possible because of the second-order expansion. Without the Hessian term, $H_j$ would be zero (or undefined), and we’d have a linear objective requiring constrained optimization or a separate line search.

The Gain Formula for Split Finding

When evaluating a candidate split that divides leaf $j$ into left child $L$ and right child $R$, the reduction in the objective (the “gain”) is:

$$\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$$

where $G_L + G_R = G_j$ and $H_L + H_R = H_j$ for the parent node. The term $\gamma$ is the complexity cost of adding a new leaf. This formula:

• Penalizes splits where the sum of child scores barely exceeds the parent score
• Naturally handles instance-weighted splits through $H_L$ and $H_R$
• Enables exact greedy or approximate split finding without evaluating loss on candidate leaf values

The factor $\frac{1}{2}$ comes from the Taylor expansion and cancels out when comparing gains, though it’s retained for consistency with the original objective scale.

Connection to Newton’s Method in Optimization

The general Newton update for minimizing a function $F(\mathbf{w})$ is:

$$\mathbf{w}^{(t)} = \mathbf{w}^{(t-1)} - [\nabla^2 F(\mathbf{w}^{(t-1)})]^{-1} \nabla F(\mathbf{w}^{(t-1)})$$

In functional gradient boosting, the “parameter” is the prediction function $\hat{y}(\mathbf{x})$, and the Newton step in function space is:

$$f_t(\mathbf{x}) = -\frac{\nabla L(y, \hat{y}^{(t-1)}(\mathbf{x}))}{\nabla^2 L(y, \hat{y}^{(t-1)}(\mathbf{x}))}$$

XGBoost’s leaf weight formula $w_j^* = -G_j/(H_j + \lambda)$ is exactly the Newton step aggregated over all instances in leaf $j$, with $\lambda$ providing Levenberg-Marquardt-style damping for numerical stability. This connects XGBoost to the broader literature on Newton-boosting and stagewise additive modeling.

The per-instance Newton step $-g_i/h_i$ would be the optimal update if we could fit a completely unregularized model. By constraining the update to a tree structure and adding regularization, XGBoost approximates the Newton direction with a piecewise-constant function, balancing fidelity to the second-order update against model complexity.

Practical Considerations

The second-order approximation assumes the loss is twice differentiable and that higher-order terms are negligible. For losses like absolute error or quantile loss, the Hessian is zero almost everywhere and undefined at the origin. XGBoost handles this by computing a smoothed Hessian or falling back to first-order methods. The quality of the approximation also degrades if $f_t(\mathbf{x}_i)$ is large relative to the curvature of the loss—a concern mitigated by the shrinkage parameter $\eta$ (learning rate) applied to leaf weights after fitting:

$$\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + \eta , f_t(\mathbf{x}_i)$$

Small $\eta$ (typically 0.1–0.3) ensures that the Taylor approximation remains accurate across boosting rounds by keeping the step size small.

FAQ

Why not use third-order or higher expansions? Third-order terms would introduce cubic dependencies on $f_t$, breaking the quadratic form that enables closed-form leaf weights. The resulting objective would require iterative optimization per leaf, defeating the computational efficiency that makes XGBoost practical. Newton’s method already achieves quadratic convergence under standard conditions; higher-order methods offer diminishing returns at disproportionate computational cost.

Does second-order boosting always outperform first-order? No. For losses with constant Hessian (squared error), the practical difference is often small. For losses with unbounded or poorly behaved second derivatives, first-order methods with appropriate learning rate scheduling can be more stable. The advantage of second-order methods is most pronounced when the Hessian carries meaningful instance-level information about prediction uncertainty.

How does $\lambda$ relate to the Newton interpretation? The regularization parameter $\lambda$ adds a constant to the denominator $H_j + \lambda$, acting as a trust-region mechanism. In classical Newton’s method, when the Hessian is near-singular, a damping term is added to ensure the update remains well-conditioned. XGBoost’s $\lambda$ serves this role while also providing $L_2$ regularization on leaf weights.