Algorithmic Aspects of Machine Learning

'The unreasonable effectiveness of modern machine learning has thrown the gauntlet down to theoretical computer science. Why do heuristic algorithms so often solve problems that are intractable in the worst case? Is there predictable structure in the problem instances that arise in practice? Can we design novel algorithms that exploit such structure? This book is an introduction to the state-of-the-art at the interface of machine learning and theoretical computer science, lucidly written by a leading expert in the area.' Tim Roughgarden, Stanford University, California 'This book is a gem. It is a series of well-chosen and organized chapters, each centered on one algorithmic problem arising in machine learning applications. In each, the reader is lead through different ways of thinking about these problems, modeling them, and applying different algorithmic techniques to solving them. In this process, the reader learns new mathematical techniques from algebra, probability, geometry and analysis that underlie the algorithms and their complexity. All this material is delivered in a clear and intuitive fashion.' Avi Wigderson, Institute for Advanced Study, New Jersey 'A very readable introduction to a well-curated set of topics and algorithms. It will be an excellent resource for students and researchers interested in theoretical machine learning and applied mathematics.' Sanjeev Arora, Princeton University, New Jersey 'This text gives a clear exposition of important algorithmic problems in unsupervised machine learning including nonnegative matrix factorization, topic modeling, tensor decomposition, matrix completion, compressed sensing, and mixture model learning. It describes the challenges that these problems present, gives provable guarantees known for solving them, and explains important algorithmic techniques used. This is an invaluable resource for instructors and students, as well as all those interested in understanding and advancing research in this area.' Avrim Blum, Toyota Technical Institute at Chicago 'Moitra ... has written a high-level, fast-paced book on connections between theoretical computer science and machine learning. ... A main theme throughout the book is to go beyond worst-case analysis of algorithms. This is done in three ways: by probabilistic algorithms, by algorithms that are very efficient on simple inputs, and by notions of stability that emphasize instances of problems that have meaningful answers and thus are particularly important to solve. ... Summing Up: Highly recommended.' M. Bona, Choice '... the challenges to prove simple but unproven claims and delving deeper into the topics makes it a fascinating read ... one of the best parts of the book is the introduction to each chapter. They thoroughly motivate the topic of the chapters.' Sarvagya Upadhyay, SIGACT News