<p>People are going to recommend</p>

<p><a href="http://www.cs.nyu.edu/~mohri/mlbook/" rel="noreferrer">http://www.cs.nyu.edu/~mohri/mlbook/</a></p>

<p>and</p>

<p><a href="http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf" rel="noreferrer">http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf</a></p>

<p>-- so I might as well do it first :)</p>

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

CC BY-SA 3.0
2017-07-12T14:59:48.127Z
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).
Jack
CC BY-SA 3.0
2017-07-12T15:00:24.670Z
For *that* you probably still can't beat Kearns-Vazirani.
Aryeh
CC BY-SA 3.0
2017-07-12T15:01:37.750Z
I see; this was my original question. So you do think that Kearns-Vazirani is the most suitable for strict theory of ML?
Jack
CC BY-SA 3.0
2017-07-12T15:02:41.903Z
Also, check out O'Donnell's book -- it has many learning applications http://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf
Aryeh
CC BY-SA 3.0
2017-07-12T15:06:33.197Z
PS you should really check out those books in my answer if you want to enter the area of ML as a researcher -- theory or applied.
Aryeh
CC BY-SA 3.0
2017-07-12T15:08:19.600Z
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.
Jack
CC BY-SA 3.0
2017-07-12T15:10:51.353Z
Your OP indicates that you'd like to eventually publish in ICML,NIPS,COLT, etc. For that, you'll definitely need the more up-to-date material of the other books I linked.
Aryeh
CC BY-SA 3.0
2017-07-12T15:13:53.800Z
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) :)
Jack
CC BY-SA 3.0
2017-07-12T15:19:13.400Z
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.
Aryeh
CC BY-SA 3.0
2017-07-12T15:20:48.737Z
Interesting. I did not know this. This is one of the reasons I asked the question. Perhaps you can elaborate on this in your answer above? What does this separation mean?
Jack
CC BY-SA 3.0
2017-07-12T15:22:37.193Z
See here for elaboration https://cstheory.stackexchange.com/questions/35965/convergence-and-representation-theorems-for-machine-learning/35967#35967
Aryeh
CC BY-SA 3.0
2017-07-12T15:24:48.220Z
But this still means that K-V is NOT enough even for the purely STOC/FOCS ML, because FOCS/STOC ML do contain statistical ML theory papers, right? Hence the answer should have been: K-V + parts of the other texts, correct?
Jack
CC BY-SA 3.0
2017-07-12T15:27:46.940Z
If you resolve the status of noisy parity or learning DNF, you'll have no trouble getting that paper into STOC/FOCS.
Aryeh
CC BY-SA 3.0
2017-07-12T15:31:03.477Z
Yes; but this is not precisely the question. The question is not what is the minimal set of books/resources enough to understand/write *some* papers in "FOCS/STOC" style ML. Rather, it aims to learn *every* FOCS/STOC style ML.
Jack
CC BY-SA 3.0
2017-07-12T15:32:23.387Z
It's still an ill-posed question. No single book is ever *enough*. You start somewhere (and KV is a great place to start) and then play catch-up.
Aryeh
CC BY-SA 3.0
2017-07-12T15:32:58.770Z
And by your patient answers I understand that K-V is a good start, but to follow also statistical ML in STOC/FOCS I would need also some parts of the other books, correct?
Jack
CC BY-SA 3.0
2017-07-12T15:34:27.160Z
Absolutely! If you want a condensed intro course on the statistical issues, check out the one I taught -- the material is mostly online: https://www.cs.bgu.ac.il/~asml162/Class_Material
Aryeh
CC BY-SA 3.0
2017-07-12T15:35:29.233Z
I don't think it is ill-posed, because of the following simple example: it is obvious that there are some books that are completely irrelevant for me (e.g., books on hardware architecture). So the question is what is the minimum number of topics/books/resources that cover contemporary STOC/FOCS style ML.
Jack
CC BY-SA 3.0
2017-07-12T15:36:05.180Z
Unfortunately, there doesn't seem to be one. It's a very rapidly expanding field.
Aryeh
CC BY-SA 3.0
2017-07-12T15:36:48.550Z
yes, no one book. But a collection of books; with K-V as a good start. I begin to understand with your help. Thanks!
Jack
CC BY-SA 3.0
2017-07-12T15:37:27.010Z
... or even one (small) set of books...
Aryeh
CC BY-SA 3.0
2017-07-12T14:40:40.363Z
2017-07-12T14:40:40.363Z
Aryeh
<p>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 <strong>theoretical</strong> computer science community (those represented mainly in STOC/FOCS). My goal is to do research in the area from the strictly theoretical perspective.</p>

<p>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)?</p>

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

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

CC BY-SA 3.0
2017-07-12T14:38:45.043Z
See this thread https://cstheory.stackexchange.com/questions/35965/convergence-and-representation-theorems-for-machine-learning/35967#35967
Aryeh
<reference-request><machine-learning>
Textbook/resources for a beginning researcher in (Machine) Learning Theory
Jack
# Textbook/resources for a beginning researcher in (Machine) Learning Theory

(Asked by: username_0 on 2017-07-12)

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

**Tags:** reference-request, machine-learning
> **Comments:**
> **username_1**: See this thread https://cstheory.stackexchange.com/questions/35965/convergence-and-representation-theorems-for-machine-learning/35967#35967  

---

## 1 answers

### Answer by username_1 on 2017-07-12. Score: 5

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.

> **Comments:**
> **username_0**: 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).  
> **username_1**: For *that* you probably still can't beat Kearns-Vazirani.  
> **username_0**: I see; this was my original question. So you do think that Kearns-Vazirani is the most suitable for strict theory of ML?  
> **username_1**: Also, check out O'Donnell's book -- it has many learning applications http://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf  
> **username_1**: PS you should really check out those books in my answer if you want to enter the area of ML as a researcher -- theory or applied.  
> **username_0**: 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.  
> **username_1**: Your OP indicates that you'd like to eventually publish in ICML,NIPS,COLT, etc. For that, you'll definitely need the more up-to-date material of the other books I linked.  
> **username_0**: 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) :)  
> **username_1**: 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.  
> **username_0**: Interesting. I did not know this. This is one of the reasons I asked the question. Perhaps you can elaborate on this in your answer above? What does this separation mean?  
> **username_1**: See here for elaboration https://cstheory.stackexchange.com/questions/35965/convergence-and-representation-theorems-for-machine-learning/35967#35967  
> **username_0**: But this still means that K-V is NOT enough even for the purely STOC/FOCS ML, because FOCS/STOC ML do contain statistical ML theory papers, right? Hence the answer should have been: K-V + parts of the other texts, correct?  
> **username_1**: If you resolve the status of noisy parity or learning DNF, you'll have no trouble getting that paper into STOC/FOCS.  
> **username_0**: Yes; but this is not precisely the question. The question is not what is the minimal set of books/resources enough to understand/write *some* papers in "FOCS/STOC" style ML. Rather, it aims to learn *every* FOCS/STOC style ML.  
> **username_1**: It's still an ill-posed question. No single book is ever *enough*. You start somewhere (and KV is a great place to start) and then play catch-up.  
> **username_0**: And by your patient answers I understand that K-V is a good start, but to follow also statistical ML in STOC/FOCS I would need also some parts of the other books, correct?  
> **username_1**: Absolutely! If you want a condensed intro course on the statistical issues, check out the one I taught -- the material is mostly online: https://www.cs.bgu.ac.il/~asml162/Class_Material  
> **username_0**: I don't think it is ill-posed, because of the following simple example: it is obvious that there are some books that are completely irrelevant for me (e.g., books on hardware architecture). So the question is what is the minimum number of topics/books/resources that cover contemporary STOC/FOCS style ML.  
> **username_1**: Unfortunately, there doesn't seem to be one. It's a very rapidly expanding field.  
> **username_0**: yes, no one book. But a collection of books; with K-V as a good start. I begin to understand with your help. Thanks!  
> **username_1**: ... or even one (small) set of books...  

---

