Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization

We consider minimizing a twice-differentiable, L-smooth, and μ-strongly convex objective φ over an n× n positive semidefinite matrix Msucceq0, under the assumption that the minimizer Mstar has low rank rstarll n. Following the Burer--Monteiro approach, we instead minimize the nonconvex objective f(X)=φ(XXT) over a factor matrix X of size n× r. This substantially reduces the number of variables from O(n2) to as few as O(n) and also enforces positive semidefiniteness for free, but at the cost of giving up the convexity of the original problem. In this paper, we prove that if the search rank r≥ rstar is overparameterized by a constant factor with respect to the true rank rstar, namely as in r>frac14(L/μ-1)2rstar, then despite nonconvexity, local optimization is guaranteed to globally converge from any initial point to the global optimum. This significantly improves upon a previous rank overparameterization threshold of r≥ n, which we show is sharp in the absence of smoothness and strong convexity, but would increase the number of variables back up to O(n2). Conversely, without rank overparameterization, we prove that such a global guarantee is possible if and only if φ is almost perfectly conditioned, with a condition number of L/μ<3. Therefore, we conclude that a small amount of overparameterization can lead to large improvements in theoretical guarantees for the nonconvex Burer--Monteiro factorization.