# Scalable Semidefinite Programming

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2019.

## Built on by (most cited first, 30 of 36)

- [Learning to Warm-Start Fixed-Point Optimization Algorithms](https://mlsanity.com/paper/2309.07835/) (2023)
- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)
- [Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence](https://mlsanity.com/paper/2302.08580/) (2023)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)
- [Training Quantized Neural Networks to Global Optimality via Semidefinite Programming](https://mlsanity.com/paper/2105.01420/) (2021)
- [Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing](https://mlsanity.com/paper/2208.07469/) (2022)
- [Principal Component Analysis in Space Forms](https://mlsanity.com/paper/2301.02750/) (2023)
- [Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization](https://mlsanity.com/paper/2306.02212/) (2023)
- [Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching](https://mlsanity.com/paper/2312.11801/) (2023)
- [Randomized Algorithms for Scientific Computing (RASC)](https://mlsanity.com/paper/2104.11079/) (2021)
- [Higher-Order Newton Methods with Polynomial Work per Iteration](https://mlsanity.com/paper/2311.06374/) (2023)
- [Federated Myopic Community Detection with One-shot Communication](https://mlsanity.com/paper/2106.07255/) (2021)
- [Support Recovery in Sparse PCA with Incomplete Data](https://mlsanity.com/paper/2205.15215/) (2022)
- [Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization](https://mlsanity.com/paper/2202.13212/) (2022)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [How robust is randomized blind deconvolution via nuclear norm minimization against adversarial noise?](https://mlsanity.com/paper/2303.10030/) (2023)
- [Partial Inference in Structured Prediction](https://mlsanity.com/paper/2306.03949/) (2023)
- [Sub-universal variational circuits for combinatorial optimization problems](https://mlsanity.com/paper/2308.14981/) (2023)
- [Interventional Causal Structure Discovery over Graphical Models with Convergence and Optimality Guarantees](https://mlsanity.com/paper/2408.04819/) (2024)
- [Learning to Optimize by Differentiable Programming](https://mlsanity.com/paper/2601.16510/) (2026)
- [Cascading Robustness Verification: Toward Efficient Model-Agnostic Certification](https://mlsanity.com/paper/2602.04236/) (2026)
- [Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs](https://mlsanity.com/paper/2106.08775/) (2021)
- [A conditional gradient homotopy method with applications to Semidefinite Programming](https://mlsanity.com/paper/2207.03101/) (2022)
- [A Novel Plug-and-Play Approach for Adversarially Robust Generalization](https://mlsanity.com/paper/2208.09449/) (2022)
- [Support Recovery in Sparse PCA with Non-Random Missing Data](https://mlsanity.com/paper/2302.01535/) (2023)
- [Oblivious Stochastic Composite Optimization](https://mlsanity.com/paper/2306.17470/) (2023)
- [Conic Descent Redux for Memory-Efficient Optimization](https://mlsanity.com/paper/2308.07343/) (2023)
- [Locally Stationary Graph Processes](https://mlsanity.com/paper/2309.01657/) (2023)
- [Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+](https://mlsanity.com/paper/2406.10407/) (2024)

## Abstract (arXiv)

Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct randomized algorithm for solving large, weakly constrained SDP problems by economizing on the storage and arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over 1014 entries.