# What does PAC-learnability say about the learner runtime?

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

• usually "pac-learnable" means in polynomial time. polynomial sample bounds are a necessary but not sufficient condition for learnability. – Sasho Nikolov Nov 10 '13 at 6:49
• @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 – seteropere Nov 10 '13 at 19:50
• 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". – Sasho Nikolov Nov 10 '13 at 21:40
• Valiant's paper: cs.princeton.edu/courses/archive/spr08/cos511/handouts/… – Sasho Nikolov Nov 10 '13 at 21:40
• 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. – usul Nov 11 '13 at 3:06