CSE 522: Algorithms and Uncertainty (Spring 2017)
| Schedule and handouts
| Related material]
Instructors: Nikhil Devanur and Anna Karlin
Time: Mondays and Fridays
in CSE 403, 11:00am -- 12:20pm
Course content: Inspired by the recent and current special semesters at the Simons Institute for Theoretical Computer Science, 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, 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
Course evaluation: 2-4 homeworks and a presentation on a paper related to the course content.
Background expected: Mathematical maturity, basics of probability and undergraduate level algorithms.
Videos and courses
- Foundations of machine learning by Mohri, Rostamizadeh and Talwalkar.
Machine learning: from theory to algorithms, by Shalev-Schwartz and Ben-David
convex optimization by Elad Hazan
- Convex optimization: algorithms and
complexity by Sebastien Bubeck
- Prediction, learning and games by Cesa-Bianchi and Lugosi
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems by Bubeck and Cesa-Bianchi
- The design of competitive online algorithms via a primal-dual approach by Buchbinder and Naor