Research map / Learning theory and algorithms / Matrix and tensor methods
A Primal-Dual Analysis of Global Optimality in Nonconvex Low-Rank Matrix Recovery
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 |
|---|---|---|---|
| Lower sample complexity from primal-dual analysis: no spurious local minima requires O(r^2 d log d) observations versus O(r^4 d log d) in prior work | noisy matrix completion landscape analysis · matrix completion theory | sample complexity order | Helped |
| Primal-dual augmented Lagrangian algorithm instead of plain gradient descent with random initialization | matrix completion · d1=2000, d2=1500, r=20, p=15/25/35% | averaged Frobenius error vs data passes | Helped |
| Primal-dual algorithm vs projected GD and perturbed GD with random initialization | matrix completion · d1=2000, d2=1500, r=20 | convergence of estimation error | No clear effect |
| Primal-dual algorithm vs GD with random initialization on phase transition | matrix completion recovery probability · d1=120, d2=100 noiseless | phase transition sample size n/rd: 2.5rd vs 4rd | Helped |
| Primal-dual algorithm vs projected GD and perturbed GD on one-bit matrix completion | one-bit matrix completion · d1=2000, d2=1500, r=20, p=10/20/50% | log averaged estimation error vs data passes | No clear effect |
| Adding the Lagrangian/primal-dual analysis with RSC/RSS conditions to handle non-square loss (one-bit) and incoherence constraints | one-bit matrix completion landscape · theory | global optimality guarantee | Helped |
Closest papers by meaning
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (ICML 2017 · similarity 0.92)
- Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent (NeurIPS 2016 · similarity 0.91)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.91)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.88)
- Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (ICLR 2024 · similarity 0.88)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.88)
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.