This is an advanced theory course that examines contemporary computational methods that enable machine learning and data science at scale. We will cover topics including randomized algorithms, concentration inequalities, dimensionality reduction, convex optimization, spectral methods, and compressed sensing. The course emphasizes rigorous mathematical analysis and algorithmic design.
Office: 370 Jay St., Brooklyn, NY • Office 1104
Instructor Office Hours: By appointment over zoom. Monday's 10 am to 11 am (please email at least a day in advance to schedule)
Lectures: Tuesdays 2:00pm–4:30pm, 2 MetroTech Center, Room 911.
Problem-Solving Session: Fridays 12:00pm–1:30pm, location TBA. Led by the teaching assistants. Weekly problem-solving and Q&A.
TA Office Hours: Wednesdays 1:00pm–2:30pm, location TBA.
This course is mathematically rigorous and intended for graduate students and advanced undergraduates. Students should have prior coursework in machine learning, a strong background in algorithms, a solid understanding of linear algebra, experience with probability theory and random variables, and comfort with writing and understanding rigorous mathematical proofs.
Problem Sets: 40%, Midterm Exam: 25%, Final Project OR Final Exam: 25%, Participation: 10%.
There will be four problem sets throughout the semester. All assignments must be submitted via Gradescope by 11:59pm ET. Due dates will be announced.
Formatting: Students have to write solutions in LaTeX or Markdown.
Grading Policy: Each problem set will be graded as follows. For each problem you solve completely, clearly indicate it is a complete solution. After submission, you will be asked to explain one randomly selected problem from among your completely solved problems on a whiteboard. You may reference your written homework during the explanation. The grade you receive on the explanation will be applied to all of your completely solved problems. For problems you do not solve completely, you may write "I don't know" to receive 25% credit on that problem. Problems that are incomplete without writing "I don't know" receive 0% credit. There is no partial credit for incomplete solutions.
Example: If a problem set has 5 problems and you completely solve 3 of them, one of those 3 will be randomly selected for you to explain. If you receive 90% on your explanation, you receive 90% on all 3 completely solved problems. For the remaining 2 problems, you can write "I don't know" on each to receive 25% credit, or 0% if you leave them incomplete. Your final score would be: (90% + 90% + 90% + 25% + 25%) / 5 = 64%.
Midterm Exam: Tuesday, October 27, 2026 (first half of class). Final Exam: Tuesday, December 8, 2026, 2:00pm–4:30pm (regular classroom). Students who choose to complete a final project may opt out of the final exam.
Project Proposal Due: Friday, October 30, 2026. Guidelines will be posted here. Example projects: here.
There is no textbook to purchase. Course material will consist of my slides, lecture notes scribed by Teal Witter, as well as assorted online resources, including papers, notes from other courses, and publicly available surveys.
The following schedule is tentative and subject to change. Topics and resources will be updated throughout the semester.
| Week | Date | Topic | Resources |
|---|---|---|---|
| 1 | 9/8 | Random variables, concentration, Markov's inequality [notes] | Probability review, Alternative resource, Mark-and-recapture paper |
| 2 | 9/15 | Efficient hashing, Chebyshev inequality [notes] [notes] | Princeton universality notes, Fingerprinting notes, Flajolet-Durand paper |
| 3 | 9/22 | Exponential tail bounds (Chernoff, Bernstein) | Terry Tao notes, Power of two choices |
| 4 | 9/29 | High-dimensional geometry | Foundations of Data Science (Ch. 2) |
| 5 | 10/6 | Johnson-Lindenstrauss lemma, dimensionality reduction | Princeton JL notes, Anupam Gupta's notes |
| 6 | 10/13 | High-dimensional nearest neighbor search, locality sensitive hashing | Stanford LSH notes, Indyk-Motwani analysis |
| 7 | 10/20 | Gradient descent, projected gradient descent | Stanford linear algebra, Mądry's notes, Moritz Hardt's notes, Sébastien Bubeck's book |
| 8 | 10/27 | Midterm | — |
| 9 | 11/3 | Online and stochastic gradient descent | Elad Hazan's book |
| 10 | 11/10 | Center of gravity, ellipsoid method, LP relaxation | Princeton ellipsoid method, Interior point method, Nisheeth Vishnoi's book |
| 11 | 11/17 | Singular value decomposition, Krylov subspace methods | Princeton power method, Foundations of Data Science (Ch. 3), Stanford notes |
| — | 11/24 | THANKSGIVING BREAK (no class) | — |
| 12 | 12/1 | Spectral graph theory, spectral clustering, Krylov methods, and stochastic block model | Princeton SBM notes, Karate Club paper, Stanford spectral graph, Princeton sketching notes, ε-nets context |
| 13 | 12/8 | FINAL EXAM (2:00pm) | Final exam preparation materials |
Note: Lecture notes, slides, and additional resources will be posted on Brightspace before each lecture.
All students are expected to follow NYU's academic integrity policies. Violations will be taken seriously and may result in failure of the course and/or disciplinary action by the university.
