Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms

Abstract

We propose perturbed proximal algorithms that can provably escape strict saddles for nonsmooth weakly convex functions. The main results are based on a novel characterization of $\epsilon$-approximate local minimum for nonsmooth functions, and recent developments on perturbed gradient methods for escaping saddle points for smooth problems. Specifically, we show that under standard assumptions, the perturbed proximal point, perturbed proximal gradient and perturbed proximal linear algorithms find $\epsilon$-approximate local minimum for nonsmooth weakly convex functions in $O({\epsilon }^{-2}\log (d{)}^4)$ iterations, where $d$ is the dimension of the problem.

References in corpus (15)

• The Loss Surfaces of Multilayer Networks
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Escaping Saddles with Stochastic Gradients
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Efficiently escaping saddle points on manifolds
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• Escaping Saddle Points in Constrained Optimization
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Escaping from saddle points on Riemannian manifolds
• Perturbed Proximal Descent to Escape Saddle Points for Non-convex and Non-smooth Objective Functions