COMS 4772 Advanced Machine Learning (Fall 2013)
Time & venue: Wednesday 4:10–6:00 PM in 545 Mudd.
Instructor: Daniel Hsu
Office hours: Friday 9:30–11:25 AM (or by appointment)
TA office hours: Monday 4–5 PM (Karl Stratos) and Tuesday 5–6 PM (Joan Cao), in the Mudd TA room
Emails: {djhsu@cs.,stratos@cs.,zc2235@}<university domain>
Course information  Homework assignments  Final project
Date  Topics and notes  References and comments 

Basic probabilistic techniques  
9/4 
Gaussian distributions, Markov's and Chebyshev's inequalities
[notes] (updated 9/25) 

9/11 
CramerChernoff bounding method, subgaussian and subgamma random variables
[same notes as last week] 

Random linear embeddings  
9/18 
Random vectors, JohnsonLindenstrauss lemma
[notes] (updated 9/19) 

9/25 
Constructions for fast JL embeddings
[notes] (updated 9/25) 

10/2 
Linear subspaces, covering numbers
[notes] 

Spectral analysis  
10/9 
Projection pursuit,
covariance matrices
[notes] 

10/16 
Principal component analysis
[notes] (updated 10/24) 

10/23 
Applications of PCA to kmeans clustering
[same notes as last week] 

10/30 
Matrix tail inequalities, approximate matrix multiplication
[notes] 

11/6 
Power iteration, orthogonal iteration, randomized lowrank approximation
[notes] (updated 11/15) 

Clustering models  
11/13 
Eigenvalues of Laplacian matrices
[notes] (updated 11/27) 

11/20 
Cheeger's inequality and graph partitioning
[same notes as last week] 

11/27 
Planted partition models
[notes] 

12/4 
Mixture models
[notes] 

Some additional references
 Dasgupta, Linear algebra review
 Trefethen and Bau, Numerical linear algebra
 Trevisan, Notes on discrete probability
 Grinstead and Snell, Introduction to probability