Timeline for What does PAC-learnability say about the learner runtime?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 12, 2013 at 17:42 | comment | added | Lev Reyzin♦ | 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! | |
| Nov 12, 2013 at 16:41 | comment | added | Chandra Chekuri | The following paper posted yesterday seems relevant to the discussion. arxiv.org/abs/1311.2272 | |
| Nov 12, 2013 at 2:13 | history | edited | Lev Reyzin♦ | CC BY-SA 3.0 |
deleted 11 characters in body
|
| Nov 12, 2013 at 1:24 | history | edited | Lev Reyzin♦ | CC BY-SA 3.0 |
added 3 characters in body
|
| Nov 12, 2013 at 1:23 | comment | added | Lev Reyzin♦ | 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.) | |
| Nov 11, 2013 at 23:56 | comment | added | Sasho Nikolov | 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)? | |
| Nov 11, 2013 at 22:28 | vote | accept | seteropere | ||
| Nov 11, 2013 at 19:15 | history | answered | Lev Reyzin♦ | CC BY-SA 3.0 |