Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
This work provides a theoretical guarantee for finding approximate local minima in nonsmooth weakly convex optimization, which is a common challenge in machine learning and other fields.
This paper introduces perturbed proximal algorithms designed to escape strict saddle points in nonsmooth weakly convex functions. The algorithms achieve an ε-approximate local minimum in O(ε^-2log(d)^4) iterations, where d is the problem dimension.
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 $ε$-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 $ε$-approximate local minimum for nonsmooth weakly convex functions in $O(ε^{-2}\log(d)^4)$ iterations, where $d$ is the dimension of the problem.