XGBoost: A Scalable Tree Boosting System

Tianqi Chen and Carlos Guestrin (University of Washington), KDD 2016. T1 — the system paper, read from the PDF. The reason gradient boosting is the default tabular method rather than one option among several.

The claim that made it famous

“Among the 29 challenge winning solutions published at Kaggle’s blog during 2015, 17 solutions used XGBoost.” Eight of those used it alone; most of the rest ensembled it with neural nets. The runner-up method, deep neural networks, appears in 11. In KDDCup 2015 “XGBoost was used by every winning team in the top-10,” and those teams reported that ensembling beat “a well-configured XGBoost by only a small amount.”

The paper’s own framing is worth keeping: the algorithm is not new — gradient boosting is Friedman’s — and the contribution is a system. What changed was that the method became cheap enough to try first.

What the system actually contributes

• A sparsity-aware split-finding algorithm. Missing values, one-hot columns and zero entries get a default direction learned per split rather than imputation.
• A weighted quantile sketch for proposing split candidates under instance weights, with a theoretical guarantee — the piece that makes approximate (rather than exact greedy) tree learning safe.
• Cache-aware block structure and out-of-core computation, so the data need not fit in RAM.
• Column subsampling and a regularized objective, both of which also help against overfitting.

The measurements

On Higgs-1M with 500 trees, exact greedy: XGBoost 0.68 s per tree at 0.8304 test AUC, scikit-learn 28.51 s at 0.8302 — same accuracy, roughly 40× the speed — and R’s gbm at 1.03 s but only 0.6224 AUC (it uses a different, less complete algorithm). Out-of-core, on the Criteo terabyte click log (1.7 billion instances after preprocessing, 67 features, over 1 TB in LibSVM format), the final method “is able to process 1.7 billion examples on a single machine,” with the file-cache transition visible in the timings. Distributed runs use a YARN cluster of EC2 m3.2xlarge machines.

Why the spoke needed it

classical-ml-algorithms was carrying the whole non-deep story alone. This page supplies the tabular default, and — with tabular-deep-learning-benchmark — the baseline that open question 7 asks for: a time-series foundation model beating seasonal-naive on synthetic data (timesfm-2-5-forecasting-tutorial) has not been compared to the thing practitioners would actually reach for.