Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching
Authors: Rico Angell, Andrew Mccallum
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We empirically demonstrate the effectiveness of our method across multiple applications, with and without warm-starting. We evaluate USBS on three different problem types with and without warm-starting strategies against the scalable semidefinite programming algorithm CGAL (Yurtsever et al., 2019; 2021) (with sketching). |
| Researcher Affiliation | Academia | Manning College of Information and Computer Sciences, University of Massachusetts Amherst, Amherst, MA, USA. |
| Pseudocode | Yes | Algorithm 1 Unified Spectral Bundling |
| Open Source Code | Yes | We make our implementation in pure JAX publicly available1. 1https://github.com/rangell/usbs |
| Open Datasets | Yes | We evaluate the CGAL and USBS with and without warm-starting on ten instances from the DIMACS10 (Bader et al.)... We evaluate CGAL and USBS on select large instances from QAPLIB (Burkard et al., 1997) and TSPLIB (Reinelt, 1995)... We evaluate the performance of the CGAL and USBS with and without warm-starting on the same three author coreference datasets used in (Angell et al., 2022). |
| Dataset Splits | Yes | We warm-start each method by dropping the last 1% of vertices from the graph, resulting in a graph with 99% of the vertices. We create a slightly smaller QAP by dropping the final row and column of both D and W (i.e. solve a size n 1 subproblem of the original instance). We use ε = 10 1 to determine the stopping condition. |
| Hardware Specification | Yes | Unless otherwise specified, we use a CPU machine with 16 cores and up to 128 GB of RAM. All runs were executed on a single NVIDIA Ge Force 1080 Ti GPU. |
| Software Dependencies | No | The paper mentions "pure JAX" as the implementation environment but does not specify a version number for JAX or any other software libraries used. |
| Experiment Setup | Yes | Unless otherwise specified, we use the following hyperparameters for USBS in our experiments: r = 10, ρ = 0.01, β = 0.25, kc = 10, kp = 1. We use the following hyperparameters for USBS in our experiments: ρ = 0.005, β = 0.25, kc = 2, kp = 0. We use the following USBS hyperparameters in our experiments: ρ = 0.01, β = 0.25, kc = 3, kp = 0. |