  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.
