# Minimal Variance Sampling in Stochastic Gradient Boosting

arXiv: https://arxiv.org/abs/1910.13204 · HTML: https://mlsanity.com/paper/1910.13204/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2019.

## Built on by (most cited first, 5 of 5)

- [Towards Computationally Feasible Deep Active Learning](https://mlsanity.com/paper/2205.03598/) (2022)
- [SketchBoost: Fast Gradient Boosted Decision Tree for Multioutput Problems](https://mlsanity.com/paper/2211.12858/) (2022)
- [Gradient Boosting Performs Gaussian Process Inference](https://mlsanity.com/paper/2206.05608/) (2022)
- [Histogram-Based Federated XGBoost using Minimal Variance Sampling for Federated Tabular Data](https://mlsanity.com/paper/2405.02067/) (2024)
- [Subsampled Ensemble Can Improve Generalization Tail Exponentially](https://mlsanity.com/paper/2405.14741/) (2024)

## Abstract (arXiv)

Stochastic Gradient Boosting (SGB) is a widely used approach to regularization of boosting models based on decision trees. It was shown that, in many cases, random sampling at each iteration can lead to better generalization performance of the model and can also decrease the learning time. Different sampling approaches were proposed, where probabilities are not uniform, and it is not currently clear which approach is the most effective. In this paper, we formulate the problem of randomization in SGB in terms of optimization of sampling probabilities to maximize the estimation accuracy of split scoring used to train decision trees. This optimization problem has a closed-form nearly optimal solution, and it leads to a new sampling technique, which we call Minimal Variance Sampling (MVS). The method both decreases the number of examples needed for each iteration of boosting and increases the quality of the model significantly as compared to the state-of-the art sampling methods. The superiority of the algorithm was confirmed by introducing MVS as a new default option for subsampling in CatBoost, a gradient boosting library achieving state-of-the-art quality on various machine learning tasks.