Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview

Abstract

Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonconvex optimization algorithms due to their susceptibility to spurious local minima, simple iterative methods such as gradient descent have been remarkably successful in practice. The theoretical footings, however, had been largely lacking until recently. In this tutorial-style overview, we highlight the important role of statistical models in enabling efficient nonconvex optimization with performance guarantees. We review two contrasting approaches: (1) two-stage algorithms, which consist of a tailored initialization step followed by successive refinement; and (2) global landscape analysis and initialization-free algorithms. Several canonical matrix factorization problems are discussed, including but not limited to matrix sensing, phase retrieval, matrix completion, blind deconvolution, robust principal component analysis, phase synchronization, and joint alignment. Special care is taken to illustrate the key technical insights underlying their analyses. This article serves as a testament that the integrated consideration of optimization and statistics leads to fruitful research findings.

Invited overview article

References in corpus (81)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Rank-Sparsity Incoherence for Matrix Decomposition
• Recovering low-rank matrices from few coefficients in any basis
• Spectral clustering and the high-dimensional stochastic blockmodel
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• An overview of low-rank matrix recovery from incomplete observations
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• Non-convex Optimization for Machine Learning
• Guaranteed Matrix Completion via Non-convex Factorization
• Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares
• Global rates of convergence for nonconvex optimization on manifolds
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Truncated Power Method for Sparse Eigenvalue Problems
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Robust Spectral Compressed Sensing via Structured Matrix Completion
• Self-Calibration and Biconvex Compressive Sensing
• How to Escape Saddle Points Efficiently
• 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
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Incoherence-Optimal Matrix Completion
• A Geometric Analysis of Phase Retrieval
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Nonconvex phase synchronization
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Fast Algorithms for Robust PCA via Gradient Descent
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Recovery Guarantees for One-hidden-layer Neural Networks
• Global Optimality in Low-rank Matrix Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Non-convex Robust PCA
• Near-optimal bounds for phase synchronization
• Efficient approaches for escaping higher order saddle points in non-convex optimization
• A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices
• The Non-convex Geometry of Low-rank Matrix Optimization
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• ROP: Matrix recovery via rank-one projections
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
• Alternating Minimization for Mixed Linear Regression
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• The Power of Normalization: Faster Evasion of Saddle Points
• Spectral MLE: Top-$K$ Rank Aggregation from Pairwise Comparisons
• Neon2: Finding Local Minima via First-Order Oracles
• Phase Retrieval: An Overview of Recent Developments
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
• Fast matrix completion without the condition number
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• Natasha 2: Faster Non-Convex Optimization Than SGD
• Experimental compressive phase space tomography
• Finding a sparse vector in a subspace: Linear sparsity using alternating directions
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Dropping Convexity for Faster Semi-definite Optimization
• Nonconvex Demixing From Bilinear Measurements
• A Selective Overview of Deep Learning
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Phase Retrieval via Incremental Truncated Wirtinger Flow
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• A Non-Convex Blind Calibration Method for Randomised Sensing Strategies
• Composite optimization for robust blind deconvolution
• Stochastic Methods for Composite and Weakly Convex Optimization Problems
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Approximate Message Passing for Amplitude Based Optimization
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization
• Coordinate Descent Algorithms for Phase Retrieval
• Spectral algorithms for tensor completion
• The Likelihood Ratio Test in High-Dimensional Logistic Regression Is Asymptotically a Rescaled Chi-Square
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing

Cited by in corpus (115)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Gridless DOA Estimation and Root-MUSIC for Non-Uniform Arrays
• Harnessing Sparsity over the Continuum: Atomic Norm Minimization for Super Resolution
• Optimization for deep learning: theory and algorithms
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• The Global Landscape of Neural Networks: An Overview
• Exploiting Shared Representations for Personalized Federated Learning
• Implicit Regularization in Deep Matrix Factorization
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• A Riemannian rank-adaptive method for low-rank matrix completion
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Subgradient Descent Learns Orthogonal Dictionaries
• Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• From Symmetry to Geometry: Tractable Nonconvex Problems
• HePPCAT: Probabilistic PCA for Data with Heteroscedastic Noise
• Projected gradient descent for non-convex sparse spike estimation
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Composite optimization for robust blind deconvolution
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Phase Retrieval via Smooth Amplitude Flow
• Estimating Differential Latent Variable Graphical Models with Applications to Brain Connectivity
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning
• Optimization Landscape of Tucker Decomposition
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• SGD_Tucker: A Novel Stochastic Optimization Strategy for Parallel Sparse Tucker Decomposition
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• Solving Complex Quadratic Systems with Full-Rank Random Matrices
• Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Blind Super-resolution of Point Sources via Projected Gradient Descent
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Complete Dictionary Learning via ${\ell }_p$-norm Maximization
• Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• On the computational and statistical complexity of over-parameterized matrix sensing
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Inference for Heteroskedastic PCA with Missing Data
• NoncovANM: Gridless DOA Estimation for LPDF System
• Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method
• Nonconvex Robust Low-rank Matrix Recovery
• Convolutional Geometric Matrix Completion
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Hessian Eigenspectra of More Realistic Nonlinear Models
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Exact Recovery of Community Structures Using DeepWalk and Node2vec
• Efficient Sparse Coding using Hierarchical Riemannian Pursuit
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
• Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
• Optimal tuning-free convex relaxation for noisy matrix completion
• General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• Information-Guided Sampling for Low-Rank Matrix Completion
• Correlating Time Series with Interpretable Convolutional Kernels
• Limitations of Implicit Bias in Matrix Sensing: Initialization Rank Matters
• The nonsmooth landscape of blind deconvolution
• Multiway Spherical Clustering via Degree-Corrected Tensor Block Models
• Sparse GCA and Thresholded Gradient Descent
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Separable Joint Blind Deconvolution and Demixing
• Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization
• Exact matrix completion based on low rank Hankel structure in the Fourier domain
• Low-rank optimization methods based on projected projected-gradient descent that accumulate at Bouligand stationary points
• Rank-one matrix estimation: analytic time evolution of gradient descent dynamics
• Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
• Subquadratic Overparameterization for Shallow Neural Networks
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• Implicit Regularization in Tensor Factorization
• Boundary Defense against Cyber Threat for Power System Operation
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape
• Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Robust Matrix Factorization with Grouping Effect
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• Non-Convex Exact Community Recovery in Stochastic Block Model
• Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reduction
• Non-Convex Structured Phase Retrieval
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
• Analytical Convergence Regions of Accelerated Gradient Descent in Nonconvex Optimization under Regularity Condition
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
• Asymptotic Escape of Spurious Critical Points on the Low-rank Matrix Manifold
• A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning
• The Nonconvex Geometry of Linear Inverse Problems
• Coordinate projected gradient descent minimization and its application to orthogonal nonnegative matrix factorization
• Provable Low Rank Phase Retrieval
• Learning Mixtures of Low-Rank Models
• Proximal Dogleg Opportunistic Majorization for Nonconvex and Nonsmooth Optimization
• Low Rank Regularization: A Review
• Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points
• Locality Sensitive Hash Aggregated Nonlinear Neighbourhood Matrix Factorization for Online Sparse Big Data Analysis
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective
• The radius of statistical efficiency
• Seeded graph matching for the correlated Gaussian Wigner model via the projected power method
• Depth Descent Synchronization in $\mathrm{SO}(D)$
• Nearly Minimal Over-Parametrization of Shallow Neural Networks