Online Gradient Boosting
Alina Beygelzimer, Elad Hazan, Satyen Kale, Haipeng Luo
Abstract
We extend the theory of boosting for regression problems to the online learning setting. Generalizing from the batch setting for boosting, the notion of a weak learning algorithm is modeled as an online learning algorithm with linear loss functions that competes with a base class of regression functions, while a strong learning algorithm is an online learning algorithm with smooth convex loss functions that competes with a larger class of regression functions. Our main result is an online gradient boosting algorithm which converts a weak online learning algorithm into a strong one where the larger class of functions is the linear span of the base class. We also give a simpler boosting algorithm that converts a weak online learning algorithm into a strong one where the larger class of functions is the convex hull of the base class, and prove its optimality.
BibTeX
@inproceedings{NIPS2015_0a1bf96b,
author = {Beygelzimer, Alina and Hazan, Elad and Kale, Satyen and Luo, Haipeng},
booktitle = {Advances in Neural Information Processing Systems},
editor = {C. Cortes and N. Lawrence and D. Lee and M. Sugiyama and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Online Gradient Boosting},
url = {https://proceedings.neurips.cc/paper_files/paper/2015/file/0a1bf96b7165e962e90cb14648c9462d-Paper.pdf},
volume = {28},
year = {2015}
}