Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
arXiv:1702.04959
Abstract
Optimization over low rank matrices has broad applications in machine learning. For large scale problems, an attractive heuristic is to factorize the low rank matrix to a product of two much smaller matrices. In this paper, we study the nonconvex problem under the assumptions that is restricted -strongly convex and -smooth on the set . We propose an accelerated gradient method with alternating constraint that operates directly on the factors and show that the method has local linear convergence rate with the optimal dependence on the condition number of . Globally, our method converges to the critical point with zero gradient from any initializer. Our method also applies to the problem with the asymmetric factorization of and the same convergence result can be obtained. Extensive experimental results verify the advantage of our method.
References in corpus (21)
- Robust Recovery of Subspace Structures by Low-Rank Representation
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Estimation of high-dimensional low-rank matrices
- Sparse PCA: Optimal rates and adaptive estimation
- Global Optimality of Local Search for Low Rank Matrix Recovery
- How to Escape Saddle Points Efficiently
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Matrix Completion has No Spurious Local Minimum
- Fast Algorithms for Robust PCA via Gradient Descent
- Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
- The Non-convex Geometry of Low-rank Matrix Optimization
- Accelerated Methods for Non-Convex Optimization
- Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
- A globally convergent algorithm for nonconvex optimization based on block coordinate update
- "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
- The Global Optimization Geometry of Low-Rank Matrix Optimization
- Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
- A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing
- Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization