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

Improve this question
$\endgroup$
6
  • $\begingroup$ usually "pac-learnable" means in polynomial time. polynomial sample bounds are a necessary but not sufficient condition for learnability. $\endgroup$
    – Sasho Nikolov
    Commented Nov 10, 2013 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
    Commented Nov 10, 2013 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
    Commented Nov 10, 2013 at 21:40
  • 1
    $\begingroup$ Valiant's paper: cs.princeton.edu/courses/archive/spr08/cos511/handouts/… $\endgroup$
    – Sasho Nikolov
    Commented Nov 10, 2013 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
    Commented Nov 11, 2013 at 3:06

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Nov 11, 2013 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 ♦
    Commented Nov 12, 2013 at 1:23
  • 1
    $\begingroup$ The following paper posted yesterday seems relevant to the discussion. arxiv.org/abs/1311.2272 $\endgroup$
    – Chandra Chekuri
    Commented Nov 12, 2013 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 ♦
    Commented Nov 12, 2013 at 17:42

Your Answer

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

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