AdaBoost is not an Optimal Weak to Strong Learner

Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:13118-13140, 2023.

Abstract

AdaBoost is a classic boosting algorithm for combining multiple inaccurate classifiers produced by a weak learner, to produce a strong learner with arbitrarily high accuracy when given enough training data. Determining the optimal number of samples necessary to obtain a given accuracy of the strong learner, is a basic learning theoretic question. Larsen and Ritzert (NeurIPS’22) recently presented the first provably optimal weak-to-strong learner. However, their algorithm is somewhat complicated and it remains an intriguing question whether the prototypical boosting algorithm AdaBoost also makes optimal use of training samples. In this work, we answer this question in the negative. Concretely, we show that the sample complexity of AdaBoost, and other classic variations thereof, are sub-optimal by at least one logarithmic factor in the desired accuracy of the strong learner.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-hogsgaard23a, title = {{A}da{B}oost is not an Optimal Weak to Strong Learner}, author = {H{\o}gsgaard, Mikael M{\o}ller and Larsen, Kasper Green and Ritzert, Martin}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {13118--13140}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/hogsgaard23a/hogsgaard23a.pdf}, url = {https://proceedings.mlr.press/v202/hogsgaard23a.html}, abstract = {AdaBoost is a classic boosting algorithm for combining multiple inaccurate classifiers produced by a weak learner, to produce a strong learner with arbitrarily high accuracy when given enough training data. Determining the optimal number of samples necessary to obtain a given accuracy of the strong learner, is a basic learning theoretic question. Larsen and Ritzert (NeurIPS’22) recently presented the first provably optimal weak-to-strong learner. However, their algorithm is somewhat complicated and it remains an intriguing question whether the prototypical boosting algorithm AdaBoost also makes optimal use of training samples. In this work, we answer this question in the negative. Concretely, we show that the sample complexity of AdaBoost, and other classic variations thereof, are sub-optimal by at least one logarithmic factor in the desired accuracy of the strong learner.} }
Endnote
%0 Conference Paper %T AdaBoost is not an Optimal Weak to Strong Learner %A Mikael Møller Høgsgaard %A Kasper Green Larsen %A Martin Ritzert %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-hogsgaard23a %I PMLR %P 13118--13140 %U https://proceedings.mlr.press/v202/hogsgaard23a.html %V 202 %X AdaBoost is a classic boosting algorithm for combining multiple inaccurate classifiers produced by a weak learner, to produce a strong learner with arbitrarily high accuracy when given enough training data. Determining the optimal number of samples necessary to obtain a given accuracy of the strong learner, is a basic learning theoretic question. Larsen and Ritzert (NeurIPS’22) recently presented the first provably optimal weak-to-strong learner. However, their algorithm is somewhat complicated and it remains an intriguing question whether the prototypical boosting algorithm AdaBoost also makes optimal use of training samples. In this work, we answer this question in the negative. Concretely, we show that the sample complexity of AdaBoost, and other classic variations thereof, are sub-optimal by at least one logarithmic factor in the desired accuracy of the strong learner.
APA
Høgsgaard, M.M., Larsen, K.G. & Ritzert, M.. (2023). AdaBoost is not an Optimal Weak to Strong Learner. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:13118-13140 Available from https://proceedings.mlr.press/v202/hogsgaard23a.html.

Related Material