Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization

We consider the optimization problem of the form ${\min }_{x\in {\mathbb{R}}^d}f(x)\triangleq {\mathbb{E}}_{\xi }[F(x;\xi )]$, where the component $F(x;\xi )$ is $L$-mean-squared Lipschitz but possibly nonconvex and nonsmooth. The recently proposed gradient-free method requires at most $\mathcal{O}(L^4{d}^{3\mathrm{/}2}{\epsilon }^{-4}+\mathrm{\Delta }{L}^3{d}^{3\mathrm{/}2}{\delta }^{-1}{\epsilon }^{-4})$ stochastic zeroth-order oracle complexity to find a $(\delta ,\epsilon )$-Goldstein stationary point of objective function, where $\mathrm{\Delta }=f(x_0)-{\inf }_{x\in {\mathbb{R}}^d}f(x)$ and $x_0$ is the initial point of the algorithm. This paper proposes a more efficient algorithm using stochastic recursive gradient estimators, which improves the complexity to $\mathcal{O}(L^3{d}^{3\mathrm{/}2}{\epsilon }^{-3}+\mathrm{\Delta }{L}^2{d}^{3\mathrm{/}2}{\delta }^{-1}{\epsilon }^{-3})$.