XGBoost: Intuition and Math

sklearn's GradientBoostingRegressor and XGBoost both build trees on residuals. XGBoost differs in three ways: it uses the second-order Taylor approximation of the loss (not just the first-order residual), adds explicit regularization to the objective, and uses histogram-based split finding for speed. This post derives where those differences come from.

Anchor: 6-sample house prices — same as the Gradient Boosting post.

import numpy as np

X = np.array([650, 850, 1100, 1400, 1600, 1900])
y = np.array([180, 220, 280, 340, 370, 430])
# F₀ = mean(y) = 303.3 — same starting point as vanilla GB

XGBoost vs sklearn GradientBoosting

XGBoost Objective Function

At tree $t$, XGBoost minimizes a regularized objective using a second-order Taylor expansion of the loss:

${\text{Obj}}^{(t)}\approx {\sum }_i\left[g_i{w}_{q(x_i)}+\frac{1}{2}(h_i+\lambda )w_{q(x_i)}^2\right]+\gamma T$

Where:

• $g_i=\frac{\partial L(y_i,F_{t-1}(x_i))}{\partial F}$ — first-order gradient (residual for MSE)
• $h_i=\frac{{\partial }^{2}L(y_i,F_{t-1}(x_i))}{\partial F^2}$ — second-order gradient (hessian); for MSE: $h_i=1$
• $w_j$ — leaf weight for leaf $j$ (what we're optimizing)
• $\lambda$ — L2 regularization coefficient on leaf weights
• $\gamma$ — minimum gain required to create any split (pruning threshold)
• $T$ — number of leaves (penalizes tree complexity)

For MSE loss: $g_i={\hat{y}}_i-y_i$ (opposite sign of residual), $h_i=1$ for all samples.

Optimal Leaf Weight Formula

Group samples in leaf $j$ as $I_j$. Define: $G_j={\sum }_{i\in I_j}{g}_i,H_j={\sum }_{i\in I_j}{h}_i$

Taking $\frac{d\text{Obj}}{d{w}_j}=0$:

$w_j^{\ast }=-\frac{G_j}{H_j+\lambda }$

When $\lambda =0$: $w_j^{\ast }=-G_j/H_j=-\frac{\sum r_i}{n_j}$ = mean residual — exactly vanilla GB.

When $\lambda >0$: leaf weights shrink toward zero. The larger $\lambda$, the more regularized the tree.

Gain Formula for Split Finding

The objective improvement from splitting a leaf into left ($L$) and right ($R$):

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

Only create the split if Gain $>0$. $\gamma$ sets the minimum gain threshold — larger $\gamma$ prunes more aggressively.

Manual Trace: 6-Sample Anchor (Tree 1, $\lambda =1$, $\gamma =0$)

Gradient Table

$F_0=303.3$ (same mean). For MSE: $g_i=F_0-y_i$ (note: positive when predicting too high).

$G_{\text{total}}=123.3+83.3+23.3-36.7-66.7-126.7=0.0$, $H_{\text{total}}=6$.

$G_{\text{total}}=0$ because $F_0=\bar{y}$ — the mean prediction cancels all gradients at the root.

Evaluate Split at sq_ft ≤ 1250

Left (samples 1,2,3): $G_L=123.3+83.3+23.3=+229.9$, $H_L=3$.

Right (samples 4,5,6): $G_R=-36.7-66.7-126.7=-230.1$, $H_R=3$.

Optimal Leaf Weights

$w_L^{\ast }=-\frac{G_L}{H_L+\lambda }=-\frac{229.9}{3+1}=-57.5$

$w_R^{\ast }=-\frac{G_R}{H_R+\lambda }=-\frac{-230.1}{3+1}=+57.5$

Update with $\nu =0.3$ (XGBoost default)

$F_1(x)=F_0+\nu \cdot w^{\ast }$

• sq_ft ≤ 1250: $303.3+0.3\times (-57.5)=303.3-17.25=286.1$
• sq_ft > 1250: $303.3+0.3\times (+57.5)=303.3+17.25=320.6$

Compare to vanilla GB (ν=0.1, leaf = mean residual = ±76.6): update was 303.3 ± 7.66, giving 295.6/311.0. XGBoost with λ=1 uses smaller leaf weights (±57.5) but larger ν (0.3), landing at similar positions — same effect, different parameterization.

Effect of λ (L2 Regularization)

Larger $\lambda$: leaf weights shrink toward zero (the tree corrects the residual less aggressively). Gain decreases — at high $\lambda$, splits that would have been created ($\text{Gain}>0$) may be rejected. $\gamma$ provides a hard cutoff: if $\text{Gain}<\gamma$, the split is never created regardless of $\lambda$.

min_child_weight

XGBoost only creates a split if each child node satisfies $H_j\ge \text{min\_child\_weight}$.

• MSE loss: $h_i=1$, so $H_j=n_j$. min_child_weight=5 requires at least 5 samples per leaf — identical to min_samples_leaf in sklearn.
• Logistic loss: $h_i={\hat{p}}_i(1-{\hat{p}}_i)$. $H_j=\sum \hat{p}(1-\hat{p})$. For probabilities near 0 or 1, $h_i\approx 0$. A leaf with 100 near-certain predictions can have $H_j<5$ — preventing overly confident leaves.

Level-Wise vs Leaf-Wise Tree Growth

Level-wise: all nodes at the same depth split together — controlled by max_depth. Leaf-wise: always split whichever existing leaf has the highest gain — faster convergence but risks deep paths that overfit. XGBoost uses level-wise by default; LightGBM uses leaf-wise with num_leaves to control depth.

Histogram-Based Split Finding

Vanilla GB (sklearn): for each feature, sort $n$ values → $n-1$ candidate thresholds → $O(n)$ evaluations per feature per level → $O(nd)$ per level.

XGBoost: bin each feature into $B\le 256$ histogram buckets. Only $B-1$ thresholds per feature → $O(Bd)$ per level. For $n=10^6$ samples, this reduces split-finding from $10^6\times d$ to $255\times d$ operations — ~4000× reduction.

The histogram is approximate: if the true optimal threshold falls between two bin boundaries, XGBoost uses the bin boundary. In practice, 256 bins is fine-grained enough that accuracy loss is negligible.

Missing Value Handling

XGBoost's sparsity-aware algorithm: during training, for each split candidate, evaluate both:

1. Route all missing values LEFT
2. Route all missing values RIGHT

Choose whichever direction reduces the objective more. At inference, the learned default direction is used for missing values. No imputation required — this is built into the split-finding algorithm.

import xgboost as xgb
import numpy as np

# Example: create data with NaN
X_with_nan = np.array([[1.0, np.nan], [2.0, 3.0], [np.nan, 4.0]])
y = np.array([0, 1, 1])

dtrain = xgb.DMatrix(X_with_nan, label=y)
# XGBoost handles NaN internally — no fillna needed

Test Your Understanding

1. At the root, $G_{\text{total}}=0$ because $F_0=\bar{y}$. The root score in the Gain formula is $G_{\text{total}}^2/(H_{\text{total}}+\lambda )=0$. Does this mean the root contributes nothing to the Gain, or does it serve a different purpose in the formula? What would happen to the Gain formula if you started with a non-mean $F_0$ (say, $F_0=0$)?

2. Optimal leaf weight is $w^{\ast }=-G_j/(H_j+\lambda )$. For MSE, $g_i=F_{t-1}(x_i)-y_i$ (not the usual residual sign). Verify: if we define pseudo-residuals as $r_i=y_i-F_{t-1}(x_i)$ (same sign as vanilla GB), then $G_j=-\sum r_i$. Show that $w^{\ast }=-G_j/H_j=+\text{mean}(r_i)$ when $\lambda =0$ — i.e., XGBoost and vanilla GB agree at $\lambda =0$.

3. With $\lambda =100$: $w_L^{\ast }=-229.9/103=-2.23$. The prediction update is $F_1(\text{left})=303.3+0.3\times (-2.23)=302.6$. The true ${\bar{y}}_{\text{left}}=(180+220+280)/3=226.7$. The model barely moves from the global mean. How many rounds would it take to approximately converge to the correct leaf prediction if every round gives a step of only 2.23?

4. Histogram binning uses $B=256$ bins. For a feature with only 10 unique values (like bedrooms in the house price dataset), the histogram has only 9 boundaries regardless of $B$. In this case, histogram XGBoost and exact vanilla GB give identical splits. For which types of features does histogram approximation actually matter, and for which is it irrelevant?

5. In leaf-wise tree growth (LightGBM), the model always splits the leaf with the highest gain. This can create one very deep branch while other branches stay as leaves. Why does LightGBM use num_leaves (total number of leaf nodes) instead of max_depth to control model complexity? What's a model with num_leaves=31 and max_depth=6 vs one with num_leaves=31 and max_depth=None — could they have the same structure?