DeLTA seminar by Kasper Green Larsen: Bagging is an Optimal PAC Learner

Delta logo

Zoom link


Kasper Green Larsen, Professor at the Department of Computer Science at Aarhus University.

Portrait of Kasper


Bagging is an Optimal PAC Learner


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 talk, we prove the surprising result that the practical and classic heuristic 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.

This work was published at COLT’23 and received the Best Paper Award.


You can subscribe to the DeLTA Seminar mailing list by sending an empty email to
Online calendar
DeLTA Lab page