Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization.

摘要: Optimization with a low rank constraint has broad applications. For large scale problems, an attractive heuristic is to factorize the matrix product of two much smaller matrices. In this paper, we study nonconvex problem $\min_{U\in\mathbf R^{n\times r}} g(U)=f(UU^T)$ under assumptions that $f(X)$ restricted $\mu$-strongly convex and $L$-smooth on set $\{X:X\succeq 0,\mbox{rank}(X)\leq r\}$. We propose accelerated gradient method provable convergence rate $g(U^{N+1})-g(U^*)\leq \left(1-O\left(\sqrt{\frac{\mu}{nL}}\right)\right)^N\|U^0-U^*\|_F^2$, where $U^*$ can be any local minimum algorithm converges to. The improved $\left(1-O\left(\sqrt{\frac{\mu}{L}}\right)\right)^N$ practical assumption entries $U^{k}$ converge nearly equally fast those $U^*$. To best our knowledge, first work establishing linear optimal dependence condition number $L/\mu$ for kind problems. Our also transferred asymmetric factorization $X=\widetilde U\widetilde V^T$.