University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Monday, October 10, 2016

DTC Seminar Series

Finding low-rank solutions via the Burer-Monteiro approach, efficiently and provably


Anastasios Kyrillidis
University of Texas at Austin

Monday, October 10, 2016
4:00 p.m. reception
4:30 p.m. seminar

401/402 Walter Library

Anastasios Kyrillidis

A low rank matrix can be described as the outer product of two tall matrices, where the total number of variables is much smaller. One could exploit this observation in optimization: e.g., consider the minimization of a convex function f over low-rank matrices, where the low-rank set is modeled via such factorization. This is not the first time such a heuristic has been used in practice. The reasons of this choice could be three-fold: (i) it might model better an underlying task (e.g., f may have arisen from a relaxation of a rank constraint in the first place), (ii) it might lead to computational gains, since smaller rank means fewer variables to maintain and optimize, (iii) it leads to statistical “gains”, as it might prevent over-fitting in machine learning or inference problems.

Though, such parameterization comes at a “cost”: the objective is now a bilinear function over the variables, and thus non-convex with respect to the factors. Such cases are known to be much harder to analyze. In this talk, we will discuss and address some of the issues raised by working directly on such parameterization: How does the geometry of the problem change after this transformation? What can we say about global/local minima? Does this parameterization introduce spurious local minima? Does initialization over the factors play a key role, and how we can initialize in practice? Can we claim any convergence guarantees under mild assumptions on the objective f? And if yes, at what rate?


Anastasios Kyrillidis received his PhD in Electrical and Computer Engineering from Ecole Polytechnique Federale de Lausanne in 2014. Currently, he is a Simons Fellowship PostDoc researcher at the WNCG Group at University of Texas at Austin. His research interests include convex/non-convex optimization and analysis, large-scale machine learning, and high-dimensional data analysis.