{"id":"arxiv/2601.21166","url":"https://arxiv.org/abs/2601.21166","tags":["math.OC"],"score":0,"title":"Noisy Pairwise-Comparison Random Search for Smooth Nonconvex Optimization","domain":"math.OC","source":"arxiv","authors":["Taha El Bakkali","Rayane Bouftini","Qiuyi Zhang","Omar Saadi"],"reviews":0,"subject":"math.OC","summary":"We study smooth nonconvex optimization using only noisy pairwise comparisons, without access to gradients or function values. We propose Noisy-Comparison Random Search (NCRS), a simple direct-search method that samples random directions and performs accept/reject updates from comparison feedback. Under a low-dimensional active-subspace structure, NCRS adapts to the intrinsic dimension $k\\le d$ rather than the ambient dimension $d$. For a uniform-margin comparison oracle with advantage $p$, NCRS achieves $ε$-first-order stationarity with comparison complexity $\\mathcal{O}(k/(p^2ε^2))$. We…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-29","reactions":{}}