The XGBoost Algorithm: A Step-by-Step Deep Dive

XGBoost (eXtreme Gradient Boosting) is a scalable, regularized implementation of gradient boosting that builds an ensemble of decision trees sequentially, where each new tree corrects the errors of the previous ensemble. The core mathematical insight is the use of a second-order Taylor approximation of the loss function, enabling Newton’s method-style optimization within each boosting round, combined with an explicit regularization term penalizing model complexity. In practice, this yields faster convergence, better generalization, and state-of-the-art performance on structured/tabular data, as described in the foundational paper by Chen & Guestrin (2016).

Initialization: The Base Prediction

Before any tree is built, XGBoost initializes the ensemble with a constant prediction $\hat{y}_i^{(0)}$ that minimizes the unregularized loss over all training examples:

Regression (squared error loss): The base prediction is the mean of the target values. For a dataset with $N$ samples and targets $y_i$, we set: $$\hat{y}i^{(0)} = \frac{1}{N}\sum{i=1}^{N} y_i$$
Binary Classification (logistic loss): The base prediction is the log-odds of the positive class. If $p$ is the proportion of positive samples, then: $$\hat{y}_i^{(0)} = \log\left(\frac{p}{1-p}\right)$$

This initial prediction is assigned to every training instance identically. The model at round $t=0$ is simply $F_0(x_i) = \hat{y}_i^{(0)}$ for all $i$.

The Regularized Objective Function

At boosting round $t$, XGBoost adds a new tree $f_t$ to minimize the following regularized objective:

$$\mathcal{L}^{(t)} = \sum_{i=1}^{N} \ell\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t)$$

The complexity penalty $\Omega(f_t)$ for a tree with $T$ leaves and leaf weight vector $w$ is defined as:

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

Here, $\gamma$ penalizes the number of leaves (controlling tree depth and granularity), while $\lambda$ is an L2 regularization coefficient on leaf weights. An additional L1 term $\alpha \sum |w_j|$ can also be included, yielding an elastic-net-style penalty. This regularization is one of XGBoost’s defining features, directly countering overfitting at the tree structure level rather than relying solely on post-hoc pruning.

Computing Gradients and Hessians

For each training instance $i$, we compute the first-order gradient $g_i$ and second-order Hessian $h_i$ of the loss function with respect to the current prediction $\hat{y}_i^{(t-1)}$:

$$g_i = \frac{\partial \ell(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}, \quad h_i = \frac{\partial^2 \ell(y_i, \hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2}$$

For a concrete example, with squared error loss $\ell = \frac{1}{2}(y_i - \hat{y}_i)^2$, we obtain $g_i = \hat{y}_i - y_i$ (the residual) and $h_i = 1$ (constant). For logistic loss, both $g_i$ and $h_i$ are non-constant functions of the current prediction, which is precisely where second-order information provides an advantage over traditional gradient boosting.

Unlike standard gradient boosting machines (GBM) that use only $g_i$ to guide tree construction, XGBoost’s simultaneous use of $g_i$ and $h_i$ enables the algorithm to account for the curvature of the loss surface when choosing splits and computing leaf values.

Second-Order Taylor Expansion and Newton’s Method

The key mathematical step is approximating the objective at round $t$ using a second-order Taylor expansion around $\hat{y}_i^{(t-1)}$:

$$\ell(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) \approx \ell(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)$$

Dropping the constant term $\ell(y_i, \hat{y}_i^{(t-1)})$ (which does not depend on $f_t$), the approximate objective for tree $f_t$ becomes:

$$\tilde{\mathcal{L}}^{(t)} = \sum_{i=1}^{N} \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2$$

This is a sum of independent quadratic functions per leaf. For a leaf $j$ containing instances in set $I_j$, the contribution is:

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

This quadratic form in $w_j$ can be minimized analytically—a direct application of Newton’s method in function space, contrasting with standard gradient boosting’s first-order steepest descent approach.

Leaf Weight Computation

For a fixed tree structure, the optimal leaf weight $w_j^*$ minimizes the quadratic expression above. Taking the derivative with respect to $w_j$ and setting to zero yields:

$$w_j^* = - \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} = - \frac{G_j}{H_j + \lambda}$$

where $G_j = \sum_{i \in I_j} g_i$ and $H_j = \sum_{i \in I_j} h_i$. The corresponding minimal loss contribution from leaf $j$ is:

$$\text{Obj}_j^* = -\frac{1}{2} \frac{G_j^2}{H_j + \lambda} + \gamma$$

The $\gamma$ term is added per leaf. This closed-form solution eliminates the need for line search or heuristic leaf value assignment, a direct consequence of the quadratic approximation.

Split Finding: The Exact Greedy Algorithm

XGBoost builds each tree by recursively partitioning the feature space. For a given node, the algorithm evaluates potential splits by computing the gain — the reduction in the regularized objective achieved by splitting the node into left and right children.

Let $I$ be the instance set at the current node, with summary statistics $G = \sum_{i \in I} g_i$ and $H = \sum_{i \in I} h_i$. For a candidate split sending instances to left child $I_L$ and right child $I_R$, 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$$

The three terms inside the brackets represent the score of the left child, the score of the right child, and the score of the parent node (if unsplit). The gain is positive only if the reduction in loss exceeds the complexity cost $\gamma$ of adding a new leaf.

The exact greedy algorithm enumerates all possible split points for each feature by sorting the instances by feature value and scanning linearly, updating cumulative $G$ and $H$ statistics. For $d$ features and $N$ sorted instances, the complexity is $O(d \cdot N \log N)$ due to sorting. In practice, XGBoost also implements an approximate algorithm using weighted quantile sketches, as detailed in the XGBoost documentation, which is essential for large-scale datasets and distributed settings.

Shrinkage and Subsampling

Shrinkage (Learning Rate $\eta$): After a tree $f_t$ is constructed, its leaf weights are scaled by a factor $\eta \in (0, 1]$ before being added to the ensemble:

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

A smaller learning rate (typical values range from 0.01 to 0.3) reduces the influence of each individual tree, forcing the model to build more trees to fit the data. This slows convergence but consistently improves generalization by smoothing the optimization path, analogous to step-size reduction in gradient descent.

Column Subsampling (Feature Subsampling): At each tree construction or at each level/split, XGBoost randomly selects a subset of features to consider. This technique, borrowed from random forests, decorrelates the trees and reduces computational cost. Typical subsampling ratios range from 0.5 to 1.0.

Row Subsampling (Instance Subsampling): Before building each tree, a random fraction of training instances (without replacement) is sampled. This stochastic component introduces diversity into the ensemble and acts as a powerful regularizer, particularly effective when combined with shrinkage.

Final Prediction

After $M$ boosting rounds, the final prediction for an instance $x$ is the sum of the initial base prediction and the contributions of all trees, each scaled by the learning rate:

$$\hat{y}_i = \hat{y}i^{(0)} + \eta \sum{t=1}^{M} f_t(x_i)$$

For classification, this raw output is transformed via a link function (e.g., sigmoid for binary classification) to produce class probabilities. The additive structure means each tree contributes independently to the final score, enabling straightforward feature importance analysis.

Pseudocode

Algorithm: XGBoost Training
Input: Training data {(x_i, y_i)}_{i=1}^N, loss function ℓ,
       number of rounds M, learning rate η, regularization params λ, γ,
       subsampling ratios
Output: Ensemble model F_M

1: F_0(x) ← argmin_c Σ ℓ(y_i, c)   // base prediction
2: for t = 1 to M do
3:     for i = 1 to N do
4:         g_i ← ∂ℓ(y_i, F_{t-1}(x_i)) / ∂F_{t-1}(x_i)
5:         h_i ← ∂²ℓ(y_i, F_{t-1}(x_i)) / ∂F_{t-1}(x_i)²
6:     end for
7:     // Optional: subsample instances and features
8:     Initialize tree f_t with root node containing all (sampled) instances
9:     Initialize queue Q with root node
10:    while Q not empty do
11:        node ← Q.pop()
12:        I ← instances in node
13:        G ← Σ_{i∈I} g_i, H ← Σ_{i∈I} h_i
14:        best_gain ← 0
15:        for each feature k do
16:            Sort I by x_{ik}
17:            G_L ← 0, H_L ← 0
18:            for each split point s do
19:                Update G_L, H_L with instances ≤ s
20:                G_R ← G - G_L, H_R ← H - H_L
21:                gain ← ½[G_L²/(H_L+λ) + G_R²/(H_R+λ) - G²/(H+λ)] - γ
22:                if gain > best_gain then
23:                    best_gain ← gain
24:                    best_split ← (k, s)
25:                end if
26:            end for
27:        end for
28:        if best_gain > 0 then
29:            Create left and right children based on best_split
30:            Assign instances to children
31:            Q.push(left_child, right_child)
32:        else
33:            Mark node as leaf
34:            w ← -G / (H + λ)
35:        end if
36:    end while
37:    F_t(x) ← F_{t-1}(x) + η f_t(x)
38: end for
39: return F_M

FAQ

Why does XGBoost use second-order derivatives instead of just gradients? The second-order Taylor expansion provides a quadratic approximation of the loss, enabling Newton’s method in function space. This yields closed-form optimal leaf weights and a principled gain metric for split evaluation, often leading to faster convergence and more accurate trees compared to first-order methods alone. It also naturally incorporates the curvature of the loss, which matters for non-linear loss functions like logistic loss.

How do $\lambda$ and $\gamma$ affect the model? $\lambda$ (L2 regularization on leaf weights) shrinks leaf values toward zero, preventing any single leaf from dominating predictions. $\gamma$ (minimum loss reduction required for a split) acts as a complexity penalty: a split is only made if the gain exceeds $\gamma$. Increasing both parameters yields simpler trees with fewer leaves and smaller leaf weights, reducing overfitting.

What is the relationship between XGBoost and gradient boosting? XGBoost is a specific highly optimized implementation of gradient boosting. It extends the standard algorithm with second-order optimization, explicit regularization, and system-level optimizations (cache-aware access, out-of-core computation, parallelization). The fundamental additive tree ensemble framework is identical, but XGBoost’s enhancements make it both more accurate and significantly faster in practice. For a detailed treatment of the theoretical foundations and system design, refer to the original XGBoost paper.