Global Convergence of Stochastic Gradient Descent for Some Non-Convex Matrix Problems
Abstract
Stochastic gradient descent (SGD) on a low-rank factorization is commonly employed to speed up matrix problems including matrix completion, subspace tracking, and SDP relaxation. In this paper, we exhibit a step size scheme for SGD on a low-rank least-squares problem, and we prove that, under broad sampling conditions, our method converges globally from a random starting point within O(ε^-1 n \log n) steps with constant probability for constant-rank problems. Our modification of SGD relates it to stochastic power iteration. We also show some experiments to illustrate the runtime and convergence of the algorithm.
Cite
Text
De Sa et al. "Global Convergence of Stochastic Gradient Descent for Some Non-Convex Matrix Problems." International Conference on Machine Learning, 2015.Markdown
[De Sa et al. "Global Convergence of Stochastic Gradient Descent for Some Non-Convex Matrix Problems." International Conference on Machine Learning, 2015.](https://mlanthology.org/icml/2015/sa2015icml-global/)BibTeX
@inproceedings{sa2015icml-global,
title = {{Global Convergence of Stochastic Gradient Descent for Some Non-Convex Matrix Problems}},
author = {De Sa, Christopher and Re, Christopher and Olukotun, Kunle},
booktitle = {International Conference on Machine Learning},
year = {2015},
pages = {2332-2341},
volume = {37},
url = {https://mlanthology.org/icml/2015/sa2015icml-global/}
}