How can nonsmooth functions be optimized using only noisy pairwise comparisons?

Comparisons reveal direction but hide magnitude

In comparison-based optimization the algorithm never sees the objective value f. It submits two points x and y and receives a single bit, equal to 1 with probability σ((f(y)−f(x))/τ), where σ is a known, strictly increasing, symmetric link and τ is a temperature. This models settings such as dueling bandits, human-in-the-loop tuning and preference signals in RLHF-style pipelines.

The difficulty is that the bit depends on the sign of the gap f(y)−f(x), not its size. Existing nonsmooth nonconvex methods that use noisy value feedback need the magnitude of value differences: randomized smoothing with two-point differences gives O(d^{3/2}δ^{−1}ε^{−4}) evaluations, variance reduction improves this to O(d^{3/2}δ^{−1}ε^{−3}), and the online-to-nonconvex conversion reaches the dimension-optimal O(dδ^{−1}ε^{−3}). None of these transfers directly when only a bit is returned.

The paper's target is a (δ,ε)-Goldstein stationary point, the standard solution concept when gradients may not exist. The central quantity is κ, the ratio of the largest queried gap to τ. Because queries are symmetric pairs x±ρu with unit u, that largest gap is 2Lρ, so κ is controlled by the smoothing radius ρ, which must satisfy ρ≤δ/2.

An unbiased gap estimator built from run lengths

The key construction expands the inverse link g=σ^{−1} in the polynomials b_m(p)=p^m−(1−p)^m. A natural estimator of each b_m from one stream of comparisons vanishes after the first change of outcome, so the whole infinite series can be computed from finitely many bits. The estimator compares the pair until the outcome changes and returns ±τ times a partial sum of the expansion coefficients.

For the logistic link the partial sum is the harmonic number of the run length. The estimator is exactly unbiased, uses at most 1+1/(1−α) comparisons in expectation where α is the largest queried success probability, and has second moment of order the gap squared plus τ². For the logistic link the paper bounds E[Δ̂²]≤13τ²(1+κ)².

The expansion exists when g is analytic on a lens {|z|≤r}∩{|z−1|≤r} in the complex plane, which covers the logistic, probit and cauchit links. Analyticity near the real interval alone is not enough: the paper gives a link that is analytic on a neighborhood of the operated range but has poles inside the lens, so no such expansion exists. This is a real restriction on which comparison models the method can serve.

From gap estimates to Goldstein stationarity

The unbiased gap estimate Δ̂ is combined with the query direction u into a gradient estimator G=(d/2ρ)Δ̂u, which is unbiased for the gradient of the smoothed objective. Randomized smoothing handles the lack of gradients, and the online-to-nonconvex conversion turns the resulting online learning sequence into a guarantee on Goldstein stationarity.

With this combination the paper obtains O(d(1+dC_link/κ²)L²Δ_f/(δε³)) comparisons when Δ_f≥Lδ, where Δ_f bounds f(x₀)−inf f and C_link depends only on the link and κ. A smoothing-plus-SGD variant costs E[N]d(1+dC_link/κ²)L³Δ_f/(δε⁴) comparisons, where E[N] is the expected number of comparisons per gap estimate.

The comparison to the value-oracle benchmark is the informative part. Relative to the optimal O(dL²Δ_f/(δε³)) rate for noisy value oracles, comparisons cost an extra factor d/κ². That factor is not a loose accounting artifact: it comes from the second moment of the comparison-based gradient estimator growing with dimension, which the experiments confirm.

A lower bound that matches in the noise-dominated regime

The paper proves that any comparison-based method needs Ω(d²τ²/(ε²δ²)) comparisons on a smooth convex subclass once d is at least of order (εδ/τ)². This bound is tailored to the comparison model rather than inherited from value-oracle lower bounds.

In the comparison-noise-dominated regime the upper and lower bounds agree in d and τ. Writing the lower bound as Ω(d²L²/(κ²ε²)) shows the shared d² and κ dependence. A factor Δ_f/(δε) remains open between the two bounds, and the paper records why chaining hard instances does not close it for larger Δ_f.

The lower bound is informative only when τ is at least of order Lδ. Outside that regime it does not constrain comparison-based methods, so the matching claim should be read as a statement about the noisy-comparison regime, not about all temperatures.

What the experiments show about cost and variance

On synthetic functions both the run-length estimator and an early-stopped nested variant are unbiased at every κ tested. The run-length estimator has the smaller second moment, while the early-stopped nested estimator has the smaller cost and cost–second-moment product; both are minimized near κ⋆≈1.5. The measured second moment of the gradient estimator grows as d with value feedback and as d² with comparisons.

In ℓ₁ regression with a ReLU model on the diabetes data (442 samples, 10 features, d=49), Comparison-O2NC reduces the loss from 1.05 to 0.73±0.03 and Comparison-SGD to 0.70±0.05 using 1.8×10⁵ comparisons, against 0.484±0.001 for the value oracle with 1.2×10⁵ evaluations. At a fixed number of iterations the comparison-based methods stay above the value oracle for d∈{49,97,193}. The cause is isolated in a separate measurement: at fixed temperature the comparison-based E‖G‖² grows by a factor 951 from d=25 to 769, close to the factor 946 expected from d² growth.

On a Chebyshev–Rosenbrock function Comparison-O2NC reaches a gradient norm of 0.87±0.06 against 0.08±0.03 for the value oracle, using ten times fewer calls. In a pendulum swing-up policy search with d=16, Comparison-O2NC succeeds from all initial states on two of three seeds using 4×10⁵ comparisons, while the value oracle succeeds on one of three with 10⁵ evaluations and Comparison-SGD stays between 6.2 and 6.8.

Temperature and link misspecification change the picture

The smoothing radius rule ρ=min{δ/2, κ⋆τ/(2L)} caps κ at a constant, and the experiments show why the cap matters. At a budget of 2×10⁵ comparisons, ρ=δ/2 works while comparisons stay informative but collapses once they become nearly deterministic: at τ₀/64 an estimate costs about 3×10⁴ comparisons, the budget covers seven iterations, and the loss stays at its initial 1.05, whereas the capped rule gives 0.63 to 0.66 for every τ≤τ₀. For τ>τ₀ the two rules coincide and the loss degrades to 0.80 at 4τ₀.

Misspecifying the link shape or the temperature by a factor of two moves the loss by at most 0.1 from its well-specified value of 0.68. The theory requires a known, lens-analytic link, but the experiments suggest the estimator degrades gracefully under moderate misspecification.

Against eight tuned baselines at τ=τ₀/32, the methods that use magnitude information (the paper's estimator, a biased plug-in, and sign-SGD) reach f≈0.35 and smoothed gradient norms in [0.23,0.39] on Chebyshev–Rosenbrock, while direct searches stall at 0.43 with gradient norms above 1.1 and direction-recovery methods do not converge. On ℓ₁ regression all methods reach 0.49 to 0.55, with sign-SGD best at 0.493 against 0.503, using a radius ρ=2δ outside the range the Goldstein argument allows.

When magnitude information earns its cost

The paper's own comparison across tasks gives the practical split. A sign costs the same at large and small gaps, whereas the cost of the unbiased gap estimator grows as e^{2Lρ/τ}. That is why sign-based updates are competitive or better on ℓ₁ regression at the budgets tested, and why the paper notes that sign-based updates carry no such guarantee.

Magnitude information pays off where the sign alone is not enough to make progress: on Chebyshev–Rosenbrock the magnitude-using methods reach f≈0.35 while direct searches stall at 0.43. The biased plug-in stays within 0.01 of the unbiased estimator on both tasks, so the experiments show no practical advantage of unbiasedness at these budgets, even though unbiasedness is what the analysis requires.

The most decision-relevant threshold is κ, the ratio of the largest queried gap to τ. When queried gaps are far below the temperature, the sign of one comparison is already an unbiased estimate of the gap up to a scalar and sign methods lead. When gaps are large relative to τ, comparisons become nearly deterministic, the run-length estimator becomes expensive, and the capped smoothing rule is what keeps the method usable.

Where the guarantee stops

The guarantee requires a known link that is lens-analytic, so the logistic, probit and cauchit links qualify but a link analytic only near the real interval does not. The lower bound is informative only when τ is at least of order Lδ, and the constants in the estimator's second-moment bound are loose. The pendulum experiment replaces the global Lipschitz constant with a finite-difference estimate of the local scale (L≈9 for d=16), while the theorems assume a global constant.

The remaining open gap is the factor Δ_f/(δε) between the upper and lower bounds. The paper closes the d and τ dependence in the comparison-noise-dominated regime but not the joint dependence on Δ_f, so the rate should be treated as matching in dimension and temperature rather than as a complete characterization of comparison-based complexity.

The priority the paper establishes

The paper's distinctive contribution is not a faster algorithm in isolation but the demonstration that an exactly unbiased gap estimate can be extracted from finitely many noisy bits, and that this suffices for Goldstein stationarity in nonsmooth nonconvex optimization. The price is explicit: a factor d/κ² over the value-oracle rate, driven by the d² growth of the comparison-based gradient estimator's second moment.

For a reader deciding whether comparison feedback is workable, the operative question is where the queried gaps sit relative to τ. If gaps are small relative to τ, sign-based updates are the cheaper choice and the unbiased estimator's advantage is theoretical. If gaps are large relative to τ, the capped smoothing rule and the run-length estimator are what make the Goldstein guarantee attainable, at a comparison cost that grows with the gap-to-temperature ratio.

Sources used in this answer