B1441
Title: Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
Authors: Nuri Vanli - MIT (United States) [presenting]
Murat A Erdogdu - University of Toronto (Canada)
Pablo Parrilo - MIT (United States)
Asuman Ozdaglar - MIT (United States)
Abstract: Semidefinite programming (SDP) with diagonal constraints arise in many 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, it has been previously proposed to reduce the dimension of the problem by appealing to a low-rank factorization, and solve the subsequent non-convex problem instead. We present coordinate ascent based methods to solve this non-convex problem with provable convergence guarantees. In particular, we prove that the block-coordinate maximization algorithm applied to the non-convex Burer-Monteiro approach globally converges to a first-order stationary point with a sublinear rate. We also show that the block-coordinate maximization algorithm is locally linearly convergent to a local maximum under local weak strong concavity assumption. We establish that this assumption generically holds when the rank of the factorization is sufficiently large. Furthermore, we propose an algorithm based on the block-coordinate maximization and Lanczos methods that is guaranteed to return a solution that provide $1-O(1/r)$ approximation to the original SDP, where $r$ is the rank of the factorization, and we quantify the number of iterations to obtain such a solution. This approximation ratio is known to be optimal under the assumption of the unique games conjecture.
