Frontiers In Online Optimization
Instructor: Yash Kanoria (Uris 404, ykanoria@columbia.edu)
Office hours: 2-3:30 pm on Wednesday in Uris 404. Sign up here
Course Assistant: Judy Gan (yg2587@columbia.edu)
Instructor: Yash Kanoria (Uris 404, ykanoria@columbia.edu)
Office hours: 2-3:30 pm on Wednesday in Uris 404. Sign up here
Course Assistant: Judy Gan (yg2587@columbia.edu)
Session 1 (9/8): Mirror Descent and Online Convex Optimization. Scribe note; Video
References:
Chapter 4, 5, 6 from "First Order Methods In Optimization" by Amir Beck
Chapter 1,5 from "Online Convex Optimization" by Elad Hazan
Session 2 (9/15): Online Convex Optimization II. Scribe note; Video
References:
Chapter 1,5 from "Online Convex Optimization" by Elad Hazan
Session 3 (9/22): Adaptive Gradient algorithms and Online Control. Scribe note; Video
References:
Chap 1, 3, 5, 6 from "Online and Non-stochastic Control" by Elad Hazan
HSZ17 Learning Linear Dynamical Systems via Spectral Filtering
HLS+18 Spectral Filtering for General Linear Dynamical Systems
Session 4 (9/29): Online and Non-stochastic Control. Scribe note; Video
References:
Chap 4, 7, 8 from "Online and Non-stochastic Control" by Elad Hazan
Online Control with Adversarial Disturbances by Agarwal, Bullins, Hazan, Kakade, and Singh
The Nonstochastic Control Problem by Hazan, Kakade, and Singh
Improper Learning for Non-stochastic Control by Simchowitz, Singh, and Hazan
Session 5 (10/6): Connections to Mirror Backpressure. Scribe note; Video
References:
Blind Dynamic Resource Allocation in Closed Networks via Mirror Backpressure by Y. Kanoria and Pengyu Qian
Session 6 (10/13): Blackwell approachability, MaxWeight from Blackwell approachability. Scribe note; Video
References:
Session 7 (10/20): Online algorithms with machine learning advice. Scribe note; Video
Presenters: Rachitesh Kumar, Aditya Bhaskara
References:
Online Learning with Predictable Sequences by Rakhlin, and Sridharan
Online Learning with Imperfect Hints by Bhaskara, Cutkosky, Kumar, and Purohit
Session 8 (11/3): Bandits with Knapsacks. Slides; Scribe; Video
Presenters: Alex Slivkins, Arpit Agrawal.
References:
Bandits with Knapsacks by Badanidiyuru, Kleinberg, and Slivkins
Adversarial Bandits with Knapsacks by Immorlica, Sankararaman, Schapire, and Slivkins
Online Learning with Vector Costs and Bandits with Knapsacks by Kesselheim, and Singla
Session 9 (11/10): Optimization-friendly generic mechanisms & Compensated coupling. Scribe; Video
Presenters: Mark Braverman, Yilun Chen.
References:
Optimization-friendly generic mechanisms without money by Mark Braverman
The bayesian prophet: A low-regret framework for online decision making by Vera and Banerjee
Online allocation and pricing: Constant regret via bellman inequalities by Vera, Banerjee and Gurvich
Session 10 (11/17): Compensated coupling II. Scribe; Video
Presenter: Yilun Chen.
References:
The bayesian prophet: A low-regret framework for online decision making by Vera and Banerjee
Online allocation and pricing: Constant regret via bellman inequalities by Vera, Banerjee and Gurvich
Session 11 (12/1): Stein's method. Notes; Video
Presenter: Siva Theja Maguluri.
References:
Fundamentals of Stein’s method by Nathan Ross
A short survey of Stein’s method by Sourav Chatterjee