Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise

We study stochastic zeroth-order (ZO) optimization of smooth nonconvex objectives under heavy-tailed sample-gradient noise, a regime motivated by empirical evidence that gradient noise in modern machine learning can violate the bounded-variance assumption underlying classical ZO theory. While the first-order literature has established optimal rates under bounded $p$-th moment noise for $p \in (1,2]$, analogous high-probability guarantees for nonconvex ZO optimization remain largely unexplored. The ZO setting is not a direct corollary of first-order theory: first-order methods update using $\nabla F(x;\xi)$, the same object on which the noise assumption is imposed, whereas derivative-free methods only observe noisy function values and construct directional finite-difference estimates. Thus, weak-$L_p$ control of $\nabla F(x;\xi)-\nabla f(x)$ must first be transferred to scalar two-point directional estimates, a concentration step absent from standard first-order analyses. We propose the Robust Scalar-Clipped Zeroth-Order method (\textbf{RSC-ZO}), a two-point method that clips each scalar directional derivative before aggregation. Under sample-wise smoothness and a weak-$L_p$ tail bound on the sample-gradient noise, RSC-ZO finds an $\varepsilon$-stationary point with high probability using $ \widetilde{O}\\left( \frac{d^{\frac{p}{2(p-1)}}} {\varepsilon^{\frac{3p-2}{p-1}}} \right) $ noisy function evaluations, matching the optimal first-order $\varepsilon$-dependence. At $p=2$, our bound becomes $\widetilde{O}(d\varepsilon^{-4})$, matching the classical dimension-accuracy dependence for stochastic ZO methods under bounded-variance noise, which is typically established only in expectation. In contrast, our guarantee holds with high probability and under the strictly weaker weak-$L_2$ tail condition, which can allow infinite gradient-noise variance. We further extend the analysis to a momentum variant and quantify the resulting batch-size/stepsize tradeoff.