When: November 16, 2016, 12:30 PM
Location: 3rd Floor Orchard View Room , Discovery Building
Contact: 608-316-4401, email@example.com
Finding low-rank solutions via the Burer-Monteiro approach, efficiently and provably
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?
Tasos Kyrillidis is a Simons PostDoc member of theWireless Networking & Communications Group (WNCG) at the University of Texas at Austin, working with Constantine Caramanis, Alex Dimakis and Sujay Sanghavi. His research interests include (but are not limited to) convex and non-convex analysis and optimization, data analysis and machine learning. more info
The weekly SILO seminar series is made possible through the generous support of the 3M Company and its Advanced Technology Group
SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group.
SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students. SILO is a lunch-and-listen format, where speakers present interesting math topics while the audience eats lunch.