Majority-of-Three Voting Proved Optimal for PAC Learning
Three independent classifiers achieve optimal learning with a simple majority vote.
In a new arXiv paper, researchers Divit Rawal and Nikita Zhivotovskiy from UC Berkeley and ETH Zurich prove that majority voting among three independent, consistent classifiers achieves optimal performance in the realizable Probably Approximately Correct (PAC) learning framework. The result is striking because it uses the simplest possible voting scheme—just three models—to match the theoretical lower bound for any learner. The authors provide a short, elegant proof that simplifies earlier work by S. Hanneke and K. Green Larsen, who required more complex ensembles and analyses.
The finding has practical implications for ensemble methods: practitioners can now rely on a minimal ensemble of three models to guarantee optimal generalization, reducing computational overhead while maintaining theoretical rigor. The proof relies on the assumption that classifiers are independent and consistent (i.e., they perfectly fit the training data). While the realizable PAC setting is idealized, this work strengthens the theoretical foundation for bagging and boosting, and may guide new algorithm designs where small ensembles are preferable to large ones.
- Proves that majority vote of three independent consistent classifiers is optimal in realizable PAC learning.
- Simplifies previous algorithms by Hanneke (optimal voting schemes) and bagging analysis by Green Larsen.
- Short 9-page proof with minimal assumptions; uses only three classifiers instead of larger ensembles.
Why It Matters
Offers a theoretically grounded minimal ensemble approach, potentially reducing compute costs in reliable AI systems.