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

Murat A Erdogdu, Asuman E. Ozdaglar, Pablo A. Parrilo, Nuri Denizcan VanliMath. Program 2018 · DOI · OpenReview

TL;DR

This paper tackles the challenge of solving large-scale Semidefinite Programs (SDPs) by introducing a novel algorithm based on block-coordinate maximization applied to a non-convex reformulation. The authors provide the first theoretical guarantees for this approach, proving both global sublinear and local linear convergence rates, and develop a second-order method that achieves near-optimal approximation ratios for SDPs.

What Problem Does This Paper Address?

Semidefinite Programs (SDPs) are powerful tools for solving complex combinatorial optimization problems, but standard convex optimization solvers struggle with their large scale. The Burer-Monteiro approach offers a way to overcome this by reformulating the SDP into a lower-dimensional, non-convex problem using a low-rank factorization. However, the convergence properties of algorithms applied to this non-convex problem were not well-understood. This paper aims to provide rigorous theoretical guarantees for a specific algorithm, block-coordinate maximization (BCM), applied to this non-convex Burer-Monteiro formulation, and to develop an improved algorithm that achieves strong approximation guarantees.

Methods

The core of the paper revolves around analyzing and extending the Block-Coordinate Maximization (BCM) algorithm for the non-convex Burer-Monteiro SDP formulation.

  • BCM Algorithm: This is a coordinate ascent-style method where, at each step, only a single row (or block of rows) of the low-rank factor matrix is updated to maximize the objective function, while keeping other rows fixed. The paper analyzes different coordinate selection rules (uniform, importance, and greedy).
  • Convergence Analysis: The authors provide theoretical proofs for:
  • Global Sublinear Convergence: BCM converges to a first-order stationary point with a sublinear rate, regardless of the problem's structure.
  • Local Linear Convergence: Under a "quadratic decay" condition (meaning the objective function decreases quadratically near a local maximum), BCM exhibits linear convergence. They also show this condition often holds generically.
  • BCM2 Algorithm: To achieve better approximation guarantees, the authors augment BCM with a second-order oracle, specifically incorporating the Lanczos method. This allows the algorithm to leverage Hessian information to find approximate second-order stationary points.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments with synthetically generated matrices.

Key Insights and Ideas

  • BCM is Theoretically Sound: The paper provides the first rigorous convergence guarantees for BCM on the non-convex Burer-Monteiro SDP. This validates its empirical success and provides a theoretical foundation for its use.
  • Quadratic Decay is Key for Linear Convergence: The authors demonstrate that a "quadratic decay" condition is crucial for BCM to achieve linear convergence near local optima. Importantly, they show this condition is often met generically, especially when the rank of the factorization is sufficiently large.
  • Second-Order Information for Near-Optimal Approximation: By combining BCM with a second-order oracle (via Lanczos), they develop an algorithm (BCM2) that can achieve approximation ratios close to the theoretical optimum for SDPs, specifically $1 - \mathcal{O}(1/r)$, where $r$ is the rank of the factorization. This is a significant result, as this approximation ratio is conjectured to be the best possible.
  • BCM's Practical Advantage: The numerical experiments highlight BCM's superior performance compared to other state-of-the-art methods (RGA and RTR) in terms of speed, especially for large-scale problems.

Key Results

  • Global Convergence: BCM achieves a global sublinear convergence rate of $\mathcal{O}(1/\epsilon)$ to a first-order stationary point.
  • Local Convergence: BCM exhibits linear convergence near a local maximum under the quadratic decay condition.
  • Generic Quadratic Decay: The quadratic decay condition holds generically for local maxima when the factorization rank $r \ge \sqrt{2n}$.
  • BCM2 Approximation: The BCM2 algorithm (BCM + second-order oracle) guarantees a $1 - \mathcal{O}(1/r)$ approximation to the optimal SDP solution. This approximation ratio is optimal under the unique games conjecture.
  • Empirical Performance: Numerical experiments show BCM significantly outperforms Riemannian Gradient Ascent (RGA) and Riemannian Trust Region (RTR) methods in terms of speed, solving large SDPs in seconds where others take minutes or fail to complete.

Limitations and Future Work

  • Diagonal Constraints: The theoretical results and algorithms presented are primarily for SDPs with diagonal constraints. The authors suggest that extending these results to more generic SDP problems would be of interest.
  • Initialization Sensitivity: While BCM has global convergence guarantees, like many non-convex optimization methods, its local convergence rate depends on being initialized sufficiently close to a local maximum.
  • Second-Order Oracle: The BCM2 algorithm relies on a second-order oracle. While the paper shows how to implement this using the Lanczos method, the efficiency and practical implementation of this oracle can still be a factor.

The paper concludes by suggesting that studying the block-coordinate maximization approach for more generic problems (beyond diagonal constraints) is a promising direction for future research.

Summary updated

Abstract

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.
BibTeX
@article{erdogdu2018convergence,
  author = {Murat A Erdogdu and Asuman E. Ozdaglar and Pablo A. Parrilo and Nuri Denizcan Vanli},
  title = {{Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs}},
  journal = {Math. Program.},
  year = {2018},
  doi = {10.1007/s10107-021-01686-3},
}
Figure