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

arXiv: https://arxiv.org/abs/2512.16200 · HTML: https://mlsanity.com/paper/2512.16200/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 25 references that are in the map.
- First posted on arXiv 18 Dec 2025.

## Builds on (most cited first, 7 of 7)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning](https://mlsanity.com/paper/1712.06567/) (2017)
- [CMA-ES for Hyperparameter Optimization of Deep Neural Networks](https://mlsanity.com/paper/1604.07269/) (2016)
- [Back to Basics: Benchmarking Canonical Evolution Strategies for Playing Atari](https://mlsanity.com/paper/1802.08842/) (2018)
- [A Unified Zeroth-Order Optimization Framework via Oblivious Randomized Sketching](https://mlsanity.com/paper/2510.10945/) (2025)
- [Convergence Rate of the (1+1)-Evolution Strategy with Success-Based Step-Size Adaptation on Convex Quadratic Functions](https://mlsanity.com/paper/2103.01578/) (2021)

## Built on by (most cited first, 2 of 2)

- [Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithm on Stochastic Smooth Functions](https://mlsanity.com/paper/2512.19104/) (2025)
- [Learning in Continuous Games from Pairwise Preference Feedback](https://mlsanity.com/paper/2610.05428/) (2026)

## Abstract (arXiv)

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 widetildemathcal O!left(fracdLμlog!fracdLμδlog!frac1varepsilonright) to find an varepsilon-suboptimal solution, and for smooth nonconvex objectives it reaches mathcal O!left(fracdLvarepsilonlog!frac1varepsilonright). Notation cO(·) hides constant terms and widetildemathcal O(·) hides extra loglogfrac1varepsilon 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.