Stochastic Optimization with Random Search

We study stochastic random search for nonconvex optimization with only noisy function evaluations. We propose Mi2P, a two-point variant of stochastic three-point methods, and analyze it under generalized $(L_0,L_1)$-smoothness. Two regimes are considered. When the mean objective $f$ is $(L_0,L_1)$-smooth and component variance is bounded, Mi2P achieves $\widetilde{O}(d^3\sigma_0^2/\varepsilon^{6})$, matching the rate of \citet{boucherouite2024mistp} under a strictly weaker assumption (they require $f$ to be $L$-smooth, i.e., $L_1=0$). When an $L^1$-average $(L_0,L_1)$-smoothness holds across $\xi$, Mi2P attains the optimal $\widetilde{O}(d\sigma^2/\varepsilon^{4})$ rate; the per-sample $L$-smoothness used by gradient-estimation methods such as RSGF \citep{ghadimi2013stochastic} (i.e., each $f_\xi$ is $L$-smooth, $L_1 = 0$ pointwise in $\xi$) is a special case of this condition. For finite sums with $G$-Lipschitz components, a translation-symmetric variance-reduction scheme yields $\widetilde{O}(\min\{d^{4/3}n^{2/3}/\varepsilon^{8/3},\, dn/\varepsilon^2\})$ without storing snapshots. We also extend the framework to $\delta$-inexact comparison feedback (e.g., RLHF, A/B testing), giving an $O(\sqrt{d\delta})$ accuracy floor. Our analysis is presented for directional distributions with bounded support; the same rates hold for any rotation-invariant distribution with sub-Gaussian tails on the norm of $s$ (including Gaussian) under a step-size restriction that does not affect the asymptotic complexity.