CSE 522: Algorithms and Uncertainty
In this course, we will explore some of the key themes and approaches to handling uncertainty in algorithm
design and analysis, with particular emphasis on basics of learning theory and online learning.
Topics to be covered will be selected from:
* Basics of learning theory: PAC learning, sample complexity, uniform convergence, VC theory, Rademacher complexity
* Online learning: MWU, Follow the perturbed leader, applications
* Online convex optimization: gradient descent, regularization, FTRL, Bregman divergence, online mirror descent
* Multi-armed bandits: stochastic and adversarial cases, linear bandits, Gittins index.
* Competitive analysis of online algorithms: online primal-dual, online stochastic packing
* Secretary problems and prophet inequalities
* Models intermediate between worst-case and average-case analysis.
Course evaluation: 2-4 homeworks and a presentation on a paper related to the course content.
Background expected: Mathematical maturity, probability and undergraduate level algorithms (e.g. 421)