Weighted quantile sketch is XGBoost’s approximate split-finding algorithm. It estimates useful feature split points with quantiles while accounting for Hessian-weighted training examples, trading exactness for faster tree learning. section 6.3.1
Its practical intuition is close to histogram-based splitting, with important differences:
- It bins feature values instead of evaluating every possible split. section 6.3.1
- It creates feature-dependent buckets rather than evenly sized bins. section 6.3.1
- It incorporates Hessian weights required by Newton boosting, unlike gradient-boosting implementations where examples are treated equally. section 6.3.1
- It supports scalable training alongside presorted data blocks, caching, compression, and sharding. section 6.3.1
The full sketch construction and implementation are intricate, so the key operational takeaway is its efficiency–exactness tradeoff: approximate, weight-aware split selection enables Newton boosting on very large datasets. section 6.3.1 section 6.6
