Bagging is an Optimal PAC Learner (Extended Abstract)

Kasper Green LarsenIJCAI 2024

Kasper Green Larsen
Extended Abstract of the IJCAI-24 Best Paper (originally appearing at COLT 2023)

Introduction

For decades, a fundamental quest in computational learning theory has been the search for a "perfect" algorithm—one that achieves the absolute minimum sample complexity required to learn a task. In the framework of "Probably Approximately Correct" (PAC) learning, the goal is to identify a hypothesis that predicts labels correctly with high probability using as few training samples ($m$) as possible.

While theoretical solutions achieving optimal sample complexity were recently discovered, they were often criticized for being "theoretical beasts"—mathematically sound but too complex for practical implementation. This paper provides a landmark result by proving that Bagging (Bootstrap Aggregation), a simple and ubiquitous algorithm introduced by Leo Breiman in 1996, is actually an optimal PAC learner. This discovery bridges a 30-year gap between empirical success and theoretical justification.

The PAC Learning Gap

In the "realizable" setting of PAC learning, we assume that a perfect classifier exists within our chosen model class. For years, the standard approach was Empirical Risk Minimization (ERM), which involves selecting any model that fits the training data perfectly. However, ERM is known to be slightly sub-optimal; it typically requires a factor of $\log(1/\epsilon)$ more data than the theoretical lower bound suggests is necessary.

In 2016, Steve Hanneke closed this gap by proposing an optimal algorithm. However, Hanneke’s construction required splitting data into a massive number of subsets ($m^{0.79}$), making it computationally prohibitive. The central question remained: Does a simpler, more practical algorithm exist that achieves this same theoretical peak?

Bagging: The Simple Solution

Bagging is a staple of machine learning education and practice. The procedure is straightforward:

  1. Given a training set $S$ of size $m$, create $t$ "bootstrap" samples by picking $n$ items from $S$ at random with replacement.
  2. Train an ERM model on each bootstrap sample.
  3. Predict the final label by taking a majority vote among all $t$ models.

Larsen’s work provides a new mathematical proof showing that this heuristic is not merely a useful trick for reducing variance, but a theoretically optimal learner. The proof demonstrates that the randomness inherent in bagging mimics the structured sub-sampling used in more complex optimal algorithms, but with significantly higher efficiency.

Key Insights

The Power of Leaving Data Out

The core mechanism behind Bagging’s optimality is its ability to create diversity. Because each bootstrap sample leaves out a significant portion of the training data (approximately $1/e \approx 37\%$), different models in the "bag" are exposed to different perspectives of the data. This creates enough independence for the majority vote to cancel out the "bad" hypotheses that a single ERM might otherwise select.

Efficiency Leap

While previous optimal algorithms required a polynomial number of sub-samples ($m^{0.79}$), Larsen proves that Bagging only requires a logarithmic number of sub-samples ($O(\log m)$) to reach optimality. This makes Bagging significantly faster and more practical than any previously known optimal learner.

Margin Analysis

The proof utilizes "voting classifier" theory and margin analysis. It shows that if the average performance across all possible bootstrap samples is strong, then a small random selection of those samples will maintain a sufficient "margin" of consensus to ensure optimal generalization.

Main Results

The paper establishes that Bagging achieves the optimal sample complexity of: $$O\left(\frac{d + \log(1/\delta)}{\epsilon}\right)$$ where $d$ is the VC-dimension of the concept class, $\epsilon$ is the error parameter, and $\delta$ is the failure probability.

According to the proof, this optimality is reached when:

  • The number of bootstrap samples $t$ is at least $18 \ln(2m/\delta)$.
  • The bootstrap sample size $n$ is at least $2\%$ of the original training set size $m$.

Limitations and Future Directions

Despite the theoretical breakthrough, the author notes several areas for further refinement:

  • The Constant Factor: The universal constant $a$ used in the proof is currently very large. While the scaling is optimal, the actual number of samples required by the current mathematical derivation is much higher than what practitioners use in the field.
  • Dependency on $\delta$: Unlike Hanneke’s algorithm, the number of sub-samples in Bagging currently depends on the failure probability $\delta$. It remains an open question whether this dependency is a fundamental requirement or an artifact of the current proof.
  • Agnostic Setting: This proof is limited to the "realizable" setting. Extending these results to the "agnostic" setting—where data may be noisy and no perfect classifier exists—is a primary goal for future research.

Conclusion

By proving that Bagging is an optimal PAC learner, this paper elevates a 30-year-old industry standard to the highest tier of theoretical efficiency. It confirms that practitioners have been using an optimal tool all along, providing a rigorous foundation for one of the most successful algorithms in the history of machine learning.

Summary updated

BibTeX
@inproceedings{larsen2024bagging,
  author = {Kasper Green Larsen},
  title = {{Bagging is an Optimal PAC Learner (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure