<p>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.</p>

<p>Indeed, it is not known whether (efficient) PAC learning is NP-hard in general, but results on the <a href="http://robotics.upenn.edu/~mkearns/papers/crypto.pdf" rel="noreferrer">cryptographic hardness of learning</a> as well as on <a href="http://researcher.watson.ibm.com/researcher/files/us-vitaly/PittValiant88-e.pdf" rel="noreferrer">hardness of proper learning</a> make it universally believed that learning is hard.</p>

CC BY-SA 3.0
2013-11-11T23:56:01.923Z
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)?
Sasho Nikolov
CC BY-SA 3.0
2013-11-12T01:23:39.687Z
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.)
Lev Reyzin
CC BY-SA 3.0
2013-11-12T16:41:44.977Z
The following paper posted yesterday seems relevant to the discussion. http://arxiv.org/abs/1311.2272
Chandra Chekuri
CC BY-SA 3.0
2013-11-12T17:42:13.597Z
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 http://www.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!
Lev Reyzin
CC BY-SA 3.0
2013-11-11T19:15:21.800Z
2013-11-12T02:13:58.357Z
2013-11-12T02:13:58.357Z
Lev Reyzin
<p>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. </p>

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

CC BY-SA 3.0
2013-11-10T06:49:20.660Z
usually "pac-learnable" means in polynomial time. polynomial sample bounds are a necessary but not sufficient condition for learnability.
Sasho Nikolov
CC BY-SA 3.0
2013-11-10T19:50:06.640Z
@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
CC BY-SA 3.0
2013-11-10T21:40:15.837Z
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
CC BY-SA 3.0
2013-11-10T21:40:54.620Z
Valiant's paper: http://www.cs.princeton.edu/courses/archive/spr08/cos511/handouts/valiant.pdf
Sasho Nikolov
CC BY-SA 3.0
2013-11-11T03:06:31.840Z
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
CC BY-SA 3.0
2013-11-12T05:19:52.190Z
@seteropere Note that $\epsilon$ and $\delta$ are not the only, nor usually the most important, parameters for computational efficiency.
Lev Reyzin
<machine-learning><lg.learning><pac-learning>
What does PAC-learnability say about the learner runtime?
seteropere
# What does PAC-learnability say about the learner runtime?

(Asked by: username_0 on 2013-11-10)

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

**Tags:** machine-learning, lg.learning, pac-learning

> **Comments:**
> **username_1**: usually "pac-learnable" means in polynomial time. polynomial sample bounds are a necessary but not sufficient condition for learnability.  
> **username_0**: @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  
> **username_1**: 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".  
> **username_1**: Valiant's paper: http://www.cs.princeton.edu/courses/archive/spr08/cos511/handouts/valiant.pdf  
> **username_2**: 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.  
> **username_3**: @username_0 Note that $\epsilon$ and $\delta$ are not the only, nor usually the most important, parameters for computational efficiency.  

---

## 1 answers

### Answer by username_3 on 2013-11-11. Score: 10 | Accepted answer

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](http://robotics.upenn.edu/~mkearns/papers/crypto.pdf) as well as on [hardness of proper learning](http://researcher.watson.ibm.com/researcher/files/us-vitaly/PittValiant88-e.pdf) make it universally believed that learning is hard.

> **Comments:**
> **username_1**: 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)?  
> **username_3**: 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.)  
> **username_4**: The following paper posted yesterday seems relevant to the discussion. http://arxiv.org/abs/1311.2272  
> **username_3**: 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 http://www.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!  

---

