From ERM to Guarantees: The PAC Framework

The gap we are trying to bound

Statistical learning theory begins with one uncomfortable fact: minimizing error on data you have seen says almost nothing, on its own, about error on data you have not. We call the first quantity the empirical risk and the second the true (or population) risk, and the whole subject is the study of the gap between them. When you run ERM you are betting that small empirical risk transfers to small true risk — a bet that is sometimes safe, sometimes ruinous, and the theory tells you which.

R(h)=\mathbb{E}_{(x,y)\sim\mathcal{D}}\big[\ell(h(x),y)\big],\qquad \hat{R}_S(h)=\frac{1}{m}\sum_{i=1}^{m}\ell(h(x_i),y_i)

True risk is the expected loss over the distribution; empirical risk is its average over the sample — the gap between them is what we must bound.

The reason the gap is not automatic is selection. If you fixed a single predictor before seeing the data, the law of large numbers would already promise that its training error converges to its true error. But ERM does not fix a predictor in advance — it chooses the one that looks best on this particular sample, and that choice is exactly the move that can make the training error a flattering lie. Controlling generalization means controlling the error of a hypothesis selected by looking at the data.

The PAC model, stated carefully

The PAC (probably approximately correct) framework, due to Valiant, makes the bet precise. Fix a hypothesis class H and a loss. We say an algorithm learns H if, for every data distribution, given enough samples it returns a hypothesis whose true risk is within ε of the best achievable — approximately correct — with probability at least 1 − δ over the random sample — probably. Two knobs, ε for accuracy and δ for confidence, and a promise that the required sample size grows in a controlled way as you tighten either one.

\Pr_{S\sim\mathcal{D}^m}\!\Big[\,R\big(A(S)\big)\le \min_{h\in H} R(h)+\varepsilon\,\Big]\ge 1-\delta

The agnostic PAC condition: with probability at least 1−δ, the learner's risk is within ε of the best hypothesis in the class.

The early literature split on an assumption. In the realizable setting some hypothesis in H achieves zero true risk — the target is literally inside your class. Real problems rarely cooperate, so the modern default is agnostic learning: make no assumption about the truth, and ask only to compete with the best hypothesis in H. The benchmark shifts from 'zero error' to 'the minimum error H can possibly achieve', and your guarantee is on the excess risk above that floor.

State H, the loss, and whether you assume realizable or agnostic.
Fix a target accuracy ε and confidence 1 − δ.
Ask: how many samples m make ERM's excess risk ≤ ε with probability ≥ 1 − δ?
That smallest m, as a function of ε, δ, and H, is the sample complexity.

One hypothesis, then finitely many

Start with a single fixed hypothesis h. Its empirical risk is an average of independent bounded random variables, so a concentration inequality — Hoeffding's, in the simplest case — says the average is unlikely to stray far from its mean. Concretely, the probability that empirical and true risk differ by more than ε decays like exp(−2mε²). One hypothesis is easy; the law of large numbers does the work.

Now let H be finite with |H| hypotheses. ERM might output any of them, so we must control them all at once. A union bound multiplies the failure probability by |H|: the chance that some hypothesis has a large risk gap is at most |H|·exp(−2mε²). Set that equal to δ and solve, and you get the first real sample complexity bound — m on the order of (1/ε²)(log|H| + log(1/δ)). The capacity of H enters only through log|H|; richness is paid for in logarithms.

\Pr\!\Big[\,\sup_{h\in H}\big|R(h)-\hat{R}_S(h)\big|>\varepsilon\,\Big]\le 2\,|H|\,e^{-2m\varepsilon^2}

Hoeffding's bound for each hypothesis, multiplied by |H| via the union bound, controls the worst-case deviation over a finite class.

# finite-class agnostic bound (sketch)
#   with prob >= 1 - delta, for all h in H:
#   risk(h)  <=  emp_risk(h)  +  sqrt( ( log|H| + log(1/delta) ) / (2 m) )
m_needed = ceil( (log(len(H)) + log(1/delta)) / (2 * eps**2) )

The uniform deviation shrinks like 1/sqrt(m); log|H| is the price of choosing.

Uniform convergence and what the bound says

The pattern above is the central tool of the whole field: uniform convergence. We do not bound the gap for one hypothesis but for all of them simultaneously, so that whichever one ERM happens to pick is automatically covered. Once uniform convergence holds at level ε, the ERM output's true risk is within 2ε of the best in H — accuracy follows from controlling the supremum of the empirical process indexed by H.

Read the sample-complexity expression as an engineering spec. The 1/ε² says halving the tolerated error quadruples the data — accuracy is expensive. The log(1/δ) says confidence is cheap — going from 90% to 99.9% confidence multiplies the data by a small constant. And log|H| is your first capacity measure: it works for finite classes but explodes for the infinite classes (linear separators, neural nets) we actually use, which is exactly the cliff the next guide is built to cross.

R(h)\le \hat{R}_S(h)+\sqrt{\frac{\log|H|+\log(2/\delta)}{2m}}\quad\text{for all } h\in H

The uniform-convergence guarantee: true risk is at most empirical risk plus a term shrinking like 1/√m, with log|H| the price of choosing.