Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization

Abstract

We consider the optimization problem of the form ${\min }_{x\in {\mathbb{R}}^d}f(x)\triangleq {\mathbb{E}}_{\hat{I}}¾[F(x;\hat{I}¾)]$, where the component $F(x;\hat{I}¾)$ 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/2}\hat{I}{\mu }^{-4}+\hat{I}”L^3{d}^{3/2}\hat{I}{´}^{-1}\hat{I}{\mu }^{-4})$ stochastic zeroth-order oracle complexity to find a $(\hat{I}´,\hat{I}\mu )$-Goldstein stationary point of objective function, where $\hat{I}”=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/2}\hat{I}{\mu }^{-3}+\hat{I}”L^2{d}^{3/2}\hat{I}{´}^{-1}\hat{I}{\mu }^{-3})$.

ICML 2023