# CS 294: Algorithmic Aspects of Machine Learning

### Fall 2024

In this graduate class, we will explore various facets of the question: **What can theory contribute to our understanding of modern machine learning? **

Our perspective will be algorithmic. We will introduce ubiquitous models like mixture models, graphical models, random graphs, linear dynamical systems, ReLU networks, Markov decision processes, diffusion models and large language models (if the instructor can figure out what to say about them!) and cover the state-of-the-art in terms of what is known in the way of algorithms and lower bounds. Through these examples, we will see powerful algorithmic methodologies in action like the method of moments, tensor decompositions, spectral methods and semi-definite programming.

In many ways, the theory of machine learning is also about how to frame problems so that we capture essential challenges in machine learning at the right level of abstraction. We will emphasize themes like beyond worst-case analysis, stability, robustness, identifiability and computational vs. statistical tradeoffs that serve as our guide for where and how to look for algorithmically interesting problems.

**Announcement:** Orr set up a Google groups for the class
here which we can use for announcements

**Announcement:** Amaan set up a discord server for the class
here which you can use for discussion, setting up study groups, etc.

**Announcement:** PSET 1 is posted
here and due September 27th via gradescope
## Course Information

**Instructor: Ankur Moitra**

**Lectures:** Tuesdays and Thursdays 12:30-2, Wheeler 102

**Prerequisites:** A course in algorithms (CS 270 or equivalent) and a strong background in probability and linear algebra.

**Textbook:** We will use this **monograph**. Lecture notes and/or presentations covering new topics will be provided.

**Office Hours: ** Thursday 2-3 in Simons Institute 2nd Floor

**Assessment:** Students will be expected to solve a handful of problem sets, and complete a research-oriented final project. This could be either a survey, or original research; students will be encouraged to find connections between the course material and their own research interests.

## Syllabus and Schedule

The syllabus and schedule of topics will vary based on student interests. Previous versions of the class taught at MIT can be found here. This section will be updated throughout the semester.
## Instructor Notes

- Latent Semantic Indexing and Nonnegative Matrix Factorization [pdf]
- Intermediate Polytope Problem and the Anchorwords Algorithm [pdf]
- Applications to Topic Models [pdf]
- Interlude: Clustering and Approximation Stability [pdf]
- Tensors: The Rotation Problem and Computational Hardness [pdf]
- Tensors II: Jennrich's Algorithm [pdf]
- Tensors III: Applications to Phylogenetic Reconstruction, HMMs, GMMs, Community Detection [pdf]