The (1+1)-ES Reliably Overcomes Saddle Points
This addresses a theoretical gap in optimization algorithms for researchers, providing foundational insights into convergence behavior, though it is incremental as it builds on known properties of ES.
The paper tackles the problem of whether step size adaptive evolution strategies can get stuck at saddle points, and establishes that the simple (1+1)-ES reliably overcomes most saddle points under mild regularity conditions.
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.