Research map / Learning theory and algorithms / Combinatorial and search optimization
Polynomial time guarantees for the Burer-Monteiro method
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add random perturbation (sigma=0.2) to a badly behaved SDP | Burer-Monteiro with augmented Lagrangian · Perturbed bad SDP (n=50, m=28, p=r=7) | percentage of instances solved: 52% -> 87% | Helped |
| increase factorization rank p above the Barvinok-Pataki bound p=r | Burer-Monteiro on planted SDPs · Random planted-solution SDPs, n=50, r in {4,7,12} | percentage solved correctly | Helped |
Closest papers by meaning
- The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound (NeurIPS 2022 · similarity 0.93)
- On the Complexity of Finite-Sum Smooth Optimization under the Polyak–Łojasiewicz Condition (ICML 2024 · similarity 0.84)
- The Computational Complexity of Finding Second-Order Stationary Points (ICML 2024 · similarity 0.84)
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching (ICML 2024 · similarity 0.83)
- Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry (NeurIPS 2024 · similarity 0.83)
- Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.