7
$\begingroup$

I am new to PAC-learnability. Assume a class $\mathcal{H}$ of hypotheses is PAC-learnable. Then all we know that if we draw polynomial number of examples (in $\delta$ and $\epsilon$), we can return a hypothesis with high accuracy.

But how this related to the complexity of the learner $L$?. Because I often read $\mathcal{H}$ is PAC-learnable if there exist an algorithm $L$ runs in time polynomial (in $\delta$ and $\epsilon$).

$\endgroup$
  • $\begingroup$ usually "pac-learnable" means in polynomial time. polynomial sample bounds are a necessary but not sufficient condition for learnability. $\endgroup$ – Sasho Nikolov Nov 10 '13 at 6:49
  • $\begingroup$ @SashoNikolov So $\mathcal{H}$ is PAC-learnable if there exists a polynomial time learner. This is completely different from what we got in the class (PAC-learnability is based on a polynomial number of examples regardless of the learner running time). Would you suggest me a resource illustrating this? Thanks $\endgroup$ – seteropere Nov 10 '13 at 19:50
  • 2
    $\begingroup$ AFAIK the standard definition is that a concept class is (efficiently) PAC learnable if there is a learner running in time polynomial in the various parameters. This is the definition in Valiant's "Theory of the Learnable", and in Kearns and Vazirani's monograph "Introduction to Computational Learning Theory". $\endgroup$ – Sasho Nikolov Nov 10 '13 at 21:40
  • 1
    $\begingroup$ Valiant's paper: cs.princeton.edu/courses/archive/spr08/cos511/handouts/… $\endgroup$ – Sasho Nikolov Nov 10 '13 at 21:40
  • 1
    $\begingroup$ I remember trying to find out recently whether there existed known classes that were PAC-learnable with a polynomial number of samples, but were not PAC-learnable in polynomial running time (say, assuming $\mathsf{P} \neq \mathsf{NP}$). I wasn't able to ascertain for certain but it seemed open to me. I'd be very interested if someone could answer this. $\endgroup$ – usul Nov 11 '13 at 3:06
10
$\begingroup$

PAC comes in two flavors -- "information theoretic PAC" and "efficient PAC." The latter asks for computational efficiency whereas the former cares only about sample size. One usually understands which is referred to from context.

Indeed, it is not known whether (efficient) PAC learning is NP-hard in general, but results on the cryptographic hardness of learning as well as on hardness of proper learning make it universally believed that learning is hard.

$\endgroup$
  • 1
    $\begingroup$ Lev, let me see if I understand you correctly: there is no known concept class with polynomial sampling complexity that requires super-polynomial running time to learn (based on cryptographic assumptions)? $\endgroup$ – Sasho Nikolov Nov 11 '13 at 23:56
  • 1
    $\begingroup$ Sorry if I wasn't clear. Yes, based on cryptographic assumptions there are classes, eg automata, that are hard to learn. We don't, however, have anything like NP-hardness of improper PAC learning. (I changed "hard" to "NP-hard" in my answer to clarify.) $\endgroup$ – Lev Reyzin Nov 12 '13 at 1:23
  • 1
    $\begingroup$ The following paper posted yesterday seems relevant to the discussion. arxiv.org/abs/1311.2272 $\endgroup$ – Chandra Chekuri Nov 12 '13 at 16:41
  • 1
    $\begingroup$ Interesting, thanks for the pointer! It seems this result is spiritually close to cryptographic hardness of learning results, which are also in some sense relying on average case hardness assumptions. Another relevant paper to this discussion is liafa.univ-paris-diderot.fr/~dxiao/docs/ABX08.pdf. It illustrates the difficulty of showing NP hardness of learning by proving that using standard techniques to get such a result would imply the collapse of the polynomial hierarchy! $\endgroup$ – Lev Reyzin Nov 12 '13 at 17:42

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.