Weak vs Strong Learnability

Imagine someone offers you a rule for predicting whether a stock goes up or down that is right only 51% of the time — barely above a coin flip. It sounds worthless. The surprising theoretical result behind boosting is that it isn't: if you can reliably find many different such barely-better-than-random rules, you can combine them into a classifier that is right almost 100% of the time. The question of whether "slightly better than random" is fundamentally the same as "as accurate as you like" is the weak-vs-strong learnability problem, and the answer — proven in 1990 — is yes, they're equivalent.

The analogy: polling many biased friends

Suppose you want to know whether a coin is fair, and instead of examining it yourself, you can only ask friends who each guess correctly 51% of the time — each one basically useless alone. But if you ask a thousand independent friends and take a majority vote, the noise in their individual 51%-accurate guesses tends to cancel out, and the vote becomes highly reliable, by the same logic that makes polling averages more accurate than any single respondent. Weak learners are like those friends: individually barely useful, but combinable into something strong, provided each one contributes a genuinely different, even slightly informative, perspective.

The formal statement

A concept class is strongly PAC-learnable if there's an algorithm that, given enough samples, outputs a hypothesis with error at most $\epsilon$ and confidence at least $1-\delta$, for any $\epsilon, \delta > 0$ — arbitrarily accurate, arbitrarily reliable. A class is weakly PAC-learnable if there's an algorithm that only guarantees error at most $\frac{1}{2} - \gamma$ for some fixed $\gamma > 0$ — just barely, and fixedly, better than random guessing ($\frac{1}{2}$ error).

$$\text{weak: error} \le \tfrac{1}{2} - \gamma \qquad\qquad \text{strong: error} \le \epsilon \text{ for any } \epsilon > 0$$

Schapire's 1990 theorem: weak learnability implies strong learnability. Any concept class with a weak learner also has a strong learner — you can boost the weak learner's fixed $\gamma$ edge into arbitrarily small error, by training a sequence of weak learners, each one focused on the examples the previous ones got wrong, and combining them by weighted vote.

Worked example 1: boosting three coin-flip-ish stumps

Suppose three decision stumps (one-feature yes/no rules) each classify a dataset of 100 points with 55% accuracy ($\gamma = 0.05$), each making errors on a different, roughly independent, 45-point subset. A majority vote of all three is correct wherever at least 2 of 3 agree correctly. If their errors were fully independent, the chance all three are simultaneously wrong on a given point is about $0.45^3 \approx 0.091$, and the chance exactly one is wrong (majority still right) adds more correct cases on top — pushing combined accuracy well above 55%, often into the 70-80% range with just three weak learners, illustrating how error probability collapses with each added independent vote.

Worked example 2: AdaBoost's core loop, one round by hand

Start with 10 training points, each weighted $w_i = 0.1$. Round 1: fit a weak learner (accuracy 60%, error $\varepsilon_1 = 0.4$). Its vote weight is $\alpha_1 = \frac{1}{2}\ln\frac{1-\varepsilon_1}{\varepsilon_1} = \frac{1}{2}\ln\frac{0.6}{0.4} = \frac{1}{2}\ln 1.5 \approx 0.203$. Points it got wrong get reweighted up by a factor of $e^{\alpha_1} \approx 1.225$, correct points down by $e^{-\alpha_1} \approx 0.816$, then weights are renormalized to sum to 1. Round 2's weak learner is now trained on this reweighted set, forced to focus on round 1's mistakes. After a handful of rounds, the weighted-vote ensemble $\text{sign}\left(\sum_t \alpha_t h_t(x)\right)$ drives training error toward zero — each weak learner only needs $\gamma > 0$, but the vote compounds their edges multiplicatively.

Each boosting round is a small step that corrects the previous ensemble's residual mistakes — watch how repeated small corrective steps converge toward a low-error point, the same mechanism that lets a sequence of $\gamma$-accurate weak learners converge toward near-zero error.

What this means in practice

This equivalence is the theoretical justification for boosting algorithms in practice — AdaBoost, gradient boosting, XGBoost — all of which build strong predictors from ensembles of deliberately weak, cheap-to-fit models like shallow trees. It's why gradient-boosted trees routinely outperform one deep, complex tree: instead of building one strong learner directly, boosting exploits the theorem's constructive proof and builds strength by combination.