Research map / Learning theory and algorithms / Matrix and tensor methods
Smoothed analysis of the low-rank approach for smooth semidefinite programs
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 |
|---|---|---|---|
| Use the low-rank Burer–Monteiro approach instead of IPM | PhaseCut for phase retrieval · Phase retrieval, n = 3000 | speedup: about 40 times faster | Helped |
| Use the low-rank Burer–Monteiro approach instead of IPM | PhaseCut for phase retrieval · Phase retrieval, n up to 3000 | solution agreement | No clear effect |
| Use the low-rank Burer–Monteiro approach instead of IPM | PhaseCut for phase retrieval · Phase retrieval, n up to 3000 | constraint satisfaction | Helped |
| Use BM rather than IPM | PhaseCut for phase retrieval · Phase retrieval, n greater than 3000 | memory feasibility | Helped |
Closest papers by meaning
- The non-convex Burer-Monteiro approach works on smooth semidefinite programs (NeurIPS 2016 · similarity 0.91)
- The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound (NeurIPS 2022 · similarity 0.89)
- Polynomial time guarantees for the Burer-Monteiro method (NeurIPS 2022 · similarity 0.89)
- A Scalable Frank-Wolfe-Based Algorithm for the Max-Cut SDP (ICML 2023 · similarity 0.88)
- The Computational Complexity of Finding Second-Order Stationary Points (ICML 2024 · similarity 0.87)
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching (ICML 2024 · similarity 0.86)
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.