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 $ε$-first-order stationarity with comparison complexity $\mathcal{O}(k/(p^2ε^2))$. We…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.21166
curl -X POST /api/v1/records/arxiv/2601.21166/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.21166/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'