On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
arXiv:2001.11668
Abstract
We revisit the use of Stochastic Gradient Descent (SGD) for solving convex optimization problems that serve as highly popular convex relaxations for many important low-rank matrix recovery problems such as \textit{matrix completion}, \textit{phase retrieval}, and more. The computational limitation of applying SGD to solving these relaxations in large-scale is the need to compute a potentially high-rank singular value decomposition (SVD) on each iteration in order to enforce the low-rank-promoting constraint. We begin by considering a simple and natural sufficient condition so that these relaxations indeed admit low-rank solutions. This condition is also necessary for a certain notion of low-rank-robustness to hold. Our main result shows that under this condition which involves the eigenvalues of the gradient vector at optimal points, SGD with mini-batches, when initialized with a "warm-start" point, produces iterates that are low-rank with high probability, and hence only a low-rank SVD computation is required on each iteration. This suggests that SGD may indeed be practically applicable to solving large-scale convex relaxations of low-rank matrix recovery problems. Our theoretical results are accompanied with supporting preliminary empirical evidence. As a side benefit, our analysis is quite simple and short.
arXiv commentAccepted to Conference on Learning Theory 2020 (COLT 2020). This version fixes some minor errors in previous version
References in corpus (7)
- A Simpler Approach to Matrix Completion
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Matrix Completion has No Spurious Local Minimum
- Fast Algorithms for Robust PCA via Gradient Descent
- Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods
- Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
- On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems