Introductory lectures on stochastic optimization
In this set of four lectures, we study the basic analytical tools and algorithms necessary for the solution of stochastic convex optimization problems, as well as for providing various optimality guarantees associated with the methods. As we proceed through the lectures, we will be more exact about the precise problem formulations, providing a number of examples, but roughly, by a stochastic optimization problem we mean a numerical optimization problem that arises from observing data from some (random) data generating process. We focus almost exclusively on first order methods for the solution of these types of problems, as they have proven quite succesful in the large scale problems that have driven many advances throughout the early 2000s, so that readers should not consider these lectures in any way a comprehensive view of stochastic optimization; the book of Shapiro et al. [50] provides a more comprehensive picture of stochastic modeling problems and optimization algorithms, and several recent surveys on online learning and online convex optimization provide complementary treatments to ours [24, 48] We briefly outline the coming lectures. The first lecture provides definitions and the convex analytic tools necessary for the development of our algorithms and other ideas, developing separation properties of convex sets as well as other properties of convex functions from basic principles. The second two lectures investigate subgradient methods and their application to certain stochastic optimization problems, demonstrating a number of convergence results. The second lecture focuses on standard subgradient type methods, while the third investigates more advanced material on mirror descent and adaptive methods, which require more care but can yield substantial practical performance benefits. The final lecture investigates optimality guarantees for the various methods we study, demonstrating two standard techniques for proving lower bounds on the ability of any algorithm to solve stochastic optimization problems. The lectures assume some limited familiarity with convex functions and convex optimization problems and their formulation, which will help appreciation of the techniques herein. All that is truly essential is a level of mathematical maturity that includes some real analysis, linear algebra, and introductory probability.