18.409: Algorithmic Aspects of Machine Learning

Spring 2015

Modern machine learning systems are often built on top of algorithms that do not have provable guarantees, and it is the subject of debate when and why they work. In this class, we will focus on designing algorithms whose performance we can rigorously analyze for fundamental machine learning problems. We will cover topics such as: nonnegative matrix factorization, tensor decomposition, sparse coding, learning mixture models, matrix completion and inference in graphical models. Almost all of these problems are computationally hard in the worst-case and so developing an algorithmic theory is about (1) choosing the right models in which to study these problems and (2) developing the appropriate mathematical tools (often from probability, geometry or algebra) in order to rigorously analyze existing heuristics, or to design fundamentally new algorithms.

Announcement: The course is now complete. Thanks for contributing to a great semester! Stay tuned for a new version of the monograph that will be based on new topics we covered this time, as well as several changes in the exposition itself.

Announcement: The Final Project is posted here and due on May 14th, by email.

Announcement: PSET 2 is posted here and due April 23rd, after class.

Announcement: PSET 1 is posted here and due March 5th, after class.

Course Information

Course Outline

Here is a tentative outline for the course: