Noisy Pairwise-Comparison Random Search for Smooth Nonconvex Optimization

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 $\epsilon$-first-order stationarity with comparison complexity $\mathcal{O}(k/(p^2\epsilon^2))$. We also introduce a gap-dependent confidence model, where comparison reliability decreases as the objective-value gap between the two candidates becomes small, and analyze a confidence-weighted voting variant of NCRS. For this oracle, the method achieves $\epsilon$-first-order stationarity with total comparison complexity $\mathcal{O}(k^2/\epsilon^4)$. These results provide intrinsic-dimension convergence guarantees for noisy comparison-based random search in smooth nonconvex optimization.

Many machine learning systems are improved using comparisons rather than exact numerical scores. For example, a person may be asked which of two model outputs is better, or users may indirectly express preferences by clicking on one result instead of another. However, these comparisons can be noisy: people may disagree, user behavior may be inconsistent, and two options that are very similar may be hard to compare reliably. This paper studies how to improve a system when the only available feedback is this kind of noisy pairwise comparison. We propose a simple random-search method that tries small changes and keeps a change when the comparison feedback suggests it is better. We show that this method can still make reliable progress even without direct access to exact scores or gradients. We also study a more realistic setting where comparisons become less reliable when two candidates are nearly tied. Finally, we show that when the problem effectively depends on a smaller number of important directions, the method can benefit from this hidden low-dimensional structure.