Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs
This work addresses the computational bottleneck of large-scale SDPs in optimization problems like Max-Cut, providing provable convergence guarantees and optimal approximation ratios, though it is incremental as it builds on the existing Burer-Monteiro method.
The paper tackles the scalability issue of solving large semidefinite programs (SDPs) by analyzing a block-coordinate maximization version of the Burer-Monteiro method, proving global sublinear convergence to a stationary point and linear convergence near local maxima under certain conditions, and achieving a near-optimal approximation ratio of 1-O(1/r) with explicit iteration bounds.
Semidefinite programming (SDP) with diagonal constraints arise in many optimization problems, such as Max-Cut, community detection and group synchronization. Although SDPs can be solved to arbitrary precision in polynomial time, generic convex solvers do not scale well with the dimension of the problem. In order to address this issue, Burer and Monteiro proposed to reduce the dimension of the problem by appealing to a low-rank factorization and solve the subsequent non-convex problem instead. In this paper, we present coordinate ascent based methods to solve this non-convex problem with provable convergence guarantees. More specifically, we prove that the block-coordinate maximization algorithm applied to the non-convex Burer-Monteiro method globally converges to a first-order stationary point with a sublinear rate without any assumptions on the problem. We further show that this algorithm converges linearly around a local maximum provided that the objective function exhibits quadratic decay. We establish that this condition generically holds when the rank of the factorization is sufficiently large. Furthermore, incorporating Lanczos method to the block-coordinate maximization, we propose an algorithm that is guaranteed to return a solution that provides $1-O(1/r)$ approximation to the original SDP without any assumptions, where $r$ is the rank of the factorization. This approximation ratio is known to be optimal (up to constants) under the unique games conjecture, and we can explicitly quantify the number of iterations to obtain such a solution.