Department of Computer Science & Engineering

Description:Upper-level UG / PG course on Stochastic Optimization with applications to statistical learning and other modern topics of relevance to computer science, machine learning, electrical engineering, and related disciplines. The course will cover the fundamentals of stochastic optimization with (sub)- gradient descent and sample average approximation algorithms. The early part of the course will provide an overview of the mathematical tools needed for analysis. A strong foundation in random variables is needed as preparation.

CourseContent: I. Preliminaries (6 lectures) Convergence of random sequences (in probability, wp1, weak, and Lp), martingale inequalities, Borel-Cantelli and Robbins-Siegmund lemmas. II. Stochastic Optimization (SO): Problem Statement and Motivating Settings (4 lectures) SO problem flavours relevant to CS, e.g., regression, maximum likelihood estimation, classification, stochastic programming and simulation optimization formulations. III. Stochastic Gradient Methods (12 lectures) Key results in stochastic (sub)-gradient methods including the behavior of fixed-step gradient methods in the smooth and nonsmooth contexts, sufficient conditions for convergence, convergence rate and complexity calculations, central-limit theorems (CLT), confidence bounds, 2nd-order variations and handling constraints. IV Continuous Time Approximation (6 lectures) Continuous-time approximation, convergence rate calculation, and CLTs. V. Sample-Average Approximation (8 lectures) General philosophy, sufficient conditions for convergence, convergence rate and complexity calculations, CLTs, and modern variations such as Retrospective Approximation. VI. SO in Infinite-Dimensions (6 lectures) Example problems from statistics and PDEs. introduction to thinking in non-Euclidean spaces, e.g., function spaces, basic philosophies and algorithmic frameworks for solution.

TextBooks:1) Shapiro, D. Dentcheva, and A. Ruszczynski, Lectures on Stochastic Programming, Modeling and Theory, MPS- SIAM Series on Optimization, 2009 2) S. van de Geer, Empiricial Processes in M-Estimation, Cambridge Series in Statistics and Probabilistic Mathematics, 2000

ReferenceBooks:1) R. J. Serfling, Approximation Theorems of Mathematical Statistics, Wiley Series in Probability and Statistics, 1980 2) P. Billingsley, Probability and Measure, Wiley, 2012 3) S. Asmussen and P. W. Glynn, Stochastic Simulation, Algorithms and Analysis, Springer, 2007 4) M. J. Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint, Cambridge Series in Statistics and Probabilistic Mathematics, 2019

Prerequisite:MA2040, CS6015 or equivalent