In 1984, computer scientist Leslie Valiant published a paper that founded modern theoretical computer science’s view of artificial intelligence: “A Theory of the Learnable”. Valiant replaced vague intuitions about learning with a rigorous, distribution-free complexity-theoretic paradigm: Probably Approximately Correct (PAC) Learning. For the first time, learning was defined not by empirical trial-and-error, but by polynomial sample complexity and quantifiable confidence bounds.
1. The Philosophy of PAC: Why “Probably” and “Approximately”?
Valiant recognized two inescapable physical realities that govern any inductive learning process:
- Approximately Correct ($epsilon$): Because training data represents a finite sample of an infinite underlying space, demanding zero error ($R(h) = 0$) on unseen test points is mathematically impossible. A learner can only guarantee that its error is bounded by an arbitrarily small accuracy parameter $epsilon > 0$:
$$R(h) le epsilon$$
- Probably ($1 – delta$): Because the training sample $S sim mathcal{D}^n$ is drawn stochastically, there is always a non-zero probability that the sample is catastrophically unrepresentative (e.g., drawing only identical edge-case points). A learner can only guarantee high accuracy with high probability $1 – delta$, where $delta in (0, 1)$ represents the failure probability:
$$mathbb{P}_{S sim mathcal{D}^n}(R(h_S) le epsilon) ge 1 – delta$$
2. Formal Definition of PAC Learnability
Let $mathcal{C}$ be a concept class of binary functions $c: mathcal{X} to {0, 1}$. The class $mathcal{C}$ is said to be PAC-learnable using hypothesis class $mathcal{H}$ if there exists an algorithm $mathcal{A}$ such that for every target concept $c in mathcal{C}$, for every probability distribution $mathcal{D}$ over $mathcal{X}$, and for all $epsilon, delta in (0, 1)$:
Algorithm $mathcal{A}$ observes sample $S sim mathcal{D}^n$ and outputs hypothesis $h in mathcal{H}$ satisfying:
$$mathbb{P}_{S sim mathcal{D}^n}left[ R(h) = mathbb{P}_{x sim mathcal{D}}(h(x) ne c(x)) le epsilon right] ge 1 – delta$$
Crucially, for learning to be computationally efficient, the required sample size $n = m(epsilon, delta)$ and the runtime of $mathcal{A}$ must scale polynomially in $1/epsilon$, $1/delta$, and the dimensional representation size $d$ of instances.
3. Sample Complexity Bounds for Finite Hypothesis Classes
Suppose the hypothesis class $mathcal{H}$ is finite (containing $|mathcal{H}|$ hypotheses) and the data is realizable—meaning the true target concept $c^*$ belongs to $mathcal{H}$, guaranteeing at least one hypothesis achieves zero training error ($R_{text{emp}}(c^*) = 0$).
Let $h in mathcal{H}$ be an “empirically consistent” hypothesis ($R_{text{emp}}(h) = 0$) that is nevertheless “bad”—possessing true risk $R(h) > epsilon$. The probability that this bad hypothesis correctly classifies a single random point $x_i$ is at most $1 – epsilon$. Because samples are drawn independently, the probability that a bad hypothesis is consistent across all $n$ training points is:
$$mathbb{P}(R_{text{emp}}(h) = 0 mid R(h) > epsilon) le (1 – epsilon)^n le e^{-nepsilon}$$
Applying the Union Bound (Boole’s Inequality) across all hypotheses in $mathcal{H}$:
$$mathbb{P}left(exists h in mathcal{H} : R_{text{emp}}(h) = 0 text{ and } R(h) > epsilonright) le |mathcal{H}| e^{-nepsilon}$$
To guarantee that this catastrophic failure probability is bounded by confidence parameter $delta$:
$$|mathcal{H}| e^{-nepsilon} le delta implies -nepsilon + ln |mathcal{H}| le ln delta implies n ge frac{1}{epsilon} left( ln |mathcal{H}| + ln frac{1}{delta} right)$$
This yields the celebrated Finite PAC Sample Complexity Bound:
$$m(epsilon, delta) ge frac{1}{epsilon} left( ln |mathcal{H}| + ln frac{1}{delta} right)$$
4. Mathematical Formalization of Occam’s Razor
Valiant’s theorem provides the first rigorous mathematical justification for William of Ockham’s 14th-century principle of parsimony: “Entities should not be multiplied beyond necessity”.
Notice that sample complexity scales logarithmically with the cardinality of the hypothesis class: $ln |mathcal{H}|$. In information theory, $ln_2 |mathcal{H}|$ is the exact minimum number of bits required to encode and transmit a hypothesis in $mathcal{H}$. Therefore:
The Occam Bound: If a hypothesis with short description length (low $ln |mathcal{H}|$) achieves zero training error on a polynomial sample of data, it is mathematically guaranteed to generalize well on future unseen data with probability $1 – delta$.
Simplicity is not merely an aesthetic preference of scientists—it is a rigorous, provable constraint of statistical learnability.
