FYI

Please contact Zhang, Xiangxiong (zhan1966@purdue.edu) by Wed if you are interested in meeting with Richard.

Time: Friday, 11:30 AM - 12:20 PM

Location: LWSN 1106

Title: Rank Overparameterization and Chordal Conversion for Large-Scale Low-rank Optimization

Abstract: Optimization problems over low-rank matrices are ubiquitous in the real-world. In principle, these can be reliably solved to global optimality via convex relaxation, but the computational costs can become prohibitive on a large scale. In practice, it is much more common to optimize over the low-rank matrices directly, as in the Burer-Monteiro approach, but their nonconvexity can cause failure by getting stuck at a spurious local minimum. For safety-critical societal applications, such as the operation and planning of an electricity grid, our inability to reliably achieve global optimality can have significant real-world consequences.

In the first part of this talk, we investigate global optimality guarantees by overparameterizing the low-rank factorization. In the smooth and strongly-convex setting, we rigorously show that, as the rank is increased, spurious local minima become increasingly rare in a step-wise fashion. In other words, rank-2 has fewer spurious local minima than rank-1, and rank-3 has fewer than rank-2, etc. Once the rank exceeds an O(1) threshold, every remaining local minimum is a global minimum, and every saddle point can be escaped.

In the second part of this talk, we revisit convex relaxations. Here, chordal conversion is a heuristic widely used to reduce the per-iteration cost of interior-point methods to as low as linear time, but a theoretical explanation for this speedup was previously unknown. We give a sufficient condition for the speedup, which covers many successful applications of chordal conversion, including the MAX-k-CUT relaxation, the Lovász Theta problem, sensor network localization, polynomial optimization, and the AC optimal power flow relaxation, thus allowing theory to match practical experience.