  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(\epsilon^{-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 experiments to illustrate the runtime and convergence
of the algorithm.
