# Majority-of-Three is Optimal

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 9 references that are in the map.
- First posted on arXiv 11 Jun 2026.

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

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)

## Built on by (most cited first, 4 of 4)

- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification](https://mlsanity.com/paper/2608.20480/) (2026)
- [Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning](https://mlsanity.com/paper/2608.26516/) (2026)
- [Adversarially Robust PAC Learning with Optimal VC Rates](https://mlsanity.com/paper/2609.24260/) (2026)

## Abstract (arXiv)

We give a short proof that the majority vote of three independent consistent classifiers is an optimal learner in the realizable PAC setting. This proves optimality for the simplest voting scheme, while simplifying both the algorithmic structure and the probabilistic analysis of previous voting learners, including the algorithm of S. Hanneke and the analysis of bagging by K. Green Larsen.