LightGBM regression

Gradient boosting with histogram-binned features and leaf-wise growth, trading a little exactness for large speed-ups.

18 min read2367 wordsadvanced15 viewsupdated 2026-10-07

Definition

LightGBM regression predicts a number as a constant plus a sum of shrunken regression trees, y^=F0+η∑tft(x)\hat y = F_0 + \eta\sum_{t} f_t(x) — the same model as every gradient-boosted tree ensemble. What makes it LightGBM is how each tree is grown: every feature is bucketed once into at most a few hundred bins, splits are searched over bin edges using per-bin gradient histograms, and the tree grows leaf-wise — always splitting the single leaf, anywhere in the tree, whose split lowers the loss most.

At a glance

Task
Regression (squared error by default; also L1, Huber, quantile, Poisson, Gamma, Tweedie, MAPE objectives)
Input → output
feature vector xx → real number y^=F0+η∑t=1Tft(x)\hat y = F_0 + \eta\sum_{t=1}^{T} f_t(x)
Learns
bin edges per feature (once, before training); then TT trees, each with a (feature, bin edge) per internal node and a weight ww per leaf
Training
binning once: O(n dlog⁡n)O(n\,d\log n); per tree: building histograms O(n d)O(n\,d) (less with subtraction and GOSS), scanning them O(leaves⋅d⋅B)O(\text{leaves}\cdot d\cdot B) — independent of nn
Prediction
O(T⋅depth)O(T\cdot\text{depth}) comparisons; depth is not bounded by default, so leaf-wise trees can be deep and lopsided
Key hyperparameters
num_leaves, learning_rate, n_estimators, min_data_in_leaf, max_bin, lambda_l2 / lambda_l1, max_depth, feature_fraction, bagging_fraction
Assumes
a differentiable loss (absolute / quantile losses get a leaf re-fit); nothing about feature distributions; no scaling needed, only the order of values (and their bin) matters; the fit is axis-aligned and piecewise constant

The problem

A gradient-boosted tree ensemble (see Gradient boosting regression for the residual-fitting idea and XGBoost regression for the second-order leaf weights) spends almost all of its training time in one place: finding the best split. The exact greedy method sorts every feature and tries every midpoint between consecutive values — n−1n-1 candidates per feature per node. With n=107n = 10^7 rows and d=100d = 100 features, every node of every tree walks a billion (row, feature) pairs, and the pre-sorted index arrays alone are several times the size of the data.

A second, quieter waste is how trees are grown. Classic implementations grow level by level: every leaf at depth 2 is split before any leaf at depth 3, even leaves whose best split barely helps. With a fixed budget of leaves, a level-wise tree spends many of them on near-useless splits while a high-error region of the data waits for the next level.

LightGBM (Ke et al., Microsoft, 2017) attacks both. It gives up on testing every threshold — it tests only bin edges, and finds that this almost never hurts accuracy — and it gives up on balanced trees, spending each leaf where the loss drops most. On the 50,000-row benchmark later in this article, it matches an exact-split learner's test error while training about 80× faster.

The idea

Think of a split search as asking, for each candidate threshold, "how much would the squared error drop if I cut here?". To answer that you only need two running totals on each side: the sum of gradients GG and the sum of hessians HH (for squared error, HH is just the row count). Those totals do not care about the exact xx values, only which side of the cut each row falls. So LightGBM pre-sorts nothing; it drops every row into a bucket (bin) once, and for each tree node it adds up gg and hh per bucket. A split is then a cut between buckets, and its score comes from prefix sums over at most a few hundred numbers — no matter whether the node holds 50 rows or 50 million.

Three more tricks then stack on top. The histogram of one child can be subtracted from the parent's to get the other child for free. Growth is leaf-wise: compare the best split of every current leaf and make only the best one. And two sampling tricks shrink the histogram-building work itself: GOSS drops many rows whose gradient is already small, and EFB merges sparse features that are never non-zero together into one.

Vocabulary

Bin
a contiguous range of one feature's values; each row stores only its bin number (a small integer) per feature
Bin edge (upper bound)
the threshold between two neighbouring bins, placed halfway between data values. The only thresholds LightGBM ever tests
max_bin
maximum number of bins per feature (default 255). Bins are roughly equal-count, so dense regions get narrow bins
Gradient histogram
for one leaf and one feature: per bin, the sums Gb=∑giG_b=\sum g_i and Hb=∑hiH_b=\sum h_i (and the row count) of the rows in that leaf that fall in bin bb
Histogram subtraction
hist(sibling)=hist(parent)−hist(child)\text{hist}(\text{sibling}) = \text{hist}(\text{parent}) - \text{hist}(\text{child}): after a split, build only the smaller child's histogram
Leaf-wise (best-first) growth
repeatedly split the leaf with the largest gain anywhere in the tree, until the tree has num_leaves leaves or no split gains anything
Level-wise (depth-wise) growth
split all leaves at one depth before going deeper (XGBoost's classic default)
num_leaves
the leaf budget per tree (default 31); the main complexity knob, instead of depth
min_data_in_leaf
minimum rows a leaf may hold (default 20); min_sum_hessian_in_leaf is the same on H
GOSS
Gradient-based One-Side Sampling: keep the rows with the largest |g|, subsample the rest and up-weight them
EFB
Exclusive Feature Bundling: pack sparse features that are (almost) never non-zero on the same row into one feature with offset bins

The math

What the trees minimize. LightGBM uses the same regularized second-order objective as XGBoost; the derivation is spelled out in XGBoost regression, so here is the short version for squared error. The model after t−1t-1 trees is FF; the next tree adds ftf_t.

L=∑i=1n12(yi−F(xi)−ft(xi))2+12λ∑jwj2,gi=F(xi)−yi,hi=1\mathcal L = \sum_{i=1}^{n}\tfrac12\big(y_i - F(x_i) - f_t(x_i)\big)^2 + \tfrac12\lambda\sum_{j}w_j^2,\qquad g_i = F(x_i)-y_i,\quad h_i = 1
yi, xiy_i,\ x_i
target and feature vector of training row i
F(xi)F(x_i)
the current ensemble's prediction for row i
ftf_t
the new tree; it outputs weight wjw_j for every row in its leaf jj
gi, hig_i,\ h_i
first and second derivative of 12(yi−F)2\tfrac12(y_i-F)^2 with respect to FF: minus the residual, and 1
λ\lambda
L2 penalty on leaf weights (lambda_l2, default 0)

Leaf weight. All rows in leaf jj get the same wjw_j, so that leaf's part of L\mathcal L is (up to a constant) Gjwj+12(Hj+λ)wj2G_j w_j + \tfrac12 (H_j+\lambda) w_j^2 with Gj=∑i∈jgiG_j=\sum_{i\in j} g_i, Hj=∑i∈jhiH_j = \sum_{i\in j}h_i. For squared error this is exact, not an approximation. Setting the derivative to zero:

wj∗=−GjHj+λ⟹Lj∗=−12 Gj2Hj+λw_j^{*} = -\frac{G_j}{H_j+\lambda}\qquad\Longrightarrow\qquad \mathcal L_j^{*} = -\frac12\,\frac{G_j^2}{H_j+\lambda}
Gj, HjG_j,\ H_j
sum of gradients and of hessians (= row count) in leaf jj
wj∗w_j^{*}
best leaf output. With λ=0\lambda=0 it is the leaf's mean residual y−F‾\overline{y-F}; λ shrinks it toward 0 as if λ extra rows with residual 0 were in the leaf
Lj∗\mathcal L_j^{*}
the lowest loss that leaf can reach (relative to w = 0)

Split gain. Splitting a leaf into LL and RR replaces one L∗\mathcal L^* by two. LightGBM reports the reduction without the 12\tfrac12:

gain=GL2HL+λ+GR2HR+λ−(GL+GR)2HL+HR+λ\text{gain} = \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}
GL, HLG_L,\ H_L
gradient and hessian sums of the rows the split sends left
GR, HRG_R,\ H_R
the same for the right side

With λ=0\lambda=0 and hi=1h_i=1, G2/H=n rˉ2G^2/H = n\,\bar r^2 for a node with mean residual rˉ\bar r, and the gain is exactly the drop in the sum of squared errors that the split would buy if each side predicted its own mean residual. So a LightGBM regression tree is a variance-reduction tree on the residuals, like a CART regression tree — what changes is which thresholds are scored and in what order leaves are split.

Histograms make the gain cheap. Map each value xijx_{ij} to its bin bij∈{0,…,B−1}b_{ij}\in\{0,\dots,B-1\} once. For a leaf ℓ\ell and feature jj, accumulate

Gb=∑i∈ℓ, bij=bgi,Hb=∑i∈ℓ, bij=bhi,GL(k)=∑b≤kGb,HL(k)=∑b≤kHbG_{b} = \sum_{i\in\ell,\ b_{ij}=b} g_i,\qquad H_{b} = \sum_{i\in\ell,\ b_{ij}=b} h_i,\qquad G_L(k)=\sum_{b\le k}G_b,\quad H_L(k)=\sum_{b\le k}H_b
bijb_{ij}
bin index of row ii on feature jj
Gb, HbG_b,\ H_b
histogram entries: gradient and hessian sums of the leaf's rows in bin bb
GL(k)G_L(k)
prefix sum — the left side of the split "bins ≤k\le k go left"; GR(k)=G−GL(k)G_R(k) = G - G_L(k)

Building the histogram is one pass over the leaf's rows, O(nℓ)O(n_\ell) per feature, with cheap integer indexing instead of sorted-order access. Scanning all candidate splits is O(B)O(B) per feature. Compare the exact method's O(nℓ)O(n_\ell) scan plus keeping sorted orders for every node. Because histograms are sums, they are additive across disjoint row sets:

hist(R)=hist(P)−hist(L)\text{hist}(R) = \text{hist}(P) - \text{hist}(L)
P, L, RP,\ L,\ R
parent leaf and its two children; L is chosen as the child with fewer rows

so after each split only the smaller child is scanned — at most half the parent's rows — and the larger child costs O(d B)O(d\,B). Each row is therefore touched in at most log⁡2n\log_2 n histogram builds per tree, instead of once per level of a deep tree.

Leaf-wise growth is a greedy rule on the same gain. Let F\mathcal F be the current set of leaves; the next split is

(ℓ∗,j∗,k∗)=arg⁡max⁡ℓ∈F, j, k gain(ℓ,j,k)while ∣F∣<num_leaves and gain>γ(\ell^{*}, j^{*}, k^{*}) = \arg\max_{\ell\in\mathcal F,\ j,\ k}\ \text{gain}(\ell, j, k)\quad\text{while } |\mathcal F| < \texttt{num\_leaves}\ \text{and gain} > \gamma
ℓ, j, k\ell,\ j,\ k
a current leaf, a feature, and a bin edge of that feature
γ\gamma
min_gain_to_split (default 0)

Every split lowers the training loss by its gain, and the gains of different leaves add, so for a fixed number of leaves the leaf-wise order greedily removes the most squared error per leaf. A level-wise tree with the same leaf count has to split some low-gain leaves first. The price: leaf-wise trees can grow long, thin branches into small groups of rows, which is exactly how they overfit.

GOSS. Rows with small ∣gi∣|g_i| are already fitted well and contribute little to the gain. GOSS keeps the top a⋅na\cdot n rows by ∣gi∣|g_i| ("top_rate", default 0.2), samples b⋅nb\cdot n of the rest uniformly ("other_rate", default 0.1), and multiplies the sampled small-gradient rows' gg and hh by (1−a)/b(1-a)/b so the sums stay unbiased:

G~L=∑i∈ALgi+1−ab∑i∈BLgi\tilde G_L = \sum_{i\in A_L} g_i + \frac{1-a}{b}\sum_{i\in B_L} g_i
ALA_L
large-gradient rows that go left (always kept)
BLB_L
sampled small-gradient rows that go left
(1−a)/b(1-a)/b
up-weighting factor: with a = 0.2, b = 0.1 each sampled row stands for 8 rows

Histograms are then built from (a+b)n(a+b)n rows — 30% with the defaults. For squared error, large ∣gi∣|g_i| means large residuals, so GOSS focuses each tree on the houses the model currently prices worst.

How each hyperparameter enters the math. λ\lambda adds to every denominator: it shrinks w∗w^* and lowers the gain of splits on small leaves the most (a leaf with H=3H=3 and λ=6\lambda=6 keeps only a third of its weight). λ1\lambda_1 (lambda_l1) soft-thresholds the gradient sum, w∗=−sign⁡(G)max⁡(∣G∣−λ1,0)/(H+λ)w^* = -\operatorname{sign}(G)\max(|G|-\lambda_1,0)/(H+\lambda), so leaves whose residuals nearly cancel output exactly 0. min_data_in_leaf and min_sum_hessian_in_leaf remove candidate edges whose HLH_L or HRH_R is too small. max_bin sets BB: fewer bins mean fewer candidate thresholds, a faster scan, and a coarser function — with one feature, the model can take at most BB different values, however many trees you add. num_leaves caps ∣F∣|\mathcal F|; learning_rate η\eta multiplies every w∗w^* before it is added.

Worked example: pricing flats by floor area

Twelve flats, one feature (floor area in m²) and the price in thousands of dollars. The mean price is exactly 260, so F0=260F_0 = 260. We grow the first tree by hand with 4 bins, num_leaves = 3, λ=0\lambda=0, min_data_in_leaf = 1 and learning rate η=0.1\eta=0.1.

FlatSize (m²)Price (k$)g = 260 − yBin
142150+1100
248162+980
355158+1020
461175+851
566180+801
672186+741
779300−402
885312−522
993318−582
10104340−803
11118425−1653
12130414−1543
Floor area → price. g = F₀ − y is the gradient of ½(y − F)² at F₀ = 260. Bins are equal-count: 3 flats each, edges at 58, 75.5 and 98.5 m².

Growing tree 1

  1. 1Bin once. 12 sorted sizes into 4 equal-count bins; the edges sit halfway between the 3rd/4th, 6th/7th and 9th/10th values: (55+61)/2=58(55+61)/2=58, (72+79)/2=75.5(72+79)/2=75.5, (93+104)/2=98.5(93+104)/2=98.5.
  2. 2Gradients. gi=260−yig_i = 260 - y_i, hi=1h_i=1. They sum to 0 because F0F_0 is the mean.
  3. 3Root histogram (one pass over 12 rows): Gb=(+310,+239,−150,−399)G_b = (+310, +239, -150, -399) for bins 0–3, Hb=(3,3,3,3)H_b = (3,3,3,3). Total G=0G=0, H=12H=12, so the parent term G2/H=0G^2/H = 0.
  4. 4Scan 3 edges instead of 11 midpoints. Edge 58: 3102/3+3102/9=42,711.1310^2/3 + 310^2/9 = 42{,}711.1. Edge 75.5: GL=549G_L = 549, 5492/6+5492/6=549^2/6 + 549^2/6 = 100,467.0. Edge 98.5: 3992/9+3992/3=70,756.0399^2/9 + 399^2/3 = 70{,}756.0. Best: size ≤ 75.5. (An exact learner tries all 11 midpoints; 75.5 is also its best root split, so binning cost nothing here.)
  5. 5Children. Left (flats 1–6) gets its histogram from a pass over its 6 rows: (310,239,0,0)(310, 239, 0, 0). Right = parent − left =(0,0,−150,−399)= (0, 0, -150, -399) — no pass over flats 7–12.
  6. 6Score every leaf. Left leaf, only edge 58: 3102/3+2392/3−5492/6=840.2310^2/3 + 239^2/3 - 549^2/6 = 840.2. Right leaf, only edge 98.5: 1502/3+3992/3−5492/6=150^2/3 + 399^2/3 - 549^2/6 = 10,333.5. An exact learner would cut the right leaf at 111 m² (gain 13,872.0), but 111 is inside bin 3, so LightGBM cannot see it — this is the "little exactness" being traded.
  7. 7Leaf-wise choice. 10,333.5>840.210{,}333.5 > 840.2, so split the right leaf at 98.5. The tree now has 3 leaves = num_leaves, so it stops. A level-wise tree with the same 3 leaves would have split the left leaf (840.2) instead.
  8. 8Leaf weights w=−G/Hw=-G/H: size ≤ 75.5: −549/6=−91.5-549/6 = -91.5; 75.5–98.5: 150/3=+50.0150/3 = +50.0; > 98.5: 399/3=+133.0399/3 = +133.0.
  9. 9Update. F1=260+0.1 wF_1 = 260 + 0.1\,w: 250.85, 265.00, 273.30. Train RMSE drops from 98.41 to 89.05 (the level-wise tree would reach 89.89).
  10. 10Predict a new 100 m² flat: 100>98.5100 > 98.5 → bin 3 → leaf w=+133w=+133 → y^=260+0.1×133=\hat y = 260 + 0.1\times133 = 273.3 k$.
Histogrambin 0bin 1bin 2bin 3Best edge (gain)
Root (12 rows)+310 / 3+239 / 3−150 / 3−399 / 375.5 (100,467.0)
Left child: built from 6 rows+310 / 3+239 / 30 / 00 / 058 (840.2)
Right child = root − left0 / 00 / 0−150 / 3−399 / 398.5 (10,333.5)
The two histogram levels of tree 1. The right child's histogram is never built from rows — it is the parent minus the left child.

Keep boosting and every new tree repeats the same procedure on the new residuals. After 10 trees the 100 m² flat is priced at 346.63, after 100 trees at 392.99 — almost exactly 393, the mean price of bin 3. With 4 bins and one feature the model can only ever output 4 values, so after 100 rounds the training RMSE stalls at 19.53, the spread of prices within the bins. Give it 255 bins and the same 100 trees fit the 12 flats to an RMSE of 0.37 — memorization. max_bin is a speed knob and a regularizer.

▸ lightgbm · one histogram treestep 1/14
bin 0bin 1bin 2bin 35875.598.5150250350k$histogram of gradients per bin (built per leaf)
bins 4leaves 1/3η 0.1train RMSE 98.41
  1. 1bin x once into max_bin bins
  2. 2F ← mean(y)
  3. 3for t = 1 … T:
  4. 4 gᵢ ← F(xᵢ) − yᵢ , hᵢ ← 1
  5. 5 hist[bin] ← (ΣG, ΣH)
  6. 6 gain ← G²_L/H_L + G²_R/H_R − G²/H
  7. 7 split best (leaf, bin) anywhere
  8. 8 sibling hist ← parent − child
  9. 9 at num_leaves: w ← −G/(H+λ)
  10. 10 F ← F + η·w
  11. 11predict: x → bin → leaf → F

Before any tree is grown, the 12 sizes are bucketed once into 4 equal-count bins with edges at 58, 75.5, 98.5 m². From now on only bin numbers 0–3 are used.

fig.Tab 1 steps through tree 1 above: binning into 4 bins, the gradient histogram (ΣG = +310, +239, −150, −399), scoring only the 3 bin edges (best 75.5, gain 100,467.0), histogram subtraction for the right child, the leaf-wise choice of the right leaf (10,333.5 vs 840.2; the exact cut at 111 is not a bin edge), leaf weights −91.5 / +50 / +133, and the 100 m² prediction 273.3. Tab 2 boosts on 60 noisy training flats (60 more held out; noise σ = 18): drag bins, num_leaves and rounds. At the default 16 bins, 4 leaves and 50 rounds, train RMSE is 13.21 and test RMSE 19.56; with 4 bins it underfits (test 26.56 at 50 rounds), with 64 bins and 16 leaves it chases noise (train 3.48, test 23.79 after 200 rounds).

The algorithm, step by step

LightGBM regression (squared error)

  1. 1Bin. For each feature, find at most max_bin equal-count bin edges from (a sample of) the training values — bin_construct_sample_cnt = 200,000 rows by default — and replace every value with its bin index. Bundle mutually exclusive sparse features (EFB). Done once.
  2. 2Initialize F0=yˉF_0 = \bar y (boost_from_average).
  3. 3For each round t=1…Tt = 1\dots T: compute gi=F(xi)−yig_i = F(x_i) - y_i, hi=1h_i = 1; optionally keep only a GOSS or bagging subset of rows.
  4. 4Root. Build the root's histogram for every feature (one pass over the rows) and find its best (feature, edge) by prefix-sum scans.
  5. 5Grow leaf-wise. Repeat until the tree has num_leaves leaves or the best gain is ≤ min_gain_to_split: split the leaf whose best split has the highest gain (respecting min_data_in_leaf, max_depth); build the smaller child's histogram, subtract it from the parent's for the larger child; find the best split of both children.
  6. 6Leaf weights w=−G/(H+λ)w = -G/(H+\lambda) (with λ1\lambda_1 soft-thresholding if set); add η w\eta\,w to every training row's FF.
  7. 7Stop after n_estimators rounds or when the validation metric (L2, RMSE, L1…) has not improved for early_stopping_rounds.
  8. 8Predict: bin the new row with the stored edges, walk each tree, sum F0+η∑twtF_0 + \eta\sum_t w_t.

Cost per tree (n rows, d features, B bins, L leaves)

Exact greedy (pre-sorted)
O(n d)O(n\,d) scan per tree level plus sorted index maintenance; memory about 2×2\times the data for sorted indices
Histogram build
O(n d)O(n\,d) for the root; with subtraction each row is re-scanned only when it lands in the smaller child, at most log⁡2n\log_2 n times
Split search
O(L d B)O(L\,d\,B) — independent of nn
With GOSS / EFB
nn shrinks to about (a+b)n(a+b)n rows; dd shrinks to the number of bundles
Memory
one byte per value when B≤256B\le 256 (vs 4–8 bytes for floats)

Leaf-wise vs depth-wise

On the worked example the two growth orders share the root split, then disagree: leaf-wise spends the third leaf on the expensive right half (gain 10,333.5), level-wise on the cheap left half (840.2). One tree later the train RMSE is 89.05 vs 89.89. On large, rich data that difference compounds — leaf-wise reaches a given loss with far fewer leaves. On small or noisy data the same greed builds deep chains that isolate a handful of rows, so LightGBM pairs num_leaves with min_data_in_leaf and an optional max_depth.

Regression objectives

Only gig_i and hih_i change between objectives; binning, histograms and leaf-wise growth are untouched. For losses whose second derivative is zero or undefined (L1, quantile), LightGBM uses hi=1h_i = 1 and afterwards re-fits each leaf to the right statistic of its residuals (the median, or the α-quantile).

objectiveLossgᵢhᵢUse for
regression (L2)½ r²−r1default; predicts the conditional mean
regression_l1|r|−sign(r)1, leaves re-fit to medianheavy-tailed noise; predicts the median
huber½ r² if |r| ≤ α, else α|r| − ½α²−r, clipped to ±α1mostly Gaussian noise with some outliers
quantileα·r if r ≥ 0, else (α − 1)·r−α or 1 − α1, leaves re-fit to α-quantileprediction intervals (e.g. α = 0.1 and 0.9)
poissone^F − yFe^F − ye^F (scaled)counts ≥ 0
gamma / tweedielog-link deviancefrom deviancefrom deviancepositive skewed amounts, insurance claims
Common LightGBM regression objectives, with ri=yi−F(xi)r_i = y_i - F(x_i). For the log-link objectives FF is the log of the predicted mean.
objectiveŷ(50 m²)ŷ(70 m²)ŷ(100 m²)
regression (L2)156.67418.33393.00
regression_l1158.00180.00414.00
huber, α = 30156.67192.50404.50
Make flat 6 (72 m²) an outlier at 900 k$ and boost 300 rounds with 4 bins, 4 leaves. Squared error drags the whole 61–72 m² bin up; L1 ignores the outlier; Huber (α = 30) sits in between.

Hyperparameters and tuning

What to tune, in order

learning_rate + n_estimators
Fix η around 0.05–0.1 and let early stopping on a validation set pick the number of trees. Halving η roughly doubles the trees needed.
num_leaves
Main capacity knob (default 31). Try 15–255; larger needs more data and a larger min_data_in_leaf.
min_data_in_leaf
Default 20. The main brake on leaf-wise overfitting; hundreds or thousands for large noisy data.
max_bin
Default 255. Lower (15–63) is faster and regularizes; higher only helps when fine thresholds matter on very large data.
feature_fraction, bagging_fraction + bagging_freq
Column and row subsampling per tree (e.g. 0.8): decorrelates trees and speeds up training.
lambda_l2, lambda_l1, min_gain_to_split
Shrink leaf weights and veto weak splits; useful once the above are set.
max_depth
Off (−1) by default; set it (e.g. 6–10) as a safety net against very deep leaf-wise chains.
data_sample_strategy = goss
Pays off on millions of rows; on small data it can be slower than plain histograms.
Modelnum_leavesmax_binTest RMSEFit time
LightGBM32551.1280.40 s
LightGBM72551.0550.54 s
LightGBM31151.1530.70 s
LightGBM31631.0570.74 s
LightGBM (defaults)312551.0580.92 s
LightGBM1272551.0651.83 s
LightGBM5112551.1084.56 s
LightGBM, GOSS312551.0641.36 s
scikit-learn GradientBoosting (exact)31—1.05973.53 s
Friedman #1 data (10 features, noise σ = 1), 50,000 training and 10,000 test rows, 300 trees, η = 0.1, one CPU thread. The noise floor is a test RMSE of 1.0; test-target std is 4.99.

Two lessons from the table. Bins: 15 bins cost accuracy (1.153), 63 are already as good as 255. Leaves: past the true complexity of the function, more leaves only overfit (511 leaves: 1.108) and cost time. GOSS was slower here — with only 50,000 rows the sampling overhead outweighs the saved histogram work.

In code

python
1import numpy as np
2
3def make_bins(x, max_bins):
4 """Equal-frequency bin edges, placed midway between neighbouring sorted values."""
5 v = np.unique(x)
6 if len(v) <= max_bins:
7 return (v[:-1] + v[1:]) / 2
8 xs = np.sort(x)
9 cuts = [round(k * len(xs) / max_bins) for k in range(1, max_bins)]
10 return np.unique([(xs[c - 1] + xs[c]) / 2 for c in cuts])
11
12def histogram(B, g, rows, n_bins):
13 """Per feature and bin: sum of gradients, sum of hessians (=count for L2), count."""
14 d = B.shape[1]
15 Hist = np.zeros((3, d, n_bins))
16 for j in range(d):
17 np.add.at(Hist[0, j], B[rows, j], g[rows])
18 np.add.at(Hist[1, j], B[rows, j], 1.0) # h_i = 1 for squared error
19 np.add.at(Hist[2, j], B[rows, j], 1.0)
20 return Hist
21
22def best_split(Hist, lam, min_leaf):
23 best = (0.0, None, None) # (gain, feature, last bin on the left)
24 G, H, N = Hist
25 for j in range(G.shape[0]):
26 GL, HL, NL = (np.cumsum(a[j])[:-1] for a in (G, H, N))
27 Gt, Ht, Nt = G[j].sum(), H[j].sum(), N[j].sum()
28 with np.errstate(divide="ignore", invalid="ignore"):
29 gain = GL**2 / (HL + lam) + (Gt - GL)**2 / (Ht - HL + lam) - Gt**2 / (Ht + lam)
30 gain[(NL < min_leaf) | (Nt - NL < min_leaf) | np.isnan(gain)] = -np.inf
31 if len(gain) and gain.max() > best[0]:
32 best = (gain.max(), j, int(gain.argmax()))
33 return best
34
35def grow_tree(B, g, n_bins, num_leaves, lam, min_leaf):
36 """Leaf-wise growth with histogram subtraction."""
37 root = np.arange(len(g))
38 leaves = {0: (root, histogram(B, g, root, n_bins))}
39 nodes = {} # node id -> (feature, bin, left id, right id)
40 while len(leaves) < num_leaves:
41 cand = {i: best_split(h, lam, min_leaf) for i, (_, h) in leaves.items()}
42 i = max(cand, key=lambda k: cand[k][0]) # the best leaf ANYWHERE in the tree
43 gain, j, k = cand[i]
44 if j is None:
45 break # no split with positive gain left
46 rows, hist = leaves.pop(i)
47 L, R = rows[B[rows, j] <= k], rows[B[rows, j] > k]
48 if len(L) <= len(R): # build the smaller child's histogram,
49 hL = histogram(B, g, L, n_bins); hR = hist - hL # get the larger one by subtraction
50 else:
51 hR = histogram(B, g, R, n_bins); hL = hist - hR
52 a, b = 2 * len(nodes) + 1, 2 * len(nodes) + 2
53 nodes[i] = (j, k, a, b)
54 leaves[a], leaves[b] = (L, hL), (R, hR)
55 value = {i: -h[0, 0].sum() / (h[1, 0].sum() + lam) for i, (_, h) in leaves.items()}
56 return nodes, value # leaf output w* = -G / (H + lambda)
57
58def route(nodes, value, B):
59 node = np.zeros(len(B), int)
60 for i, (j, k, a, b) in nodes.items(): # parents were stored before children
61 at = node == i
62 node[at] = np.where(B[at, j] <= k, a, b)
63 return np.array([value[i] for i in node])
64
65class TinyLightGBMRegressor:
66 def __init__(self, n_estimators=100, learning_rate=0.1, num_leaves=31,
67 max_bin=255, lambda_l2=0.0, min_data_in_leaf=20):
68 self.T, self.eta, self.leaves = n_estimators, learning_rate, num_leaves
69 self.max_bin, self.lam, self.min_leaf = max_bin, lambda_l2, min_data_in_leaf
70
71 def _bin(self, X):
72 return np.stack([np.searchsorted(e, X[:, j]) for j, e in enumerate(self.edges)], 1)
73
74 def fit(self, X, y):
75 self.edges = [make_bins(X[:, j], self.max_bin) for j in range(X.shape[1])]
76 B, n_bins = self._bin(X), max(len(e) for e in self.edges) + 1 # bin ONCE, up front
77 self.f0 = y.mean()
78 F = np.full(len(y), self.f0)
79 self.trees = []
80 for _ in range(self.T):
81 g = F - y # gradient of 1/2 (F - y)^2
82 nodes, value = grow_tree(B, g, n_bins, self.leaves, self.lam, self.min_leaf)
83 F += self.eta * route(nodes, value, B)
84 self.trees.append((nodes, value))
85 return self
86
87 def predict(self, X):
88 B = self._bin(np.asarray(X, float))
89 return self.f0 + self.eta * sum(route(n, v, B) for n, v in self.trees)
90
91size = np.array([42, 48, 55, 61, 66, 72, 79, 85, 93, 104, 118, 130], float)
92price = np.array([150, 162, 158, 175, 180, 186, 300, 312, 318, 340, 425, 414], float)
93X = size.reshape(-1, 1)
94for T in [1, 100]:
95 m = TinyLightGBMRegressor(T, 0.1, num_leaves=3, max_bin=4, min_data_in_leaf=1).fit(X, price)
96 rmse = np.sqrt(np.mean((m.predict(X) - price) ** 2))
97 print(f"T={T:3d} bin edges={m.edges[0]} train RMSE={rmse:.3f} f(100 m2)={m.predict([[100.]])[0]:.3f}")
98# T= 1 bin edges=[58. 75.5 98.5] train RMSE=89.053 f(100 m2)=273.300
99# T=100 bin edges=[58. 75.5 98.5] train RMSE=19.531 f(100 m2)=392.992
From scratch: equal-count binning, gradient histograms, histogram subtraction, leaf-wise growth. Reproduces the worked example.
python
1import numpy as np
2import lightgbm as lgb
3
4size = np.array([42, 48, 55, 61, 66, 72, 79, 85, 93, 104, 118, 130], float)
5price = np.array([150, 162, 158, 175, 180, 186, 300, 312, 318, 340, 425, 414], float)
6X = size.reshape(-1, 1)
7
8params = dict(objective="regression", num_leaves=3, learning_rate=0.1,
9 max_bin=5, min_data_in_bin=1, # 4 bins: 58 | 75.5 | 98.5
10 min_data_in_leaf=1, min_sum_hessian_in_leaf=0,
11 lambda_l2=0.0, verbose=-1)
12
13booster = lgb.train(params, lgb.Dataset(X, price, params=params), num_boost_round=1)
14print(booster.trees_to_dataframe()[["node_depth", "threshold", "split_gain", "value", "count"]])
15# node_depth threshold split_gain value count
16# 0 1 75.5 100467.0 260.00 12
17# 1 2 NaN NaN 250.85 6
18# 2 2 98.5 10333.5 269.15 6
19# 3 3 NaN NaN 265.00 3
20# 4 3 NaN NaN 273.30 3
21print(booster.predict([[100.0]])) # [273.3]
22
23for rounds in [10, 100]:
24 b = lgb.train(params, lgb.Dataset(X, price, params=params), num_boost_round=rounds)
25 rmse = np.sqrt(np.mean((b.predict(X) - price) ** 2))
26 print(rounds, round(rmse, 3), round(b.predict([[100.0]])[0], 3))
27# 10 39.674 346.626
28# 100 19.531 392.992
29
30# On real data: scikit-learn API + early stopping on a validation set
31# model = lgb.LGBMRegressor(n_estimators=5000, learning_rate=0.05, num_leaves=31,
32# min_child_samples=20, subsample=0.8, subsample_freq=1,
33# colsample_bytree=0.8)
34# model.fit(X_tr, y_tr, eval_set=[(X_va, y_va)], eval_metric="l2",
35# callbacks=[lgb.early_stopping(100)])
The same tree with the lightgbm library. min_data_in_leaf and friends must be lowered for 12 rows; max_bin = 5 gives 4 bins because LightGBM always reserves a bin boundary at zero.

Use when

  • +Large tabular data (10⁵ rows and up): histogram splits and leaf-wise growth train an order of magnitude or more faster than exact boosting at the same accuracy.
  • +Many sparse or one-hot features: EFB bundles them, and bins are 1 byte each.
  • +You need robust or distributional losses (L1, Huber, quantile, Poisson, Tweedie) with the same fast trainer.
  • +Native categorical features (categorical_feature) and missing values are needed without preprocessing.

Avoid when

  • −The dataset is small (hundreds of rows): leaf-wise trees overfit easily and the defaults may not split at all.
  • −You need smooth predictions or extrapolation: the fit is piecewise constant and flat beyond the training range.
  • −The relationship is mostly linear in a few features: a regularized linear model is simpler and extrapolates.
  • −You need a single interpretable model: hundreds of deep, lopsided trees are not readable.

Where it's used

Demand and sales forecasting

Retail and supply-chain teams regress daily units sold on calendar, price and lag features over millions of rows; LightGBM was the workhorse of most top solutions in the M5 forecasting competition.

Ad and ranking signals

Predicting click-through or dwell time on huge, sparse feature sets — the workload LightGBM was built for at Microsoft.

Insurance claim severity

Gamma and Tweedie objectives model positive, right-skewed claim amounts with many zeros.

Real-estate and pricing models

Automated valuation from size, location and amenities; quantile objectives give price intervals instead of a single number.

Check yourself

A leaf's histogram scan reaches an edge with G_L = −120, H_L = 4 on the left and G_R = +120, H_R = 6 on the right (λ = 0). What gain does LightGBM report?

Check yourself

A model has one feature binned into 8 bins. After 10,000 boosting rounds, how many different predictions can it output at most?

Check yourself

A tree has 3 leaves. Their best splits gain 300 (leaf A), 1,200 (leaf B, at depth 4) and nothing (leaf C, at depth 1). With num_leaves = 4, what does LightGBM do next?

Check yourself

GOSS runs with top_rate a = 0.2 and other_rate b = 0.1. By what factor are the sampled small-gradient rows' gradients multiplied?

Remember

  • ✓For squared error gi=F(xi)−yig_i = F(x_i)-y_i, hi=1h_i = 1: leaf weight −G/(H+λ)-G/(H+\lambda) is a shrunken mean residual, and the split gain (λ = 0) is exactly the drop in squared error.
  • ✓Features are binned once; splits are scored only at bin edges from per-bin gradient histograms, so split search costs O(bins), not O(rows).
  • ✓Histogram subtraction builds only the smaller child; leaf-wise growth spends each leaf on the largest gain anywhere in the tree.
  • ✓num_leaves and min_data_in_leaf are the main capacity controls; max_bin trades speed and smoothness (one feature with B bins gives at most B output values).
  • ✓GOSS and EFB cut rows and features for very large or sparse data; on small data, lower the defaults or use a simpler model.
← back to ML Algorithms roadmap