PAC learning

Probably Approximately Correct (PAC) learning is the standard formal model for asking how many training examples a learning algorithm needs. A learner sees $n$ independent, identically distributed labeled examples drawn from an unknown distribution and must output a hypothesis $\hat{h}$ from a fixed class; the model asks how large $n$ must be so that, with probability at least $1-\delta$ over the random sample, $\hat{h}$‘s true error is within some small amount of the best error achievable by any hypothesis in the class.

In the realizable setting, some hypothesis in the class perfectly labels the data (achieves zero error), and the question is how fast the learner’s error shrinks toward zero as $n$ grows. In the more realistic agnostic setting, no hypothesis need be perfect — the best achievable error $L^{\ast }$ may be strictly positive (for example, because the labels themselves are noisy) — and the learner is instead judged by how close its error comes to $L^{\ast }$. The size of the hypothesis class that matters for these bounds is usually not its raw cardinality but its VC dimension $d$, a combinatorial measure of how many different labelings of a finite point set the class can realize; sample-complexity bounds are typically stated in terms of $d$, the sample size $n$, and the confidence parameter $\delta$, often with two additive terms — a “slow” term scaling like $\sqrt{L^{\ast }d/n}$ that dominates when $L^{\ast }$ is large, and a “fast” term scaling like $d/n$ that dominates when $L^{\ast }$ is small or zero.