ICML 2015poster206 citations
Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
Christopher De Sa, Christopher Re, Kunle Olukotun
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.
BibTeX
@InProceedings{pmlr-v37-sa15,
title = {Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems},
author = {Sa, Christopher De and Re, Christopher and Olukotun, Kunle},
booktitle = {Proceedings of the 32nd International Conference on Machine Learning},
pages = {2332--2341},
year = {2015},
editor = {Bach, Francis and Blei, David},
volume = {37},
series = {Proceedings of Machine Learning Research},
address = {Lille, France},
month = {07--09 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v37/sa15.pdf},
url = {https://proceedings.mlr.press/v37/sa15.html},
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.}
}