We propose and analyze a stochastic direct-search method for unconstrained zeroth-order minimization of locally Lipschitz, possibly nonsmooth, objectives. The method combines random polling directions with a stochastic extrapolating line search based on a sufficient-decrease test of order \(p\). Under conditional accuracy assumptions on the stochastic estimates, which can be verified for mean-zero finite-higher-moment oracle noise through suitable sample averaging, we prove almost-sure convergence to Clarke stationary points. We further establish an expected iteration complexity bound. Specifically, using a supermartingale stopping-time argument, we prove that \(\mathcal O\left(\max\left\{r^{-p}, \varepsilon^{-p/(p-1)} \right\} \right) \) iterations are sufficient in expectation to reach an \((r,\varepsilon)\)-Goldstein stationary point. Moreover, we derive a corresponding expected tested-point complexity bound of order \(\mathcal O\bigl(\varepsilon^{1-n} \max\{r^{-p},\varepsilon^{-p/(p-1)}\}\bigr)\). To the best of our knowledge, this is the first convergence and expected-complexity analysis for an extrapolation-based direct-search method in a nonsmooth stochastic setting. Numerical experiments on a DFO benchmark suite highlight competitive performance against well-established stochastic direct-search methods.
Extrapolation-based Direct Search for Nonsmooth Stochastic Zeroth-Order Optimization
\(\)