Foundations of Machine Learning

This graduate-level textbook introduces fundamental concepts and methods in machine learning. It describes several important modern algorithms, provides the theoretical underpinnings of these algorithms, and illustrates key aspects for their application. The authors aim to present novel theoretical tools and concepts while giving concise proofs even for relatively advanced topics. Foundations of Machine Learning fills the need for a general textbook that also offers theoretical details and an emphasis on proofs. Certain topics that are often treated with insufficient attention are discussed in more detail here; for example, entire chapters are devoted to regression, multi-class classification, and ranking. The first three chapters lay the theoretical foundation for what follows, but each remaining chapter is mostly self-contained. The appendix offers a concise probability review, a short introduction to convex optimization, tools for concentration bounds, and several basic properties of matrices and norms used in the book.

The book is intended for graduate students and researchers in machine learning, statistics, and related areas; it can be used either as a textbook or as a reference text for a research seminar.

Table of Contents

1 Introduction
2 The PAC Learning Framework
3 Rademacher Complexity and VC Dimension
4 Support Vector Machines
5 Kernel Methods
6 Boosting
7 On-Line Learning
8 Multi-Class Classification
9 Ranking
10 Regression
11 Algorithmic Stability
12 Dimensionality Reduction
13 Learning Automata and Languages
14 Reinforcement Learning Conclusion
Appendix A Linear Algebra Review
Appendix B Convex Optimization
Appendix C Probability Review
Appendix D Concentration inequalities
Appendix E Notation