# Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 108 references that are in the map.
- First posted on arXiv 19 Dec 2023.

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

- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Large Language Models Enable Few-Shot Clustering](https://mlsanity.com/paper/2307.00524/) (2023)
- [Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming](https://mlsanity.com/paper/2010.11645/) (2020)
- [FRUIT: Faithfully Reflecting Updated Information in Text](https://mlsanity.com/paper/2112.08634/) (2021)
- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints](https://mlsanity.com/paper/1906.11357/) (2019)
- [Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data](https://mlsanity.com/paper/1706.05736/) (2017)
- [(Almost) All of Entity Resolution](https://mlsanity.com/paper/2008.04443/) (2020)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [Entity Linking and Discovery via Arborescence-based Supervised Clustering](https://mlsanity.com/paper/2109.01242/) (2021)
- [S2AND: A Benchmark and Evaluation System for Author Name Disambiguation](https://mlsanity.com/paper/2103.07534/) (2021)
- [Rank optimality for the Burer-Monteiro factorization](https://mlsanity.com/paper/1812.03046/) (2018)
- [Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage](https://mlsanity.com/paper/1702.06838/) (2017)
- [A Conditional Gradient-Based Augmented Lagrangian Framework](https://mlsanity.com/paper/1901.04013/) (2019)
- [Interactive Bayesian Hierarchical Clustering](https://mlsanity.com/paper/1602.03258/) (2016)
- [The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints](https://mlsanity.com/paper/1706.00476/) (2017)
- [Optimal Convergence Rates for the Proximal Bundle Method](https://mlsanity.com/paper/2105.07874/) (2021)
- [A Universal Primal-Dual Convex Optimization Framework](https://mlsanity.com/paper/1502.03123/) (2015)
- [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)
- [An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementarity](https://mlsanity.com/paper/1902.03373/) (2019)
- [Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting](https://mlsanity.com/paper/1810.05231/) (2018)
- [Scalable Semidefinite Relaxation for Maximum A Posterior Estimation](https://mlsanity.com/paper/1405.4807/) (2014)
- [Semidefinite Programming Approach for the Quadratic Assignment Problem with a Sparse Graph](https://mlsanity.com/paper/1703.09339/) (2017)
- [The many faces of degeneracy in conic optimization](https://mlsanity.com/paper/1706.03705/) (2017)
- [Low-rank spectral optimization via gauge duality](https://mlsanity.com/paper/1508.00315/) (2015)
- [Error Bounds and Singularity Degree in Semidefinite Programming](https://mlsanity.com/paper/1908.04357/) (2019)

## Built on by (most cited first, 4 of 4)

- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Learning Transferable Topology Priors for Multi-Agent LLM Collaboration Across Domains](https://mlsanity.com/paper/2605.17359/) (2026)
- [Learning for Dynamic Combinatorial Optimization without Training Data](https://mlsanity.com/paper/2505.19497/) (2025)
- [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)

While semidefinite programming (SDP) has traditionally been limited to moderate-sized problems, recent algorithms augmented with matrix sketching techniques have enabled solving larger SDPs. However, these methods achieve scalability at the cost of an increase in the number of necessary iterations, resulting in slower convergence as the problem size grows. Furthermore, they require iteration-dependent parameter schedules that prohibit effective utilization of warm-start initializations important in practical applications with incrementally-arriving data or mixed-integer programming. We present Unified Spectral Bundling with Sketching (USBS), a provably correct, fast and scalable algorithm for solving massive SDPs that can leverage a warm-start initialization to further accelerate convergence. Our proposed algorithm is a spectral bundle method for solving general SDPs containing both equality and inequality constraints. Moveover, when augmented with an optional matrix sketching technique, our algorithm achieves the dramatically improved scalability of previous work while sustaining convergence speed. We empirically demonstrate the effectiveness of our method across multiple applications, with and without warm-starting. For example, USBS provides a 500x speed-up over the state-of-the-art scalable SDP solver on an instance with over 2 billion decision variables.