Is that true that PAC learnable implies agnostic PAC learnable for binary classification tasks

Question

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.

Answer 1

The question here is answered (in the comment section) on other SE's site here. I wrote this answer here merely for reference.

The part that I was missing here is not to take into account 1. and 4. are equivalent and also 1. and 3. are equivalent. So 3. and 4. are equivalent (through 1.).

There's also a direct approach to prove 3. and 4. are equivalent without using VC dimension here.