Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization

This paper studies the problem of solving nonconvex nonsmooth optimization over a closed convex set. Most previous works tackle such problems by transforming the constrained problem into an unconstrained problem. However, they only provide asymptotic convergence analysis for their methods. In this work, we provide the nonasymptotic convergence analysis for solving constrained nonconvex nonsmooth optimization. We first generalize classical gradient mapping and the Frank-Wolfe gap in the nonsmooth setting. Then we introduce novel notions of approximate stationarity concerning such generalized quantities. We also propose several stochastic zeroth-order algorithms for the problem, along with their nonasymptotic convergence guarantees of obtaining the proposed approximate stationarity. Finally, we conduct numerical experiments that demonstrate the effectiveness of our algorithms.

MB-ZOSPGD (γ, δ, ϵ)-GGSP O(d

stochastic projected gradient descent algorithm with a minibatch gradient estimator obtains the (γ, δ, ϵ)-generalized Goldstein stationary point through O(d 3 2 δ -1 ϵ -4 ) function query oracle calls. To tackle the case where the feasible set is so complicated that projection onto it is rather expensive or even intractable, we also propose a zeroth-order stochastic Frank-Wolfe algorithm with a minibatch gradient estimator for problem (1) which attains the (δ, ϵ)-Goldstein Frank-Wolfe stationary point through O(d