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 explicit, and non-asymptotic query complexities. For a d-dimension problem, if the function is L-smooth and μ-strongly convex, the algorithm achieves O\! (dLμ\!dLμδ\!1) to find an -suboptimal solution, and for smooth nonconvex objectives it reaches O\! (dL\!1). Notation () hides constant terms and O () hides extra 1 term. These query complexities hold with a probability at least 1-δ with 0<δ<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.
Haishan Ye (Thu,) studied this question.