Optimal and Adaptive Algorithms for Online Boosting
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 4120-4123.
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.
@inproceedings{ijcai2016p614,
title = {Optimal and Adaptive Algorithms for Online Boosting},
author = {Beygelzimer, Alina and Kale, Satyen and Luo, Haipeng},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {4120--4123},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/614},
}
TY - CPAPER TI - Optimal and Adaptive Algorithms for Online Boosting AU - Beygelzimer, Alina AU - Kale, Satyen AU - Luo, Haipeng T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 4120 EP - 4123 UR - https://ijcai.org/proceedings/2016/614 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
