Majority-of-Three is Optimal

Generally in learning theory, we are concerned with a notion of statistical optimality: given $n$ samples, how little error can a learner incur on the true distribution? Generally, we know some lower bound, and the main challenge is designing an algorithm that matches that lower bound. In the theory of PAC (probably approximately correct) learning, the first algorithm to achieve the optimal statistical rate was given in 2016 [Han16]. However, the algorithm was based around a very sophisticated splitting of the dataset and carefully designed overlaps, and its analysis was similarly quite involved. Thus, a new line of work emerged with a different goal: find the simplest optimal PAC learner. In particular, one such proposed algorithm was majority-of-three, proposed by [AHL+24] and proven to be optimal in expectation (i.e. on average it achieves the optimal rate). It was not, however, proven optimal with high probability¹ — an extra $\log\log$ factor remained in their analysis, and it was conjectured that it could be removed to prove that majority-of-three is indeed optimal with high probability. In this short note, we give a better analysis and prove that the algorithm is an optimal PAC learner.

Setup#

Supervised Learning, Hypothesis Classes, and VC Dimension#

Generally, the supervised learning setup is as follows: some true function $f^\star$ exists, we see it applied to some finite set of samples drawn i.i.d. from some unknown distribution $P$, and we must then predict the rule. Let's introduce some notation: we see $(\mathcal X, \mathcal Y)$, where $\mathcal X$ is our training set, and $\mathcal Y = f^\star(\mathcal X)$ are the labels. Let's assume all the labels are binary, i.e. either $-1$ or $+1$ (one can also use $0$ and $1$, or really anything, it doesn't matter). Further, let us assume that we know that the true function $f^\star$ is a member of some class of functions $\mathcal F$. Immediately, this is helpful; our learner need not search over all functions, only over $\mathcal F$.

We call $\mathcal F$ our hypothesis class. Knowing that we need only search over $\mathcal F$ is helpful, but intuitively, if $\mathcal F$ is a very complex function class, our learning problem is much harder. In order to quantify this, we use the VC dimension. The VC dimension $d$ is just the largest number of samples that $\mathcal F$ can label in every possible way. It might help to think of this as a game: assume you're playing against some adversary who wants to make the learning problem as hard as possible for you. Since the adversary knows that you both know the search space is $\mathcal F$, the adversary can choose points on which every possible labeling is produced by some $f$ in $\mathcal F$, so no labeling can be ruled out in advance and you get no usable information. Knowing the VC dimension of $\mathcal F$ is $d$ then just says that for any $d+1$ points, there is at least one labeling that no $f$ in $\mathcal F$ can produce.

A good example here is the hypothesis class of thresholds: functions $f_a(x)$ that predict $+1$ if $x \geq a$ and $-1$ if $x < a$. It is clear that the VC dimension of this class is 1: every possible labeling of a single point is realizable by just choosing a threshold above or below $x$, and we can construct a labeling of 2 points that is not realizable. Indeed, for $x_1, x_2$ such that $x_1 < x_2$, set the label of $x_1$ to $+1$ and the label of $x_2$ to $-1$ — no threshold function can realize this labeling (if you're not convinced, try drawing it out!).

PAC Learning#

Recall that we see $n$ samples drawn i.i.d. from some probability distribution $P$, along with their labels. So, from that, we want to do well on the entire distribution $P$. In PAC learning, we basically want that most of the time (the probably) we are pretty close to the right answer (the approximately correct). To make this more formal, we want that for some $\varepsilon$ and $\delta$, we are within error $\varepsilon$ at least $1-\delta$ of the time. More formally, define $\operatorname{err}(f) \doteq P(f(x) \neq f^\star(x))$. Then, PAC learning wants $$\Pr[\operatorname{err}(f) > \varepsilon] \leq \delta.$$

We can attain this trivially by setting $\varepsilon=1$, so assume $n$ and $\delta$ are fixed. Now we ask how small $\varepsilon$ can be. For realizable PAC learning (the setting we've been working in where we know the answer is in our family $\mathcal F$),² the answer is $$\varepsilon = \Theta\left( \frac{d + \log(1/\delta)}{n} \right),$$ where the $\Theta$ notation indicates scaling up to a constant (this is the matching upper and lower bounds thing we discussed earlier). Reading the above relation, we can think of the $d/n$ term as what we pay for the expressiveness of the class (a more complex class is harder to get right) and the $\log (1/\delta) / n$ term as the price of guaranteeing that it holds over unlucky samples. Our focus will be on the second term.

Finally, let us make a remark on in-expectation vs. high-probability bounds. Bounding error in expectation is a much simpler ask: we need only show that on average $\operatorname{err}(f) < \varepsilon$. On the other hand, showing a high-probability bound requires showing that the tails decay sufficiently fast; we might be optimal in expectation, but have fat tails.

Empirical Risk Minimization#

By this point, all this machinery probably feels overly complex; surely the right answer is simply to minimize the error on our training set. Since we're in the realizable regime, there is at least one rule that gets every training point right, so just output one of those rules! This is empirical risk minimization (ERM), simply understood as "output any rule consistent with the data."

Note the use of the word "any." ERM is a family of algorithms since when several rules are consistent, nothing tells us which to pick. Formally, we just fix some deterministic tie-breaking rule upfront and assume nothing else about it.³ Because of this, one can actually show that some consistent rules are suboptimal and miss the optimal rate, hence the interest (and difficulty) in developing optimal algorithms.

Let's also make one observation here, for use later. Every statement we've made here has been about symmetric differences with the target, so we can relabel so that the target is the empty set (this just means we can relabel so that $f^\star$ is the function which assigns $0$ to every sample).⁴ Once we've done this, a consistent hypothesis (meaning a hypothesis that matches the training data we've seen) is just a set containing none of the training points, and its error is just the probability mass that the distribution $P$ assigns to it. So going forward, ERM gives us a set avoiding the sample, and we want to prove that that set is small.

The Majority-of-Three Rule#

The majority-of-three algorithm is about as simple as an algorithm could possibly be:

1. Split the sample $S$ of size $n$ into three independent blocks $S^{(1)}, S^{(2)}, S^{(3)}$ of size $m = \lfloor n/3 \rfloor$.
2. Run ERM on each block to get three hypotheses $h_1, h_2, h_3$.
3. The final prediction is the majority vote: $\text{Maj}(h_1(x), h_2(x), h_3(x))$.⁵

The open problem was whether this algorithm achieves the theoretically optimal rate of $O\left(\frac{d + \log(1/\delta)}{n}\right)$, or whether it incurs the extra $\log\log\left(\min\{n/d, 1/\delta\}\right)$ left by previous analysis.

[NOTE] From here it gets a bit more technical — some background in probability will likely be useful.

Reducing to an Overlap Problem#

With the target relabeled to the empty set, each $h_a$ is an error region, so the majority vote is wrong at $x$ exactly when at least two of the three sets contain $x$. Writing this in set notation: $$\mathcal{E}_{\text{Maj}} = (h_1 \cap h_2) \cup (h_2 \cap h_3) \cup (h_3 \cap h_1),$$ and by the union bound the error is at most $P(h_1 \cap h_2) + P(h_2 \cap h_3) + P(h_3 \cap h_1)$. Since the blocks are independent, each of those three terms has the same law and we've reduced our problem into bounding the overlaps of two ERM outputs.

Remember, the whole point of this is to get high-probability bounds, and the standard way to get these is through the method of moments.⁶ Write $Y \doteq P(A(S) \cap A(T))$ for the overlap of the ERM outputs on two independent samples and study $$R_q \doteq \mathbb{E}_{S,T}\bigl[Y^q\bigr].$$ Raising the overlap to the $q$-th power is the same as asking for $q$ independent test points to all land in the overlap, and a point lands in the overlap exactly when both ERMs contain it. So if we write $X = (x_1, \dots, x_q)$ for an ordered tuple of $q$ test points and $$p_X \doteq \Pr_S\bigl[X \subseteq A(S)\bigr]$$ for the probability that a single ERM output consumes the entire tuple, then independence of $S$ and $T$ factors the two ERMs apart and $$R_q = \mathbb{E}_X\bigl[p_X^2\bigr].$$

So now, all that remains for us to answer is how likely a single ERM is to contain $q$ prescribed points at once.

Ideally, we want a bound of the form $$R_q \le \left(\frac{C(d+q)}{m}\right)^q.$$ Given the above bound, the optimal rate follows immediately. Taking $L^q$ norms and applying Minkowski's inequality to the three-term union bound gives $\|P(\mathcal{E}_{\text{Maj}})\|_q \leq 3R_q^{1/q} \leq 3C(d+q)/m$, and then Markov's inequality on the $q$-th moment converts that into a tail bound decaying like $e^{-q}$. Choosing $q = \lceil \log(1/\delta) \rceil$ forces the tail down to $\delta$, and since $d + q \le 2(d + \log(1/\delta))$, we are done.

A Proof by Partitioning into Dyadic Scales#

We need to control $p_X$; the chance that one ERM contains a whole tuple. The issue is that ERM is a rather finicky process: conditioning on the event that it already contains $x_1$ reweights which samples we are looking at and the conditioned process can behave completely differently.

By the chain rule of conditional probability, $$p_X = \prod_{\ell=1}^q q_{X_{\lt \ell}}(x_\ell),$$ where $q_{X_{\lt \ell}}(x_\ell)$ is the conditional probability that the ERM contains $x_\ell$ given that it already contains all the earlier points of the tuple.

Dyadic Profiles#

The main trick here is to not evaluate the conditional probabilities, but rather to track their scale. For each point $x_\ell$, let $k_\ell$ be the integer with $$2^{-k_\ell-1} \lt q_{X_{\lt \ell}}(x_\ell) \le 2^{-k_\ell},$$ and call the vector $\mathbf{k} = (k_1, \dots, k_q)$ the dyadic profile of the tuple. Every tuple has a dyadic profile, and the profile immediately gives $p_X \le 2^{-\sum_\ell k_\ell}$. The profiles are countable, so we can bound each class of tuples separately and sum at the end.

Within a profile class, the $\varepsilon$-net theorem and Sauer's lemma apply to each level set, and give that the set of points whose conditional inclusion probability sits at level $k$ has mass at most about $$\frac{\bigl(d(k+1) + \log(e/p_{\mathbf{a}})\bigr)2^k}{m},$$ where $p_{\mathbf{a}}$ is the probability of the conditioning event. There are two notable features of the above that drive the proof.

The first is that the level sets balance nicely. A point that is very likely to be included (small $k$) can only live in a very thin slice of the space; a point sitting in a fat slice has to be correspondingly unlikely to be included. Intuitively, the product of "how big is this level set" and "how likely is inclusion at this level" is bounded, so everything is nicely behaved.

The second is a bit more subtle. The VC contribution is $d(k+1)$: it depends on the level, but not on how many points we have already conditioned on. Conditioning on a long prefix does not inflate the effective VC dimension. The only cost we pay for conditioning is the rarity term $\log(e/p_{\mathbf{a}})$ and rarity is something that a profile already knows since a profile that has large $k$'s at earlier levels has small prefix probability. So, we may rewrite the rarity term as a deterministic function of the profile, and the bound stops depending on the particular prefix entirely!

Closing It Out#

Once the one-step bound is independent of the prefix, every level has the same upper bound regardless of the points that came before it, and we can iterate Fubini's theorem up the chain, integrating out the last point, then the one before it, etc. all the way down to the empty prefix. That gives us a bound on the probability of each profile class, and summing the resulting series over all profiles (more or less just a counting exercise and an application of AM-GM) gives $$R_q \le \left(\frac{C(d+q)}{m}\right)^q,$$ as desired. The optimal rate then follows.

A Recursive Proof#

The dyadic profiling argument is neat, but it required a lot of intermediate machinery. It turns out that the entire multiscale decomposition can be collapsed into a single recursion. In particular, if we track the "rarity the conditioning has accumulated so far," we never need the levels at all.

Concretely, instead of partitioning the space, define a weighted functional $M_k$ on prefixes of length $k$, with the rarity penalty built into the weight: $$M_k = \mathbb{E}_{X_{1:k}}\left[ p_k(X_{1:k})^2 \left( 64(d+q) + \log\frac{e}{p_k(X_{1:k})} \right)^{q-k} \right].$$ At first, this looks pretty magical (at least it did to me), but let's get some intuition for this by looking at the endpoints. At $k = q$ the exponent $q-k$ is zero, the penalty disappears, and $M_q$ is exactly our target overlap moment $R_q$. At $k = 0$ the prefix is empty, $p_0 = 1$, and $M_0$ is a deterministic constant, roughly $(64(d+q))^q$. So the functional interpolates between the thing we want to bound and something we already know.

The step from $M_k$ to $M_{k-1}$ integrates out the last point, via a uniform tail bound on the conditional inclusion probability $\alpha_z(X)$. Fixing a prefix $z$, classical VC theory gives $$\Pr(\alpha_z(X) > a) \le \frac{C}{am} \left( d\log\frac{e}{a} + \log\frac{e}{p_z} \right),$$ which is the same $\varepsilon$-net estimate as before, just stated as a tail instead of being applied level by level. Rewriting the expectation over $x_k$ as an integral against this tail and doing a bit of calculus gives the contraction: $$M_k \le \frac{960}{m} M_{k-1}.$$ Note that the $\log(e/p_z)$ generated by the tail bound during integration is exactly absorbed by the penalty already sitting in the functional, and the exponent $q-k$ increasing by one is what "pays" for it.

With the one-step contraction established, the rest more or less writes itself. Iterate $q$ times, from the full tuple down to the empty prefix: $$R_q = M_q \le \left(\frac{960}{m}\right)^q M_0 \le \left(\frac{C(d+q)}{m}\right)^q.$$

An Experiment with LLMs#

The recursive argument above was found (in part) by an LLM. The original proof was worked out by hand, with an LLM used only to check intermediate calculations and look for local simplifications; on reviewing it we experimented further and found that, given a prompt of hints distilled from that proof, the models were able to streamline it considerably. Interestingly, they were not able to prove the conjecture from the problem statement alone.

This is discussed a bit more in Appendix A of the note. My original proof is outlined in Appendix B, and the full version is available here.