.png){kind=icon}
.png){kind=icon}
Return
Provable accelerated gradient method for nonconvex low rank optimization
.png){kind=icon}
OA
AI
DOI：10.1007/s10994-019-05819-w.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 minU R-nxr g(U) = f (UUT) under the assumptions that f (X) is restricted mu-strongly convex and L-smooth on the set {X : X greater than or similar to 0, rank(X) <= 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 root 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 = UVT and the same convergence result can be obtained. Extensive experimental results verify the advantage of our method.
Keywords:
MATRIX COMPLETION
OPTIMAL RATES
ALGORITHM
BOUNDS
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.