Pith. sign in

REVIEW 2 major objections 2 cited by

Majority-of-Three is Optimal

T0 review · 2 major / 0 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The majority vote of three independent consistent classifiers is an optimal learner in the realizable PAC setting.

desk verdict Short proof that majority-of-three is optimal in realizable PAC with independent consistent classifiers, simplifying earlier voting analyses but remaining narrow in scope. read the letter →

arxiv 2606.13614 v1 pith:36CZ2O5R submitted 2026-06-11 stat.ML cs.LGmath.STstat.TH

Divit Rawal , Nikita Zhivotovskiy This is my paper · ORCID
classification stat.MLcs.LGmath.STstat.TH
keywords PAClearningmajorityvoteconsistentclassifiersrealizablesettingoptimallearnersamplecomplexityvotingschemes
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the majority vote among three independent classifiers, each consistent with the training data, yields an optimal learner in the realizable PAC model where a perfect hypothesis exists. This result shows that the simplest possible voting rule suffices to match known optimal sample complexity bounds. The short proof simplifies both the construction and the analysis used in earlier optimal voting schemes. A reader would care because it reduces the ensemble size and proof complexity needed to achieve the best guarantees in this standard learning framework.

What carries the argument

Majority vote of three independent consistent classifiers, which returns the label agreed upon by at least two of them.

What would settle it

A realizable PAC learning problem together with three independent consistent classifiers whose majority vote fails to achieve the known optimal sample complexity lower bound.

Watch

Extended reading notes

Core claim

In the realizable PAC setting, the majority vote of three independent consistent classifiers is an optimal learner. The proof establishes this optimality directly and simplifies prior results on more elaborate voting learners, including Hanneke's algorithm and the analysis of bagging.

Load-bearing premise

The three classifiers must be independent and each must be consistent with zero training error on samples drawn from a distribution that admits a zero-risk hypothesis.

Editorial extensions

If this is right

  • It supplies a simpler algorithmic structure than previous optimal voting learners.
  • It simplifies the probabilistic analysis required for bagging.
  • Optimal performance is achieved with the smallest non-trivial number of classifiers.
  • The result applies to any collection of independent consistent learners.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The emphasis on independence may suggest ways to enforce or approximate it in practical ensemble training.
  • The minimal ensemble size invites direct empirical checks on whether three classifiers suffice in benchmark realizable tasks.
  • The short proof technique could be examined for extension to other small fixed ensemble sizes.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 0 minor

Summary. The paper claims to give a short proof that the majority vote of three independent consistent classifiers is an optimal learner in the realizable PAC setting. It positions this result as proving optimality for the simplest voting scheme while simplifying the algorithmic structure and probabilistic analysis of previous voting learners, including the algorithm of S. Hanneke and the analysis of bagging by K. Green Larsen.

Significance. If the claimed proof holds and the requisite definitions are supplied, the result would establish optimality of a minimal ensemble method under standard realizable PAC assumptions, offering a direct and simplified alternative to more involved voting constructions in the literature.

major comments (2)
  1. [Abstract] Abstract: the manuscript states that it 'give[s] a short proof' of optimality, yet supplies neither the proof, the formal definition of independence among the three classifiers, the precise optimality criterion (e.g., whether it is minimax, asymptotic, or sample-complexity optimal), nor any derivation steps. The central claim therefore cannot be evaluated for correctness or gaps.
  2. [Full text] Full text: no measure-theoretic assumptions, no statement of the PAC model, and no derivation are present, so it is impossible to check whether the claimed direct proof avoids the circularity or post-hoc fitting issues that the reader flags as absent.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the comments, which identify areas where the manuscript requires greater explicitness to allow independent verification. We will revise the paper to incorporate formal statements of the model, definitions, and the complete proof with all steps.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the manuscript states that it 'give[s] a short proof' of optimality, yet supplies neither the proof, the formal definition of independence among the three classifiers, the precise optimality criterion (e.g., whether it is minimax, asymptotic, or sample-complexity optimal), nor any derivation steps. The central claim therefore cannot be evaluated for correctness or gaps.

    Authors: We agree the abstract is overly concise. In revision we will expand it to state that optimality refers to matching the minimax sample complexity lower bound in the realizable PAC setting. We will also note the independence assumption (classifiers trained on independent samples) and direct readers to the expanded proof in the body. All derivation steps will be supplied in the main text. revision: yes

  2. Referee: [Full text] Full text: no measure-theoretic assumptions, no statement of the PAC model, and no derivation are present, so it is impossible to check whether the claimed direct proof avoids the circularity or post-hoc fitting issues that the reader flags as absent.

    Authors: The manuscript was written under the assumption of standard PAC background. We will add an explicit preliminary section stating the realizable PAC model (including the underlying probability space), the definition of consistency, and the precise independence condition on the three classifiers. The proof will be rewritten with every derivation step shown, allowing direct inspection that no circularity or post-hoc fitting occurs. This addresses the evaluation concern. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

Direct mathematical proof; no circular reductions identified

full rationale

The paper states it gives a short proof that majority vote of three independent consistent classifiers is optimal in the realizable PAC setting. The abstract and description indicate a direct proof of optimality rather than any parameter fitting, self-referential definitions, or load-bearing self-citations. No equations or steps are presented that reduce the claimed result to its own inputs by construction. Citations to prior work (Hanneke, Larsen) are to external results and do not form a self-citation chain. The derivation is therefore self-contained as a proof.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The claim rests on the standard definition of realizable PAC learning and the assumption that the three classifiers are independent and consistent; no free parameters or invented entities are mentioned.

assumptions (1)
  • domain assumption Realizable PAC setting with consistent learners
    Invoked directly in the abstract as the framework for optimality.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Majority-of-Three is Optimal." pith.science (2026). https://pith.science/paper/36CZ2O5R

@misc{pith2026260613614,
  author       = {Pith},
  title        = {Pith review of: Majority-of-Three is Optimal},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/36CZ2O5R}},
  note         = {Machine review of arXiv:2606.13614}
}
read the original abstract

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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Bagging Robustly Learns VC Classes with Linear Sample Complexity

    stat.ML 2026-08 conditional novelty 8.0 of 10

    Bagging robust ERMs achieves robust risk O(d/n) for VC classes with VC dimension d, and Ω(d*) RERM calls are necessary where d* is the dual VC dimension.

  2. An Optimal Agnostic PAC Algorithm

    cs.LG 2026-08 conditional novelty 8.0 of 10

    An agnostic PAC learner attains excess risk L* + C(√(L*d'/n) + d'/n) with d' = d + log(1/δ), matching known lower bounds up to constants.

Reference graph

Works this paper leans on

18 extracted references · 1 canonical work pages · cited by 2 Pith papers

  1. [1]

    Vapnik, V. N. and Chervonenkis, A. Ya. , title =. Theory of Probability & Its Applications , volume =. 1971 , doi =

    1971

  2. [2]

    , title =

    Valiant, Leslie G. , title =. Communications of the ACM , volume =. 1984 , doi =

    1984

  3. [3]

    Information and Computation , volume=

    A general lower bound on the number of examples needed for learning , author=. Information and Computation , volume=. 1989 , publisher=

    1989

  4. [4]

    , title =

    Blumer, Anselm and Ehrenfeucht, Andrzej and Haussler, David and Warmuth, Manfred K. , title =. Journal of the ACM , volume =. 1989 , doi =

    1989

  5. [5]

    , title =

    Simon, Hans U. , title =. Proceedings of The 28th Conference on Learning Theory , pages =. 2015 , editor =

    2015

  6. [6]

    Journal of Machine Learning Research , volume =

    Hanneke, Steve , title =. Journal of Machine Learning Research , volume =. 2016 , url =

    2016

  7. [7]

    Machine Learning , volume =

    Breiman, Leo , title =. Machine Learning , volume =. 1996 , doi =

    1996

  8. [8]

    Proceedings of Thirty Sixth Conference on Learning Theory , pages =

    Larsen, Kasper Green , title =. Proceedings of Thirty Sixth Conference on Learning Theory , pages =. 2023 , editor =

    2023

Show all 18 references
  1. [9]

    Majority-of-Three: The Simplest Optimal Learner? , booktitle =

    Aden-Ali, Ishaq and H. Majority-of-Three: The Simplest Optimal Learner? , booktitle =. 2024 , editor =

    2024

  2. [10]

    and Chi, Ed H

    Wang, Xuezhi and Wei, Jason and Schuurmans, Dale and Le, Quoc V. and Chi, Ed H. and Narang, Sharan and Chowdhery, Aakanksha and Zhou, Denny , title =. The Eleventh International Conference on Learning Representations , year =

  3. [11]

    2023 , eprint =

    Zheng, Chuanyang and Liu, Zhengying and Xie, Enze and Li, Zhenguo and Li, Yu , title =. 2023 , eprint =

    2023

  4. [12]

    Zheng, Daniel and von Glehn, Ingrid and Zwols, Yori and Beloshapka, Iuliya and Buesing, Lars and Roy, Daniel M. and Wattenberg, Martin and Georgiev, Bogdan and Schmidt, Tatiana and Cowie, Andrew and Viegas, Fernanda and Kanevsky, Dimitri and Kahlon, Vineet and Maennel, Hartmut...

    2026

  5. [13]

    Discrete & Computational Geometry , volume =

    Haussler, David and Welzl, Emo , title =. Discrete & Computational Geometry , volume =. 1987 , doi =

    1987

  6. [14]

    Improved Margin Generalization Bounds for Voting Classifiers , booktitle =

    H. Improved Margin Generalization Bounds for Voting Classifiers , booktitle =. 2025 , editor =

    2025

  7. [15]

    , title =

    Haussler, David and Littlestone, Nick and Warmuth, Manfred K. , title =. Information and Computation , volume =. 1994 , doi =

    1994

  8. [16]

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Aden-Ali, Ishaq and Cherapanamjeri, Yeshwanth and Shetty, Abhishek and Zhivotovskiy, Nikita , title =. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2023 , publisher =. doi:10.1109/FOCS57990.2023.00071 , url =

    2023 doi

  9. [17]

    Proceedings of Thirty Sixth Conference on Learning Theory , pages =

    Aden-Ali, Ishaq and Cherapanamjeri, Yeshwanth and Shetty, Abhishek and Zhivotovskiy, Nikita , title =. Proceedings of Thirty Sixth Conference on Learning Theory , pages =. 2023 , editor =

    2023

  10. [18]

    The Many Faces of Optimal Weak-to-Strong Learning , booktitle =

    H. The Many Faces of Optimal Weak-to-Strong Learning , booktitle =. 2024 , publisher =

    2024

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.