<p>I think that "there is a natural limit to what computers can learn", while definitely true, is not one of the main takeaways of Valiant's paper, for two reasons. One is that I could not find any discussion of lower bounds or no-free-lunch results in this paper. Two is that surely statisticians had been aware of such fundamental limitations on learnability prior to Valiant, if only as folklore.</p>

<p>I'd say the reason that paper has had such an impact is that it formalized an intuitively appealing learning model (what came to be known as PAC), which turned out to have a rich and satisfying mathematical structure, as well as numerous generalizations and extensions. Of course, finite-sample bounds had been obtained by Vapnik and Chervonenkis previously, but Valiant placed learning in an algorithmic setting by (among other things) emphasizing the importance of <em>representation</em>. In particular, he argued that DNFs are a natural human-interpretable representation and wondered whether these can be efficiently PAC-learned. (We now know that properly PAC-learning 3-term DNFs in polytime would imply NP=RP, but the agnostic case is still an active area of research and a major open question, as far as I know).</p>

<p>In summary: by Valiant's own admission, the statistical contributions of the paper are minor. He doesn't even need the full power of VC theory, since he mostly (exclusively) deals with discrete function classes, for which cardinality bounds + Chernoff do just fine. The reason that this paper has had such an impact on CS -- and indeed, probably the main reason why machine learning, by default, resides in CS departments -- has mainly to do with the computational aspects.</p>

CC BY-SA 4.0
2019-04-25T08:55:45.920Z
I think one delineate Valiant's contribution more clearly: PAC learning brought together, for the first time, and in a mathematically compelling model, two hitherto unconnected but rich theory traditions:  statistical learning and computational (worst-case time) complexity theory, yielding a tractable and *mathematical* (as opposed to folklore) notion of *feasible learning problem* by analogy with **P**, the poly-time computable functions. Or, more informally: PAC Learning connected (1) what can be learned with (2) how many steps it takes to learn.
Martin Berger
CC BY-SA 4.0
2019-05-07T01:26:33.403Z
Can you point to specific influential papers that followed from this?
Someone
CC BY-SA 4.0
2019-04-24T22:35:58.937Z
2019-04-25T08:52:45.410Z
2019-04-25T08:52:45.410Z
Aryeh
<p>It seems like two of the main takeaways were that there is a natural limit to what computers can learn, and learning is bounded by polynomial algorithms. Why was his paper significant in the broader area of machine learning?</p>

CC BY-SA 4.0
2019-04-25T08:51:56.777Z
I can see why people are voting to close, but I think this paper is sufficiently important that it's useful to clear up misconceptions around it.
Aryeh
<machine-learning>
What was the significance of Leslie Valiant's, "A Theory of the Learnable?"
Someone
# What was the significance of Leslie Valiant's, "A Theory of the Learnable?"

(Asked by: username_0 on 2019-04-24)

It seems like two of the main takeaways were that there is a natural limit to what computers can learn, and learning is bounded by polynomial algorithms. Why was his paper significant in the broader area of machine learning?

**Tags:** machine-learning

> **Comments:**
> **username_1**: I can see why people are voting to close, but I think this paper is sufficiently important that it's useful to clear up misconceptions around it.  

---

## 1 answers

### Answer by username_1 on 2019-04-24. Score: 8 | Accepted answer

I think that "there is a natural limit to what computers can learn", while definitely true, is not one of the main takeaways of Valiant's paper, for two reasons. One is that I could not find any discussion of lower bounds or no-free-lunch results in this paper. Two is that surely statisticians had been aware of such fundamental limitations on learnability prior to Valiant, if only as folklore.

I'd say the reason that paper has had such an impact is that it formalized an intuitively appealing learning model (what came to be known as PAC), which turned out to have a rich and satisfying mathematical structure, as well as numerous generalizations and extensions. Of course, finite-sample bounds had been obtained by Vapnik and Chervonenkis previously, but Valiant placed learning in an algorithmic setting by (among other things) emphasizing the importance of *representation*. In particular, he argued that DNFs are a natural human-interpretable representation and wondered whether these can be efficiently PAC-learned. (We now know that properly PAC-learning 3-term DNFs in polytime would imply NP=RP, but the agnostic case is still an active area of research and a major open question, as far as I know).

In summary: by Valiant's own admission, the statistical contributions of the paper are minor. He doesn't even need the full power of VC theory, since he mostly (exclusively) deals with discrete function classes, for which cardinality bounds + Chernoff do just fine. The reason that this paper has had such an impact on CS -- and indeed, probably the main reason why machine learning, by default, resides in CS departments -- has mainly to do with the computational aspects.

> **Comments:**
> **username_2**: I think one delineate Valiant's contribution more clearly: PAC learning brought together, for the first time, and in a mathematically compelling model, two hitherto unconnected but rich theory traditions:  statistical learning and computational (worst-case time) complexity theory, yielding a tractable and *mathematical* (as opposed to folklore) notion of *feasible learning problem* by analogy with **P**, the poly-time computable functions. Or, more informally: PAC Learning connected (1) what can be learned with (2) how many steps it takes to learn.  
> **username_0**: Can you point to specific influential papers that followed from this?  

---

