# Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 61 references that are in the map.
- First posted on arXiv 16 Jun 2021.

## Builds on (most cited first, 21 of 21)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017)
- [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015)
- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (2016)
- [A Lyapunov Analysis of Momentum Methods in Optimization](https://mlsanity.com/paper/1611.02635/) (2016)
- [On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings](https://mlsanity.com/paper/2002.12414/) (2020)
- [Scheduled Restart Momentum for Accelerated Stochastic Gradient Descent](https://mlsanity.com/paper/2002.10583/) (2020)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form](https://mlsanity.com/paper/1803.00186/) (2018)
- [Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality](https://mlsanity.com/paper/1703.08729/) (2017)
- [Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs](https://mlsanity.com/paper/1807.04428/) (2018)
- [Correlation Clustering with Low-Rank Matrices](https://mlsanity.com/paper/1611.07305/) (2016)
- [An Inexact Proximal Path-Following Algorithm for Constrained Convex Minimization](https://mlsanity.com/paper/1311.1756/) (2013)
- [Fixed-rank Rayleigh Quotient Maximization by an MPSK Sequence](https://mlsanity.com/paper/1401.6968/) (2014)
- [A single-phase, proximal path-following framework](https://mlsanity.com/paper/1603.01681/) (2016)

## Abstract (arXiv)

We present a novel, practical, and provable approach for solving diagonally constrained semi-definite programming (SDP) problems at scale using accelerated non-convex programming. Our algorithm non-trivially combines acceleration motions from convex optimization with coordinate power iteration and matrix factorization techniques. The algorithm is extremely simple to implement, and adds only a single extra hyperparameter -- momentum. We prove that our method admits local linear convergence in the neighborhood of the optimum and always converges to a first-order critical point. Experimentally, we showcase the merits of our method on three major application domains: MaxCut, MaxSAT, and MIMO signal detection. In all cases, our methodology provides significant speedups over non-convex and convex SDP solvers -- 5X faster than state-of-the-art non-convex solvers, and 9 to 10^3 X faster than convex SDP solvers -- with comparable or improved solution quality.