acceptodds
Under review as a conference paper at ICLR 2027

When Do Rankings Beat Signs? Gradient Direction Recovery under Even Nuisance

Abstract

Can ranking a batch of antipodal query pairs recover a gradient direction with fewer evaluations than using within-pair signs alone? We study fixed-center recovery in dimensions for a linear signal plus an unknown differentiable even nuisance, counting function evaluations and feedback rounds separately. Shared pair offsets create an information hierarchy: Mirror retains within-pair signs, Reverse couples reversed cross-pair orders to cancel offsets, and Full enforces all ranking inequalities. Relative shell variation is the nuisance range over the query sphere normalized by the linear-signal scale. When it is at most , Reverse localizes every consistent direction to angular accuracy using evaluations in one round at fixed confidence, without a variation bound supplied to the decoder. This matches a lower bound up to logarithmic factors, versus the one-round sign-only minimax cost on the same class. Over well-conditioned positive-definite quadratics with no common relative-curvature bound, the -round minimax cost is instead , even with cumulative rankings. We extend validity beyond exact evenness under supplied error bounds. Matched-endpoint experiments certify information beyond signs and short cycles. On two ridge tasks under joint evaluation and round caps, short-cycle recovery attains lower terminal mean gaps than the tested batch-capable controls. An additional optimization benefit from fitting the complete ranking remains unestablished.

Primary area:
learning theory
Keywords:
gradient direction recovery, comparison-based optimization, antipodal query pairs, even nuisance, relative shell variation, whole-cell recovery, cumulative rankings, feedback rounds

Reviews

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

The paper studies gradient estimation from comparisons, specifically, whether antipodal-query rankings can recover gradient directions faster than within-pair signs rankings. It identifies some form of information hierarchy within this model, prove a nearly optimal bound, and certify information gains. Validation on two datasets show some improvements over the baseline method ZO-RankSGD.

Critical strengths

The paper seems to provide thorough theoretical analysis and discussion. I could not check the correctness, see critical weaknesses below.

Critical weaknesses

The way the paper is written is very convoluted, with many new (and often ambiguous) terms introduced without sufficient definition or context. For example,

(L014) Shared pair offsets create an information hierarchy: Mirror retains within-pair signs, Reverse couples reversed cross-pair orders to cancel offsets, and Full enforces all ranking inequalities.

What are shared pair offsets, within-pair signs, and cross-pair orders? Mirror, reverse, and full are also yet to be defined.

(L018) When it is at most cϵ/dc\epsilon / \sqrt d, ...

c is undefined.

(L051) f(x)=b+gTx+E(x)f(x) = b + g^Tx + E(x)

f, b, and g are undefined. Undefined variables also show in the equations in the analysis. For example, u^,v,z,K(⋅)\hat{u}, v, z, K(\cdot) in page 3. Also, multiple interpretations of the optimization problem exist without further clarifications. For example, is it a design optimization (e.g., find x that maximizes an objective function f(x)), or a predictor optimization (e.g., find b and g that minimizes a loss function L(f(x) - f^{gt}(x)))?

(L072) Even noiseless orders need not exclude the alternative directions allowed by signs. Nor does an accurate estimate alone establish an information gain: other directions can remain consistent.

What does it mean for an "alternative direction" to be "allowed by signs", and "other directions can remain consistent"=?

On several occasions, sentences have the correct words and grammars, but serve unclear purposes in the text. For example,

(L116) A batch is chosen before its feedback arrives.

(L119) A round is one feedback synchronization, not a count of comparisons or annotation efforts.

(L269) Gradients, optima, and held-out losses are audit quantities.

(L283) Lines guide the eye.

(L323) MSE also depends on the analytic-center selector; the exact cycle witnesses do not.

(L358) Squared loss is exactly linearplus-even at every center.

There are also paragraphs with multiple short statements where the readers have to infer how the sentences tie together. For example,

(L143) Strict observations are relaxed to weak candidate inequalities. Observed ties impose both inequalities. Adjacent-order inequalitie suffice. Repeated physical pairs share one offset. A common additive offset changes no order, so one offset can be fixed. On one shell xi=aWix_i = aW_i, rescaling gives C(w,π)C(w,\pi) Across shells retain physical coordinates and the same gradient. Mirror keeps within-pair signs; Reverse adds all signed relations from Equation (4).

These issues occur throughout the paper and make the paper very hard to understand, even with significant effort and multiple re-readings. As a result, I might have missed other important strengths and weaknesses.

Questions for authors

The paper requires a major revision in its presentation before I can properly assess its technical contributions.

Reviewer_BhnVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies fixed-center gradient-direction recovery from ranked antipodal queries for a linear signal plus an unknown differentiable even nuisance. It distinguishes Mirror constraints from within-pair signs, Reverse constraints from offset-cancelling two-edge cycles, and Full consistency with the complete ranking. Under sufficiently small relative shell variation, it proves nearly optimal one-round recovery using order d+d/εd + \sqrt{d/\varepsilon} endpoints up to logarithmic factors, compared with order d/εd/\varepsilon for one-round sign-only recovery. It also establishes a tight endpoint–round tradeoff over quadratics with unbounded curvature scale and extends validity to calibrated departures from evenness. Experiments examine information gains, direction estimation, and optimization on low-dimensional ridge tasks.

Critical strengths
  1. A substantive characterization of when rankings add information. Theorem 2 localizes the entire consistency set, and Reverse alone attains the stated rate. The decoder does not receive a shell-variation bound. The proof handles dependence among comparisons through endpoint-disjoint witnesses, and the one-round lower bound matches the rate up to logarithmic factors. Theorem 3 complements this result by showing that even well-conditioned quadratics can erase the minimax advantage when their curvature scale is unbounded. This is a meaningful separation between the favorable and unfavorable regimes.

  2. Careful separation of information gains from optimization gains. Proposition 1 and the exact negative-cycle witnesses show that Full can exclude directions surviving Reverse, independently of the numerical direction selector. The paper also reports that Full's extra information has not produced an established optimization advantage over Reverse, and that STP and CMA-ES attain lower gaps when the round cap is removed (Tables 2–3). Explicit endpoint accounting and these qualifications strengthen the empirical interpretation.

Critical weaknesses
  1. The fast recovery regime still requires difficult operational conditions. Theorem 2 assumes relative shell variation of order ε/d\varepsilon/\sqrt{d}. Although this quantity need not be supplied to the decoder, a general procedure for selecting a radius that achieves the condition is not established. Outside exact evenness, the robust guarantees need supplied error calibration, and the implemented initializer is not guaranteed throughout the full robust-localization regime (Section 4.4 and Appendix J.4). Exact-even validity remains intact at larger variation; it is the accelerated recovery rate and its use in a general optimizer that are limited.

  2. The optimization comparisons do not isolate the practical benefit of the additional information. On the ridge tasks, Full and Reverse use unit directions, whereas ZO-RankSGD is not normalized before line search. There is a matched Mirror comparison, but no independently tuned Mirror arm against the external controls (Appendix H.3). Moreover, on these inexpensive objectives, Reverse's reported whole-run times are 0.43/0.61 seconds on Airfoil/Concrete versus 0.10/0.05 for ZO-RankSGD (Appendix H.5). In the separate scaling study, fitting takes a median 1.64 seconds at d=100d=100, N=1600N=1600, while optional certification takes 142.55 seconds (Table 12). Certification should be charged only when used. The results establish information gains and lower terminal gaps under the tested joint caps, but leave attribution and time-to-accuracy benefits unresolved.

Questions for authors
  1. Evidence for attribution. Under the same development budget and line-search convention, how do a unit-normalized ZO-RankSGD control and an independently tuned Mirror control perform on the ridge tasks? The normalized control on the separate non-even task cohort does not resolve this ridge-specific comparison.

  2. Practical cost clarification. Can the recorded trajectories and resource ledger support a comparison of time to a common training-gap target, including direction fitting and any radius selection? Reverse and ZO-RankSGD spend the same endpoint and round budgets in Table 5, so higher feedback latency alone does not remove Reverse's additional fitting cost at that fixed budget. A matched-accuracy comparison, or a quantified comparison with the more sequential controls, would clarify when the information gain yields a time advantage. Please report optional certification separately.

Reviewer_J68vOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies gradient direction recovery when the function evaluation is unavailable and only comparisons are allowed, with an even nuisance (i.e., the noise is symmetric). This paper asks whether when the cross-pair comparisons (rankings) has a benefit over using only within-pair comparisons (signs), in an antipodal query batch, under the one-round feedback. The paper establishes a tight (up to log term) evaluation bound, which is an improved bound compared to the bound for signs.

Critical strengths
  • This paper shows that using the cross-pair comparisons can improve complexity compared to only using within-pair comparison, and using the cross-pair comparisons has been shown to be near-optimal by establishing a lower bound.
Critical weaknesses

Clarity Issues

  1. Several definitions are not sufficiently provided. Terms such as Mirror, Reverse, Full are not clearly defined in the paper, although they are central to the paper's contribution. As a result, the reader has to infer their meanings from the context. Also, some notation (proj⁡v(⋅),vi,Crev,Cmirror\operatorname{proj}_{v}(\cdot), v_{i}, C_{\text{rev}}, C_{\text{mirror}}, ...) is not rigorously defined.
  2. The use of undefined terminology. For instance, reverse, (short-)cycles, two-edge, ... Since the inequality constraints can be interpreted as a graph, the reader may infer that the terms such as "cycle" or "edge" denote a chain of the constraints or an offset. However, this still leaves the reader with the burden of inferring precise definitions from context. Furthermore, it does not appear to have a specific reason why terminologies from graph theory are adopted.

Others

  • It appears to lack sufficient motivation and justification for studying even nuisance.
Questions for authors
  • In Theorem 2, is it correct to interpret uu as u^\hat{u} (in P(u∈C… )\mathbb{P}(u\in \mathcal{C}\dots))?
  • It would be helpful if the authors could provide the motivation of Theorem 3, as it is unclear how the theorem relates to the other results.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.