<p><em>The Fundamental Theorem of Statistical Learning</em> from the book &quot;Shai et al., <em>Understanding Machine Learning: From Theory to Algorithms</em>, Cambridge Press University&quot;, is written as follows:</p>
<blockquote>
<p>Let <span class="math-container">$\mathcal{H}$</span> be a hypothesis class of functions from a domain <span class="math-container">$\mathcal{X}$</span> to <span class="math-container">$\{0, 1\}$</span> and let the loss function be the 0−1 loss. Then, the following are equivalent:</p>
<ol>
<li><span class="math-container">$\mathcal{H}$</span> has the uniform convergence property</li>
<li>... (skipped this one)</li>
<li><span class="math-container">$\mathcal{H}$</span> is agnostic PAC learnable.</li>
<li><span class="math-container">$\mathcal{H}$</span> is PAC learnable.</li>
</ol>
</blockquote>
<p>But 3. equivalent to 4. means that PAC learnable implies agnostic PAC learnable for the hypothesis class of binary classifiers. But is that really true?</p>
<p>I know that 3. implies 4. is true because agnostic PAC learnable is a generalization of PAC learnable (and so it's true for all other types of learning tasks not only binary classification). But 3. implies 4. for binary classification isn't quite obvious to me.</p>
<p>Here's what I've tried so far:</p>
<p>Denote by <span class="math-container">$\mathbb{N}$</span> the set of natural numbers, <span class="math-container">$\mathbb{P}[\cdot]$</span> the probability of some random event, <span class="math-container">$\mathbb{M}$</span> the set of all functions from <span class="math-container">$(0,1)\times (0,1)\to \mathbb{N}$</span>, <span class="math-container">$\mathbb{D}$</span> the set of all distributions over <span class="math-container">$\mathcal{X}$</span>, <span class="math-container">$F$</span> the set of all functions from the domain set <span class="math-container">$\mathcal{X}\to \{0, 1\}$</span>, <span class="math-container">$\mathcal{S}_{\mathcal{D}}$</span> the set of all training sets generated by some <span class="math-container">$\mathcal{D}\in \mathbb{D}$</span>, <span class="math-container">$\mathbb{A}$</span> is a set of all functions from <span class="math-container">$\mathcal{S}_{\mathcal{D}}\to \mathcal{H}$</span>, that is <span class="math-container">$\mathcal{A}$</span> accepts a training set <span class="math-container">$S\in\mathcal{S}_{\mathcal{D}}$</span> as input and returns a hypothesis <span class="math-container">$h\in \mathcal{H}$</span>. Also:</p>
<p><span class="math-container">$$
R=(\forall \mathcal{D}\in\mathbb{D})(\exists h^{\star}\in F)(L_{\mathcal{D}, f}(h^{\star})=0)
$$</span></p>
<p>Suppose <span class="math-container">$\mathcal{H}$</span> is PAC-learnable, from def. of PAC-learnability we have that:</p>
<p><span class="math-container">$$
\begin{align}
R(\mathcal{H}\text{ is PAC-learnable})&amp;\leftrightarrow
(\forall\mathcal{D}\in\mathbb{D})(\forall \epsilon\in(0, 1))(\forall\delta\in(0, 1))
\\
&amp;(\exists m_{\mathcal{H}}\in \mathbb{M})(\exists A\in \mathbb{A})
\\
&amp;(\forall m\ge m_{\mathcal{H}})(\forall S\in\mathcal{S}_{\mathcal{D}^{m}})(h=A(S))
\\
&amp;(\mathbb{P}[L_{\mathcal{D}, f}(h):=\underset{x\sim\mathcal{D}}{\mathbb{P}}[h(x)\neq h^{\star}(x)]\le\epsilon])\ge1-\epsilon)
\end{align}
$$</span></p>
<p>Now for agnostic PAC-learnable, not only <span class="math-container">$R=True$</span> no longer holds but a number of things changed:</p>
<ul>
<li>The data-label function is replaced by data-generating distribution, which follows that,</li>
<li>The generalization loss function changed to <span class="math-container">$L_{\mathcal{D}}(h):=\underset{(x, y)\sim\mathcal{D}}{\mathbb{P}}[h(x)\neq y]$</span> which leads to</li>
<li>The inequality for <span class="math-container">$\mathcal{H}$</span> in PAC-learnable setting <span class="math-container">${\mathbb{P}}[h(x)\neq h^{\star}(x)]\le\epsilon])\ge1-\epsilon$</span> no longer applicable.</li>
</ul>
<p>And the entire logic goes haywire.</p>

CC BY-SA 4.0
2023-11-04T06:00:08.933Z
It is true but not obvious.
mathworker21
CC BY-SA 4.0
2023-11-04T08:46:05.287Z
@mathworker21 could you collaborate more on it, PAC-learning assumes realizability holds when PAC-learning assumes a data-generating distribution, how can I adapt the same hypothesis class to two fundamentally different settings now?
Tran Khanh
CC BY-SA 4.0
2023-11-04T08:49:30.610Z
Have you looked at the book at all? The way it's proven is by showing finite VC dimension is necessary and sufficient for each learning task separately. I.e., if $\mathcal{H}$ is PAC learnable, then $\mathcal{H}$ has finite VC dimension, and thus $\mathcal{H}$ is agnostic PAC learnable.
mathworker21
CC BY-SA 4.0
2023-11-04T08:50:10.380Z
Alternatively, there is this [recent paper](https://arxiv.org/abs/2111.04746), which shows the equivalence directly (I think for the first time?).
mathworker21
CC BY-SA 4.0
2023-11-04T09:11:46.490Z
@mathworker21, wow it's very true!!! the part you mentioned leveraging VC dimension that's where I'd been missing (and so dumb trying to prove the fact without using it), it couldn't be more simple as that turn of logic! Thanks for pointing that out.
Tran Khanh
CC BY-SA 4.0
2023-11-04T09:22:11.213Z
@mathworker21, and also for the paper you provided!
Tran Khanh
CC BY-SA 4.0
2023-11-04T09:23:24.537Z
No problem. Also worth noting the sample complexity for agnostic PAC learning is strictly larger (in general) than the sample complexity for PAC learning.
mathworker21
<machine-learning><pac-learning>
Does PAC learnable imply agnostic PAC learnable for binary classification tasks?
Tran Khanh
# Does PAC learnable imply agnostic PAC learnable for binary classification tasks?

(Asked by: username_0 on 2023-11-04)

*The Fundamental Theorem of Statistical Learning* from the book "Shai et al., *Understanding Machine Learning: From Theory to Algorithms*, Cambridge Press University", is written as follows:

> Let $\mathcal{H}$ be a hypothesis class of functions from a domain $\mathcal{X}$ to $\{0, 1\}$ and let the loss function be the 0−1 loss. Then, the following are equivalent:
>
> 1. $\mathcal{H}$ has the uniform convergence property
> 2. ... (skipped this one)
> 3. $\mathcal{H}$ is agnostic PAC learnable.
> 4. $\mathcal{H}$ is PAC learnable.

But 3. equivalent to 4. means that PAC learnable implies agnostic PAC learnable for the hypothesis class of binary classifiers. But is that really true?

I know that 3. implies 4. is true because agnostic PAC learnable is a generalization of PAC learnable (and so it's true for all other types of learning tasks not only binary classification). But 3. implies 4. for binary classification isn't quite obvious to me.

Here's what I've tried so far:

Denote by $\mathbb{N}$ the set of natural numbers, $\mathbb{P}[\cdot]$ the probability of some random event, $\mathbb{M}$ the set of all functions from $(0,1)\times (0,1)\to \mathbb{N}$, $\mathbb{D}$ the set of all distributions over $\mathcal{X}$, $F$ the set of all functions from the domain set $\mathcal{X}\to \{0, 1\}$, $\mathcal{S}\_{\mathcal{D}}$ the set of all training sets generated by some $\mathcal{D}\in \mathbb{D}$, $\mathbb{A}$ is a set of all functions from $\mathcal{S}\_{\mathcal{D}}\to \mathcal{H}$, that is $\mathcal{A}$ accepts a training set $S\in\mathcal{S}\_{\mathcal{D}}$ as input and returns a hypothesis $h\in \mathcal{H}$. Also:

$$
R=(\forall \mathcal{D}\in\mathbb{D})(\exists h^{\star}\in F)(L\_{\mathcal{D}, f}(h^{\star})=0)
$$

Suppose $\mathcal{H}$ is PAC-learnable, from def. of PAC-learnability we have that:

$$
\begin{align}
R(\mathcal{H}\text{ is PAC-learnable})&\leftrightarrow
(\forall\mathcal{D}\in\mathbb{D})(\forall \epsilon\in(0, 1))(\forall\delta\in(0, 1))
\\
&(\exists m\_{\mathcal{H}}\in \mathbb{M})(\exists A\in \mathbb{A})
\\
&(\forall m\ge m\_{\mathcal{H}})(\forall S\in\mathcal{S}\_{\mathcal{D}^{m}})(h=A(S))
\\
&(\mathbb{P}[L\_{\mathcal{D}, f}(h):=\underset{x\sim\mathcal{D}}{\mathbb{P}}[h(x)\neq h^{\star}(x)]\le\epsilon])\ge1-\epsilon)
\end{align}
$$

Now for agnostic PAC-learnable, not only $R=True$ no longer holds but a number of things changed:

* The data-label function is replaced by data-generating distribution, which follows that,
* The generalization loss function changed to $L\_{\mathcal{D}}(h):=\underset{(x, y)\sim\mathcal{D}}{\mathbb{P}}[h(x)\neq y]$ which leads to
* The inequality for $\mathcal{H}$ in PAC-learnable setting ${\mathbb{P}}[h(x)\neq h^{\star}(x)]\le\epsilon])\ge1-\epsilon$ no longer applicable.

And the entire logic goes haywire.

**Tags:** machine-learning, pac-learning
> **Comments:**
> **username_1**: It is true but not obvious.  
> **username_0**: @mathworker21 could you collaborate more on it, PAC-learning assumes realizability holds when PAC-learning assumes a data-generating distribution, how can I adapt the same hypothesis class to two fundamentally different settings now?  
> **username_1**: Have you looked at the book at all? The way it's proven is by showing finite VC dimension is necessary and sufficient for each learning task separately. I.e., if $\mathcal{H}$ is PAC learnable, then $\mathcal{H}$ has finite VC dimension, and thus $\mathcal{H}$ is agnostic PAC learnable.  
> **username_1**: Alternatively, there is this [recent paper](https://arxiv.org/abs/2111.04746), which shows the equivalence directly (I think for the first time?).  
> **username_0**: @mathworker21, wow it's very true!!! the part you mentioned leveraging VC dimension that's where I'd been missing (and so dumb trying to prove the fact without using it), it couldn't be more simple as that turn of logic! Thanks for pointing that out.  
> **username_0**: @mathworker21, and also for the paper you provided!  
> **username_1**: No problem. Also worth noting the sample complexity for agnostic PAC learning is strictly larger (in general) than the sample complexity for PAC learning.  

---

## 0 answers

