Escaping Strict Saddle Points of the Moreau Envelope in Nonsmooth Optimization
Damek Davis, Mateo Díaz, Dmitriy Drusvyatskiy · SIAM Journal on Optimization · 2022
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 many algorithms applied to the proximal subproblem yield directions that approximate the gradient of the Moreau envelope.