18.409: Algorithmic Aspects of Machine Learning

Course Information

• Instructor: Ankur Moitra


• Lectures: Tuesday and Thursday 9:30-11:00, 37-212


• Prerequisites: A course in algorithms (6.046/18.410 or equivalent) and probability (6.041/18.440 or equivalent). You will need a strong background in algorithms, probability and linear algebra.


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


• Office Hours: Tuesday and Thursday 11:00-12:00 (meet after class)


• 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.

Course Outline

Nonnegative Matrix Factorization [slides]

• Qualitative Comparisons to SVD
• New Algorithms via Separability
• Applications to Topic Models


D. Lee and S. Seung. Learning the Parts of Objects by Nonnegative Matrix Factorization, Nature 1999.
S. Vavasis. On the Complexity of Nonnegative Matrix Factorization, SIOPT 2009.
S. Arora, R. Ge, R. Kannan and A. Moitra. Computing a Nonnegative Matrix Factorization -- Provably, STOC 2012.
S. Arora, R. Ge and A. Moitra. Learning Topic Models -- Going Beyond SVD, FOCS 2012.
S. Arora et al. A Practical Algorithm for Topic Modeling with Provable Guarantees, ICML 2013.


Discussion: When does well-posedness lead to better algorithms?

M. Balcan, A. Blum and A. Gupta. Clustering under Approximation Stability, JACM 2013.

Tensor Decompositions [slides]

• Tensor Rank, Border Rank and the Rotation Problem
• Jennrich's Algorithm and the Generalized Eigenvalue Problem
• Learning HMMs
• Mixed Membership Models and Community Detection
• Cumulants and Independent Component Analysis


C. Hillar and L. Lim. Most Tensor Problems are NP-hard, JACM 2013.
E. Mossel and S. Roch. Learning Nonsingular Phylogenies and Hidden Markov Models, STOC 2005.
A. Anandkumar, D. Foster, D. Hsu, S. Kakade and Y. Liu A Spectral Algorithm for Latent Dirichlet Allocation, NIPS 2012.
A. Anandkumar, R. Ge, D. Hsu and S. Kakade. A Tensor Spectral Approach to Learning Mixed Membership Community Models, COLT 2013.
N. Goyal, S. Vempala and Y. Xiao. Fourier PCA, STOC 2014.


Discussion: When do algorithms rely (too much) on a distributional model?

U. Feige and J. Kilian. Heuristics for Semirandom Graph Problems, JCSS 2001.

Sparse Coding

• Sparse Recovery, Incoherence and Uncertainty Principles
• Alternating Minimization via Approximate Gradient Descent [slides]
• Sum-of-Squares and Noisy Tensor Decomposition


B. Olshausen and D. Field. Emergence of Simple-cell Receptive Field Properties by Learning a Sparse Code for Natural Images, Nature 1996.
D. Spielman, H. Wang and J. Wright. Exact Recovery of Sparsely-Used Dictionaries, COLT 2012.
S. Arora, R. Ge, T. Ma and A. Moitra. Simple, Efficient and Neural Algorithms for Sparse Coding, Manuscript 2014.
B. Barak, J. Kelner and D. Steurer. Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method, Manuscript 2014.


Discussion: When does belief propagation (provably) work?

S. Geman and D. Geman. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images, Trans. Pattern Analysis and Machine Intelligence 1984.

Learning Mixture Models

• Expectation Maximization
• Clustering in High-Dimensions
• Method of Moments and Systems of Polynomial Equations [slides]


A. Dempster N. Laird and D. Rubin. Maximum Likelihood from Incomplete Data via the EM Algorithm, J. Royal Statistical Society 1977.
S. Dasgupta. Learning Mixtures of Gaussians, FOCS 1999.
S. Arora and R. Kannan. Learning Mixtures of Separated Nonspherical Gaussians, Annals of Applied Probability 2005.
A. Kalai, A. Moitra and G. Valiant. Efficiently Learning Mixtures of Two Gaussians, STOC 2010.
A. Moitra and G. Valiant. Settling the Polynomial Learnability of Mixtures of Gaussians, FOCS 2010.
M. Belkin and K. Sinha. Polynomial Learning of Distribution Families, FOCS 2010.


Discussion: Is nature an adversary? And if not, how can we model and exploit that?

A. Bhaskara, M. Charikar, A. Moitra and A. Vijayaraghavan. Smoothed Analysis of Tensor Decompositions, STOC 2014.

Linear Inverse Problems

• Nuclear Norm, Atomic Norm and Matrix Completion
• Alternating Minimization via Principal Angles
• Tensor Prediction and Random CSPs


E. Candes and B. Recht. Exact Matrix Completion via Convex Optimization, FOCM 2009.
V. Chandrasekaran, P. Parrilo, B. Recht and A. Willsky. The Convex Geometry of Linear Inverse Problems, FOCM 2012.
P. Jain, P. Netrapalli and S. Sanghavi. Low-rank Matrix Completion using Alternating Minimization, STOC 2013.
M. Hardt. Understanding Alternating Minimization for Matrix Completion, FOCS 2014.
B. Barak and A. Moitra. Tensor Prediction, Rademacher Complexity and Random 3-XOR, Manuscript 2015.


Discussion: Do we have enough average-case assumptions?

Q. Berthet and P. Rigollet. Computational Lower Bounds for Sparse PCA, COLT 2013.
V. Chandrasekaran and M. Jordan. Computational and Statistical Tradeoffs via Convex Relaxation, PNAS 2013.