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 (20)

• Guaranteed Matrix Completion via Non-convex Factorization
• A Geometric Analysis of Phase Retrieval
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• The Non-convex Geometry of Low-rank Matrix Optimization
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• Grassmannian Optimization for Online Tensor Completion and Tracking with the t-SVD
• A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• The local convexity of solving systems of quadratic equations
• Negative eigenvalues of the Hessian in deep neural networks
• Accelerated Stochastic Power Iteration
• MOSES: A Streaming Algorithm for Linear Dimensionality Reduction
• Exponentially convergent stochastic k-PCA without variance reduction
• Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning
• Adaptive PCA for Time-Varying Data
• Compact Factorization of Matrices Using Generalized Round-Rank
• The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
• Towards Lightweight and Automated Representation Learning System for Networks
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem