Escaping Saddle Points Efficiently with Occupation-Time-Adapted
  Perturbations
  Motivated by the super-diffusivity of self-repelling random walk, which has
roots in statistical physics, this paper develops a new perturbation mechanism
for optimization algorithms. In this mechanism, perturbations are adapted to
the history of states via the notion of occupation time. After integrating this
mechanism into the framework of perturbed gradient descent (PGD) and perturbed
accelerated gradient descent (PAGD), two new algorithms are proposed: perturbed
gradient descent adapted to occupation time (PGDOT) and its accelerated version
(PAGDOT). PGDOT and PAGDOT are shown to converge to second-order stationary
points at least as fast as PGD and PAGD, respectively, and thus they are
guaranteed to avoid getting stuck at non-degenerate saddle points. The
theoretical analysis is corroborated by empirical studies in which the new
algorithms consistently escape saddle points and outperform not only their
counterparts, PGD and PAGD, but also other popular alternatives including
stochastic gradient descent, Adam, AMSGrad, and RMSProp.
