Lecture Number | Date | Topic | Readings | Additional Readings |
1 | Jan. 14 | Course organization and logistics Applications of stochastic optimization Warmup: Sensor placement to maximize Entropy | [KG], [Survey] | |
Stochastic Optimization and Approximation Algorithms | ||||
2 | Jan. 19 | Entropy and Kraft's inequality Submodularity and the Greedy Algorithm | [NWF] | [FMV], [BFNS], [BFNS2]: Non-monotone submodular functions [BENW],[MZ]: Distributed algorithms |
3 | Jan. 21 | More examples of submodularity: Influence in social networks, Extreme values | [KKT] | [MR]: Shows influence is submodular |
4 | Jan. 26 | Stochastic set cover: Adaptive vs. non-adaptive algorithms | [MSW] [EHJK] | |
5 |
Jan. 28 |
Adaptive greedy algorithm and duality |
[LPRY] |
[Das]: Adaptive greedy algorithm for active learning [AH], [CPRS]: Adaptive greedy decision tree construction [KKM]: Evaluating monotone CNF/DNF formulae |
6 | Feb. 2 | Prophet Inequalities and Linear Programming: Optimal policies and LP Relaxations | [M-slides] | [KW]: Matroid prophet inequalities |
7 |
Feb. 4 |
LP Rounding and duality |
[DGV]: Stochastic knapsack and adaptivity gaps | |
8 |
Feb. 9 |
Stochastic matchings and LP-based Policies |
[BGLMNR] |
[MSU]: Stochastic scheduling with precedence constraints Auction theory: [AGT, Ch. 9], [BCMX], [CHK], [CHMS], [BILW] |
9 |
Feb. 11 |
Markov Decision Processes Bellman's equation, Value Iteration, Bandit problems |
||
10 |
Feb. 16 |
Greedy revisited: The Gittins Index Theorem |
[Tsi] |
[FW]: Four proofs of the Gittins index theorem [FKKK], [GM]: Crowdsourcing, auctions, and the Gittins index [GM09b], [GKN], [GMS], [GKMR]: Bandits and approximation |
Online Learning and Prediction Problems | ||||
11 | Feb. 18 | Online Prediction and No-regret Learning The Randomized Weighted Majority (RWM) algorithm | [LW], [AGT, Ch. 4] | [Sec], [K], [BIKK],
[KP]: The secretary model |
12 |
Feb. 23 |
No-regret learning via regularization: Hannan's Follow the Regularized Leader (FTRL) Algorithm |
[KV] [Haz, Ch. 5] |
[K-notes], [ABH], [FV]: Blackwell's Approachability |
13 | Feb. 25 | Gradient descent in convex spaces | [Haz, Ch. 2] |
[AGT, Ch. 4], [ACFS]: Adversarial multi-armed bandits [FKM]: Convex multi-armed bandits [ACF], [AG1],[AG2],[AG3],[GM]: Stochastic Multi-armed bandits |
14 | Mar. 1 | No-regret learning via gradient descent Tight lower bounds for regret | [Haz, Ch. 3] | |
15 |
Mar. 3 |
Applications:
Stochastic gradient descent Agnostic PAC learning |
[Haz, Ch. 9] | [CCP], [KSH]: Sample-Average Approximation (SAA) |
16 | Mar. 8 | Zero sum games via no-regret learning | [Haz, Ch. 7] | [BC-B]: Survey of bandit algorithms [BSS]: Truthful mechanisms for keyword auctions [Times]: The human mind also trades off exploration and exploitation! |
17 | Mar. 10 | Solving Linear Programs via No-regret learning | [AHK] | [LN], [You], [AK], [BGM], [WMMR]: Parallel implementations [AD]: Online LPs with stochastic inputs [BGM]: Algorithm for Optimal Bayesian Auctions PROJECT PROPOSALS DUE |
SPRING BREAK | ||||
Online Algorithms | ||||
18 |
Mar. 22 |
Online Data Compression Dynamic Huffman coding, Move-to-front, Lempel-Ziv |
[Albers] | |
19 | Mar. 24 | Online Algorithms with Adversarial Inputs: Ski Rental, List update, Potential functions | [Albers] | [MMAW], [FL], [CGMP]: Switch scheduling [IKM1, IKM2]: General models for scheduling |
20 |
Mar. 29 |
Deterministic and Randomized algorithms for Paging |
[FKLMSY] | |
21 | Mar. 31 | Yao's theorem and lower bounds Online load balancing | ||
22 | Apr. 5 | Online Steiner trees and the Greedy algorithm Online matchings and Dual Fitting | [IW] [Tim-notes] | Note the nice lower bound construction in [IW] [GGLS]: Stochastic Steiner trees |
23 |
Apr. 7 |
Randomized matching and optimal dual fitting |
[Tim-notes] |
|
24 | Apr. 12 | Primal-dual algorithms: Ski Rental, Budgeted allocations | [BN] | |
25 | Apr. 14 | Online set cover | [BN] | |
26 | Apr. 19 | PROJECT PRESENTATIONS |