Matrix Completion has No Spurious Local Minimum

By Rong Ge, Jason D. Lee, Tengyu Ma. 2016

633 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “Several papers ( e.g. Ge et al. (2015); Lee et al. (2016)) have shown that (given certain smoothness properties) it sufﬁces for critical points to meet the following two conditions: (i) no poor local minima — every local minimum is close in its objective value to a global minimum; and (ii) strict…”
Diverse Neural Network Learns True Target Functions (2016, neutral): “In addition, we will further investigate the issue of designing an algorithm that guarantees good discrepancy thus small errors, possibly in a way similar to [Ge et al., 2016] in low-rank recovery problems.”
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs (2017, background): “These include for example matrix completion (Ge et al., 2016) and tensor decompositions (Ge et al., 2015).”
Learning One-hidden-layer Neural Networks with Landscape Design (2017, methodology): “The optimization landscape has also been analyzed for other machine learning problems, including SVD/PCA phase retrieval/synchronization, orthogonal tensor decomposition, dictionary learning, matrix completion, matrix sensing [BH89, SJ13, GHJY15, SQW15, BBV16, GLM16, BNS16, GJZ17].”
Implicit Regularization in Matrix Factorization (2017, background): “This is not surprising since with large enough d this non-convex problem has no spurious local minima [4, 9] and gradient descent converges almost surely to a global optima [12]; there has also been recent work establishing conditions for global convergence for low d [3, 7].”
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks (2017, methodology): “…as phase retrieval, matrix completion, dictionary learning, and tensor decomposition, do not have spurious local minima under suitable assumptions, in which case local search methods have a chance of succeeding (e.g., [Ge et al., 2015, Sun et al., 2015, Ge et al., 2016, Bhojanapalli et al., 2016]).”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, background): “…al., 2015], dictionary learning [Sun et al., 2017], phase retrieval [Sun et al., 2016], matrix sensing [Bhojanapalli et al., 2016, Park et al., 2017], matrix completion [Ge et al., 2017a, 2016] and matrix factorization [Li et al., 2016] can be solved in polynomial time with local search algorithms.”
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (2017, background): “…for learning multi-layer neural networks, Bandeira et al. [2016], Mei et al. [2017] for synchronization and MaxCut, Boumal et al. [2016] for smooth semideﬁnite programs, Bhojanapalli et al. [2016] for matrix sensing, Ge et al. [2016] for matrix completion, and Ge et al. [2017] for robust PCA.”
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, background): “Notice that our proof is different from (Ge et al., 2016), as we focus on the direction ∆ for both first and second order conditions while they need to select different directions for the Hessian.”
Non-convex Optimization for Machine Learning (2017, background): “Another interesting line of work for matrix completion is that of [Ge et al., 2016, Sun and Lu, 2015] which shows that under certain regularization assumptions, the matrix completion problem does not have any non-optimal stationary points once one gets close-enough to the global minimum.”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, background): “In several problems [40,48,49,75,77,86,87,105,106], it is further suggested that the optimization landscape is benign under sufficiently large sample complexity, in the sense that all local minima are globally optimal, and hence nonconvex iterative algorithms become promising in solving such problem”
The Power of Normalization: Faster Evasion of Saddle Points (2016, background): “Recently, a stochastic version of NGD was explored in the context of stochastic quasi-convex optimization, Hazan et al. (2015).”
Global rates of convergence for nonconvex optimization on manifolds (2016, positive): “See for example (Sun et al., 2017a,b; Boumal, 2015b, 2016; Bandeira et al., 2016; Bhojanapalli et al., 2016; Ge et al., 2016) and the example in Section 4.”
On critical points of quadratic low-rank matrix optimization problems (2020, background): “Such remarkable properties have been rigorously proven under suitable assumptions for different low-rank optimization problems like matrix sensing [4, 23], matrix completion [34, 14], general convex functions on M≤k [18, 41], SDPs [6, 7], and also for some other problems in the context of compressed”
Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations (2017, neutral): “, see [36, 15, 3, 14, 13, 39] and references therein).”
Collapse of Deep and Narrow Neural Nets (2018, background): “Under various assumptions, especially on the landscape, many results claim that the gradient method can find a global minimum, can escape saddle points, and can avoid spurious local minima [2, 8–10, 13, 14, 25, 32, 52, 55, 57].”
Knowledge Graph Completion via Complex Tensor Factorization (2017, background): “Recent results show that there are no spurious local minima in the completion problem of positive semi-definite matrix (Ge et al., 2016; Bhojanapalli et al., 2016).”
Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization (2021, background): “Du et al. [2018] further uses a geometric result (all saddle points in the objective function are strict and all local minima are global minima [Ge et al., 2015, 2017b, 2016, Li et al., 2019b]), and then invokes the stable manifold theorem to show the global convergence of gradient ﬂow [Lee et al.,…”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “The optimization landscape for matrix completion was pioneered by [30], and later improved by [143], [144].”
Implicit Regularization in Deep Matrix Factorization (2019, background): “These questions were studied extensively for matrix factorization — cf. [17, 6, 39, 18] — and more recently for linear neural networks of arbitrary depth — see [5, 3, 4, 14].”