Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization

Abstract

We consider the problem of finding an approximate second-order stationary point of a constrained non-convex optimization problem. We first show that, unlike the gradient descent method for unconstrained optimization, the vanilla projected gradient descent algorithm may converge to a strict saddle point even when there is only a single linear constraint. We then provide a hardness result by showing that checking $({\epsilon }_g,{\epsilon }_H)$-second order stationarity is NP-hard even in the presence of linear constraints. Despite our hardness result, we identify instances of the problem for which checking second order stationarity can be done efficiently. For such instances, we propose a dynamic second order Frank--Wolfe algorithm which converges to (${\epsilon }_g,{\epsilon }_H$)-second order stationary points in $\mathcal{O}(\max \{{\epsilon }_g^{-2},{\epsilon }_H^{-3}\})$ iterations. The proposed algorithm can be used in general constrained non-convex optimization as long as the constrained quadratic sub-problem can be solved efficiently.

References in corpus (15)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• How to Escape Saddle Points Efficiently
• Nonconvex phase synchronization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Gradient Descent Converges to Minimizers
• When Are Nonconvex Problems Not Scary?
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• Efficient approaches for escaping higher order saddle points in non-convex optimization
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• First-order Methods Almost Always Avoid Saddle Points
• Depth Creates No Bad Local Minima
• Gradient Descent Can Take Exponential Time to Escape Saddle Points
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity
• On the Behavior of the Expectation-Maximization Algorithm for Mixture Models

Cited by in corpus (10)

• Efficient Algorithms for Smooth Minimax Optimization
• An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
• Escaping from saddle points on Riemannian manifolds
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints
• SNAP: Finding Approximate Second-Order Stationary Solutions Efficiently for Non-convex Linearly Constrained Problems
• A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees
• Stochastic In-Face Frank-Wolfe Methods for Non-Convex Optimization and Sparse Neural Network Training
• Convergence to Second-Order Stationarity for Non-negative Matrix Factorization: Provably and Concurrently
• Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems