1
$\begingroup$

This is usually shown by an application of the Statistical No Free Lunch Theorem.

But is this possible to show this by working simply with the definition of PAC learnability and the sample complexity VC bound.

In particular if it's PAC learnable we know that for any $\epsilon$ and $\delta$ we have a sample complexity VC lower bound $m(\epsilon, \delta)$ such that if we have $m > m(\epsilon, \delta)$ samples we get a $L_D(A(S)) <\epsilon$, where $m(\epsilon,\delta)=\Theta(\frac{VC}{\epsilon^2})$. Thus with an infinite VC dimension the sample complexity lower bound tends to infinity, meaning that we won't be able to learn assuming a non-infinite sample of data.

Are there any issues with this argument that infinite VC dimension of a hypothesis class implies that the hypothesis class is not PAC learnable?

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you please proofread the post? I'm confused about what is common knowledge, what only you know, and what you are asking about. $\endgroup$
    – Dmitry
    Mar 21 at 0:03
  • $\begingroup$ @Dmitry Proofread and edited for clarity. I am asking if the argument that there would need to be an infinite number of samples in the infinite VC dimension case means that it is not PAC learnable. $\endgroup$
    – JustBlaze
    Mar 21 at 14:48
  • $\begingroup$ Thanks. Yes, infinite VC dimension means that it's not PAC learnable. Check e.g. "Learnability and the Vapnik-Chervonenkis dimension", Theorem 2.1. It might be better to look at some lecture notes/slides, e.g. cs.princeton.edu/~rlivni/cos511/lectures/lect3.pdf or cs.uu.nl/docs/vakken/mbd/slides/PAC-and-VC.pdf. You might consider some weaker notion of learnability where you drop some uniformity requirements (e.g. that you must handle arbitrary input distribution or arbitrary ground-truth concept). $\endgroup$
    – Dmitry
    Mar 21 at 15:21

0

Reset to default

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.