Gradient Descent Only Converges to Minimizers

By Jason D. Lee, Max Simchowitz, Michael I. Jordan, B. Recht. 2016

646 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

fPINNs: Fractional Physics-Informed Neural Networks (2018, background): “There are multiple local minima for the loss function, and the gradient-based optimizer almost surely gets stuck in one of the local minima [61]; finding global minima is a NP-hard problem [62, 63].”
Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs (2018, background): “[14] showed that under mild conditions gradient descent almost surely converges to a local minimizer and not a saddle point, starting from a random initialization.”
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…”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “The hope is to leverage recent advance in first-order algorithms (Ge et al., 2015; Lee et al., 2016; Jin et al., 2017) which showed that if the landscape satisfies (1) all local minima are global and (2) all saddle points are strict (i.”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, methodology): “Algorithms that provably work in this setting include cubic regularization [36], trust region methods [16], approximate cubic regularization schemes [3], [12], [13], randomly initialized and perturbed (stochastic) gradients [17], [22], [22], [29], [30].”
Spectral Norm Regularization for Improving the Generalizability of Deep Learning (2017, background): “SGD can reach a local minimum with high probability over the selection of the starting point [23], and all local minima attain similar loss values [4, 8, 17].”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “For this function class, researchers have shown (perturbed) gradient descent (Jin et al., 2017; Ge et al., 2015; Lee et al., 2016; Du et al., 2017a) can find a global minimum.”
Few-Shot Learning via Learning the Representation, Provably (2020, background): “Therefore, randomly initialized gradient descent or perturbed gradient descent are guaranteed to converge to a global minimum of (16) in polynomial-time (Ge et al., 2015, Lee et al., 2016, Jin et al., 2017).”
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs (2017, background): “4 Therefore, recent methods for showing global convergence of gradient-based optimizers on non-convex objectives (Lee et al., 2016; Ge et al., 2015) cannot be used in our case, because they assume all saddles are strict 5 and the objective function is continuously diﬀerentiable everywhere.”
Implicit Regularization in Matrix Factorization (2017, background): “…has no spurious local minima (Burer and Monteiro, 2003; Journée et al., 2010) and gradient descent converges almost surely to a global optima (Lee et al., 2016); there has also been recent work establishing conditions for global convergence for low d (Bhojanapalli et al., 2016; Ge et al.,…”
Gradient Descent with Identity Initialization Efficiently Learns Positive-Definite Linear Transformations by Deep Residual Networks (2018, background): “rks in the presence of a weight decay regularizer; they studied networks that transform the input to the output through a process indexed by a continuous variable, instead of through discrete layers. Lee et al. (2016) showed that, given regularity conditions, for a random initialization, gradient de”
Implicit Bias of Gradient Descent on Linear Convolutional Networks (2018, background): “…sufﬁcient over-parameterization (as is the case with our settings), loss landscape of linear models are well behaved and all local minima are global minima making the problem tractable Burer and Monteiro [2003], Journée et al. [2010], Kawaguchi [2016], Nguyen and Hein [2017], Lee et al. [2016].”
Stochastic Gradient Descent Performs Variational Inference, Converges to Limit Cycles for Deep Networks (2017, background): “SGD and noise: Noise is often added in SGD to improve its behavior around saddle points for non-convex losses, see Lee et al. (2016); Anandkumar and Ge (2016); Ge et al. (2015).”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, background): “, a global minimum of the training loss [8], [10].”
On the energy landscape of deep networks (2015, methodology): “However, the mini-batch gradient often does not have high variance in all directions which necessitates additional gradient noise (Jim et al., 1996; Nalisnick et al., 2015) and makes SGD highly dependent on the dimensionality (Lee et al., 2016).”
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions (2017, background): “ion (Nocedal and Wright, 2006), and while saddle points and local maxima are stationary, excepting pathological cases, descent methods that converge to a stationary point converge to a local minimum (Lee et al., 2016; Nemirovski, 1999, x3.2.2). If we assume fis convex, gradient descent satises the b”
Accelerated Methods for Non-Convex Optimization (2016, background): “[18] show that GD generically converges to second-order local optima.”