Majority-of-Three is Optimal
arXiv:2606.13614v19.9
Predicted impact top 26% in ML · last 90 daysOriginality Incremental advance
AI Analysis
Provides a simpler optimal algorithm for PAC learning, of interest to learning theory researchers.
The paper proves that the majority vote of three independent consistent classifiers achieves optimal learning in the realizable PAC setting, simplifying previous voting-based learners.
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.