<p>The end of the proof of Theorem 7.2 explicitly states <em>&quot;Using the fundamental theorem of statistical learning, this implies that the VC dimension of <span class="math-container">$\mathcal{H}_n$</span> must be finite, and therefore <span class="math-container">$\mathcal{H}_n$</span> is agnostic PAC learnable.&quot;</em></p>
<p>Now, this is confusing, since looking at this &quot;fundamental theorem of statistical learning&quot; (Theorem 6.7 in this book), it looks like we want to use the implication <span class="math-container">$(4) \Rightarrow (6)$</span>, namely PAC learnability implies finite VC dimension. But, as you point out, instead of PAC learnability we only have the seemingly weaker guarantee you wrote:</p>
<blockquote>
<p>With probability at least <span class="math-container">$6/7$</span> over <span class="math-container">$S\sim \mathcal{D}^m$</span> we have <span class="math-container">$L_{\mathcal{D}}(A(S))\leq 1/8$</span></p>
</blockquote>
<p>using the notation of the book. <em>However</em>, if you look at the proof of Theorem 6.7, <span class="math-container">$(4) \Rightarrow (6)$</span> follows from the No-Free-Lunch theorem (Theorem 5.1), or rather its implication in terms of VC dimension (Corollary 6.4, and then Theorem 6.6). I'll let you check the details, but essentially it proves the stronger-looking statement you need:</p>
<blockquote>
<p>Let <span class="math-container">$\mathcal{H}$</span> be a class of infinite VC dimension. Then, for every <span class="math-container">$m$</span>, and every learning algorithm <span class="math-container">$A$</span>, there exists a distribution <span class="math-container">$\mathcal{D}$</span> and a predictor <span class="math-container">$h\in\mathcal{H}$</span> such that (i) <span class="math-container">$L_{\mathcal{D}}(h) = 0$</span>; but (ii) with probability at least <span class="math-container">$1/7$</span> over <span class="math-container">$S\sim \mathcal{D}^m$</span> we have <span class="math-container">$L_{\mathcal{D}}(A(S)) &gt; 1/8$</span>.</p>
</blockquote>

CC BY-SA 4.0
2020-10-11T17:33:25.127Z
That is a remarkable lemma. By definition if $H$ is not PAC learnable, there must be some degree of reliability $(\epsilon, \delta)$ small enough that for any $n$, the algorithm fails to be that reliable on samples of size $n$. Your version of the NFL theorem implies that $(\epsilon, \delta)$, if it exists, can always be chosen to be $(1/8, 1/7)$. That's as if there were some "magic number" like $1/8$ such that any sequence which isn't eventually within $1/8$ of a number $L$ does not converge to $L$, or equivalently, any sequence which is eventually within $1/8$ of $L$ *does* converge to $L$.
Jack M
CC BY-SA 4.0
2017-10-25T04:36:55.107Z
2020-10-11T18:12:47.550Z
2020-10-11T18:12:47.550Z
Clement C.
<p>Suppose we have a hypothesis class $\mathcal{H}$ that is non-uniform learnable via sample compelxity function $m_{\text{NUL}}:[0,1]^2 \times \mathcal{H} \rightarrow \mathbb{N}$.
If we define $\mathcal{H}_n=\{h \in \mathcal{H}: m_{\text{NUL}}(0.1,0.1,h) \le n\}$, why is $\mathcal{H}_n$ PAC-learnable?</p>

<p>This argument is used in <em>proof of theorem 7.2</em> in this book
<a href="http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf" rel="nofollow noreferrer">http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf</a></p>

<p>It is stated that, by assuming realizability, using the same learning algorithm $A$, with probability at least $0.9$ over sample $S \sim \mathcal{D}^n$, we have $L_{\mathcal{D}}(A(S)) \le 0.1$.
But I don't see immediately why this is PAC-learnable because we should be able to compress the error below any $\epsilon$ with arbitrarily high probability $1-\delta$. What is the trick?</p>

<machine-learning><lg.learning>
$L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability
raja.damanik
# $L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability

(Asked by: username_0 on 2017-10-23)

Suppose we have a hypothesis class $\mathcal{H}$ that is non-uniform learnable via sample compelxity function $m\_{\text{NUL}}:[0,1]^2 \times \mathcal{H} \rightarrow \mathbb{N}$.
If we define $\mathcal{H}\_n=\{h \in \mathcal{H}: m\_{\text{NUL}}(0.1,0.1,h) \le n\}$, why is $\mathcal{H}\_n$ PAC-learnable?

This argument is used in *proof of theorem 7.2* in this book
<http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf>

It is stated that, by assuming realizability, using the same learning algorithm $A$, with probability at least $0.9$ over sample $S \sim \mathcal{D}^n$, we have $L\_{\mathcal{D}}(A(S)) \le 0.1$.
But I don't see immediately why this is PAC-learnable because we should be able to compress the error below any $\epsilon$ with arbitrarily high probability $1-\delta$. What is the trick?

**Tags:** machine-learning, lg.learning

---

## 1 answers

### Answer by username_1 on 2017-10-25. Score: 4 | Accepted answer

The end of the proof of Theorem 7.2 explicitly states *"Using the fundamental theorem of statistical learning, this implies that the VC dimension of $\mathcal{H}\_n$ must be finite, and therefore $\mathcal{H}\_n$ is agnostic PAC learnable."*

Now, this is confusing, since looking at this "fundamental theorem of statistical learning" (Theorem 6.7 in this book), it looks like we want to use the implication $(4) \Rightarrow (6)$, namely PAC learnability implies finite VC dimension. But, as you point out, instead of PAC learnability we only have the seemingly weaker guarantee you wrote:

> With probability at least $6/7$ over $S\sim \mathcal{D}^m$ we have $L\_{\mathcal{D}}(A(S))\leq 1/8$

using the notation of the book. *However*, if you look at the proof of Theorem 6.7, $(4) \Rightarrow (6)$ follows from the No-Free-Lunch theorem (Theorem 5.1), or rather its implication in terms of VC dimension (Corollary 6.4, and then Theorem 6.6). I'll let you check the details, but essentially it proves the stronger-looking statement you need:

> Let $\mathcal{H}$ be a class of infinite VC dimension. Then, for every $m$, and every learning algorithm $A$, there exists a distribution $\mathcal{D}$ and a predictor $h\in\mathcal{H}$ such that (i) $L\_{\mathcal{D}}(h) = 0$; but (ii) with probability at least $1/7$ over $S\sim \mathcal{D}^m$ we have $L\_{\mathcal{D}}(A(S)) > 1/8$.

> **Comments:**
> **username_2**: That is a remarkable lemma. By definition if $H$ is not PAC learnable, there must be some degree of reliability $(\epsilon, \delta)$ small enough that for any $n$, the algorithm fails to be that reliable on samples of size $n$. Your version of the NFL theorem implies that $(\epsilon, \delta)$, if it exists, can always be chosen to be $(1/8, 1/7)$. That's as if there were some "magic number" like $1/8$ such that any sequence which isn't eventually within $1/8$ of a number $L$ does not converge to $L$, or equivalently, any sequence which is eventually within $1/8$ of $L$ *does* converge to $L$.  

---

