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.

  • $\begingroup$ It is true but not obvious. $\endgroup$ Nov 4 at 6:00
  • $\begingroup$ @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? $\endgroup$
    – Tran Khanh
    Nov 4 at 8:46
  • $\begingroup$ 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. $\endgroup$ Nov 4 at 8:49
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tran Khanh
    Nov 4 at 9:11
  • 1
    $\begingroup$ No problem. Also worth noting the sample complexity for agnostic PAC learning is strictly larger (in general) than the sample complexity for PAC learning. $\endgroup$ Nov 4 at 9:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.