← back to utils

Histogram Gradient Boosting

How LightGBM & sklearn's HistGradientBoosting actually work

1 · Binbucket features into ≤255 bins
→
2 · Gradientsresiduals of current model
→
3 · Histogram splitscan bins, pick best gain
→
4 · Boostadd tree × learning rate, repeat

Trees: 0  ·  MSE: –  ·  prediction starts at the mean — add a tree to fit the residuals

① Data · Binning · Ensemble Prediction

Raw points (blue), bin edges (faint columns), and the boosted model's prediction (violet staircase). The model only ever splits at bin edges.

② Residuals = Negative Gradients

What the current ensemble gets wrong. For squared loss, the gradient of each point is just its residual — the next tree is fit to these.

③ Gradient Histogram & Split Scan

Per-bin gradient sums (bars) for the next tree's root. The gain curve (pink) is computed with one cheap left-to-right scan; the dashed line marks the winning split.

④ Training Loss

Mean squared error after each boosting round. Small learning rates descend slowly but smoothly; large ones move fast and can overfit the noise.

Why histograms?

1 · Bin once, split forever

Classic gradient boosting must sort every feature at every node to try every possible threshold — O(n log n) per feature, per node. Histogram GBMs discretize each feature into at most 255 buckets once, up front (sklearn uses quantiles, so each bin holds roughly equal data). After that a feature value is just a small integer, and only bin edges are candidate splits. Memory drops too: a uint8 per value instead of a float64.

2 · Trees fit gradients, not targets

Boosting builds the model in rounds: F₀ is a constant (the mean), then each round fits a small tree hₘ to the negative gradient of the loss at the current predictions. For squared error that gradient is simply the residual y − F(x). Fm(x) = Fm−1(x) + η · hm(x) The learning rate η shrinks each step so no single tree dominates — many weak learners, gently stacked.

3 · Split finding is a histogram scan

At each node, accumulate two arrays over its samples: ΣGᵢ (gradient sum) and count per bin — one O(n) pass. Then a single sweep across the ≤255 bins evaluates every candidate split: gain = G²L/nL + G²R/nR − G²/n That's panel ③ above. Bonus — the subtraction trick: a child's histogram equals its parent's minus its sibling's, so only the smaller child needs to be built from data.

4 · Why it wins in practice

Binning caps the split search at 255 candidates regardless of dataset size, histograms are cache-friendly contiguous arrays, and everything parallelizes cleanly. That's why HistGradientBoosting, LightGBM, and XGBoost's hist mode train orders of magnitude faster than exact GBMs on large data — while giving up almost nothing in accuracy, since super-fine thresholds mostly fit noise anyway. Native missing-value and categorical support fall out of the same design: they're just extra bins.