<p>The standard no-free-lunch argument can be stated and understood without any knowledge or deep understanding of VC theory. (The upper bound, with its reliance on Sauer’s lemma, is intimately intertwined with VC theory.) Let <span class="math-container">$\mathcal{X}=\mathbb{N}$</span> be the set of all natural numbers and let <span class="math-container">$\mathcal{C}$</span> be the collection of all Boolean functions (classifiers) on <span class="math-container">$\mathcal{X}$</span>. We can prove that <span class="math-container">$\mathcal{C}$</span> is not PAC-learnable as follows.</p>
<p>Suppose some learner claims that under <em>any</em> distribution, given <span class="math-container">$m$</span> iid labeled samples, he can guarantee an accuracy <span class="math-container">$0.99$</span> with confidence <span class="math-container">$0.99$</span>. Since we get to construct an adversarial distribution and target function, we can choose the distribution to be uniform on <span class="math-container">$[1,N]$</span>, for some <span class="math-container">$N\gg m$</span>, and the target function to be uniformly random among the <span class="math-container">$2^{2^{N}}$</span> classifiers (since the support is <span class="math-container">$[1,N]$</span>, it doesn't matter that these are not defined on all of <span class="math-container">$\mathcal{X}$</span>).</p>
<p>Here comes the key (and really, only) insight. Since the learner will, by construction, observe a sample much smaller than the support size of the distribution, and since the target function <span class="math-container">$f^*$</span> is chosen uniformly at random, the learner can do no better than to flip a coin at the instances whose label he has not observed. This can be made rigorous by an appeal to Fubini's theorem: when taking expectations, it doesn't matter whether the unseen values of <span class="math-container">$f^*$</span> were drawn before or after the sample was drawn.</p>
<p>Thus, the learner's expected error will behave like <span class="math-container">$\frac{N-m}{2N}$</span>, or close to <span class="math-container">$1/2$</span> for <span class="math-container">$N\gg m$</span>.</p>

CC BY-SA 4.0
2021-10-05T16:55:09.780Z
2021-10-06T07:37:19.407Z
2021-10-06T07:37:19.407Z
Aryeh
<p>I'm learning about PAC-learnability. I've figured out how to show that a class of classifiers is PAC-learnable, but what about if I want to show that a class of classifiers is not PAC-learnable? How should I go about it? Is it possible to do it without using VC-dimensions as argument? Thanks!</p>

CC BY-SA 4.0
2021-10-05T16:49:11.713Z
The fundamental theorem of statistical learning says that a class of classifiers if PAC-learnable iff it has finite VC-dimension, so perhaps the answer to your last question is no.
Bolton Bailey
<pac-learning>
Non-(PAC)-Learnable Classes
M. Fire
# Non-(PAC)-Learnable Classes

(Asked by: username_0 on 2021-10-05)

I'm learning about PAC-learnability. I've figured out how to show that a class of classifiers is PAC-learnable, but what about if I want to show that a class of classifiers is not PAC-learnable? How should I go about it? Is it possible to do it without using VC-dimensions as argument? Thanks!

**Tags:** pac-learning

> **Comments:**
> **username_1**: The fundamental theorem of statistical learning says that a class of classifiers if PAC-learnable iff it has finite VC-dimension, so perhaps the answer to your last question is no.  

---

## 1 answers

### Answer by username_2 on 2021-10-05. Score: 3

The standard no-free-lunch argument can be stated and understood without any knowledge or deep understanding of VC theory. (The upper bound, with its reliance on Sauer’s lemma, is intimately intertwined with VC theory.) Let $\mathcal{X}=\mathbb{N}$ be the set of all natural numbers and let $\mathcal{C}$ be the collection of all Boolean functions (classifiers) on $\mathcal{X}$. We can prove that $\mathcal{C}$ is not PAC-learnable as follows.

Suppose some learner claims that under *any* distribution, given $m$ iid labeled samples, he can guarantee an accuracy $0.99$ with confidence $0.99$. Since we get to construct an adversarial distribution and target function, we can choose the distribution to be uniform on $[1,N]$, for some $N\gg m$, and the target function to be uniformly random among the $2^{2^{N}}$ classifiers (since the support is $[1,N]$, it doesn't matter that these are not defined on all of $\mathcal{X}$).

Here comes the key (and really, only) insight. Since the learner will, by construction, observe a sample much smaller than the support size of the distribution, and since the target function $f^\*$ is chosen uniformly at random, the learner can do no better than to flip a coin at the instances whose label he has not observed. This can be made rigorous by an appeal to Fubini's theorem: when taking expectations, it doesn't matter whether the unseen values of $f^\*$ were drawn before or after the sample was drawn.

Thus, the learner's expected error will behave like $\frac{N-m}{2N}$, or close to $1/2$ for $N\gg m$.


---

