Majority-of-Three is Optimal

Technical Summary: Majority-of-Three is Optimal

Problem Statement
The paper addresses the central problem of determining the optimal sample complexity for PAC learning in the realizable setting. While the existence of optimal learners was established by Hanneke [Han16] (building on Simon [Sim15]), the resulting algorithms and their probabilistic analyses are complex. A specific, elementary candidate for an optimal learner is the "majority-of-three" rule: splitting a training sample into three independent blocks, training a consistent classifier on each block, and outputting the majority vote. Previous work [AAHLZ24] proved this rule achieves an optimal bound in expectation and a near-optimal PAC bound (up to a doubly logarithmic factor, $\log \log(\min\{n/d, 1/\delta\})$). The authors of [AAHLZ24] conjectured that the majority-of-three rule achieves the optimal PAC bound without these extra factors. This paper provides a proof of that conjecture.

Methodology
The proof establishes a high-probability upper bound on the error of the majority-of-three classifier, $Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)$, where each $\hat{f}_i$ is a consistent classifier trained on an independent block $S_i$ of size $m = n/3$.

1. Reduction to Overlap Moments:
   The error of the majority vote occurs only when at least two of the three classifiers misclassify a point $x$. Letting $E_i = \{x : \hat{f}_i(x) \neq f^\star(x)\}$ be the error set of the $i$-th classifier, the total error is bounded by the sum of pairwise intersections:
   $$\text{err}_P(Maj) \leq P(E_1 \cap E_2) + P(E_2 \cap E_3) + P(E_1 \cap E_3).$$
   The proof focuses on bounding the $L_q$ moments of these intersection probabilities, specifically $\|P(E_1 \cap E_2)\|_{L_q}$.

2. Key Technical Tool: Proposition 2.2:
   The core of the argument is Proposition 2.2, which provides a moment bound for the overlap of error sets from two independent samples $S$ and $T$ of size $m$. For a VC class $\mathcal{C}$ with dimension $d$ and a deterministic consistent selector $A$ (where $A(S) \cap S = \emptyset$), the proposition states:
   $$\|P(A(S) \cap A(T))\|_{L_q} \leq 62400 \frac{d + q}{m}.$$
   This result is analogous to Simon's [Sim15] overlap estimate but applies to independent samples rather than nested ones. The independence is crucial for avoiding the doubly logarithmic factors present in previous analyses of nested structures.

3. Recursive Decomposition and Conditional Probabilities:
   To prove Proposition 2.2, the authors analyze the $q$-th moment of the overlap by introducing $q$ independent test points $X = (X_1, \dots, X_q)$. The moment is rewritten as $\mathbb{E}_X [p_q(X)^2]$, where $p_q(X) = P(X \subseteq A(S))$.
   Using a chain-rule decomposition, $p_q(X)$ is expressed as a product of conditional inclusion probabilities:
   $$p_q(X) = \prod_{\ell=1}^q \alpha_{X_{<\ell}}(X_\ell), \quad \text{where } \alpha_{z}(x) = P(x \in A(S) \mid z \subseteq A(S)).$$
   The proof relies on Lemma 3.1, a tail bound for these conditional probabilities. It shows that for a conditioning event $E_z$ with probability $p_z$, the probability that the conditional inclusion probability $\alpha_z(X)$ exceeds a threshold $a$ is bounded by:
   $$P(\alpha_z(X) > a) \leq \frac{160}{am} \left( d \log \frac{e}{a} + \log \frac{e}{p_z} \right).$$
   This bound controls the "rarity" of the conditioning event without inflating the VC dimension term.

4. Recursive Argument:
   The authors define a weighted functional $M_k$ involving the squared conditional probabilities and a logarithmic term. They establish a recursion $M_k \leq \frac{960}{m} M_{k-1}$. Iterating this recursion from $k=1$ to $q$ yields the desired bound for the $q$-th moment, which is then converted to a high-probability bound using Markov's inequality with $q = \lceil \log(1/\delta) \rceil$.

Key Contributions and Results

• Optimality Proof: The paper proves that the majority-of-three learner achieves the optimal sample complexity in the realizable PAC setting. Specifically, for any distribution $P$, target $f^\star$, and confidence $\delta$:
  $$P\left( \text{err}_P(Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)) \leq 107 \frac{d + \log(1/\delta)}{n} \right) \geq 1 - \delta.$$
  This matches the classic lower bound [EHKV89] up to a universal constant.
• Simplification of Analysis: The proof simplifies the algorithmic structure and probabilistic analysis of previous optimal learners (such as Hanneke's [Han16] and Larsen's bagging analysis [Lar23]). It removes the need for complex nested sample structures and the resulting doubly logarithmic factors.
• Independence over Nesting: The work demonstrates that using independent blocks (as opposed to nested samples) allows for a cleaner analysis that avoids the $\log \log$ factors previously thought necessary for simple voting schemes.

Significance and Claims
The authors claim that this result resolves the conjecture from [AAHLZ24] regarding the optimality of the majority-of-three rule. The paper positions this as a significant simplification in the theory of PAC learning, providing the "simplest voting scheme" that is provably optimal. The proof is described as short and self-contained, relying on a novel recursive decomposition of conditional inclusion probabilities rather than the more intricate constructions of prior optimal learners.

The paper also includes an appendix detailing the use of Large Language Models (LLMs) to simplify the proof. The authors note that the initial proof was longer and derived by the first author, but LLM assistance was used to explore alternative arguments, leading to the shorter recursive form presented in the final manuscript. The mathematical claims were verified and written by the authors.