CSE 522: Algorithms and Uncertainty (Spring 2017)

[Course description | Schedule and handouts | Related material]

Important Announcements

Schedule and Handouts

Date Topic Resources
Mar 27 Intro to PAC learning (notes) Avrim Blum's slides, [KV, chaps 1-2], [SSS, chaps 2-4], [MRT, chap 2], video - Andrew Ng
Mar 31 Sample complexity via growth functions (notes) Avrim Blum's slides and notes, [KV, chap 3], [SSS, chaps 2-6], [MRT, chap 3]
Apr 3 VC dimension (notes) [KV, chap 3], [SSS, chaps 2-6], [MRT, chap 3]
Apr 7 Rademacher complexity (notes) Avrim Blum's notes, [SSS, chap 26], [MRT, chap 3]
Apr 10 Intro online learning (notes) [AHK survey], [Hazan, Ch 1]
Apr 14 Applications of experts (notes) Bobby Kleinberg lecture notes
Apr 17 + 21 Applications, cont. + Follow the perturbed leader (notes) FTPL by Kalai and Vempala
Apr 21 + 24 Intro to online convex optimization (notes) [SSS survey, Ch 2], [Hazan, Ch 5]; Sebastien Bubeck notes
May 1 Follow the regularized leader (notes) See above, and Bubeck's book; Useful facts about relative entropy
May 5 Equivalence to online mirror descent, applications; (notes) See above; other notes on mirror descent here and here
May 8 Application to approx Caratheodory (notes); Intro linear bandits (notes) Tight bounds for Approx Caratheodory Thm
May 12 Multi-armed bandits (notes) [SSS survey, Ch 4]; MAB book draft by Slivkins; Bubeck and Cesa-Bianchi; Bubeck lecture notes part 1 and part 2
May 15 Linear bandits see above
May 19 Linear and contextual bandits (notes) see above
May 22 Stochastic multi-armed bandits Slivkins, chaps 2-3; Shipra Agrawal notes #1 and #2
May 26 Markovian MAB, Gittins index Richard Weber lecture notes, chap 7, Shipra Agrawal notes #1, #2, #3
June 2 Student presentations Linear coupling: An ultimate unification of gradient and mirror descent

Towards minimax policies for online linear optimization with bandit feedback

June 5 Sebastien Bubeck guest lecture Mirror descent and self-concordant barriers for the linear bandit problem
June 7 Student presentations Katyusha: The first direct acceleration of stochastic gradient methods

Analysis of Thompson Sampling for multi-armed bandits

Kernel-based methods for bandit convex optimization

Equality of opportunity in supervised learning

In the above list:

Course Details

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:

Course evaluation: 2-4 homeworks and a small project.

Background expected: Mathematical maturity, basics of probability and undergraduate level algorithms.


Videos and courses


  1. Foundations of machine learning by Mohri, Rostamizadeh and Talwalkar.
  2. Understanding Machine learning: from theory to algorithms, by Shalev-Schwartz and Ben-David
  3. Online convex optimization by Elad Hazan
  4. Convex optimization: algorithms and complexity by Sebastien Bubeck
  5. Prediction, learning and games by Cesa-Bianchi and Lugosi
  6. Regret analysis of stochastic and nonstochastic multi-armed bandit problems by Bubeck and Cesa-Bianchi
  7. The design of competitive online algorithms via a primal-dual approach by Buchbinder and Naor