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.

本文通过优化随机梯度增强（SGB）各节点采样的概率，提出了一种新的迭代加速技术 Minimal Variance Sampling (MVS)。该方法不仅能够减少每次迭代所需样本数，而且还能够显著提高模型的质量，因此提出 MVS 为新的默认选项，用于 CatBoost 这一基于梯度增强的机器学习库中。

随机梯度提升中的最小方差抽样