Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions

By Ioannis Panageas, Georgios Piliouras. 2016

160 citations recorded by the source corpus.

Given a non-convex twice differentiable cost function f , we prove that the set of initial conditions so that gradient descent converges to saddle points where ∇f has at least one strictly negative eigenvalue has (Lebesgue) measure zero, even for cost functions f with non-isolated critical points, answering an open question in [12]. Moreover, this result extends to forward-invariant convex subspaces, allowing for weak (non-globally Lipschitz) smoothness assumptions. Finally, we produce an upper bound on the allowable step-size.

Subfields: Applied Mathematics, Orthopedics and Sports Medicine, Surgery

How researchers see this paper

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

In Applied Mathematics

In Orthopedics and Sports Medicine

In Surgery

Citations in the corpus

Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond (2016, background): “One such step has been taken in Panageas & Piliouras (2016) in relaxing the isolated singularity condition that was assumed in Lee et al. (2016).”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, methodology): “…are perturbed, (ii) all saddle points and local maxima are strict (i.e., there exists a direction with negative curvature), and (iii) all local minima are global (no spurious local minimum), then gradient descent [Lee et al., 2016, Panageas and Piliouras, 2016] converges to a global minimum.”
A Geometric Analysis of Phase Retrieval (2016, unknown): “Examples include the noisy gradient and stochastic gradient methods [44] (see also [66,83]), curvilinear search [47] and trust-region methods [37,75,97].”
Empirical Analysis of the Hessian of Over-Parametrized Neural Networks (2017, background): “A relaxation of the above convergence to the case of non-isolated critical points can be found in [Panageas and Piliouras, 2016].”
Stable Opponent Shaping in Differentiable Games (2018, background): “Convergence has widely been studied in convex n-player games, see especially Rosen (1965); Facchinei & Kanzow (2007). However, the recent success of non-convex games exemplified by GANs calls for a better understanding of this general class where comparatively little is known.”
Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization (2021, background): “…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., 2016, Panageas and Piliouras, 2016].”
Generalization Error Bounds for Optimization Algorithms via Stability (2016, background): “The following theorem gives the expected generalization error bound for nonconvex cases under the widely used assumptions (Lian et al. 2015; Reddi et al. 2016; Lee et al. 2016; Panageas and Piliouras 2016).”
Ellipsoidal Trust Region Methods and the Marginal Value of Hessian Information for Neural Network Training (2019, background): “[62] Ioannis Panageas and Georgios Piliouras.”
Singularity of the Hessian in Deep Learning (2016, background): “One such step has been taken in Panageas & Piliouras (2016) in relaxing the isolated singularity condition that was assumed in Lee et al. (2016).”
The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization (2018, background): “…we get where the Hessian of f is given by It suﬃces to show that the matrix below does not have an eigenvalue that is equal to − 1 /α (by just subtracting the identity matrix), It is easy to see that If the function ∇ f is L-Lipschitz, it follows that (cid:13)(cid:13) ∇ 2 f 2 ≤ L (Lemma 6 in [18]).”
Minmax Optimization: Stable Limit Points of Gradient Descent Ascent are Locally Optimal (2019, background): “Lee et al. [2016] and Panageas and Piliouras [2016] show that gradient descent converges to only these points with probability one.”