Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
Provides a provably accelerated method for nonconvex low-rank optimization, a common bottleneck in large-scale machine learning.
The paper proposes an accelerated gradient method for nonconvex low-rank matrix optimization that achieves local linear convergence with optimal dependence on the condition number √(L/μ) and global convergence to a critical point. Experiments confirm the method's advantage.
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(UU^T)$ under the assumptions that $f(X)$ is restricted $μ$-strongly convex and $L$-smooth on the set $\{X:X\succeq 0,rank(X)\leq 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/μ}$. 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=\widetilde U\widetilde V^T$ and the same convergence result can be obtained. Extensive experimental results verify the advantage of our method.