A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery

Abstract

We propose a generic framework based on a new stochastic variance-reduced gradient descent algorithm for accelerating nonconvex low-rank matrix recovery. Starting from an appropriate initial estimator, our proposed algorithm performs projected gradient descent based on a novel semi-stochastic gradient specifically designed for low-rank matrix recovery. Based upon the mild restricted strong convexity and smoothness conditions, we derive a projected notion of the restricted Lipschitz continuous gradient property, and prove that our algorithm enjoys linear convergence rate to the unknown low-rank matrix with an improved computational complexity. Moreover, our algorithm can be employed to both noiseless and noisy observations, where the optimal sample complexity and the minimax optimal statistical rate can be attained respectively. We further illustrate the superiority of our generic framework through several specific examples, both theoretically and experimentally.

42 pages, 3 figures

References in corpus (21)

• 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
• Stochastic Variance Reduction for Nonconvex Optimization
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Variance Reduction for Faster Non-Convex Optimization
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Fast matrix completion without the condition number
• Fast and Simple PCA via Convex Optimization
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Computational Limits for Matrix Completion
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• Exponential Family Matrix Completion under Structural Constraints
• 1-Bit Matrix Completion under Exact Low-Rank Constraint
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements

Cited by in corpus (6)

• Provable quantum state tomography via non-convex methods
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• Fast Low-Rank Matrix Estimation without the Condition Number
• Simple and practical algorithms for ${\ell }_p$-norm low-rank approximation
• On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization
• A Unified Framework for Stochastic Matrix Factorization via Variance Reduction