PAC Learning, Empirical Risk Minimization, and the Finite-Class Bound

Intuition Beginner

You are handed a stack of past examples — emails marked spam or not, photos marked cat or dog — and asked to produce a rule that will label the next, unseen example correctly. The trouble is that you only ever see the past stack, while you will be judged on the future. A rule that nails every example you were shown can still be useless tomorrow: it may have simply memorised the stack rather than learning the pattern. Learning theory is the study of when, and how strongly, doing well on the examples you have seen lets you trust that you will do well on examples you have not.

Two numbers carry the whole story. The first is the training error: the fraction of your given examples your rule gets wrong. The second is the true error: the fraction of all possible future examples it would get wrong, averaged over how often each one actually shows up. You can measure the first directly. You can never measure the second. The entire game is to bound the gap between them, so that a small measured training error becomes a promise about the unmeasured true error.

The natural strategy is to pick, from some agreed menu of candidate rules, whichever one makes the fewest mistakes on your examples. That strategy is called fitting the data, and the menu of candidates is your hypothesis class. The size of that menu matters: a richer menu fits the past better but is easier to fool into memorising. The finite-class bound makes this precise — with enough examples, and a menu that is not too large, the rule that fits best is, with high confidence, approximately correct.

Visual Beginner

Picture two bars for each candidate rule: a light bar for how often it errs on your training examples, and a dark bar for how often it would err on all future examples. You can read the light bars; the dark bars are hidden. With few examples the two bars can disagree wildly. As you collect more examples, the light bar is pulled toward the dark bar, and the gap shrinks at a predictable rate.

 error
   ^
   |  small sample             large sample
   |  light  dark              light  dark
   |  [###]  [#]               [##]   [##]
   |  [#]    [####]            [###]  [###]
   |  big gap                  bars nearly equal
   +----------------------------------------------> hypotheses

Examples seen	Training-error bar vs true-error bar	What you can promise
few	far apart, unreliable	almost nothing
many	close together	small training error means small true error

The lesson the picture teaches: more data narrows the gap, and a smaller menu of rules narrows it faster.

Worked example Beginner

A spam filter chooses among a menu of $|\mathcal{H}|=1000$ candidate rules. You collect $m=2000$ labelled emails, drawn at random, and you happen to be in the lucky case where at least one menu rule labels every kind of email perfectly — the realizable case. You run the obvious procedure: keep only rules that make zero mistakes on your $2000$ emails, and output one of them.

Step 1. Decide what counts as failure. Call a rule bad if its true error is more than $\epsilon =0.01$, that is, it would misclassify more than $1\%$ of future emails. We want to avoid outputting a bad rule.

Step 2. Bound the chance one fixed bad rule survives. A bad rule gets each random email wrong with chance more than $0.01$, so it gets each one right with chance less than $0.99$. To survive, it must get all $2000$ right, which has chance less than $0.99^{2000}$. Since $0.99^{2000}=(0.99^{100}{)}^{20}\approx 0.366^{20}$, this is about $10^{-9}$ — astronomically small.

Step 3. Account for all bad rules at once. There are at most $1000$ bad rules, and any one of them surviving would let us output a bad rule. The chance that some bad rule survives is at most $1000\times 0.99^{2000}\approx 1000\times 10^{-9}=10^{-6}$.

Step 4. Read off the guarantee. With chance at least $1-10^{-6}$, no bad rule survived, so every surviving rule — including the one we output — has true error at most $1\%$. We started knowing only the training error and ended with a promise about the true error.

What this tells us: combining "one bad rule rarely survives" with "there are not too many rules" turns a perfect fit on a finite sample into a high-confidence bound on future performance.

Check your understanding Beginner

Formal definition Intermediate+

Fix a domain (instance) set $\mathcal{X}$ and a label set $\mathcal{Y}$, with $\mathcal{Y}=\{0,1\}$ in the binary case. A hypothesis is a function $h:\mathcal{X}\to \mathcal{Y}$, and a hypothesis class $\mathcal{H}$ is a set of such functions. Data are generated by an unknown probability distribution $\mathcal{D}$ over $\mathcal{X}\times \mathcal{Y}$; a training sample $S=(z_1,\dots ,z_m)$ with $z_i=(x_i,y_i)$ is drawn i.i.d. from $\mathcal{D}$, written $S\sim {\mathcal{D}}^m$. A loss function $\ell :\mathcal{H}\times (\mathcal{X}\times \mathcal{Y})\to [0,1]$ scores a hypothesis on one example; the canonical choice is the $0$–$1$ loss $\ell (h,(x,y))=1[h(x)\ne y]$.

Definition (true and empirical risk). The true risk (population risk, generalization error) of $h$ is the expected loss

$$L_{\mathcal{D}}(h)={\mathbb{E}}_{z\sim \mathcal{D}}\ell (h,z)=\underset{(x,y)\sim \mathcal{D}}{\mathrm{Pr}}[h(x)\ne y],$$

and the empirical risk of $h$ on a sample $S$ is the average loss

$$L_S(h)=\frac{1}{m}\sum _{i=1}^m\ell (h,z_i)=\frac{|\{i:h(x_i)\ne y_i\}|}{m}.$$

For each fixed $h$, the strong law of large numbers 37.02.02 gives $L_S(h)\to L_{\mathcal{D}}(h)$ almost surely as $m\to \infty$; the quantitative rate is the content of this unit.

Definition (empirical risk minimization). An ERM rule for $\mathcal{H}$ returns any hypothesis minimizing empirical risk:

$${\mathrm{ERM}}_{\mathcal{H}}(S)\in \arg \underset{h\in \mathcal{H}}{\min }{L}_S(h).$$

Run over an unrestricted class, ERM overfits: a rule that memorizes $S$ achieves $L_S=0$ yet has true risk near that of random guessing. Restricting ERM to a fixed class $\mathcal{H}$ — choosing $\mathcal{H}$ before seeing the data — is the inductive bias that makes the procedure sound.

Definition (realizable case). The learning problem is realizable with respect to $\mathcal{H}$ if there exists $h^{\star }\in \mathcal{H}$ with $L_{\mathcal{D}}(h^{\star })=0$ (equivalently, in the noise-free model, the labels are $y=f(x)$ for some target $f\in \mathcal{H}$). In the realizable case ERM returns a hypothesis with $L_S=0$.

Definition (PAC learnability, realizable). A class $\mathcal{H}$ is PAC learnable if there is a function $m_{\mathcal{H}}:(0,1{)}^2\to \mathbb{N}$ and a learner $A$ such that for every $\epsilon ,\delta \in (0,1)$ and every realizable distribution $\mathcal{D}$, whenever $m\ge m_{\mathcal{H}}(\epsilon ,\delta )$,

$$\underset{S\sim {\mathcal{D}}^m}{\mathrm{Pr}}[L_{\mathcal{D}}(A(S))\le \epsilon ]\ge 1-\delta .$$

The reading is probably (confidence $1-\delta$) approximately correct (accuracy $\epsilon$); $m_{\mathcal{H}}$ is the sample complexity.

Definition (agnostic PAC learnability). Dropping realizability, $\mathcal{H}$ is agnostically PAC learnable if there is $m_{\mathcal{H}}$ and a learner $A$ such that for every $\epsilon ,\delta$ and every distribution $\mathcal{D}$, whenever $m\ge m_{\mathcal{H}}(\epsilon ,\delta )$,

$$\underset{S\sim {\mathcal{D}}^m}{\mathrm{Pr}}[L_{\mathcal{D}}(A(S))\le \underset{h\in \mathcal{H}}{\min }{L}_{\mathcal{D}}(h)+\epsilon ]\ge 1-\delta .$$

The benchmark is now the best achievable risk within $\mathcal{H}$, not zero: the learner competes with ${\inf }_{h\in \mathcal{H}}{L}_{\mathcal{D}}(h)$ rather than with perfection ^{[Mohri Rostamizadeh Talwalkar 2018]}.

Counterexamples to common slips Intermediate+

• "ERM with $L_S=0$ means the rule is correct." Only relative to the class. The memorizing rule $h(x)=y_i$ on seen $x_i$ and $h(x)=0$ elsewhere has $L_S=0$ but true risk near $\frac{1}{2}$; the guarantee comes from restricting to a fixed $\mathcal{H}$, not from $L_S=0$ alone.

• "PAC learnability needs to know $\mathcal{D}$." The definition quantifies over all distributions; the sample-complexity bound must hold uniformly, distribution-free. A learner tuned to one $\mathcal{D}$ is not a PAC learner.

• "The realizable and agnostic rates are the same." They are not: the realizable finite-class bound scales as $1/\epsilon$, the agnostic as $1/{\epsilon }^2$. The square comes from estimating a nonzero risk, where Hoeffding gives a $\sqrt{1/m}$ deviation rather than the exponentially-fast survival argument of the realizable case.

• "Agnostic learning makes the true error small." It makes the true error close to the best in class. If ${\min }_h{L}_{\mathcal{D}}(h)$ is large because $\mathcal{H}$ is a poor class, the agnostic guarantee is still satisfied while the absolute error stays large; choosing $\mathcal{H}$ is a separate, modelling decision.

Key theorem with proof Intermediate+

The two signature results are the finite-class bounds. In the realizable case the union bound over $\epsilon$-bad hypotheses gives a sample complexity scaling as $1/\epsilon$; in the agnostic case Hoeffding's inequality per hypothesis, followed by the same union bound, gives uniform convergence at rate $1/{\epsilon }^2$. Both run the deviation machinery of 40.07.05 against the finitely many members of $\mathcal{H}$.

Theorem (realizable finite-class bound). Let $\mathcal{H}$ be finite and the problem realizable. Let $A={\mathrm{ERM}}_{\mathcal{H}}$. Then for every $\epsilon ,\delta \in (0,1)$ and every realizable $\mathcal{D}$, if

$$m\ge \frac{\log (|\mathcal{H}|/\delta )}{\epsilon },$$

then ${\mathrm{Pr}}_{S\sim {\mathcal{D}}^m}[L_{\mathcal{D}}(A(S))\le \epsilon ]\ge 1-\delta$. Hence $\mathcal{H}$ is PAC learnable with $m_{\mathcal{H}}(\epsilon ,\delta )=\lceil \log (|\mathcal{H}|/\delta )/\epsilon \rceil$. ^{[Shalev-Shwartz Ben-David 2014]}

Proof. Realizability gives some $h^{\star }\in \mathcal{H}$ with $L_{\mathcal{D}}(h^{\star })=0$, so $L_S(h^{\star })=0$ for every sample, and ERM returns a hypothesis $A(S)$ with $L_S(A(S))=0$. The output can fail the accuracy goal only if it is bad and consistent: define the set of bad hypotheses

$${\mathcal{H}}_{\mathrm{bad}}=\{h\in \mathcal{H}:L_{\mathcal{D}}(h)>\epsilon \},$$

and the misleading event $M=\{S:\exists h\in {\mathcal{H}}_{\mathrm{bad}},L_S(h)=0\}$. If $S\notin M$ then no bad hypothesis is empirically consistent, so the consistent output $A(S)$ is not bad, that is $L_{\mathcal{D}}(A(S))\le \epsilon$. It remains to bound $\mathrm{Pr}(M)$.

Fix one $h\in {\mathcal{H}}_{\mathrm{bad}}$. Each example is misclassified by $h$ with probability $L_{\mathcal{D}}(h)>\epsilon$, so it is correctly classified with probability $1-L_{\mathcal{D}}(h)<1-\epsilon$. By independence of the $m$ examples,

$$\underset{S}{\mathrm{Pr}}[L_S(h)=0]=(1-L_{\mathcal{D}}(h){)}^m<(1-\epsilon {)}^m\le e^{-\epsilon m},$$

using $1-\epsilon \le e^{-\epsilon }$. A union bound over the at most $|\mathcal{H}|$ bad hypotheses gives

$$\mathrm{Pr}(M)=\underset{S}{\mathrm{Pr}}[\bigcup _{h\in {\mathcal{H}}_{\mathrm{bad}}}\{L_S(h)=0\}]\le \sum _{h\in {\mathcal{H}}_{\mathrm{bad}}}\underset{S}{\mathrm{Pr}}[L_S(h)=0]\le |\mathcal{H}|e^{-\epsilon m}.$$

Requiring $|\mathcal{H}|e^{-\epsilon m}\le \delta$ is, after taking logarithms, the condition $m\ge \log (|\mathcal{H}|/\delta )/\epsilon$, under which $\mathrm{Pr}(M)\le \delta$ and the accuracy guarantee holds with probability $\ge 1-\delta$. $\square$

Theorem (agnostic finite-class bound). Let $\mathcal{H}$ be finite, $\ell \in [0,1]$, and $\mathcal{D}$ arbitrary. Then for every $\delta \in (0,1)$, with probability at least $1-\delta$ over $S\sim {\mathcal{D}}^m$, uniform convergence holds:

$$\underset{h\in \mathcal{H}}{\sup }|L_S(h)-L_{\mathcal{D}}(h)|\le \sqrt{\frac{\log (2|\mathcal{H}|/\delta )}{2m}}.$$

Consequently $A={\mathrm{ERM}}_{\mathcal{H}}$ satisfies $L_{\mathcal{D}}(A(S))\le {\min }_{h\in \mathcal{H}}{L}_{\mathcal{D}}(h)+2\sqrt{\log (2|\mathcal{H}|/\delta )/(2m)}$, and $\mathcal{H}$ is agnostically PAC learnable with $m_{\mathcal{H}}(\epsilon ,\delta )=\lceil 2\log (2|\mathcal{H}|/\delta )/{\epsilon }^2\rceil$. ^{[Shalev-Shwartz Ben-David 2014]}

Proof. For a fixed $h$, the loss values $\ell (h,z_1),\dots ,\ell (h,z_m)$ are i.i.d. in $[0,1]$ with mean $L_{\mathcal{D}}(h)$, and $L_S(h)$ is their average. Hoeffding's inequality 40.07.05 applied to these bounded summands gives, for any $t>0$,

$$\underset{S}{\mathrm{Pr}}[|L_S(h)-L_{\mathcal{D}}(h)|\ge t]\le 2\exp (-2m{t}^2).$$

A union bound over the $|\mathcal{H}|$ hypotheses yields

$$\underset{S}{\mathrm{Pr}}[\underset{h\in \mathcal{H}}{\sup }|L_S(h)-L_{\mathcal{D}}(h)|\ge t]\le 2|\mathcal{H}|\exp (-2m{t}^2).$$

Setting the right side equal to $\delta$ and solving, $2|\mathcal{H}|e^{-2m{t}^2}=\delta$ gives $t=\sqrt{\log (2|\mathcal{H}|/\delta )/(2m)}$, which is the stated uniform bound holding with probability $\ge 1-\delta$. For the ERM consequence, let $h^{\star }\in \arg {\min }_h{L}_{\mathcal{D}}(h)$. On the high-probability event,

$$L_{\mathcal{D}}(A(S))\le L_S(A(S))+t\le L_S(h^{\star })+t\le L_{\mathcal{D}}(h^{\star })+2t,$$

where the middle inequality is the definition of ERM ($L_S(A(S))\le L_S(h^{\star })$) and the outer two are uniform convergence applied to $A(S)$ and to $h^{\star }$. Demanding $2t\le \epsilon$ gives the sample complexity. $\square$

Bridge. The finite-class bounds are the foundational reason that empirical risk minimization is sound, and they isolate the two ingredients every later generalization bound recombines: a per-hypothesis deviation estimate and a counting argument over the class. This is exactly the union-bound-over-bad-hypotheses pattern, and it builds toward uniform convergence over infinite classes in 45.07.02, where the naive factor $|\mathcal{H}|$ — meaningless when $\mathcal{H}$ is infinite — is replaced by the growth function and ultimately by the VC dimension of 45.07.03. The realizable-to-agnostic passage generalises the survival argument $(1-\epsilon {)}^m$ into the Hoeffding rate $e^{-2m{t}^2}$: putting these together, the realizable case is the degenerate limit where the competitor's risk is zero and the variance of the per-example loss collapses, so the $1/{\epsilon }^2$ agnostic rate sharpens to $1/\epsilon$. The central insight is that the cost of searching a class is logarithmic in its size, which appears again in 45.05.01 as the reason a union bound over $d$ or $d^2$ high-dimensional events costs only $\sqrt{\log d}$ once the per-event tail is sub-Gaussian. The bridge is that learning is concentration plus a covering count, and everything downstream refines the count.

Exercises Intermediate+

Advanced results Master

The finite-class bounds are the base case of a structure that extends in four directions: the bias-complexity tradeoff that quantifies the cost of the inductive bias, the No-Free-Lunch theorem that forbids distribution-free learning without any bias, the passage to infinite classes through uniform convergence, and the variance-aware sharpening that interpolates between the realizable and agnostic rates.

Theorem 1 (error decomposition and the bias-complexity tradeoff). For any $\mathcal{H}$ and the ERM output $\hat{h}$, the excess risk over the Bayes-optimal risk $L^{\star }={\inf }_{h:\mathcal{X}\to \mathcal{Y}}{L}_{\mathcal{D}}(h)$ splits as

$$L_{\mathcal{D}}(\hat{h})-L^{\star }=\underset{\text{approximation error}}{\underbrace{(\underset{h\in \mathcal{H}}{\inf }{L}_{\mathcal{D}}(h)-L^{\star })}}+\underset{\text{estimation error}}{\underbrace{(L_{\mathcal{D}}(\hat{h})-\underset{h\in \mathcal{H}}{\inf }{L}_{\mathcal{D}}(h))}}.$$

The approximation error is the price of the inductive bias and decreases as $\mathcal{H}$ grows; the estimation error is bounded by the agnostic finite-class theorem, $2\sqrt{\log (2|\mathcal{H}|/\delta )/(2m)}$, and increases with $|\mathcal{H}|$. Choosing $\mathcal{H}$ is the choice of where to sit on this tradeoff; richer classes lower bias and raise variance, the learning-theoretic form of the bias–variance decomposition ^{[Shalev-Shwartz Ben-David 2014]}.

Theorem 2 (No-Free-Lunch). For binary classification under $0$–$1$ loss, let $A$ be any learner and $m<|\mathcal{X}|/2$. Then there is a distribution $\mathcal{D}$ over $\mathcal{X}\times \{0,1\}$ such that some $f:\mathcal{X}\to \{0,1\}$ has $L_{\mathcal{D}}(f)=0$, yet

$$\underset{S\sim {\mathcal{D}}^m}{\mathrm{Pr}}[L_{\mathcal{D}}(A(S))\ge \frac{1}{8}]\ge \frac{1}{7}.$$

No learner succeeds on every distribution from few examples: learnability is impossible without restricting the hypothesis class. The proof averages the error of $A$ over all $2^{|C|}$ labelings of a set $C$ of $2m$ points; the learner sees at most half of $C$, and on the unseen half its expected error is $\ge 1/2$, so by averaging some labeling forces large error ^{[Shalev-Shwartz Ben-David 2014]}. No-Free-Lunch is the converse to PAC learnability: it shows the inductive bias of a fixed $\mathcal{H}$ is not a convenience but a logical necessity.

Theorem 3 (uniform convergence characterizes agnostic learnability). Say $\mathcal{H}$ has the uniform convergence property if there is $m_{\mathcal{H}}^{\mathrm{UC}}(\epsilon ,\delta )$ such that for $m\ge m_{\mathcal{H}}^{\mathrm{UC}}(\epsilon ,\delta )$, with probability $\ge 1-\delta$, ${\sup }_{h\in \mathcal{H}}|L_S(h)-L_{\mathcal{D}}(h)|\le \epsilon$. If $\mathcal{H}$ has uniform convergence then ERM agnostically PAC learns $\mathcal{H}$ with $m_{\mathcal{H}}(\epsilon ,\delta )\le m_{\mathcal{H}}^{\mathrm{UC}}(\epsilon /2,\delta )$. For binary classification the converse also holds — uniform convergence, agnostic learnability, and finite VC dimension are equivalent — the fundamental theorem of statistical learning ^{[Shalev-Shwartz Ben-David 2014]}. The finite-class theorem of this unit is the statement that every finite $\mathcal{H}$ has uniform convergence with $m_{\mathcal{H}}^{\mathrm{UC}}(\epsilon ,\delta )=\lceil \log (2|\mathcal{H}|/\delta )/(2{\epsilon }^2)\rceil$, the entry point to the equivalence.

Theorem 4 (interpolation: the low-noise / Bernstein regime). When the best-in-class risk is small — say $L_{\mathcal{D}}(h^{\star })=\beta$ — the agnostic rate interpolates between $1/{\epsilon }^2$ and $1/\epsilon$. Using the variance-aware Bernstein inequality 45.05.01 in place of Hoeffding, the estimation error of ERM over a finite class satisfies, with probability $\ge 1-\delta$,

$$L_{\mathcal{D}}(\hat{h})-L_{\mathcal{D}}(h^{\star })\le c\left(\sqrt{\frac{\beta \log (|\mathcal{H}|/\delta )}{m}}+\frac{\log (|\mathcal{H}|/\delta )}{m}\right),$$

a Bernstein-type or optimistic rate: when $\beta =0$ (realizable) the square-root term vanishes and the bound is the $1/m$ "fast rate", recovering the realizable theorem; when $\beta$ is bounded away from $0$ the square-root term dominates and the bound is the $1/\sqrt{m}$ "slow rate" of the agnostic theorem ^{[Mohri Rostamizadeh Talwalkar 2018]}. The variance term $\beta$ is exactly the quantity Hoeffding discards and Bernstein keeps, so the fast/slow dichotomy of learning is the Gaussian/exponential two-regime structure of 45.05.01 read through the lens of the optimal risk.

Synthesis. The finite-class bounds are one concentration argument run against a finite menu, and the foundational reason ERM is sound is that learning factors into a per-hypothesis deviation estimate times a count of the class — a count that the realizable union bound prices at $\log |\mathcal{H}|$ and that everything downstream refines. This is exactly the bias-complexity tradeoff: the count is the estimation error and grows with $|\mathcal{H}|$, while the approximation error shrinks with it, so No-Free-Lunch makes the choice of a fixed $\mathcal{H}$ a logical necessity rather than a modelling luxury. The realizable and agnostic theorems are the two endpoints of a single Bernstein-type bound, and they generalise the survival argument $(1-\epsilon {)}^m$ and the Hoeffding rate $e^{-2m{t}^2}$ into one interpolation governed by the best-in-class risk $\beta$: putting these together, the fast $1/m$ rate is the low-variance limit and the slow $1/\sqrt{m}$ rate the constant-variance limit of the variance-aware tail of 45.05.01, so the dichotomy of learning is the Gaussian/exponential dichotomy of concentration. The central insight is that the literal cardinality $|\mathcal{H}|$ is the wrong complexity measure for infinite classes and must be replaced by the growth function and the VC dimension, at which point uniform convergence, agnostic learnability, and finite VC dimension coincide — the fundamental theorem — and the bridge upward at every level is the same: estimate one hypothesis with concentration, then pay only the logarithm of an effective count.

Full proof set Master

Proposition 1 (realizable finite-class bound). If $\mathcal{H}$ is finite, the problem realizable, and $m\ge \log (|\mathcal{H}|/\delta )/\epsilon$, then ${\mathrm{ERM}}_{\mathcal{H}}$ outputs a hypothesis of true risk $\le \epsilon$ with probability $\ge 1-\delta$.

Proof. Realizability gives $h^{\star }\in \mathcal{H}$ with $L_{\mathcal{D}}(h^{\star })=0$, so $L_S(h^{\star })=0$ and ERM's output $\hat{h}$ has $L_S(\hat{h})=0$. The output fails only if some $\epsilon$-bad hypothesis is consistent, so let ${\mathcal{H}}_{\mathrm{bad}}=\{h:L_{\mathcal{D}}(h)>\epsilon \}$. For fixed $h\in {\mathcal{H}}_{\mathrm{bad}}$, by independence and $1-\epsilon \le e^{-\epsilon }$,

$$\underset{S}{\mathrm{Pr}}[L_S(h)=0]=(1-L_{\mathcal{D}}(h){)}^m<(1-\epsilon {)}^m\le e^{-\epsilon m}.$$

The union bound over ${\mathcal{H}}_{\mathrm{bad}}$ gives ${\mathrm{Pr}}_S[\exists h\in {\mathcal{H}}_{\mathrm{bad}}:L_S(h)=0]\le |\mathcal{H}|e^{-\epsilon m}$. The hypothesis $m\ge \log (|\mathcal{H}|/\delta )/\epsilon$ rearranges to $|\mathcal{H}|e^{-\epsilon m}\le \delta$, so with probability $\ge 1-\delta$ no bad hypothesis is consistent and $L_{\mathcal{D}}(\hat{h})\le \epsilon$. $\square$

Proposition 2 (Hoeffding deviation for a fixed hypothesis). For a fixed $h$ with loss in $[0,1]$ and i.i.d. sample of size $m$, ${\mathrm{Pr}}_S[|L_S(h)-L_{\mathcal{D}}(h)|\ge t]\le 2e^{-2m{t}^2}$.

Proof. The values $\ell (h,z_1),\dots ,\ell (h,z_m)$ are i.i.d., bounded in $[0,1]$, with mean $L_{\mathcal{D}}(h)$, and $L_S(h)$ is their average. Hoeffding's inequality 40.07.05 for an average of $m$ independent $[0,1]$-bounded variables states $\mathrm{Pr}[|\bar{X}-\mathbb{E}\bar{X}|\ge t]\le 2\exp (-2m{t}^2)$, where the constant $2m$ in the exponent comes from ${\sum }_i(b_i-a_i{)}^2=m\cdot 1^2$ in the denominator of the Hoeffding exponent $2t^2{m}^2/{\sum }_i(b_i-a_i{)}^2$. Substituting $\bar{X}=L_S(h)$ gives the claim. $\square$

Proposition 3 (agnostic uniform convergence). For finite $\mathcal{H}$ and loss in $[0,1]$, with probability $\ge 1-\delta$, ${\sup }_{h\in \mathcal{H}}|L_S(h)-L_{\mathcal{D}}(h)|\le \sqrt{\log (2|\mathcal{H}|/\delta )/(2m)}$.

Proof. By Proposition 2 and subadditivity of probability over the finite union,

$$\underset{S}{\mathrm{Pr}}[\underset{h\in \mathcal{H}}{\sup }|L_S(h)-L_{\mathcal{D}}(h)|\ge t]\le \sum _{h\in \mathcal{H}}\underset{S}{\mathrm{Pr}}[|L_S(h)-L_{\mathcal{D}}(h)|\ge t]\le 2|\mathcal{H}|e^{-2m{t}^2}.$$

Choose $t=\sqrt{\log (2|\mathcal{H}|/\delta )/(2m)}$; then $2m{t}^2=\log (2|\mathcal{H}|/\delta )$ and $2|\mathcal{H}|e^{-2m{t}^2}=2|\mathcal{H}|\cdot \delta /(2|\mathcal{H}|)=\delta$, so the supremum exceeds $t$ with probability $\le \delta$. $\square$

Proposition 4 (agnostic ERM excess-risk bound). Under the hypotheses of Proposition 3, with probability $\ge 1-\delta$ the ERM output $\hat{h}$ satisfies $L_{\mathcal{D}}(\hat{h})\le {\min }_{h\in \mathcal{H}}{L}_{\mathcal{D}}(h)+2\sqrt{\log (2|\mathcal{H}|/\delta )/(2m)}$.

Proof. Work on the event of Proposition 3, with $t=\sqrt{\log (2|\mathcal{H}|/\delta )/(2m)}$, and let $h^{\star }\in \arg {\min }_h{L}_{\mathcal{D}}(h)$. Uniform convergence at $\hat{h}$ gives $L_{\mathcal{D}}(\hat{h})\le L_S(\hat{h})+t$; ERM optimality gives $L_S(\hat{h})\le L_S(h^{\star })$; uniform convergence at $h^{\star }$ gives $L_S(h^{\star })\le L_{\mathcal{D}}(h^{\star })+t$. Chaining, $L_{\mathcal{D}}(\hat{h})\le L_{\mathcal{D}}(h^{\star })+2t$. $\square$

Proposition 5 (No-Free-Lunch, averaging form). Let $\mathcal{X}$ be finite with $|\mathcal{X}|=2m$, and consider learners receiving $m$ examples under $0$–$1$ loss. For any learner $A$, ${\max }_f{\mathbb{E}}_{S\sim {\mathcal{D}}_f^m}{L}_{{\mathcal{D}}_f}(A(S))\ge \frac{1}{4}$, where ${\mathcal{D}}_f$ is uniform on $\mathcal{X}$ labelled by $f$.

Proof. Let $C=\mathcal{X}$, $|C|=2m$, and let ${\mathcal{D}}_f$ be the uniform distribution on $C$ with deterministic labels $y=f(x)$, ranging over all $2^{2m}$ functions $f:C\to \{0,1\}$. Average the expected loss over $f$ drawn uniformly:

$${\mathbb{E}}_f{\mathbb{E}}_S{L}_{{\mathcal{D}}_f}(A(S))={\mathbb{E}}_f{\mathbb{E}}_S\frac{1}{2m}\sum _{x\in C}1[A(S)(x)\ne f(x)].$$

Fix the unlabelled sample positions and the draw of $S$; a sample of size $m$ touches at most $m$ of the $2m$ points, so at least $m$ points are unseen. For an unseen $x$, the label $f(x)$ is, under the uniform prior over $f$ and conditioned on the seen labels, a fair coin independent of $A(S)(x)$, so ${\mathrm{Pr}}_f[A(S)(x)\ne f(x)]=1/2$. Hence the averaged loss is at least $\frac{1}{2m}\cdot m\cdot \frac{1}{2}=\frac{1}{4}$. Since the average over $f$ is $\ge 1/4$, some $f$ achieves ${\mathbb{E}}_S{L}_{{\mathcal{D}}_f}(A(S))\ge 1/4$; a Markov argument on this expectation then yields a constant-probability lower bound on the error, the quantitative No-Free-Lunch statement. $\square$

Connections Master

• This unit is the base case for uniform convergence over infinite hypothesis classes in 45.07.02: there the factor $|\mathcal{H}|$ of the agnostic finite-class bound, vacuous when $\mathcal{H}$ is infinite, is replaced by the growth function ${\Pi }_{\mathcal{H}}(m)$ counting the distinct labelings $\mathcal{H}$ induces on $m$ points, and the same Hoeffding-plus-union-bound skeleton survives once symmetrization reduces the supremum over $\mathcal{H}$ to a supremum over those finitely many labelings.

• The complexity measure that controls the growth function is the VC dimension of 45.07.03: the Sauer–Shelah lemma bounds ${\Pi }_{\mathcal{H}}(m)$ by a polynomial of degree the VC dimension, so $\log {\Pi }_{\mathcal{H}}(m)=O(d\log m)$ takes the role $\log |\mathcal{H}|$ plays here, and the fundamental theorem of statistical learning identifies finite VC dimension with agnostic PAC learnability — the exact statement that this unit's finite-class theorem is the $d={\log }_2|\mathcal{H}|$ special case of.

• The deviation engine is the concentration spine: the agnostic bound is Hoeffding's inequality 40.07.05 applied per hypothesis, and the fast-rate / low-noise refinement is the variance-aware Bernstein inequality 45.05.01, whose Gaussian-then-exponential two-regime structure is precisely the slow-rate / fast-rate interpolation of learning, with the best-in-class risk $\beta$ playing the role of the variance term Hoeffding discards.

• The bias-complexity decomposition of the Advanced results is the learning-theoretic form of the bias–variance tradeoff of estimation 45.01.03, with approximation error in the role of squared bias and estimation error in the role of variance; the choice of hypothesis class here is the structural analogue of the regularization-parameter choice in high-dimensional regression 45.06.01, where the same tension between fitting capacity and statistical stability is resolved by a complexity penalty.

Historical & philosophical context Master

The probably-approximately-correct framework was introduced by Leslie Valiant in 1984 in Communications of the ACM ^{[Valiant 1984]}, which fused the statistical question of accuracy with the computational question of efficiency: a concept class is learnable if a polynomial-time algorithm, from polynomially many examples drawn from an arbitrary unknown distribution, returns with high probability a hypothesis of small error. Valiant's insistence on distribution-free guarantees and on explicit confidence ($\delta$) and accuracy ($\epsilon$) parameters set the template the field still uses. The realizable finite-class bound, with its union-bound-over-bad-hypotheses argument, is the simplest theorem in this model.

The statistical core predates Valiant. Vapnik and Chervonenkis, in their 1971 paper on the uniform convergence of relative frequencies to probabilities, established the uniform-convergence machinery and the dimension that bears their names, working in the agnostic (distribution-free) setting that Valiant's realizable model specializes ^{[Vapnik Chervonenkis 1971]}. The synthesis of the two traditions — the computational PAC model and the statistical VC theory — produced the fundamental theorem of statistical learning, that for binary classification agnostic PAC learnability, uniform convergence, and finite VC dimension coincide. The textbook treatments of Shalev-Shwartz and Ben-David (2014) and Mohri, Rostamizadeh and Talwalkar (2018) ^{[Mohri Rostamizadeh Talwalkar 2018]} organize the subject around exactly the finite-class bounds proved here as the entry point to that theorem.

Bibliography Master

@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}
}

@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}
}

@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{boucheronbousquetlugosi2005,
  author  = {Boucheron, St\'{e}phane and Bousquet, Olivier and Lugosi, G\'{a}bor},
  title   = {Theory of classification: a survey of some recent advances},
  journal = {ESAIM: Probability and Statistics},
  volume  = {9},
  pages   = {323--375},
  year    = {2005}
}

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