# Bagging is an Optimal PAC Learner

arXiv: https://arxiv.org/abs/2212.02264 · HTML: https://mlsanity.com/paper/2212.02264/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 19 references that are in the map.
- First posted on arXiv 5 Dec 2022.

## Builds on (most cited first, 2 of 2)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Optimal Weak to Strong Learning](https://mlsanity.com/paper/2206.01563/) (2022)

## Built on by (most cited first, 30 of 34)

- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Bagging Provides Assumption-free Stability](https://mlsanity.com/paper/2301.12600/) (2023)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [Revisiting Agnostic PAC Learning](https://mlsanity.com/paper/2407.19777/) (2024)
- [The Impossibility of Parallelizing Boosting](https://mlsanity.com/paper/2301.09627/) (2023)
- [AdaBoost is not an Optimal Weak to Strong Learner](https://mlsanity.com/paper/2301.11571/) (2023)
- [Are Ensembles Getting Better all the Time?](https://mlsanity.com/paper/2311.17885/) (2023)
- [On Agnostic PAC Learning in the Small Error Regime](https://mlsanity.com/paper/2502.09496/) (2025)
- [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024)
- [Improved Margin Generalization Bounds for Voting Classifiers](https://mlsanity.com/paper/2502.16462/) (2025)
- [Learning with Monotone Adversarial Corruptions](https://mlsanity.com/paper/2601.02193/) (2026)
- [Majority-of-Three is Optimal](https://mlsanity.com/paper/2606.13614/) (2026)
- [Boosting, Voting Classifiers and Randomized Sample Compression Schemes](https://mlsanity.com/paper/2402.02976/) (2024)
- [The Cost of Parallelizing Boosting](https://mlsanity.com/paper/2402.15145/) (2024)
- [The Many Faces of Optimal Weak-to-Strong Learning](https://mlsanity.com/paper/2408.17148/) (2024)
- [Understanding Aggregations of Proper Learners in Multiclass Classification](https://mlsanity.com/paper/2410.22749/) (2024)
- [Proper Learnability and the Role of Unlabeled Data](https://mlsanity.com/paper/2502.10359/) (2025)
- [Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets](https://mlsanity.com/paper/2511.20407/) (2025)
- [The Sample Complexity of Replicable Realizable PAC Learning](https://mlsanity.com/paper/2602.19552/) (2026)
- [An Optimal Agnostic PAC Algorithm](https://mlsanity.com/paper/2608.06363/) (2026)
- [Universal rates of ERM for agnostic learning](https://mlsanity.com/paper/2506.14110/) (2025)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [PAC-Causal Learnability: From Identification to Finite-Sample Guarantees](https://mlsanity.com/paper/2507.18903/) (2025)
- [A One-Inclusion Graph Approach to Multi-Group Learning](https://mlsanity.com/paper/2603.23208/) (2026)
- [A Fine-Grained Understanding of Uniform Convergence for Halfspaces](https://mlsanity.com/paper/2605.06004/) (2026)
- [The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity](https://mlsanity.com/paper/2605.29819/) (2026)
- [Surprises in Proper Positive-Only Learning](https://mlsanity.com/paper/2606.28309/) (2026)

## Abstract (arXiv)

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 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.