PAC Learning & VC Dimension
When can you learn from finitely many examples?
How many examples does it take to learn? Valiant's PAC model made the question precise, and Vapnik and Chervonenkis had already found the quantity that answers it. A class can be learned from finitely many examples exactly when its VC dimension is finite, and that dimension, not the number of parameters, sets the sample size.
What you’ll learn
- Define realizable and agnostic PAC learnability, and derive the finite-class sample complexity .
- Compute VC dimensions, and prove the Sauer–Shelah lemma .
- State the fundamental theorem of statistical learning with its rates, and prove the upper bound by symmetrization, Rademacher complexity and Massart's lemma.
- Explain margin bounds and the lower-bound constructions, and survey what is still open beyond binary classification.
The PAC model, precisely
"Probably" is the , "approximately correct" the . The guarantee is distribution-free: one sample size must work for every , including adversarial ones, which is why the resulting bounds are worst-case. The learner may output a hypothesis outside (improper learning); for sample complexity that freedom matters only by constant factors, but it can change computational complexity drastically.
Call bad if . A fixed bad agrees with the target on one random example with probability below , hence on all independent examples with probability below :
ERM returns a hypothesis with zero training error (the target has none), so it can fail only if some bad hypothesis is consistent. A union bound over at most bad hypotheses:
Set the right side equal to and solve for .
The agnostic finite-class bound of Probability Essentials (Hoeffding plus the union bound) needs about examples: noise costs a factor . In the realizable case one counterexample refutes a bad hypothesis; with noise, error rates must be estimated to precision , which takes order samples.
Conjunctions of literals over Boolean variables (each variable appears positively, negated or not at all, so ). How many examples guarantee error at most with probability at least in the realizable case?
Show the answer
532 examples
and , so . About 3.5 billion hypotheses cost only 22 nats. Valiant's elimination algorithm (start with all literals; delete each literal that a positive example falsifies) finds a consistent conjunction in time , so conjunctions are efficiently PAC learnable.
Shattering, VC dimension and Sauer–Shelah
| Class | VC dimension | Why |
|---|---|---|
| Thresholds on | 1 | two points can never be labeled |
| Intervals on | 2 | three points can never be labeled |
| Axis-aligned rectangles in | 4 | a diamond of four points is shattered; among any five, a rectangle around the leftmost, rightmost, top and bottom points contains the fifth |
| Half-spaces in | affinely independent points are shattered; by Radon's theorem any points split into two groups with intersecting convex hulls | |
| on | one parameter, yet the points are shattered by a suitable | |
| ReLU networks with weights in layers | between and | Bartlett, Harvey, Liaw & Mehrabian (2019) |
Prove a stronger claim: for every finite , is at most the number of subsets of that shatters. No set larger than is shattered, so that number is at most . For the claim is immediate: the empty set is always shattered, and is shattered exactly when both labels occur.
For , set and classify the labelings of : holds those that extend to a labeling in in at least one way, those that extend in both ways ( and ). Then
By induction, is at most the number of shattered subsets of that avoid . For , let contain the hypotheses that have a partner in agreeing on and disagreeing at . Then , and if shatters , the partners supply both labels of , so shatters :
Adding the two bounds counts every shattered subset of once, which proves the claim. For the closed form, with :
Think first Of the labelings of 100 points in general position in the plane, how many can half-planes realize?
Exactly by Cover's theorem; Sauer–Shelah with gives the cruder . Either way it is polynomial, , against . That collapse from exponential to polynomial is what makes learning from finite samples possible.
The fundamental theorem
The upper bounds rest on Rademacher complexity. For a class of functions and a sample , , with independent uniform signs , and . It measures how well the class can correlate with pure noise on samples of size . The key fact (Koltchinskii & Panchenko; Bartlett & Mendelson, 2002) is that with probability at least , simultaneously for all , .
Let . Replacing one changes by at most , so McDiarmid's inequality (Probability Essentials) concentrates it around its mean:
Symmetrization. Introduce an independent ghost sample , write , and move the supremum inside the expectation over :
Swapping with leaves the joint law unchanged, so each difference can be multiplied by a random sign for free. Splitting the supremum gives twice the Rademacher complexity:
Finitely many patterns. With labels and hypotheses in , the 0–1 loss is , so the loss class has half the complexity of . On a sample, realizes at most sign vectors of norm . Massart's lemma, , and Sauer–Shelah give
Combine: with probability at least , simultaneously for all , the bound below holds; one more Hoeffding bound for the best turns it into an excess-risk bound for ERM. Chaining (Dudley's entropy integral with Haussler's packing bound) removes the and gives the rate.
Lower bounds. If , then for every there is a shattered set of size , and the PAC form of the no-free-lunch theorem (proved in The Scaling Era & the Bitter Lesson) applies on it: some distribution has a perfect hypothesis in , yet the learner's error is at least with probability at least . For finite , a distribution that puts most of its mass on one point of a shattered set and spreads mass of order over the others forces realizable examples (Ehrenfeucht, Haussler, Kearns & Valiant, 1989); in the agnostic case, telling slightly biased coins apart on the shattered points forces .
Think first A class has VC dimension , and you have examples. With , how large is the uniform deviation ? Estimate it before revealing.
and , so the first term is ; the second is . The total, about , promises test error within 14 points of training error: valid for every distribution, but loose. Worst-case bounds pay for distributions you will never meet; data-dependent bounds (next step) are often much tighter.
Beyond VC: margins, compression and open problems
Rademacher complexity can be small when the VC dimension is huge. For linear functions on inputs with , Cauchy–Schwarz and Jensen give , independent of the dimension. Composing with the ramp loss, which is -Lipschitz, and Talagrand's contraction lemma yield the margin bound: with probability at least , for all such ,
where is the fraction of training points with margin (a union over a grid of values adds a term). This is why maximum-margin classifiers in enormous or infinite feature spaces can generalize (Kernels & Support Vector Machines).
Other routes to generalization:
- Sample compression (Littlestone & Warmuth, 1986): if every labeled sample can be reconstructed from of its points, the reconstructed hypothesis has error of order in the realizable case, with no reference to VC dimension. Moran & Yehudayoff (2016) proved that every class of VC dimension has a compression scheme of size .
- Online learning: the Littlestone dimension characterizes learnability with a bounded number of mistakes against an adversary (Littlestone, 1988). Thresholds on have VC dimension 1 but infinite Littlestone dimension. Remarkably, PAC learnability under differential privacy is equivalent to finite Littlestone dimension (Alon, Livni, Malliaris & Moran, 2019; Bun, Livni & Moran, 2020).
- Multiclass: with infinitely many labels the Natarajan dimension no longer characterizes learnability; the DS dimension does (Brukhim, Carmon, Dinur, Moran & Yehudayoff, 2022), and there ERM can fail even for learnable classes.
A linear classifier works in a feature space of dimension , trained on examples, all with , and it separates them with margin at . Which bound can be non-vacuous?
- Neither: with more dimensions than examples, nothing can be said
- The VC bound, since half-spaces have VC dimension only
- Both, by the same argument
- The margin bound: its complexity term does not depend on the dimension
Show the answer
D. The margin bound: its complexity term does not depend on the dimension
The VC term is of order with , which is vacuous. The margin bound replaces the dimension by , playing the role of an effective dimension: , plus a small confidence term.
Key takeaways
- PAC learning asks for error at most (or excess risk at most in the agnostic model) with probability at least , for every distribution. Finite classes need realizable and order agnostic examples.
- The VC dimension is the size of the largest shattered set, a combinatorial quantity rather than a parameter count: half-spaces in have , the one-parameter sine class has .
- Sauer–Shelah: , so beyond a class realizes only polynomially many labelings.
- Fundamental theorem: finite VC dimension, uniform convergence, PAC learnability and the success of ERM are equivalent, with sample complexity agnostic and realizable.
- Scale-sensitive complexity (Rademacher, margins) can be dimension-free; compression schemes, multiclass and online learnability, and computational hardness are where the theory is still moving.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
What is the VC dimension of axis-aligned rectangles in the plane (points inside are labeled 1)?
- 2
- 3
- 4
- 5
Show the answer
C. 4
Four points in a diamond can be shattered: for any subset, the smallest rectangle around it excludes the others. Among any five points, a rectangle that contains the leftmost, rightmost, highest and lowest (at most four points) contains the fifth, so the labeling "fifth point 0, others 1" is impossible.
A class has VC dimension 3. By the Sauer–Shelah lemma, at most how many of the labelings of 10 points can it realize?
- 1024
- 176
- 120
- 30
Show the answer
B. 176
. Past , the count grows only polynomially, here at most like .
Is the one-parameter class PAC learnable?
- Yes: one parameter means VC dimension 1
- Yes, but only in the realizable case
- Only if the inputs are bounded
- No: it shatters arbitrarily large sets, so its VC dimension is infinite
Show the answer
D. No: it shatters arbitrarily large sets, so its VC dimension is infinite
The points , , can be given any labels by a suitable , for every . By the fundamental theorem, infinite VC dimension rules out PAC learning in either model, whatever the algorithm.
For a class of fixed VC dimension (with ), how does the agnostic sample complexity change when you halve , compared with the realizable one?
- Agnostic: about ; realizable: about
- Both about
- Both about
- Agnostic: about ; realizable: about
Show the answer
A. Agnostic: about ; realizable: about
and . Noise forces you to estimate error rates, at the price of estimation; without noise, a single counterexample kills a bad hypothesis.
Further reading
- L. G. Valiant, "A theory of the learnable," Communications of the ACM 27(11), 1134–1142 (1984).
- V. N. Vapnik & A. Ya. Chervonenkis, "On the uniform convergence of relative frequencies of events to their probabilities," Theory of Probability and Its Applications 16(2), 264–280 (1971).
- A. Blumer, A. Ehrenfeucht, D. Haussler & M. K. Warmuth, "Learnability and the Vapnik–Chervonenkis dimension," Journal of the ACM 36(4), 929–965 (1989).
- P. L. Bartlett & S. Mendelson, "Rademacher and Gaussian complexities: risk bounds and structural results," Journal of Machine Learning Research 3, 463–482 (2002).
- S. Shalev-Shwartz & S. Ben-David, Understanding Machine Learning: From Theory to Algorithms (Cambridge University Press, 2014), chapters 2–6 and 26.