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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-01-29 Page: https://delphi.science/r/arxiv/2601.21166 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…