# Low-Rank Extragradient Methods for Scalable Semidefinite Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 14 Feb 2024.

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

- [Global rates of convergence for nonconvex optimization on manifolds](https://mlsanity.com/paper/1605.08101/) (2016)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Random Laplacian matrices and convex relaxations](https://mlsanity.com/paper/1504.03987/) (2015)
- [Rank optimality for the Burer-Monteiro factorization](https://mlsanity.com/paper/1812.03046/) (2018)
- [On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems](https://mlsanity.com/paper/1902.01644/) (2019)
- [Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization](https://mlsanity.com/paper/1901.01287/) (2019)
- [On the simplicity and conditioning of low rank semidefinite programs](https://mlsanity.com/paper/2002.10673/) (2020)
- [Revisiting Spectral Bundle Methods: Primal-dual (Sub)linear Convergence Rates](https://mlsanity.com/paper/2008.07067/) (2020)
- [On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems](https://mlsanity.com/paper/2001.11668/) (2020)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle](https://mlsanity.com/paper/2210.13968/) (2022)
- [Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementarity](https://mlsanity.com/paper/2308.01677/) (2023)

## Abstract (arXiv)

We consider several classes of highly important semidefinite optimization problems that involve both a convex objective function (smooth or nonsmooth) and additional linear or nonlinear smooth and convex constraints, which are ubiquitous in statistics, machine learning, combinatorial optimization, and other domains. We focus on high-dimensional and plausible settings in which the problem admits a low-rank solution which also satisfies a low-rank complementarity condition. We provide several theoretical results proving that, under these circumstances, the well-known Extragradient method, when initialized in the proximity of an optimal primal-dual solution, converges to a solution of the constrained optimization problem with its standard convergence rates guarantees, using only low-rank singular value decompositions (SVD) to project onto the positive semidefinite cone, as opposed to computationally-prohibitive full-rank SVDs required in worst-case. Our approach is supported by numerical experiments conducted with a dataset of Max-Cut instances.