  Gradient descent is a popular algorithm in optimization, and its performance
in convex settings is mostly well understood. In non-convex settings, it has
been shown that gradient descent is able to escape saddle points asymptotically
and converge to local minimizers [Lee et. al. 2016]. Recent studies also show a
perturbed version of gradient descent is enough to escape saddle points
efficiently [Jin et. al. 2015, Ge et. al. 2017]. In this paper we show a
negative result: gradient descent may take exponential time to escape saddle
points, with non-pathological two dimensional functions. While our focus is
theoretical, we also conduct experiments verifying our theoretical result.
Through our analysis we demonstrate that stochasticity is essential to escape
saddle points efficiently.
