Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization

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 ${\min }_{U\in {\mathcal{R}}^{n\times r}}g(U)=f(U{U}^T)$ under the assumptions that $f(X)$ is restricted $\mu$-strongly convex and $L$-smooth on the set $\{X:X⪰0,rank(X)\le r\}$. We propose an accelerated gradient method with alternating constraint that operates directly on the $U$ factors and show that the method has local linear convergence rate with the optimal dependence on the condition number of $\sqrt{L/\mu }$. 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 $X=\tilde{U}{\tilde{V}}^T$ and the same convergence result can be obtained. Extensive experimental results verify the advantage of our method.

References in corpus (8)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• How to Escape Saddle Points Efficiently
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Accelerated Methods for Non-Convex Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing

Cited by in corpus (2)

• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Applying Adaptive Gradient Descent to solve matrix factorization