Gradient-Boosted Trees from First Principles: How XGBoost and LightGBM Really Work

Gradient-boosted decision trees (GBDTs) are still the default model for tabular business data: churn, fraud, propensity, credit risk, demand. They train fast, handle mixed feature types and missing values, need little preprocessing, and are hard to beat without very large datasets. They are also easy to use badly. This post derives how they work, so the hyperparameters stop being magic numbers, and then covers how we tune, validate, calibrate and explain them in production.

What is boosting, mathematically?

Boosting builds an additive model one weak learner at a time:

$$F_M(x) = F_0(x) + \sum_{m=1}^{M} \eta\, f_m(x)$$

where each $f_m$ is a small regression tree and $\eta$ is the learning rate (shrinkage). Given a differentiable loss $L(y, F(x))$, each new tree is fitted to reduce the loss of the current ensemble. In classic gradient boosting (Friedman, 2001) the tree is fitted to the negative gradient of the loss with respect to the current prediction, the pseudo-residuals:

$$r_i = -\left.\frac{\partial L(y_i, F)}{\partial F}\right|_{F = F_{m-1}(x_i)}$$

For squared error, $L = \tfrac12 (y - F)^2$, the pseudo-residual is just $y - F$: each tree fits what the previous trees got wrong. For log-loss on binary labels, with $F$ in log-odds space and $p = \sigma(F)$, the gradient is $p - y$. So boosting is gradient descent in function space: each tree is one step, and $\eta$ is the step size.

Why does XGBoost use second-order gradients?

XGBoost (Chen and Guestrin, 2016) takes a second-order Taylor expansion of the loss around the current prediction, and adds an explicit penalty on tree complexity. For a new tree $f$ the objective at step $m$ is approximately:

$$\mathcal{L}^{(m)} \approx \sum_i \left[ g_i f(x_i) + \tfrac12 h_i f(x_i)^2 \right] + \gamma T + \tfrac12 \lambda \sum_{j=1}^{T} w_j^2$$

with $g_i$ and $h_i$ the first and second derivatives of the loss for row $i$, $T$ the number of leaves, and $w_j$ the leaf values.

Loss	$g_i$	$h_i$
Squared error	$\hat y_i - y_i$	$1$
Binary log-loss	$p_i - y_i$	$p_i(1-p_i)$

A tree maps each row to one leaf, so group the sums by leaf. Let $G_j = \sum_{i \in j} g_i$ and $H_j = \sum_{i \in j} h_i$. The objective becomes a sum of independent quadratics in each $w_j$, which we can minimise in closed form:

$$w_j^{*} = -\frac{G_j}{H_j + \lambda}, \qquad \mathcal{L}^{*} = -\tfrac12 \sum_j \frac{G_j^2}{H_j + \lambda} + \gamma T$$

That gives a score for any tree structure, and therefore a gain for any split. Splitting a leaf into left and right children changes the objective by:

$$\text{Gain} = \tfrac12 \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$$

Nearly every XGBoost hyperparameter can be read straight off this formula:

• reg_lambda ($\lambda$) shrinks leaf values towards zero and damps splits on leaves with little hessian mass.
• gamma / min_split_loss ($\gamma$) is the minimum gain a split must achieve. It is pre-pruning.
• min_child_weight is a lower bound on $H$ in each child. For log-loss, $h = p(1-p)$, so a leaf full of confidently predicted rows has tiny hessian mass and cannot be split further. This is not a row count, which surprises people.
• learning_rate ($\eta$) scales each tree's contribution, trading more trees for better generalisation.

The split search in a few lines of NumPy

Here is the core of an exact greedy split search for one feature. It is the real algorithm, minus the engineering.

import numpy as np

def best_split(x: np.ndarray, g: np.ndarray, h: np.ndarray, lam: float = 1.0, gamma: float = 0.0):
    """Return (threshold, gain) of the best split on a single feature.

    x: feature values, g/h: per-row gradient and hessian of the loss.
    """
    order = np.argsort(x, kind="stable")
    x, g, h = x[order], g[order], h[order]
    G, H = g.sum(), h.sum()
    GL = np.cumsum(g)[:-1]            # left-child sums for every candidate cut
    HL = np.cumsum(h)[:-1]
    GR, HR = G - GL, H - HL
    gain = 0.5 * (GL**2 / (HL + lam) + GR**2 / (HR + lam) - G**2 / (H + lam)) - gamma
    valid = x[:-1] != x[1:]           # only cut between distinct values
    if not valid.any():
        return None, 0.0
    gain = np.where(valid, gain, -np.inf)
    k = int(np.argmax(gain))
    return (x[k] + x[k + 1]) / 2, float(gain[k])

# Log-loss gradients for the current predictions p:
# g = p - y;  h = p * (1 - p)

Production libraries never sort per split. That is where the next section comes in.

How do histogram methods and leaf-wise growth make it fast?

Histogram-based splitting. Before training, each feature is bucketed into at most max_bin bins (256 by default in XGBoost's hist method; LightGBM's max_bin defaults to 255). Finding a split then means accumulating $G$ and $H$ per bin, and scanning bins rather than rows. That is linear in rows, cache-friendly and easy to parallelise. A further trick: the parent histogram minus one child's histogram gives the other child's for free. Since XGBoost 2.0, tree_method="hist" is the default.

Depth-wise and leaf-wise growth. XGBoost grows trees level by level by default (grow_policy="depthwise", bounded by max_depth). LightGBM grows leaf-wise: it always splits the leaf with the largest gain, bounded by num_leaves. Leaf-wise trees reach a lower loss with the same number of leaves, but can grow deep and overfit on small data. Constrain them with num_leaves, min_data_in_leaf and max_depth together. A common mistake is setting num_leaves larger than $2^{\text{max\_depth}}$, which makes one of the two limits meaningless.

LightGBM also introduced GOSS (Gradient-based One-Side Sampling: keep rows with large gradients, subsample the rest and reweight them) and EFB (Exclusive Feature Bundling: merge sparse features that are rarely non-zero together). Both cut cost on large, sparse data.

How do GBDTs handle missing values and categorical features?

Missing values. XGBoost and LightGBM learn a default direction for missing values at every split. They evaluate the gain with all missing rows sent left, then right, and keep the better one. Missingness becomes a signal the model can use. Imputing with the mean before training throws that signal away, and is often worse.

Categorical features. One-hot encoding high-cardinality categoricals produces many weak, sparse splits. Better options:

• LightGBM supports native categorical splits. It sorts categories by their gradient statistics and finds the best partition into two groups. Pass the columns as categorical_feature (or the pandas category dtype). Regularise with cat_smooth and min_data_per_group, because native splits can overfit rare categories.
• XGBoost supports categoricals with enable_categorical=True on category-typed pandas columns, using the hist or approx tree methods.
• CatBoost uses ordered target statistics. It encodes each category using target statistics computed only on rows that precede the current row in a random permutation. It combines this with ordered boosting, which avoids the target leakage that naive target encoding causes. It is often the strongest choice when categoricals dominate.

If you target-encode yourself, do it out-of-fold. Encoding with statistics that include the row's own label is one of the most common sources of offline-to-online performance collapse.

How do we tune a GBDT without wasting a week?

Tune in this order. The interactions mostly flow downwards.

1. Fix a smallish learning rate (0.03–0.1) and use early stopping on a validation set to choose the number of trees. Never grid-search n_estimators.
2. Tree complexity: max_depth (XGBoost) or num_leaves (LightGBM), plus min_child_weight / min_data_in_leaf.
3. Randomisation: subsample (row sampling per tree) and colsample_bytree (feature sampling). Values around 0.6–0.9 typically reduce variance.
4. Regularisation: reg_lambda, reg_alpha, gamma.
5. Finally, lower the learning rate and let early stopping add trees, for a last small gain.

import optuna
import xgboost as xgb
from sklearn.metrics import average_precision_score

def objective(trial: optuna.Trial) -> float:
    params = dict(
        n_estimators=5000,                 # upper bound; early stopping picks the real number
        learning_rate=0.05,
        tree_method="hist",
        early_stopping_rounds=200,
        eval_metric="aucpr",
        max_depth=trial.suggest_int("max_depth", 3, 10),
        min_child_weight=trial.suggest_float("min_child_weight", 1e-2, 50, log=True),
        subsample=trial.suggest_float("subsample", 0.5, 1.0),
        colsample_bytree=trial.suggest_float("colsample_bytree", 0.4, 1.0),
        reg_lambda=trial.suggest_float("reg_lambda", 1e-3, 50, log=True),
        reg_alpha=trial.suggest_float("reg_alpha", 1e-3, 10, log=True),
        gamma=trial.suggest_float("gamma", 0.0, 5.0),
    )
    model = xgb.XGBClassifier(**params)
    model.fit(X_train, y_train, eval_set=[(X_valid, y_valid)], verbose=False)
    trial.set_user_attr("best_iteration", model.best_iteration)
    return average_precision_score(y_valid, model.predict_proba(X_valid)[:, 1])

study = optuna.create_study(direction="maximize", sampler=optuna.samplers.TPESampler(seed=42))
study.optimize(objective, n_trials=60)

Two notes. First, keep a third, untouched test set. The validation set is consumed by early stopping and tuning, so its score is optimistically biased. Second, pick the metric that matches the decision. For imbalanced problems, area under the precision–recall curve (aucpr) is usually more informative than ROC AUC.

How should you validate a tabular model?

Most "the model was great offline and useless in production" stories are validation failures, not algorithm failures.

• Time-based splits for anything that will predict the future. Train on the past and validate on a later period. Random K-fold on temporal data leaks future patterns into training.
• Group-aware splits (GroupKFold) when several rows belong to one entity, such as a customer or device, so the same entity never appears in both train and validation.
• Point-in-time correct features. Every feature must be computed only from data available at prediction time. In a lakehouse this means joining features as of the event timestamp, not "latest value".
• Leakage audits. If one feature dominates importance and looks too good, assume leakage until proven otherwise.

What about class imbalance and calibration?

For rare positives such as fraud, you have two levers: reweight the classes (scale_pos_weight in XGBoost, is_unbalance or scale_pos_weight in LightGBM), or leave the weights alone and choose the decision threshold carefully. Reweighting can improve ranking slightly, but it distorts the predicted probabilities. The model will systematically overestimate risk.

If downstream decisions use probabilities directly (expected loss, pricing, budget allocation), calibrate on a held-out set and check a reliability curve:

from sklearn.calibration import CalibratedClassifierCV, calibration_curve
from sklearn.frozen import FrozenEstimator   # scikit-learn >= 1.6

calibrated = CalibratedClassifierCV(FrozenEstimator(model), method="isotonic")
calibrated.fit(X_calib, y_calib)              # a separate calibration split, not the training data

prob_true, prob_pred = calibration_curve(y_test, calibrated.predict_proba(X_test)[:, 1], n_bins=15)

Use isotonic regression when you have thousands of calibration rows. Use method="sigmoid" (Platt scaling) when you have fewer.

How do we explain GBDT predictions?

Built-in feature importance is a weak guide. Split count ("weight") is biased towards high-cardinality features. Gain is better, but it is still a global, model-internal statistic. For trees, SHAP values computed with the TreeSHAP algorithm are exact for the model, and run in polynomial time:

import shap

explainer = shap.TreeExplainer(model)
sv = explainer(X_test.sample(2000, random_state=0))
shap.plots.beeswarm(sv)          # global: direction and spread of each feature's effect
shap.plots.waterfall(sv[0])      # local: why this one row got its score

SHAP explains the model, not the world. Correlated features share credit in ways that can mislead. Use SHAP to debug and communicate, not to make causal claims.

When is a GBDT the wrong choice?

• Extrapolation. Trees predict piecewise constants learned from the training range. Outside the range of the training features their prediction is flat, so they cannot extrapolate a trend. For trending targets, model the trend separately or predict differences or ratios.
• Unstructured data. Images, audio and free text are better served by neural networks. A good pattern is to feed embeddings from those models into a GBDT, alongside tabular features.
• Very smooth or monotone relationships with small data. A regularised linear or generalised additive model may generalise better and be easier to defend. If business logic demands monotonicity (higher income should never raise credit risk), use monotone_constraints, which XGBoost and LightGBM both support.

How do we run this at scale?

On Databricks we usually train on a single large node. GBDTs on tens of millions of rows fit comfortably in memory with the histogram method. We distribute the tuning trials rather than the training. When the data truly does not fit, xgboost.spark (SparkXGBClassifier / SparkXGBRegressor) trains across a Spark cluster. Every run logs parameters, metrics, the feature list and the training-data version to MLflow. The model is registered in Unity Catalog, so the exact model scored in production can be traced back to its data and code. How we take that to production is covered in our productionisation playbook.

Key takeaways

• Boosting is gradient descent in function space. XGBoost's second-order objective yields closed-form leaf weights and the split-gain formula behind most hyperparameters.
• Histogram binning and leaf-wise growth are what make modern GBDTs fast. Leaf-wise trees need num_leaves and minimum-leaf-size constraints.
• Let the model handle missing values. Use native or out-of-fold categorical encodings.
• Tune with early stopping and a fixed learning rate first, validate with time- and group-aware splits, and keep an untouched test set.
• Reweighting classes distorts probabilities, so calibrate when probabilities drive decisions. Explain with TreeSHAP, not split counts.

References

• J. H. Friedman, Greedy Function Approximation: A Gradient Boosting Machine, Annals of Statistics, 2001.
• T. Chen and C. Guestrin, XGBoost: A Scalable Tree Boosting System, KDD 2016.
• G. Ke et al., LightGBM: A Highly Efficient Gradient Boosting Decision Tree, NeurIPS 2017.
• L. Prokhorenkova et al., CatBoost: Unbiased Boosting with Categorical Features, NeurIPS 2018.
• S. Lundberg et al., From Local Explanations to Global Understanding with Explainable AI for Trees, Nature Machine Intelligence, 2020.