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
E-mails: {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)
  • N. Alon and J. Spencer, The Probabilistic Method, chapter on second moment method.

  • Please read sections 4.1.1–4.1.3 in the notes to complete the discussion on Gaussian distributions.
  • Homework 0 assigned.
9/11 Cramer-Chernoff bounding method, subgaussian and subgamma random variables
[same notes as last week]
  • N. Alon and J. Spencer, The Probabilistic Method, appendix on large deviations.

  • Please read section 3.4 and the rest of section 4 in the notes (from last week) to complete the discussion on subgamma random variables and prepare for next week's lecture.
  • Homework 1 assigned.
Random linear embeddings
9/18 Random vectors, Johnson-Lindenstrauss 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 k-means clustering
[same notes as last week]

10/30 Matrix tail inequalities, approximate matrix multiplication
[notes]
11/6 Power iteration, orthogonal iteration, randomized low-rank approximation
[notes] (updated 11/15)
Clustering models
11/13 Eigenvalues of Laplacian matrices
[notes] (updated 11/27)
  • D. Spielman, Spectral graph theory, Combinatorial Scientific Computing, Chapman and Hall/CRC Press, 2011.

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