NYU CSGY 9223I
Algorithmic Machine Learning
and Data Science
Advanced topics course exploring contemporary algorithmic techniques and recent research on computational methods that enable machine learning and data science at scale.
Course Instructor: Professor Christopher Musco
Course Summary
Prerequisites: This course is mathematically rigorous, and is intended for graduate students or advanced undergraduates. I require a previous course in machine learning (for example, CSUY 4563, CSGY 6923, or ECEGY 6143) and a previous course in algorithm design and analysis (for example, CSUY 2413, CSGY 6033, or CSGY 6043). Experience with linear algebra and probability is also necessary. Email the course instructor if you have questions about your preparation for the course! Undergraduates wishing to enroll will be registering for CSUY 3943.
Coursework: One meeting per week. 4 problem sets involving analysis and application of algorithmic methods learned in class, potentially with programming exercises to further explore lecture content (40% of grade). Midterm exam (20% of grade). Final exam (30% of grade). Class participation is the remaining 10% of the grade. Please consult the formal syllabus for more information.
Resources: There is no textbook to purchase. Course material will consist of my written lecture notes, as well as assorted online resources, including papers, notes from other courses, and publicly available surveys. Please refer to the course webpage before and after lectures to keep uptodate as new resources are posted.
Homework:
Homework 1 (due Thursday, Sept. 26th by 11:59pm).
Homework 2 (due Thursday, Oct. 17th by 11:59pm).
Homework 3, UScities.txt (due Monday, Dec. 2nd by 11:59pm).
Homework 4 (due Monday, Dec. 16th by 11:59pm).
Administrative Information
Lectures: Wednesdays 3:205:50pm in Rogers Hall, RGSH 707.
Syllabus: here.
Office hours: Thursdays, 35pm, or by appointment. 370 Jay St., Office 1105 (11th floor).
Reading Group: 10am Tuesdays, 370 Jay St. Room 1114.
Homework: While not required, I encourage students to prepare problem sets in LaTeX or Markdown (with math support.) You can use this template for LaTeX. While there is a learning curve for LaTeX (less for Markdown), it typically saves students lots of time by the end of the semester!
For regular homework problems collaboration is allowed, but solutions and any code must be written independently. Students must list collaborators on their problem sets (for each problem separately). See the syllabus for full details.Optional Reading Group: It's an exciting time for research at the intersection of algorithm design and the data sciences. Many of the ideas covered in this course are still the subject of active research. We currently hold a reading to discuss recent papers on Tuesdays at 10am in Room 1114, 370 Jay St.. If you are interested in participating in the reading group, please email me.
Lecture #  Topic  Required Reading  Optional Reading  

The Power of Randomness  
1. 9/4  Concentration of random variables + applications to hashing and load balancing  Lecture 1 notes. 


2. 9/11  Chernoff bounds + sketching and streaming algorithms 
Lecture 2 notes. (annotated) 

3. 9/18  Sketching, the JohnsonLindenstrauss lemma + applications 
Lecture 3 notes. (annotated) 


4. 9/25  Nearest neighbor search + locality sensitive hashing 
Lecture 4 notes. (annotated) 


FirstOrder Optimization  
5. 10/2  Convexity in machine learning + vanilla, stochastic, and online gradient descent 
Lecture 5 notes. (annotated) 


6. 10/9  Finishing up SGD, smoothness, strong convexity, conditioning. 
Lecture 6 notes. (annotated) 


7. 10/16  Preconditioning, acceleration, randomized coordinate descent, adaptive methods.  Lecture 7 notes. (annotated) 


8. 10/23 
Midterm exam (first half of class) Finishing up coordinate descent, optimization beyond convexity (second half of class) 
Lecture 8 notes. (annotated)  
Spectral Methods and Linear Algebra  
9. 10/30  Singular value decomposition, Power Method, Krylov methods  Lecture 9 notes. (annotated) 


10. 11/6  Finish up Krylov methods, spectral clustering, and spectral graph theory.  Lecture 10 notes. (annotated) 


11. 11/13  Finish spectral graph theory, start randomized linear algebra, sketching for linear regression, εnets arguments  Lecture 11 notes. (annotated) 


12. 11/20  Randomized numerical linear algebra linear, fast JohnsonLindenstrauss transform, sampling.  Lecture 12 notes. (annotated) 


11/27  No Class, Thanksgiving  
Fourier Methods  
13. 12/4  Compressed sensing, the restricted isometry property, basis pursuit, the discrete Fourier transform  Lecture 13 notes. (annotated) 


14. 12/11  High dimensional geometry, maybe some more Fourier methods  Lecture 14 notes. (annotated)  
15. 12/18  Final exam 