Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
This work addresses a key challenge in nonsmooth optimization for researchers and practitioners, but it is incremental as it builds on existing smooth optimization techniques.
The paper tackles the problem of escaping strict saddle points in nonsmooth optimization by extending stochastic perturbation methods to the Moreau envelope, showing that various algorithms can achieve this at a controlled rate.
Recent work has shown that stochastically perturbed gradient methods can efficiently escape strict saddle points of smooth functions. We extend this body of work to nonsmooth optimization, by analyzing an inexact analogue of a stochastically perturbed gradient method applied to the Moreau envelope. The main conclusion is that a variety of algorithms for nonsmooth optimization can escape strict saddle points of the Moreau envelope at a controlled rate. The main technical insight is that typical algorithms applied to the proximal subproblem yield directions that approximate the gradient of the Moreau envelope in relative terms.