Fast low-rank estimation by projected gradient descent: Statistical and algorithmic guarantees

Martin Wainwright (University Berkeley)
Wednesday, October 28, 2015 - 10:00am
WIAS, Erhard-Schmidt-Saal, Mohrenstraße 39, 10117 Berlin

Optimization problems with rank constraints arise in many applications, including matrix regression, structured PCA, matrix completion and matrix decomposition problems. An attractive heuristic for solving such problems is to factorize the low-rank matrix, and to run projected gradient descent on the nonconvex problem in the lower dimensional factorized space. We provide a general set of conditions under which projected gradient descent, when given a suitable initialization, converges geometrically to a statistically useful solution. Our results are applicable even when the initial solution is outside any region of local convexity, and even when the problem is globally concave. Based on joint work with Yudong Chen, Cornell University