Optimal and Adaptive Algorithms for Online Boosting
Abstract
We study online boosting, the task of converting any weak online learner into a strong online learner. Based on a novel and natural definition of weak online learnability, we develop two online boosting algorithms. The first algorithm is an online version of boost-by-majority. By proving a matching lower bound, we show that this algorithm is essentially optimal in terms of the number of weak learners and the sample complexity needed to achieve a specified accuracy. The second algorithm is adaptive and parameter-free, albeit not optimal.
Cite
Text
Beygelzimer et al. "Optimal and Adaptive Algorithms for Online Boosting." International Conference on Machine Learning, 2015.Markdown
[Beygelzimer et al. "Optimal and Adaptive Algorithms for Online Boosting." International Conference on Machine Learning, 2015.](https://mlanthology.org/icml/2015/beygelzimer2015icml-optimal/)BibTeX
@inproceedings{beygelzimer2015icml-optimal,
title = {{Optimal and Adaptive Algorithms for Online Boosting}},
author = {Beygelzimer, Alina and Kale, Satyen and Luo, Haipeng},
booktitle = {International Conference on Machine Learning},
year = {2015},
pages = {2323-2331},
volume = {37},
url = {https://mlanthology.org/icml/2015/beygelzimer2015icml-optimal/}
}