Research map / Learning theory and algorithms / Sample complexity

Majority-of-Three is an Optimal PAC Learner

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of ranking and selection

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies whether optimal realizable PAC learning can be achieved by a simpler majority-of-three combination of ERM calls rather than Hanneke's poly(n) ERM construction.

Problem

Realizable PAC learning has an optimal sample complexity settled by Hanneke (2016), but his algorithm is complex, requiring poly(n) ERM calls on carefully crafted subsets of data; a single ERM call is provably suboptimal.

Approach

Based on the title and abstract, the paper appears to propose a simpler optimal PAC learner that aggregates a constant number of ERMs via majority vote over three hypotheses, in contrast to Hanneke's poly(n) ERM construction. Details beyond the abstract could not be verified.

Surprising findings

• A single ERM call is provably suboptimal for realizable PAC learning, per the abstract.

Experimental setup

Builds on: Hanneke (2016) optimal PAC learner Simon (2015)

Closest papers by meaning

• On Agnostic PAC Learning in the Small Error Regime (NeurIPS 2025 · similarity 0.88)
• Collaborative Learning with Different Labeling Functions (ICML 2024 · similarity 0.86)
• Universal Rates of Empirical Risk Minimization (NeurIPS 2024 · similarity 0.86)
• On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.85)
• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale (NeurIPS 2026 · similarity 0.85)
• Fast Rates for Bandit PAC Multiclass Classification (NeurIPS 2024 · similarity 0.85)