Provable Alternating Minimization Methods for Low-rank Matrix Estimation Problems

Prateek Jain
Researcher, Microsoft Research Lab, Bangalore, India
Date: June 6, 2013


Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix Challenge.

In the alternating minimization approach, the low-rank target matrix is written in a bi-linear form, i.e. $X = UV^dag$; the algorithm then alternates between finding the best $U$ and the best $V$. Typically, each alternating step in isolation is convex and tractable. However the overall problem becomes non-convex and there has been almost no theoretical understanding of when this approach yields a good result.

In this talk, we present one of the first theoretical analysis of alternating minimization methods for several different low-rank matrix estimation problems, e.g., matrix completion, inductive matrix completion etc. For these problems, celebrated recent results have shown that they become well-posed and tractable once certain (now standard) conditions are imposed on the problem. We show that alternating minimization also succeeds under similar conditions. Moreover, compared to existing results, our paper shows that alternating minimization guarantees faster (in particular, geometric) convergence to the global optima, while allowing a simpler analysis.

This is a joint work with Praneeth Netrapalli, Sujay Sanghavi, Inderjit Dhillon.


Prateek Jain is a researcher at Microsoft Research, Bangalore, India in the Machine Learning and Optimization, and Algorithms and Modeling Research Groups. He completed his Ph.D at University of Texas at Austin, under Inderjit Dhillon. He has won student paper awards at ICML in 2007 and at CVPR in 2008.