18.S996: Algorithmic Aspects of Machine Learning

Fall 2013



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: spectral clustering, learning mixture models, matrix completion, tensor decomposition, nonnegative matrix factorization, sparse dictionary learning, inference in graphical models and deep learning. 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 analyze the performance of an algorithm.

Announcement 1: Info about Final Projects is available here. Please send me your final report by December 14th. Here is a sample final project by Yufei Zhao

Announcement 2: Here are the lecture notes for the course!

Course Information

Course Outline

Here is a tentative outline for the course:

References