Mathematical Analysis of Machine Learning Algorithms

The mathematical theory of machine learning not only explains the current algorithms but can also motivate principled approaches for the future. This self-contained textbook introduces students and researchers of AI to the main mathematical techniques used to analyze machine learning algorithms, with motivations and applications. Topics covered include the analysis of supervised learning algorithms in the iid setting, the analysis of neural networks (e.g. neural tangent kernel and mean-field analysis), and the analysis of machine learning algorithms in the sequential decision setting (e.g. online learning, bandit problems, and reinforcement learning). Students will learn the basic mathematical tools used in the theoretical analysis of these machine learning problems and how to apply them to the analysis of various concrete algorithms. This textbook is perfect for readers who have some background knowledge of basic machine learning methods, but want to gain sufficient technical knowledge to understand research papers in theoretical machine learning.

Table of Contents:
1. Introduction; 2. Basic probability inequalities for sums of independent random variables; 3. Uniform convergence and generalization analysis; 4. Empirical covering number analysis and symmetrization; 5. Covering number estimates; 6. Rademacher complexity and concentration inequalities; 7. Algorithmic stability analysis; 8. Model selection; 9. Analysis of kernel methods; 10. Additive and sparse models; 11. Analysis of neural networks; 12. Lower bounds and minimax analysis; 13. Probability inequalities for sequential random variables; 14. Basic concepts of online learning; 15. Online aggregation and second order algorithms; 16. Multi-armed bandits; 17. Contextual bandits; 18. Reinforcement learning; A. Basics of convex analysis; B. f-Divergence of probability measures; References; Author index; Subject index.

About the Author :
Tong Zhang is Chair Professor of Computer Science and Mathematics at the Hong Kong University of Science and Technology, where his research focuses on machine learning, big data, and their applications. A Fellow of the IEEE, the American Statistical Association, and the Institute of Mathematical Statistics, Zhang has served as Chair or Area chair at major machine learning conferences such as NeurIPS, ICML, and COLT, and he has been an associate editor for several top machine learning publications including PAMI, JMLR, and 'Machine Learning.'

Review :
'This graduate-level text gives a thorough, rigorous and up-to-date treatment of the main mathematical tools that have been developed for the analysis and design of machine learning methods. It is ideal for a graduate class, and the exercises at the end of each chapter make it suitable for self-study. An excellent addition to the literature from one of the leading researchers in this area, it is sure to become a classic.' Peter Bartlett, University of California, Berkeley 'This book showcases the breadth and depth of mathematical ideas in learning theory. The author has masterfully synthesized techniques from the many disciplines that have contributed to this subject, and presented them in an accessible format that will be appreciated by both newcomers and experts alike. Readers will learn the tools-of-the-trade needed to make sense of the research literature and to express new ideas with clarity and precision.' Daniel Hsu, Columbia University 'Tong Zhang shares in this book his deep and broad knowledge of machine learning, writing an impressively comprehensive and up-to-date reference text, providing a rigorous and rather advanced treatment of the most important topics and approaches in the mathematical study of machine learning. As an authoritative reference and introduction, his book will be a great asset to the field.' Robert Schapire, Microsoft Research 'This book gives a systematic treatment of the modern mathematical techniques that are commonly used in the design and analysis of machine learning algorithms. Written by a key contributor to the field, it is a unique resource for graduate students and researchers seeking to gain a deep understanding of the theory of machine learning.' Shai Shalev-Shwartz, Hebrew University of Jerusalem 'Impressively comprehensive, exceptionally well written, effectively organized and presented, [this book] is an ideal addition to personal, professional, college, and university library Computer Science collections and Programming Algorithms & Pattern Recognition curriculum studies lists.' James A. Cox, Midwest Book Review '… the new textbook Mathematical Analysis of Machine Learning Algorithms by Professor Tong Zhang is a tour de force.… The book stands as a monumental achievement, and Zhang deserves high praise for this work … an indispensable resource for graduate students, researchers, and anyone seeking a rigorous understanding of machine learning.' Chinmay Hegde, SIGACT News 'This book provides an excellent introduction to theoretical aspects of machine learning for those who are willing to learn and appreciate the mathematical complexity of the underlying algorithms and statistics.' Physics Book Reviews