| Week | Topic | Due |
|---|---|---|
| January 22 | Overview. Review of key concepts from machine learning and statistics. Canonical examples of large data problems; associated technical and ethical concerns (genomics, recommender systems, advertising). | Nothing. |
| January 29 | Convex sets and functions. Standard classes of convex optimization problems. Specific examples and an overview of associated computational complexity. Exponential lower bounds on generic optimization problems. | Read: Boyd Chapter 4. Read: These notes and slides. |
| February 5 | Large scale convex optimization problems and relation to our canonical settings. Stochastic methods (eg. SGD) and a proof of convergence. A sketching teaser. | Read: Woodruff introduction. Problem Set 1. (tex, cls, soln) |
| February 12 | Large scale least squares problems via sketching and theoretical comparison to other solution algorithms. Proof of correctness for Gaussian sketches, and why that doesn't result in fast algorithms. Fast JL Transforms, CountSketch Matrices, and applications. | Read: Woodruff Chapter 2. Problem Set 2. (tex, soln) |
| February 19 | Finishing up sketching. Proof of correctness of Fast Johnson-Lindenstrauss Transform. Review of Lagrange Duality. Duality gaps and Slater's Condition. Duals of common optimization problems. | Read: Boyd Chapter 5. Read: Great Example Solution Problem Set 3. (tex) |
| February 26 | More Lagrange duality theory. Duality-driven algorithms for optimization (mirror descent) and applications (optimization on simplex). Non-convex optimization problems and prevalence of use. | Read: this paper Read: this paper. Problem Set 4. (tex) |
| March 5 | Optimization algorithms in the non-convex setting (Adam, saddle point aversion, ...) and recent guarantees. Provably solveable non-convex problems. Applications to recommender systems. | Read: this paper. Read: this paper. Work on midterm project. |
| March 12 | High capacity convex alternatives to deep models (Gaussian Processes and kernel methods) and associated comptuational drawbacks. Preconditioned kernel machine solvers and trace estimation to relieve these difficulties. | Read: this paper. Read: notes on GPs. Read: notes on Rec. Systems. Midterm project. |
| March 19 (no class) | Enjoy Spring Break! | |
| March 26 | Review of concentration. Some key results from non-asymptotic random matrix theory. Associated random graphs (stochastic block model) and and some theory. | Read: Vershynin Chapter 3. Problem Set 5. (tex, very small, due Friday) |
| April 2 | Clustering. Simple algorithms for NP-hard problems: k-means, and k-means++. Spectral clustering algorithms for guaranteed clustering of graphs. | Read: this paper. Read: this paper. Problem Set 6. (tex) Literature Review. |
| April 9 | Matrix completion redux. SVD and provable recovery of observed sparse, low rank matrices. Computational considerations and faster iterative algorithms. | Read: Vershynin Chapter 6. Problem Set 7. (tex) |
| April 16 | More streaming algorithms; the turnstile model. Counting large numbers with very little memory (Morris' algorithm). Lower bounds for number storage. Sketching vector norms in the turnstile model. | Read: these slides. Work on final project! |
| April 23 | Approximate matrix multiplication in the turnstile model via sketching. Associated lower bound. | Problem Set 8. (tex) |
| April 30 | Work on final project. | |
| May 8 | Final Project Presentations. Note this is on Wednesday from 5-8pm. | Final projects. (no extensions) |