No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis

By Rong Ge, Chi Jin, Yi Zheng. 2017

478 citations recorded by the source corpus.

In this paper we develop a new framework that captures the common landscape underlying the common non-convex low-rank matrix problems including matrix sensing, matrix completion and robust PCA. In particular, we show for all above problems (including asymmetric cases): 1) all local minima are also globally optimal; 2) no high-order saddle points exists. These results explain why simple algorithms such as stochastic gradient descent have global converge, and efficiently optimize these non-convex objective functions in practice. Our framework connects and simplifies the existing analyses on optimization landscapes for matrix sensing and symmetric matrix completion. The framework naturally leads to new results for asymmetric matrix completion and robust PCA.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

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 Numerical Analysis

Citations in the corpus

Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions (2022, background): “spectral initialization [7]) or adding a regularization term that enforces smoothness [12], none of which are applicable in our setting.”
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].”
How to Start Training: The Effect of Initialization and Architecture (2018, background): “…distinguish two kinds: problems that prevent a given neural network from ever achieving better-than-chance performance and problems that have to do with later stages of training, such as escaping ﬂat regions and saddle points [12, 27], reaching spurious local minima [5, 15], and overﬁtting [2, 34].”
Gradient Descent with Identity Initialization Efficiently Learns Positive-Definite Linear Transformations by Deep Residual Networks (2018, background): “For an interesting survey on the rich literature on these algorithms, please see Ge et al. (2017a); successful algorithms have included a regularizer that promotes balance in the sizes of U and V .”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, background): “…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 ﬁnd a global minimum in…”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, methodology): “In [Tu et al., 2015, Ge et al., 2017a], a regularization term for balancing the two layers is added to (1): min UPRd1ˆr,V PRd2ˆr 1 2 › ›UV J ´M › › 2 F ` 1 8 › ›UJU ´ V JV › › 2 F .”
Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization (2021, background): “To deal with the non-smooth problem, they also added a balancing regularization term [Park et al., 2017, Tu et al., 2016, Ge et al., 2017a, Li et al., 2019b k − k F to the objective function to ensure balancedness between U and V throughout the optimization process.”
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; Bho-janapalli et al., 2016; Ge et al., 2015a; Sun et al., 2017; Ge et al., 2017, 2016; Park et al., 2017).”
Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes (2019, background): “For example, (Ge et al., 2017b) proved convergence of GD on a modified loss; (Shamir, 2018) compared optimization properties of residual networks with respect to linear models; in (Dauphin et al., 2014) it is argued that the issues arising in the optimization of NN architectures are due to the…”
Learning Two-layer Neural Networks with Symmetric Inputs (2018, background): “Ge et al. (2017b) gave a new and more complicated objective function that does not have bad local minima.”
Minmax Optimization: Stable Limit Points of Gradient Descent Ascent are Locally Optimal (2019, background): “Ge et al. [2015] and Jin et al. [2017] show that with a small amount of randomness gradient descent also converges to second-order stationary points and give nonasymptotic rates of convergence.”
The non-convex geometry of low-rank matrix optimization (2016, background): “In particular, Claim 1 and (1.2) indicate that when β α > 3, the spurious local minima will occur for the weighted PCA in (1.1).”
Stochastic Cubic Regularization for Fast Nonconvex Optimization (2017, methodology): “The work of Nesterov and Polyak [2006] first proposed the cubic-regularized Newton method, which requires O(✏ 1.”
On critical points of quadratic low-rank matrix optimization problems (2020, unknown): “See also Ge et al. (2017) for an overview.”
Algorithmic Regularization in Over-parameterized Matrix Recovery (2017, background): “Such a phenomenon was long known for the PCA problem and recently shown for phase retrieval, robust PCA, and random tensor decomposition as well (e.g., see [28, 12, 2, 11, 10, 30] and reference therein).”
Deep Learning is Robust to Massive Label Noise (2017, background): “(Shalev-Shwartz et al., 2017; Jin et al., 2017; Kawaguchi, 2016; Ge et al., 2017)) that the space of networks has abundant hard-to-escape saddle points, flat regions, and local optima; therefore, it might be supposed that too many erroneous steps could lead to a part of the space from which further ”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “Many applications require solving a constrained quadratic maximization (or constrained PCA) problem: maximize f(x) = x>Lx, (92a) subject to x ∈ C, (92b) where C encodes the set of feasible points.”