Gradient Boosted Trees

Gradient boosted trees have won more Kaggle competitions than any other algorithm. On structured tabular data — the dominant form of data in finance, healthcare, and industry — they routinely outperform deep learning models while being faster to train, more robust to hyperparameter choices, and more interpretable. Understanding what makes them work, and how XGBoost, LightGBM, and CatBoost each improve on the original formulation, is essential for any practitioner working with real-world data.

The Gradient Boosting Framework

Gradient boosting (Friedman, 2001) builds an ensemble by training each new tree to predict the residual error of the current ensemble. The prediction at round $m$ is:

$$F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \eta \cdot h_m(\mathbf{x})$$

where $h_m$ is a new tree fitted to the negative gradient of the loss with respect to the current predictions, and $\eta$ is the learning rate (shrinkage).

For squared error loss $\mathcal{L} = \frac{1}{2}(y - F(\mathbf{x}))^2$, the negative gradient is simply the residual $y - F_{m-1}(\mathbf{x})$. For other losses (log-loss, quantile loss), the pseudo-residuals are the gradient of the loss evaluated at current predictions.

The Algorithm

The core gradient boosting loop:

1. Initialize $F_0(\mathbf{x}) = \arg\min_\gamma \sum_i \mathcal{L}(y_i, \gamma)$ (usually the mean)
2. For $m = 1$ to $M$:
   1. Compute pseudo-residuals: $r_{im} = -\frac{\partial \mathcal{L}(y_i, F(\mathbf{x}i))}{\partial F(\mathbf{x}i)}\bigg|{F=F{m-1}}$
   2. Fit a tree $h_m$ to $({\mathbf{x}i, r{im}})$
   3. Compute leaf values by line search: $\gamma_{jm} = \arg\min_\gamma \sum_{i \in R_{jm}} \mathcal{L}(y_i, F_{m-1}(\mathbf{x}_i) + \gamma)$
   4. Update: $F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \eta \sum_j \gamma_{jm} \mathbf{1}[\mathbf{x} \in R_{jm}]$
3. Return $F_M$

XGBoost

XGBoost (Chen & Guestrin, 2016) reformulates gradient boosting with a second-order Taylor expansion of the loss and explicit regularization, dramatically improving both accuracy and training speed.

Regularized Objective

At round $m$, XGBoost minimizes the approximate objective:

$$\tilde{\mathcal{L}}m = \sum{i=1}^n \left[ g_i f_m(\mathbf{x}_i) + \frac{1}{2} h_i f_m(\mathbf{x}_i)^2 \right] + \Omega(f_m)$$

where:

• $g_i = \partial_{\hat{y}} \mathcal{L}(y_i, \hat{y}_i)$ — first-order gradient (like standard boosting)
• $h_i = \partial^2_{\hat{y}} \mathcal{L}(y_i, \hat{y}_i)$ — second-order gradient (Hessian)
• $\Omega(f) = \gamma T + \frac{1}{2}\lambda |\mathbf{w}|^2$ — regularization on tree structure ($T$ = number of leaves) and leaf weights

The optimal leaf weight for leaf $j$ is:

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

The optimal split gain (information gain for splitting a leaf):

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

Splits are only accepted when Gain > 0. The $\gamma$ parameter directly controls minimum gain for a split — a principled tree pruning mechanism.

XGBoost in Practice

import xgboost as xgb
from sklearn.model_selection import train_test_split
from sklearn.metrics import roc_auc_score
import numpy as np

X_train, X_val, y_train, y_val = train_test_split(X, y, test_size=0.2, random_state=42)

dtrain = xgb.DMatrix(X_train, label=y_train)
dval = xgb.DMatrix(X_val, label=y_val)

params = {
    "objective": "binary:logistic",
    "eval_metric": "auc",
    "max_depth": 6,             # Maximum tree depth
    "learning_rate": 0.05,      # Shrinkage
    "n_estimators": 1000,       # Will be tuned by early stopping
    "subsample": 0.8,           # Row subsampling per tree
    "colsample_bytree": 0.8,    # Feature subsampling per tree
    "reg_alpha": 0.1,           # L1 regularization on leaf weights
    "reg_lambda": 1.0,          # L2 regularization on leaf weights
    "min_child_weight": 5,      # Minimum sum of Hessian in a leaf
    "gamma": 0.1,               # Minimum gain to split a leaf
    "tree_method": "hist",      # Histogram-based split finding (fast)
    "device": "cuda",           # GPU acceleration
}

model = xgb.train(
    params,
    dtrain,
    num_boost_round=1000,
    evals=[(dval, "val")],
    early_stopping_rounds=50,
    verbose_eval=100,
)

preds = model.predict(dval)
print(f"Val AUC: {roc_auc_score(y_val, preds):.4f}")

LightGBM

LightGBM (Microsoft, 2017) addresses XGBoost’s computational bottleneck — finding the best split requires scanning every feature at every split candidate — with two innovations: leaf-wise tree growth and histogram-based split finding.

Leaf-Wise vs. Level-Wise Growth

XGBoost grows trees level-wise: all leaves at depth $d$ are split before any leaf at depth $d+1$. LightGBM grows trees leaf-wise: always split the leaf with the greatest gain, regardless of depth.

Level-wise (XGBoost):          Leaf-wise (LightGBM):

        root                          root
       /    \                        /    \
      A      B     ←depth 1         A      B
     / \    / \                    / \
    C  D   E  F   ←depth 2        C   D    ← only best leaf split
                                 / \
                                G   H   ← continue on best leaf

Leaf-wise growth achieves lower loss with fewer leaves but can overfit on small datasets. The num_leaves hyperparameter (rather than max_depth) is the primary capacity control.

Histogram Binning

LightGBM discretizes continuous features into 256 bins (by default) before training. Each bin stores the sum of gradients and Hessians for training examples in that bin. Split finding scans 256 bin boundaries instead of thousands of unique feature values — up to 20× faster than XGBoost’s exact split algorithm.

GOSS and EFB

GOSS (Gradient-based One-Side Sampling): keep all large-gradient samples (most informative) and randomly sample small-gradient ones. This reduces the training set for split finding without losing much accuracy.

EFB (Exclusive Feature Bundling): sparse features that rarely take non-zero values simultaneously can be bundled together into a single feature — reducing the effective feature dimension.

import lightgbm as lgb

train_data = lgb.Dataset(X_train, label=y_train)
val_data = lgb.Dataset(X_val, label=y_val, reference=train_data)

params = {
    "objective": "binary",
    "metric": "auc",
    "num_leaves": 63,           # Primary depth control (2^max_depth - 1)
    "learning_rate": 0.05,
    "feature_fraction": 0.8,    # Column subsampling (GOSS equivalent)
    "bagging_fraction": 0.8,    # Row subsampling
    "bagging_freq": 5,
    "min_child_samples": 20,    # Minimum samples in a leaf
    "reg_alpha": 0.1,
    "reg_lambda": 1.0,
    "max_bin": 255,
    "device": "gpu",
}

model = lgb.train(
    params,
    train_data,
    num_boost_round=1000,
    valid_sets=[val_data],
    callbacks=[
        lgb.early_stopping(stopping_rounds=50),
        lgb.log_evaluation(100),
    ],
)

preds = model.predict(X_val)

CatBoost

CatBoost (Yandex, 2017) solves the most persistent problem in gradient boosting: target leakage from categorical features. Standard approaches (label encoding, one-hot encoding) or naive target encoding leak target statistics computed over the same examples being trained on.

Ordered Boosting

CatBoost uses ordered boosting: for each training example $i$, the pseudo-residual is computed using a model trained only on examples $1, \ldots, i-1$ (in a random permutation). This ensures no example’s pseudo-residual is influenced by its own target value.

Native Categorical Handling

CatBoost computes ordered target statistics for categorical features — a form of target encoding that avoids leakage:

$$\hat{x}{i,k} = \frac{\sum{j < i, x_{j,k} = x_{i,k}} y_j + \text{prior}}{\sum_{j < i, x_{j,k} = x_{i,k}} 1 + 1}$$

No preprocessing of categorical features is required — pass them directly with cat_features:

from catboost import CatBoostClassifier, Pool

train_pool = Pool(
    X_train,
    label=y_train,
    cat_features=["city", "product_type", "payment_method"],
)
val_pool = Pool(
    X_val,
    label=y_val,
    cat_features=["city", "product_type", "payment_method"],
)

model = CatBoostClassifier(
    iterations=1000,
    learning_rate=0.05,
    depth=6,
    l2_leaf_reg=3.0,
    random_strength=1.0,    # Controls exploration in split finding
    bagging_temperature=0.5,
    eval_metric="AUC",
    task_type="GPU",
    early_stopping_rounds=50,
    verbose=100,
)

model.fit(train_pool, eval_set=val_pool)
preds = model.predict_proba(X_val)[:, 1]

Comparison

Feature Importance and SHAP

All three frameworks provide feature importance. The most reliable measure is SHAP values (Shapley Additive exPlanations), which provide per-prediction attribution with theoretical guarantees:

import shap

# XGBoost SHAP (built-in Tree SHAP — O(TLD²) exact computation)
explainer = shap.TreeExplainer(xgb_model)
shap_values = explainer.shap_values(X_val)

# Summary plot: feature importance + distribution of effects
shap.summary_plot(shap_values, X_val, feature_names=feature_names)

# Waterfall plot: single prediction explanation
shap.waterfall_plot(explainer(X_val[0:1])[0])

Tree SHAP is exact and efficient — no sampling approximation required — because tree structure allows dynamic programming over the exponential number of feature coalitions.

Hyperparameter Tuning Strategy

A practical tuning order:

1. Set learning_rate=0.05, n_estimators=1000 with early stopping — fix trees and LR first
2. Tune max_depth (XGBoost/CatBoost) or num_leaves (LightGBM) — primary capacity control
3. Tune min_child_weight / min_child_samples — controls overfitting at leaf level
4. Tune subsample and colsample_bytree — row/column sampling for variance reduction
5. Tune regularization (reg_alpha, reg_lambda, gamma) — fine-grained overfitting control
6. Lower learning_rate to 0.01–0.02 and increase n_estimators proportionally for final model

import optuna
from sklearn.model_selection import cross_val_score


def objective(trial):
    params = {
        "n_estimators": 1000,
        "learning_rate": 0.05,
        "max_depth": trial.suggest_int("max_depth", 3, 10),
        "min_child_weight": trial.suggest_int("min_child_weight", 1, 20),
        "subsample": trial.suggest_float("subsample", 0.5, 1.0),
        "colsample_bytree": trial.suggest_float("colsample_bytree", 0.5, 1.0),
        "reg_alpha": trial.suggest_float("reg_alpha", 1e-8, 10.0, log=True),
        "reg_lambda": trial.suggest_float("reg_lambda", 1e-8, 10.0, log=True),
        "eval_metric": "auc",
        "tree_method": "hist",
        "early_stopping_rounds": 50,
    }
    model = xgb.XGBClassifier(**params)
    scores = cross_val_score(model, X_train, y_train, cv=5, scoring="roc_auc")
    return scores.mean()


study = optuna.create_study(direction="maximize")
study.optimize(objective, n_trials=100)

Summary

Gradient boosted trees dominate tabular ML because they combine the expressiveness of non-linear decision boundaries with efficient training and natural handling of heterogeneous features:

• XGBoost’s regularized objective and second-order gradients produce robust models with principled pruning via the gain threshold
• LightGBM’s leaf-wise growth and histogram binning achieve the fastest training on large datasets at the cost of slightly higher overfitting risk
• CatBoost’s ordered boosting eliminates target leakage from categorical encoding without any preprocessing, making it the default choice when high-cardinality categorical features are present
• SHAP values with Tree SHAP provide exact, efficient feature attribution for any of these models

For most tabular problems, start with LightGBM for speed during experimentation, then compare CatBoost when categorical features are important, and use SHAP throughout for understanding model behavior.