Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements

Abstract

We study the problem of estimating low-rank matrices from linear measurements (a.k.a., matrix sensing) through nonconvex optimization. We propose an efficient stochastic variance reduced gradient descent algorithm to solve a nonconvex optimization problem of matrix sensing. Our algorithm is applicable to both noisy and noiseless settings. In the case with noisy observations, we prove that our algorithm converges to the unknown low-rank matrix at a linear rate up to the minimax optimal statistical error. And in the noiseless setting, our algorithm is guaranteed to linearly converge to the unknown low-rank matrix and achieves exact recovery with optimal sample complexity. Most notably, the overall computational complexity of our proposed algorithm, which is defined as the iteration complexity times per iteration time complexity, is lower than the state-of-the-art algorithms based on gradient descent. Experiments on synthetic data corroborate the superiority of the proposed algorithm over the state-of-the-art algorithms.

arXiv comment24 pages, 1 table, 1 figure

References in corpus (17)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Simpler Approach to Matrix Completion
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Estimation of high-dimensional low-rank matrices
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Stochastic Variance Reduction for Nonconvex Optimization
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Variance Reduction for Faster Non-Convex Optimization
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Fast and Simple PCA via Convex Optimization
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation

Cited by in corpus (3)

• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction