GOSS and Exclusive Feature Bundling

Gradient boosting spends most of its time scanning rows and columns to find the best split at each node. LightGBM speeds this up with two independent tricks that shrink, respectively, the number of rows and the number of columns it has to look at without meaningfully hurting accuracy.

How each works

GOSS reasons that rows the model already predicts well (small gradients) have little left to teach the next tree, while rows it still gets wrong (large gradients) matter most for improvement. So it keeps 100% of the top-gradient rows but randomly samples only a small fraction of the rest, then rescales the sampled low-gradient rows' weight upward so the overall gradient estimate stays roughly unbiased. This cuts the number of rows scanned for each split without discarding the examples doing the most work.

Exclusive feature bundling looks for features that are rarely both nonzero on the same row — common with one-hot encoded categorical variables — and merges several of them into one column, since a split test can still tell them apart by which value range each original feature occupied within the merged column. Bundling many such mutually-exclusive sparse features into one dramatically shrinks the effective number of columns a split search has to scan.

Worked example

Training on a dataset with 1 million rows where 90% already have tiny gradients after several boosting rounds, GOSS might keep all 100,000 high-gradient rows plus a 10% sample (90,000) of the low-gradient ones, scanning roughly 190,000 rows per split instead of 1 million — a more than 5x reduction with only a small increase in gradient-estimate noise.