
CS 294128: Algorithms and Uncertainty (Fall, 2016) 
Grading Policy: Students taking the class for credit will be expected to contribute scribe notes for up to two lectures each and to read and present in a group of up to four a recent research paper related to a course topic. Scribes contribute 25%, final presentation 75%.
Textbook: There
will be no standard textbook, and links to various reading material
will be provided during the course.
Tentative
list of topics:
Lectures:
(will
be updated as the course proceeds)
Lecture  Date/Location  Topic  Reading Material 
1  Aug 24, We  Introduction  Scribe notes (pdf ) 
Recommended: Aug 22 26, Algorithms and Uncertainty Boot Camp  
2  Aug 29, Mo  Congestion Minimization,
Randomized Paging 
Fun
survey
on the doubling trick; Lecture notes of
Goemans (Sec 19) Online Congestion Minimization (section 2,2.1 here); Scribe notes (pdf) 
3  Aug 31, We  Online primal dual method and its applications  BuchbinderNaor survey
on PrimalDual Boot camp talk on PrimalDual; Scribe notes (pdf) 
Sep 5, Mo  Academic Holiday  
4  Sep 7, We  Paging via Primal Dual, Dual fitting  Naveen Garg's tutorial
on dualfitting for online algorithms Online rounding for paging (section 4.2 here); Scribe notes (pdf) 
5  Sep 12, Mo  Finish Dual Fitting, Online Prediction, Regret Minimization  Section 1.3 of
Hazan's book
(online prediction, RWM) Scribe notes (pdf) 
6  Sep 14, We  Multiplicative weights,
aapplications to Zero sum games, packing/covering LP with low
width 
AroraHazanKale survey
on multiplicative weights My notes on MWU applications. Scribe notes (pdf) 
7  Sep 19, Mo  Fast approximate max flow  Christiano
et al paper
on approximate maxflow My rough notes. Scribe notes (pdf) 
Recommended: Sep 1923, Workshop on optimization and decisionmaking under uncertainty  
Sep 21, We  Class cancelled due to Workshop  Watch
videos of workshop, with goal of choosing paper for presentation 

8  Sep 26, Mo  Bandits, Experts via Potential functions 
KL divergence potential function proof in AHK survey Auer et al paper on bandits. Scribe notes (pdf) 
9  Sep 28, We  Exp3 Bandit Algorithm, Experts via Primal dual, Metrical Task System, Unfair MTS, connection to shifting experts  Blum Burch paper on UMTS, connection to shifting experts and combining online algorithms using MTS . Primal dual proofs for Experts and UMTS (sec 2.3 and 2.2 here). Scrine notes (pdf) 
10  Oct 3, Mo 
Unfair MTS bound, Work function Algorithm 
Primal dual UMTS proof in sec 2.2 here; Work function based proof for randomized UMTS sec 3.13.3 here. A great reference for basic properties of Work Functions and for proof of the 2n1 bound for MTS, is the Borodin ElYaniv book. Scribe notes (pdf) 
11  Oct 5, We  Guest Lecture by Seeun
Umboh: Online Network Design 
Paper by Umboh on using HSTs for analysis in hindsight. Construction of tree embeddings (Chap. 8.5 of the WilliamsonShmoys textbook). The book also has several applications of HSTs in approximation algorithms. Scribe notes (pdf) 
12  Oct 10, Mo  Online Convex Optimization, Gradient Descent, logarithmic regret, tightness of bounds, FTL  We will roughly cover the material in Chapters 2,3 on Hazan's book (but some proofs will be different). Scribe notes (pdf) 
13  Oct 12, We  Regularization, FTRL, entropic regularization, Bregman Divergences, Mirror Descent view 
Chapter 5 of Hazan's book. ShalevSchwartz notes Scribe notes (pdf) 
14  Oct 17, Mo  Mirror Descent continued. 
Scribe notes (pdf) 
15 
Oct 19, We  Bandit Linear Optimization, optimum regret bound, efficient algorithm using selfcorcordant barriers  Chapter 6 of Hazan's book. Abernethy et al paper. Scribe notes (pdf) 
16  Oct 24, Mo  Finish of BLO proof. Intro to stochastic problems 
Scribe notes (pdf) 
17  Oct 26, We  Policy design via LPs: Stochastic Knapsack;Variants of Secretary Problems  Scribe notes (pdf) BJS paper on Secretaries via LPs; Nagarajan's slides on stochastic Knapsack; DGV paper; Munagala's talk and slides on approximation for stochastic problems 
18  Oct 31, Mo  Guest Lecture by
Thomas Kesselheim: Random Order Problems, matching, packing LPs 
Papers on the matching in random order model (pdf, pdf) Scribe notes (pdf) 
19  Nov 2, We  Guest Lecture by Marco Molinaro: Load balancing simulatenously in worst case and random order 
The paper (pdf) 
20  Nov 7, Mo  Guest Lecture by Matt Weinberg/Thomas Kesselheim: Prophet Inequalities  The prophet inequalities paper (pdf) Slides for the lecture 
21  Nov 9, We  MDPs, Basics, Finite horizon and Discounted rewards, Value iteration, Gittin's index statement  Some notes on MDPs (pdf); Four proofs of Gittin's index theorem (pdf) 
22  Nov 14, Mo 
Guest Lecture by Anupam
Gupta: Stochastic online algorithms, One/Proofs of Gittin's index theorem, Myerson's optimum action design 

Recommended: Nov 1418 Workshop on learning, Algorithm Design and Beyond WorstCase Analysis  
23  Nov 16, We  UCB1 Policy for stochastic Bandits, Markov Paging 
Scribe notes (pdf) Auer, CesaBianchi, Fischer paper on UCB1 for stochastic bandits Lund, Philips, Reingold et al paper on distributional paging. See also sections 5.3.1 and 5.3.2 in Borodin ElYaniv book 
24  Nov 21, Mo  Student presentations  Set covering with our eyes closed. Quico Spaen, Eric Manalac, Michael Dennis 
Nov 23, We  Noninstruction day  
25  Nov 28, Mo 
Student presentations  Fast Convergence of Regularized Learning in Games (pdf). Xingyou Song, Willem Eck, Daniel Shaw 
26  Nov 30, We  Student presentations  Bandit Convex Optimization: Towards tight bounds. Yiqun Chen and Siqi Liu (siqi's notes on missing proofs) 
27  Dec 5, Mo  Student presentations  Online Learning with feedback graphs. Antares Chen, Daniel Li, Nick Sutardja 
28  Dec 7, We  Student presentations  Logarithmic regret for Constant Rebalanced Portfolio. Kiarash Mavandad and Alex khodaverdian 
Template for Scribe Notes: (tex, pdf)
Guidelines: The scribe notes should not be a verbatim copy of
the
lecture. They should add clarification for proofs, and add explanation
for simple exercises and facts mentioned during the class without proof
(feel free to email me if something is unclear while preparing the
notes).
The scribe notes should be submitted within 5 days
after the lecture.