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 426 Mudd
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
Nov 4
In Homework 3 Problem 4, there was a typo in the definition of \(\Pi\). The correct definition is: \(\Pi \in \mathbb{R}^{n \times n}\) is the orthogonal projector to the \((n-1)\)-dimensional subspace of \(\mathbb{R}^n\) comprised of points \(x\in\mathbb{R}^n\) such that \(\sum_{i=1}^n x_i = 0\).
Oct 28
In Homework 3 Problem 1, you should make the lower bound as tight as possible, but it should only depend on the quantities \(p, d, \gamma\). Also, you may assume that \(p > \ln(d)/(2\gamma)\) if you like, but this isn't necessary.
Oct 21
In Homework 2 Problem 5, the "fraction of [the set of] unit vectors" does not need to be so close to one anymore.
Oct 19
I modified Homework 2 Problem 4(b) to remove a confusing part of the problem statement.
Oct 12
In Homework 2 Problem 2, you may assume that \(k \geq 2\) (or any absolute positive constant you like); just state the precise assumption explicitly in your write-up.
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
Dec 7
HW4 due by 5:00 PM.
Dec 10
Final project report due by end-of-day (send to course e-mail).
Date Topics Reading Homework
Sept 9 Course overview
Sept 14 High dimensional Euclidean space Lec 1 of Ball; Sec 2.1-2.4 of BHK
Sept 16 Probability Sec 12.4 of BHK; Notes on probability HW1 (due Fri Oct 2)
Sept 21 Probability; random linear maps Dasgupta and Gupta
Sept 23 Random linear maps; subspace embeddings Notes on J-L lemma
Sept 28 Subspace embeddings; approximate least squares
Sept 30 Structured random linear maps Sec 2 of Ailon and Chazelle
Oct 5 Spectral decomposition; multivariate Gaussians Sec 2.6, 2.9, 12.6 of BHK
Oct 7 Separating Gaussian populations; projection pursuit Sec 2.8 of BHK HW2 (due Fri Oct 23)
Oct 12 PCA and SVD Notes on PCA/SVD
Oct 14 Matrix norms; low-rank matrix approximation Sec 3.4-3.6, 3.9 of BHK
Oct 19 Low-rank matrix approximation; power method Sec 3.7-3.10 of BHK
Oct 21 Power method; sketch-and-solve low rank approximation
Oct 26 Sketch-and-solve low rank approximation; k-center clustering Notes on low rank approximations HW3 (due Mon Nov 9)
Oct 28 k-means clustering; k-means++ Sec 8.1-8.2 of BHK
Nov 2 No lecture
Nov 4 k-means++; divide-and-conquer k-means clustering Aggarwal, Deshpande, and Kannan
Nov 9 k-means + PCA; Euclidean embeddings Sec 8.4 of BHK; notes on k-means
Nov 11 Embeddings into \(\ell_2\) and \(\ell_\infty\) Sec 15.4 of Matoušek
Nov 16 Fréchet embeddings Sec 15.7 of Matoušek
Nov 18 Embedding \(\ell_2^d\) into \(\ell_1^{O(d)}\); approximating sparsest cuts Sec 15.8 of Matoušek; notes on \(\ell_2^d \to \ell_1^{O(d)}\) HW4 (due Mon Dec 7)
Nov 23 Prony's method; uncertainty principle Sec 10.3 (intro), 10.4 of BHK
Nov 25 No lecture
Nov 30 Incoherence; orthogonal matching pursuit Notes on sparsity
Dec 2 Orthogonal matching pursuit; restricted isometry property
Dec 7 No lecture
Dec 9 Basis pursuit Sec 10.3 of BHK; notes on dual cert
Dec 14 Project presentations
Dec 21 Project presentations
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).
[BHK] Avrim Blum, John Hopcroft, and Ravi Kannan, Foundations of Data Science (local copy).
Jiří Matoušek, (Revised) Chapter 15 of Lectures on Discrete Geometry (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.