LightGBM GOSS & EFB

LightGBM accelerates training on huge, high-dimensional data with three mechanisms. (1) Histogram-based splitting: each continuous feature is discretized into $k$ bins and splits are only searched on bin boundaries — split complexity drops from $O(n \cdot d)$ (pre-sorting) to $O(k \cdot d)$, memory from $O(n \cdot d)$ to $O(k \cdot d)$, and parent-child histograms are reused incrementally. (2) GOSS (Gradient-based One-Side Sampling): when computing split gain, sort samples by absolute gradient $|g_i|$ descending, keep all of the top $a \times 100\%$ large-gradient samples, randomly sample $b \times 100\%$ from the remaining $(1 - a) \times 100\%$ small-gradient samples, and amplify the weights of sampled small-gradient samples by $\frac{1 - a}{b}$ — the gain is estimated from weighted statistics, unbiased in expectation, while only $(a + b)$ of the data is used (e.g. $a = 0.2, b = 0.1$ uses ~30%). Intuition: large $|g_i|$ means large pseudo-residuals, i.e. under-fitted samples carrying most of the learning signal; uniform random sampling would likely drop them. (3) EFB (Exclusive Feature Bundling): in sparse data many features (especially one-hot encoded) are mutually exclusive — they are rarely nonzero simultaneously; bundling them into one composite feature (via greedy graph coloring with a conflict threshold) reduces the feature count from $d$ to the number of bundles, cutting histogram construction from $O(\text{data} \times d)$ to $O(\text{data} \times \text{bundles})$. LightGBM also grows trees leaf-wise: each split expands the leaf with the current largest gain (capped by max_depth) — it converges faster and reaches lower error than level-wise growth, but overfits more easily with little data; categorical features are natively supported (no one-hot needed).

GOSS and EFB principles, leaf-wise vs level-wise growth, and histogram vs pre-sorting are frequent interview topics; in practice LightGBM powers CTR prediction and large-scale ranking on massive sparse features, one of the two dominant GBDT engines alongside XGBoost.

XGBoost's exact greedy search pre-sorts every feature ($O(n \log n)$ per column) and level-wise growth visits all nodes, which is too slow when samples and features are both huge — GOSS reaches near full-data accuracy with ~30% of samples (typically 5–10x faster with negligible accuracy loss); EFB squeezes features from $d$ down to bundles (often 3–8x on sparse one-hot data); histograms cut memory from $O(n \cdot d)$ to $O(k \cdot d)$ — together these are the core speed advantage of LightGBM over XGBoost.

GOSS mechanism: keep all large-gradient samples + randomly sample small-gradient ones; why are sampled small-gradient weights amplified by $\frac{1-a}{b}$? (unbiased estimation)

Why do large-gradient samples carry more information? Relationship between $g_i$ and GBDT pseudo-residuals

EFB: what makes features mutually exclusive? How is the conflict ratio measured? How much does bundling reduce complexity?

Leaf-wise vs level-wise growth: why is leaf-wise more efficient yet more prone to overfitting? Mitigation (max_depth)?

Histogram vs pre-sorted: memory/accuracy tradeoff from $O(n \cdot d)$ to $O(k \cdot d)$; overall LightGBM vs XGBoost comparison