Escaping Saddle Points in Constrained Optimization
share
In this paper, we focus on escaping from saddle points in smooth nonconvex optimization problems subject to a convex set C. We propose a generic framework that yields convergence to a second-order stationary point of the problem, if the convex set C is simple for a quadratic objective function. To be more precise, our results hold if one can find a ρ-approximate solution of a quadratic program subject to C in polynomial time, where ρ<1 is a positive constant that depends on the structure of the set C. Under this condition, we show that the sequence of iterates generated by the proposed framework reaches an (ϵ,γ)-second order stationary point (SOSP) in at most O({ϵ^-2,ρ^-3γ^-3}) iterations. We further characterize the overall arithmetic operations to reach an SOSP when the convex set C can be written as a set of quadratic constraints. Finally, we extend our results to the stochastic setting and characterize the number of stochastic gradient and Hessian evaluations to reach an (ϵ,γ)-SOSP.
READ FULL TEXT