Escaping Saddle Points in Constrained Optimization

Abstract

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.

Cited by in corpus (14)

• Efficiently escaping saddle points on manifolds
• Stochastic Conditional Gradient++
• One Sample Stochastic Frank-Wolfe
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Escaping Saddle Points Faster with Stochastic Momentum
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Safe Learning under Uncertain Objectives and Constraints
• Multi-task Reinforcement Learning in Reproducing Kernel Hilbert Spaces via Cross-learning
• Escaping Saddle-Points Faster under Interpolation-like Conditions
• Stochastic Gradient Langevin Dynamics with Variance Reduction
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems
• Scalable Projection-Free Optimization
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum