Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization

We consider the optimization problem of the form min(x is an element of Rd) f(x) =(Delta) 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 O(L(4)d(3/2)epsilon(-4) + Delta L(3)d(3/2)delta(-1)epsilon(-4)) stochastic zeroth-order oracle complexity to find a (delta, epsilon)-Goldstein stationary point of objective function, where Delta = f(x(0)) - inf(x is an element of Rd) 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 O(L(3)d(3/2)epsilon(-3) + Delta L(2)d(3/2)delta(-1)epsilon(-3)).