CSE 291: Learning Theory I

TuTh 3.30-5 in Center 203

Sanjoy Dasgupta
Office hours Mon 1-2 in EBU3B 4138

This course covers a broad range of learning theory, with one major omission --- online learning, which is the subject of a separate course taught by Yoav Freund.

Supplementary reading material:
Kearns and Vazirani, An introduction to computational learning theory
Devroye, Gyorfi, Lugosi, A probabilistic theory of pattern recognition

Part I: Supervised learning

Lecture 1. The Laplace functional [9/21, 9/26, 9/28]
Probability review, concentration of Lipschitz functions of bounded independent random variables
Homework 1, due 10/3

Lecture 2. The PAC model of learning [10/3, 10/5, 10/10]
Proper and agnostic learning, canonical function classes, Occam-style bounds
Homework 2, due 10/17

Lecture 3. Uniform convergence [10/10, 10/12, 10/17, 10/19]
VC dimension, canonical examples, Rademacher averages
Homework 3, due 11/14

Lecture 4. Mistake-bounded learning [10/24, 10/26]
Halving, perceptron, winnow, conversions to PAC

Lecture 5. Strong and weak learning [10/31, 11/2, 11/7]
Boosting algorithms, margin-based bounds

Lecture 6. Fourier methods [11/14, 11/16, 11/21]
Linear-algebra approach to learning, decision trees, circuits

Lecture 7. Models of noise [11/28, 11/30]
Random misclassification, statistical queries, malicious noise

Part II: Unsupervised, semisupervised, and active learning

Lecture 8. Gaussian concentration
Johnson-Lindenstrauss lemma
Lecture 9. Embedding finite metrics into L2
Notions of distortion, Bourgain's embedding, probabilistic embeddings
Lecture 10. Algorithms for nearest neighbor search
Locality-sensitive hashing, cover trees
Lecture 11. Spectral projection
Low-rank approximation, application to mixture models
Lecture 12. Approximation algorithms for clustering
k-center, k-median, k-means, correlation clustering
Lecture 13. Semisupervised learning
Lecture 14. Active learning