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

arXiv: https://arxiv.org/abs/1807.04428 · HTML: https://mlsanity.com/paper/1807.04428/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2018.

## Built on by (most cited first, 7 of 7)

- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [SDP Achieves Exact Minimax Optimality in Phase Synchronization](https://mlsanity.com/paper/2101.02347/) (2021)
- [Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs](https://mlsanity.com/paper/2106.08775/) (2021)
- [Efficient semidefinite bounds for multi-label discrete graphical models](https://mlsanity.com/paper/2111.12491/) (2021)
- [Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part II: Theoretical & Computational Results](https://mlsanity.com/paper/2208.03625/) (2022)
- [Inference and Optimization for Engineering and Physical Systems](https://mlsanity.com/paper/2208.13880/) (2022)

## Abstract (arXiv)

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.