Improved global guarantees for the nonconvex Burer-Monteiro factorization via rank overparameterization

• 成果类型: Article
• 署名作者: Zhang, Richard Y.
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02160-6
• 发表日期: 2025
• 页码: 1009-1038
• 关键词: matrix factorization; local minima; optimization; CONVERGENCE; algorithm

摘要

We consider minimizing a twice-differentiable, L-smooth, and mu -strongly convex objective 4 over an n x n positive semidefinite matrix M 0, under the assumption that the minimizer M* has low rank r* << n . Following the Burer-Monteiro approach, we instead minimize the nonconvex objective f (X) = 4 (XXT) over a factor matrix X of size nxr. 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 >= r* is overparameterized by a constant factor with respect to the true rank r * , namely as in r > 1/4 (L/mu - 1)2r*, 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 backup to O(n(2)). Conversely, without rank overparameterization, we prove that such a global guarantee is possible if and only if 4 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.