SNAP: Finding Approximate Second-Order Stationary Solutions Efficiently for Non-convex Linearly Constrained Problems

Abstract

This paper proposes low-complexity algorithms for finding approximate second-order stationary points (SOSPs) of problems with smooth non-convex objective and linear constraints. While finding (approximate) SOSPs is computationally intractable, we first show that generic instances of the problem can be solved efficiently. More specifically, for a generic problem instance, certain strict complementarity (SC) condition holds for all Karush-Kuhn-Tucker (KKT) solutions (with probability one). The SC condition is then used to establish an equivalence relationship between two different notions of SOSPs, one of which is computationally easy to verify. Based on this particular notion of SOSP, we design an algorithm named the Successive Negative-curvature grAdient Projection (SNAP), which successively performs either conventional gradient projection or some negative curvature based projection steps to find SOSPs. SNAP and its first-order extension SNAP${}^{+}$, require $\mathcal{O}(1/{\epsilon }^{2.5})$ iterations to compute an $(\epsilon ,\sqrt{\epsilon })$-SOSP, and their per-iteration computational complexities are polynomial in the number of constraints and problem dimension. To our knowledge, this is the first time that first-order algorithms with polynomial per-iteration complexity and global sublinear rate have been designed to find SOSPs of the important class of non-convex problems with linear constraints.

References in corpus (4)

• Tensor Decomposition for Signal Processing and Machine Learning
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization

Cited by in corpus (4)

• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Alternating Direction Method of Multipliers for Quantization
• Convergence to Second-Order Stationarity for Non-negative Matrix Factorization: Provably and Concurrently