COMS 4772 Advanced Machine Learning (Fall 2015)

Time & venue
Monday and Wednesday 1:10–2:25 PM in 750 CEPSR
Daniel Hsu
Course e-mail (replace #### with course number)
Office hours
Wednesday 2:30–4:30 PM in 702 CEPSR
CA office hours
Angus: Tuesday 10:00–11:00 AM in TA/CA room
Chang: Thursday 2:00–3:00 PM in TA/CA room
Online forum
Sept 27
Daniel's office hours this week will be on Monday (after lecture) instead of Wednesday.
Sept 23
Information about the course project.
June 16
There will be a calibration quiz during the first lecture on which admittance into the course will be based.
At present, registration may only be open to CS students. It will be open to non-CS students closer to the start of the semester.
Upcoming due dates
Oct 2
HW1 due at 5:00 PM.
Oct 14
Project proposal due by end-of-day.
Sept 9
Course overview [slides]
Sept 14
High dimensional Euclidean space
Reading: Chapter 1 of Ball; Sections 2.1-2.4 of Blum-Hopcroft-Kannan.
Sept 16
Reading: Chapter 7 of Ball; Section 12.4 of Blum-Hopcroft-Kannan.
Homework: HW1 (due Fri Oct 2)
Sept 21
Probability; random linear maps
Reading: Notes on probability; Dasgupta and Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss.
Sept 23
Random linear maps; subspace embeddings
Reading: Notes on J-L lemma.
Sept 28
Subspace embeddings; approximate least squares [slides]
Sept 30
Structured random linear maps [slides]
Reading: Section 2 of Ailon and Chazelle, Approximate nearest neighbors and the FJLT
Oct 5
Spectral decomposition; multivariate Gaussians
Reading: Sections 2.6, 2.9, and 12.6 of Blum-Hopcroft-Kannan.
Oct 7
Separating Gaussian populations; PCA
Reading: Section 2.8 of Blum-Hopcroft-Kannan.
Oct 12
Noisy subspace recovery; SVD
Oct 14
Matrix norms; low-rank matrix approximation
Oct 19
Power method
Oct 21
Sketch-and-solve low rank approximation
Oct 26
k-center and k-means clustering
Oct 28
Additional topics (as time permits)
Spectral clustering
Sparse coding
Maximum entropy
Online optimization
Course information and policies
Selected topics in machine learning theory
Machine learning (at the level of COMS W4771/STAT 4400)
Algorithms and data structures (at the level of CSOR W4231)
Linear algebra (e.g., orthogonal subspaces, eigenvalue decompositions)
Multivariable calculus (e.g., convergent sequences, gradients, multiple integrals)
Probability and statistics (e.g., random variables, independence, confidence intervals)
General mathematical maturity
I will assign reading from notes, books, and research papers available on the web.
Keith Ball, An Elementary Introduction to Modern Convex Geometry (local copy).
Avrim Blum, John Hopcroft, and Ravi Kannan, Foundations of Data Science (local copy).
Course work
Homework assignments (50%)
Project and oral presentation (50%)
Homework write-ups
Your write-up must be neatly typeset as a PDF document. You can use LaTeX (see intro, short math guide, wikibook for tips) or any other system that produces typesetting of equal quality and legibility (especially for symbolic expressions).
If you use LaTeX, please use the following template: homework.tex, homework.cls, homework.pdf. If you do not use LaTeX, please use an equivalent template. In particular, ensure that your name, your UNI, and the UNI's of students you discussed the homework with appear on the first page.
Submit your write-up as a single PDF file on Courseworks by 5:00 PM of the specified due date. Late assignments will not be accepted.
Policies on collaboration, outside references, and academic honesty will be strictly enforced.