Simple Algorithm
Artificial Intelligence · Deep Layer · 30 min

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 (ln⁡∣H∣+ln⁡(1/δ))/ε(\ln\abs{\mathcal H}+\ln(1/\delta))/\varepsilon.
  • Compute VC dimensions, and prove the Sauer–Shelah lemma ΠH(m)≤∑i≤d(mi)≤(em/d)d\Pi_{\mathcal H}(m)\le\sum_{i\le d}\binom mi\le(em/d)^d.
  • 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 δ\delta, "approximately correct" the ε\varepsilon. The guarantee is distribution-free: one sample size must work for every D\mathcal D, including adversarial ones, which is why the resulting bounds are worst-case. The learner may output a hypothesis outside H\mathcal H (improper learning); for sample complexity that freedom matters only by constant factors, but it can change computational complexity drastically.

DerivationProof
  1. Pr⁡[R^m(h)=0]<(1−ε)m≤e−εm\Pr\big[\hat R_m(h)=0\big]<(1-\varepsilon)^m\le e^{-\varepsilon m}

    Call hh bad if R(h)>εR(h)>\varepsilon. A fixed bad hh agrees with the target on one random example with probability below 1−ε1-\varepsilon, hence on all mm independent examples with probability below (1−ε)m(1-\varepsilon)^m:

  2. Pr⁡[R(h^)>ε]≤Pr⁡[∃ h bad: R^m(h)=0]≤∣H∣ e−εm\Pr\big[R(\hat h)>\varepsilon\big]\le\Pr\big[\exists\,h\text{ bad}:\ \hat R_m(h)=0\big]\le\abs{\mathcal H}\,e^{-\varepsilon m}

    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 ∣H∣\abs{\mathcal H} bad hypotheses:

  3. m≥ln⁡∣H∣+ln⁡(1/δ)εm\ge\frac{\ln\abs{\mathcal H}+\ln(1/\delta)}{\varepsilon}

    Set the right side equal to δ\delta and solve for mm.

The agnostic finite-class bound of Probability Essentials (Hoeffding plus the union bound) needs about 2ln⁡(2∣H∣/δ)/ε22\ln(2\abs{\mathcal H}/\delta)/\varepsilon^2 examples: noise costs a factor 1/ε1/\varepsilon. In the realizable case one counterexample refutes a bad hypothesis; with noise, error rates must be estimated to precision ε\varepsilon, which takes order 1/ε21/\varepsilon^2 samples.

Predict before you look

Conjunctions of literals over n=20n=20 Boolean variables (each variable appears positively, negated or not at all, so ∣H∣=320\abs{\mathcal H}=3^{20}). How many examples guarantee error at most 0.050.05 with probability at least 0.990.99 in the realizable case?

Show the answer

532 examples

ln⁡∣H∣=20ln⁡3≈21.97\ln\abs{\mathcal H}=20\ln3\approx21.97 and ln⁡(1/δ)=ln⁡100≈4.61\ln(1/\delta)=\ln100\approx4.61, so m≥26.58/0.05≈532m\ge26.58/0.05\approx532. About 3.5 billion hypotheses cost only 22 nats. Valiant's elimination algorithm (start with all 2n2n literals; delete each literal that a positive example falsifies) finds a consistent conjunction in time O(nm)\order{nm}, so conjunctions are efficiently PAC learnable.

Shattering, VC dimension and Sauer–Shelah

ClassVC dimensionWhy
Thresholds x↦1{x≥a}x\mapsto\mathbf 1\{x\ge a\} on R\R1two points x1<x2x_1<x_2 can never be labeled (1,0)(1,0)
Intervals on R\R2three points can never be labeled (1,0,1)(1,0,1)
Axis-aligned rectangles in R2\R^24a diamond of four points is shattered; among any five, a rectangle around the leftmost, rightmost, top and bottom points contains the fifth
Half-spaces 1{w⊤x+b≥0}\mathbf 1\{\mathbf w^\top\mathbf x+b\ge0\} in Rd\R^dd+1d+1affinely independent points are shattered; by Radon's theorem any d+2d+2 points split into two groups with intersecting convex hulls
x↦1{sin⁡(θx)>0}x\mapsto\mathbf 1\{\sin(\theta x)>0\} on R\R∞\inftyone parameter, yet the points xi=10−ix_i=10^{-i} are shattered by a suitable θ\theta
ReLU networks with WW weights in LL layersbetween cWLlog⁡(W/L)cWL\log(W/L) and CWLlog⁡WCWL\log WBartlett, Harvey, Liaw & Mehrabian (2019)
VC dimension often tracks the number of parameters, but it is a combinatorial quantity, not a count: the sine class shows how far apart the two can be.
DerivationProof by induction on m
  1. ∣HC∣ ≤ ∣{B⊆C: H shatters B}∣ ≤ ∑i=0d(mi)\abs{\mathcal H_C}\ \le\ \abs{\{B\subseteq C:\ \mathcal H\text{ shatters }B\}}\ \le\ \sum_{i=0}^d\binom mi

    Prove a stronger claim: for every finite CC, ∣HC∣\abs{\mathcal H_C} is at most the number of subsets of CC that H\mathcal H shatters. No set larger than dd is shattered, so that number is at most ∑i≤d(mi)\sum_{i\le d}\binom mi. For m=1m=1 the claim is immediate: the empty set is always shattered, and {x}\{x\} is shattered exactly when both labels occur.

  2. ∣HC∣=∣Y0∣+∣Y1∣,Y0=HC′\abs{\mathcal H_C}=\abs{Y_0}+\abs{Y_1},\qquad Y_0=\mathcal H_{C'}

    For C={c1,…,cm}C=\{c_1,\dots,c_m\}, set C′=C∖{c1}C'=C\setminus\{c_1\} and classify the labelings of C′C': Y0Y_0 holds those that extend to a labeling in HC\mathcal H_C in at least one way, Y1Y_1 those that extend in both ways (c1↦0c_1\mapsto0 and c1↦1c_1\mapsto1). Then

  3. ∣Y1∣=∣HC′′∣≤∣{B⊆C′: H′ shatters B}∣≤∣{B⊆C: c1∈B, H shatters B}∣\abs{Y_1}=\abs{\mathcal H'_{C'}}\le\abs{\{B\subseteq C':\ \mathcal H'\text{ shatters }B\}}\le\abs{\{B\subseteq C:\ c_1\in B,\ \mathcal H\text{ shatters }B\}}

    By induction, ∣Y0∣\abs{Y_0} is at most the number of shattered subsets of CC that avoid c1c_1. For Y1Y_1, let H′⊆H\mathcal H'\subseteq\mathcal H contain the hypotheses that have a partner in H\mathcal H agreeing on C′C' and disagreeing at c1c_1. Then Y1=HC′′Y_1=\mathcal H'_{C'}, and if H′\mathcal H' shatters B⊆C′B\subseteq C', the partners supply both labels of c1c_1, so H\mathcal H shatters B∪{c1}B\cup\{c_1\}:

  4. ∑i=0d(mi)≤(md)d∑i=0d(mi)(dm)i≤(md)d(1+dm)m≤(emd)d\sum_{i=0}^d\binom mi\le\Big(\frac md\Big)^d\sum_{i=0}^d\binom mi\Big(\frac dm\Big)^i\le\Big(\frac md\Big)^d\Big(1+\frac dm\Big)^m\le\Big(\frac{em}d\Big)^d

    Adding the two bounds counts every shattered subset of CC once, which proves the claim. For the closed form, with m≥dm\ge d:

Think first Of the 2100≈1.3×10302^{100}\approx1.3\times10^{30} labelings of 100 points in general position in the plane, how many can half-planes realize?

Exactly 2∑k=02(99k)=9,9022\sum_{k=0}^{2}\binom{99}k=9{,}902 by Cover's theorem; Sauer–Shelah with d=3d=3 gives the cruder ∑i≤3(100i)=166,751\sum_{i\le3}\binom{100}i=166{,}751. Either way it is polynomial, O(m3)\order{m^3}, against 2m2^m. 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 F\mathcal F of functions z↦f(z)∈[0,1]z\mapsto f(z)\in[0,1] and a sample S=(z1,…,zm)S=(z_1,\dots,z_m), R^S(F)=Eσ[sup⁡f∈F1m∑iσif(zi)]\hat{\mathfrak R}_S(\mathcal F)=\E_{\boldsymbol\sigma}\big[\sup_{f\in\mathcal F}\frac1m\sum_i\sigma_if(z_i)\big], with independent uniform signs σi∈{±1}\sigma_i\in\{\pm1\}, and Rm(F)=ES R^S(F)\mathfrak R_m(\mathcal F)=\E_S\,\hat{\mathfrak R}_S(\mathcal F). It measures how well the class can correlate with pure noise on samples of size mm. The key fact (Koltchinskii & Panchenko; Bartlett & Mendelson, 2002) is that with probability at least 1−δ1-\delta, simultaneously for all f∈Ff\in\mathcal F, Ef≤1m∑if(zi)+2Rm(F)+ln⁡(1/δ)/(2m)\E f\le\frac1m\sum_if(z_i)+2\mathfrak R_m(\mathcal F)+\sqrt{\ln(1/\delta)/(2m)}.

DerivationProof sketch of the upper bound
  1. Φ(S)≤E Φ(S)+ln⁡(1/δ)2mwith probability at least 1−δ\Phi(S)\le\E\,\Phi(S)+\sqrt{\frac{\ln(1/\delta)}{2m}}\qquad\text{with probability at least }1-\delta

    Let Φ(S)=sup⁡f(Ef−E^Sf)\Phi(S)=\sup_f\big(\E f-\hat\E_Sf\big). Replacing one ziz_i changes Φ\Phi by at most 1/m1/m, so McDiarmid's inequality (Probability Essentials) concentrates it around its mean:

  2. E Φ(S)≤ES,S′sup⁡f1m∑i=1m(f(zi′)−f(zi))\E\,\Phi(S)\le\E_{S,S'}\sup_f\frac1m\sum_{i=1}^m\big(f(z_i')-f(z_i)\big)

    Symmetrization. Introduce an independent ghost sample S′S', write Ef=ES′E^S′f\E f=\E_{S'}\hat\E_{S'}f, and move the supremum inside the expectation over S′S':

  3. ES,S′,σsup⁡f1m∑i=1mσi(f(zi′)−f(zi))≤2 Rm(F)\E_{S,S',\boldsymbol\sigma}\sup_f\frac1m\sum_{i=1}^m\sigma_i\big(f(z_i')-f(z_i)\big)\le2\,\mathfrak R_m(\mathcal F)

    Swapping ziz_i with zi′z_i' leaves the joint law unchanged, so each difference can be multiplied by a random sign σi\sigma_i for free. Splitting the supremum gives twice the Rademacher complexity:

  4. 2 Rm(loss class)=Rm(H)≤2ln⁡ΠH(m)m≤2dln⁡(em/d)m2\,\mathfrak R_m(\text{loss class})=\mathfrak R_m(\mathcal H)\le\sqrt{\frac{2\ln\Pi_{\mathcal H}(m)}m}\le\sqrt{\frac{2d\ln(em/d)}m}

    Finitely many patterns. With labels and hypotheses in {±1}\{\pm1\}, the 0–1 loss is (1−yh(x))/2(1-yh(x))/2, so the loss class has half the complexity of H\mathcal H. On a sample, H\mathcal H realizes at most ΠH(m)\Pi_{\mathcal H}(m) sign vectors of norm m\sqrt m. Massart's lemma, Eσmax⁡a∈A1mσ⊤a≤max⁡a∈A∥a∥22ln⁡∣A∣/m\E_{\boldsymbol\sigma}\max_{\mathbf a\in A}\frac1m\boldsymbol\sigma^\top\mathbf a\le\max_{\mathbf a\in A}\norm{\mathbf a}_2\sqrt{2\ln\abs A}/m, and Sauer–Shelah give

  5. R(h)≤R^m(h)+2dln⁡(em/d)m+ln⁡(1/δ)2mR(h)\le\hat R_m(h)+\sqrt{\frac{2d\ln(em/d)}m}+\sqrt{\frac{\ln(1/\delta)}{2m}}

    Combine: with probability at least 1−δ1-\delta, simultaneously for all h∈Hh\in\mathcal H, the bound below holds; one more Hoeffding bound for the best h⋆h^\star turns it into an excess-risk bound for ERM. Chaining (Dudley's entropy integral with Haussler's packing bound) removes the ln⁡(em/d)\ln(em/d) and gives the d/ε2d/\varepsilon^2 rate.

Lower bounds. If VCdim⁡(H)=∞\operatorname{VCdim}(\mathcal H)=\infty, then for every mm there is a shattered set of size 2m2m, 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 H\mathcal H, yet the learner's error is at least 1/81/8 with probability at least 1/71/7. For finite dd, a distribution that puts most of its mass on one point of a shattered set and spreads mass of order ε/d\varepsilon/d over the others forces Ω(d/ε)\Omega(d/\varepsilon) realizable examples (Ehrenfeucht, Haussler, Kearns & Valiant, 1989); in the agnostic case, telling slightly biased coins apart on the shattered points forces Ω(d/ε2)\Omega(d/\varepsilon^2).

Think first A class has VC dimension d=10d=10, and you have m=10,000m=10{,}000 examples. With δ=0.05\delta=0.05, how large is the uniform deviation 2dln⁡(em/d)/m+ln⁡(1/δ)/(2m)\sqrt{2d\ln(em/d)/m}+\sqrt{\ln(1/\delta)/(2m)}? Estimate it before revealing.

em/d=1000e≈2718em/d=1000e\approx2718 and ln⁡2718≈7.91\ln2718\approx7.91, so the first term is 158.2/104≈0.126\sqrt{158.2/10^4}\approx0.126; the second is 3.00/20,000≈0.012\sqrt{3.00/20{,}000}\approx0.012. The total, about 0.140.14, 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 {x↦w⊤x:∥w∥2≤1}\{\mathbf x\mapsto\mathbf w^\top\mathbf x:\norm{\mathbf w}_2\le1\} on inputs with ∥x∥2≤X\norm{\mathbf x}_2\le X, Cauchy–Schwarz and Jensen give R^S≤X/m\hat{\mathfrak R}_S\le X/\sqrt m, independent of the dimension. Composing with the ramp loss, which is (1/γ)(1/\gamma)-Lipschitz, and Talagrand's contraction lemma yield the margin bound: with probability at least 1−δ1-\delta, for all such w\mathbf w,

Pr⁡[y w⊤x≤0] ≤ R^γ(w)+2Xγm+ln⁡(1/δ)2m,\Pr\big[y\,\mathbf w^\top\mathbf x\le0\big]\ \le\ \hat R_\gamma(\mathbf w)+\frac{2X}{\gamma\sqrt m}+\sqrt{\frac{\ln(1/\delta)}{2m}},

where R^γ\hat R_\gamma is the fraction of training points with margin y w⊤x<γy\,\mathbf w^\top\mathbf x<\gamma (a union over a grid of γ\gamma values adds a log⁡log⁡\log\log 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 kk of its points, the reconstructed hypothesis has error of order kln⁡(m/δ)/mk\ln(m/\delta)/m in the realizable case, with no reference to VC dimension. Moran & Yehudayoff (2016) proved that every class of VC dimension dd has a compression scheme of size exp⁡(O(d))\exp(\order{d}).
  • Online learning: the Littlestone dimension characterizes learnability with a bounded number of mistakes against an adversary (Littlestone, 1988). Thresholds on [0,1][0,1] 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.
Check your understanding

A linear classifier works in a feature space of dimension 10610^6, trained on m=104m=10^4 examples, all with ∥x∥≤1\norm{\mathbf x}\le1, and it separates them with margin γ=0.2\gamma=0.2 at ∥w∥=1\norm{\mathbf w}=1. Which bound can be non-vacuous?

  1. Neither: with more dimensions than examples, nothing can be said
  2. The VC bound, since half-spaces have VC dimension only 106+110^6+1
  3. Both, by the same argument
  4. The margin bound: its complexity term 2X/(γm)=0.12X/(\gamma\sqrt m)=0.1 does not depend on the dimension
Show the answer

D. The margin bound: its complexity term 2X/(γm)=0.12X/(\gamma\sqrt m)=0.1 does not depend on the dimension

The VC term is of order dln⁡(m/d)/m\sqrt{d\ln(m/d)/m} with d≈106>md\approx10^6>m, which is vacuous. The margin bound replaces the dimension by (X/γ)2=25(X/\gamma)^2=25, playing the role of an effective dimension: 2⋅1/(0.2⋅100)=0.12\cdot1/(0.2\cdot100)=0.1, plus a small confidence term.

Key takeaways

  • PAC learning asks for error at most ε\varepsilon (or excess risk at most ε\varepsilon in the agnostic model) with probability at least 1−δ1-\delta, for every distribution. Finite classes need (ln⁡∣H∣+ln⁡(1/δ))/ε(\ln\abs{\mathcal H}+\ln(1/\delta))/\varepsilon realizable and order ln⁡(∣H∣/δ)/ε2\ln(\abs{\mathcal H}/\delta)/\varepsilon^2 agnostic examples.
  • The VC dimension is the size of the largest shattered set, a combinatorial quantity rather than a parameter count: half-spaces in Rd\R^d have d+1d+1, the one-parameter sine class has ∞\infty.
  • Sauer–Shelah: ΠH(m)≤∑i≤d(mi)≤(em/d)d\Pi_{\mathcal H}(m)\le\sum_{i\le d}\binom mi\le(em/d)^d, so beyond m=dm=d 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 Θ((d+ln⁡(1/δ))/ε2)\Theta((d+\ln(1/\delta))/\varepsilon^2) agnostic and Θ((d+ln⁡(1/δ))/ε)\Theta((d+\ln(1/\delta))/\varepsilon) 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.

Question 1

What is the VC dimension of axis-aligned rectangles in the plane (points inside are labeled 1)?

  1. 2
  2. 3
  3. 4
  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.

Question 2

A class has VC dimension 3. By the Sauer–Shelah lemma, at most how many of the 210=10242^{10}=1024 labelings of 10 points can it realize?

  1. 1024
  2. 176
  3. 120
  4. 30
Show the answer

B. 176

∑i=03(10i)=1+10+45+120=176\sum_{i=0}^3\binom{10}i=1+10+45+120=176. Past m=dm=d, the count grows only polynomially, here at most like (em/d)d(em/d)^d.

Question 3

Is the one-parameter class {x↦1{sin⁡(θx)>0}:θ∈R}\{x\mapsto\mathbf 1\{\sin(\theta x)>0\}:\theta\in\R\} PAC learnable?

  1. Yes: one parameter means VC dimension 1
  2. Yes, but only in the realizable case
  3. Only if the inputs are bounded
  4. 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 xi=10−ix_i=10^{-i}, i=1,…,mi=1,\dots,m, can be given any labels by a suitable θ\theta, for every mm. By the fundamental theorem, infinite VC dimension rules out PAC learning in either model, whatever the algorithm.

Question 4

For a class of fixed VC dimension dd (with d≫ln⁡(1/δ)d\gg\ln(1/\delta)), how does the agnostic sample complexity change when you halve ε\varepsilon, compared with the realizable one?

  1. Agnostic: about 4×4\times; realizable: about 2×2\times
  2. Both about 2×2\times
  3. Both about 4×4\times
  4. Agnostic: about 2×2\times; realizable: about 4×4\times
Show the answer

A. Agnostic: about 4×4\times; realizable: about 2×2\times

magn≍(d+ln⁡(1/δ))/ε2m^{\mathrm{agn}}\asymp(d+\ln(1/\delta))/\varepsilon^2 and mreal≍(d+ln⁡(1/δ))/εm^{\mathrm{real}}\asymp(d+\ln(1/\delta))/\varepsilon. Noise forces you to estimate error rates, at the 1/ε21/\varepsilon^2 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.