Source-linked AI summary
Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching
Rico Angell, Andrew McCallum
TL;DR
Standard SDP solvers are costly, and scalable sketching approaches can be difficult to warm-start reliably. USBS combines spectral bundling for equality- and inequality-constrained SDPs with optional sketching; it reports a 500x speedup over the prior scalable solver on a 2-billion-variable instance.
Problem
Standard SDP solvers incur high computational costs, while the cited sketching approach has iteration-dependent parameters that impede reliable warm-start use.
Source: §1 · pp. 1–2Method
Results
500x speedup over the previous state-of-the-art scalable solver on an instance with 2 billion decision variables.
Source: §1 · p. 2Takeaways & Limitations
USBS can more reliably leverage warm-start initialization to accelerate convergence on practical SDP instances.
Source: §7 · p. 12The analysis assumes strong duality; Slater’s condition and surjective A are stated as sufficient for it.
Source: §2.1 · p. 3
Abstract
from arXiv · showhide
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.
1 Introduction
Standard SDP solvers face high computational costs, while scalable alternatives have trade-offs in memory, convexity, or warm-start use. USBS unifies spectral bundling for equality- and inequality-constrained SDPs and combines scalability with fast convergence and warm-start benefits.
1 Introduction
- Standard SDP projections require a full eigendecomposition that scales cubically with problem dimension, limiting projected-gradient and ADMM approaches.Interior-point methods for small-to-moderate SDPs require even more computational resources.Source: §1 · p. 1
- Projection-free methods reduce per-iteration cost but remain limited by storing the full primal matrix, which scales quadratically with dimension.The cited approaches include dual-space subgradient descent and conditional gradients on an unconstrained augmented objective.Source: §1 · p. 1
- USBS can leverage warm starts, unlike the cited sketching approach whose iteration-dependent parameters impede reliable use of warm-start initializations.The paper reports more than a 100x convergence speedup from warm-starting USBS compared with cold-starting.Source: §1 · p. 2
- Prior spectral bundle methods considered either equality-only or inequality-only SDPs, and lacked an efficient standalone implementation for evaluating massive instances.USBS is presented as a unified spectral bundle method for both constraint types, with optional sketching to improve scalability while maintaining fast convergence.Source: §1 · p. 2
- USBS achieves a 500x speedup over the previous state-of-the-art scalable solver on an instance with 2 billion decision variables.The paper also reports a quality solution for an SDP with over 10^13 decision variables where that solver did not reach an accurate solution within 72 hours.Source: §1 · p. 2
2 Preliminaries
The preliminaries specify the SDP setting, solution assumptions, and structured features the algorithm aims to exploit. They also introduce proximal bundle iterations and model requirements used to establish convergence.
2.1 Semidefinite Programming
- The SDP setup partitions constraints into inequality and equality index sets, represented through the primal feasibility set K.The text cautions that converting inequalities to standard-form equalities increases the problem dimension by one per inequality constraint.Source: §2.1 · pp. 2–3
- The analysis assumes strong duality, with nonempty compact solution sets and zero duality gap; Slater’s condition and surjective A suffice for strong duality.Strict complementarity is defined by ranks of the primal solution and dual slack summing to n.Source: §2.1 · p. 3
- The motivating application structure includes sparse cost matrices, relatively few constraints, and low-rank primal solutions.The stated goal is to exploit these features in an algorithm that can solve any SDP.Source: §2.1 · p. 3
2.2 Proximal Bundle Method
- A proximal bundle iteration applies a proximal step to an objective model and accepts the candidate iterate only when actual decrease reaches a fixed fraction of predicted decrease.Otherwise it takes a null step, retaining the current iterate while using the candidate to construct the next model.Source: §2.2 · p. 3
- Bundle models are built from subgradients and must meet conditions that preserve first-order information and approximation accuracy.Under model requirements, prior work proves non-asymptotic convergence rates summarized for this work.Source: §2.2 · pp. 3–4
3 Unified Spectral Bundling
USBS applies a unified spectral bundle method to SDPs with equality and inequality constraints, with optional matrix sketching for greater scalability. Its low-dimensional spectral model supports candidate-iterate computation, and the method has convergence guarantees under stated assumptions.
3 Unified Spectral Bundling
- USBS unifies spectral bundling for SDPs with equality and inequality constraints and can be integrated with matrix sketching for greater scalability.The method minimizes a reformulation equivalent to the dual SDP in solution set and objective.Source: §3 · p. 4
3.1 Spectral Bundle Model
- The spectral model restricts the primal search to a low-dimensional subspace parameterized by a primal matrix and a small set of current and past spectral directions.The matrix V_t includes a maximum eigenvector, while the weighted sum of past spectral bounds supports the model’s approximation condition.Source: §3.1 · pp. 4–5
3.2 Computing the Candidate Iterate
- USBS computes candidate iterates with a proximal step and has no iteration-dependent step sizes or parameters, making warm-start initialization more practical.The main cost of evaluating the objective and candidate objective is a maximum-eigenvalue computation.Source: §3.2 · pp. 5–6
- Under strong duality, USBS achieves its stated convergence conditions by O(1/ε^3) iterations, or O(1/ε) with strict complementarity; Slater’s condition and a unique y⋆ improve feasibility and primal-dual gap to ε.The improved feasibility and gap bounds are dist(AX_t, K) ≤ ε and |⟨b, y_t⟩−⟨C, X_t⟩| ≤ ε.Source: §3.2 · p. 7
4 Scaling with Matrix Sketching
USBS uses a Nyström sketch to track a compressed projection of the primal iterate, addressing the storage burden of large SDPs. The approximation error is confined to the primal-matrix approximation and does not compound over time.
4 Scaling with Matrix Sketching
- A Nyström sketch tracks a compressed low-rank projection of the primal iterate, from which a provably accurate low-rank approximation can be computed.The sketch is maintained under low-rank updates to the primal iterate.Source: §4 · p. 7
- The sketch’s only approximation error is in the primal-matrix approximation, and that error is constant rather than compounding over time.When only solving the dual problem, USBS can avoid explicitly storing the primal iterate and maintain its needed quantities with low-rank updates.Source: §4 · p. 7
5 Experiments
The experiments compare USBS with CGAL, with and without warm starts, across MaxCut, QAP, and interactive entity resolution. They report that USBS solves all ten MaxCut instances within 28 hours without warm-starting, and evaluate its scalability and warm-start performance on the other tasks.
5.1 MaxCut
- USBS reaches an ε-approximate solution on all ten MaxCut instances within 28 hours without warm-starting, while CGAL fails on seven.The comparison uses ε = 10^-1; instances range from 16K to 3.7M vertices.Source: Figure 1 · p. 8
- The MaxCut comparison tests ten DIMACS10 graphs, using solutions from graphs with 99% of the vertices to initialize warm starts.The smaller-graph solutions are padded with zeros and rescaled as needed.Source: §5.1 · p. 8
5.2 Quadratic Assignment Problem
- Sketching reduces the QAP relaxation from O(n^4) decision variables to an O(n^3)-entry sketch, enabling instances with n = 198.The reported largest instance has 1.5 billion decision variables.Source: §5.2 · p. 9
- For QAP, CGAL and USBS are evaluated on selected QAPLIB and TSPLIB instances of sizes 136–198, applying rounding at every iteration and measuring relative gap.Warm starts solve a size n − 1 subproblem; the smaller problem and original instance are each optimized for one hour. Figure 2 plots relative gap and best relative gap over time for one TSPLIB instance.Source: §5.2 · p. 9
5.3 Interactive Entity Resolution with ∃-constraints
- The entity-resolution experiments add ∃-constraints sequentially and warm-start each SDP from the solution to the preceding problem.The three author-coreference datasets are evaluated until the inference algorithm predicts perfect entity-resolution decisions.Source: §5.3 · p. 10
6 Related Work
Prior SDP solvers trade per-iteration cost against convergence speed, and memory-efficient approaches can sacrifice convexity or face scaling limits. USBS extends spectral bundling to equality- and inequality-constrained SDPs and addresses practical scalability.
Efficient SDP solving
- Interior-point methods have high per-iteration complexity, while first-order methods have lower per-iteration complexity but slower convergence.ADMM and splitting-based methods remain constrained by full eigenvalue decompositions.Source: §6 · pp. 10–11
Spectral bundle methods
- Across author-coreference datasets, the observed performance gap between USBS and CGAL grows with problem size.Figure 3 measures cumulative SDP solve time against the number of generated ∃-constraints.Source: Figure 3 · p. 11
- Earlier spectral bundle methods address either equality- or inequality-constrained SDPs, whereas USBS supports both and offers a more flexible model and greater scalability.The cited related work includes equality-constrained methods with convergence-rate guarantees under assumptions.Source: §6 · p. 11
Memory-efficient semidefinite programming
- Burer–Monteiro factorization controls memory through low-rank factors but sacrifices convexity and can require high rank or risk local minima.Other cited memory-efficient approaches include dual-slack storage and matrix sketching with conditional-gradient methods.Source: §6 · p. 11
7 Conclusion
The conclusion presents USBS as a practical spectral bundle method for large SDPs with equality and inequality constraints. It reports non-asymptotic convergence guarantees, empirical speed and scalability, and more reliable use of warm starts.
7 Conclusion
- USBS is a practical spectral bundle method for large SDPs with both equality and inequality constraints.The paper reports non-asymptotic convergence rates under standard assumptions, empirical speed and scalability, and more reliable warm-start use.Source: §7 · p. 12
A Derivations
The appendix derives USBS’s penalized dual formulation, candidate-iterate updates, and interior-point procedures for its iteration subproblems. It also describes Nyström sketch reconstruction and the resulting memory requirements.
A.1 Penalized Dual Objective; A.2 Equivalent Penalized Dual Objective
- The derivation rewrites the dual problem using a penalized dual objective and an equivalent formulation based on the dual of an indicator function.The indicator is zero on its feasible set and infinite outside it.Source: §A.1 · p. 19, §A.2 · p. 19
A.3 Candidate Iterate
- The candidate iterate is computed by fixing a feasible pair, completing the square, and solving an optimization problem over the candidate set.The update is presented through the candidate-iterate derivation.Source: §A.3 · pp. 19–20
B Solving Iteration Subproblems
- The appendix introduces svec and the symmetric Kronecker product to formulate the small semidefinite subproblem solved by a primal-dual interior-point method.The implementation uses the explicit symmetric Kronecker-product definition.Source: B Solving Iteration Subproblems · p. 20
B.1 Computing ˆft(˜yt+1)
- For computing the model value, the interior-point method follows a central path with Newton steps, eliminating variables to solve for svec(∆S).It uses backtracking to preserve strict feasibility and iterates until the barrier parameter is small enough.Source: §B.1 · pp. 21–22
B.2 Solving (16)
- The second subproblem computes η and S for the candidate iterate; its interior-point procedure can warm-start from the previous execution’s solution.The appendix reports non-negligible convergence improvements over arbitrary initialization when these executions run in sequence.Source: §B.2 · pp. 23–24
B.3 Remark on Solving Subproblems
- The authors report that projected gradient descent performs poorly in practice because selecting a high-quality step size is difficult and varies across iterations.They instead use a primal-dual interior-point method for the subproblem.Source: §B.3 · p. 24
C Additional Details on Scaling with Matrix Sketching; C.1 Nyström Sketch Reconstruction
- Nyström reconstruction yields a rank-r approximation from a sketch, with an error bound that remains valid after rank truncation.The appendix describes a numerically stable implementation and a provably good approximation for sketched matrices.Source: §C.1 · p. 25
C.2 USBS Memory Requirements.
- With matrix sketching, USBS requires O(nr + nk + m + k^4) working memory, excluding problem data, rather than O(n^2) to store the full iterate.The memory accounting includes the sketch, low-rank factors, constraints, and interior-point subproblems.Source: §C.2 · p. 25
D Proof of Theorem 3.1
The proof establishes non-asymptotic convergence for USBS, with faster rates under additional conditions. The experimental setup and MaxCut sections describe the evaluation machinery and how sketching and rounding are applied.
D Proof of Theorem 3.1
- O(1/ε^3) iterations suffice for ε accuracy under bounded iterates and subgradients, improving to O(1/ε) under quadratic growth.The proof says strict complementarity guarantees quadratic growth; Slater’s condition gives singularity degree zero.Source: D Proof of Theorem 3.1 · pp. 25–26
D.1 Proof of Theorem 3.1
- The proof derives primal feasibility, dual feasibility, and primal-dual optimality convergence from convergence of the penalized dual objective.Its strategy applies the proximal bundle rate to the penalized dual gap, then uses three lemmas to establish those convergence properties.Source: §D.1 · p. 28
E Experimental Setup and Details
- Both solvers use thick-restart Lanczos with 32 inner iterations and up to 10 restarts, in 64-bit arithmetic; experiments generally use a 16-core CPU with up to 128 GB RAM.The setup also specifies that metrics marked ↑ are higher-is-better and those marked ↓ are lower-is-better.Source: E Experimental Setup and Details · p. 29
E.1 MaxCut
- MaxCut is NP-hard, but rounding an SDP relaxation can yield strong approximate solutions.The section presents MaxCut as a fundamental combinatorial optimization problem and a common test bed for SDP solvers.Source: §E.1 · p. 29
E.1.1 SDP Relaxation
- The MaxCut relaxation imposes diag(X) = 1 and X ⪰ 0; sparse graph Laplacians and low-rank solutions make sketching X with relatively small r attractive.For a cut vector x ∈ {±1}^n, X = xx⊤ is positive semidefinite with unit diagonal.Source: §E.1.1 · p. 29
E.1.2 Rounding
- Rounding reconstructs a low-rank approximation from the sketch and selects the best cut among the sign patterns of its columns.The method evaluates the r cuts given by the columns of sgn(U).Source: §E.1.2 · p. 30
E.1.3 Experimental Setup
The experiments describe warm-starting on MaxCut and motivate large QAP instances as a test of sketching. The QAP relaxation and rounding procedure reduce the problem to a scalable representation and feasible assignments.
E.1.3 Experimental Setup
- MaxCut experiments use ten DIMACS10 instances and warm-start from graphs formed by dropping the final 1% of vertices.The smaller-problem solution is padded with zeros and rescaled for initialization.Source: §E.1.3 · p. 30
E.2 Quadratic Assignment Problem
- QAPs include problems such as traveling salesman and max-clique, and exact solutions are generally intractable for n > 30.The experiments use SDP relaxation and rounding to obtain solutions for QAPs with n between 136 and 198.Source: §E.2 · p. 30
E.2.1 SDP Relaxation
- Sketching the QAP primal variable with r = n yields O(n^3) entries and enables CGAL and USBS to scale to n = 198, with more than 1.5 billion decision variables and constraints.The unsketched relaxation has O(n^4) decision variables; sparse instances can have O(n^3) constraints.Source: §E.2.1 · p. 30
E.2.2 Rounding
- The rounding procedure reshapes each reconstructed sketch column into an n × n matrix and projects it onto permutation matrices using the Hungarian method.It chooses the permutation matrix with the lowest objective among the rounded columns to obtain an upper bound.Source: §E.2.2 · p. 31
E.2.3 Experimental Setup
The QAP setup evaluates rounded solutions against known optima, while the entity-resolution sections specify existential feedback and its SDP treatment. The relaxation’s fractional output is converted into a clustering for user review.
E.2.3 Experimental Setup
- QAP evaluation uses best relative gap, applies rounding at every iteration, and limits optimization to one hour per problem.Warm-start runs spend one hour on the smaller QAP and another hour on the original instance.Source: §E.2.3 · p. 31
E.3 Interactive Entity Resolution with ∃-constraints
- Interactive entity resolution uses human feedback to correct clustering predictions, with ∃-constraints as a feedback paradigm for expressing entity-feature requirements.The setup simulates this feedback through an oracle that generates constraints until the ground-truth clustering is predicted.Source: §E.3 · pp. 31–32
E.3.1 ∃-constraints
- An ∃-constraint specifies positive features that must occur and negative features that must be absent in at least one ground-truth cluster.More than one ground-truth cluster may satisfy a constraint; with unique mention features, the framework encompasses must-link and cannot-link constraints.Source: §E.3.1 · p. 32
E.3.2 SDP relaxation
- The SDP relaxation represents pairwise affinity with a positive semidefinite matrix, constraining its diagonal to ones and all entries to be nonnegative.The formulation adds constraints to ensure ∃-constraint satisfaction and incompatibility requirements.Source: §E.3.2 · pp. 32–33
E.3.3 Rounding
- Rounding builds a hierarchical clustering using the fractional SDP solution as similarity, then uses dynamic programming to select a flat clustering.The selected clustering maximizes the number of satisfied ∃-constraints and the correlation-clustering objective, after which users can provide additional feedback.Source: §E.3.3 · p. 33
E.3.4 Experimental Setup
The author-coreference experiments compare CGAL and USBS with and without warm-starting on three datasets. They simulate incremental feedback with an oracle and use an expanded primal initialization for each new constraint.
E.3.4 Experimental Setup
- The three author-coreference datasets aggregate pairwise mention similarities into a block-diagonal matrix, then use spectral sparsification; Table 3 reports dataset statistics including nnz(W).Mentions are author-paper pairs, and the task is to identify pairs written by the same author.Source: §E.3.4 · p. 33, Table 3 · p. 34
- An oracle adds one ∃-constraint at a time until the ground-truth clustering is predicted; runs stop when the relative-error tolerance and absolute-infeasibility condition are met.The experiments use ε = 10^-1 and non-sketching variants because the problems are small.Source: §E.3.4 · p. 34
- For warm-starting, the new primal initialization averages low-rank representations of positive-feature vertices, while the dual variable is padded with zeros.The setup also scales selected constraint norms for vertices sharing features with the new constraint.Source: §E.3.4 · p. 34
F.1 MaxCut
Across the three applications, USBS shows improved convergence behavior with warm-starts, while its performance depends on parameter settings and the particular initialization. The reported comparisons also highlight GPU speedups and benefits that grow with problem size.
F.1 MaxCut
- Warm-starting accelerated USBS convergence on the MaxCut instance, and its rounded cuts deteriorated less than CGAL’s under warm-starting.USBS with and without warm-starting also produced a marginally better graph cut than CGAL.Source: §F.1 · p. 34, Figure 4 · p. 35
- 10–25x GPU speedup over CPU was observed on the DIMACS10 instance, and USBS performed best when kc ≥ kp.The comparisons covered CPU and GPU runs across settings of kc and kp.Source: §F.1 · p. 34, Figure 9 · p. 37, Figure 10 · p. 38
F.2 QAP
- On most QAPLIB and TSPLIB instances, USBS achieved a better one-hour best relative gap than CGAL, and it leveraged warm-starts more reliably.Warm-starting did not always yield a better best relative gap; for the three plotted instances, the best gap appeared within the first few minutes.Source: §F.2 · p. 39, Figure 11 · p. 39, Figure 12 · p. 39
F.3 Interactive Entity Resolution with ∃-constraints
- For interactive entity resolution, warm-starting gave USBS an average 20–100x SDP solve-time speedup per ∃-constraint, with greater benefit on larger SDPs.In some cases, an initialization far from the new SDP’s solution set did not help; CGAL’s warm-start fold change was at most one.Source: §F.3 · p. 41, Figure 14 · p. 41