Bagging is an Optimal PAC Learner

Speaker: Kasper Green Larsen, Asst. Professor, Dept. of Computer Science, Aarhus University , Aarhus University

Date: Tuesday, December 05, 2023

Time: 4:00 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G449 KIVA

Event Type: Seminar

Room Description: G449 KIVA

Host: Mohsen Ghaffari, CSAIL MIT


Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Kasper Green Larsen: 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.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2023.

Created by Nathan Higgins Email at Tuesday, November 14, 2023 at 2:57 PM.