Skip to content
nonconvexcard

XGBoost: A Scalable Tree Boosting System

Tianqi Chen, Carlos Guestrin · 2016 · KDD

Classical MLgradient boostingtreessecond orderregularisationtabular
Read the paper

The problem

Gradient boosting used a first-order approximation and greedy split search that did not scale, and had no principled tree-complexity regularisation.

The contribution

A second-order expansion of the loss giving closed-form leaf values and split gains, plus explicit complexity regularisation and systems work for sparsity and out-of-core training.

What problem does this paper solve?

Making gradient boosting both more accurate and fast enough for large tabular datasets, which is where it remains the strongest method.

What mathematical objects are introduced?

The regularised objective at round tt, expanded to second order in the new tree hh:

L(t)≈∑i=1n[gih(xi)+12hih(xi)2]+γT+12λ∑j=1Twj2,\mathcal{L}^{(t)} \approx \sum_{i=1}^n\left[g_ih(x_i) + \tfrac12 h_ih(x_i)^2\right] + \gamma T + \tfrac12\lambda\sum_{j=1}^Tw_j^2 ,

with gi,hig_i,h_i the first and second derivatives of the loss at the current prediction, TT the number of leaves and wjw_j the leaf values.

What assumptions are made?

That the second-order expansion is adequate — true for the losses in use (squared, logistic), whose second derivatives are bounded and well behaved.

What equations matter?

Because the objective is a sum of independent per-leaf quadratics, the optimal leaf value and the resulting objective are closed-form:

wj⋆=−∑i∈Ijgi∑i∈Ijhi+λ,L⋆=−12∑j=1T(∑i∈Ijgi)2∑i∈Ijhi+λ+γT.w_j^\star = -\frac{\sum_{i\in I_j}g_i}{\sum_{i\in I_j}h_i + \lambda}, \qquad \mathcal{L}^\star = -\frac12\sum_{j=1}^T\frac{\big(\sum_{i\in I_j}g_i\big)^2}{\sum_{i\in I_j}h_i+\lambda} + \gamma T .

The split gain is the difference of this quantity before and after a split, which is what the greedy search maximises. The γT\gamma T term means a split with insufficient gain is rejected — pruning is built into the objective rather than being a post-hoc step.

What theorem or result is important?

No theorem; the derivation above is the mathematical content. Its relation to first-order gradient boosting is exactly that of Newton's method to gradient descent.

What proof techniques are used?

Per-leaf minimisation of a quadratic; the algebra is elementary and complete.

What prior mathematics is required?

Second-order Taylor expansion; minimisation of a one-dimensional quadratic; the functional-gradient view of boosting.

Limitations

Second-order expansion requires a twice-differentiable loss. Many hyperparameters with substantial interactions. And the method inherits boosting's general lack of a generalisation theory — margin arguments explain the resistance to overfitting only partially.

Why it mattered

It is, with LightGBM and CatBoost, the default method for tabular prediction, and it remains competitive with or superior to deep learning on that data type — a standing reminder that the dominance of neural networks is domain-specific.