Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points

DOI10.1109/TAC.2019.2914998MaRDI QIDQ5211250zbMATH OpenOpenAlexWikidataFDO

Authors Brian Swenson, Soummya Kar, Ryan W. Murray

Publication date 28 January 2020

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.05224

Mathematics Subject Classification ID

Asymptotic properties of solutions to ordinary differential equations (34D05) Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26)

Abstract: The note considers normalized gradient descent (NGD), a natural modification of classical gradient descent (GD) in optimization problems. A serious shortcoming of GD in non-convex problems is that GD may take arbitrarily long to escape from the neighborhood of a saddle point. This issue can make the convergence of GD arbitrarily slow, particularly in high-dimensional non-convex problems where the relative number of saddle points is often large. The paper focuses on continuous-time descent. It is shown that, contrary to standard GD, NGD escapes saddle points `quickly.' In particular, it is shown that (i) NGD `almost never' converges to saddle points and (ii) the time required for NGD to escape from a ball of radius $r$ about a saddle point $x^{\ast }$ is at most $5sqrtkappar$, where $kappa$ is the condition number of the Hessian of $f$ at $x^{\ast }$. As an application of this result, a global convergence-time bound is established for NGD under mild assumptions.

Cited in

(8)

• Robust preconditioned one-shot methods and direct-adjoint-looping for optimizing Reynolds-averaged turbulent flows
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
• scientific article; zbMATH DE number 7742927 (Why is no real title available?)
• A universal quantum algorithm for weighted maximum cut and Ising problems
• Continuous trajectory planning for non-convex utility functions using hybrid optimization
• Adversarial flows: a gradient flow characterization of adversarial attacks
• Asymptotic analysis of the Ruppert-Polyak averaging for stochastic order oracle

This page was built for publication: Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211250)