{"ID":2827397,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.16200","arxiv_id":"2512.16200","title":"Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithms on Smooth Functions","abstract":"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 $μ$-strongly convex, the algorithm achieves $\\widetilde{\\mathcal O}\\!\\left(\\frac{dL}μ\\log\\!\\frac{dL}{μδ}\\log\\!\\frac{1}{\\varepsilon}\\right)$ to find an $\\varepsilon$-suboptimal solution, and for smooth nonconvex objectives it reaches $\\mathcal O\\!\\left(\\frac{dL}{\\varepsilon}\\log\\!\\frac{1}{\\varepsilon}\\right)$. Notation $\\cO(\\cdot)$ hides constant terms and $\\widetilde{\\mathcal O}(\\cdot)$ hides extra $\\log\\log\\frac{1}{\\varepsilon}$ term. These query complexities hold with a probability at least $1-δ$ with $0\u003cδ\u003c1$. 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.","short_abstract":"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,...","url_abs":"https://arxiv.org/abs/2512.16200","url_pdf":"https://arxiv.org/pdf/2512.16200v1","authors":"[\"Haishan Ye\"]","published":"2025-12-18T05:46:37Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.NE\"]","methods":"[]","has_code":false}