E0 215: Algorithms under Uncertainty, Fall 2022

Course Description

Motivations and Objectives: : In many domains the input arrives over time and an algorithm is required to make its current decision without knowing the future in its entirety. This requirement---of online decision making with uncertain inputs---naturally appears in various real-world settings, such as ad allocations and job scheduling. This course will cover multiple algorithmic approaches that have been developed for dealing with such algorithmic problems involving uncertainty. These techniques are quite diverse and span several research areas including (i) competitive analysis of algorithms, (ii) regret minimization and online convex optimization in theoretical machine learning, (iii) stochastic approaches such as multi-armed bandits and prophet inequalities.

In this course, we address both classical works and several recent developments in these fields. Another goal of the course will be to understand the strengths and weakness (lower bounds) of various design methodologies.

Course Methodology: The course will have a significant project component. This will engage the students to explore active research fronts in the above-mentioned topics.

Intended audience: Graduate students in computer science and mathematics with theoretical interests. Interested undergraduate students with very strong mathematical skills.

Prerequisites: E0 225 (Design and Analysis of Algorithms) is a soft prerequisite. Alternatively, a foundational understanding of algorithms and sufficient mathematical maturity will suffice.

Grading: 50% HW, 20% Projects, 30% Final.

Tentative Topics

The following topics will likely be covered in the course:

Online Algorithms: Competitive ratio and types of adversaries. Paging, Ski-rental, power of randomization, lower bound using Yao's lemma, Doubling trick, online set cover, primal-dual schema, online matching, online bin packing, Random Order Arrival, IID model.
Streaming Algorithms: Finding frequent elements, Misra-Gries algorithm. Finding moments of data stream. Finding frequent items by sketching: Count-Min Sketch. AMS Estimator. Communication Complexity and connection with Streaming Algorithms.
Online Learning and Bandits: Multiplicative-weights algorithm, Follow the leader, Regularization, Online convex optimization, Gradient Descent and Mirror Descent. Upper confidence bound algorithm and median elimination. Combining competitive ratio and regret.
Stochastic Settings: Markov Decision Processes, Index Policies, Gittins Index. Prophet Inequalities.

Lecture Schedule

Refresher

Probability Refresher:
Scribe notes from Toolkit, Handwritten notes.

LP Refresher:
Scribe Notes 1, Scribe Notes 2
Handwritten Notes 1, Handwritten Notes 2

LP Videos
Intro to LP, LP Duality, Max Flow Min Cut, Algorithms for LP, Extreme Point Solutions.
Deterministic Rounding, Randomized Rounding, Primal-Dual Schema, Dual Fitting.

Week 1 & 2

Basics, Paging/Caching.
Basics, Competitive Ratio.
Optimal Offline Paging,
Deterministic Algorithms: Marking, Lower bounds.
Randomized Algorithms: Adversary models, Mark algorithm

Lower bounds for Randomized Algorithms:
Yao's Lemma.

Sources:
Borodin-ElYaniv Book: 3.4, 3.5, 4.1.1, 4.2, 4.3, 4.4.

Lecture Notes:
Notes for weeks 1 and 2 by Prof. Arindam.

Week 3

Doubling trick:
Lecture Notes by Prof. Arindam.
Online bidding and cow-path problem [From Chrobak-Kenyon survey.]

Online Set Cover
Lecture Notes by Prof. Arindam.
Potential-function based Algorithm.
Pitt's Algorithm.
[From Online Set cover (by Alon et al.) and Lecture notes by Anupam Gupta]

Week 4

Ski-rental.
Ski-rental: deterministic and randomized algorithms.
Yao's minimax lemma and lower bounds for randomized algorithms for ski-rental.

Handwritten notes on Ski Rental by Prof. Arindam.

Primal-Dual Analysis:
Primal-Dual Algorithm for Ski-rental and Set Cover.

Sources:
Primal-Dual Survey by Buchbinder-Naor: Ch3 and 4.

Week 5

Online Matching.
Ranking, Economic-Bases Analysis.
Ranking Analysis: Birnbaum-Mathieu
Economic Based analysis: SOSA'21 paper by Eden et al.
Notes on Online Bipartite Matching and Economic Analysis of Ranking by Prof. Arindam.

Week 6

Online Bin Packing.
Next-Fit, Harmonic Algorithm, Weight Functions.
Notes on Bin Packing by Prof. Arindam.

Random Order Arrival: Secretary Problem
Random Order Models: a survey by Gupta-Singla Survey

IID Model

Notes on Secretary Problem by Prof. Arindam.

Week 7

Streaming Algorithms.
Notes on Streaming Algorithms by Prof. Arindam.

Basics, Model, Finding Frequent Elements:
Bayer-Moore Majority Voting Algo, Misra Gries Algorithms. AC Lec 0, 1.

Finding Moments of Data Stream:
Flajolet-Martin Algorithm for F0, Hash Functions, k-wise independence. AC Lec 2.
Finding frequent Items by Sketching: Count-Min Sketch. AC Lec 5. MPI 3.4.

AC= Amit Chakrabarty's Lecture Notes

Week 8-14

Online Learning+MDPs.
Online Convex optimization
Follow the leader, Regularization
Gradient Descent and Mirror Descent
Experts (MWU, EXP3, FTRL,...)
Bandits (UCB, Median elimination)

Important Dates:

First day of class: 04 August, 2022.
Course Registration Deadline: 18 August, 2022.
Course drop deadline without mention: 17 October, 2022.
Course drop deadline with mention: 15 Novermber, 2022.
Final: 20 Nov 2022 to 09 Dec 2022 (exact date will be finalized later).

Scribe Templates

Assignments

Project Topics

Potential Functions in Scheduling:
A Tutorial on Amortized Local Competitiveness in Online Scheduling (By Im-Moseley-Pruhs)
Potential-Function Proofs for Gradient Methods:
Survey by Bansal-Gupta
Online Set Cover Algorithms via Projections (Mirror Descent)
k-Servers with a Smile by Buchbinder et al.
Random Order Set Cover is as Easy as Offline by Gupta et al.
Dynamic Matching:
Survey by Henzinger et al.
Deterministic Rounding of Dynamic Fractional Matchings by Bhattacharya and Kiss
Dynamic Set Cover:
Online and Dynamic Algorithms for Set Cover by Gupta et al.
Fully Dynamic Set Cover via Hypergraph Maximal Matching by Assadi-Solomon
Online Bin Packing and Weight Function Methods:
Upper bound by Balogh et al.
Lower bound by Balogh et al.
Dynamic Geometric Algorithms:
Geometric Set Cover by Chan et al.
Geometric Set Cover and Hitting Set by Agarwal et al.
Geometric Independent Sets by Henzinger et al.
Streaming Algorithms for Graph Coloring:
Brooks's theorem in graph streams by Assadi et al.
Deterministic graph coloring in the streaming model by Assadi et al.
Semi-streaming Algorithms for Matching:
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space by Assadi et al.
A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching by Assadi et al.
Online Network Design:
Tight Bounds for Online Weighted Tree Augmentation by Naor et al.
Online Network Design Algorithms via Hierarchical Decompositions by Umboh
Online vector balancing:
Online vector balancing and geometric discrepancy by Bansal et al.
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing by Bansal et al.
Online discrepancy:
Online Discrepancy with Recourse for Vectors and Graphs by Gupta et al.
Online Discrepancy Minimization for Stochastic Arrivals by Bansal et al.
Online stochastic matching:
Online stochastic matching, poisson arrivals, and the natural linear program by Huang et al.
The power of multiple choices in online stochastic matching by Huang et al.
Chasing nested bodies:
Chasing Convex Bodies with Linear Competitive Ratio by Gupta et al.
Bandits with Knapsacks:
Online Learning with Vector Costs and Bandits with Knapsacks by Kesselheim et al.
Adversarial Bandits with Knapsacks by Immorlica et al.
Bandits with Knapsacks beyond the Worst-Case by Sankararaman et al.
The k-server problem and WFA:
Weak Adversaries for the k-server problem by Elias Koutsoupias in FOCS '99
Background material in Online Computation and Competitive Analysis: by Allan Borodin, and Ran El-Yaniv.
Background on k-server and work functions can also be found on variouslecture notes on the internet
Contention resolution schemes:
Online Contention Resolution Schemes by Moran Feldman, Ola Svensson and Rico Zenklusen in SODA '16
Background material on offline contention resolution schemes and related material
Thompson Sampling:
Further optimal regret bounds for thompson sampling by Shipra Agrawal and Navin Goyal
More background material can be found on links here
Markov Paging:
A polynomial time strategy for page requests arriving from a Markov Process.
Section 5.3.2 in Online Computation and Competitive Analysis: by Allan Borodin, and Ran El-Yaniv.
IP over connection-oriented networks and distributional paging by Lund, C.; Phillips, S.; Reingold, N. at FOCS'94
Faster Packing Covering:
Improving the dependence on \epsilon for packing problems.
Nearly-linear time positive LP solver with faster covergence rate by Allen-Zhu and Orecchia at STOC'15
Swap regret and connection to correlated equilibria:
Survey Chapter: Learning, Regret minimization, and Equilibria by Blum and Mansour
Online Learning with Feedback Graphs:
Online Learning with Feedback Graphs: Beyond Bandits by Alon, Cesa-Bianchi, Dekel, Koren. at COLT'15
Approximate Carath?odory Problem:
Revisiting the Approximate Caratheodory Problem via the Frank-Wolfe Algorithm by CW Combettes, S Pokutta at Mathematical Programming, '21
Frank-Wolfe Methods For Optimization And Machine Learning: by Cyrille W. Combettes.

References

We will be teaching materials from multiple books/sources. Some of them are the following.

Books:
Since the course topics span several fields, we will be teaching material from multiple books/sources.

Allan Borodin, and Ran El-Yaniv. Online Computation and Competitive Analysis: Cambridge University Press, 2005.
Blum, Hopcroft, and Kannan. Foundations of Data Science.
Muthukrishnan. Data streams: Algorithms and applications. Now Publishers Inc, 2005.
Lattimore and Szepesvari. Bandit Algorithms. Cambridge University Press, 2020.
Hazan. Introduction to Online Convex Optimization. Now Publishers Inc, 2016.
Roughgarden (Ed.). Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2021.

Surveys/book chapters:

Bookchaper by Susanne Albers from 2003.
Primal Dual Survey by Buchbinder and Naor(See the videos and slides).

Recent Lecture Notes: (with other related topics such as stochastic optimization, online learning, online convex optimization)

CMU Advanced Algorithms, Fall 2018 (by Anupam Gupta) - one of the recent courses.
Algorithms and Uncertainty (by Nikhil Bansal at Berkeley'16).
Competitive analysis via convex optimization (UW'18 by Bubeck and Lee).
Decision Making at Scale (by Kamesh Munagala at Duke'18).
On-line and Approximation algorithms (by Yossi Azar at TAU'18).
Online Algorithms (by Shahin Kamali at U. Manitoba '18).
Optimization and decision-making under uncertainty (by Kamesh Munagala).
Online Algorithm (by Yair Bartal).
Decision Analysis (by Elad Hazan, mostly on online learning).
Topics in Stochastic Optimization (by Ashish Goel).

Other special topics:

Online matching and ad allocation survey (by Aranyak Mehta).
Approximation and Online Algorithms for Multidimensional Bin Packing. (by Arindam Khan '17). Link to presentation here.
Online Scheduling Survey (by Susanne Albers).
Online Vehicle Routing Problems (Survey by Jaillet & Wagner).
A Technique to Obtain Hardness Results for Randomized Online Algorithms - A Survey (by Bockenhauer et al.).
Competitive analysis of paging (by S Irani'98).
Online Algorithms with Advice: A Survey. (by Boyar et al.).

Older Lecture notes/courses:

15-854 Approximation and Online Algorithms ( by Avrim Blum at CMU'00).
CSCI 2950-w - Online Algorithms (by Claire Mathieu at Brown'09).
CS 294-1 Home Page (by Yair Bartal at HUJI'97) and CS 294-1 (by Yair Bartal at HUJI'05).
Online Algorithms (by Vanessa Petrausch at U Paderborn).
Competitive Analysis via Regularization (by Buchbinder et al. '14).
CS369 lecture notes (by Serge Plotkin at Stanford'13).

Workshops:

Algorithms and Uncertainty: Simons Institute for the Theory of Computing.
Online Algorithms and Learning Workshop from 17 Nov 2014 through 21 Nov 2014.
Workshop on modern algorithms.