Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
arXiv:1803.00186
Abstract
Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we consider the Burer--Monteiro factorization approach for solving SDPs. We show that all approximate local optima are global optima for the penalty formulation of appropriately rank-constrained SDPs as long as the number of constraints scales sub-quadratically with the desired rank of the optimal solution. Our result is based on a simple penalty function formulation of the rank-constrained SDP along with a smoothed analysis to avoid worst-case cost matrices. We particularize our results to two applications, namely, Max-Cut and matrix completion.
arXiv comment24 pages
References in corpus (10)
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Guaranteed Matrix Completion via Non-convex Factorization
- Global rates of convergence for nonconvex optimization on manifolds
- How to Escape Saddle Points Efficiently
- Matrix Completion has No Spurious Local Minimum
- Global Optimality in Low-rank Matrix Optimization
- On the low-rank approach for semidefinite programs arising in synchronization and community detection
- Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
- Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
- Random matrices: overcrowding estimates for the spectrum
Cited by in corpus (7)
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
- The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints
- An equivalence between critical points for rank constraints versus low-rank factorizations
- Smoothed analysis of the low-rank approach for smooth semidefinite programs
- Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets
- Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs