Matrix Completion has No Spurious Local Minimum

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.

• Publication year

  2016

• Venue

  Neural Information Processing Systems

• Publication date

  2016-05-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1605.07272
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent

  2016cited by this paper
• On the low-rank approach for semidefinite programs arising in synchronization and community detection

  2016cited by this paper
• Recovery guarantee of weighted low-rank approximation via alternating minimization

  2016cited by this paper
• Global Optimality of Local Search for Low Rank Matrix Recovery

  2016cited by this paper
• Gradient Descent Converges to Minimizers

  2016cited by this paper
• When Are Nonconvex Problems Not Scary?

  2015cited by this paper
• Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition

  2015influential reference
• A Nonconvex Optimization Framework for Low Rank Matrix Estimation

  2015cited by this paper
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

  2015cited by this paper
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees

  2015cited by this paper
• Guaranteed Matrix Completion via Non-Convex Factorization

  2014influential reference
• Matrix completion and low-rank SVD via fast alternating least squares

  2014cited by this paper
• Fast matrix completion without the condition number

  2014cited by this paper
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems

  2014cited by this paper
• Fast Exact Matrix Completion with Finite Samples

  2014cited by this paper
• Support recovery without incoherence: A case for nonconvex regularization

  2014cited by this paper
• Understanding Alternating Minimization for Matrix Completion

  2013cited by this paper
• Regularized M-estimators with nonconvexity: statistical and algorithmic theory for local optima

  2013cited by this paper
• Low-rank matrix completion using alternating minimization

  2012cited by this paper
• 1-Bit Matrix Completion

  2012cited by this paper
• A tail inequality for quadratic forms of subgaussian random vectors

  2011cited by this paper
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise

  2010cited by this paper
• Sums of random Hermitian matrices and an inequality by Rudelson

  2010cited by this paper
• Spectral Regularization Algorithms for Learning Large Incomplete Matrices

  2010cited by this paper
• A Simpler Approach to Matrix Completion

  2009influential reference
• The Power of Convex Relaxation: Near-Optimal Matrix Completion

  2009cited by this paper
• Matrix Completion from Noisy Entries

  2009cited by this paper
• The BellKor Solution to the Netflix Grand Prize

  2009cited by this paper
• Matrix completion from a few entries

  2009cited by this paper
• Robust principal component analysis?

  2009cited by this paper
• Exact Matrix Completion via Convex Optimization

  2008cited by this paper
• Uncovering shared structures in multiclass classification

  2007cited by this paper
• Cubic regularization of Newton method and its global performance

  2006cited by this paper
• Rank, Trace-Norm and Max-Norm

  2005cited by this paper
• Fast maximum margin matrix factorization for collaborative prediction

  2005cited by this paper
• Maximum-Margin Matrix Factorization

  2004cited by this paper
• Weighted Low-Rank Approximations

  2003cited by this paper
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

  2003cited by this paper
• Nonconvergence to Unstable Points in Urn Models and Stochastic Approximations

  1990cited by this paper
• Neural networks and principal component analysis: Learning from examples without local minima

  1989cited by this paper

• Continuized Nesterov Momentum Achieves the $O(\varepsilon^{-7/4})$ Complexity without Additional Mechanisms

  2026cites this paper
• cuFastTuckerPlusTC: A Stochastic Parallel Sparse FastTucker Decomposition Using GPU Tensor Cores

  2026cites this paper
• Improved Global Landscape Guarantees for Low-rank Factorization in Synchronization

  2026cites this paper
• One-Sided Matrix Completion from Ultra-Sparse Samples

  2026influential citation
• Acceleration for Polyak-{\L}ojasiewicz Functions with a Gradient Aiming Condition

  2026cites this paper
• Second-order methods for provably escaping strict saddle points in composite nonconvex and nonsmooth optimization

  2025cites this paper
• Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization

  2025cites this paper
• Burer-Monteiro factorizability of nuclear norm regularized optimization

  2025cites this paper
• Unmixing of Imaging Mass Spectrometry Measurements Using Microscopy-Informed Constraints

  2025cites this paper
• Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent

  2025cites this paper
• On the stability properties of gradient flow dynamics for a symmetric low-rank matrix factorization problem

  2025cites this paper
• Degree-of-freedom and optimization-dynamic effects on the observability of Kuramoto-Sivashinsky systems

  2025cites this paper
• Escaping Saddle Point Efficiently in Minimax and Bilevel Optimizations

  2025cites this paper
• Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima

  2025cites this paper
• Group-Sparse Inductive Matrix Completion Through Transfer Learning

  2025cites this paper
• Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings

  2025cites this paper
• Scalable Second-order Riemannian Optimization for K-means Clustering

  2025cites this paper
• Temporal Functional Factor Analysis of Brain Connectivity

  2025cites this paper
• On a spherically lifted spin model at finite temperature

  2025cites this paper
• k-SVD with Gradient Descent

  2025influential citation
• Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent

  2025cites this paper
• Balancing Gradient and Hessian Queries in Non-Convex Optimization

  2025cites this paper
• A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression

  2025cites this paper
• Automatic Rank Determination for Low-Rank Adaptation via Submodular Function Maximization

  2025cites this paper
• Dynamics of Learning: Generative Schedules from Latent ODEs

  2025cites this paper
• Sensor network localization has a benign landscape after low-dimensional relaxation

  2025influential citation
• Smooth Quasar-Convex Optimization with Constraints

  2025cites this paper
• A Unified Theory of Sparse Dictionary Learning in Mechanistic Interpretability: Piecewise Biconvexity and Spurious Minima

  2025cites this paper
• Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization

  2025cites this paper
• Analyzing the Role of Permutation Invariance in Linear Mode Connectivity

  2025cites this paper
• Continuized Nesterov Acceleration for Non-Convex Optimization

  2025cites this paper
• The Adaptive Complexity of Finding a Stationary Point

  2025cites this paper
• Matrix Completion via Residual Spectral Matching

  2024cites this paper
• Accelerated Scaled Gradient Descent Algorithm For Low-Rank Matrix Factorization

  2024cites this paper
• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization

  2024cites this paper
• Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problem

  2024cites this paper
• Asymptotic dynamics of alternating minimization for bilinear regression

  2024cites this paper
• Novel Optimization Techniques for Parameter Estimation

  2024cites this paper
• Lecture Notes on Linear Neural Networks: A Tale of Optimization and Generalization in Deep Learning

  2024cites this paper
• Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity

  2024cites this paper
• On Newton's Method to Unlearn Neural Networks

  2024cites this paper
• $\ell_1$-norm rank-one symmetric matrix factorization has no spurious second-order stationary points

  2024cites this paper
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms

  2024cites this paper
• Preparing for Black Swans: The Antifragility Imperative for Machine Learning

  2024cites this paper
• cuFastTuckerPlus: A Stochastic Parallel Sparse FastTucker Decomposition Using GPU Tensor Cores

  2024cites this paper
• Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptation

  2024cites this paper
• Riemannian trust-region methods for strict saddle functions with complexity guarantees

  2024influential citation
• Exploring Neural Network Landscapes: Star-Shaped and Geodesic Connectivity

  2024cites this paper
• Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing

  2024cites this paper
• LoRA Training in the NTK Regime has No Spurious Local Minima

  2024influential citation
• Implicit Regularization via Spectral Neural Networks and Non-linear Matrix Sensing

  2024cites this paper
• How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization

  2024cites this paper
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction

  2024cites this paper
• Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscape

  2024cites this paper
• Symmetric Matrix Completion with ReLU Sampling

  2024cites this paper
• Noise is All You Need: Private Second-Order Convergence of Noisy SGD

  2024cites this paper
• The Probabilistic Stability of Stochastic Gradient Descent

  2023cites this paper
• Preconditioning Matters: Fast Global Convergence of Non-convex Matrix Factorization via Scaled Gradient Descent

  2023cites this paper
• Finding Local Minima Efficiently in Decentralized Optimization

  2023cites this paper
• ON THE ASYMPTOTIC LINEAR CONVERGENCE OF GRADIENT DESCENT FOR NON-SYMMETRIC MATRIX COMPLETION

  2023cites this paper
• Wave Physics-Informed Matrix Factorizations

  2023cites this paper
• The Local Landscape of Phase Retrieval Under Limited Samples

  2023cites this paper
• Local Geometry Determines Global Landscape in Low-rank Factorization for Synchronization

  2023cites this paper
• The Law of Parsimony in Gradient Descent for Learning Deep Linear Networks

  2023cites this paper
• Adaptive thresholding for iterative matrix completion with heterogeneous missing probability: H-AdaptiveImpute

  2023cites this paper
• Are Graph Neural Networks Optimal Approximation Algorithms?

  2023cites this paper
• Geometric Analysis of Matrix Sensing over Graphs

  2023cites this paper
• Fermionic Reduced Density Low-Rank Matrix Completion, Noise Filtering, and Measurement Reduction in Quantum Simulations

  2023cites this paper
• One-sided Matrix Completion from Two Observations Per Row

  2023cites this paper
• Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learning

  2023cites this paper
• Global stability of first-order methods for coercive tame functions

  2023cites this paper
• Reconstruction of Randomly Sampled Quantum Wavefunctions using Tensor Methods

  2023cites this paper
• Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles

  2023cites this paper
• Global Optimality in Bivariate Gradient-based DAG Learning

  2023cites this paper
• Quantum speedups for stochastic optimization

  2023cites this paper
• Matrix Completion in Almost-Verification Time

  2023cites this paper
• Time-Variation in Online Nonconvex Optimization Enables Escaping From Spurious Local Minima

  2023cites this paper
• expOSE: Accurate Initialization-Free Projective Factorization using Exponential Regularization

  2023cites this paper
• Accelerated Stochastic Optimization Methods under Quasar-convexity

  2023cites this paper
• Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensing and Neural Networks with Quadratic Activations

  2023cites this paper
• The essential best and average rate of convergence of the exact line search gradient descent method

  2023cites this paper
• Can Learning Be Explained by Local Optimality in Robust Low-Rank Matrix Recovery?

  2023cites this paper
• Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing

  2023cites this paper
• Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models

  2023cites this paper
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization

  2023cites this paper
• Disjunctive Branch-And-Bound for Certifiably Optimal Low-Rank Matrix Completion

  2023cites this paper
• A Momentum Accelerated Adaptive Cubic Regularization Method for Nonconvex Optimization

  2022cites this paper
• Are All Losses Created Equal: A Neural Collapse Perspective

  2022cites this paper
• A Validation Approach to Over-parameterized Matrix and Image Recovery

  2022cites this paper
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks

  2022cites this paper
• A Unified Complexity Metric for Nonconvex Rank-one Generalized Matrix Completion

  2022cites this paper
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization

  2022cites this paper
• Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition

  2022influential citation
• Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion

  2022cites this paper
• Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization

  2022cites this paper
• Guarantees for Spontaneous Synchronization on Random Geometric Graphs

  2022cites this paper
• Simple Alternating Minimization Provably Solves Complete Dictionary Learning

  2022cites this paper
• Preconditioned Gradient Descent for Overparameterized Nonconvex Burer-Monteiro Factorization with Global Optimality Certification

  2022cites this paper
• Faster Rates of Convergence to Stationary Points in Differentially Private Optimization

  2022cites this paper
• Identifying good directions to escape the NTK regime and efficiently learn low-degree plus sparse polynomials

  2022cites this paper