Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithms on Smooth Functions

Rank-based zeroth-order (ZO) optimization – which relies only on the ordering of function evaluations – offers strong robustness to noise and monotone transformations, and underlies many successful algorithms such as CMA-ES, natural evolution strategies, and rank-based genetic algorithms. Despite its widespread use, the theoretical understanding of rank-based ZO methods remains limited: existing analyses provide only asymptotic insights and do not yield explicit convergence rates for algorithms selecting the top-$k$ directions. This work closes this gap by analyzing a simple rank-based ZO algorithm and establishing the first \emph{explicit}, and \emph{non-asymptotic} query complexities. For a $d$-dimension problem, if the function is $L$-smooth and $\mu$-strongly convex, the algorithm achieves $\tilde{\mathcal{O}}\text{\hspace{0.17em}⁣}(\frac{dL}{\mu }\log \text{\hspace{0.17em}⁣}\frac{dL}{\mu \delta }\log \text{\hspace{0.17em}⁣}\frac{1}{\epsilon })$ to find an $\epsilon$-suboptimal solution, and for smooth nonconvex objectives it reaches $\mathcal{O}\text{\hspace{0.17em}⁣}(\frac{dL}{\epsilon }\log \text{\hspace{0.17em}⁣}\frac{1}{\epsilon })$. Notation $\text{cO}(\cdot )$ hides constant terms and $\tilde{\mathcal{O}}(\cdot )$ hides extra $\log \log \frac{1}{\epsilon }$ term. These query complexities hold with a probability at least $1-\delta$ with $0<\delta <1$. The analysis in this paper is novel and avoids classical drift and information-geometric techniques. Our analysis offers new insight into why rank-based heuristics lead to efficient ZO optimization.