** Time **

TuTh 3.30-5 in Center 203

** Instructor: **

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 **