The Fundamental Theorem of Statistical Learning

Intuition Beginner

Two earlier ideas now meet. The first is a promise: every rule on your menu has a measured error close to its true error, so the rule that looks best really is near-best. The second is a number: the largest set of points your menu can tag in every possible yes/no pattern. The surprise of this unit is that these are the same thing. A menu keeps its promise exactly when that number is finite, and it breaks the promise exactly when the number is infinite. There is no in-between case to worry about.

So learnability stops being a vague worry and becomes one yes/no question. Can your family of rules learn from data at all? Look at its number. If the number is finite, the family can learn, picking the empirically best rule works, and you can write down how many examples you need. If the number is infinite, no amount of data is enough and no method rescues you. One dial controls the entire outcome.

The dial also tells you the price. A family with number $d$ needs roughly $d$ examples for each unit of accuracy you demand, give or take. Double the number and you roughly double the data. Ask for a tighter error and the data needed grows in a known way. The whole subject collapses to: find the number, then read off both whether you can learn and how much it costs.

Visual Beginner

Picture a single dial labelled with the family's number. Turn it to any finite setting and four lamps light up together: "can learn", "best-looking rule works", "errors are trustworthy", "data cost is known". Turn it to the infinite setting and all four lamps go dark at once. The lamps are never mixed — they share one switch, and that switch is the number.

        dial = capacity number d
   d finite ............... d infinite
   [on] can learn          [off] cannot learn
   [on] best rule works    [off] best rule fails
   [on] errors trusted     [off] errors useless
   [on] data cost known    [off] no budget works
   four lamps, ONE switch

Family's number	Can it learn?	Does fitting the data work?	Data you need
finite, equal to $d$	yes	yes	about $d$ per unit of accuracy
infinite	no	no	no amount suffices

The picture teaches the lesson: four good things arrive together or not at all, decided by one count.

Worked example Beginner

Take the family of thresholds on a line: each rule picks a cutoff and says yes above it. From earlier work its number is $1$ — it can tag one point in both patterns but cannot tag two points in the order yes-then-no. We use the theorem to read off everything else.

Step 1. Decide learnability. The number is $1$, which is finite, so the theorem says thresholds can learn, the best-looking cutoff on the data is a good choice, and the measured errors are trustworthy. All four good things are on.

Step 2. Read the agnostic data cost. The rule of thumb for the noisy case is about $(d+\text{a confidence amount})$ divided by accuracy squared. With $d=1$, an accuracy of $0.1$, and a modest confidence amount of $5$, the count is about $(1+5)/(0.1\times 0.1)=6/0.01=600$ examples.

Step 3. Read the realizable data cost. When the data are clean (some threshold is exactly right), the cost is cheaper: about $(d\times \text{an accuracy amount}+\text{confidence amount})$ divided by accuracy, not accuracy squared. The single power of accuracy in the denominator is why clean data costs far less.

Step 4. Compare. Going from clean to noisy data swapped one over accuracy for one over accuracy squared, a jump from a few dozen to a few hundred examples at accuracy $0.1$.

What this tells us: once you know the number is $1$, you know thresholds are learnable and you can estimate the data budget for both the clean and the noisy setting without any further theory.

Check your understanding Beginner

Formal definition Intermediate+

The setting is the binary-classification specialisation of 45.07.02 and 45.07.03: a domain $\mathcal{X}$, label set $\{0,1\}$, a hypothesis class $\mathcal{H}\subseteq \{0,1{\}}^{\mathcal{X}}$, the $0$–$1$ loss $\ell (h,(x,y))=1[h(x)\ne y]$, true risk $L_{\mathcal{D}}(h)={\mathrm{Pr}}_{(x,y)\sim \mathcal{D}}[h(x)\ne y]$, empirical risk $L_S(h)=\frac{1}{m}{\sum }_{i=1}^{m}1[h(x_i)\ne y_i]$, and an ERM rule ${\mathrm{ERM}}_{\mathcal{H}}(S)\in \arg {\min }_{h\in \mathcal{H}}{L}_S(h)$.

The four properties the theorem equates are the following.

Definition (uniform-convergence property). $\mathcal{H}$ has the UC property if there is $m_{\mathcal{H}}^{\mathrm{UC}}:(0,1{)}^2\to \mathbb{N}$ with, for all $\epsilon ,\delta$ and all $\mathcal{D}$, ${\mathrm{Pr}}_{S\sim {\mathcal{D}}^m}[{\sup }_{h\in \mathcal{H}}|L_S(h)-L_{\mathcal{D}}(h)|\le \epsilon ]\ge 1-\delta$ whenever $m\ge m_{\mathcal{H}}^{\mathrm{UC}}(\epsilon ,\delta )$ ^{[Shalev-Shwartz Ben-David 2014]}.

Definition (agnostic-PAC learnability; ERM success). $\mathcal{H}$ is agnostically PAC learnable if some learner $A$ and sample bound $m_{\mathcal{H}}$ satisfy ${\mathrm{Pr}}_{S\sim {\mathcal{D}}^m}[L_{\mathcal{D}}(A(S))\le {\min }_{g\in \mathcal{H}}{L}_{\mathcal{D}}(g)+\epsilon ]\ge 1-\delta$ for $m\ge m_{\mathcal{H}}(\epsilon ,\delta )$, all $\epsilon ,\delta ,\mathcal{D}$. ERM success is the same statement with $A={\mathrm{ERM}}_{\mathcal{H}}$. The realizable versions add the assumption that some $h\in \mathcal{H}$ has $L_{\mathcal{D}}(h)=0$ and replace the comparison risk by $0$.

Definition (finite VC dimension). $\mathcal{H}$ has finite VC dimension if $\mathrm{VCdim}(\mathcal{H})<\infty$, where $\mathrm{VCdim}$ is the largest size of a shattered set, with growth function ${\Pi }_{\mathcal{H}}(m)={\max }_{|C|=m}|{\mathcal{H}}_C|$ as in 45.07.03.

Sample-complexity quantities. The sample-complexity function $m_{\mathcal{H}}(\epsilon ,\delta )$ is the least $m$ for which a learner meets the PAC guarantee; $m_{\mathcal{H}}^{\mathrm{UC}}(\epsilon ,\delta )$ is the least $m$ for the UC guarantee. The theorem pins both to $\Theta$ of explicit expressions in $d=\mathrm{VCdim}(\mathcal{H})$.

Counterexamples to common slips Intermediate+

• "The equivalence holds for every loss and label set." It is proved for binary classification with $0$–$1$ loss. For real-valued prediction or general losses, learnability can hold without uniform convergence (some convex stochastic optimization problems are learnable by a stable algorithm yet ERM is not a uniform learner), so the four-way equivalence is special to the binary $0$–$1$ setting.
• "Agnostic and realizable rates are the same." The realizable rate is $\Theta ((d\log (1/\epsilon )+\log (1/\delta ))/\epsilon )$, with a single power of $1/\epsilon$; the agnostic rate is $\Theta ((d+\log (1/\delta ))/{\epsilon }^2)$, with $1/{\epsilon }^2$. Clean data is genuinely cheaper, by a factor of order $1/\epsilon$ up to the log.
• "Finite VC dimension means the class is finite." An infinite class — thresholds, halfspaces, intervals — has finite VC dimension. Finiteness of $d$ is finiteness of capacity, measured by shattering, not of cardinality.

Key theorem with proof Intermediate+

The signature result is the equivalence of learnability with finite VC dimension, together with the quantitative sample complexity. The non-routine direction is that finite VC dimension forces uniform convergence; this is the analytic engine, and the proof is symmetrisation followed by the Sauer-Shelah growth bound.

Theorem (Fundamental theorem of statistical learning). Let $\mathcal{H}$ be a class of functions $\mathcal{X}\to \{0,1\}$ under $0$–$1$ loss. The following are equivalent:

(i) $\mathcal{H}$ has the uniform-convergence property; (ii) any ERM rule is a successful agnostic-PAC learner for $\mathcal{H}$; (iii) $\mathcal{H}$ is agnostically PAC learnable; (iv) any ERM rule is a successful PAC learner for $\mathcal{H}$ in the realizable case; (v) $\mathcal{H}$ is PAC learnable (realizable case); (vi) $\mathrm{VCdim}(\mathcal{H})=d<\infty$.

Moreover, when $d<\infty$ there are absolute constants $C_1,C_2$ with

$$C_1\frac{d+\log (1/\delta )}{{\epsilon }^2}\le m_{\mathcal{H}}(\epsilon ,\delta )\le C_2\frac{d+\log (1/\delta )}{{\epsilon }^2}$$

in the agnostic case, and

$$C_1\frac{d+\log (1/\delta )}{\epsilon }\le m_{\mathcal{H}}(\epsilon ,\delta )\le C_2\frac{d\log (1/\epsilon )+\log (1/\delta )}{\epsilon }$$

in the realizable case. ^{[Shalev-Shwartz Ben-David 2014]}

Proof. The implications $(i)\Rightarrow (ii)\Rightarrow (iii)$ and $(iv)\Rightarrow (v)$ are the content of 45.07.02: uniform convergence makes the three-inequality ERM excess-risk chain valid, and an agnostic learner is in particular a realizable one. The implications $(iii)\Rightarrow (vi)$ and $(v)\Rightarrow (vi)$ are the contrapositive of the No-Free-Lunch corollary of 45.07.02: if $\mathrm{VCdim}(\mathcal{H})=\infty$ then for every $m$ there is a $2m$-point set shattered by $\mathcal{H}$, and feeding it to the No-Free-Lunch construction defeats every learner at every sample size, so $\mathcal{H}$ is neither agnostically nor realizably learnable. It remains to prove $(vi)\Rightarrow (i)$, which closes the cycle, and to establish the rates.

Assume $\mathrm{VCdim}(\mathcal{H})=d<\infty$. Fix $\mathcal{D}$, $\epsilon$, and $m$, and write $\theta (S)={\sup }_{h\in \mathcal{H}}|L_S(h)-L_{\mathcal{D}}(h)|$. The first step replaces the unknown true risk $L_{\mathcal{D}}(h)$ by a second independent ghost sample $S^{\prime }\sim {\mathcal{D}}^m$. A standard symmetrisation inequality (proved in the Full proof set) gives, for $m{\epsilon }^2\ge 2$,

$$\underset{S}{\mathrm{Pr}}[\theta (S)>\epsilon ]\le 2\underset{S,S^{\prime }}{\mathrm{Pr}}[\underset{h\in \mathcal{H}}{\sup }|L_S(h)-L_{S^{\prime }}(h)|>\frac{\epsilon }{2}].$$

The right side involves only the doubled sample $S\cup S^{\prime }$ of $2m$ points. Introduce independent Rademacher signs ${\sigma }_i\in \{\pm 1\}$ that swap the $i$-th points of $S$ and $S^{\prime }$; since $S$ and $S^{\prime }$ are i.i.d., swapping does not change the joint law, so the probability equals its average over $\sigma$. Conditioned on the $2m$ points, the supremum over $h\in \mathcal{H}$ ranges over only $|{\mathcal{H}}_{S\cup S^{\prime }}|\le {\Pi }_{\mathcal{H}}(2m)$ distinct labelings; a union bound over those, with a Hoeffding tail for each fixed labeling under the random signs, yields

$$\underset{S,S^{\prime }}{\mathrm{Pr}}[\underset{h}{\sup }|L_S(h)-L_{S^{\prime }}(h)|>\frac{\epsilon }{2}]\le {\Pi }_{\mathcal{H}}(2m)\cdot 2e^{-m{\epsilon }^2/8}.$$

Combining, ${\mathrm{Pr}}_S[\theta (S)>\epsilon ]\le 4{\Pi }_{\mathcal{H}}(2m)e^{-m{\epsilon }^2/8}$. By the Sauer-Shelah lemma of 45.07.03, ${\Pi }_{\mathcal{H}}(2m)\le (2em/d{)}^d$ for $m\ge d$, so

$$\underset{S}{\mathrm{Pr}}[\theta (S)>\epsilon ]\le 4(2em/d{)}^d{e}^{-m{\epsilon }^2/8}.$$

The polynomial prefactor is of order $e^{d\log m}$ and is overpowered by $e^{-m{\epsilon }^2/8}$ once $m=\Omega ((d\log (1/\epsilon )+\log (1/\delta ))/{\epsilon }^2)$, at which point the right side drops below $\delta$. Hence $\mathcal{H}$ has the UC property, establishing $(vi)\Rightarrow (i)$ and closing the equivalence.

For the agnostic rate, $(i)\Rightarrow (ii)$ converts the UC radius into excess risk at the cost of halving $\epsilon$, giving the upper bound $m_{\mathcal{H}}(\epsilon ,\delta )=O((d+\log (1/\delta ))/{\epsilon }^2)$ after the sharpened chaining of 45.07.03 removes the spurious $\log (1/\epsilon )$; the matching lower bound $\Omega ((d+\log (1/\delta ))/{\epsilon }^2)$ is the No-Free-Lunch construction on a shattered $d$-set. For the realizable rate the $\epsilon$-net theorem replaces the two-sided uniform deviation by a one-sided consistency statement, removing one power of $\epsilon$ and producing $O((d\log (1/\epsilon )+\log (1/\delta ))/\epsilon )$, with the matching $\Omega ((d+\log (1/\delta ))/\epsilon )$ lower bound. $\square$

Bridge. This theorem is the foundational reason the whole PAC/VC apparatus is one subject rather than four: it shows that the analytic uniform-convergence property of 45.07.02, the algorithmic success of ERM, the abstract learnability of the class, and the combinatorial finiteness of the VC dimension of 45.07.03 are a single condition wearing four faces, and the bridge is the symmetrisation step that converts $L_{\mathcal{D}}$ into a ghost sample so that Sauer-Shelah can act. This is exactly the substitution that lets the cardinality $|\mathcal{H}|$ of the finite-class union bound be replaced by the growth function ${\Pi }_{\mathcal{H}}(2m)$, and it generalises the finite-class theorem to every class of finite capacity. It builds toward the distribution-dependent refinement of 45.07.05, where the worst-case growth function is replaced by the Rademacher complexity that adapts to $\mathcal{D}$, and the central insight reappears: learnability is concentration of a supremum over an effective count. Putting these together, the No-Free-Lunch lower bound of 45.07.02 and the Sauer-Shelah upper bound of 45.07.03 meet here as the two halves of one equivalence, and this is exactly the closing of the cycle the chapter was built to reach.

Exercises Intermediate+

Advanced results Master

The equivalence is the hinge between four developments: the precise quantitative bounds with matching lower bounds, the symmetrisation machinery that proves the upper direction, the realizable-case sharpening through $\epsilon$-nets, and the necessity direction that turns the characterisation into an equivalence rather than a one-way sufficiency.

Theorem 1 (quantitative fundamental theorem). For a binary class of VC dimension $d<\infty$ under $0$–$1$ loss there are absolute constants such that the agnostic sample complexity is $m_{\mathcal{H}}(\epsilon ,\delta )=\Theta ((d+\log (1/\delta ))/{\epsilon }^2)$ and the realizable sample complexity is $\Theta ((d\log (1/\epsilon )+\log (1/\delta ))/\epsilon )$, the realizable lower bound being $\Omega ((d+\log (1/\delta ))/\epsilon )$. The agnostic upper bound is tight without a $\log (1/\epsilon )$ factor — the chaining / Dudley-entropy refinement removes the logarithm that a crude union bound over ${\Pi }_{\mathcal{H}}(2m)$ leaves — while the realizable upper bound retains a $\log (1/\epsilon )$ that is necessary for some classes and removable for others (the gap to the lower bound is a genuine and studied phenomenon) ^{[Shalev-Shwartz Ben-David 2014]}. These are the optimal distribution-free rates: no learner does asymptotically better against the worst distribution.

Theorem 2 (symmetrisation and the growth-function bound). For any class and $m{\epsilon }^2\ge 2$,

$$\underset{S}{\mathrm{Pr}}[\underset{h}{\sup }|L_S(h)-L_{\mathcal{D}}(h)|>\epsilon ]\le 2\underset{S,S^{\prime }}{\mathrm{Pr}}[\underset{h}{\sup }|L_S(h)-L_{S^{\prime }}(h)|>\frac{\epsilon }{2}]\le 4{\Pi }_{\mathcal{H}}(2m)e^{-m{\epsilon }^2/8}.$$

The first inequality is the ghost-sample reduction; the second is the Rademacher-swap union bound over the ${\Pi }_{\mathcal{H}}(2m)$ labelings realised on the doubled sample, each controlled by Hoeffding under the random signs ^{[Vapnik Chervonenkis 1971]}. This is the Vapnik-Chervonenkis route: the worst-case growth function is the only data-dependent quantity, and its logarithm is the effective dimension counted by the bound.

Theorem 3 ($\epsilon$-net theorem and the realizable rate). If $\mathrm{VCdim}(\mathcal{H})=d$ and $S$ is an i.i.d. sample of size $m\ge \frac{8}{\epsilon }(d\log \frac{16}{\epsilon }+\log \frac{2}{\delta })$, then with probability $\ge 1-\delta$ the sample is an $\epsilon$-net: every $h\in \mathcal{H}$ with $L_{\mathcal{D}}(h)\ge \epsilon$ errs on at least one sample point. Consequently any consistent learner (ERM in the realizable case) returns a hypothesis of true risk $<\epsilon$ ^{[Blumer Ehrenfeucht Haussler Warmuth 1989]}. The single power of $1/\epsilon$ is the structural reason realizable learning is cheaper than agnostic learning: a consistency event has an $e^{-m\epsilon }$ tail, not $e^{-m{\epsilon }^2}$.

Theorem 4 (necessity: uniform convergence forces finite VC dimension). If $\mathrm{VCdim}(\mathcal{H})=\infty$ then ${\Pi }_{\mathcal{H}}(m)=2^m$ for all $m$, so $\log {\Pi }_{\mathcal{H}}(m)/m=\log 2$ does not vanish, and the symmetrised bound is vacuous; concretely, the No-Free-Lunch averaging over the $2^{2m}$ labelings of a shattered $2m$-set produces, for every learner and every $m$, a distribution with excess risk $\ge 1/8$ with probability $\ge 1/7$ ^{[Shalev-Shwartz Ben-David 2014]}. Hence finite VC dimension is not merely sufficient but necessary for uniform convergence and for learnability, which is what upgrades the Vapnik-Chervonenkis sufficiency theorem and the Blumer-Ehrenfeucht-Haussler-Warmuth realizable bound into a full characterisation.

Synthesis. The foundational reason the subject closes is that one combinatorial integer governs an analytic property, an algorithmic property, and an abstract one, and every result here is that single fact read through a different lens. This is exactly the meeting of the No-Free-Lunch lower bound of 45.07.02 and the Sauer-Shelah upper bound of 45.07.03: the former shows infinite VC dimension defeats every learner at every scale, the latter shows finite VC dimension forces the growth function polynomial, and putting these together learnability becomes a zero-one property switched by whether $d$ is finite. The agnostic and realizable rates are dual readings of the same growth-function tail — two-sided risk estimation gives $1/{\epsilon }^2$, one-sided consistency through the $\epsilon$-net gives $1/\epsilon$ — and the symmetrisation step is the central insight that makes both possible, since it is what replaces the unknown true risk by a ghost sample on which only ${\Pi }_{\mathcal{H}}(2m)$ labelings survive. The cardinality $|\mathcal{H}|$ of the finite-class union bound generalises first to the growth function and here to the VC dimension, and the bridge upward at every level is the same substitution; the distribution-dependent sharpening that replaces the worst-case growth function by the Rademacher complexity of 45.07.05 is the next reading of the identical principle, that learnability is the concentration of a supremum over an effective count.

Full proof set Master

Proposition 1 (symmetrisation / ghost-sample inequality). Let $\mathcal{H}$ be a class under $0$–$1$ loss, $S,S^{\prime }\sim {\mathcal{D}}^m$ independent, and $\theta (S)={\sup }_h|L_S(h)-L_{\mathcal{D}}(h)|$. For $m{\epsilon }^2\ge 2$, ${\mathrm{Pr}}_S[\theta (S)>\epsilon ]\le 2{\mathrm{Pr}}_{S,S^{\prime }}[{\sup }_h|L_S(h)-L_{S^{\prime }}(h)|>\epsilon /2]$.

Proof. On the event $\theta (S)>\epsilon$ select a witness $h_S\in \mathcal{H}$, measurable in $S$, with $|L_S(h_S)-L_{\mathcal{D}}(h_S)|>\epsilon$. Independently of $S$, by Chebyshev applied to the empirical mean $L_{S^{\prime }}(h_S)$, whose variance is $L_{\mathcal{D}}(h_S)(1-L_{\mathcal{D}}(h_S))/m\le 1/(4m)$,

$$\underset{S^{\prime }}{\mathrm{Pr}}[|L_{S^{\prime }}(h_S)-L_{\mathcal{D}}(h_S)|\le \epsilon /2]\ge 1-\frac{1/(4m)}{(\epsilon /2{)}^2}=1-\frac{1}{m{\epsilon }^2}\ge \frac{1}{2}.$$

When both $|L_S(h_S)-L_{\mathcal{D}}(h_S)|>\epsilon$ and $|L_{S^{\prime }}(h_S)-L_{\mathcal{D}}(h_S)|\le \epsilon /2$ hold, the triangle inequality gives $|L_S(h_S)-L_{S^{\prime }}(h_S)|>\epsilon /2$, so ${\sup }_h|L_S(h)-L_{S^{\prime }}(h)|>\epsilon /2$. Integrating, ${\mathrm{Pr}}_{S,S^{\prime }}[{\sup }_h|L_S-L_{S^{\prime }}|>\epsilon /2]\ge \frac{1}{2}{\mathrm{Pr}}_S[\theta (S)>\epsilon ]$, which is the claim. $\square$

Proposition 2 (growth-function tail). With the notation of Proposition 1, ${\mathrm{Pr}}_{S,S^{\prime }}[{\sup }_h|L_S(h)-L_{S^{\prime }}(h)|>\epsilon /2]\le {\Pi }_{\mathcal{H}}(2m)\cdot 2e^{-m{\epsilon }^2/8}$, hence ${\mathrm{Pr}}_S[\theta (S)>\epsilon ]\le 4{\Pi }_{\mathcal{H}}(2m)e^{-m{\epsilon }^2/8}$.

Proof. Condition on the multiset of $2m$ points $T=S\cup S^{\prime }$. Let ${\sigma }_1,\dots ,{\sigma }_m$ be independent uniform $\pm 1$; swapping the $i$-th point of $S$ with the $i$-th point of $S^{\prime }$ when ${\sigma }_i=-1$ preserves the joint distribution of $(S,S^{\prime })$ because the $2m$ points are i.i.d. Thus ${\mathrm{Pr}}_{S,S^{\prime }}[{\sup }_h|L_S(h)-L_{S^{\prime }}(h)|>\epsilon /2]={\mathbb{E}}_T{\mathrm{Pr}}_{\sigma }[{\sup }_h|{\Delta }_{\sigma }(h)|>\epsilon /2]$, where ${\Delta }_{\sigma }(h)=\frac{1}{m}{\sum }_{i=1}^m{\sigma }_i(1[h(x_i)\ne y_i]-1[h(x_i^{\prime })\ne y_i^{\prime }])$. Conditioned on $T$, the value of ${\Delta }_{\sigma }(h)$ depends on $h$ only through its labeling of the $2m$ points, of which there are at most $|{\mathcal{H}}_T|\le {\Pi }_{\mathcal{H}}(2m)$. For each fixed labeling, ${\Delta }_{\sigma }$ is an average of $m$ independent mean-zero terms in $[-1/m,1/m]\cdot m$ scaled appropriately; Hoeffding's inequality gives ${\mathrm{Pr}}_{\sigma }[|{\Delta }_{\sigma }(h)|>\epsilon /2]\le 2e^{-2(\epsilon /2{)}^{2}m/4}=2e^{-m{\epsilon }^2/8}$. A union bound over the $\le {\Pi }_{\mathcal{H}}(2m)$ labelings and taking ${\mathbb{E}}_T$ yields the first inequality; combining with Proposition 1 gives the second. $\square$

Proposition 3 ($(vi)\Rightarrow (i)$: finite VC dimension implies uniform convergence). If $\mathrm{VCdim}(\mathcal{H})=d<\infty$ then $\mathcal{H}$ has the uniform-convergence property with $m_{\mathcal{H}}^{\mathrm{UC}}(\epsilon ,\delta )=O((d\log (1/\epsilon )+\log (1/\delta ))/{\epsilon }^2)$.

Proof. By Sauer-Shelah 45.07.03, ${\Pi }_{\mathcal{H}}(2m)\le (2em/d{)}^d$ for $m\ge d$. Proposition 2 gives ${\mathrm{Pr}}_S[\theta (S)>\epsilon ]\le 4(2em/d{)}^d{e}^{-m{\epsilon }^2/8}$. Taking logarithms, the right side is $\le \delta$ once $m{\epsilon }^2/8\ge \log 4+d\log (2em/d)+\log (1/\delta )$. At $m=K(d\log (1/\epsilon )+\log (1/\delta ))/{\epsilon }^2$ one has $\log m=O(\log (1/\epsilon )+\log d+\log \log (1/\delta ))$, so $d\log (2em/d)=O(d\log (1/\epsilon ))$, and for $K$ a large enough absolute constant the inequality holds. Hence $\theta (S)\le \epsilon$ with probability $\ge 1-\delta$ for all such $m$, the UC property. $\square$

Proposition 4 ($\epsilon$-net theorem; realizable rate). If $\mathrm{VCdim}(\mathcal{H})=d$ and $m\ge \frac{8}{\epsilon }(d\log \frac{16}{\epsilon }+\log \frac{2}{\delta })$, then with probability $\ge 1-\delta$ over $S\sim {\mathcal{D}}^m$ every $h\in \mathcal{H}$ with $L_{\mathcal{D}}(h)\ge \epsilon$ errs on at least one point of $S$. Hence in the realizable case any consistent learner outputs $\hat{h}$ with $L_{\mathcal{D}}(\hat{h})<\epsilon$ with probability $\ge 1-\delta$.

Proof. Let $B=\{h\in \mathcal{H}:L_{\mathcal{D}}(h)\ge \epsilon \}$ be the bad hypotheses; the failure event is that some $h\in B$ is consistent with $S$. A double-sample symmetrisation as in Proposition 1 (one-sided, comparing $S$ with a ghost $S^{\prime }$) bounds the probability that some $h\in B$ is consistent on $S$ yet errs on $\ge \epsilon m/2$ points of $S^{\prime }$ by $2{\Pi }_{\mathcal{H}}(2m)2^{-\epsilon m/2}$, because for a fixed bad labeling the random swap places its errors on the $S^{\prime }$ side with the required deficit with probability $\le 2^{-\epsilon m/2}$. By Sauer-Shelah this is $\le 2(2em/d{)}^d{2}^{-\epsilon m/2}$, which falls below $\delta$ at the stated $m$. On the complementary event no bad hypothesis is consistent with $S$, so a consistent $\hat{h}$ (which exists in the realizable case, as some $h^{\star }\in \mathcal{H}$ has $L_{\mathcal{D}}(h^{\star })=0$ and is consistent) has $L_{\mathcal{D}}(\hat{h})<\epsilon$. $\square$

Proposition 5 (lower bounds; necessity). For a class with $\mathrm{VCdim}(\mathcal{H})=d$ (possibly $\infty$), agnostic learning requires $m_{\mathcal{H}}(\epsilon ,\delta )=\Omega ((d+\log (1/\delta ))/{\epsilon }^2)$ and realizable learning requires $\Omega ((d+\log (1/\delta ))/\epsilon )$; if $d=\infty$ no finite sample suffices for either.

Proof. Take a shattered set $C$ of size $d$ (of arbitrary size if $d=\infty$). Restricting all distributions to $C$, every labeling of $C$ is realised in $\mathcal{H}$, so $\mathcal{H}$ on $C$ is the full class of binary functions on $d$ points. The No-Free-Lunch averaging argument of 45.07.02 over the $2^d$ labelings, with the points carrying slightly biased label noise of magnitude $\epsilon$, forces any learner to incur excess risk $>\epsilon$ with probability $>\delta$ unless $m=\Omega ((d+\log (1/\delta ))/{\epsilon }^2)$ in the agnostic case (the $d/{\epsilon }^2$ term from estimating $d$ near-balanced coins to accuracy $\epsilon$, the $\log (1/\delta )/{\epsilon }^2$ term from a single coin) and $\Omega ((d+\log (1/\delta ))/\epsilon )$ in the realizable case (deterministic labels, where one consistent-but-wrong hypothesis survives until $\Omega (1/\epsilon )$ relevant points are seen). For $d=\infty$ the bound is unbounded in $d$, so no finite $m$ works. $\square$

Connections Master

This unit is the capstone of the chapter opened by 45.07.02 and 45.07.03. The uniform-convergence property and the bias-complexity decomposition of 45.07.02 supply implications $(i)\Rightarrow (ii)\Rightarrow (iii)$ and the No-Free-Lunch lower bound that gives $(iii)\Rightarrow (vi)$; the Sauer-Shelah lemma of 45.07.03 supplies the growth bound that closes $(vi)\Rightarrow (i)$. The two earlier units are the analytic and combinatorial halves whose meeting is this equivalence, and the symmetrisation proof here is what joins them.

The destination from here is the distribution-dependent refinement of the chapter, the Rademacher-complexity bounds of 45.07.05: the worst-case growth function ${\Pi }_{\mathcal{H}}(2m)$ that controls the uniform deviation in this unit is replaced by the empirical Rademacher complexity ${\hat{\mathfrak{R}}}_S(\mathcal{H})$, which adapts to the actual distribution and recovers the VC bound through Massart's finite-class lemma and Sauer-Shelah as its worst case. The fundamental theorem is the distribution-free skeleton that the Rademacher theory fleshes out.

The lower-bound half rests on the No-Free-Lunch and averaging machinery already proved in 45.07.02: the matching $\Omega ((d+\log (1/\delta ))/{\epsilon }^2)$ agnostic bound is that construction applied to a shattered $d$-set with $\epsilon$-biased noise, so the optimality of the rate is inherited directly from the adversary argument of the prerequisite unit rather than reproved.

The symmetrisation and ghost-sample technique that drives the upper bound is the same empirical-process device that underlies the VC-Donsker theory and the uniform laws of large numbers of 45.05.03: there a VC class of functions is shown $P$-Donsker because Sauer-Shelah controls the metric entropy, and the doubled-sample randomisation here is the finite-sample shadow of that limit theorem. The Hoeffding and bounded-differences tails feeding both are the concentration spine of 40.07.05, which provides the per-labeling exponential bound that the union over ${\Pi }_{\mathcal{H}}(2m)$ labelings rests on.

Historical & philosophical context Master

The sufficiency half of the theorem — that a bound on the growth function yields uniform convergence of empirical frequencies to probabilities, with finiteness of the capacity (later named the VC dimension) the operative condition — was proved by Vladimir Vapnik and Alexey Chervonenkis in their 1971 paper, which also established the necessity of sublinear log-growth, making their result a characterisation of uniform convergence rather than a one-way bound ^{[Vapnik Chervonenkis 1971]}. The symmetrisation argument with a second independent sample is theirs.

The recasting of this analysis in the probably-approximately-correct framework introduced by Leslie Valiant in 1984 was carried out by Anselm Blumer, Andrzej Ehrenfeucht, David Haussler and Manfred Warmuth in their 1989 Journal of the ACM paper, which proved that a concept class is PAC learnable in the realizable case if and only if it has finite VC dimension, supplied the $\epsilon$-net theorem as the technical core of the realizable upper bound, and gave the matching lower bounds ^{[Blumer Ehrenfeucht Haussler Warmuth 1989]}. Their realizable rate $O((1/\epsilon )(d\log (1/\epsilon )+\log (1/\delta )))$ and its $\Omega (d/\epsilon )$ lower bound are the source of the realizable-versus-agnostic rate gap recorded here. The agnostic-case rate and the textbook assembly of all six conditions into the single named theorem are due to Shalev-Shwartz and Ben-David (2014) ^{[Shalev-Shwartz Ben-David 2014]}, building on the agnostic-PAC extension of Haussler and the empirical-process refinements of Talagrand and Dudley.

Bibliography Master

@article{vapnikchervonenkis1971,
  author  = {Vapnik, Vladimir N. and Chervonenkis, Alexey Ya.},
  title   = {On the uniform convergence of relative frequencies of events to their probabilities},
  journal = {Theory of Probability and Its Applications},
  volume  = {16},
  number  = {2},
  pages   = {264--280},
  year    = {1971}
}

@article{blumer1989,
  author  = {Blumer, Anselm and Ehrenfeucht, Andrzej and Haussler, David and Warmuth, Manfred K.},
  title   = {Learnability and the {Vapnik}-{Chervonenkis} dimension},
  journal = {Journal of the ACM},
  volume  = {36},
  number  = {4},
  pages   = {929--965},
  year    = {1989}
}

@book{shalevshwartzbendavid2014,
  author    = {Shalev-Shwartz, Shai and Ben-David, Shai},
  title     = {Understanding Machine Learning: From Theory to Algorithms},
  publisher = {Cambridge University Press},
  year      = {2014}
}

@book{mohri2018,
  author    = {Mohri, Mehryar and Rostamizadeh, Afshin and Talwalkar, Ameet},
  title     = {Foundations of Machine Learning},
  edition   = {2},
  publisher = {MIT Press},
  year      = {2018}
}

@article{haussler1992,
  author  = {Haussler, David},
  title   = {Decision theoretic generalizations of the {PAC} model for neural net and other learning applications},
  journal = {Information and Computation},
  volume  = {100},
  number  = {1},
  pages   = {78--150},
  year    = {1992}
}

@article{valiant1984,
  author  = {Valiant, Leslie G.},
  title   = {A theory of the learnable},
  journal = {Communications of the ACM},
  volume  = {27},
  number  = {11},
  pages   = {1134--1142},
  year    = {1984}
}

@book{vapnik1998,
  author    = {Vapnik, Vladimir N.},
  title     = {Statistical Learning Theory},
  publisher = {Wiley-Interscience},
  year      = {1998}
}