mlsanityData to 7 Oct 2026

Majority-of-Three is Optimal

arXiv 2606.13614 ↗First posted 11 Jun 2026stat.ML cs.LG math.STcited by 4

Not on the map. Why?

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.

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

Builds on

4 of 9 references.

References · 4

  1. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  2. 2022Bagging is an Optimal PAC Learnercited by 34
  3. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  4. 2024Majority-of-Three: The Simplest Optimal Learner?cited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Bagging Robustly Learns VC Classes with Linear Sample Complexitycited by 1
  2. 2026When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classificationcited by 0
  3. 2026Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learningcited by 0
  4. 2026Adversarially Robust PAC Learning with Optimal VC Ratescited by 0