Nonsmooth Nonconvex Optimization from Noisy Comparisons: Unbiased Gap Estimation and the Price of Preference Feedback

We study the minimization of $L$-Lipschitz, possibly nonsmooth and nonconvex functions $f$ when the only access to $f$ is a noisy pairwise comparison: comparing $x$ and $y$ returns a bit whose probability of favoring $y$ is $\sigma ((f(y)-f(x))/\tau )$ for a known link $\sigma$ and temperature $\tau$. The goal is a $(\delta ,ϵ)$-Goldstein stationary point. We give an exactly unbiased estimator of the value gap $f(y)-f(x)$: compare the pair until the outcome changes and return $\pm \tau$ times a partial sum of the coefficients of an expansion of the inverse link, the harmonic number of the run length for the logistic link. It uses $1+1/(1-\alpha )$ comparisons in expectation, where $\alpha$ is the largest queried success probability, and has a second moment of order the gap squared plus ${\tau }^2$; the expansion exists when ${\sigma }^{-1}$ is analytic on a lens in the complex plane, which holds for the logistic, probit, and cauchit links. Combining the estimator with randomized smoothing and the online-to-nonconvex conversion yields $(\delta ,ϵ)$-Goldstein stationarity with $O(d(1+d{C}_{link}/{\kappa }^2)L^2{\Delta }_f/(\delta {ϵ}^3))$ comparisons, where $\kappa$ is the ratio of the largest queried gap to the temperature and $C_{link}$ depends only on the link and $\kappa$. Because the online-to-nonconvex conversion does not pay for the smoothness of the smoothed objective, the smoothing radius can be chosen freely below $\delta /2$, which caps $\kappa$ at a constant and gives $\kappa =\min \{({\kappa }^{\star },L\delta /\tau )\}$. Relative to the optimal rate $O(d{L}^2{\Delta }_f/(\delta {ϵ}^3))$ for noisy value oracles, comparisons cost an additional factor $d/{\kappa }^2$. We prove that this factor is necessary: any comparison-based method needs $\Omega (d^2{\tau }^2/({ϵ}^2{\delta }^2))$ comparisons, already on smooth convex instances, because each comparison carries bounded Fisher information about the location of the minimizer; the upper and lower bounds differ by exactly ${\Delta }_f/(\delta ϵ)$. Small-scale experiments confirm the estimator's cost and variance, the $d^2$ growth of the gradient-estimator second moment, and the $d^2/T$ estimation rate behind the lower bound.