| Schedule and handouts
| Related material]
|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)|
In the above list:
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.