XGBoost

The regularised objective#

Chen & Guestrin (2016) frame boosting as additive training on a regularised objective. The model after K rounds is a sum of trees:

ŷ_i = SUM_{k=1..K} f_k(x_i) ,       f_k in F, the space of regression trees

L = SUM_i l(y_i, ŷ_i)  +  SUM_k Ω(f_k)

Ω(f) = γ T  +  (1/2) λ ||w||^2

• l — any twice-differentiable loss (squared error, logistic, ranking objectives)
• T — the number of leaves in tree f
• w ∈ R^T — the leaf output values, called leaf weights
• γ — the cost charged per additional leaf; gamma in the API
• λ — L2 penalty on leaf weights; reg_lambda in the API

The explicit Ω term is the substantive departure from Friedman (2001). Classical gradient boosting controls complexity through tree depth and shrinkage; XGBoost puts it in the objective, where it participates in the split decision itself.

Second-order expansion#

At round t, holding the previous t−1 trees fixed, take a second-order Taylor expansion of the loss around ŷ^(t−1):

L^(t)  ≈  SUM_i [ g_i f_t(x_i)  +  (1/2) h_i f_t(x_i)^2 ]  +  Ω(f_t)  +  const

g_i = ∂ l(y_i, ŷ) / ∂ŷ        evaluated at ŷ = ŷ_i^(t−1)      (gradient)
h_i = ∂² l(y_i, ŷ) / ∂ŷ²      evaluated at ŷ = ŷ_i^(t−1)      (hessian)

For squared error, g_i = 2(ŷ_i − y_i) and h_i = 2, which recovers "fit the next tree to the residuals" — the loop in the Developer section. For logistic loss, g_i = p_i − y_i and h_i = p_i(1 − p_i), so the hessian downweights confidently-classified points automatically.

Using h_i is what "second order" buys. Friedman's GBM uses only g_i and applies a separate line search for leaf values; XGBoost gets the step size analytically per leaf.

Optimal leaf weights and the split gain#

Fix the tree structure and let I_j be the set of training rows landing in leaf j. Write G_j = SUM_{i ∈ I_j} g_i and H_j = SUM_{i ∈ I_j} h_i. The objective becomes a sum of independent quadratics in w_j, so the minimiser is closed form:

w_j*  =  − G_j / ( H_j + λ )

L*    =  − (1/2) SUM_{j=1..T}  G_j^2 / ( H_j + λ )   +  γ T

L* scores a tree structure. The gain from splitting a leaf into left and right children follows directly:

Gain = (1/2) [  G_L^2/(H_L + λ)  +  G_R^2/(H_R + λ)  −  (G_L+G_R)^2/(H_L+H_R+λ)  ]  −  γ

Three consequences are worth naming.

• γ is a genuine threshold. A split whose gain does not exceed γ is not taken. This is pre-pruning built into the criterion, unlike CART's impurity decrease, which is always non-negative.
• λ shrinks leaf weights towards zero and, because it appears in the denominator, penalises leaves with small H_j more. Leaves supported by few or low-confidence rows get pulled harder.
• The gain can be negative. XGBoost grows to max_depth and then prunes bottom-up, removing splits with negative gain. A depth-first greedy stop would miss a strong split hiding behind a weak one.

Shrinkage and subsampling#

ŷ^(t) = ŷ^(t−1)  +  η · f_t(x)

η is the learning rate (eta, learning_rate). Friedman (2001) established that small η with many rounds beats large η with few, and the standard operating range is 0.01 to 0.1. The mechanism is regularisation by slow fitting: each tree contributes a small fraction, so the ensemble approaches the fit along a smoother path.

Friedman (2002) added row subsampling (subsample), sampling without replacement rather than the bootstrap used by bagging. XGBoost adds column subsampling per tree, per level and per split (colsample_bytree, colsample_bylevel, colsample_bynode), imported from random forests. Column subsampling is frequently the more effective of the two on wide tabular data.

Sparsity-aware split finding#

The Developer section shows NaN handled without imputation. The mechanism: at each split, XGBoost enumerates candidate thresholds twice — once sending all missing values left, once sending them right — and stores the better direction as that node's default direction.

Missing rows are excluded from the threshold enumeration entirely, so the cost is linear in the number of non-missing entries. On genuinely sparse data this yields the large speedups reported in the paper. The learned default direction also means "missingness" carries information through the model rather than being erased by an imputation step.

Approximate split finding#

Exact greedy split finding enumerates every distinct feature value, costing O(n d) per level after sorting. XGBoost's approximate algorithm proposes candidate split points from quantiles of the feature distribution, then aggregates gradient statistics into those buckets.

Because the second-order objective weights each row by h_i, the quantiles must be weighted by h_i too. The paper's weighted quantile sketch supports merge and prune operations with a provable error bound, which the standard unweighted sketches do not. Setting sketch_eps = ε yields roughly 1/ε candidate splits.

Modern practice defaults to tree_method="hist": bin each feature into a fixed number of bins (max_bin, default 256) once, then accumulate gradient histograms per node. Cost per level drops to O(n_bins · d) and the histogram of a child is obtained by subtracting a sibling's from the parent's.

exact greedy    O(n d)         per level, after a global pre-sort
histogram       O(n d)         to bin, then O(n_bins · d) per node
memory          O(n d)         compressed column blocks, cache-aware prefetch

The three implementations#

LightGBM (Ke et al., 2017) grows leaf-wise: it expands whichever leaf offers the largest gain, anywhere in the tree. That gives lower loss per leaf and a stronger tendency to overfit small datasets, so num_leaves must be controlled. GOSS keeps all large-gradient rows and subsamples small-gradient ones with a compensating weight. EFB bundles mutually exclusive sparse features into single columns.

CatBoost (Prokhorenkova et al., 2018) targets target leakage in categorical encoding, the exact failure demonstrated in feature engineering. Its ordered target statistics compute a category's encoding using only rows preceding it in a random permutation. Ordered boosting extends the same permutation trick to the gradient estimates themselves, removing the prediction shift that arises from computing gradients on the same rows used to fit the tree. Its oblivious trees — the same split condition at every node of a level — act as strong regularisation and make inference exceptionally fast.

Boosting theory#

Boosting predates gradient boosting. Schapire (1990) answered Kearns and Valiant's question of whether weak learnability implies strong learnability, in the affirmative. Freund & Schapire (1997) gave AdaBoost, with a training error bound decreasing exponentially in the number of rounds.

AdaBoost's resistance to overfitting was explained by Schapire et al. (1998) through the margin distribution: rounds after training error reaches zero continue to increase margins, and the generalisation bound depends on the margin distribution rather than on the number of rounds.

Friedman, Hastie & Tibshirani (2000) reinterpreted AdaBoost as forward stagewise additive modelling under exponential loss, which opened the door to arbitrary losses. Friedman (2001) then generalised it to gradient descent in function space — the framework everything above sits inside.

The empirical picture on tabular data remains stable. Grinsztajn, Oyallon & Varoquaux (2022) find tree ensembles still outperform deep learning on medium-sized tabular datasets, attributing it to rotation-invariance being the wrong inductive bias for tabular features, and to robustness against uninformative columns. Shwartz-Ziv & Armon (2022) reach the same conclusion and add that proposed deep tabular architectures often fail to reproduce outside their own papers' datasets.

Papers#

• Schapire, R. (1990). The Strength of Weak Learnability. Machine Learning 5(2).
• Freund, Y. & Schapire, R. (1997). A Decision-Theoretic Generalization of On-Line Learning. JCSS 55(1).
• Friedman, J., Hastie, T. & Tibshirani, R. (2000). Additive Logistic Regression: A Statistical View of Boosting. Annals of Statistics 28(2).
• Friedman, J. (2001). Greedy Function Approximation: A Gradient Boosting Machine. Annals of Statistics 29(5).
• Friedman, J. (2002). Stochastic Gradient Boosting. Computational Statistics and Data Analysis 38(4).
• Chen, T. & Guestrin, C. (2016). XGBoost: A Scalable Tree Boosting System. KDD — arxiv.org/abs/1603.02754
• Ke, G. et al. (2017). LightGBM: A Highly Efficient Gradient Boosting Decision Tree. NeurIPS.
• Prokhorenkova, L. et al. (2018). CatBoost: Unbiased Boosting with Categorical Features. NeurIPS — arxiv.org/abs/1706.09516
• Lundberg, S. et al. (2020). From Local Explanations to Global Understanding with Explainable AI for Trees. Nature Machine Intelligence 2.
• Grinsztajn, L., Oyallon, E. & Varoquaux, G. (2022). Why Do Tree-Based Models Still Outperform Deep Learning on Tabular Data? NeurIPS — arxiv.org/abs/2207.08815

What to learn next#

• Overfitting and underfitting — the U-shaped curve on this page, explained properly.
• Feature engineering — the columns you feed it matter more than the settings you tune.
• Model evaluation — choosing the number you early-stop on.