CS 294-128: Algorithms and Uncertainty (Fall, 2016)



Instructor:  Nikhil Bansal
Email:  n.bansal@tue.nl

Time/Place: Mondays and Wednesdays, 5:30-7:00, Room 310, Soda Hall   (starts Aug 24) 

Course Summary: In many settings such as stock-market prediction, job scheduling, routing etc., the input arrives over time and an algorithm must make its current decisions without a complete knowledge of the future. The goal of the course is to look at various algorithmic approaches that have been developed for dealing with problems involving uncertainty. These approaches are quite diverse and span several different research areas such as (i) competitive anlaysis of algorithms, (ii) regret minimization and online convex optimization in machine learning (iii) stochastic approaches such as Markov decision processes, Bayesian methods and so on. 

In the course we will look at both classical results and several latest developments in these areas. A special  focus will be on recent unifying techniques based on methods from optimization and linear and convex programming duality. Another goal of the course will be to understand the strengths and weakness of the various approaches. To this end, we will also consider models beyond traditional worst case analysis such as smoothed analysis, semi-random models and other structured inputs.

This course will be self-contained, but run in parallel to the Simons Institute semester on Algorithms and Uncertainty. One goal of the class will be to provide graduate students with sufficient background to participate fully in the Simons Institute semester. There will be occasional guest speakers from the Simons Institute program, presenting recent research results related to course materials.

Prerequisites:  We will assume that students have taken an advanced undergraduate or graduate level algorithms course, and are familar with concepts such as  LP relaxations and their use in approximation algorithms,  linear programming duality, Chernoff Bounds, basic algorithms such as for max-flow and shortest paths. Otherwise, the class will be self-contained and new concepts will be introduced as needed.

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:

Competitive Analysis of Algorithms:
Basic problems: Paging, Load-balancing/Scheduling, k-server, dynamic optimality, network design.
Role of randomization, Yao's Minimax Lemma
Primal Dual Methods
Dual-Fitting
Work Function Methods
Convex Programming and Fenchel Duality
Price of Anarchy, Potential Games

Online Learning and Regret Minimization:
Prediction with experts, Multiplicate-Weight Updates
Applications of MWU to solving LPs quickly, faster max-flow etc.
Online Convex optimization
Follow the leader, Regularization
Gradient Descent  and Mirror Descent
Bandit Optimization
Combining Regret and Competitive Analysis

Stochastic Settings:
Markov Decision Processes, Index Policies, Gittins Index
Prophet Inequalities
Random Order Problems
Decision trees, adaptive and non-adaptive strategies
Markov Paging

Beyond Worst Case Analysis:
Smoothed Analysis
Planted and Semi-random models
Clustering and partitioning under stability


Some related Courses on the web:

Optimization and decision-making under uncertainty by Kamesh Munagala
Online Algorithms by Yair Bartal
Decision Analysis by Elad Hazan (mostly on online learning)
Topics in Stochastic Optimization by Ashish Goel
Approximation and Online Algorithms by Avrim Blum


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 1-9)
Online Congestion Minimization (section 2,2.1 here); Scribe notes (pdf)
3 Aug 31, We Online primal dual method and its applications Buchbinder-Naor survey on Primal-Dual
Boot camp talk on Primal-Dual; Scribe notes  (pdf)
Sep 5, Mo Academic Holiday
4 Sep 7, We Paging via Primal Dual, Dual fitting Naveen Garg's tutorial on dual-fitting 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
 		Arora-Hazan-Kale 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 max-flow
My rough notes. Scribe notes (pdf)
Recommended: Sep 19-23, Workshop on optimization and decision-making 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.1-3.3 here. A great reference for basic properties of Work Functions and for proof of the 2n-1 bound for MTS,  is the Borodin El-Yaniv 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 Williamson-Shmoys 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. Shalev-Schwartz 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 self-corcordant 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 14-18 Workshop on learning, Algorithm Design and Beyond Worst-Case Analysis 
23 Nov 16, We UCB1 Policy for stochastic Bandits, Markov Paging
 Scribe notes (pdf)
Auer, Cesa-Bianchi, 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 El-Yaniv book
24 Nov 21, Mo Student presentations Set covering with our eyes closed. Quico Spaen, Eric Manalac, Michael Dennis
Nov 23, We Non-instruction 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.

Possible Presentation Topics

Guidelines: Presentations can be done  in groups of up to 4 students. It  should be a white-board presentation (no slides).     
The lecture should be extremely clear with the goal of explaining and clarifying the main conceptual ideas.
Think about intructive examples or special cases to discuss that explain the key issue underlying the problem.
Once you really understand a proof, you can often present in a much cleaner than what might be in the paper.

The group should make an appointment with me at least a week in advance of the presentation date for clarifications of technical material, feedback on the presentation and any other input.

A list of potential topics is below. If you like to pick your own topic, you should discuss it with me before Oct 10.
Projects will be assigned in a first-come-first served manner. You should mail me your top  3 choices by Oct 15.
The projects will be assigned by Oct 16.

Topics/Papers:

1.  The k-server problem and proof that WFA is 2k-1 competitive (based on simpler proof in the paper below).
     Elias Koutsoupias; Weak Adversaries for the k-server problem, FOCS 1999. Paper here.
     Background on k-server and work functions, can be found in the book by Borodin and El-Yaniv, or various lecture notes on the internet.

2.  Moran Feldman, Ola Svensson, Rico Zenklusen: Online Contention Resolution Schemes, SODA 2016. Paper here
     Background on (offline) contention resolution schemes and related material see here.

3. Thompson Sampling.  This is a widely used heuristic in practice for multi-armed bandit problems.
    Shipra Agrawal, Navin Goyal:  Further optimal regret bounds for thompson sampling. Paper here
    More background material can be found in references here

4. Set Covering with our eyes closed.  Grandoni et al FOCS 2008. Paper here

5. This paper shows T^{1/2} regret for smooth and strongly convex functions.
    Bandit Convex Optimization: Towards tight bounds.  Hazan and Levy, NIPS 2014. Paper here
    Plus, a lower bound for these functions in:  On the complexity of bandit and derivative-free stochastic  convex optimizatoion.  Paper here

6. Markov Paging.  A polynomial time strategy for page requests arriving from a Markov Process.
    Section 5.3.2 in Borodin El-Yaniv book.
    Original Paper: IP over connection-oriented networks and distributional paging, Lund, C.; Phillips, S.; Reingold, N., FOCS 1994/JCSS'99.

7. Faster Packing Covering. Improving the dependence on \epsilon for packing problems.
    Nearly-linear time positive LP solver with faster covergence rate.  Allen-Zhu and Orecchia. STOC 2015.  Paper here
    (Notes for lectures 3 and 4 here might be useful)

8. Swap regret and connection to correlated equilibria.
    Survey chapter by Blum and Mansour.

9. Online Learning with Feedback Graphs by  Alon, Cesa-Bianchi, Dekel, Koren. Paper here