How many examples is enough? Valiant turned "learnable" into a number. Feed a learner a finite, realizable hypothesis class and a countable sample; if the sample is at least m = (1/ε)(ln|H| + ln(1/δ)), then any hypothesis consistent with the data is Probably (with prob ≥ 1−δ) Approximately (error ≤ ε) Correct. Down the center the demands go in, the engine computes the sample count, the guarantee comes out. The blue team proves it; the red team tries to break it.
source L. G. Valiant, A Theory of the Learnable (1984), Communications of the ACM 27(11), 1134–1142 — dl.acm.org/doi/10.1145/1968.1972. Rendered, not quoted.
Fix error target ε and confidence δ. Call a hypothesis bad if its true error exceeds ε. A single bad hypothesis survives one random labelled example (stays consistent) with probability < (1−ε); over m independent examples, < (1−ε)m.
Union over at most |H| bad hypotheses: P[some bad survives] ≤ |H|·(1−ε)m. Force that ≤ δ and solve — using (1−ε) ≤ e−ε — for the sample count.
For the current demands, the arithmetic, live:
| quantity | value |
|---|
the-vc-dimension measures how much a class can fit — its capacity. Valiant asks the next question: given that capacity, how many examples are enough to pin the truth down?
For a finite class the answer is ln|H| examples per unit of (1/ε) precision. For an infinite class, |H| is replaced by the VC dimension and the count becomes ~(d/ε)·ln(1/ε). Learnability made quantitative — each sphere is the next one's premise.
The blue team's live check: re-derive the guarantee from scratch — confirm the union bound sits at or below δ at the required m, that m grows in 1/ε, ln|H| and ln(1/δ), and run the threshold-class experiment. If red tampers, this badge is where it shows.
A PAC learner states three things before it ever sees data: the hypothesis class it will search, the accuracy ε it wants, and the confidence δ of failure it will tolerate.
| demand | meaning | direction |
|---|---|---|
| |H| | size of the finite class | ↑ needs more m |
| ε | max tolerated error | ↓ needs more m |
| δ | max failure probability | ↓ needs more m |
Realizable assumption: the target is in H, so a zero-error (consistent) hypothesis always exists to be found. Feed these into the panel below.
Occam bound: m = (1/ε)(ln|H| + ln(1/δ)) — the clean, slightly loose count that Valiant's argument gives directly.
Change any demand — the sample count and the guarantee are computed from the union bound on the spot, never looked up.
What the machine produces, proven: a finite sample count m after which any consistent hypothesis is, with probability ≥ 1−δ, within ε of the truth. The survival bound |H|·(1−ε)m at that m sits at or below δ — that inequality is the PAC guarantee.
The blue team's witness (left) re-derives this live; the red team (right) tries to make the count too small.
It also assumes examples are i.i.d. from a single fixed distribution shared by train and test — no covariate shift, no adversarial ordering. And for an infinite class ln|H| is meaningless: the count only survives by replacing it with VC dimension. PAC is a guarantee about a model of learning, not a promise about any dataset you happen to hold.
"PAC tells you the exact number of examples you need." Cut. It is a sufficient upper bound. The exact threshold uses −ln(1−ε) ≥ ε, so the true count is a little smaller; 1/ε is the honest-but-loose simplification. Toggle EXACT to see both.
"More hypotheses always means hopeless." Cut. Cost grows as ln|H|, not |H| — a billion hypotheses cost only ~21 examples per (1/ε). Capacity, not raw count, is what bites.
"Valiant's paper is the PAC model as taught today." Kept, corrected. His 1984 learner used positive examples and membership queries; the distribution-free two-sided form we run here is the model his paper launched, not verbatim what it stated.
The red team's move: drop the ln|H| term — pretend there is only one hypothesis to rule out — so the claimed sample size shrinks and the true survival bound |H|·(1−ε)m climbs back above δ. The guarantee is void; the witness (window 7) is watching.
Drop ln|H| and the count falls short: for |H| > 1 the survival bound exceeds δ, so a bad hypothesis can slip through consistent. The witness recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.