I'm looking to begin understanding basic concepts, notions, results and definitions in the area of Computational Learning Theory (or the theory of Machine Learning), as is done in the theoretical computer science community (those represented mainly in STOC/FOCS). My goal is to do research in the area from the strictly theoretical perspective.

What kind of textbooks/resources, basic papers are available for me? What kind of knowledge I need to have? Algorithms theory, or computational complexity theory? Or probability/probabilistic-methods (a la, Alon-Spencer)?

I have only seen a single textbook An Introduction to Computational Learning Theory by Michael Kearns and Umesh Virkumar Vazirani (1994), but I don't know if this is adequate/up to date.

So the question shortly is: How can a researcher start obtaining knowledge in theoretical Machine Learning? (Note I'm not interested as of now in any form of applications of ML.)


People are going to recommend




-- so I might as well do it first :)

I still think the Anthony-Bartlett is a better start for the mathematically oriented beginner.

| cite | improve this answer | |
  • 2
    $\begingroup$ Are these books adequate to those interested solely in STOC/FOCS style theoretical machine learning (if this style even exists)? As I'm not searching to understand applications (note the second book claims to speak about ML applications). $\endgroup$ – Jack Jul 12 '17 at 14:59
  • 1
    $\begingroup$ For that you probably still can't beat Kearns-Vazirani. $\endgroup$ – Aryeh Jul 12 '17 at 15:00
  • 1
    $\begingroup$ Thanks. But I don't follow precisely. Above you said that for theoretical ML as represented in STOC/FOCS Kearns-Vazinary is the best as a start, right? So do you think that also the other two books are essential? Note that one cannot start with more than one book. $\endgroup$ – Jack Jul 12 '17 at 15:08
  • 1
    $\begingroup$ I see. So perhaps I was not explaining the question correctly. I'm not interested in ICML, NIPS or COLT per se. I'm interested in what is happening in "STOC/FOCS" style ML. And any paper that is in the intersection of STOC/FOCS and ICML,NIPS, COLT (but not outside this intersection) :) $\endgroup$ – Jack Jul 12 '17 at 15:13
  • 1
    $\begingroup$ Advances in ML roughly decompose into algorithmic and statistical types. For the latter, you'll definitely need those books I linked. For the former, I am not aware of a modern algorithmic learning textbook beyond K-V. Perhaps someone should write one. $\endgroup$ – Aryeh Jul 12 '17 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.