Global Optimality of Local Search for Low Rank Matrix Recovery

By Srinadh Bhojanapalli, Behnam Neyshabur, Nati Srebro. Neural Information Processing Systems, 2016

412 citations recorded by the source corpus.

We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial time global convergence guarantee for stochastic gradient descent {\em from random initialization}.

Subfields: Biomedical Engineering, Computational Mechanics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/4a4ba96debb9719766830c419ca01e14cb465b83

How researchers see this paper

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

In Biomedical Engineering

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

Algorithmic Regularization in Over-parameterized Matrix Recovery (2017, background): “The recent work of Ge et al. [12] and Bhojanapalli et al. [2] shows that the non-convex objectives on matrix completion and matrix sensing with low-rank parameterization don’t have any spurious local minima, and stochastic gradient descent algorithm on them converges to the global minimum.”
Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path? (2018, methodology): “Some of this literature apply to regression problems as well (such as low-rank regression (Bhojanapalli et al., 2016; Boumal et al., 2016; Burer & Monteiro, 2003; Li et al., 2018)).”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, background): “…non-convex objective functions whose landscape satisﬁes “no spurious local minima” property [Li et al., 2016, Sun et al., 2016, Ge et al., 2017a, 2016, Bhojanapalli et al., 2016, Ge et al., 2017b], our result highlights a conceptually surprising phenomenon: Randomly initialized local search can…”
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].”
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.”
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).”
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, background): “, 2015a], matrix sensing [Bhojanapalli et al., 2016, Park et al., 2016] and matrix completion [Ge et al., 2016] have well-behaved optimization landscape: all local optima are also globally optimal. Combined with recent results (e.g. Ge et al. [2015], Carmon et al. [2016], Agarwal et al. [2016], Jin ”
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”
The non-convex geometry of low-rank matrix optimization (2016, background): “5 ⇐⇒ δ4r ∈ [ 0, 1 5 ] .”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, background): “There is a growing list of statistical estimation problems for which nonconvex approaches are guaranteed to find global optimal solutions, including but not limited to phase retrieval [18,25,90], low-rank matrix sensing and completion [7,32,48,115,130], blind deconvolution and self-calibration [72,7”
Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile (2018, background): “For example, the well-known “strict saddle” property was shown to hold in a wide range of salient objective functions ranging from low-rank matrix factorization (Bhojanapalli et al., 2016; Ge et al., 2017, 2016) and dictionary learning (Sun et al.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “This work inspired the line of global geometric analysis for many aforementioned problems, including phase retrieval [28], [90], matrix sensing [31], [32], [143], [153], [154], matrix completion [30], [32], [143], [144], robust PCA [143], M-estimation [155].”
An Analysis of the t-SNE Algorithm for Data Visualization (2018, background): “Researchers have managed to rigorously analyze non-convex optimization algorithms in a host of settings (Dasgupta, 1999; Arora et al., 2012, 2014; Bhojanapalli et al., 2016; Ge et al., 2015a; Sun et al., 2017; Ge et al., 2017, 2016; Park et al., 2017).”
Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations (2017, background): “[3] shows that the non-convex objectives on matrix completion and matrix sensing with low-rank parameterization don’t have any spurious local minima, and stochastic gradient descent algorithm on them converges to the global minimum.”
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].”
How to Escape Saddle Points Efficiently (2017, background): “In many real applications, objective functions further admit the property that all saddle points are strict [Ge et al., 2015, Sun et al., 2016a,b, Bhojanapalli et al., 2016, Ge et al., 2016].”
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]).”
Dynamics of Deep Neural Networks and Neural Tangent Hierarchy (2019, result): “A line of recent results show that, in many optimization problems of interest (Ge et al., 2015; 2016; Sun et al., 2018; 2016; Bhojanapalli et al., 2016; Park et al., 2016), loss landscapes are in such class.”