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

Abstract

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.

10 pages, 8 figures, preprint under review

References in corpus (4)

• Near-optimal bounds for phase synchronization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints