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