The fundamental theorem of statistical learning

Parent: vc-dimension Prereq: learning-theory — H, err, ε, δ, m; and sauer-shelah.

PAC-learnable ⟺ finite VC

A binary hypothesis class H is PAC-learnable if and only if VCdim(H) = d < ∞. Moreover empirical risk minimization (pick the h ∈ H with fewest mistakes on the sample) achieves it, with sample complexity

$$m(\varepsilon,\delta) \;=\; \Theta\!\left(\frac{d + \log(1/\delta)}{\varepsilon^{2}}\right)$$

in the agnostic case (and $\Theta\big((d\log(1/\varepsilon) + \log(1/\delta))/\varepsilon\big)$ in the realizable case).

Two directions.

(⇐) Finite VC ⟹ learnable — uniform convergence

The whole game is to bound the generalization gap $\sup_{h\in H} |\hat{err}(h) - err(h)|$ (where $\hat{err}$ is the error on the sample). If this is ≤ ε for all h at once, then the empirical minimizer is within 2ε of the best in H.

1. Symmetrization (ghost sample). Compare the sample of m points to a second independent "ghost" sample of m; the gap is controlled by how H behaves on the 2m points together.
2. Sauer–Shelah. On those 2m points H realizes at most $\Pi_H(2m) \le (2em/d)^d$ distinct labelings — polynomial, not $2^{2m}$. So although H is infinite, only polynomially many "effective hypotheses" matter here.
3. Union bound + Hoeffding. For each of those finitely many behaviors, Hoeffding bounds the chance its empirical and true errors differ by > ε; a union bound over the (2em/d)ᵈ behaviors gives

Because $\Pi_H(2m)$ is only polynomial in m, the exponential wins: the bound drops below δ once $m = O\big((d + \log(1/\delta))/\varepsilon^2\big)$. Uniform convergence holds → ERM generalizes → learnable. ∎

The one place VC entered was step 2 — finite d is exactly what makes the union bound polynomial instead of vacuous.

(⇒) Infinite VC ⟹ not learnable — no free lunch

Suppose VCdim(H) = ∞. Fix any sample size m; pick a shattered set of size 2m and put the uniform distribution on it. Let the target be a uniformly random labeling of these 2m points (realizable: H shatters them, so some h matches).

A learner sees m labeled points; the other ≥ m are unseen. On an unseen point the label is an independent fair coin that the sample reveals nothing about, so any learner errs there with probability 1/2. Unseen points carry ≥ 1/2 of the mass, so expected true error ≥ 1/4 — for every m. No finite sample drives error below 1/4 → not PAC-learnable. ∎

Reading it

• d is the price tag: samples scale linearly in VCdim(H) — this is where the bias–variance cost comes from.
• d = ∞ is a wall: the sin class (one parameter, infinite VC) cannot be learned, no matter the algorithm or data size — the exact "too flexible to learn" boundary.