Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees

Abstract

Optimization problems with rank constraints arise in many applications, including matrix regression, structured PCA, matrix completion and matrix decomposition problems. An attractive heuristic for solving such problems is to factorize the low-rank matrix, and to run projected gradient descent on the nonconvex factorized optimization problem. The goal of this problem is to provide a general theoretical framework for understanding when such methods work well, and to characterize the nature of the resulting fixed point. We provide a simple set of conditions under which projected gradient descent, when given a suitable initialization, converges geometrically to a statistically useful solution. Our results are applicable even when the initial solution is outside any region of local convexity, and even when the problem is globally concave. Working in a non-asymptotic framework, we show that our conditions are satisfied for a wide range of concrete models, including matrix regression, structured PCA, matrix completion with real and quantized observations, matrix decomposition, and graph clustering problems. Simulation results show excellent agreement with the theoretical predictions.

References in corpus (4)

• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• Projected Wirtinger Gradient Descent for Low-Rank Hankel Matrix Completion in Spectral Compressed Sensing

Cited by in corpus (95)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Matrix Completion has No Spurious Local Minimum
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• When Are Nonconvex Problems Not Scary?
• Mind Mappings: Enabling Efficient Algorithm-Accelerator Mapping Space Search
• ME-Net: Towards Effective Adversarial Robustness with Matrix Estimation
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Dropping Convexity for Faster Semi-definite Optimization
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• A Survey of Optimization Methods from a Machine Learning Perspective
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Characterization of Gradient Dominance and Regularity Conditions for Neural Networks
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• On Robustness of Principal Component Regression
• Robust PCA by Manifold Optimization
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Convolutional Phase Retrieval via Gradient Descent
• Harnessing Structures for Value-Based Planning and Reinforcement Learning
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Estimating Differential Latent Variable Graphical Models with Applications to Brain Connectivity
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• A Dictionary-Based Generalization of Robust PCA with Applications to Target Localization in Hyperspectral Imaging
• A Dictionary-Based Generalization of Robust PCA Part II: Applications to Hyperspectral Demixing
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• Solving Complex Quadratic Systems with Full-Rank Random Matrices
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimizations
• Blind Super-resolution of Point Sources via Projected Gradient Descent
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Provable quantum state tomography via non-convex methods
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• On Asymptotic Linear Convergence Rate of Iterative Hard Thresholding for Matrix Completion
• Provable Online CP/PARAFAC Decomposition of a Structured Tensor via Dictionary Learning
• On the computational and statistical complexity of over-parameterized matrix sensing
• Instability, Computational Efficiency and Statistical Accuracy
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Reducing Crowdsourcing to Graphon Estimation, Statistically
• Inference for Heteroskedastic PCA with Missing Data
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• Alternating minimization and alternating descent over nonconvex sets
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Matrix Completion and Related Problems via Strong Duality
• Fast Low-Rank Matrix Estimation without the Condition Number
• Gradient descent with nonconvex constraints: local concavity determines convergence
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
• Optimal tuning-free convex relaxation for noisy matrix completion
• On Approximation Guarantees for Greedy Low Rank Optimization
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect
• Riemannian Perspective on Matrix Factorization
• Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Randomized Value Functions via Posterior State-Abstraction Sampling
• Spectral State Compression of Markov Processes
• Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery
• Spectral Compressed Sensing via Projected Gradient Descent
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise
• AutoGFI: Streamlined Generalized Fiducial Inference for Modern Inference Problems in Models with Additive Errors
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• Implicit Regularization in Matrix Sensing via Mirror Descent
• Spectral M-estimation with Applications to Hidden Markov Models
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time
• Tensor Canonical Correlation Analysis with Convergence and Statistical Guarantees
• On Recovering the Best Rank-r Approximation from Few Entries
• High Dimensional Multivariate Regression and Precision Matrix Estimation via Nonconvex Optimization
• Provably convergent acceleration in factored gradient descent with applications in matrix sensing
• Robust spectral compressive sensing via vanilla gradient descent
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering