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 $\tilde{O}(d^3{\sigma }_0^2/{\epsilon }^6)$, matching the rate of 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 $\tilde{O}(d{\sigma }^2/{\epsilon }^4)$ rate; the per-sample $L$-smoothness used by gradient-estimation methods such as RSGF 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 $\tilde{O}(\min \{d^{4/3}{n}^{2/3}/{\epsilon }^{8/3},dn/{\epsilon }^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.