NYU CS-GY 6763 INET
Algorithmic Machine Learning
and Data Science

(Asynchronous Offering)

Advanced theory course exploring contemporary computational methods that enable machine learning and data science at scale.

Lectures: Students are responsible for watching recorded lectures asychronously. There will be roughly 2.5 hours of material each week.
Professor office hours: Thursday, 7-8:30pm, Zoom link.

Grading: Problem Sets 30%, 3 Oral Exams 50%, Final Project 20%.

Prerequisites: This course is mathematically demanding. Formally, we require previous courses in machine learning, algorithms, and linear algebra. Experience with probability and random variables is necessary. Email Prof. Musco if you have questions about your preparation for the course!

Homework: Homeworks consisting of 1-2 proof based problems (and occasional coding problems) will be assigned weekly, and must be turned in via Gradescope by 11:59pm on Sunday following the week assigned. You can either scan handwritten solutions or upload a compiled PDF if you use Markdown or LaTeX.

Unless otherwise stated, referencing theorems besides those given in class or previous problems is not allowed. All solutions must be proven from scratch. If you are unsure if you can use a fact, ask on Ed.

Problem sets are intended for your own learning! While other students and AI tools are often useful for discussing background material, you will get the most out of the course (and be best prepared for exams) if you put in the time to solve the problems independently. This will require roughly 1-4 hours each week.

To encourage independent work, problem sets will be graded lightly: you will receive a grade of incomplete, ✓-, or ✓+. ✓+ will be given to any submission that provides solutions to every problem, even if there are errors.

Resources: 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. Please use the course webpage to keep up-to-date as new resources are posted. Sometimes slide decks contain slides that I did not have time to cover in lecture. These can be ignored.

Oral Exams: 3 times during the semester I will schedule a 20 minute one-on-one meeting with each student. This meeting can be held either on Zoom or in person at 370 Jay St. During the meeting, you will be given one problem from a previous homework assignment, and asked to walk me through the solution from scratch. I will ask questions about your approach and various steps of the solution.

If you plan to take the exams remotely you must have access to a tablet that you can link to Zoom and use for writing. Let me know ASAP if you do not have access to a tablet or similar device.

Final Project: It's an exciting time for research at the intersection of algorithm design and the data sciences. Most of the topics covered in this course are still the subject of active research. The final project is an opportunity to gain some exposure to that current research.

For the final project, you will choose and read one research paper (I will provide a list of options, or you can suggest one) and you will record a 30 minute lecture (with slides) on the paper. The presentation must cover at least one technical result from the paper, and should roughly mimic the format of a lecture from the class. The best presentation (based on student vote) will be awarded a prize, and I will use the presenter's material in a future lecture for this course.

Week # Topic Reading Homework
The Power of Randomness
1. 1/19 Random variables and concentration, Markov's inequality, applications
  • Watch Lecture 1. Ignore discussion about last years course logistics -- structure is different for in-person offering.
  • Homework 1, due Sunday 1/25.
2. 1/26 Efficient hashing, Chebyshev inequality and applications
3. 2/2 Exponential tail bounds (Chernoff + Bernstein)
4. 2/9 High-dimensional geometry
  • Watch Lecture 4. The recording didn't get cut off properly - only watch to the end of lecture, not the entire 10 hours!
  • Schedule first oral exam, covering Homeworks 1-3. Keep in mind that Homework 3 solutions will not be released until evening of 2/8.
5. 2/16 Johnson-Lindenstrauss lemma and dimensionality reduction.
6. 2/23 High-dimensional nearest neighbor search.
Optimization
7. 3/2 Gradient descent and projected gradient descent
  • Lecture 7 notes (annotated).
  • Teal's lecture notes.

  • If you need to freshen up on linear algebra, now is good time! This quick reference from Stanford mostly covers what we need.
  • Good book on optimization which is freely available online through NYU libraries.
  • Good lecture notes from Aleksander Mądry for more reading on analyzing gradient descent.
  • Moritz Hardt's lecture notes with proofs of gradient descent convergence in all the regimes discussed in class.
  • Sébastien Bubeck's convex optimization book mentioned in class. Fairly technical, but great reference.
8. 3/9 Finish up gradient descent and projected gradient descent.
  • Watch Lecture 8. Only 50 minutes long.
  • Schedule second oral exam, covering Homeworks 5-7.
3/16 NO WORK. SPRING BREAK
9. 3/23 Online and stochastic gradient descent
10. 3/30 Center of gravity method, ellipsoid method
Spectral Methods and Linear Algebra
11. 4/6 Linear Programming and Convex Relaxation, Singular value decomposition
  • Watch Lecture 11.
  • Submit 1 page final project proposal.
12. 4/13 Krylov subspace methods, spectral graph theory, spectral clustering
13. 4/20 Stochastic Block Model, randomized numerical linear algebra, sketching for linear regression, ε-nets
  • Watch Lecture 13.
  • Schedule third oral exam, covering Homeworks 9,10,12.
14. 4/27 Fast JL, Sparse recovery and compressed sensing
15. 5/4 Reading day/exam week
  • Submit final project Friday 5/8.
  • View and vote on other student projects by Wednesday 5/13.