Gradient-boosted decision trees (GBDT)

Deep dive

How it works

Parts:

• binned matrix — each feature quantized to u8, column-major
• gradient arrays — g_i, h_i per row, recomputed each round
• histogram builder — (G, H) sums per feature and bin
• split finder — prefix scan over bins scoring the gain formula
• tree ensemble — leaves with weights, summed with learning rate η
• validation loop — early stopping on a held-out metric

1. Bin each feature once by quantiles into ≤ 255 bins plus one for missing. Store as u8, column-major.
2. Init F₀ = argmin_c Σ loss(y, c) (log-odds of the mean for logistic).
3. For each round m: a. Compute g_i, h_i at the current predictions. b. Histogram: for the node's rows, for each feature f, hist[f][bin] += (g_i, h_i). c. Split search: scan bins left to right accumulating (G_L, H_L). G_R = G − G_L. Score with the gain formula. Respect min_child_weight (H) and min_data_in_leaf. d. Partition rows by the best (feature, bin). Build the smaller child's histogram; the sibling is parent − smaller. e. Stop at max depth or max leaves (LightGBM grows leaf-wise: always split the leaf with the largest gain). f. Leaf values w = −G/(H+λ). Update F += η·tree(x).
4. Stop on a validation metric with early stopping.

feature f bins:  0    1    2    3    4    5        G = ΣG_b, H = ΣH_b
(G_b, H_b):     ...  ...  ...  ...  ...  ...
threshold after bin k: left = prefix sum up to k, right = total − left → gain(k); best over all f, k

Code

/// Histogram GBDT with logistic loss. bins: column-major u8 [feature][row].
pub struct Params { pub depth: usize, pub lambda: f64, pub gamma: f64, pub min_hess: f64, pub eta: f64, pub nbins: usize }
pub enum Node { Leaf(f64), Split { f: usize, bin: u8, left: Box<Node>, right: Box<Node> } } // go left if bin <= threshold

type Hist = Vec<(f64, f64)>;                                           // [feature * nbins + bin] -> (G, H)

fn build_hist(bins: &[Vec<u8>], rows: &[u32], g: &[f64], h: &[f64], nb: usize) -> Hist {
    let mut hist = vec![(0.0, 0.0); bins.len() * nb];
    for (f, col) in bins.iter().enumerate() {
        let hf = &mut hist[f * nb..(f + 1) * nb];
        for &r in rows { let e = &mut hf[col[r as usize] as usize]; e.0 += g[r as usize]; e.1 += h[r as usize]; }
    }
    hist
}

/// Best (gain, feature, bin) over all thresholds, from one histogram.
fn best_split(hist: &Hist, nf: usize, p: &Params) -> Option<(f64, usize, u8)> {
    let score = |g: f64, h: f64| g * g / (h + p.lambda);
    let mut best: Option<(f64, usize, u8)> = None;
    for f in 0..nf {
        let hf = &hist[f * p.nbins..(f + 1) * p.nbins];
        let (gt, ht) = hf.iter().fold((0.0, 0.0), |a, b| (a.0 + b.0, a.1 + b.1));
        let (mut gl, mut hl) = (0.0, 0.0);
        for b in 0..p.nbins - 1 {
            gl += hf[b].0; hl += hf[b].1;
            let (gr, hr) = (gt - gl, ht - hl);
            if hl < p.min_hess || hr < p.min_hess { continue; }
            let gain = 0.5 * (score(gl, hl) + score(gr, hr) - score(gt, ht)) - p.gamma;
            if gain > best.map_or(0.0, |x| x.0) { best = Some((gain, f, b as u8)); }
        }
    }
    best
}

fn grow(bins: &[Vec<u8>], rows: Vec<u32>, hist: Hist, g: &[f64], h: &[f64], p: &Params, depth: usize) -> Node {
    let (gs, hs) = hist[..p.nbins].iter().fold((0.0, 0.0), |a, b| (a.0 + b.0, a.1 + b.1)); // totals from feature 0
    let leaf = Node::Leaf(-gs / (hs + p.lambda));
    if depth == p.depth { return leaf; }
    let Some((_, f, bin)) = best_split(&hist, bins.len(), p) else { return leaf };
    let (l, r): (Vec<u32>, Vec<u32>) = rows.iter().partition(|&&i| bins[f][i as usize] <= bin);
    let small_is_left = l.len() <= r.len();
    let small = build_hist(bins, if small_is_left { &l } else { &r }, g, h, p.nbins);
    let large: Hist = hist.iter().zip(&small).map(|(a, b)| (a.0 - b.0, a.1 - b.1)).collect(); // subtraction trick
    let (hl, hr) = if small_is_left { (small, large) } else { (large, small) };
    Node::Split { f, bin, left: Box::new(grow(bins, l, hl, g, h, p, depth + 1)),
                  right: Box::new(grow(bins, r, hr, g, h, p, depth + 1)) }
}

fn predict(node: &Node, bins: &[Vec<u8>], row: usize) -> f64 {
    match node {
        Node::Leaf(w) => *w,
        Node::Split { f, bin, left, right } => predict(if bins[*f][row] <= *bin { left } else { right }, bins, row),
    }
}

/// Quantile binning of one raw column into at most nbins u8 codes.
pub fn quantize(col: &[f64], nbins: usize) -> Vec<u8> {
    let mut s = col.to_vec();
    s.sort_by(|a, b| a.partial_cmp(b).unwrap());
    let cuts: Vec<f64> = (1..nbins).map(|k| s[k * s.len() / nbins]).collect();
    col.iter().map(|v| cuts.partition_point(|c| c <= v) as u8).collect()
}

pub fn boost(bins: &[Vec<u8>], y: &[f64], rounds: usize, p: &Params) -> (f64, Vec<Node>) {
    let n = y.len();
    let mean = y.iter().sum::<f64>() / n as f64;
    let base = (mean / (1.0 - mean)).ln();                             // log-odds init
    let mut f = vec![base; n];
    let mut trees = Vec::new();
    for _ in 0..rounds {
        let pr: Vec<f64> = f.iter().map(|z| 1.0 / (1.0 + (-z).exp())).collect();
        let g: Vec<f64> = pr.iter().zip(y).map(|(p, y)| p - y).collect();
        let h: Vec<f64> = pr.iter().map(|p| (p * (1.0 - p)).max(1e-16)).collect();
        let rows: Vec<u32> = (0..n as u32).collect();
        let hist = build_hist(bins, &rows, &g, &h, p.nbins);
        let tree = grow(bins, rows, hist, &g, &h, p, 0);
        for i in 0..n { f[i] += p.eta * predict(&tree, bins, i); }
        trees.push(tree);
    }
    (base, trees)
}

fn main() {
    let n = 5000;
    let mut s = 88172645463325252u64;
    let mut u = || { s ^= s << 13; s ^= s >> 7; s ^= s << 17; (s >> 11) as f64 / (1u64 << 53) as f64 };
    let x: Vec<Vec<f64>> = (0..3).map(|_| (0..n).map(|_| u() * 4.0 - 2.0).collect()).collect();
    let y: Vec<f64> = (0..n).map(|i| {
        let clean = x[0][i] * x[1][i] > 0.0;                            // XOR-like interaction, x[2] is noise
        (clean != (u() < 0.1)) as u8 as f64                             // flip 10 % of labels
    }).collect();
    let p = Params { depth: 3, lambda: 1.0, gamma: 0.0, min_hess: 1.0, eta: 0.3, nbins: 64 };
    let bins: Vec<Vec<u8>> = x.iter().map(|c| quantize(c, p.nbins)).collect();
    let (base, trees) = boost(&bins, &y, 50, &p);
    let acc = (0..n).filter(|&i| {
        let z = base + trees.iter().map(|t| p.eta * predict(t, &bins, i)).sum::<f64>();
        (z > 0.0) == (y[i] > 0.5)
    }).count() as f64 / n as f64;
    println!("train accuracy on XOR-like target with 10% label noise: {acc:.3} (ceiling about 0.9)");
}

Complexity and constants

• Histogram build is the hot loop: one random-access add of (g, h) per row per feature, about n·f operations per tree level, memory-bound on the gradient arrays. Row-major u8 bins with gradients packed next to them improve locality; GPUs use shared-memory atomics.
• Split search: leaves × f × bins per level, negligible next to building when n ≫ bins.
• Binning: 1 byte per value instead of 4-8. 10⁸ rows × 100 features = 10 GB of bins.
• Prediction: trees × depth branches per row. 1000 trees of depth 6 is order of 1-10 µs per row on one core. Oblivious trees (CatBoost) evaluate as a bit index and vectorize well.

Efficiency

• Cost: training is memory-bound on the histogram build: one random-access add of (g, h) per row per feature per tree level, about n·f operations. Bins take 1 byte per value, so 10⁸ rows × 100 features is 10 GB (this page). Prediction is trees × depth branches per row, 1000 trees of depth 6 order of 1-10 µs per row on one core (this page); branch mispredictions bound it.
• Levers:
  • Histogram binning to at most 255 bins — no per-node sorting, 1 byte per value (XGBoost, LightGBM) — default for any large n.
  • Histogram subtraction — build the smaller child, get the sibling as parent minus child (LightGBM docs) — every split.
  • GOSS plus EFB — up to over 20x faster with almost the same accuracy (Ke 2017) — large n or sparse, bundled features.
  • Oblivious trees or compiled trees — branch-free index lookup, vectorizes (CatBoost, Treelite) — latency-critical serving.
• Naive → standard → state of the art:
  • Exact greedy splits, sort every feature at every node · O(n log n · f) per level
  • Histogram GBT with fixed bins · O(n·f) per level
  • Histogram plus subtraction, GOSS/EFB, GPU build · up to over 20x faster than conventional GBDT (Ke 2017)

Implementation notes

• Missing values: one dedicated bin. Try sending it left and right at every split and keep the better (XGBoost's learned default direction).
• Categoricals: LightGBM sorts categories by G/H within a node and splits that order (Fisher's method). CatBoost uses ordered target statistics. One-hot works for low cardinality.
• Regularize with η 0.03-0.1 and more rounds, min_child_weight/min_data_in_leaf, λ, row subsampling (0.5-0.9) and column subsampling.
• Early stopping on a validation set with patience of order of 50-200 rounds. Report the best iteration, and predict with it.
• Parallelize over features in histogram building (or over row blocks with per-thread histograms, then reduce). Distributed training all-reduces histograms, not rows.
• Storing gradients as f32 halves the traffic of the histogram build. Accumulate histograms in f64 when n is large to avoid round-off in G and H.

Pitfalls

• Target leakage through features computed with future data or with target statistics on the full training set.
• Leaf-wise growth with large num_leaves and small data overfits quickly. Cap max_depth too.
• Too few bins for features with fine-grained signal (timestamps, IDs mapped to numbers). Raise max_bin or engineer the feature.
• Comparing models across different early-stopping points on the test set.
• Probabilities from boosted logistic models are reasonably calibrated but not exactly. Check reliability (calibration), especially after class re-weighting.

Variants and alternatives

In production

XGBoost, LightGBM, CatBoost, scikit-learn HistGradientBoostingClassifier (LightGBM-style, 255 bins), Spark MLlib GBT. Used for search ranking (LambdaMART), ad click prediction, high-energy physics event classification, store sales forecasting, fraud and credit scoring, and Kaggle tabular competitions.

Implementations

Sources

• Friedman, Greedy Function Approximation: A Gradient Boosting Machine, Annals of Statistics 2001. paper
• Chen and Guestrin, XGBoost: A Scalable Tree Boosting System, KDD 2016. paper · code
• Ke et al., LightGBM: A Highly Efficient Gradient Boosting Decision Tree, NeurIPS 2017. paper · code
• Prokhorenkova et al., CatBoost: Unbiased Boosting with Categorical Features, NeurIPS 2018. paper · code
• Burges, From RankNet to LambdaRank to LambdaMART: An Overview, Microsoft Research TR 2010. paper
• Grinsztajn, Oyallon, Varoquaux, Why Do Tree-Based Models Still Outperform Deep Learning on Typical Tabular Data?, NeurIPS 2022. paper