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!

  • $\begingroup$ 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. $\endgroup$ Oct 5 '21 at 16:49

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.