The (1+1)-ES Reliably Overcomes Saddle Points
It is known that step size adaptive evolution strategies (ES) do not converge (prematurely) to regular points of continuously differentiable objective functions. Among critical points, convergence to minima is desired, and convergence to maxima is easy to exclude. However, surprisingly little is known on whether ES can get stuck at a saddle point. In this work we establish that even the simple (1+1)-ES reliably overcomes most saddle points under quite mild regularity conditions. Our analysis is based on drift with tail bounds. It is non-standard in that we do not even aim to estimate hitting times based on drift. Rather, in our case it suffices to show that the relevant time is finite with full probability.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Stabilizing Adversarial Nets With Prediction Methods
Adversarial neural networks solve many important problems in data science, but are notoriously difficult to train. These difficulties come from the fact that optimal weights for adversarial nets correspond to saddle poin…
PredictionType-II Saddles and Probabilistic Stability of Stochastic Gradient Descent
Characterizing and understanding the dynamics of stochastic gradient descent (SGD) around saddle points remains an open problem. We first show that saddle points in neural networks can be divided into two types, among wh…
Learning TheoryHeavy-ball Algorithms Always Escape Saddle Points
Nonconvex optimization algorithms with random initialization have attracted increasing attention recently. It has been showed that many first-order methods always avoid saddle points with random starting points. In this …
A Generic Approach for Escaping Saddle points
A central challenge to using first-order methods for optimizing nonconvex problems is the presence of saddle points. First-order methods often get stuck at saddle points, greatly deteriorating their performance. Typicall…
Second-order methodsSaddlepoints in Unsupervised Least Squares
This paper sheds light on the risk landscape of unsupervised least squares in the context of deep auto-encoding neural nets. We formally establish an equivalence between unsupervised least squares and principal manifolds…
Denoising