Stochastic gradient descent (SGD) on a low-rank factorization is commonly to speed up matrix problems including matrix completion, subspace, and SDP relaxation. In this paper, we exhibit a step size scheme for on a low-rank least-squares problem, and we prove that, under broad conditions, our method converges globally from a random starting point O(\ε⁻¹ n log n) steps with constant probability for-rank problems. Our modification of SGD relates it to stochastic power. We also show experiments to illustrate the runtime and convergence the algorithm.
No takes yet. Share an insight, caveat, or question.
De et al. (2014) studied this question.