Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs

Semidefinite programming (SDP) with diagonal constraints arise in many\noptimization problems, such as Max-Cut, community detection and group\nsynchronization. Although SDPs can be solved to arbitrary precision in\npolynomial time, generic convex solvers do not scale well with the dimension of\nthe problem. In order to address this issue, Burer and Monteiro proposed to\nreduce the dimension of the problem by appealing to a low-rank factorization\nand solve the subsequent non-convex problem instead. In this paper, we present\ncoordinate ascent based methods to solve this non-convex problem with provable\nconvergence guarantees. More specifically, we prove that the block-coordinate\nmaximization algorithm applied to the non-convex Burer-Monteiro method globally\nconverges to a first-order stationary point with a sublinear rate without any\nassumptions on the problem. We further show that this algorithm converges\nlinearly around a local maximum provided that the objective function exhibits\nquadratic decay. We establish that this condition generically holds when the\nrank of the factorization is sufficiently large. Furthermore, incorporating\nLanczos method to the block-coordinate maximization, we propose an algorithm\nthat is guaranteed to return a solution that provides $1-O(1/r)$ approximation\nto the original SDP without any assumptions, where $r$ is the rank of the\nfactorization. This approximation ratio is known to be optimal (up to\nconstants) under the unique games conjecture, and we can explicitly quantify\nthe number of iterations to obtain such a solution.\n