Minimal Variance Sampling in Stochastic Gradient Boosting

[StrikerRUS]

Summary

MVS can be considered as an improved version of the Gradient-based One-Side Sampling (GOSS, see details in the paper) implemented in LightGBM, which samples a given number of top examples by values |gi| with the probability 1 and samples other examples with the same fixed probability. Due to the theoretical basis, MVS provides a lower variance of the estimate Eg than GOSS.

References

Docs:

• https://catboost.ai/docs/concepts/algorithm-main-stages_bootstrap-options.html

Code:

• catboost/catboost@0bd529c
• https://github.com/catboost/catboost/pull/1005/files

NeurIPS 2019 Poster:

• https://github.com/ibr11/mvs_paper/raw/master/mvs_poster.pdf

NeurIPS 2019 Paper:

• http://papers.nips.cc/paper/9645-minimal-variance-sampling-in-stochastic-gradient-boosting.pdf

[StrikerRUS]

Closed in favor of being in #2302. We decided to keep all feature requests in one place.

Welcome to contribute this feature! Please re-open this issue (or post a comment if you are not a topic starter) if you are actively working on implementing this feature.

[guolinke]

refer to https://github.com/ibr11/LightGBM

[StrikerRUS]

@guolinke Exciting!
However, the author disabled possibility to open issues in that repo and I can't find their contact info in the GitHub profile to ask for creating a PR.

What do you think about borrowing that code with referring to the author. I guess if the author wished to contribute to the upstream repo, it was enough time to do it from the latest commits...

[StrikerRUS]

Uhhh, just noticed that this is one of the authors of MVS!

[StrikerRUS]

Closing according to #5091 (comment).

Welcome to contribute this feature! Feel free to fork https://github.com/microsoft/LightGBM/tree/mvs_dev branch.