acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

We study the minimization of -Lipschitz, possibly nonsmooth and nonconvex functions when the only access to is a noisy pairwise comparison: comparing and returns a bit whose probability of favoring is for a known link and temperature . The goal is a -Goldstein stationary point. We give an exactly unbiased estimator of the value gap : compare the pair until the outcome changes and return 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 comparisons in expectation, where is the largest queried success probability, and has a second moment of order the gap squared plus ; the expansion exists when 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 -Goldstein stationarity with comparisons, where is the ratio of the largest queried gap to the temperature and depends only on the link and . Because the online-to-nonconvex conversion does not pay for the smoothness of the smoothed objective, the smoothing radius can be chosen freely below , which caps at a constant and gives . Relative to the optimal rate for noisy value oracles, comparisons cost an additional factor . We prove that this factor is necessary: any comparison-based method needs 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 . Small-scale experiments confirm the estimator's cost and variance, the growth of the gradient-estimator second moment, and the estimation rate behind the lower bound.

Primary area:
optimization
Keywords:
Preference-based optimization, non-smooth, unbiased estimation, link functions

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_q22jOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies Goldstein stationarity for nonsmooth nonconvex objectives when the oracle returns noisy pairwise comparisons. It constructs an unbiased gap estimator that stops after the first change in comparison outcome. Combined with randomized smoothing and an online-to-nonconvex conversion, this gives an upper bound on the number of comparisons. A separate information-theoretic argument gives a lower bound for a smooth convex subclass. Simulations check the estimator, dimension scaling, and optimization behavior.

Critical strengths
  • The run-length estimator gives an exact unbiased gap estimate with finite expected comparison cost and a controlled second moment under clear link assumptions.
  • The paper connects this estimator to a Goldstein-stationarity guarantee and derives a comparison-specific lower bound. I found no decisive error in the core proof paths.
Critical weaknesses
  • The lower bound covers a narrow regime. Theorem 5.1 uses a convex subclass with initial gap at most 128εδ128\varepsilon\delta and requires d≥222(εδ/τ)2d\geq 2^{22}(\varepsilon\delta/\tau)^2. Its match with Theorem 4.2 therefore does not settle the comparison cost for general nonsmooth nonconvex objectives with larger initial gaps. The authors identify this remaining factor in Section 5.
  • The experiments do not show a practical benefit from unbiased gap estimation. At matched comparison budgets, the biased plug-in within O2NC has a lower smoothed-gradient norm on Chebyshev–Rosenbrock than Comparison-O2NC (0.230 versus 0.387; Appendix C, Table 3). Sign-SGD also has lower regression loss (0.493 versus 0.518), although this comparison does not isolate unbiasedness. The results use three seeds, and the authors themselves report no practical advantage from unbiasedness at these budgets.
  • The applied settings differ from the guarantee. Theorem 4.2 uses a global Lipschitz bound and specifies the step and clipping parameters. The real-task runs replace the global LL with a local finite-difference estimate and tune the parameters by grid search (Section 6, Appendix B). They illustrate the algorithm, but do not show how the theorem-prescribed settings perform.
Questions for authors
  • Can the lower bound be extended to larger initial gaps, or can the upper bound be improved there? Which dependence on Δf/(δε)\Delta_f/(\delta\varepsilon) do the authors expect to be necessary?
  • Can the authors test whether the unbiased estimator helps on a broader set of problems and budgets?
6 comments

We thank the reviewer for the careful review and for checking the core proof paths. We are preparing a revised version that incorporates the changes described below and will post it as soon as possible; we wanted to start the discussion now.

Regime of the lower bound, and the factor Δf/(δε)\Delta_f/(\delta\varepsilon) (Weakness 1, Question 1). Following an observation by Reviewer K4C5, the upper bound improves. Our analysis bounded every queried gap by 2Lρ2L\rho; since Δu=f(x+ρu)−f(x−ρu)\Delta_u=f(x+\rho u)-f(x-\rho u) is odd and 2Lρ2L\rho-Lipschitz on the sphere, it concentrates at scale Lρ/dL\rho/\sqrt d, and the cost and second moment of the estimator can be controlled direction by direction. With ρ=min⁡�0�\rho=\min�0� the estimator uses O(1)O(1) comparisons per gradient estimate, and the comparison complexity becomes O(dL2Δhδε3(1+dτ2L2δ2)).O\Big(\frac{dL^2\Delta_h}{\delta\varepsilon^3}\Big(1+\frac{d\tau^2}{L^2\delta^2}\Big)\Big). On the hard family of Theorem 5.1 this is O(dL2/ε2+d2τ2/(δ2ε2))O(dL^2/\varepsilon^2+d^2\tau^2/(\delta^2\varepsilon^2)), whose comparison-specific term equals the lower bound. So for small initial gaps the comparison cost is settled up to link-dependent constants.

The remaining question is whether Δf/(δε)\Delta_f/(\delta\varepsilon) multiplies the comparison term for larger initial gaps, as in our upper bound. Two facts bear on it:

  • We have Ω(Δf/(δε))\Omega(\Delta_f/(\delta\varepsilon)) for smooth functions without a global Lipschitz bound, by reduction from first-order lower bounds.
  • We expect the product to be necessary, by analogy with value oracles, where the corresponding product dΔf/(δε3)d\Delta_f/(\delta\varepsilon^3) is the best known upper bound and is conjectured to be tight (Kornowski and Shamir, 2023). A joint lower bound is open in both settings. Appendix A.6 records why lengthening our hard family into a chain does not prove it. Completing KK stages forces queries of norm of order δK\delta\sqrt K. The sensitivity of a comparison to the next hidden direction grows with that norm, and the resulting bound decreases in KK.

Practical benefit of unbiasedness (Weakness 2, Question 2). The reviewer's reading of Table 3 is correct, and the paper reports that the experiments show no practical advantage of unbiasedness at these budgets. Unbiasedness is what makes the analysis go through. Whether it helps in practice depends on whether the bias of the alternatives exceeds the target accuracy, and with tuned radii at our budgets it did not.

For the revision we are:

  • rerunning the comparison with the new radius rule ρ=min⁡�1�\rho=\min�1�;
  • extending the grids and using more seeds;
  • adding longer runs at smaller target accuracy;
  • adding a broader set of problems, including the probit and cauchit links, whose coefficients we now compute: a canonical choice gives cm=ζ(m+1)/πc_m=\zeta(m+1)/\pi for cauchit and a one-dimensional integral for probit. We will report the outcomes as they come and keep the conclusions descriptive.

One further result bears on the comparison with sign-based methods. One comparison of an antithetic pair gives the smoothed gradient up to a positive scale and a bias quadratic in the radius, for any link with σ′(0)>0\sigma'(0)>0. This is the mechanism behind the competitiveness of sign-SGD in our experiments. The revision adds the corresponding guarantee, with one comparison per pair and without knowledge of the link: it matches the known-link rate at high temperature and costs a factor of order L/εL/\varepsilon at low temperature.

Theorem settings versus the experiments (Weakness 3). We agree that the real-task runs illustrate the algorithm rather than test the theorem. The revision adds, next to the tuned runs, runs with the theorem-prescribed step size, clipping parameter and radius (the latter now ρ=min⁡�2�\rho=\min�2�). It also describes the finite-difference constant as a local Lipschitz scale rather than an estimate of the global constant the theorem assumes.

We have uploaded a revised version; new and revised parts are shown in blue. In relation to your review:

  • Regime of the lower bound (Section 3.3, Appendix A.12). With the improved Theorem 3.8, run with the Lipschitz constant 32ϵ32\epsilon of the hard instances, the upper bound matches the lower bound on them. For larger initial gaps the joint dependence on Δf\Delta_f remains open, as for value oracles. The complementary bound Ω(Δf/(δϵ))\Omega(\Delta_f/(\delta\epsilon)) is stated for smooth functions without a global Lipschitz bound.
  • Practical benefit of unbiasedness (Section 5, Figure 1, Tables 3 and 4). With 10 seeds and the new radius, sign-SGD remains as good or better, and the plug-in estimator is close to ours. With three times the budget there is no crossover (Figure 2). The paper says this plainly. The new one-comparison method of Section 4 is competitive and the fastest comparison-based method on Chebyshev–Rosenbrock.
  • Theorem settings (Table 5, Appendix C.3). Untuned runs with the radius and variance bound of the theorems reduce the objective substantially but stay far from the tuned runs. The explicit schedules do not fit these budgets, and the paper states what was actually run. The finite-difference constant is described as a local Lipschitz scale.
  • Further experiments (Table 6). The cauchit link behaves like the logistic link. For the probit link we report all five seeds, including one that stalled, and explain it: the selected radius lies outside the range covered by the cost bound.

Thank you for your detailed response. The new radius improves the upper bound but the lower bound still covers only a very small initial gap. The new Section 4 is a useful addition but it also weakens the main contribution because by Theorem 4.3 a simple one-comparison method has the same bound at high noise and the unbiased estimator can give an advantage only at low noise. In the low-noise experiments (Table 3) the simple method is not worse. My main concerns about the significance of the contribution remain. Therefore, I keep my rating.

Reviewer_K4C5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies nonsmooth nonconvex optimization using noisy pairwise comparisons, with the goal of finding (δ,ϵ)(\delta,\epsilon)-Goldstein stationary points.

The main contribution is an unbiased estimator of function-value differences constructed from repeated Bernoulli comparisons. The estimator has finite expected query complexity and bounded second moment under suitable analyticity assumptions on the inverse link function. Combining this estimator with randomized smoothing and online-to-nonconvex conversion, the authors establish an upper bound of

O(d(1+dClink/κ2)L2Δfδϵ3),O\left(\frac{d(1+dC_{\mathrm{link}}/\kappa^2)L^2\Delta_f}{\delta\epsilon^3}\right),

for Δf≥Lδ\Delta_f\geq L\delta, with the smoothing radius chosen to control the gap-to-temperature ratio κ\kappa.

The paper also establishes a lower bound of Ω(d2τ2/(ϵ2δ2))\Omega(d^2\tau^2/(\epsilon^2\delta^2)) under a high-dimensional condition, and presents numerical experiments comparing the proposed approach with existing methods.

Critical strengths
  1. The unbiased estimator is an interesting technical contribution. The construction is simple, requires no truncation parameter, and comes with theoretical guarantees on its expected cost and variance. The characterization through lens-analyticity, together with the counterexample and the connection to Russian-roulette estimation, provides useful insight into when the construction applies.

  2. The paper addresses a relevant problem and provides a substantial theoretical analysis. The combination with online-to-nonconvex conversion is natural, and the lower bound helps characterize the difficulty of optimization under noisy comparison feedback. The arguments I checked appear correct, and the authors explicitly acknowledge several limitations of their results.

Critical weaknesses

1. The dimension and noise dependence of the upper bound appear unnecessarily pessimistic.

My main concern is the characterization of the "price of preference feedback." The analysis relies on the uniform bound ∣Δu∣≤2Lρ|\Delta_u|\leq 2L\rho, which motivates restricting κ≤κ⋆\kappa\leq\kappa^\star. Consequently, even as τ→0\tau\to0, the resulting complexity remains a factor dd worse than the corresponding value-oracle rate.

However, this worst-case restriction does not appear necessary when controlling the expected comparison complexity. Since

Δu=f(x+ρu)−f(x−ρu)\Delta_u=f(x+\rho u)-f(x-\rho u)

is odd and 2Lρ2L\rho-Lipschitz on the unit sphere, concentration of measure implies

Eu[Δu2]=O(L2ρ2/d),\mathbb E_u[\Delta_u^2]=O(L^2\rho^2/d),

together with sub-Gaussian tail bounds.

For the logistic link, the per-direction guarantees give (the proof of Theorem 3.6(iii) only uses max⁡{p,1−p}=σ(∣Δu∣/τ)\max\{p,1-p\}=\sigma(|\Delta_u|/\tau), so it applies per direction)

\leq 13(\tau+|\Delta_u|)^2,$$ and the exact expected comparison cost satisfies $$\mathbb E[N\mid u] =1+e^{\Delta_u/\tau}+e^{-\Delta_u/\tau}.$$ Using spherical concentration, this implies $$\mathbb E[N] \leq 1+2\exp\left( \frac{CL^2\rho^2}{d\tau^2} \right)$$ for an absolute constant $C$. Therefore, choosing $$\rho = \min \left\\{ \frac{\delta}{2}, c\frac{\tau\sqrt d}{L} \right\\}$$ for a suitable constant $c>0$ appears sufficient to maintain $O(1)$ expected comparisons per gradient estimate. Furthermore, averaging the conditional second-moment guarantee over $u$ yields $$\mathbb E\|G\|^2 =O\left(dL^2+\frac{d^2\tau^2}{\rho^2}\right),$$ and with this choice of $\rho$, the term $d^2\tau^2/\rho^2$ is at most of order $dL^2+d^2\tau^2/\delta^2$, so that $$\mathbb E\|G\|^2 =O\left(dL^2+\frac{d^2\tau^2}{\delta^2}\right).$$ Applying the same online-to-nonconvex conversion would then give, at least for the logistic link, a comparison complexity of $$O\left( \frac{dL^2\Delta_f}{\delta\epsilon^3} \left(1+\frac{d\tau^2}{L^2\delta^2}\right) \right),$$ when $\Delta_f\geq L\delta$. If this argument is correct, the price of preference feedback would instead be at most, up to constants, $$1+\frac{d\tau^2}{L^2\delta^2},$$ which removes the additional dimension factor in the low-noise regime. Extending this to the probit and cauchit links would require per-$p$ moment bounds as the worst-case $\alpha$ approaches 1. Unless there is an obstacle to this argument, the current upper bound does not appear tight. This is particularly relevant to the paper's characterization of the price of comparison feedback. The lower bound establishes the necessity of the noise-dependent term in a restricted regime but does not rule out this improvement. **2. The scope of the lower bound and the empirical contribution could be better justified.** The lower bound is established on a smooth convex subclass with an initial optimality gap of order $\epsilon\delta$. While this is sufficient to establish a valid lower bound for the broader problem class, it does not characterize the joint dependence on dimension, accuracy, and $\Delta_f$ for general nonsmooth nonconvex optimization. The construction also shares similarities with existing information-theoretic lower bounds for noisy zeroth-order optimization, particularly arguments based on Assouad's lemma. Although the paper discusses these connections, the precise novelty relative to previous lower-bound techniques could be better emphasized. The experimental evidence is also somewhat unconvincing as a demonstration of the estimator's practical benefits. Sign-based methods and the biased plug-in estimator perform comparably to, and sometimes better than, the proposed approach. In particular, the experiments do not identify a regime where unbiasedness provides a clear practical advantage. Finally, the method requires repeated independent comparisons of the same pair. This assumption may be restrictive in applications involving human preference feedback, which are an important part of the paper's motivation.
Questions for authors
  1. Upper bound: Why does the analysis require a uniform bound on Δu\Delta_u, rather than controlling the expected number of comparisons over random directions? In particular, is there an obstacle to the improved second-moment and comparison-complexity bounds suggested above? Identifying where this argument fails, if applicable, would help clarify the necessity of the current dimension dependence.

  2. Novelty of the estimator: How does the proposed construction relate to classical sequential unbiased estimation for Bernoulli parameters? In particular, inverse binomial sampling has been used to construct unbiased estimates of logarithmic Bernoulli probabilities (e.g., van Opheusden et al., 2020, Unbiased and Efficient Log-Likelihood Estimation with Inverse Binomial Sampling). It would be useful to clarify what is new in the logistic run-length estimator relative to this literature, and which aspects of the general lens-analytic construction constitute the main methodological contribution.

  3. Lower bound: The lower bound matches the dominant dimension and temperature dependence only under particular assumptions on the noise level, dimension, and initial optimality gap. Could the authors clarify which dependencies are established as necessary and which remain open? Additionally, the main-text proof sketch of Theorem 5.1 introduces a choice of a2a^2 depending on T,τ,LT,\tau,L, whereas Appendix A.6 uses a fixed construction and the slope G=32ϵG=32\epsilon. These descriptions should be reconciled.

  4. Empirical relevance: Is there a regime, particularly at high accuracy, where the unbiased estimator consistently outperforms the biased alternatives? Could the theoretical guarantees be adapted to settings where each pair can only be queried a limited number of times?

Minor comments

  • Some notation is overloaded, particularly ρ\rho, Δ\Delta, and α\alpha.
  • Appendix A.3 states that ρˉ=ρc>1\bar\rho=\rho_c>1 for every lens-analytic link. This appears to rely on the generic analytic coefficient bound, whereas the explicit logistic coefficients permit ρc=1\rho_c=1. This distinction should be clarified.
  • The gradient norms reported in Figure 6 and Table 3 correspond to different temperatures, which should be made explicit when comparing these results.
  • The step-size parameters selected for the comparison-based methods in Figure 6 lie at the lower boundary of the search grid. Although this is acknowledged in the appendix, extending the grid would make the comparison more convincing.
5 comments

We thank the reviewer for a detailed and technically engaged review. The argument on the upper bound is correct, and we adopt it. We are preparing a revised version that incorporates the changes described below and will post it as soon as possible; we wanted to start the discussion now.

Upper bound (Weakness 1, Question 1). There is no obstacle to the reviewer's argument. The uniform bound ∣Δu∣≤2Lρ|\Delta_u|\le2L\rho was a simplification, and the analysis does not need it. For the logistic link the per-direction quantities are exactly as stated: E[N∣u]=1+2cosh⁡(Δu/τ)\mathbb E[N\mid u]=1+2\cosh(\Delta_u/\tau), and E[Δ~2∣u]≤13(τ+∣Δu∣)2\mathbb E[\tilde\Delta^2\mid u]\le13(\tau+|\Delta_u|)^2 by Theorem 3.6(iii) applied per direction. Since u↦Δuu\mapsto\Delta_u is odd and 2Lρ2L\rho-Lipschitz on the sphere, Lévy-type concentration gives E[N]≤1+2exp⁡(CL2ρ2/(dτ2))\mathbb E[N]\le1+2\exp(CL^2\rho^2/(d\tau^2)) and Eu[Δu2]=O(L2ρ2/d)\mathbb E_u[\Delta_u^2]=O(L^2\rho^2/d). With ρ=min⁡{δ/2,cτd/L}\rho=\min\{\delta/2,c\tau\sqrt d/L\} this yields E[N]=O(1)\mathbb E[N]=O(1), E∥G∥2=O(dL2+d2τ2/δ2)\mathbb E\|G\|^2=O(dL^2+d^2\tau^2/\delta^2), and the comparison complexity O(dL2Δhδε3(1+dτ2L2δ2))O\big(\frac{dL^2\Delta_h}{\delta\varepsilon^3}(1+\frac{d\tau^2}{L^2\delta^2})\big).

We checked this numerically on ∥x∥∞\|x\|_\infty and ∥x∥1/d\|x\|_1/\sqrt d with d∈{50,400}d\in\{50,400\} and τ\tau from 10−410^{-4} to 10−110^{-1}. With the new radius, the expected number of comparisons per estimate is about 4.34.3 and E∥G∥2/(dL2)\mathbb E\|G\|^2/(dL^2) about 33 at every temperature. Under our previous rule the latter is 4848 at d=50d=50 and 379379 at d=400d=400, which is the extra factor dd the reviewer identified.

Probit and cauchit. The extension the reviewer mentions requires per-pp bounds as α→1\alpha\to1. It goes through with a canonical choice of the coefficients, cm=1π∫1∞t−m−1Im⁡σ−1(t+i0) dtc_m=\frac1\pi\int_1^\infty t^{-m-1}\operatorname{Im}\sigma^{-1}(t+i0)\,dt, which gives cm=1/mc_m=1/m (logistic), cm=ζ(m+1)/πc_m=\zeta(m+1)/\pi (cauchit) and, for probit, coefficients with cm∼1/(m2log⁡m)c_m\sim1/(m\sqrt{2\log m}):

  • Second moment. Both satisfy E[Δ~2]≤Cσ(τ2+Δ2)\mathbb E[\tilde\Delta^2]\le C_\sigma(\tau^2+\Delta^2) for every gap. We checked this numerically, with Cσ≈1.0C_\sigma\approx1.0 for probit up to gaps of 4.6τ4.6\tau and Cσ≈2.0C_\sigma\approx2.0 for cauchit up to 30τ30\tau, where it approaches its limit 22.
  • Cost. E[N∣u]\mathbb E[N\mid u] grows like eΔu2/(2τ2)e^{\Delta_u^2/(2\tau^2)} (probit) or like ∣Δu∣/τ|\Delta_u|/\tau (cauchit). Both are integrable against the sub-Gaussian law of Δu\Delta_u when cc is small enough. The revision states the improved theorem under these per-gap conditions, proves them for the logistic and cauchit links, and reports them as numerical evidence for the probit link, for which we do not have a proof.

Consequences. On the hard family of Theorem 5.1 the comparison-specific term of the new upper bound equals the lower bound. The new radius is also the one our experiments selected: the queried gaps were 0.10.1 to 0.40.4 of the worst case, and the tuned radii sat at the top of the grid.

Novelty of the estimator (Question 2). The reviewer is right that the logistic case is classical in its ingredients, and the revision says so precisely.

  • The classical estimator. Under inverse binomial sampling (sample until the first success; Haldane, 1945), −HN−1-H_{N-1} is unbiased for log⁡p\log p (Girshick, Mosteller and Savage, 1946; DeGroot, 1959), which van Opheusden, Acerbi and Ma (2020) use for log-likelihood estimation. Mendo (2024) estimates the log odds without bias with two independent inverse-binomial runs, one until the rrth success and one until the rrth failure, for r≥2r\ge2.
  • Our estimator is that construction, coupled. It is the case r=1r=1 of this construction (which Mendo does not consider; unbiasedness at r=1r=1 is classical) with the two runs sharing their first observation. If the first outcome is a success, the run "until the first success" ends immediately and contributes H0=0H_0=0, while the other run continues. Each run keeps its geometric marginal law, so unbiasedness follows from linearity without independence.
  • Neither dominates. Sharing the first draw saves exactly one comparison, E[N]=1p(1−p)−1\mathbb E[N]=\frac1{p(1-p)}-1, at the price of a larger second moment. In cost times second moment, E[N]⋅E[Δ^2]/τ2\mathbb E[N]\cdot\mathbb E[\hat\Delta^2]/\tau^2, the two-run version is better near p=1/2p=1/2 (4.74.7 against 6.46.4 at κ=0\kappa=0), and ours slightly better from κ≈2\kappa\approx2 (228228 against 232232 at κ=3\kappa=3).
  • What we contribute. Both versions use the same coefficients for any link, and our analysis applies to either. The contributions are therefore:
    1. the characterization of the links whose inverse is unbiasedly estimable in this way (lens analyticity), with the counterexample;
    2. the canonical coefficient formula with explicit or computable coefficients for probit and cauchit;
    3. cost and moment bounds uniform in the gap;
    4. the optimization analysis with the matching lower bound. The revision adds these references and this comparison.

Lower bound (Weakness 2, Question 3). What is established as necessary:

  • Ω(d2τ2/(ε2δ2))\Omega(d^2\tau^2/(\varepsilon^2\delta^2)) comparisons, for every link with cσ<∞c_\sigma<\infty, on a smooth convex subclass with initial gap 128εδ128\varepsilon\delta, once d≥222(εδ/τ)2d\ge2^{22}(\varepsilon\delta/\tau)^2. The bound also holds when the number of comparisons is random with sup⁡vEv[N]≤T\sup_v\mathbb E_v[N]\le T, the budget model of our upper bounds.
  • Ω(Δf/(δε))\Omega(\Delta_f/(\delta\varepsilon)) for smooth functions without a global Lipschitz bound, by reduction from the first-order lower bound of Carmon et al. (2020), whose construction is not globally Lipschitz. What is open is the joint dependence on Δf\Delta_f, dd and τ\tau.

Relative to Assouad-type bounds for noisy zeroth-order optimization, the new ingredients are:

  1. a bound on the total sensitivity of one comparison to all coordinates of the hidden parameter that holds for arbitrarily distant query pairs, so the queries are not restricted;
  2. the choice of the hard family's slope proportional to ε\varepsilon rather than LL, which is what produces the τ2/ε2\tau^2/\varepsilon^2 dependence (with slope LL the bound would be weaker by (L/ε)2(L/\varepsilon)^2);
  3. the shifted Fisher-information constant cσc_\sigma, which controls the Bernoulli divergence away from p=1/2p=1/2. The main-text sketch is corrected in the revision to follow Appendix A.6 (cube radius 16δ16\delta, slope G=32εG=32\varepsilon, and the optimization over the radius).

Empirical relevance (Weakness 2, Question 4). We agree that the experiments do not show a practical advantage of unbiasedness, and the paper states this. The theory predicts a difference only when the bias of the alternatives exceeds the target accuracy; with tuned radii at our budgets it did not. For the revision we are:

  • rerunning the comparison with the new radius rule;
  • adding runs with the theorem-prescribed parameters;
  • extending the step-size grids that were cut at their edge and using more seeds;
  • adding longer runs at smaller target accuracy. We will report the outcome either way.

Limited repeated queries (Weakness 2, Question 4). This is a real limitation for human raters, and the revision states it. Two answers:

  • With the new radius rule, the expected number of comparisons per pair is a small constant, about 33 to 55.
  • One comparison per pair is also enough, with a guarantee. Because the pair x±ρux\pm\rho u is antithetic, the even part of the link cancels, and one comparison gives d2ρ(2Y−1)u\frac d{2\rho}(2Y-1)u with mean 2σ′(0)τ∇fρ(x)\frac{2\sigma'(0)}\tau\nabla f_\rho(x) plus a bias of norm at most 111 C3L3ρ2/(dτ3)111\,C_3L^3\rho^2/(d\tau^3). Here C3C_3 bounds the third-order remainder of the odd part σ(t)−σ(−t)\sigma(t)-\sigma(-t) (C3=1/24C_3=1/24 for the logistic link). Extending the online-to-nonconvex conversion to a biased oracle gives O(Δhδε3(C3dL3σ′(0)ε+d2τ2δ2))O\big(\frac{\Delta_h}{\delta\varepsilon^3}(\frac{C_3dL^3}{\sigma'(0)\varepsilon}+\frac{d^2\tau^2}{\delta^2})\big) comparisons up to link constants, one per pair. This holds for any link with σ′(0)>0\sigma'(0)>0, in particular an unknown one, at the cost of a factor of order L/εL/\varepsilon in the low-temperature regime and none at high temperature.

Minor comments.

  • Notation. The revision renames the coefficient growth rate, writes the online increments as vtv_t, and reserves Δ\Delta for gaps and α\alpha for the largest success probability; a notation table lists the remaining symbols.
  • ρˉ>1\bar\rho>1. The reviewer is right: it came from the generic Cauchy bound. With the canonical coefficients, ρc=1\rho_c=1 and all moments are finite for the logistic and cauchit links; for the probit link this holds numerically only. Appendix A.3 will say so.
  • Temperatures in Figure 6 and Table 3. Figure 6 is at τ0\tau_0 and Table 3 at τ0/32\tau_0/32; both will be labeled.
  • Grid boundary. The grids will be extended below the selected step sizes.

We have uploaded a revised version; new and revised parts are shown in blue. In relation to your review:

  • Upper bound (Section 3.2). Your argument is now Theorem 3.8. It uses the radius ρ=min⁡�0�\rho=\min�0�, Lemma 2.1 for the concentration of the queried gap, Lemma 3.7 for the moments of GG, and an explicit integer schedule (proof in Appendix A.9). The gap-uniform bounds are proved for the logistic and cauchit links (Theorem 3.4(iii)); for the probit link they are numerical only.
  • Relation to inverse binomial sampling (Remark 3.5, Appendix A.4). Our logistic estimator is the case r=1r=1 of Mendo's two-run log-odds estimator (which he states for r≥2r\ge2, running until the rrth success and the rrth failure), with the two runs sharing their first comparison. Table 2 compares the two for all three links, and the contribution list is revised accordingly.
  • Lower bound (Section 3.3, Appendix A.12). On the hard instances, Theorem 3.8 run with their Lipschitz constant 32ϵ32\epsilon matches the lower bound. The main-text sketch now follows the appendix. The complementary bound Ω(Δf/(δϵ))\Omega(\Delta_f/(\delta\epsilon)) holds for smooth functions without a global Lipschitz bound; transferring it to the Lipschitz class needs a modified construction, as the paper states.
  • Repeated queries (Section 4). Theorem 4.3 uses one comparison per pair and holds for any link with σ′(0)>0\sigma'(0)>0, including an unknown one.
  • Empirics (Section 5, Appendix C). New runs use 10 seeds, the radius of Theorem 3.8, theorem-prescribed parameters without tuning, longer runs, and the cauchit and probit links. They confirm that unbiasedness gives no practical advantage at these budgets, and that the one-comparison method is competitive.
  • Minor comments. The coefficient growth rate is renamed μ\mu and the online increments vtv_t. With the canonical coefficients, all moments are finite for the logistic and cauchit links. Temperatures are labeled in all tables and figures, and no selected step size lies on a grid edge.
Reviewer_mKaiOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies the optimization of Lipschitz functions, potentially nonconvex and nonsmooth with only access to a comparison oracle that satisfies Pr⁡[Y=1∣x,y]=σ(Δ(x,y)/τ)\Pr[Y=1 \mid x,y] = \sigma(\Delta(x,y)/\tau). The idea is: first estimate the function gap f(x)−f(y)f(x)-f(y) by repeatedly querying the oracle, then using the estimated function gap to estimate the gradients and use online-to-nonconvex or SGD to minimize the function. To estimate the gap, the paper requires coefficient cmc_m in the expansion of the inverse link function: σ−1(p)−∑m≥1(pm−(1−p)m)\sigma^{-1}(p)-\sum_{m\ge 1} (p^m - (1-p)^m) and uses estimator τ(2Y1−1)∑m=1N−1∑mcm\tau(2Y_1-1) \sum_{m=1}^{N-1}\sum_m c_m where NN is the first time the outcome of the oracle query differs from the first outcome. Once they have the unbiased gap estimator, the remaining pipeline uses established machinery of zeroth-order method. The paper also provides a lower bound for comparison based approaches in term of the dimension dd, τ,δ\tau,\delta and ϵ\epsilon.

Critical strengths
  • The approach in this paper is principled and simple. Essentially, it's a zeroth order method with the additional estimator for the function gap. So the analysis can be streamlined, even though it's not obvious how to construct an unbiased estimator with guarantees (the obvious one doesn't work)
  • To this end, the paper has an elegant unbiased estimator for the function gap.
Critical weaknesses
  • The main weakness of the paper I can see is the restrictiveness of the estimator. It requires the inverse of the link function as well as the coefficients cmc_m. For logistic link, these coefficients are provided but for general admissible links, it's a stronger implementation requirement. Even for probit and cauchit links, the paper does not provide explicit coefficients cmc_m, a numerical implementation, or coefficient-computation complexity.
  • The upperbound and lowerbound still have gap. Also the lower bound doesn't provide the dependence on the initial function gap.
  • Another important weakness of the paper is the presentation. The paper provides very little context in the main body. So far, the main body is just a series of theorem statements and proof sketches. An overview of the approach, more discussion on the assumptions, more intuition in each section will help a lot with the understanding of the paper.

After the rebuttal: the paper added the explicit computation for cauchit links and add bounds for unknown links.

Questions for authors
  • Can the authors discuss how to compute the coefficients beyond logistic link, the procedure and its complexity?
  • It seems that knowing τ\tau is required, which seems to be a strong assumption. Can the authors discuss whether it is possible to forgo this assumption?
4 comments

We thank the reviewer for the careful reading, and for noting that the obvious estimator does not work and that the construction is principled. We are preparing a revised version that incorporates the changes described below and will post it as soon as possible; we wanted to start the discussion now.

Computing the coefficients beyond the logistic link (Weakness 1, Question 1). The estimator returns τ(2Y1−1)SN−1\tau(2Y_1-1)S_{N-1} with Sk=c1+⋯+ckS_k=c_1+\dots+c_k, and its mean is τ(h(p)−h(1−p))\tau(h(p)-h(1-p)) with h(z)=∑mcmzmh(z)=\sum_mc_mz^m. Any hh holomorphic on a disc of radius larger than α\alpha with h(z)−h(1−z)=σ−1(z)h(z)-h(1-z)=\sigma^{-1}(z) gives an unbiased estimator, so the coefficients are not unique. The canonical choice places all singularities of σ−1\sigma^{-1} on [1,∞)[1,\infty) into hh and those on (−∞,0](-\infty,0] into h(1−z)h(1-z). By the Plemelj formula, cm=1π∫1∞t−m−1 Im⁡σ−1(t+i0) dt,Sk=1π∫1∞Im⁡σ−1(t+i0) 1−t−kt(t−1) dt,c_m=\frac1\pi\int_1^\infty t^{-m-1}\,\operatorname{Im}\sigma^{-1}(t+i0)\,dt,\qquad S_k=\frac1\pi\int_1^\infty\operatorname{Im}\sigma^{-1}(t+i0)\,\frac{1-t^{-k}}{t(t-1)}\,dt, where σ−1(t+i0)\sigma^{-1}(t+i0) is the boundary value from the upper half-plane. For the three running links:

  • Logistic: Im⁡σ−1(t+i0)=π\operatorname{Im}\sigma^{-1}(t+i0)=\pi, which gives cm=1/mc_m=1/m and Sk=HkS_k=H_k.
  • Cauchit: σ−1(z)=−cot⁡(πz)\sigma^{-1}(z)=-\cot(\pi z) has simple poles at the integers, and the formula gives cm=ζ(m+1)/πc_m=\zeta(m+1)/\pi, that is h(z)=−(ψ(1−z)+γ)/πh(z)=-(\psi(1-z)+\gamma)/\pi with ψ\psi the digamma function. Then Sk=(k+1)/πS_k=(k+1)/\pi up to an error below 2−k2^{-k}.
  • Probit: Im⁡Φ−1(t+i0)\operatorname{Im}\Phi^{-1}(t+i0) is computed by continuing Φ−1\Phi^{-1} from z=1/2z=1/2 around the branch point z=1z=1, with Newton's method on erfc⁡\operatorname{erfc} along the path. It is positive (minimum 0.540.54), so all cm>0c_m>0, with c1,…,c4=0.694, 0.297, 0.182, 0.130c_1,\dots,c_4=0.694,\,0.297,\,0.182,\,0.130, cm∼1/(m2log⁡m)c_m\sim1/(m\sqrt{2\log m}) and Sk≈2log⁡kS_k\approx\sqrt{2\log k}. After a run of length kk the estimator returns about τ Φ−1(1−1/k)\tau\,\Phi^{-1}(1-1/k). Procedure and cost. For the probit link, the boundary values on 5⋅1045\cdot10^4 points take 0.20.2 s, and a table of SkS_k at 600600 logarithmically spaced kk up to 10910^9 takes 0.50.5 s. This is done once per link. Any SkS_k can also be computed on demand by one quadrature, so runs of any length are handled without truncation.

Checks. The representation ∑mcm(pm−(1−p)m)=σ−1(p)\sum_mc_m(p^m-(1-p)^m)=\sigma^{-1}(p) holds on [0.03,0.97][0.03,0.97] to 10−1510^{-15} (logistic), 10−1410^{-14} (cauchit) and 7⋅10−77\cdot10^{-7} (probit, quadrature error). In simulation with 2⋅1062\cdot10^6 draws, the three estimators are unbiased within two standard errors at κ∈{0.5,1.5,3}\kappa\in\{0.5,1.5,3\}.

Consequences. For the logistic and cauchit links we prove E[Δ~2]≤13(τ+∣Δ∣)2\mathbb E[\tilde\Delta^2]\le13(\tau+|\Delta|)^2 and ≤5(τ+∣Δ∣)2\le5(\tau+|\Delta|)^2 for every gap, and all moments are finite; Assumption 3.2's margin r>αr>\sqrt\alpha is then not needed for these two links. For the probit link these properties hold numerically (E[Δ~2]≤0.96(τ2+Δ2)\mathbb E[\tilde\Delta^2]\le0.96(\tau^2+\Delta^2) at the tested gaps up to 4.6τ4.6\tau), but we do not have a proof, and Proposition 3.3 still provides proven probit coefficients on every fixed operated range. The revision will include the formula, the proofs for the logistic and cauchit links, the probit computation, and the code.

Knowledge of τ\tau (Question 2). The estimator of Δ/τ\Delta/\tau, namely (2Y1−1)SN−1(2Y_1-1)S_{N-1}, does not involve τ\tau. The temperature enters the algorithm only as a global scale of the gradient estimate and, through the parameter choices, as the ratios L/τL/\tau, Δf/τ\Delta_f/\tau and ε/τ\varepsilon/\tau: the problem constants measured in units of the comparison noise. Knowing τ\tau separately from these is not required.

The link itself can also be unknown. Because the pair (x−ρu,x+ρu)(x-\rho u,x+\rho u) is antithetic, the even part of σ\sigma cancels, and the law of G^:=d2ρ(2Y−1)u\hat G:=\frac d{2\rho}(2Y-1)u depends on σ\sigma only through ψ(t)=σ(t)−σ(−t)\psi(t)=\sigma(t)-\sigma(-t). Assume σ′(0)≥s0>0\sigma'(0)\ge s_0>0 and ∣ψ(t)−2σ′(0)t∣≤C3∣t∣3|\psi(t)-2\sigma'(0)t|\le C_3|t|^3 for all tt; any link with three continuous derivatives near 00 qualifies, and the logistic link has C3=1/24C_3=1/24. Then E[G^]=2σ′(0)τ∇fρ(x)+b(x),∥b(x)∥≤111 C3L3ρ2dτ3,\mathbb E[\hat G]=\frac{2\sigma'(0)}\tau\nabla f_\rho(x)+b(x),\qquad\|b(x)\|\le\frac{111\,C_3L^3\rho^2}{d\tau^3}, using spherical concentration of the gap, and ∥G^∥=d/(2ρ)\|\hat G\|=d/(2\rho) almost surely. The unknown scale is positive, and since ∥G^∥\|\hat G\| is known exactly, the step size of the conversion does not depend on it. We extended the online-to-nonconvex conversion to a biased oracle (the bias adds 2βˉ2\bar\beta to the stationarity bound) and obtain, with ρ=min⁡{δ/2,τs0dε/(222C3L3)}\rho=\min\{\delta/2,\tau\sqrt{s_0d\varepsilon/(222C_3L^3)}\} and an explicit integer schedule, N=O(s1s03⋅Δhδε3(C3s0⋅dL3ε+d2τ2δ2)),s1:=(27C3/32)1/3,N=O\Big(\frac{s_1}{s_0^3}\cdot\frac{\Delta_h}{\delta\varepsilon^3}\Big(\frac{C_3}{s_0}\cdot\frac{dL^3}{\varepsilon}+\frac{d^2\tau^2}{\delta^2}\Big)\Big),\qquad s_1:=(27C_3/32)^{1/3}, comparisons, one per pair. The algorithm uses s0s_0 and C3C_3, a class of links, but not σ\sigma. At high temperature this matches the known-link rate; at low temperature it costs a factor of order C3L/(s0ε)C_3L/(s_0\varepsilon), and we do not know whether that factor is necessary. The revision will include this as a section with full proofs.

Gap between the bounds, and dependence on Δf\Delta_f (Weakness 2). Following an observation by Reviewer K4C5, the upper bound improves. Our analysis bounded every queried gap by 2Lρ2L\rho; since Δu=f(x+ρu)−f(x−ρu)\Delta_u=f(x+\rho u)-f(x-\rho u) is odd and 2Lρ2L\rho-Lipschitz on the sphere, it concentrates at scale Lρ/dL\rho/\sqrt d, and the cost and second moment can be controlled direction by direction. With ρ=min⁡{δ/2,cτd/L}\rho=\min\{\delta/2,c\tau\sqrt d/L\} the estimator uses O(1)O(1) comparisons per gradient estimate, and the complexity becomes O(dL2Δhδε3(1+dτ2L2δ2))O\big(\frac{dL^2\Delta_h}{\delta\varepsilon^3}(1+\frac{d\tau^2}{L^2\delta^2})\big). On the hard family of Theorem 5.1 (initial gap 128εδ128\varepsilon\delta) this is O(dL2/ε2+d2τ2/(δ2ε2))O(dL^2/\varepsilon^2+d^2\tau^2/(\delta^2\varepsilon^2)), whose comparison-specific term equals the lower bound. So for initial gaps of order εδ\varepsilon\delta the dependence on dd, τ\tau, δ\delta and ε\varepsilon is settled up to link constants.

The lower bound does not capture the dependence on Δf\Delta_f. For smooth functions without a global Lipschitz bound, an exact first-order oracle simulates a comparison, which gives Ω(Δf/(δε))\Omega(\Delta_f/(\delta\varepsilon)) by reduction to Carmon et al. (2020); their construction is not globally Lipschitz, so this does not directly apply to our class. A joint bound in (d,δ,ε,Δf)(d,\delta,\varepsilon,\Delta_f) is open even for value oracles (Kornowski and Shamir, 2023), and Appendix A.6 explains why lengthening our hard family into a chain does not prove it.

Presentation (Weakness 3). We agree. The revision restructures the main text:

  • an overview section with a diagram of the pipeline (comparisons, gap estimate, gradient estimate, online-to-nonconvex conversion) and the role of each assumption;
  • a paragraph of intuition before each main result;
  • a discussion of the assumptions: known or unknown link, repeated comparisons, global Lipschitz constant;
  • a notation table;
  • proof sketches moved to the appendix.

We have uploaded a revised version; new and revised parts are shown in blue. In relation to your review:

  • Coefficients beyond the logistic link (Section 3.1, Appendix A.2). Proposition 3.2 gives the coefficients in closed form for the cauchit link, cm=ζ(m+1)/πc_m=\zeta(m+1)/\pi, with k/π≤Sk≤(k+1)/πk/\pi\le S_k\le(k+1)/\pi, and Theorem 3.4(iii) proves the gap-uniform bound E[Δ~2]≤5(τ+∣Δ∣)2\mathbb{E}[\tilde\Delta^2]\le5(\tau+|\Delta|)^2 for it. For the probit link we compute the coefficients numerically and state them as numerical evidence, not as a proof; Proposition 3.1(ii) gives proven probit coefficients on every fixed operated range.
  • Knowledge of the link and of τ\tau (Section 4). For an unknown link with σ′(0)>0\sigma'(0)>0 and a smooth odd part, one comparison of an antithetic pair gives the smoothed gradient up to a positive scale and a bias quadratic in the radius (Lemma 4.2). The estimator uses neither σ\sigma nor τ\tau; the guarantee of Theorem 4.3 uses one comparison per pair and bounds on the link's slope and curvature at 00. Section 4 also explains why these assumptions are mild.
  • Gap between the bounds (Sections 3.2 and 3.3). Theorem 3.8 now uses a radius adapted to the typical queried gap and gives O((1+dτ2/(L2δ2)) dL2Δh/(δϵ3))O\big((1+d\tau^2/(L^2\delta^2))\,dL^2\Delta_h/(\delta\epsilon^3)\big); run with the Lipschitz constant of the hard instances, it matches the lower bound on them. The joint dependence on Δf\Delta_f remains open.
  • Presentation. The paper is restructured as known link (Section 3), then unknown link (Section 4), with the main results in the main text, proofs in the appendix, and intuition after each result.

Thank you for your response. The response and the paper revisions partially addressed my concerns. In particular, the new section on unknown link and computation for cauchit link. I still think the paper will benefit more from improving the presentation, adding more context and intuition. I will increase my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the discussion

We thank the reviewers and the Area Chair. We summarize the discussion and the revision.

Contributions. To our knowledge, this is the first work to give guarantees for (δ,ϵ)(\delta,\epsilon)-Goldstein stationarity of nonsmooth nonconvex functions from noisy comparisons, and the first lower bound in this setting:

  1. a characterization of the links whose inverse can be estimated exactly from comparisons (lens analyticity, with a counterexample showing that real analyticity does not suffice), with coefficients beyond the logistic link and moment bounds uniform in the gap;
  2. the rate O((1+dτ2/(L2δ2)) dL2Δh/(δϵ3))O\big((1+d\tau^2/(L^2\delta^2))\,dL^2\Delta_h/(\delta\epsilon^3)\big), which equals the value-oracle rate at low noise;
  3. the lower bound Ω(d2τ2/(ϵ2δ2))\Omega(d^2\tau^2/(\epsilon^2\delta^2)), which this rate matches on the hard instances;
  4. for an unknown link, a guarantee with one comparison per pair, requiring only a positive slope at zero and a bounded third-order remainder.

Together, these say whether comparisons cost more than function values, by how much, and what knowledge of the link buys.

Correctness. No reviewer identified an error in the results. Reviewer K4C5 suggested the argument behind the improved upper bound, which the revision adopts as Theorem 3.8, and Reviewer q22j found the unknown-link section a useful addition.

Revision (changes in blue):

  • the improved upper bound, with an explicit schedule, and its match with the lower bound on the hard instances (Sections 3.2 and 3.3);
  • coefficients beyond the logistic link: in closed form for the cauchit link, and numerical for the probit link, stated as numerical evidence (Section 3.1, Appendix A.2);
  • the relation to inverse binomial sampling: the logistic estimator is the r=1r=1 form of Mendo's log-odds estimator with a shared first comparison (Remark 3.5, Appendix A.4);
  • the unknown-link guarantee (Section 4, Appendix B);
  • a restructured presentation (known link, then unknown link, with proofs in the appendix);
  • new experiments with 10 seeds, theorem-prescribed parameters, longer runs and other links (Section 5, Appendix C).

Remaining concerns.

  • Regime of the lower bound. Reviewer q22j no longer counts it against the paper. The bound covers initial gaps of order ϵδ\epsilon\delta and is tight there up to constants; a joint bound in (d,δ,ϵ,Δf)(d,\delta,\epsilon,\Delta_f) is open even for value oracles (Kornowski and Shamir, 2023).
  • Significance of the unbiased estimator relative to one comparison per pair.
    • The guarantee for one comparison per pair is itself a result of this paper. Under a link such as Bradley–Terry, comparisons at small gaps are correct with probability close to 1/21/2, and to our knowledge no prior guarantee covers this case for nonsmooth nonconvex objectives.
    • At low noise, the unbiased estimator lets comparisons reach the rate of the best known method with function values; our bound for one comparison per pair is larger by a factor L/ϵL/\epsilon, whose necessity is open, as the paper states.
    • The unbiased estimator yields an unbiased stochastic gradient with a second-moment bound, which any algorithm analyzed under these conditions can use with its guarantee unchanged; the one-comparison estimator is biased with an unknown scale and needs a separate analysis for each algorithm.
  • No practical advantage of unbiased estimation in the experiments. We report this plainly. The predicted advantage is in the exponent of ϵ\epsilon at low noise, so it concerns accuracies our budgets do not reach. The contribution we claim is theoretical.
  • Novelty. We have listed the new results and the prior work they extend in our replies; the discussion has not pointed to prior work containing them.

Reviewer mKai's questions concerned the coefficients beyond the logistic link, knowledge of the temperature, the gap between the bounds, and the presentation. They are addressed in Proposition 3.2 and Appendix A.2, Section 4, Sections 3.2 and 3.3, and the restructured paper respectively.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.