Dropping Convexity for Faster Semi-definite Optimization

Abstract

We study the minimization of a convex function $f(X)$ over the set of $n\times n$ positive semi-definite matrices, but when the problem is recast as ${\min }_{U}g(U):=f(U{U}^{\top })$, with $U\in {\mathbb{R}}^{n\times r}$ and $r\le n$. We study the performance of gradient descent on $g$---which we refer to as Factored Gradient Descent (FGD)---under standard assumptions on the original function $f$. We provide a rule for selecting the step size and, with this choice, show that the local convergence rate of FGD mirrors that of standard gradient descent on the original $f$: i.e., after $k$ steps, the error is $O(1/k)$ for smooth $f$, and exponentially small in $k$ when $f$ is (restricted) strongly convex. In addition, we provide a procedure to initialize FGD for (restricted) strongly convex objectives and when one only has access to $f$ via a first-order oracle; for several problem instances, such proper initialization leads to global convergence guarantees. FGD and similar procedures are widely used in practice for problems that can be posed as matrix factorization. To the best of our knowledge, this is the first paper to provide precise convergence rate guarantees for general convex functions under standard convex assumptions.

40 pages

References in corpus (10)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Low-rank optimization for distance matrix completion
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• The local convexity of solving systems of quadratic equations
• Sparse PCA via Bipartite Matchings

Cited by in corpus (18)

• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Global Optimality in Low-rank Matrix Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• When Are Nonconvex Problems Not Scary?
• The Non-convex Geometry of Low-rank Matrix Optimization
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Recovery guarantee of weighted low-rank approximation via alternating minimization
• Quartic First-Order Methods for Low-Rank Minimization
• Efficient Low-Rank Semidefinite Programming with Robust Loss Functions