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. PDF
Cite
Text
Beygelzimer et al. "Optimal and Adaptive Algorithms for Online Boosting." International Joint Conference on Artificial Intelligence, 2016.Markdown
[Beygelzimer et al. "Optimal and Adaptive Algorithms for Online Boosting." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/beygelzimer2016ijcai-optimal/)BibTeX
@inproceedings{beygelzimer2016ijcai-optimal,
title = {{Optimal and Adaptive Algorithms for Online Boosting}},
author = {Beygelzimer, Alina and Kale, Satyen and Luo, Haipeng},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2016},
pages = {4120-4124},
url = {https://mlanthology.org/ijcai/2016/beygelzimer2016ijcai-optimal/}
}