Back to Search
Start Over
Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points.
- Source :
- IEEE Transactions on Automatic Control; Nov2019, Vol. 64 Issue 11, p4818-4824, 7p
- Publication Year :
- 2019
-
Abstract
- The paper considers normalized gradient descent (NGD), a natural modification of classical gradient descent (GD) in optimization problems. It is shown that, contrary to GD, NGD escapes saddle points “quickly.” A serious shortcoming of GD in nonconvex problems is that it can take arbitrarily long to escape from the neighborhood of a saddle point. In practice, this issue can significantly slow the convergence of GD, particularly in high-dimensional nonconvex problems. The paper focuses on continuous-time dynamics. It is shown that 1) NGD “almost never” converges to saddle points and 2) the time required for NGD to escape from a ball of radius $r$ about a saddle point $x^*$ is at most $5\sqrt{\kappa }r$ , where $\kappa$ is the condition number of the Hessian of $f$ at $x^*$. As a simple application of these results, a global convergence-time bound is established for NGD under mild assumptions. [ABSTRACT FROM AUTHOR]
- Subjects :
- SADDLERY
LINEAR programming
NOISE measurement
RADIO frequency
Subjects
Details
- Language :
- English
- ISSN :
- 00189286
- Volume :
- 64
- Issue :
- 11
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Automatic Control
- Publication Type :
- Periodical
- Accession number :
- 139437758
- Full Text :
- https://doi.org/10.1109/TAC.2019.2914998