Understanding PAC Learning
The framework starts by admitting what cannot be promised. A finite sample can always mislead, so demanding the exactly correct hypothesis with certainty rules out learning entirely. PAC asks instead for a hypothesis whose true error is at most epsilon, and it accepts a failure probability of delta - the sample may be unrepresentative, and no method can prevent that. A class is learnable when the samples needed to meet both targets can be written down as a function of epsilon and delta alone.
For a finite class the argument is a counting one. Hoeffding's inequality bounds the chance that a single fixed hypothesis shows a training error far from its true error; the union bound multiplies that by the number of hypotheses to cover them all at once. Solving for the sample size gives n of order (log|H| + log(1/delta)) / epsilon squared. The logarithm is the whole story: a class of two needs 220 samples for epsilon 0.1 and 95% confidence, and a class of over a million needs 878.
The uniformity is not a technicality. The learner inspects the sample and then chooses, so the hypothesis it returns is itself a function of the data and is not fixed in advance. A bound holding only for a pre-specified hypothesis would say nothing about the one actually produced. Paying log|H| purchases a statement about every member simultaneously, which then necessarily covers the winner.
What goes wrong without it is measurable. On data where every hypothesis has a true error of exactly 0.5, a single fixed hypothesis shows a training error within 0.0002 of the truth, while the best of a thousand shows 0.1149 below it. None of those thousand is better than any other; the gap is entirely the cost of selection, and it is why a training score is not an estimate of future performance.
How to Calculate
P( err(ĥ) ≤ min_h err(h) + ε ) ≥ 1 − δ, n ≥ (ln|H| + ln(2/δ)) / (2ε²)
where
- ε
- the tolerance: how far above the best achievable error is acceptable
- δ
- the failure probability: how often an unrepresentative sample may defeat the guarantee
- ĥ
- the hypothesis the algorithm returns after seeing the sample
- ln|H|
- the price of the search; for infinite classes the VC dimension replaces it
Example of PAC Learning
At epsilon 0.1 and delta 0.05, the samples required are 220 for a class of 2, 300 for 10, 530 for 1,000 and 878 for 1,048,576. Half a million times the hypotheses costs 658 extra samples, because the requirement grows with the number of digits in the class size.
The selection effect the bound protects against, on pure noise where every hypothesis has true error 0.5: the best of 1 is 0.0002 below the truth on its training sample, the best of 10 is 0.0549 below, the best of 100 is 0.0887 below and the best of 1,000 is 0.1149 below.
For infinite classes the same argument runs with the VC dimension in place of log|H|, since Sauer's lemma caps the distinct behaviours on n points by a polynomial - at dimension 2 and n = 20, 211 of them rather than 1,048,576.
Frequently Asked Questions
Are PAC bounds useful in practice?
Rarely as numbers. They are worst-case over every distribution and typically demand far more data than works in reality. Their value is structural: they say which quantity controls generalisation, and that is what transfers.
What does distribution-free mean here?
The bound holds whatever distribution generates the data, which is why it is worst-case and loose. It does require the training and test data to come from the same distribution - a real assumption, and the one that breaks first in practice.
Does PAC learning say anything about how to find the hypothesis?
Not by itself. The sample complexity is about information, not computation; a class can be learnable with modest data while the search for a good hypothesis remains intractable.
The Bottom Line
PAC is worth learning for its shape rather than its numbers. It says generalisation is bought by limiting the search, prices that limit as a logarithm, and makes clear that a training score is a report on a search rather than an estimate of future error.