Matrix Completion has No Spurious Local Minimum

Abstract

Matrix completion is a basic machine learning problem that has wide applications, especially in collaborative filtering and recommender systems. Simple non-convex optimization algorithms are popular and effective in practice. Despite recent progress in proving various non-convex algorithms converge from a good initial point, it remains unclear why random or arbitrary initialization suffices in practice. We prove that the commonly used non-convex objective function for \textit{positive semidefinite} matrix completion has no spurious local minima --- all local minima must also be global. Therefore, many popular optimization algorithms such as (stochastic) gradient descent can provably solve positive semidefinite matrix completion with \textit{arbitrary} initialization in polynomial time. The result can be generalized to the setting when the observed entries contain noise. We believe that our main proof strategy can be useful for understanding geometric properties of other statistical problems involving partial or noisy observations.

NIPS'16 best student paper. fixed Theorem 2.3 in preliminary section in the previous version. The results are not affected

References in corpus (4)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Gradient Descent Converges to Minimizers
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Fast matrix completion without the condition number

Cited by in corpus (72)

• Global Optimality of Local Search for Low Rank Matrix Recovery
• 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
• Learning One-hidden-layer Neural Networks with Landscape Design
• An Analysis of the t-SNE Algorithm for Data Visualization
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Depth Creates No Bad Local Minima
• The Power of Normalization: Faster Evasion of Saddle Points
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Knowledge Graph Completion via Complex Tensor Factorization
• Introduction to Nonnegative Matrix Factorization
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
• Generalization Bounds for Convolutional Neural Networks
• Homotopy Analysis for Tensor PCA
• Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Optimization Landscape of Tucker Decomposition
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• Finding Local Minima via Stochastic Nested Variance Reduction
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• An Unconstrained Layer-Peeled Perspective on Neural Collapse
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap
• Maximum likelihood estimation of determinantal point processes
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Nonconvex Robust Low-rank Matrix Recovery
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization
• Entropy Penalized Semidefinite Programming
• Matrix Completion and Related Problems via Strong Duality
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• The Global Optimization Geometry of Shallow Linear Neural Networks
• Simple and practical algorithms for ${\ell }_p$-norm low-rank approximation
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• Fast Convergence for Langevin Diffusion with Manifold Structure
• The Landscape of Matrix Factorization Revisited
• Unique Sharp Local Minimum in ${\ell }_1$-minimization Complete Dictionary Learning
• Binary Matrix Completion Using Unobserved Entries
• A Unified Convergence Analysis of the Multiplicative Update Algorithm for Regularized Nonnegative Matrix Factorization
• Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method
• Distributed Gradient Methods for Nonconvex Optimization: Local and Global Convergence Guarantees
• Understanding Notions of Stationarity in Non-Smooth Optimization
• Streaming Principal Component Analysis From Incomplete Data
• How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?
• On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• PCA by Determinant Optimization has no Spurious Local Optima
• Proximal algorithms for constrained composite optimization, with applications to solving low-rank SDPs
• A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points
• Using Negative Curvature in Solving Nonlinear Programs
• Convergence Rates of Inertial Splitting Schemes for Nonconvex Composite Optimization
• Error bound of critical points and KL property of exponent $1/2$ for squared F-norm regularized factorization
• Depth Descent Synchronization in $\mathrm{SO}(D)$
• How Much Are You Willing to Share? A "Poker-Styled" Selective Privacy Preserving Framework for Recommender Systems
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• Uncertainty Quantification For Low-Rank Matrix Completion With Heterogeneous and Sub-Exponential Noise
• Maximin Optimization for Binary Regression