Textbook/resources for a beginning researcher in (Machine) Learning Theory 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

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.