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

Abstract

We consider minimizing a twice-differentiable, $L$-smooth, and $\mu$-strongly convex objective $\varphi$ over an $n\times n$ positive semidefinite matrix $M⪰0$, under the assumption that the minimizer $M^{\star }$ has low rank $r^{\star }\ll n$. Following the Burer--Monteiro approach, we instead minimize the nonconvex objective $f(X)=\varphi (X{X}^T)$ over a factor matrix $X$ of size $n\times r$. This substantially reduces the number of variables from $O(n^2)$ 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\ge r^{\star }$ is overparameterized by a \emph{constant factor} with respect to the true rank $r^{\star }$, namely as in $r>\frac{1}{4}(L/\mu -1{)}^2{r}^{\star }$, 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\ge 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(n^2)$. Conversely, without rank overparameterization, we prove that such a global guarantee is possible if and only if $\varphi$ is almost perfectly conditioned, with a condition number of $L/\mu <3$. Therefore, we conclude that a small amount of overparameterization can lead to large improvements in theoretical guarantees for the nonconvex Burer--Monteiro factorization.

References in corpus (7)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Low-rank optimization for semidefinite convex problems
• Global Optimality in Low-rank Matrix Optimization
• Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs

Cited by in corpus (2)

• The landscape of deterministic and stochastic optimal control problems: One-shot Optimization versus Dynamic Programming
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms