Distributed Gradient Boosting

"Each of us learns only what the trees before us got wrong. You cannot rush ahead and fix a mistake that has not been made yet."

A Boosting Round Waiting Its Turn

The previous section built random forests, where hundreds of trees are grown independently on bootstrap samples and then averaged. Independence is what made them trivial to distribute: hand each worker a subset of trees, grow them in isolation, collect the forest at the end, and never communicate during training. Gradient boosting throws that gift away. It also grows many trees, but it grows them in a strict sequence, each one correcting the ensemble that precedes it. You cannot grow tree number fifty until trees one through forty-nine exist, because tree fifty is defined entirely by their collective error. The parallelism that distributes boosting therefore lives at a completely different level, and finding it is the whole story of this section.

1. Why Boosting Refuses to Parallelize Across Trees Intermediate

Gradient boosting builds an additive model. After $t-1$ rounds the ensemble predicts a score $F_{t-1}(x)$, and round $t$ adds one more tree $f_t$ scaled by a learning rate $\eta$, so that $F_t(x) = F_{t-1}(x) + \eta\, f_t(x)$. The new tree is not fit to the labels; it is fit to how wrong the current ensemble is. Concretely, for a differentiable loss $\ell(y, F)$ we compute, for every training example, the first and second derivatives of the loss with respect to the current score,

the gradient $g_i$ and the Hessian $h_i$. The tree $f_t$ is then grown to predict a step that reduces a second-order Taylor approximation of the loss around the current scores. The dependence is total: $g_i$ and $h_i$ are functions of $F_{t-1}$, which is the sum of every tree built so far. Change one earlier tree and every later gradient changes. This is exactly the sequential structure of the synchronous-versus-asynchronous trade-off introduced in Chapter 10, except here the sequence is intrinsic to the algorithm rather than a choice about how to schedule updates.

2. Splitting on Gradients: the Histogram Inside Each Round Intermediate

Inside one round, growing the tree means repeatedly choosing the best feature and threshold to split a node. Boosting scores a candidate split not by Gini impurity or variance, as an ordinary decision tree would, but by how much it reduces the second-order loss. If a node holds a set of examples and a candidate split sends some to the left child and the rest to the right, define $G = \sum g_i$ and $H = \sum h_i$ summed over the examples in a child. The standard XGBoost split gain is

where $\lambda$ is an $L_2$ regularizer on leaf weights and $\gamma$ is a complexity penalty per split. The optimal weight assigned to a leaf holding totals $(G, H)$ is $w^\star = -G / (H + \lambda)$. The crucial observation for distribution is that the gain depends on the data only through the sums $G_L, H_L, G_R, H_R$. To evaluate every candidate threshold for a feature, you do not need the raw rows; you need the gradient sum and Hessian sum in each bin of that feature. That is precisely a histogram: bin the feature values once, then accumulate $g_i$ and $h_i$ into per-bin buckets. Sweeping the bins left to right gives every candidate split's $(G_L, H_L)$ as a running prefix sum, so one pass over a histogram of $B$ bins evaluates all $B-1$ thresholds.

This is where the data-parallel structure of Chapter 4 reappears. A histogram is additive: the global gradient/Hessian histogram over all rows equals the sum of the per-shard histograms, exactly as the global gradient in Section 1.1 was the sum of per-shard partial gradients. So each worker bins its own shard, builds a small local histogram of size (number of features $\times$ number of bins), and the cluster all-reduces those histograms. After the all-reduce every worker holds the identical global histogram and therefore independently picks the identical best split, with no further communication. Figure 12.5.1 traces the full pattern: trees in sequence, and within each tree a single all-reduce of histograms across the shards.

3. A Runnable Distributed Boosting Round Intermediate

The code below implements a few rounds of gradient boosting from scratch in pure NumPy, with the split-finding step distributed exactly as Figure 12.5.1 describes. To keep the geometry visible we use a single numeric feature, bin it into a shared quantile sketch once, and grow a one-split stump per round (the depth-one case shows the all-reduce without burying it in tree-recursion bookkeeping). Each round computes the log-loss gradient $g_i = p_i - y_i$ and Hessian $h_i = p_i(1-p_i)$ at the current scores, every shard builds its local histogram, the histograms are summed (the all-reduce), and the global histogram drives the split gain and leaf weights from Section 2. A second function repeats the same boosting over all the data in one pass, with no shards, so we can check the two agree.

import numpy as np

rng = np.random.default_rng(7)
N, K, ROUNDS, BINS = 4000, 4, 6, 16
LR, LAMBDA = 0.3, 1.0

# One numeric feature, a non-linear target -> binary labels.
x = rng.uniform(-3.0, 3.0, N)
prob = 1.0 / (1.0 + np.exp(-(1.5 * np.sin(1.3 * x) + 0.6 * x)))
y = (rng.uniform(size=N) < prob).astype(np.float64)

# Shared bin edges (a pre-agreed quantile sketch). Each example -> a bin id.
edges = np.quantile(x, np.linspace(0, 1, BINS + 1))
bin_id = np.clip(np.digitize(x, edges[1:-1]), 0, BINS - 1)
shards = np.array_split(np.arange(N), K)             # K disjoint data shards

def best_split_from_hist(g_hist, h_hist, lam):       # sweep bins, max the gain
    G_tot, H_tot = g_hist.sum(), h_hist.sum()
    best_b, best_gain, GL, HL = -1, -np.inf, 0.0, 0.0
    for b in range(BINS - 1):
        GL += g_hist[b]; HL += h_hist[b]
        GR, HR = G_tot - GL, H_tot - HL
        gain = GL*GL/(HL+lam) + GR*GR/(HR+lam) - G_tot*G_tot/(H_tot+lam)
        if gain > best_gain: best_gain, best_b = gain, b
    return best_b, best_gain

def fit_distributed():
    F = np.zeros(N)                                  # ensemble score, all examples
    for r in range(ROUNDS):
        p = 1.0 / (1.0 + np.exp(-F))
        grad, hess = p - y, p * (1 - p)              # log-loss gradient and Hessian
        # ---- each shard builds a LOCAL gradient/Hessian histogram over bins ----
        g_local = np.zeros((K, BINS)); h_local = np.zeros((K, BINS))
        for k, s in enumerate(shards):
            np.add.at(g_local[k], bin_id[s], grad[s])
            np.add.at(h_local[k], bin_id[s], hess[s])
        # ---- ALL-REDUCE: sum the per-shard histograms into ONE global one ----
        g_hist, h_hist = g_local.sum(axis=0), h_local.sum(axis=0)
        b, gain = best_split_from_hist(g_hist, h_hist, LAMBDA)
        GL, HL = g_hist[:b+1].sum(), h_hist[:b+1].sum()
        GR, HR = g_hist[b+1:].sum(), h_hist[b+1:].sum()
        wL, wR = -GL/(HL+LAMBDA), -GR/(HR+LAMBDA)    # optimal leaf weights
        F = F + LR * np.where(bin_id <= b, wL, wR)   # add the stump to the ensemble
        p = np.clip(1/(1+np.exp(-F)), 1e-12, 1-1e-12)
        loss = float(np.mean(-(y*np.log(p) + (1-y)*np.log(1-p))))
        print(f"round {r+1}: split@bin {b:2d}  gain {gain:8.2f}  "
              f"leaf(L,R)=({wL:+.3f},{wR:+.3f})  log-loss {loss:.5f}")
    return F

Running it prints the per-round log-loss and then compares the distributed final scores against a single-machine baseline that boosts over all the rows in one pass.

data N=4000  shards K=4  rounds=6  bins=16
start log-loss      : 0.69315

round 1: split@bin  7  gain  1597.03  leaf(L,R)=(-1.287,+1.238)  log-loss 0.59115
round 2: split@bin  8  gain   821.44  leaf(L,R)=(-0.832,+1.025)  log-loss 0.53857
round 3: split@bin  6  gain   490.42  leaf(L,R)=(-0.846,+0.636)  log-loss 0.50717
round 4: split@bin  7  gain   288.66  leaf(L,R)=(-0.598,+0.569)  log-loss 0.48867
round 5: split@bin  8  gain   167.70  leaf(L,R)=(-0.409,+0.522)  log-loss 0.47794
round 6: split@bin  6  gain   101.94  leaf(L,R)=(-0.439,+0.312)  log-loss 0.47141

final log-loss (K=4 shards, all-reduced) : 0.47141
final log-loss (single machine)            : 0.47141
max abs score difference                   : 1.78e-15

The agreement to fifteen decimal places is the same exactness guarantee that data parallelism gave us for gradient descent, now riding on the additivity of histograms instead of the additivity of gradients. The workers never share rows; they share a sum of small per-bin statistics, and the resulting splits are bit-for-bit the ones a single machine would have chosen. That is what lets a distributed XGBoost or LightGBM job claim it produces the same model as its single-node counterpart, only faster and on data that would never fit on one box.

4. Data-Parallel and Feature-Parallel Modes Advanced

Code 12.5.1 distributes by rows, the data-parallel mode: each worker owns a shard of examples, builds histograms over its rows, and the cluster all-reduces. This is the default in distributed XGBoost and LightGBM because the communication volume per round depends only on the histogram size (features $\times$ bins), not on the number of rows, so it scales to enormous datasets. There is a second axis. In feature-parallel mode each worker owns a subset of the columns, finds the best split among its own features, and the workers exchange only their local best splits to agree on a global winner; the chosen split then has to be broadcast so everyone can partition their rows. Feature parallelism helps when there are very many features but it forces the workers to communicate row-partitioning information every split, which is why row partitioning dominates in practice. Real systems combine both, and they overlap the histogram all-reduce with computation just as the communication-avoiding training of Chapter 10 overlaps gradient all-reduce with the backward pass.

The two flagship systems made boosting scale through a stack of complementary ideas. XGBoost introduced an approximate split-finding algorithm that proposes candidate thresholds from a weighted quantile sketch (weighting each example by its Hessian $h_i$, because high-Hessian points matter more to the second-order objective), plus a sparsity-aware split finder that learns a default direction for missing values and skips absent entries, which is what lets it tear through sparse one-hot and click data. LightGBM pushed the histogram idea further with leaf-wise (best-first) tree growth instead of level-wise, gradient-based one-side sampling (GOSS), which keeps all the large-gradient examples and subsamples the small-gradient ones to shrink the per-round work, and exclusive feature bundling (EFB), which packs mutually-exclusive sparse features into a single column to cut the histogram cost. All of these accelerate the same inner loop: build histograms, all-reduce them, split.

# XGBoost on a Dask cluster: rows are sharded, histograms all-reduced per round.
import xgboost as xgb
from xgboost import dask as dxgb

dtrain = dxgb.DaskDMatrix(client, X, y)            # X, y are distributed Dask arrays
out = dxgb.train(client, {"tree_method": "hist", "objective": "binary:logistic",
                          "eta": 0.3, "lambda": 1.0},
                 dtrain, num_boost_round=200)       # cluster all-reduces histograms

# LightGBM in data-parallel mode (one process per worker):
import lightgbm as lgb
params = {"objective": "binary", "tree_learner": "data",   # data-parallel histograms
          "num_leaves": 63, "learning_rate": 0.05}
booster = lgb.train(params, lgb.Dataset(X_local, y_local), num_boost_round=200)

5. Why Boosted Trees Still Beat Deep Nets on Tables Beginner

It is worth asking why this fifteen-year-old family of models remains the default for tabular problems when deep learning has swept image, text, and audio. Tabular data is heterogeneous: columns mix scales, units, and meanings, many features are uninformative, and the useful signal often sits in sharp, axis-aligned thresholds ("flag the transaction if amount exceeds X and the account age is under Y"). Decision trees model exactly those axis-aligned, non-smooth interactions natively, while a neural network must learn them through smooth compositions of weighted sums, which is a harder fit on the modest dataset sizes typical of tabular problems. Boosting then squeezes the residual signal out greedily, round after round. The result is a model that needs little preprocessing, tolerates irrelevant and correlated features, handles missing values directly, and trains fast. For the great majority of business tables, that combination still wins on accuracy per unit of engineering effort, which is why distributing boosting well, rather than replacing it, is the high-value move.

With boosting distributed by all-reducing histograms inside each round, we have now covered the three big supervised tree families: single trees (Section 12.3), forests of independent trees (Section 12.4), and the sequential, communication-coupled boosted ensemble here. The chapter turns next from supervised prediction to unsupervised structure. Section 12.6 distributes clustering, where the quantity that becomes additive across shards is no longer a gradient or a histogram but the per-cluster point sums that define each centroid.