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?

  • 3
    $\begingroup$ 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. $\endgroup$
    – Aryeh
    Apr 25, 2019 at 8:51

1 Answer 1


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.

  • 2
    $\begingroup$ 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. $\endgroup$ Apr 25, 2019 at 8:55
  • $\begingroup$ Can you point to specific influential papers that followed from this? $\endgroup$
    – Someone
    May 7, 2019 at 1:26

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.