# LightGBM regression

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

Source: https://www.mlfoundry.in/learn/lightgbm-regression  
Section: ML Algorithms › Supervised · Regression  
Level: advanced · 18 min read · updated 2026-10-07

**LightGBM regression:** predicts a number as a constant plus a sum of shrunken regression trees, $\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.

- **Task:** Regression (squared error by default; also L1, Huber, quantile, Poisson, Gamma, Tweedie, MAPE objectives)
- **Input → output:** feature vector $x$ → real number $\hat y = F_0 + \eta\sum_{t=1}^{T} f_t(x)$
- **Learns:** bin edges per feature (once, before training); then $T$ trees, each with a (feature, bin edge) per internal node and a weight $w$ per leaf
- **Training:** binning once: $O(n\,d\log n)$; per tree: building histograms $O(n\,d)$ (less with subtraction and GOSS), scanning them $O(\text{leaves}\cdot d\cdot B)$ — independent of $n$
- **Prediction:** $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-1$ candidates per feature per node. With $n = 10^7$ rows and $d = 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** $G$ and the **sum of hessians** $H$ (for squared error, $H$ is just the row count). Those totals do not care about the exact $x$ 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 $g$ and $h$ 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 $G_b=\sum g_i$ and $H_b=\sum h_i$ (and the row count) of the rows in that leaf that fall in bin $b$
- **Histogram subtraction:** $\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-1$ trees is $F$; the next tree adds $f_t$.

$$
\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
$$

- $y_i,\ x_i$: target and feature vector of training row i
- $F(x_i)$: the current ensemble's prediction for row i
- $f_t$: the new tree; it outputs weight $w_j$ for every row in its leaf $j$
- $g_i,\ h_i$: first and second derivative of $\tfrac12(y_i-F)^2$ with respect to $F$: minus the residual, and 1
- $\lambda$: L2 penalty on leaf weights (`lambda_l2`, default 0)

**Leaf weight.** All rows in leaf $j$ get the same $w_j$, so that leaf's part of $\mathcal L$ is (up to a constant) $G_j w_j + \tfrac12 (H_j+\lambda) w_j^2$ with $G_j=\sum_{i\in j} g_i$, $H_j = \sum_{i\in j}h_i$. For squared error this is exact, not an approximation. Setting the derivative to zero:

$$
w_j^{*} = -\frac{G_j}{H_j+\lambda}\qquad\Longrightarrow\qquad \mathcal L_j^{*} = -\frac12\,\frac{G_j^2}{H_j+\lambda}
$$

- $G_j,\ H_j$: sum of gradients and of hessians (= row count) in leaf $j$
- $w_j^{*}$: best leaf output. With $\lambda=0$ it is the leaf's mean residual $\overline{y-F}$; λ shrinks it toward 0 as if λ extra rows with residual 0 were in the leaf
- $\mathcal L_j^{*}$: the lowest loss that leaf can reach (relative to w = 0)

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

$$
\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}
$$

- $G_L,\ H_L$: gradient and hessian sums of the rows the split sends left
- $G_R,\ H_R$: the same for the right side

With $\lambda=0$ and $h_i=1$, $G^2/H = n\,\bar r^2$ for a node with mean residual $\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 $x_{ij}$ to its bin $b_{ij}\in\{0,\dots,B-1\}$ once. For a leaf $\ell$ and feature $j$, accumulate

$$
G_{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
$$

- $b_{ij}$: bin index of row $i$ on feature $j$
- $G_b,\ H_b$: histogram entries: gradient and hessian sums of the leaf's rows in bin $b$
- $G_L(k)$: prefix sum — the left side of the split "bins $\le k$ go left"; $G_R(k) = G - G_L(k)$

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

$$
\text{hist}(R) = \text{hist}(P) - \text{hist}(L)
$$

- $P,\ 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)$. Each row is therefore touched in at most $\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 $\mathcal F$ be the current set of leaves; the next split is

$$
(\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
$$

- $\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 $|g_i|$ are already fitted well and contribute little to the gain. GOSS keeps the top $a\cdot n$ rows by $|g_i|$ ("top_rate", default 0.2), samples $b\cdot n$ of the rest uniformly ("other_rate", default 0.1), and multiplies the sampled small-gradient rows' $g$ and $h$ by $(1-a)/b$ so the sums stay unbiased:

$$
\tilde G_L = \sum_{i\in A_L} g_i + \frac{1-a}{b}\sum_{i\in B_L} g_i
$$

- $A_L$: large-gradient rows that go left (always kept)
- $B_L$: sampled small-gradient rows that go left
- $(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$ rows — 30% with the defaults. For squared error, large $|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^*$ and lowers the gain of splits on small leaves the most (a leaf with $H=3$ and $\lambda=6$ keeps only a third of its weight). $\lambda_1$ (`lambda_l1`) soft-thresholds the gradient sum, $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 $H_L$ or $H_R$ is too small. `max_bin` sets $B$: fewer bins mean fewer candidate thresholds, a faster scan, and a coarser function — with one feature, the model can take **at most $B$ different values**, however many trees you add. `num_leaves` caps $|\mathcal F|$; `learning_rate` $\eta$ multiplies every $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 $F_0 = 260$. We grow the first tree by hand with **4 bins**, **num_leaves = 3**, $\lambda=0$, min_data_in_leaf = 1 and learning rate $\eta=0.1$.

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².

| Flat | Size (m²) | Price (k$) | g = 260 − y | Bin |
| --- | --- | --- | --- | --- |
| 1 | 42 | 150 | +110 | 0 |
| 2 | 48 | 162 | +98 | 0 |
| 3 | 55 | 158 | +102 | 0 |
| 4 | 61 | 175 | +85 | 1 |
| 5 | 66 | 180 | +80 | 1 |
| 6 | 72 | 186 | +74 | 1 |
| 7 | 79 | 300 | −40 | 2 |
| 8 | 85 | 312 | −52 | 2 |
| 9 | 93 | 318 | −58 | 2 |
| 10 | 104 | 340 | −80 | 3 |
| 11 | 118 | 425 | −165 | 3 |
| 12 | 130 | 414 | −154 | 3 |

**Growing tree 1**

1. **Bin 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$, $(72+79)/2=75.5$, $(93+104)/2=98.5$.
2. **Gradients.** $g_i = 260 - y_i$, $h_i=1$. They sum to 0 because $F_0$ is the mean.
3. **Root histogram** (one pass over 12 rows): $G_b = (+310, +239, -150, -399)$ for bins 0–3, $H_b = (3,3,3,3)$. Total $G=0$, $H=12$, so the parent term $G^2/H = 0$.
4. **Scan 3 edges** instead of 11 midpoints. Edge 58: $310^2/3 + 310^2/9 = 42{,}711.1$. Edge 75.5: $G_L = 549$, $549^2/6 + 549^2/6 = $ **100,467.0**. Edge 98.5: $399^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. **Children.** Left (flats 1–6) gets its histogram from a pass over its 6 rows: $(310, 239, 0, 0)$. Right = parent − left $= (0, 0, -150, -399)$ — no pass over flats 7–12.
6. **Score every leaf.** Left leaf, only edge 58: $310^2/3 + 239^2/3 - 549^2/6 = 840.2$. Right leaf, only edge 98.5: $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. **Leaf-wise choice.** $10{,}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. **Leaf weights** $w=-G/H$: size ≤ 75.5: $-549/6 = -91.5$; 75.5–98.5: $150/3 = +50.0$; > 98.5: $399/3 = +133.0$.
9. **Update.** $F_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. **Predict** a new 100 m² flat: $100 > 98.5$ → bin 3 → leaf $w=+133$ → $\hat y = 260 + 0.1\times133 = $ **273.3 k$**.

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.

| Histogram | bin 0 | bin 1 | bin 2 | bin 3 | Best edge (gain) |
| --- | --- | --- | --- | --- | --- |
| Root (12 rows) | +310 / 3 | +239 / 3 | −150 / 3 | −399 / 3 | **75.5** (100,467.0) |
| Left child: built from 6 rows | +310 / 3 | +239 / 3 | 0 / 0 | 0 / 0 | 58 (840.2) |
| Right child = root − left | 0 / 0 | 0 / 0 | −150 / 3 | −399 / 3 | **98.5** (10,333.5) |

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.

> Figure: 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).

> **Binning coarsens thresholds, not the target:** Bins only restrict *where* a tree can cut. The leaf values are still exact means of real residuals, and the next tree can cut at a different feature, so a slightly misplaced threshold is mostly repaired by later trees. That is why 63–255 bins typically match exact splitting — in the Friedman benchmark below, 255 bins and 31 leaves score test RMSE 1.058 against 1.059 for scikit-learn's exact-split gradient boosting.

## The algorithm, step by step

**LightGBM regression (squared error)**

1. **Bin.** 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. **Initialize** $F_0 = \bar y$ (`boost_from_average`).
3. **For each round** $t = 1\dots T$: compute $g_i = F(x_i) - y_i$, $h_i = 1$; optionally keep only a GOSS or bagging subset of rows.
4. **Root.** Build the root's histogram for every feature (one pass over the rows) and find its best (feature, edge) by prefix-sum scans.
5. **Grow 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. **Leaf weights** $w = -G/(H+\lambda)$ (with $\lambda_1$ soft-thresholding if set); add $\eta\,w$ to every training row's $F$.
7. **Stop** after `n_estimators` rounds or when the validation metric (L2, RMSE, L1…) has not improved for `early_stopping_rounds`.
8. **Predict:** bin the new row with the stored edges, walk each tree, sum $F_0 + \eta\sum_t w_t$.

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

- **Exact greedy (pre-sorted):** $O(n\,d)$ scan per tree level plus sorted index maintenance; memory about $2\times$ the data for sorted indices
- **Histogram build:** $O(n\,d)$ for the root; with subtraction each row is re-scanned only when it lands in the smaller child, at most $\log_2 n$ times
- **Split search:** $O(L\,d\,B)$ — independent of $n$
- **With GOSS / EFB:** $n$ shrinks to about $(a+b)n$ rows; $d$ shrinks to the number of bundles
- **Memory:** one byte per value when $B\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`.

> **num_leaves is not 2^max_depth:** A depth-7 balanced tree has 128 leaves; a leaf-wise tree with `num_leaves = 128` can be 30 levels deep down one branch. Translating an XGBoost `max_depth = 7` into `num_leaves = 128` usually overfits. Start with `num_leaves` well below `2^max_depth` (the defaults are 31 leaves and no depth limit) and raise it only while the validation error keeps falling.

## Regression objectives

Only $g_i$ and $h_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 $h_i = 1$ and afterwards **re-fits each leaf** to the right statistic of its residuals (the median, or the α-quantile).

Common LightGBM regression objectives, with $r_i = y_i - F(x_i)$. For the log-link objectives $F$ is the log of the predicted mean.

| objective | Loss | gᵢ | hᵢ | Use for |
| --- | --- | --- | --- | --- |
| `regression` (L2) | ½ r² | −r | 1 | default; predicts the conditional mean |
| `regression_l1` | \|r\| | −sign(r) | 1, leaves re-fit to median | heavy-tailed noise; predicts the median |
| `huber` | ½ r² if \|r\| ≤ α, else α\|r\| − ½α² | −r, clipped to ±α | 1 | mostly Gaussian noise with some outliers |
| `quantile` | α·r if r ≥ 0, else (α − 1)·r | −α or 1 − α | 1, leaves re-fit to α-quantile | prediction intervals (e.g. α = 0.1 and 0.9) |
| `poisson` | e^F − yF | e^F − y | e^F (scaled) | counts ≥ 0 |
| `gamma` / `tweedie` | log-link deviance | from deviance | from deviance | positive skewed amounts, insurance claims |

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.

| objective | ŷ(50 m²) | ŷ(70 m²) | ŷ(100 m²) |
| --- | --- | --- | --- |
| regression (L2) | 156.67 | **418.33** | 393.00 |
| regression_l1 | 158.00 | 180.00 | 414.00 |
| huber, α = 30 | 156.67 | 192.50 | 404.50 |

## 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.

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.

| Model | num_leaves | max_bin | Test RMSE | Fit time |
| --- | --- | --- | --- | --- |
| LightGBM | 3 | 255 | 1.128 | 0.40 s |
| LightGBM | 7 | 255 | 1.055 | 0.54 s |
| LightGBM | 31 | 15 | 1.153 | 0.70 s |
| LightGBM | 31 | 63 | 1.057 | 0.74 s |
| **LightGBM (defaults)** | **31** | **255** | **1.058** | **0.92 s** |
| LightGBM | 127 | 255 | 1.065 | 1.83 s |
| LightGBM | 511 | 255 | 1.108 | 4.56 s |
| LightGBM, GOSS | 31 | 255 | 1.064 | 1.36 s |
| scikit-learn GradientBoosting (exact) | 31 | — | 1.059 | 73.53 s |

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
import numpy as np

def make_bins(x, max_bins):
    """Equal-frequency bin edges, placed midway between neighbouring sorted values."""
    v = np.unique(x)
    if len(v) <= max_bins:
        return (v[:-1] + v[1:]) / 2
    xs = np.sort(x)
    cuts = [round(k * len(xs) / max_bins) for k in range(1, max_bins)]
    return np.unique([(xs[c - 1] + xs[c]) / 2 for c in cuts])

def histogram(B, g, rows, n_bins):
    """Per feature and bin: sum of gradients, sum of hessians (=count for L2), count."""
    d = B.shape[1]
    Hist = np.zeros((3, d, n_bins))
    for j in range(d):
        np.add.at(Hist[0, j], B[rows, j], g[rows])
        np.add.at(Hist[1, j], B[rows, j], 1.0)        # h_i = 1 for squared error
        np.add.at(Hist[2, j], B[rows, j], 1.0)
    return Hist

def best_split(Hist, lam, min_leaf):
    best = (0.0, None, None)                          # (gain, feature, last bin on the left)
    G, H, N = Hist
    for j in range(G.shape[0]):
        GL, HL, NL = (np.cumsum(a[j])[:-1] for a in (G, H, N))
        Gt, Ht, Nt = G[j].sum(), H[j].sum(), N[j].sum()
        with np.errstate(divide="ignore", invalid="ignore"):
            gain = GL**2 / (HL + lam) + (Gt - GL)**2 / (Ht - HL + lam) - Gt**2 / (Ht + lam)
        gain[(NL < min_leaf) | (Nt - NL < min_leaf) | np.isnan(gain)] = -np.inf
        if len(gain) and gain.max() > best[0]:
            best = (gain.max(), j, int(gain.argmax()))
    return best

def grow_tree(B, g, n_bins, num_leaves, lam, min_leaf):
    """Leaf-wise growth with histogram subtraction."""
    root = np.arange(len(g))
    leaves = {0: (root, histogram(B, g, root, n_bins))}
    nodes = {}                                        # node id -> (feature, bin, left id, right id)
    while len(leaves) < num_leaves:
        cand = {i: best_split(h, lam, min_leaf) for i, (_, h) in leaves.items()}
        i = max(cand, key=lambda k: cand[k][0])       # the best leaf ANYWHERE in the tree
        gain, j, k = cand[i]
        if j is None:
            break                                     # no split with positive gain left
        rows, hist = leaves.pop(i)
        L, R = rows[B[rows, j] <= k], rows[B[rows, j] > k]
        if len(L) <= len(R):                          # build the smaller child's histogram,
            hL = histogram(B, g, L, n_bins); hR = hist - hL   # get the larger one by subtraction
        else:
            hR = histogram(B, g, R, n_bins); hL = hist - hR
        a, b = 2 * len(nodes) + 1, 2 * len(nodes) + 2
        nodes[i] = (j, k, a, b)
        leaves[a], leaves[b] = (L, hL), (R, hR)
    value = {i: -h[0, 0].sum() / (h[1, 0].sum() + lam) for i, (_, h) in leaves.items()}
    return nodes, value                               # leaf output w* = -G / (H + lambda)

def route(nodes, value, B):
    node = np.zeros(len(B), int)
    for i, (j, k, a, b) in nodes.items():           # parents were stored before children
        at = node == i
        node[at] = np.where(B[at, j] <= k, a, b)
    return np.array([value[i] for i in node])

class TinyLightGBMRegressor:
    def __init__(self, n_estimators=100, learning_rate=0.1, num_leaves=31,
                 max_bin=255, lambda_l2=0.0, min_data_in_leaf=20):
        self.T, self.eta, self.leaves = n_estimators, learning_rate, num_leaves
        self.max_bin, self.lam, self.min_leaf = max_bin, lambda_l2, min_data_in_leaf

    def _bin(self, X):
        return np.stack([np.searchsorted(e, X[:, j]) for j, e in enumerate(self.edges)], 1)

    def fit(self, X, y):
        self.edges = [make_bins(X[:, j], self.max_bin) for j in range(X.shape[1])]
        B, n_bins = self._bin(X), max(len(e) for e in self.edges) + 1   # bin ONCE, up front
        self.f0 = y.mean()
        F = np.full(len(y), self.f0)
        self.trees = []
        for _ in range(self.T):
            g = F - y                                 # gradient of 1/2 (F - y)^2
            nodes, value = grow_tree(B, g, n_bins, self.leaves, self.lam, self.min_leaf)
            F += self.eta * route(nodes, value, B)
            self.trees.append((nodes, value))
        return self

    def predict(self, X):
        B = self._bin(np.asarray(X, float))
        return self.f0 + self.eta * sum(route(n, v, B) for n, v in self.trees)

size  = np.array([42, 48, 55, 61, 66, 72, 79, 85, 93, 104, 118, 130], float)
price = np.array([150, 162, 158, 175, 180, 186, 300, 312, 318, 340, 425, 414], float)
X = size.reshape(-1, 1)
for T in [1, 100]:
    m = TinyLightGBMRegressor(T, 0.1, num_leaves=3, max_bin=4, min_data_in_leaf=1).fit(X, price)
    rmse = np.sqrt(np.mean((m.predict(X) - price) ** 2))
    print(f"T={T:3d}  bin edges={m.edges[0]}  train RMSE={rmse:.3f}  f(100 m2)={m.predict([[100.]])[0]:.3f}")
# T=  1  bin edges=[58.  75.5 98.5]  train RMSE=89.053  f(100 m2)=273.300
# 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
import numpy as np
import lightgbm as lgb

size  = np.array([42, 48, 55, 61, 66, 72, 79, 85, 93, 104, 118, 130], float)
price = np.array([150, 162, 158, 175, 180, 186, 300, 312, 318, 340, 425, 414], float)
X = size.reshape(-1, 1)

params = dict(objective="regression", num_leaves=3, learning_rate=0.1,
              max_bin=5, min_data_in_bin=1,          # 4 bins: 58 | 75.5 | 98.5
              min_data_in_leaf=1, min_sum_hessian_in_leaf=0,
              lambda_l2=0.0, verbose=-1)

booster = lgb.train(params, lgb.Dataset(X, price, params=params), num_boost_round=1)
print(booster.trees_to_dataframe()[["node_depth", "threshold", "split_gain", "value", "count"]])
#    node_depth  threshold  split_gain   value  count
# 0           1       75.5    100467.0  260.00     12
# 1           2        NaN         NaN  250.85      6
# 2           2       98.5     10333.5  269.15      6
# 3           3        NaN         NaN  265.00      3
# 4           3        NaN         NaN  273.30      3
print(booster.predict([[100.0]]))                     # [273.3]

for rounds in [10, 100]:
    b = lgb.train(params, lgb.Dataset(X, price, params=params), num_boost_round=rounds)
    rmse = np.sqrt(np.mean((b.predict(X) - price) ** 2))
    print(rounds, round(rmse, 3), round(b.predict([[100.0]])[0], 3))
# 10 39.674 346.626
# 100 19.531 392.992

# On real data: scikit-learn API + early stopping on a validation set
# model = lgb.LGBMRegressor(n_estimators=5000, learning_rate=0.05, num_leaves=31,
#                           min_child_samples=20, subsample=0.8, subsample_freq=1,
#                           colsample_bytree=0.8)
# model.fit(X_tr, y_tr, eval_set=[(X_va, y_va)], eval_metric="l2",
#           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.

> **Defaults silently do nothing on small data:** With the default `min_data_in_leaf = 20`, a 12-row dataset cannot be split at all: `LGBMRegressor(n_estimators=100).fit(X, price)` predicts the constant 260 for every flat. LightGBM's defaults are tuned for thousands of rows or more; on small data lower `min_data_in_leaf` (sklearn name `min_child_samples`) — or use a simpler model.

> **λ can veto a split, not just shrink it:** Rerun the worked example with `lambda_l2 = 6`. The root still splits at 75.5 (gain halves to 50,233.5), but the right leaf's split now scores $150^2/9 + 399^2/9 - 549^2/12 < 0$ and is dropped, so the tree has only 2 leaves and the 100 m² flat gets $260 + 0.1\cdot549/12 = 264.58$ instead of 273.3. Small leaves are penalized hardest; tune λ together with `num_leaves`, not after.

> **Same parameter, two names:** The scikit-learn wrapper renames several parameters: `min_child_samples` = `min_data_in_leaf`, `subsample` = `bagging_fraction`, `colsample_bytree` = `feature_fraction`, `reg_lambda` = `lambda_l2`. `max_bin` is a Dataset parameter: changing it after the Dataset is constructed has no effect.

**Strengths**

- 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.

**Limitations**

- 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.

- **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.

**Question:** 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?

- A. 0
- B. 2,400
- C. 6,000
- D. 14,400

**Answer:** C. 6,000 — The parent has $G = 0$, so its term vanishes: $120^2/4 + 120^2/6 - 0 = 3600 + 2400 = 6000$ — the drop in the sum of squared errors.

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

- A. 8
- B. 16
- C. 10,000
- D. Unlimited — every tree adds new values

**Answer:** A. 8 — Every split is at a bin edge, so all rows in the same bin always land in the same leaf of every tree and get the same total. Adding trees changes the 8 values, not their number.

**Question:** 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?

- A. Split leaf C, the shallowest
- B. Split leaf A, then B
- C. Split leaf B, then stop
- D. Split A and B together

**Answer:** C. Split leaf B, then stop — Leaf-wise growth takes the single highest-gain split anywhere in the tree, regardless of depth. After splitting B the tree has 4 leaves = num_leaves, so it stops.

**Question:** 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?

- A. 2
- B. 5
- C. 8
- D. 10

**Answer:** C. 8 — $(1-a)/b = 0.8/0.1 = 8$: the 10% sampled rows stand in for the 80% of rows outside the top-gradient set, keeping $G$ and $H$ unbiased.

**Key points**

- For squared error $g_i = F(x_i)-y_i$, $h_i = 1$: leaf weight $-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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
