The Drift Method: from Stochastic Networks to Machine Learning

This course is an exploration of the drift method: a family of simple, yet surprisingly powerful, meta-algorithms that in each step the greedily and incrementally minimizes a certain potential function. Manifested in different forms, MaxWeight, c-mu rule, EXP3, policy gradient, to name a few, the drift method powers some of the most popular algorithmic paradigms in queueing networks, optimization and machine learning. Using the drift method as a unifying theme, we will explore major developments in these areas to understand what features can explain the method¿s effectiveness, how we can rigorously evaluate its performance, and what are some of the emerging research topics. We will develop rigorous probabilistic and optimization methodologies for answering these questions, such as Lyapunov stability theory, state-space collapse, and weak convergence. Applications to be covered include dynamic control and scheduling in queueing networks, delay and stability analysis of stochastic networks, stochastic approximation, and online/supervised/reinforcement learning. The course will be primarily taught in a lecture format, along with some guest lectures and student project presentations. Objective: For students to acquire fundamental methodologies that can be applied to pursuing research topics in theoretical or applied areas. Target Audience: The course is intended for PhD students in Business, Engineering and Economics. The students should have a good background in probability and stochastic processes (e.g., Stat 310A / MS&E 321). Most topics will be self-contained.