Majority-of-Three is an Optimal PAC Learner

Finding the optimal sample complexity of realizable PAC learning was a major open problem in learning theory, which was settled by the breakthrough result of Hanneke (2016), building on prior work by Simon (2015). Hanneke's algorithm is quite involved and requires training $\text{poly}(n)$ Empirical Risk Minimizers (ERMs) on carefully crafted subsets of the data. Since using a single ERM call is provably suboptimal, recent work by Aden-Ali (2024) proposed the majority-of-three ERMs as a candidate for the *simplest* optimal PAC learner, and established its optimality in the *in-expectation* regime. Their main open question was whether this algorithm is optimal in the classical *high-probability* regime. In this work, building on their ideas, we answer this question affirmatively.