Nonsmooth Optimization with Zeroth Order Comparison Feedback

We study unconstrained optimization problems of nonsmooth, nonconvex Lipschitz functions, using only noisy pairwise comparisons governed by a known link function. Our goal is to compute a (δ,varepsilon)-Goldstein stationary point. We combine randomized smoothing with a novel unbiased reduction from comparisons to local value differences. By leveraging a Russian-roulette truncation on the Bernoulli-product expansion of the inverse link, we construct an exactly unbiased estimator for directional differences. This estimator has finite expected cost and variance scaling quadratically with the function gap, O(B2), under mild conditions. Plugging this into the smoothed gradient identity enables a standard nonconvex SGD analysis, yielding explicit comparison-complexity bounds for common symmetric links such as logistic, probit, and cauchit.