6.1 Overview and core innovations
XGBoost (eXtreme Gradient Boosting) is a scalable end-to-end tree boosting system introduced by Tianqi Chen and Carlos Guestrin at ACM SIGKDD in 2016 (KDD 2016, paper XGBoost: A Scalable Tree Boosting System). It reworks gradient boosted decision trees (GBDT) on both the algorithmic and the engineering side, combining second-order Taylor expansion, an explicitly regularized objective, weighted quantile sketches, sparsity-aware split finding and system-level optimizations (block structure, cache awareness, out-of-core computation) to break new ground in both speed and accuracy.
XGBoost’s core innovations come down to five items:
- A regularized learning objective: an explicit penalty on tree complexity (leaf-count penalty plus an L2 penalty on leaf weights in the paper; the implementation also offers an L1 penalty) is folded into the tree-learning objective rather than applied as post-processing.
- Second-order Taylor expansion: the second derivative (Hessian) of the loss drives a Newton-type optimization that converges faster and more stably than the first-order-only GBDT.
- Weighted quantile sketch: an efficient search for candidate split points on large data, using the second derivative as the sample weight. The paper gives a distributed weighted quantile sketch algorithm that supports merge and prune operations with a provable error guarantee (proved in the appendix).
- Sparsity-aware split finding: missing-value handling is built into tree learning — the default direction for missing values is learned, so no imputation is needed.
- System-level optimization: column blocks, cache-aware prefetching and out-of-core computation squeeze the hardware hard.
6.2 How it differs from GBDT
The table compares XGBoost with classic GBDT (Friedman 2001) along three axes: algorithm, regularization and systems.
| Feature | GBDT (Friedman 2001) | XGBoost (Chen & Guestrin 2016) |
|---|---|---|
| Optimization order | First derivative (gradient) | First + second derivative (gradient + Hessian) |
| Objective regularization | No explicit regularization | L1 + L2 + tree-complexity penalty ($\gamma T$) |
| Split algorithm | Exact greedy (pre-sorted) | Exact greedy + approximation + weighted quantile sketch + histograms |
| Missing values | Needs preprocessing (mean/median imputation) | Sparsity-aware split finding; default direction learned |
| Column sampling | Not in the original (scikit-learn supports per-split feature sampling via max_features) | Three levels: per tree, per level, per node |
| Row sampling | Supported (subsampling) | Supported (subsampling) |
| Parallelization | No intra-tree parallelism | Feature-level parallelism, column blocks, cache awareness |
| Out-of-core computation | Not supported | Supported; compressed, blocked storage and reading |
| Distributed training | Not supported | Supported (AllReduce-based communication, implemented by the Rabit library in early versions) |
| Custom objectives | The framework allows any differentiable loss, but common implementations (scikit-learn, for example) ship only built-in losses | Supported (supply the first and second derivatives) |
The key point: XGBoost isn’t a disruptive replacement for GBDT. It adds second-order information and explicit regularization on top of GBDT’s first-order framework, backed by systems engineering, which takes tree boosting to a new level in both accuracy and efficiency.
6.3 Deriving the objective in full
6.3.1 The raw objective
At iteration $t$, XGBoost’s objective is
$$ \mathrm{Obj}^{(t)} = \sum_{i=1}^{n} L\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t) $$Notation:
| Symbol | Meaning |
|---|---|
| $n$ | Number of training samples |
| $y_i$ | True label of sample $i$ |
| $\hat{y}_i^{(t-1)}$ | Model prediction accumulated over the first $t-1$ rounds |
| $f_t(x_i)$ | Output of the new tree at round $t$ for sample $i$ (the weight $w_{q(x_i)}$ of the leaf it falls into) |
| $L(\cdot, \cdot)$ | A differentiable loss (MSE, log loss) |
| $\Omega(f_t)$ | Regularization penalty on the $t$-th tree |
6.3.2 Second-order Taylor expansion
One of XGBoost’s core ideas is to approximate the loss with a second-order Taylor expansion. Let $x = \hat{y}_i^{(t-1)}$ and $\Delta x = f_t(x_i)$. By Taylor’s formula,
$$ f(x + \Delta x) \approx f(x) + f'(x)\Delta x + \frac{1}{2}f''(x)(\Delta x)^2 $$Expanding $L(y_i, \hat{y}_i^{(t-1)} + f_t(x_i))$ around $\hat{y}_i^{(t-1)}$:
$$ \mathrm{Obj}^{(t)} \approx \sum_{i=1}^{n}\left[ L(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t) $$where the first derivative $g_i$ and the second derivative (Hessian) $h_i$ are
$$ g_i = \partial_{\hat{y}^{(t-1)}} L(y_i, \hat{y}_i^{(t-1)}) = \frac{\partial L(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}} $$$$ h_i = \partial^2_{\hat{y}^{(t-1)}} L(y_i, \hat{y}_i^{(t-1)}) = \frac{\partial^2 L(y_i, \hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2} $$Notation:
| Symbol | Meaning |
|---|---|
| $g_i$ | First derivative of the loss at sample $i$’s current prediction (its negation $-g_i$ is the pseudo-residual in GBDT) |
| $h_i$ | Second derivative (curvature) at sample $i$’s current prediction |
Since $\hat{y}_i^{(t-1)}$ is fixed after the first $t-1$ rounds, $L(y_i, \hat{y}_i^{(t-1)})$ is a constant that doesn’t affect the optimization and can be dropped. That leaves
$$ \mathrm{Obj}^{(t)} \approx \sum_{i=1}^{n}\left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t) $$Why is second-order better than first-order alone?
- First-order methods (classic GBDT) use the gradient (pseudo-residual) to determine tree structure — gradient descent in function space. The step size has to come from the learning rate $\eta$ and an extra line search (Friedman’s GBDT runs a one-dimensional line search in each leaf; see Gradient Boosting Machine), and the tree structure itself uses no curvature information.
- Second-order methods (Newton boosting) use the curvature in $h_i$ to adapt the step automatically: where the loss curves sharply ($h_i$ large) the update shrinks, and where it’s flat ($h_i$ small) a larger step is allowed. Each leaf’s update $-\frac{G_j}{H_j+\lambda}$ is exactly a one-step Newton-Raphson update with L2 regularization, which usually converges faster and more stably.
- Statistically, the second-order expansion is a local quadratic approximation of the loss, which characterizes the optimal update direction more precisely.
6.3.3 Regularizing the tree structure
XGBoost defines an explicit penalty on each tree’s complexity:
$$ \Omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2 + \alpha \sum_{j=1}^{T} \lvert w_j \rvert $$Notation:
| Symbol | Meaning |
|---|---|
| $T$ | Number of leaves in the tree |
| $w_j$ | Output weight of the $j$-th leaf |
$\gamma$ (gamma / min_split_loss) | Leaf-count penalty coefficient; larger values favor simpler trees |
$\lambda$ (lambda / reg_lambda) | L2 regularization coefficient, penalizing large weights (default 1) |
$\alpha$ (alpha / reg_alpha) | L1 regularization coefficient, producing sparse weights (default 0) |
The $\gamma T$ term penalizes the number of leaves and pushes the model toward simpler structures; $\frac{1}{2}\lambda \sum_j w_j^2$ is the L2 penalty that smooths leaf outputs; $\alpha \sum_j \lvert w_j \rvert$ is the L1 penalty, which can drive some leaf weights to exactly 0.
Paper versus implementation The original paper’s penalty is only $\gamma T + \frac{1}{2}\lambda \lVert w \rVert^2$; the L1 term $\alpha$ is a parameter the XGBoost implementation adds (
alpha/reg_alpha). The derivations in Sections 6.3.4–6.3.6 match the paper and take $\alpha = 0$; the $\alpha > 0$ result appears at the end of Section 6.3.5.
6.3.4 Rewriting the objective by leaf
Group samples by leaf. Let $I_j = \{i \mid q(x_i) = j\}$ be the set of sample indices falling into leaf $j$, where $q(x)$ is the tree structure function mapping a sample to a leaf index, so $f_t(x_i) = w_{q(x_i)}$. With $\alpha = 0$, the objective can be rewritten as
$$ \mathrm{Obj}^{(t)} = \sum_{j=1}^{T}\left[\left(\sum_{i \in I_j} g_i\right)w_j + \frac{1}{2}\left(\sum_{i \in I_j} h_i + \lambda\right)w_j^2\right] + \gamma T $$Define the gradient statistics for leaf $j$:
$$ G_j = \sum_{i \in I_j} g_i, \quad H_j = \sum_{i \in I_j} h_i $$The objective then takes a compact quadratic form:
$$ \mathrm{Obj}^{(t)} = \sum_{j=1}^{T}\left[ G_j w_j + \frac{1}{2}(H_j + \lambda)w_j^2 \right] + \gamma T $$6.3.5 Deriving the optimal leaf weight
For each leaf $j$, the objective is a quadratic in $w_j$:
$$ \mathcal{L}_j(w_j) = G_j w_j + \frac{1}{2}(H_j + \lambda)w_j^2 $$Differentiate with respect to $w_j$ and set it to zero:
$$ \frac{\partial \mathcal{L}_j}{\partial w_j} = G_j + (H_j + \lambda)w_j = 0 $$Solving gives the optimal leaf weight in closed form:
$$ \boxed{w_j^* = -\frac{G_j}{H_j + \lambda}} $$Substituting $w_j^*$ back gives the optimal structure score:
$$ \boxed{\mathrm{Obj}^* = -\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j + \lambda} + \gamma T} $$Notation:
| Symbol | Meaning |
|---|---|
| $w_j^*$ | Optimal output weight of leaf $j$ |
| $\mathrm{Obj}^*$ | Optimal objective value for a given tree structure |
| $G_j$ | Sum of first derivatives over the samples in leaf $j$ |
| $H_j$ | Sum of second derivatives over the samples in leaf $j$ |
What the structure score means:
- $\frac{G_j^2}{H_j + \lambda}$ measures how much leaf $j$ contributes to lowering the overall loss: the larger it is, the smaller $-\frac{1}{2}\frac{G_j^2}{H_j+\lambda}$ is, and the more that leaf reduces the loss.
- $\gamma T$ penalizes the leaf count and guards against overfitting. As $T$ grows, the penalty grows linearly.
- $\mathrm{Obj}^*$ is an approximation of the loss, and the smaller it is the better the structure (the paper’s own words: “the smaller the score is, the better the structure is”). It plays a role like impurity in a decision tree, scoring structures; when searching for a split, the algorithm picks the one that drops $\mathrm{Obj}^*$ the most — the split with the largest gain, as in the next section.
The optimal leaf weight with L1 regularization ($\alpha > 0$): now each leaf minimizes $G_j w_j + \frac{1}{2}(H_j+\lambda) w_j^2 + \alpha \lvert w_j \rvert$. Solving the three cases $w_j>0$, $w_j<0$ and $w_j=0$ gives a soft-threshold form:
$$ w_j^* = -\frac{\operatorname{sign}(G_j)\max\left(\lvert G_j \rvert - \alpha,\ 0\right)}{H_j + \lambda} $$So when $\lvert G_j \rvert \le \alpha$ the leaf weight is exactly 0, which is why L1 produces sparse leaf weights. Substituting back, that leaf’s optimal value is $-\frac{1}{2}\frac{\left(\max(\lvert G_j \rvert - \alpha, 0)\right)^2}{H_j+\lambda}$, i.e. every $G^2$ in the formulas below becomes $\left(\max(\lvert G \rvert - \alpha, 0)\right)^2$.
6.3.6 Deriving the split gain
Splitting a leaf produces a left subtree $L$ and a right subtree $R$. The structure score before the split is
$$ \mathrm{Obj}_{\text{before}} = -\frac{1}{2}\frac{(G_L + G_R)^2}{H_L + H_R + \lambda} + \gamma $$and after the split:
$$ \mathrm{Obj}_{\text{after}} = -\frac{1}{2}\left(\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda}\right) + 2\gamma $$The gain from splitting is the objective before minus the objective after:
$$ \boxed{\mathrm{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} $$Notation:
| Symbol | Meaning |
|---|---|
| $G_L = \sum_{i \in I_L} g_i$ | Sum of gradients over the left subtree |
| $H_L = \sum_{i \in I_L} h_i$ | Sum of Hessians over the left subtree |
| $G_R = \sum_{i \in I_R} g_i$ | Sum of gradients over the right subtree |
| $H_R = \sum_{i \in I_R} h_i$ | Sum of Hessians over the right subtree |
| $\gamma$ | Complexity penalty: a split must reduce the loss by at least $\gamma$ to be allowed |
Reading the gain formula:
- The bracketed term measures the “purity” of the two subtrees after splitting: if the split separates positive- and negative-gradient samples well, then $\frac{G_L^2}{H_L+\lambda}$ and $\frac{G_R^2}{H_R+\lambda}$ are both large.
- The last term, $\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}$, is the baseline from before the split.
- $-\gamma$ is the complexity penalty: one more leaf costs $\gamma$, so the split is worth keeping only when $\mathrm{Gain} > 0$ (the loss must drop by more than $\gamma$). In the XGBoost implementation the
gammaparameter (aliasmin_split_loss, default 0) is this $\gamma$; after the tree is grown, thepruneupdater removes splits whose loss reduction is belowmin_split_loss(see the official Tree Methods docs and theupdaterparameter), so $\gamma$ also acts as post-pruning.
What min_child_weight means: the min_child_weight parameter (default 1) is a lower bound on $H = \sum_{i} h_i$ in a child, and a split that would produce a child below it is abandoned. You can think of $h_i$ as a sample’s “weight” in the second-order approximation: for squared loss $\frac{1}{2}(y-\hat{y})^2$, $h_i = 1$, so the bound becomes a minimum child sample count; for binary log loss, $h_i = p_i(1-p_i) \le \frac{1}{4}$, so the more confident the model is on a sample ($p_i$ near 0 or 1) the smaller the $h_i$ it contributes, and the harder it is to keep splitting nodes containing such samples.
Versus information gain: traditional decision trees use information gain or Gini impurity, which are based on label distributions. XGBoost’s gain is based on the gradient statistics $G_j$ and $H_j$, so it directly optimizes the reduction in the loss, regularization included.
6.4 The split gain: a worked example
The gain formula is derived above. To make it concrete, take a numerical example: a leaf holds 10 samples with $G_{\text{parent}} = 5.0$, $H_{\text{parent}} = 8.0$, $\lambda = 1.0$, $\gamma = 0.1$. After splitting, the left subtree has $G_L = 4.0, H_L = 3.0$ and the right has $G_R = 1.0, H_R = 5.0$. Then
$$ \mathrm{Gain} = \frac{1}{2}\left[\frac{16}{3+1} + \frac{1}{5+1} - \frac{25}{8+1}\right] - 0.1 \approx \frac{1}{2}\left[4 + 0.167 - 2.778\right] - 0.1 \approx 0.594 > 0 $$The gain is positive, so the split is allowed. The optimal weights of the two leaves are $w_L^* = -\frac{4}{3+1} = -1$ and $w_R^* = -\frac{1}{5+1} \approx -0.167$; without the split, the parent weight would be $-\frac{5}{8+1} \approx -0.556$.
6.5 Split finding: exact greedy, approximation, weighted quantile sketch
6.5.1 Exact greedy
The exact greedy algorithm enumerates every possible split point on every feature and takes the one with the largest gain. It suits smaller datasets that fit entirely in memory and where exact split points are wanted; in recent XGBoost practice, hist is the preferred method for most large-scale work.
Pseudocode:
- Input: the current node’s instance set $I$, feature dimension $d$
- Initialize: $\mathit{score} \leftarrow 0$, $G \leftarrow \sum_{i \in I} g_i$, $H \leftarrow \sum_{i \in I} h_i$
- For each feature $k = 1, 2, \dots, d$:
- Initialize: $G_L \leftarrow 0$, $H_L \leftarrow 0$
- Sort the samples in $I$ ascending by feature value $x_{jk}$
- For each sample $j$ in sorted order:
- $G_L \leftarrow G_L + g_j$, $H_L \leftarrow H_L + h_j$
- $G_R \leftarrow G - G_L$, $H_R \leftarrow H - H_L$
- $\mathit{score} \leftarrow \max\left(\mathit{score},\ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{G^2}{H+\lambda}\right)$
- Output: the split point with the largest $\mathit{score}$ (here $\mathit{score}$ is $2(\mathrm{Gain}+\gamma)$; the constant factor and $\gamma$ don’t affect the comparison)
Complexity: if every node re-sorts, a single node costs about $O(d\, n \log n)$ ($n$ samples in the node, $d$ features). XGBoost instead sorts each column once before training and stores it in a column block (see 6.7.2), after which each level only needs a linear scan. The paper’s overall complexity: with $K$ trees, maximum depth $d_{\max}$ and $\lVert \mathbf{x} \rVert_0$ non-missing entries in the training data, the original sparsity-aware exact algorithm costs $O(K d_{\max} \lVert \mathbf{x} \rVert_0 \log n)$, which drops to $O(K d_{\max} \lVert \mathbf{x} \rVert_0 + \lVert \mathbf{x} \rVert_0 \log n)$ with column blocks, where $O(\lVert \mathbf{x} \rVert_0 \log n)$ is the one-time, amortizable pre-sorting cost.
6.5.2 Approximation and the weighted quantile sketch
Exact greedy is infeasible on large data. XGBoost’s approximate algorithm has two stages:
Stage one: proposal
- Propose candidate split points based on feature quantiles.
- Global strategy: propose all candidates once when tree building starts, shared across all levels.
- Local strategy: re-propose candidates after each split; more precise but more expensive.
Stage two: aggregation and selection
- Bin the continuous feature by candidate points.
- Aggregate the gradient statistics $G$ and $H$ within each bin.
- Pick the largest gain among the candidates.
| Strategy | When candidates are proposed | Number of candidates | Accuracy | Cost |
|---|---|---|---|---|
| Global | Once, before tree building | More | Slightly lower | Lower |
| Local | After every split | Fewer | Higher | Higher |
Experiments showed that on the Higgs 10M dataset the local strategy matched the global strategy’s accuracy with fewer candidate points.
Weighted quantile sketch: candidate split points can’t simply be equal-frequency quantiles, because each sample contributes differently to the loss. XGBoost weights by the second derivative $h_i$ and defines a weighted rank function.
Write the multiset of values and second derivatives for feature $k$ as $\mathcal{D}_k = \{(x_{1k}, h_1), (x_{2k}, h_2), \dots, (x_{nk}, h_n)\}$ and define the weighted rank function
$$ r_k(z) = \frac{1}{\sum_{(x,h) \in \mathcal{D}_k} h} \sum_{(x,h) \in \mathcal{D}_k,\ x < z} h $$which is the fraction of total Hessian weight carried by samples whose feature-$k$ value is below $z$. The goal is to find candidate points $\{s_{k1}, s_{k2}, \dots, s_{kl}\}$ (with $s_{k1} = \min_i x_{ik}$ and $s_{kl} = \max_i x_{ik}$) such that adjacent points differ in weighted rank by less than $\epsilon$:
$$ \left\lvert r_k(s_{k,j}) - r_k(s_{k,j+1}) \right\rvert < \epsilon $$where $\epsilon$ is the approximation factor, yielding roughly $1/\epsilon$ candidates. That $h_i$ is the right weight follows from completing the square in the objective:
$$ \sum_{i=1}^{n}\left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] = \sum_{i=1}^{n} \frac{1}{2}h_i\left(f_t(x_i) + \frac{g_i}{h_i}\right)^2 - \sum_{i=1}^{n}\frac{g_i^2}{2h_i} $$The last term on the right doesn’t involve $f_t$, so the round-$t$ objective is equivalent to a weighted squared loss with weights $h_i$ and regression labels $-g_i/h_i$. Samples with large Hessians matter more to the loss, so split points should be denser around them.
A sign error in the paper The paper writes this expansion with $\left(f_t(x_i) - g_i/h_i\right)^2$ and label $g_i/h_i$, which is wrong. Expanding verifies the correct form is $+g_i/h_i$, with label $-g_i/h_i$ (the direction of a one-step Newton update).
6.5.3 Histogram optimization and the three tree_method options
Building on the approximation, XGBoost adds histograms:
- Bin each feature’s continuous values into a discrete histogram.
- Compute gradient statistics at bin boundaries rather than at every unique value.
- Histogram aggregation parallelizes well and suits GPU acceleration.
Parameters: tree_method='hist' enables histogram optimization, and max_bin caps the number of bins (default 256, used only by hist / approx).
XGBoost has three tree-building methods, distinguished as follows (per the official Tree Methods docs):
tree_method | Where candidate split points come from | Characteristics |
|---|---|---|
exact | Enumerates every value in the data (6.5.1) | Most precise but slowest; no out-of-core or distributed training, no categorical support, no lossguide growth |
approx | Rebuilds a sketch on all samples before each tree, weighted by the Hessian (the weighted quantile sketch of 6.5.2) | Candidates refresh per tree; sometimes more accurate on objectives where the Hessian isn’t constant, but slower than hist |
hist | Builds the sketch once before training, using only the user-supplied sample weights and not the Hessian; every node’s histogram then reuses that global binning | Fastest; auto (the default since 2.0) is the same as hist |
For objectives such as reg:squarederror where the Hessian is constant, the weighted sketch is no different from plain quantiles and hist should be preferred. The docs also note that in most cases hist with a larger max_bin matches or beats approx in accuracy. Both hist and approx support grow_policy='lossguide' (grow the leaf with the largest loss reduction, together with max_leaves, similar to LightGBM’s leaf-wise growth; see LightGBM).
6.6 Sparsity-aware split finding (missing values)
Sparsity is everywhere in real data: missing values, frequent zeros (statistical sparsity), and feature-engineering artifacts such as the many zeros from one-hot encoding. Conventional approaches need preprocessing (mean imputation, say), which can introduce bias. XGBoost’s sparsity-aware split finding builds missing-value handling into tree learning.
The idea: learning the default direction
XGBoost attaches a default direction to each tree node. When a sample’s value on the splitting feature is missing, it goes that way. Crucially, the default direction isn’t preset — it’s learned from the data.
For each candidate split, the algorithm does the following:
- Compute the potential split using only samples with non-missing values.
- Enumerate both directions for the missing samples:
- all missing values go left
- all missing values go right
- Compute the gain in both cases and pick the better direction as the default.
Pseudocode:
- Input: the current node’s instance set $I$, and the non-missing samples for feature $k$, $I_k = \{i \in I \mid x_{ik} \neq \text{missing}\}$
- Compute statistics: for non-missing samples $G_k = \sum_{i \in I_k} g_i$, $H_k = \sum_{i \in I_k} h_i$; for missing samples $G_m = \sum_{i \in I \setminus I_k} g_i$, $H_m = \sum_{i \in I \setminus I_k} h_i$
- Initialize: $G_L \leftarrow 0$, $H_L \leftarrow 0$, $\mathit{score} \leftarrow 0$
- For each non-missing sample $j \in I_k$ in ascending order of $x_{jk}$:
- $G_L \leftarrow G_L + g_j$, $H_L \leftarrow H_L + h_j$
- $G_R \leftarrow G_k - G_L$, $H_R \leftarrow H_k - H_L$
- $\mathit{score}_{\text{left}} \leftarrow \mathrm{Gain}(G_L + G_m, H_L + H_m, G_R, H_R)$ // missing values go left
- $\mathit{score}_{\text{right}} \leftarrow \mathrm{Gain}(G_L, H_L, G_R + G_m, H_R + H_m)$ // missing values go right
- $\mathit{score} \leftarrow \max(\mathit{score}, \mathit{score}_{\text{left}}, \mathit{score}_{\text{right}})$
- Output: the best split and its default direction
The paper (Algorithm 3) instead scans the non-missing samples once ascending and once descending: in the ascending pass missing values fall to the right, in the descending pass to the left. The single-pass form above is equivalent.
Performance and behavior:
- Efficiency: the sparsity-aware algorithm visits only non-missing values, so its cost is linear in the number of non-missing entries. On the Allstate-10K dataset it’s 50 times faster than a naive implementation.
- Uniform handling: missing values, zeros and one-hot sparsity are all treated the same way, with no need to distinguish their origin.
- Prediction: the learned tree routes missing-value samples by the default direction.
- Parameter:
missing(present in bothDMatrixand the sklearn interface, defaultnp.nan) lets you designate a specific value (such as-999) as missing. For sparse matrix input (ascipy.sparse.csr_matrix, say), entries that aren’t stored also count as missing, which is exactly why the sparsity-aware algorithm only visits non-missing entries.
6.7 Column sampling and parallel optimization (blocks, cache awareness, out-of-core)
6.7.1 Column sampling
Borrowing from random forests, XGBoost offers three levels of column sampling to guard against overfitting:
| Parameter | Level | Meaning |
|---|---|---|
colsample_bytree | Per tree | Sample a fraction of features before building each tree |
colsample_bylevel | Per level | Sample a fraction of features at each level of the tree |
colsample_bynode | Per node | Sample a fraction of features at each node split |
All three default to 1 and nest and multiply: each level’s features are drawn from the tree’s selected features, and each node’s from the level’s. With 64 features and all three set to 0.5, for instance, each split sees only $64 \times 0.5^3 = 8$ candidate features (an example from the official docs). colsample_bynode isn’t supported with exact.
The paper reports, based on user feedback, that column sampling can prevent overfitting even more effectively than the traditional row sampling (subsample) while also speeding up the parallel algorithm. Intuitively, each tree sees only some features, so trees are less likely to make the same mistakes — the same reasoning as random forests.
6.7.2 Parallel optimization: the block structure
Column blocks: XGBoost stores data in a compressed columnar format (CSC):
- Each column is pre-sorted by feature value and stored in an in-memory unit called a block.
- The sorted blocks are reused across training rounds, avoiding repeated sorting.
- Bin statistics on a sorted column become a linear scan, which speeds up the approximation algorithm considerably.
- Blocks can be split into smaller blocks by row for parallel and distributed processing. For the approximation algorithm, the paper found $2^{16}$ samples per block strikes a good balance between cache hits and parallel load: too small and each thread has too little work, too large and the gradient statistics don’t fit in CPU cache.
Feature-level parallelism: the per-column statistics ($G$ and $H$) are computed independently, which parallelizes naturally. Tree building is sequential (boosting is inherently so), but split finding within one tree parallelizes well.
6.7.3 Cache-aware access
The gradient statistics $g_i$ and $h_i$ are stored by sample index. Scanning a sorted feature column visits sample indices out of order, which causes cache misses. XGBoost’s answer:
- Give each thread an internal buffer.
- Use cache-aware prefetching: fetch the gradient statistics about to be used into the buffer in order, then accumulate in mini-batches, turning the “read one, accumulate it immediately” dependency into a longer chain and so reducing stalls from cache misses.
- On the Allstate and Higgs 10-million-sample datasets, the cache-aware exact greedy algorithm ran about 2 times faster than a naive implementation; at 1 million samples the difference was small, since the gradient statistics fit in cache.
6.7.4 Out-of-core computation
When the data exceed memory:
- Store it in blocks on disk, overlapping computation with disk reads during training.
- Block compression: blocks are compressed by column and decompressed on load by a separate thread. The paper reports compression ratios of about 26%-29% on the datasets tested.
- Sharding: split the data across disks and read in parallel, sidestepping the disk I/O bottleneck.
- Compression and decompression cost far less than disk access, so the overall speedup is substantial.
6.8 XGBoost in Kaggle competitions
XGBoost has dominated Kaggle since 2014-2015:
- 2015: of the 29 winning solutions Kaggle’s blog surveyed that year, 17 used XGBoost (8 used it alone; most of the rest ensembled it with neural networks).
- KDD Cup 2015: all top-10 teams used XGBoost.
- Applications: ad click-through rate prediction (CTR), insurance claims, customer behavior analysis, spam and malware classification, particle physics (Higgs boson event classification).
Why does XGBoost do so well in competitions?
- It suits tabular data: on structured, tabular data, tree models capture feature interactions better than linear models.
- It’s robust to feature engineering choices: insensitive to feature scaling, and it handles all feature types (numeric, categorical, binary).
- It handles missing values automatically, skipping a tedious preprocessing step.
- Regularization prevents overfitting: explicit regularization generalizes well under competition conditions.
- It’s fast: at equal accuracy it trains far faster than classic GBDT, which makes iteration quick.
- It’s interpretable: feature importance and SHAP values support model explanation.
6.9 The Python API (native + scikit-learn compatible)
XGBoost offers two Python interfaces.
Native API
| |
Scikit-learn compatible API
| |
Both snippets above use the test set as the early-stopping validation set for simplicity; a real project should hold out a separate validation set, otherwise test scores come out optimistic (see the early-stopping and cross-validation discussion in Tuning Guide and Best Practices).
Native categorical support: since XGBoost 1.5, categorical features can be handled directly, with no need to one-hot encode first. Mark the column as pandas category dtype and pass enable_categorical=True when building the DMatrix or the sklearn model (requires hist or approx). From 1.6 there’s optimal partitioning: when the number of categories is below max_cat_to_onehot, split one category against the rest (one-hot style); otherwise sort the categories by gradient statistics and partition them into two subsets, the same idea as LightGBM’s categorical splits (see §7.6 of LightGBM; per the official Categorical Data docs and the max_cat_to_onehot parameter description).
Common objectives and metrics:
objective | When |
|---|---|
reg:squarederror | Regression (mean squared error) |
binary:logistic | Binary classification (outputs probabilities) |
binary:logitraw | Binary classification (outputs raw logits) |
multi:softmax | Multiclass (outputs the class) |
multi:softprob | Multiclass (outputs probabilities) |
rank:pairwise | Learning to rank |
survival:aft | Survival analysis |
eval_metric | Meaning |
|---|---|
rmse | Root mean squared error |
mae | Mean absolute error |
logloss | Log loss |
error | Classification error rate |
auc | Area under the ROC curve |
merror | Multiclass error rate |
ndcg | Normalized discounted cumulative gain |
6.10 Pseudocode and the overall training flow
The overall XGBoost training flow
flowchart TD
A["Initialize predictions y_hat_i = base_score"] --> B["For t = 1 to T"]
B --> C["Compute g_i and h_i for each sample"]
C --> D["Build tree t: find the best splits"]
D --> E["Compute the optimal leaf weights w_j*"]
E --> F["Update predictions y_hat_i += eta * f_t(x_i)"]
F --> G{"t < T ?"}
G -->|Yes| B
G -->|No| H["Output the final model F(x) = base_score + eta * sum_t f_t(x)"]
Pseudocode:
- Input: training set $D = \{(x_i, y_i)\}_{i=1}^n$, number of rounds $T$, loss $L$, regularization $\Omega$
- Initialize: $\hat{y}_i \leftarrow b_0$ for all $i$ ($b_0$ is
base_score. Since XGBoost 2.0, most built-in objectives estimate this intercept from the data before training; you can also set it, e.g.base_score=0.5) - For $t = 1, 2, \dots, T$:
- Compute the gradient statistics:
- For each sample $i = 1, \dots, n$:
- $g_i \leftarrow \frac{\partial L(y_i, \hat{y}_i)}{\partial \hat{y}_i}$
- $h_i \leftarrow \frac{\partial^2 L(y_i, \hat{y}_i)}{\partial \hat{y}_i^2}$
- For each sample $i = 1, \dots, n$:
- Store the data in column blocks (can be done ahead of time)
- Build the $t$-th tree: $f_t \leftarrow \text{BuildTree}(\{(x_i, g_i, h_i)\}_{i=1}^n, \Omega)$
- For each node in the queue:
- Initialize $\mathit{best\_gain} \leftarrow 0$, $\mathit{best\_split} \leftarrow \text{None}$
- For each feature $k$:
- Get candidate split points (exact greedy or approximation)
- For each candidate:
- $\mathit{gain} \leftarrow \operatorname{ComputeGain}(\text{node}, \text{candidate}, \Omega)$ // per 6.3.6, $\gamma$ already deducted; includes sparsity-aware handling
- If $\mathit{gain} > \mathit{best\_gain}$: update $\mathit{best\_gain}$ and $\mathit{best\_split}$
- If $\mathit{best\_gain} > 0$, and both children’s Hessian sums are at least
min_child_weight, andmax_depthisn’t exceeded: split and enqueue the children
- For each leaf $j$: $w_j^* \leftarrow -\frac{G_j}{H_j + \lambda}$
- For each node in the queue:
- Update predictions (with shrinkage): $\hat{y}_i \leftarrow \hat{y}_i + \eta \cdot f_t(x_i)$ for all $i$
- Compute the gradient statistics:
- Output: the final model $F(x) = b_0 + \eta \sum_{t=1}^T f_t(x)$ (this outputs the margin; classification tasks still need sigmoid / softmax)
6.11 A custom objective
XGBoost accepts custom objectives; you just return $g_i$ and $h_i$ for each sample. With the native API, pass it as xgb.train(..., obj=function); the signature is (preds, dtrain), where preds is the untransformed margin:
| |
About this Huber example Where $\lvert \text{diff} \rvert > \delta$, Huber loss has zero second derivative, so those samples contribute nothing to $H_j$: the leaf weight $-\frac{G_j}{H_j+\lambda}$ can blow up, and nodes can fail to split because $H$ falls below
min_child_weight. In practice people switch to the twice-differentiable pseudo-Huber loss, which XGBoost ships asobjective='reg:pseudohubererror'(threshold parameterhuber_slope). The sklearn interface also acceptsobjective=<callable>, in which case the signature is(y_true, y_pred).
6.12 A commented Python example
| |
