XGBoost · From Decision Trees to Gradient Boosting in 8 Steps

If you’ve used xgb.train() but feel like there’s a black box between import xgboost and model.predict(), this article is for you. We’ll build up from a single decision tree to the full XGBoost algorithm in eight logical steps.

Step 1: A single decision tree predicts one value per leaf

A decision tree partitions the feature space into regions (leaves) and assigns a constant prediction to each leaf. For regression, the predicted value for a sample that falls into leaf $j$ is simply the mean of the target values in that leaf:

$$ \hat{y}i = \bar{y}{\text{leaf}(i)} $$

For a tree with $T$ leaves, the output is a step function over the feature space. The tree is trained by recursively splitting nodes to minimize impurity (variance for regression, Gini or entropy for classification).

The problem with a single tree? High variance. A slight change in training data can produce a dramatically different tree. This is where ensembling comes in.

Step 2: Bagging averages many trees to reduce variance

Bagging (Bootstrap Aggregating) trains $K$ trees on $K$ bootstrap samples of the data and averages their predictions:

$$ \hat{y}i = \frac{1}{K} \sum{k=1}^{K} f_k(x_i) $$

Each tree $f_k$ is trained independently. Random Forest adds a second layer of randomization — at each split, only a random subset of features is considered. Independent training means bagging can run in parallel, but the trees don’t learn from each other’s mistakes.

Step 3: Boosting trains trees sequentially, each fixing the last one’s errors

Unlike bagging, boosting trains trees sequentially. Tree $k$ is trained to predict the residuals (errors) from the ensemble of the first $k-1$ trees:

$$ \hat{y}i^{(k)} = \sum{j=1}^{k-1} f_j(x_i) + f_k(x_i) $$

The new tree $f_k$ fits the residuals $r_i = y_i - \hat{y}_i^{(k-1)}$. By repeatedly fitting residuals, the ensemble incrementally refines its predictions.

Step 4: Gradient boosting reframes residuals as negative gradients

Instead of explicitly computing residuals, gradient boosting fits each new tree to the negative gradient of the loss function with respect to the current predictions:

$$ r_{i}^{(k)} = -\left[ \frac{\partial L(y_i, \hat{y}_i)}{\partial \hat{y}i} \right]{\hat{y}_i = \hat{y}_i^{(k-1)}} $$

This generalization is powerful: it means the same boosting framework can optimize any differentiable loss function. For squared error loss $L = (y - \hat{y})^2$, the negative gradient is exactly the residual $2(y - \hat{y})$, so this reduces to Step 3. But for logistic loss, Huber loss, or custom objectives, the gradient points the way.

Step 5: XGBoost uses a second-order Taylor approximation

Standard gradient boosting uses only the first derivative (gradient). XGBoost’s key innovation is incorporating the second derivative (Hessian) via a second-order Taylor expansion of the loss function around the current prediction:

$$ L(y_i, \hat{y}_i^{(k-1)} + f_k(x_i)) \approx L(y_i, \hat{y}_i^{(k-1)}) + g_i f_k(x_i) + \frac{1}{2} h_i f_k^2(x_i) $$

where $g_i = \partial L / \partial \hat{y}_i$ and $h_i = \partial^2 L / \partial \hat{y}_i^2$ are the gradient and Hessian. This approximation enables a closed-form solution for the optimal leaf weight, which we’ll see in Step 6.

Step 6: XGBoost has a closed-form optimal leaf weight

For a tree with structure $q$ (mapping features to leaf indices) and leaf weight vector $w$, the regularized objective for tree $k$ is:

$$ \mathcal{L}^{(k)} = \sum_{i=1}^{n} \left[ g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2 \right] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2 $$

The $\gamma T$ term penalizes the number of leaves (controlling tree complexity), and $\lambda \sum w_j^2$ is L2 regularization on leaf weights. For a fixed tree structure, the optimal leaf weight $w_j^*$ is:

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

where $I_j$ is the set of samples in leaf $j$. Substitute this back to get the structure score — the value a potential split must beat:

$$ \mathcal{L}{\text{split}} = \frac{1}{2} \left[ \frac{(\sum{i \in I_L} g_i)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{(\sum_{i \in I_R} g_i)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I} h_i + \lambda} \right] - \gamma $$

If $\mathcal{L}_{\text{split}} > 0$, the split is worthwhile; if not, the tree stops growing at this node.

Step 7: The split-finding algorithm is approximate and weighted quantile-based

Exact greedy split finding (evaluating every possible split point for every feature) is $O(n \log n)$ per feature — expensive for large datasets. XGBoost uses an approximate algorithm based on weighted quantile sketches. The key insight: the Hessian $h_i$ represents the “weight” of each sample’s contribution to the loss. The weighted quantile sketch ensures split candidates are placed where the loss surface is steepest.

Step 8: Putting it all together: the XGBoost training loop

1. Start with initial prediction $\hat{y}_i^{(0)}$ (e.g., the mean of $y$ for regression)
2. For $k = 1$ to $K$: a. Compute $g_i$ and $h_i$ for all samples b. Build tree $f_k$ greedily: propose splits using weighted quantile sketch, evaluate $\mathcal{L}_{\text{split}}$, grow if gain > $\gamma$ c. Compute optimal leaf weights $w_j^*$ for the grown tree d. Update $\hat{y}_i^{(k)} = \hat{y}_i^{(k-1)} + \eta \cdot f_k(x_i)$ where $\eta$ is the learning rate
3. Return ensemble $\hat{y} = \sum_{k=1}^K \eta f_k(x)$

The learning rate $\eta$ (eta, typically 0.01–0.3) is crucial — it shrinks each tree’s contribution, making the ensemble more robust to overfitting at the cost of requiring more trees.

Beyond the 8 steps

XGBoost adds several practical features on top of this foundation: column subsampling (like Random Forest), row subsampling (stochastic gradient boosting), sparsity-aware split finding (handling missing values natively), cache-aware data access patterns, and out-of-core computation for datasets that don’t fit in memory. We cover each of these in separate articles.