The Strength of Weak Learnability

In 1984 Leslie Valiant introduced the PAC (Probably Approximately Correct) learning model. A concept class is strongly learnable if an algorithm can, with high probability, find a hypothesis whose error is as small as you want. A concept class is weakly learnable if the algorithm only needs to do slightly better than flipping a coin — say, error at most $1/2 - \gamma$ for some tiny $\gamma > 0$.

Michael Kearns posed the hypothesis boosting problem in 1988: can we always convert a weak learner into a strong one? He showed the naive idea — running the weak learner many times and voting — does not work, because all runs see the same distribution and make correlated errors.

Schapire's breakthrough was proving that the answer is yes, provided you change the distribution between runs — you filter the examples to force the weak learner to focus on the mistakes.

The core idea is elegant. Start with a weak learner $A$ whose error on any distribution is at most $\alpha < 1/2$. Schapire builds a new algorithm $A'$ that calls $A$ three times on three different distributions, then combines the results:

Round 1 — Learn the easy parts. Run $A$ on the original distribution $D_1 = D$, producing hypothesis $h_1$. This hypothesis captures whatever patterns the learner can find, but it still misclassifies an $\alpha$-fraction of the data.

Round 2 — Neutralize the advantage. Construct a new distribution $D_2$ where each example has a 50/50 chance of being one that $h_1$ gets right vs. one it gets wrong. On this distribution $h_1$ is useless — its advantage has been destroyed. Run $A$ on $D_2$ to produce $h_2$, which must learn something new about the hard region.

Round 3 — Focus on disagreement. Construct $D_3$ by keeping only examples where $h_1$ and $h_2$ disagree. These are the uncertain cases — exactly the instances where a tiebreaker is needed. Run $A$ on $D_3$ to produce $h_3$.

The final hypothesis: given an instance $v$, if $h_1(v) = h_2(v)$ then predict the agreed-upon value; otherwise, predict $h_3(v)$. In other words, take the majority vote of $h_1$, $h_2$, and $h_3$.

The key theorem shows that the combined hypothesis $h$ has error at most $g(\alpha) = 3\alpha^2 - 2\alpha^3$. To see why this is powerful, consider concrete numbers: if the weak learner has error $\alpha = 0.4$ (accuracy 60%), one round of boosting gives error $g(0.4) = 3(0.16) - 2(0.064) = 0.352$. That doesn't sound dramatic — but the magic is in the recursion.

Since $g(\alpha) < \alpha$ for all $\alpha \in (0, 1/2)$, the construction can be applied recursively. Each time, the error passes through the function $g$, shrinking rapidly. After $k$ levels of recursion, the error is $g^k(\alpha)$, which converges to zero double-exponentially fast.

Before Schapire's work, the natural idea was: run the weak learner $T$ times independently on the same distribution, obtain hypotheses $h_1, \dots, h_T$, and predict the majority vote. If the errors were independent, majority vote would work beautifully — the Chernoff bound would guarantee exponentially fast convergence.

But errors are not independent. Every run sees the same distribution, so every hypothesis struggles with the same hard region. Running the procedure 1000 times just gives you 1000 copies of roughly the same mistake pattern. The errors are correlated, and majority vote cannot break through.

Schapire's insight: change the distribution between rounds so each hypothesis is forced to learn something new. The filtered distributions $D_2$ and $D_3$ destroy the previous hypotheses' advantages, guaranteeing that each successive learner captures complementary information.

The three-hypothesis construction is just one step. To achieve arbitrary accuracy, Schapire applies it recursively through a procedure called Learn.

Learn takes an error target $\varepsilon$ and works top-down. If $\varepsilon \geq 1/2 - 1/p(n,s)$ (within the weak learner's reach), it calls the weak learner directly. Otherwise, it computes $\alpha = g^{-1}(\varepsilon)$ and calls itself three times with error target $\alpha$, producing three sub-hypotheses. These sub-hypotheses are combined via majority vote, yielding a hypothesis with error at most $g(\alpha) = \varepsilon$.

The depth of this recursion is $O(\log p(n,s) + \log\log(1/\varepsilon))$ — only double-logarithmic in the desired accuracy. This means even pushing error down to $10^{-100}$ requires only a modest number of recursive layers.

Define four quantities over distribution $D$ for instance $v$:

• $w = \Pr[h_2(v) \neq h_1(v) = c(v)]$ — $h_1$ right, $h_2$ wrong
• $x = \Pr[h_1(v) = h_2(v) = c(v)]$ — both right
• $y = \Pr[h_1(v) \neq h_2(v) = c(v)]$ — $h_1$ wrong, $h_2$ right
• $z = \Pr[h_1(v) = h_2(v) \neq c(v)]$ — both wrong

The final hypothesis $h$ errs only when both $h_1$ and $h_2$ are wrong ($z$), or when they disagree and $h_3$ is wrong. The error is bounded by $z + \alpha_3(w + y)$. Using the constraints from $D_2$'s construction and that each $\alpha_i \leq \alpha$, this resolves to at most $3\alpha^2 - 2\alpha^3$.

Beyond the main theorem, Schapire derived surprising complexity bounds for any learnable concept class:

• Hypothesis compression. Any strong learner can be converted into one whose output hypothesis has size polynomial in $\log(1/\varepsilon)$, not $1/\varepsilon$. A sample of size $m$ can be compressed into a rule of size poly-logarithmic in $m$.

• Space efficiency. There exists a learning algorithm for any learnable class needing space only poly-logarithmic in $1/\varepsilon$. This is far less than storing the entire sample.

• On-line learning. For any learnable class, there exists an on-line algorithm whose expected mistakes on the first $m$ trials grow only as a polynomial in $\log m$.

• Hardness results. Any concept class not computable by polynomial-size circuits is unlearnable — the first representation-independent hardness result not relying on cryptographic assumptions.

Schapire's original construction was a theoretical proof-of-concept. The three-round recursive structure was elegant but not practical: each level of recursion tripled the number of weak learner calls, and the filtered distributions required repeatedly scanning through examples to find ones matching specific criteria.

In 1995 Yoav Freund developed a more efficient boosting algorithm. Then in 1997, Freund and Schapire together introduced AdaBoost, which made boosting practical. Instead of three rounds per recursion level, AdaBoost runs $T$ sequential rounds, each time reweighting the entire training set: examples the current ensemble misclassifies get higher weight, forcing the next weak learner to focus on them. The final prediction is a weighted vote of all $T$ hypotheses, where better hypotheses get higher voting weight.

This simple iterative scheme replaced Schapire's recursive filtering with a single loop, and it worked spectacularly in practice. AdaBoost with decision stumps became a standard baseline in machine learning competitions and influenced every subsequent ensemble method — from gradient boosting to XGBoost to random forests.