Accelerated gradient methods for nonconvex optimization: Escape
  trajectories from strict saddle points and convergence to local minima
Rishabh Dixit Mert Gurbuzbalaban Waheed U. Bajwa
This paper considers the problem of understanding the behavior of a general
class of accelerated gradient methods on smooth nonconvex functions. Motivated
by some recent works that have proposed effective algorithms, based on Polyak's
heavy ball method and the Nesterov accelerated gradient method, to achieve
convergence to a local minimum of nonconvex functions, this work proposes a
broad class of Nesterov-type accelerated methods and puts forth a rigorous
study of these methods encompassing the escape from saddle-points and
convergence to local minima through a both asymptotic and a non-asymptotic
analysis. In the asymptotic regime, this paper answers an open question of
whether Nesterov's accelerated gradient method (NAG) with variable momentum
parameter avoids strict saddle points almost surely. This work also develops
two metrics of asymptotic rate of convergence and divergence, and evaluates
these two metrics for several popular standard accelerated methods such as the
NAG, and Nesterov's accelerated gradient with constant momentum (NCM) near
strict saddle points. In the local regime, this work provides an analysis that
leads to the "linear" exit time estimates from strict saddle neighborhoods for
trajectories of these accelerated methods as well the necessary conditions for
the existence of such trajectories. Finally, this work studies a sub-class of
accelerated methods that can converge in convex neighborhoods of nonconvex
functions with a near optimal rate to a local minima and at the same time this
sub-class offers superior saddle-escape behavior compared to that of NAG.