Bagging is an Optimal PAC Learner

Kasper Green Larsen
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:450-468, 2023.

Abstract

Determining the optimal sample complexity of PAC learning in the realizable setting was a central open problem in learning theory for decades. Finally, the seminal work by Hanneke (2016) gave an algorithm with a provably optimal sample complexity. His algorithm is based on a careful and structured sub-sampling of the training data and then returning a majority vote among hypotheses trained on each of the sub-samples. While being a very exciting theoretical result, it has not had much impact in practice, in part due to inefficiency, since it constructs a polynomial number of sub-samples of the training data, each of linear size.In this work, we prove the surprising result that the practical and classic heuristic \emph{bagging} (a.k.a. bootstrap aggregation), due to Breiman (1996), is in fact also an optimal PAC learner. Bagging pre-dates Hanneke’s algorithm by twenty years and is taught in most undergraduate machine learning courses. Moreover, we show that it only requires a logarithmic number of sub-samples to reach optimality.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-larsen23a, title = {Bagging is an Optimal PAC Learner}, author = {Larsen, Kasper Green}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {450--468}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/larsen23a/larsen23a.pdf}, url = {https://proceedings.mlr.press/v195/larsen23a.html}, abstract = {Determining the optimal sample complexity of PAC learning in the realizable setting was a central open problem in learning theory for decades. Finally, the seminal work by Hanneke (2016) gave an algorithm with a provably optimal sample complexity. His algorithm is based on a careful and structured sub-sampling of the training data and then returning a majority vote among hypotheses trained on each of the sub-samples. While being a very exciting theoretical result, it has not had much impact in practice, in part due to inefficiency, since it constructs a polynomial number of sub-samples of the training data, each of linear size.In this work, we prove the surprising result that the practical and classic heuristic \emph{bagging} (a.k.a. bootstrap aggregation), due to Breiman (1996), is in fact also an optimal PAC learner. Bagging pre-dates Hanneke’s algorithm by twenty years and is taught in most undergraduate machine learning courses. Moreover, we show that it only requires a logarithmic number of sub-samples to reach optimality. } }
Endnote
%0 Conference Paper %T Bagging is an Optimal PAC Learner %A Kasper Green Larsen %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-larsen23a %I PMLR %P 450--468 %U https://proceedings.mlr.press/v195/larsen23a.html %V 195 %X Determining the optimal sample complexity of PAC learning in the realizable setting was a central open problem in learning theory for decades. Finally, the seminal work by Hanneke (2016) gave an algorithm with a provably optimal sample complexity. His algorithm is based on a careful and structured sub-sampling of the training data and then returning a majority vote among hypotheses trained on each of the sub-samples. While being a very exciting theoretical result, it has not had much impact in practice, in part due to inefficiency, since it constructs a polynomial number of sub-samples of the training data, each of linear size.In this work, we prove the surprising result that the practical and classic heuristic \emph{bagging} (a.k.a. bootstrap aggregation), due to Breiman (1996), is in fact also an optimal PAC learner. Bagging pre-dates Hanneke’s algorithm by twenty years and is taught in most undergraduate machine learning courses. Moreover, we show that it only requires a logarithmic number of sub-samples to reach optimality.
APA
Larsen, K.G.. (2023). Bagging is an Optimal PAC Learner. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:450-468 Available from https://proceedings.mlr.press/v195/larsen23a.html.

Related Material