Zeroth-Order SGD with Momentum Resetting Achieves Dimension-Dependent Optimality in Nonsmooth Nonconvex Optimization

We investigate the complexity of zeroth-order stochastic gradient methods with momentum for finding $(\delta ,ϵ)$-stationary points of Lipschitz-continuous objectives that may be both nonsmooth and nonconvex, where the algorithm has access only to function values. Recent work has developed specialized zeroth-order schemes that achieve the best-known dependence on the key problem parameters in this setting. However, these guarantees rely on particular algorithmic constructions and do not directly apply to classical SGD-type methods, whose existing analyses typically inherit an additional dependence on the smoothness constant of the smoothed objective. In this work, we study a simple variant of zeroth-order SGD with momentum (ZO-SGDM), which retains the standard SGDM update while incorporating an epoch-wise outer loop with periodic momentum resetting. By exploiting the recursive averaging structure of momentum, we show that this ZO-SGDM-type method achieves an oracle complexity of $\mathcal{O}\left(d{\delta }^{-1}{ϵ}^{-3}\right)$ for finding a $(\delta ,ϵ)$-stationary point, matching the best-known dependence on $d$, $\delta$, and $ϵ$ attained by specialized zeroth-order methods. Our analysis develops a new proof route that, to the best of our knowledge, is the first to isolate the dimension dependence entirely to the zeroth-order gradient estimator itself, thereby avoiding the additional dimension factor arising from the smoothness of the smoothed objective. Although the theoretical guarantee employs periodic resetting and epoch averaging, our experiments show that these mechanisms do not materially degrade performance and mainly serve as analytical devices, providing an empirical recovery of behavior closer to standard ZO-SGDM.