Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems


Christopher De Sa, Christopher Re, Kunle Olukotun ;
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:2332-2341, 2015.


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.

Related Material