Minimal Variance Sampling in Stochastic Gradient Boosting

Bulat Ibragimov, Gleb GusevNeurIPS 2019

TL;DR

This paper introduces Minimal Variance Sampling (MVS), a theoretically grounded subsampling method for Gradient Boosted Decision Trees (GBDT). By mathematically optimizing sampling probabilities to minimize the variance of split scoring, MVS achieves higher model accuracy and faster training times than existing techniques like uniform sampling or GOSS, and it is now a default feature in the popular CatBoost library.

What Problem Does This Paper Address?

Gradient Boosted Decision Trees (GBDT) are a "gold standard" for tabular data, but they face a major bottleneck: training time scales linearly with the number of data instances. To handle massive datasets, researchers use Stochastic Gradient Boosting (SGB), which trains each tree on a random subset of the data.

However, not all data points are created equal. Some instances provide more information for building a tree than others. While uniform sampling is simple, it often hurts model quality. Existing non-uniform methods, like Gradient-Based One-Side Sampling (GOSS) used in LightGBM, rely on empirical heuristics (keeping all "large gradient" samples and a random portion of "small gradient" ones). The authors identify a gap: there was no mathematically rigorous way to determine the optimal sampling probability for each instance to ensure the resulting trees are as accurate as possible.

Methods

The authors formulate the sampling problem as an optimization task. Their goal is to choose sampling probabilities $p_i$ that minimize the expected squared error of the split score—the metric used to decide where to branch a decision tree.

The MVS Formula

Through their theoretical analysis, they derive a closed-form solution for the optimal sampling probability $p_i$ for the $i$-th instance: $$p_i = \min\left(1, \frac{\sqrt{g_i^2 + \lambda h_i^2}}{\mu}\right)$$ Where:

  • $g_i$ is the gradient (first derivative of the loss).
  • $h_i$ is the hessian (second derivative).
  • $\lambda$ is a regularization parameter that balances the influence of the gradient magnitude against the sample size.
  • $\mu$ is a threshold chosen to satisfy a target "sample rate" (e.g., if you want to use only 20% of your data).

Key Innovations:

  1. Inverse Probability Weighting: To keep the estimates unbiased, sampled instances are assigned a weight $w_i = 1/p_i$.
  2. MVS Adaptive: The authors propose a version that automatically sets $\lambda$ based on the squared mean of leaf values, removing a hyperparameter for the user to tune.
  3. Efficient Thresholding: They provide an $O(N)$ algorithm (similar to quick-select) to find the threshold $\mu$ without needing to fully sort the gradients at every iteration.

Datasets

The researchers evaluated MVS across a diverse set of benchmarks:

  • Standard Benchmarks: KDD Internet, Adult, Amazon, KDD Upselling, Kick prediction, KDD Churn, and Click prediction.
  • Large-Scale Datasets: The Higgs dataset (11 million instances) and Recsys datasets (16.5 million instances) were used to demonstrate speedups on industry-scale problems.
  • CatBoost Internal Benchmark: A massive test suite of 153 proprietary and public binary classification datasets.

Key Insights and Ideas

  • Split Scoring is the Target: Unlike previous work that focused on estimating the global loss, MVS focuses on the accuracy of the split score. This is crucial because GBDT builds trees by comparing scores of candidate splits; if the scores are noisy, the algorithm picks the wrong splits.
  • The $\lambda$ Tradeoff: Setting $\lambda=0$ leads to "Importance Sampling," which can be unstable when gradients are near zero. Setting $\lambda \to \infty$ leads to uniform sampling. MVS finds the optimal middle ground where "informative" samples (high gradients) are prioritized, but "well-trained" samples are still represented to maintain stability.
  • Regularization via Sampling: Interestingly, the authors show that MVS doesn't just speed up training; it often improves generalization (test accuracy) by acting as a form of regularization, reducing the pairwise correlation between trees in the ensemble.

Key Results

  • Superior Accuracy: In a benchmark of 153 datasets, MVS outperformed the default CatBoost settings (no sampling) in 97 cases, compared to only 55 wins for the default.
  • Better than GOSS: MVS consistently achieved lower error rates than GOSS and uniform SGB across various sampling rates. For example, on the Amazon dataset, MVS at a 10% sample rate performed significantly better than GOSS at the same rate.
  • Significant Speedups: On the Recsys dataset, MVS achieved a 61.5% reduction in training time (using a 10% sample rate) while maintaining or improving model quality.
  • Integration: The method was so successful it was implemented as the new default subsampling option in CatBoost.

Limitations and Future Work

  • Hessian Dependence: The method relies on having access to hessians ($h_i$). While common in many loss functions (like LogLoss), for some custom loss functions where the second derivative is zero or constant, the advantage of the $\lambda h_i^2$ term might be diminished.
  • Hyperparameter Sensitivity: While "MVS Adaptive" helps, the performance can still be sensitive to the choice of the sample rate, which remains a manual choice for the user.
  • Scope: The paper focuses on GBDT. While the logic of variance-minimized sampling is general, its application to other iterative algorithms (like neural network mini-batching) is suggested but not explored here.

Summary updated

BibTeX
@inproceedings{ibragimov2019minimal,
  author = {Bulat Ibragimov and Gleb Gusev},
  title = {{Minimal Variance Sampling in Stochastic Gradient Boosting}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure