What do you think?
Rate this book
Adaptive Computation and Machine Learning
Introduction to Online Convex Optimization
This manuscript portrays optimization as a process. In many practical applications the environment is so complex that it is infeasible to lay out a comprehensive theoretical model and use classical algorithmic theory and mathematical optimization. It is necessary as well as beneficial to take a robust approach, by applying an optimization method that learns as one goes along, learning from experience as more aspects of the problem are observed. This view of optimization as a process has become prominent in varied fields and has led to some spectacular success in modeling and systems that are now part of our daily lives.
209 pages, Paperback
Published April 22, 2017
17 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 of 1 review
August 5, 2018
This book is a practical overview of the growing field of online convex optimization. This area combines insights from game theory, computer science, optimization, statistics, and machine learning, and depending on the source, one will find a different emphasis, but by now there exists a mature body of algorithms and analysis techniques which form a unified discipline. In the "Online Convex Optimization" setup, one is faced with a series of convex functions f_t(x), and must choose before each one arrives a point x_t so as to be close to the minimum of the arriving function, with the objective to find an algorithm for picking points x_t to obtain an average value of f_t(x_t) not much larger than the average of f_t(x*) for the smallest possible point, over all possible sequences of f_t in some class. While the setting seems abstract, it has been shown to nest a variety of problems in optimization, forecasting, and game theory which require robust decision-making over time, and has substantial practical application in many of the algorithms which keep the web running by adapting decisions automatically to constantly shifting data.
This introduction is, more than others I've seen, rooted in optimization theory, drawing connections between online algorithms and classical convex optimization approaches, and while it includes a chapter of overview on the basics of first order convex optimization algorithms (gradient descent and its friends), many of the later chapters are devoted to constructing and analyzing online versions of more advanced classical methods including Newton's method (though the "online Newton" method is in fact a quasi-Newton approach), interior point methods, and conditional gradient (Franke Wolfe) methods. Applications include classics like prediction with expert advice, but also recommender systems (through the now-standard matrix completion formulation, which computer scientists have somehow settled on as the "right" model for this high dimensional preference estimation problem), finding Nash equilibria of zero sum games, and multi-armed bandits. The focus is tight, befitting a book designed for a single course, with approaches drawn from traditional convex analysis and optimization rather than statistics: this is a big contrast with, say, the Rakhlin and Sridharan book on this topic, which treats the area as an extension of statistical learning theory in terms of content and methods, or specialized books on bandit problems, which consider a mix of statistical and regret-based approaches. There is a concern with computational speed throughout, befitting the most successful practical applications of these methods in large scale data applications, and it is relentlessly practical, with descriptions detailed enough for a motivated reader to implement all the algorithms described. This will serve well a reader already convinced of the utility of the online learning approach and looking to begin solving practical problems.
This introduction is, more than others I've seen, rooted in optimization theory, drawing connections between online algorithms and classical convex optimization approaches, and while it includes a chapter of overview on the basics of first order convex optimization algorithms (gradient descent and its friends), many of the later chapters are devoted to constructing and analyzing online versions of more advanced classical methods including Newton's method (though the "online Newton" method is in fact a quasi-Newton approach), interior point methods, and conditional gradient (Franke Wolfe) methods. Applications include classics like prediction with expert advice, but also recommender systems (through the now-standard matrix completion formulation, which computer scientists have somehow settled on as the "right" model for this high dimensional preference estimation problem), finding Nash equilibria of zero sum games, and multi-armed bandits. The focus is tight, befitting a book designed for a single course, with approaches drawn from traditional convex analysis and optimization rather than statistics: this is a big contrast with, say, the Rakhlin and Sridharan book on this topic, which treats the area as an extension of statistical learning theory in terms of content and methods, or specialized books on bandit problems, which consider a mix of statistical and regret-based approaches. There is a concern with computational speed throughout, befitting the most successful practical applications of these methods in large scale data applications, and it is relentlessly practical, with descriptions detailed enough for a motivated reader to implement all the algorithms described. This will serve well a reader already convinced of the utility of the online learning approach and looking to begin solving practical problems.
Displaying 1 of 1 review