Majority-of-Three is Optimal

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.

ML methods stat.ML cs.LG math.ST

View graph Source

Paper

Similar papers

Majority-of-Three: The Simplest Optimal Learner?Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen et al.2024 · arXiv (Cornell University) In Library

Bagging is an Optimal PAC LearnerKasper Green Larsen2022 · arXiv (Cornell University) In Library

Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization BoundValentina Zantedeschi, Paul Viallard, Emilie Morvant et al.2021 · arXiv (Cornell University) · 21 citations In Library

Optimal PAC Bounds without Uniform ConvergenceIshaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty et al.2023 In Library

Optimal PAC Bounds Without Uniform ConvergenceIshaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty et al.2023 · arXiv (Cornell University) In Library

Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning AlgorithmPascal Germain, A. Lacasse, François Laviolette et al.2015 · Journal of machine learning research · 156 citations In Library

Proper Learning, Helly Number, and an Optimal SVM BoundOlivier Bousquet, Steve Hanneke, Shay Moran et al.2020 · arXiv (Cornell University) In Library

Second Order PAC-Bayesian Bounds for the Weighted Majority VoteAndrés R. Masegosa, Stephan Sloth Lorenzen, Christian Igel et al.2020 · Research at the University of Copenhagen (University of Copenhagen) In Library

On Agnostic PAC Learning in the Small Error RegimeJulian Asilis, M. Hogsgaard, Grigoris Velegkas2025 · Neural Information Processing Systems · 2 citations In Library

Second Order PAC-Bayesian Bounds for the Weighted Majority VoteAndrés R. Masegosa, Stephan Sloth Lorenzen, Christian Igel et al.2020 · arXiv (Cornell University) · 46 citations In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal