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.
Majority-of-Three is Optimal
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
citation-role summary
background 1
citation-polarity summary
fields
cs.LG 1years
2026 1verdicts
CONDITIONAL 1roles
background 1polarities
support 1representative citing papers
citing papers explorer
-
An Optimal Agnostic PAC Algorithm
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.