6
$\begingroup$

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

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
5
$\begingroup$

People are going to recommend

http://www.cs.nyu.edu/~mohri/mlbook/

and

http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf

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

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

Improve this answer
$\endgroup$
21
  • 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, 2017 at 14:59
  • 1
    $\begingroup$ For that you probably still can't beat Kearns-Vazirani. $\endgroup$
    – Aryeh
    Jul 12, 2017 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, 2017 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, 2017 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, 2017 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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