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({\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.

Cited by in corpus (5)

• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• Negative eigenvalues of the Hessian in deep neural networks
• Exponentially convergent stochastic k-PCA without variance reduction
• Adaptive PCA for Time-Varying Data
• Towards Lightweight and Automated Representation Learning System for Networks