Polynomial time guarantees for the Burer-Monteiro method
Authors: Diego Cifuentes, Ankur Moitra
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 6 Experiments We present some experimental results to complement our theorems. We rely on the library NLopt [24] (MIT license) to solve the nonlinear problem (BM). Concretely, we use the augmented Lagrangian method (ALM) implemented in NLopt (which is based on [8]), and we use the preconditioned truncated Newton method as the subroutine. We also rely on the commercial solver Mosek for SDPs. Figure 1 shows the percentage of experiments solved correctly for each value of r and p. |
| Researcher Affiliation | Academia | Diego Cifuentes School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332 diego.cifuentes@isye.gatech.edu Ankur Moitra Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139 moitra@mit.edu |
| Pseudocode | No | The paper refers to algorithms (e.g., 'Theorem 4 below we show that AFAC points can be computed in polynomial time'), but it does not provide explicit pseudocode or an algorithm block for any method. |
| Open Source Code | Yes | Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] In supplementary material |
| Open Datasets | No | For our first experiment we consider a random SDP with a planted solution. More precisely, we take a matrix X0 S50, X0 0 of rank r {4, 7, 12}, and generate a random SDP for which X0 is an optimal solution. To do so, we generate m := τ(r) random constraints that are satisfied at X0, and then find a cost matrix C in the normal cone of X0. We generate 100 random SDPs for each r. We use random data for the experiments. |
| Dataset Splits | No | The paper states 'N/A' for specifying 'training details (e.g., data splits, hyperparameters, how they were chosen)' in the ethics review guidelines. |
| Hardware Specification | No | The paper states 'N/A' for 'total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)' in the ethics review guidelines, indicating no specific hardware details. |
| Software Dependencies | No | The paper mentions 'NLopt [24]' and 'Mosek' as software used, but it does not specify version numbers for these components. |
| Experiment Setup | No | The paper states 'N/A' for specifying 'training details (e.g., data splits, hyperparameters, how they were chosen)' in the ethics review guidelines. |