Lecture Number | Date | Topic | Readings | Additional Readings |
1 | Aug. 24 | Course organization and logistics Applications of stochastic optimization Warmup: Sensor placement and submodularity | [KG] | |
Known Distributions: Stochastic Optimization and Adaptivity | ||||
2 | Aug. 26 | Submodular function maximization: Greedy algorithm Graphical models, inference, and belief propagation. | [KG], [KMN] | [FMV]: Approximating non-monotone submodular functions [Svi]: 1-1/e approximation with general costs; similar to [KMN] |
3 | Aug. 31 | Influence in social networks | [KKT] | [MR]: Shows influence is submodular in general |
4 | Sep. 2 | Continuous Query Processing: Pipelined filters: Greedy non-adaptive algorithm Correlations and the conditional greedy algorithm | [MBMW] | [FLT], [CFK]: Also show 4-approximation for min-sum set cover [DGV]: Again note the use of a fixed ordering schedule [MSU]: Stochastic scheduling with precedence constraints |
5 | Sep. 7 | Shared conjunctive queries with expensive predicates: Adaptivity gaps, LP bounds, and semi-adaptive algorithms | [MSW] | Note the large gap between adaptive and fixed ordering schemes [EHJK]: A simpler version of the same problem |
6 | Sep. 9 | Greedy set cover and Harmonic hypergraph cover The adaptive greedy and harmonic algorithms Accounting via dual pricing and conditioning | [LPRY] | [Das]: Adaptive greedy algorithm for active learning [AH], [CPRS]: Adaptive greedy decision tree construction [KKM]: Evaluating monotone CNF/DNF formulae |
Learning Distributions: Multi-armed Bandit Problems | ||||
7 | Sep. 14 | Keyword auctions and the multi-armed bandit problem Beta priors, Bayesian updates, Explore-exploit tradeoffs | [PO], [GM09] | [GP], [BSS]: Truthful mechanisms for keyword auctions [Times]: The human mind also trades off exploration and exploitation! |
8 | Sep. 16 | MDP formulation, decision policies, and dynamic programming | [SB, Ch. 2, 3, 4] | |
9 | Sep. 21 | Uniform discounting: The Gittins index policy | [Tsi] | [FW]: Four different proofs of the Gittins index theorem |
10 | Sep. 23 | Finite horizon problems, relaxations, and duality | [GM09b], [GKN] | [GMS]: "Restless bandit" problem with similar solution idea [SU]: Brownian restless bandits with a regret measure of performance |
11 | Sep. 28 | Removing the prior: The stochastic multi-armed bandit problem Regret measure and the UCB1 policy | [ACF] | PROJECT PROPOSALS DUE |
12 | Sep. 30 | Tight lower bound for regret | [ACFS] | |
FALL BREAK | ||||
13 | Oct. 7 | Robust regret and the adversarial bandit problem Onine prediction: Weighted majority algorithm | [LW] | |
14 | Oct. 12 | Relation between bandit problems and online prediction | [AGT], Chapter 4 | |
15 | Oct. 14 | Online Prediction: Follow the Perturbed Leader | [KV] | Essentially Hannan's 1954 algorithm. |
16 | Oct. 19 | Prediction over convex spaces: Gradient descent | [Zin] | Can you use [Zin] to solve the problem considered in [KV]? |
17 | Oct. 21 | Low Variance Unbiased Estimators Barycentric spanners, Gradient estimators | [FKM], [AK] | [AHR]: The introduction unifies FPL and gradient descent as regularization Also a nice description of why variance plays a role in regret. |
Distribution-oblivious: Online Algorithms | ||||
18 | Oct. 26 | List access and Paging | [Karp1] | |
19 | Oct. 28 | Randomized algorithms for paging Lower bounds for randomized paging | [Karp2] | |
20 | Nov. 2 | Online Steiner trees | [IW] | Note the nice lower bound construction in [IW] |
21 | Nov. 4 | Sampling from the future: Online Steiner trees with prior information | [GGLS] | [CCP], [GPRS]: Multi-stage stochastic optimization [FMMM]: Online adword matching |
22 | Nov. 9 | Yao's Theorem and the MinMax Theorem | [AHK] | |
23 | Nov. 11 | Primal-dual algorithm: Ski Rental, Budgeted allocations | [BN] | [BLMNO]: Application to wireless power allocation |
24 | Nov. 16 | Online Set Cover | [BN] | |
25 | Nov. 18 | Online Auctions and Secretary Problems: Random order model and aspiration strategies | [Sec], [K] | [BIKK]: Survey of known results for the secretary problem [KP]: Secretary problem for graphs |
26 | Nov. 23 | PROJECT PRESENTATIONS |