Escaping Saddle Points in Constrained Optimization
  In this paper, we study the problem of escaping from saddle points in smooth
nonconvex optimization problems subject to a convex set $\mathcal{C}$. We
propose a generic framework that yields convergence to a second-order
stationary point of the problem, if the convex set $\mathcal{C}$ is simple for
a quadratic objective function. Specifically, our results hold if one can find
a $\rho$-approximate solution of a quadratic program subject to $\mathcal{C}$
in polynomial time, where $\rho<1$ is a positive constant that depends on the
structure of the set $\mathcal{C}$. Under this condition, we show that the
sequence of iterates generated by the proposed framework reaches an
$(\epsilon,\gamma)$-second order stationary point (SOSP) in at most
$\mathcal{O}(\max\{\epsilon^{-2},\rho^{-3}\gamma^{-3}\})$ iterations. We
further characterize the overall complexity of reaching an SOSP when the convex
set $\mathcal{C}$ can be written as a set of quadratic constraints and the
objective function Hessian has a specific structure over the convex set
$\mathcal{C}$. Finally, we extend our results to the stochastic setting and
characterize the number of stochastic gradient and Hessian evaluations to reach
an $(\epsilon,\gamma)$-SOSP.
