acceptodds
Under review as a conference paper at ICLR 2027

Online Convex Optimization with Dueling Feedback

Abstract

Noisy binary comparison between two candidates is a common interface between human and learning systems, especially in modern large language model (LLM) post-training alignment. We study online convex optimization with dueling (pairwise comparison) feedback, where the learner observes only a binary preference between two queried points. We consider adversarial sequences of convex losses and measure regret with the loss at both queried points, under a comparison link with a known nonzero slope at the origin. We propose a simple reduction that converts dueling feedback into approximate gradients, enabling the use of standard first-order methods. We show that regret guarantees transfer under this reduction, yielding static and adaptive regret, and dynamic regret with unknown comparator path length . For strongly convex losses, the static and adaptive bounds improve to . For smooth losses, we presents unified dueling ellipsoidal FTRL, and proves static regret, which improves to under additional strong convexity.

Primary area:
optimization
Keywords:
Dueling, Convex, Bandit, Smooth, Strongly Convex, Online, Adversarial

Reviews

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

The paper studies online convex optimization with noisy binary comparison feedback, and proposes DTFO, a reduction framework that converts dueling feedback into approximate gradient information. By combining this reduction with existing first-order algorithms, the authors obtain expected static, dynamic, and interval regret bounds. An ellipsoidal FTRL method further improves the static bounds under smoothness and strong convexity.

Critical strengths
  • The paper studies a meaningful problem and measures regret directly in terms of the underlying losses, accounting for both queried actions.

  • The reduction provides a unified, reusable framework for applying existing online algorithms under dueling feedback. The ellipsoidal bias analysis, particularly the cancellation of the inverse exploration matrix, is a useful technical contribution.

Critical weaknesses
  • The technical novelty appears limited. The core results, Theorem 1 and Lemma 1, mainly rely on standard arguments and appear to require few new technical ideas. Although the ellipsoidal bias analysis provides useful refinements, the overall contribution seems incremental.

  • The definition of expected interval regret in (1) introduces the expected operation. Therefore, all regret bounds for the original losses hold in expectation over exploration and comparison noise, whereas first-order baselines such as Ader provide deterministic guarantees. This distinction should be emphasized in the main comparisons, particularly since no high-probability guarantee is provided.

Questions for authors
  • What motivates introducing expected interval regret? This formulation appears unnecessary, as the same results could be obtained by analyzing the three standard regret notions separately.

  • Are the proposed regret bounds optimal? Can the authors provide matching lower bounds or discuss the gap between their upper bounds and existing lower bounds?

  • I suggest using utu_t instead of wt∗w_t^* for the comparator sequence, as the star notation may incorrectly suggest that wt∗w_t^* must be a per-round minimizer.

6 comments
AuthorsOpenReview ↗

Response to Reviewer n4hN - Part 1

Thank you for the review and for recognizing the loss-based benchmark at both queried actions, the reusable reduction, and the ellipsoidal bias analysis. We address the three questions first, followed by the remaining weaknesses.

Q1. What motivates introducing expected interval regret? Could the three standard regret notions be analyzed separately?

The interval formulation states the regret reduction once for a fixed interval and an arbitrary comparator sequence. A first-order algorithm's surrogate-regret guarantee can then be inserted directly: a full-horizon fixed comparator gives static regret, a comparator path gives dynamic regret, and an interval's best fixed comparator gives adaptive regret. The projection used in the reduction also preserves the required path-length bound.

The three consequences could be analyzed separately. The Introduction and Section 2 now state that the notation packages the standard benchmarks so the regret reduction can be written once. The definition describes expected regret on an interval and does not introduce an additional performance measure.

Q2. Are the regret bounds optimal? Can you provide matching lower bounds or discuss the gap?

We do not claim general minimax optimality. The paper provides upper bounds under comparison feedback, and it does not establish matching lower bounds for the general convex, nonsmooth strongly convex, smooth convex, or dynamic guarantees. The exploration/estimation tradeoff determines the stated parameter tuning but does not itself prove a lower bound.

The value-feedback rates supply reference results under different observation protocols. In particular, matching a classical exponent does not establish optimality under one noisy comparison per round. Conversely, a one-point value-feedback lower bound cannot be imported automatically: a duel queries two actions, receives a different random observation, and charges both actions. A matching lower bound requires an argument for the comparison protocol or a suitable reduction. Section 6 now states the unresolved optimality gaps explicitly, and Appendix A explains the value-feedback comparisons.

Q3. Use utu_t instead of wt∗w_t^* for an arbitrary comparator sequence

We now use utu_t and UU for arbitrary comparator sequences in the definitions, regret-reduction theorem (Theorem 1), dynamic theorem, and their proofs. Stars are reserved for actual hindsight minimizers, which Section 2 defines explicitly for static and adaptive regret. The dynamic theorem allows any comparator path fixed independently of learner randomization; it does not require per-round minimizers.

AuthorsOpenReview ↗

Response to Reviewer n4hN - Part 2

W1. The core arguments appear standard and the overall technical contribution incremental

The contribution beyond existing analysis has two parts, now distinguished in the Introduction before Contributions.

General reduction (Lemma 1 and Theorem 1). From one comparison at the query center wtw_t, Lemma 1 supplies the estimate g^t\widehat g_t, and all experts receive the shared surrogate gradient ∇qt(w)=g^t+σ(w−wt)\nabla q_t(w)=\widehat g_t+\sigma(w-w_t) at their own predictions ww. For a known curvature lower bound σ>0\sigma>0, the surrogate's curvature and exp-concavity hold for every realized bit, even when the original losses are nonsmooth. These properties support strongly convex updates and expert aggregation without additional comparisons. Theorem 1 bounds expected original-loss regret at both queries by expected surrogate regret plus Csphδ∣I∣C_{\mathrm{sph}}\delta|I| on a fixed interval II, where δ\delta is the query radius and CsphC_{\mathrm{sph}} depends on the problem parameters. Projection preserves arbitrary comparator paths' path-length bounds. The resulting interface supports static, dynamic, and adaptive base guarantees.

Additional smooth-loss analysis (Equation (11), Lemma 2, and Theorem 6). Under smooth losses and the additional third-derivative link bound, the ellipsoidal analysis controls the conditional estimator bias BtB_t by

\le \frac{2M_3G^3}{\gamma(d+2)} \delta^2\operatorname{tr}(A_t^2).$$ Here $A_t$ is the exploration matrix, and the bias is relative to the smoothed-loss gradient. Although the estimator contains $A_t^{-1}$, the inverse matrix cancels before the remainder is bounded. Lemma 2 / Equation (12) then compares with unperturbed comparators, including boundary points, while retaining the strong-convexity term and the same geometric scaling of the combined error. No loss evaluations outside the domain are required. Theorem 6 combines these properties with FTRL. Under strong convexity, $\|A_t\|_{\mathrm{op}}^2\le1/(\eta\sigma t)$ yields a harmonic geometric sum, with its $1/\eta$ prefactor retained in the analysis. The Introduction now pairs these obstacles with the corresponding results and defines the inline notation locally. Standard surrogate ingredients are credited in Section 3.1, the shared spherical identity with Saha et al. (2025) is identified after Lemma 1 in Section 3.2, and the inherited exploration method is credited to Hazan and Levy (2014) in Sections 1 and 5.2. The contribution concerns the guarantees and compatible error control established by this analysis. For the precise comparison with Saha et al.'s Lemma 3, please also see our response to Reviewer m5ik, Q1(b). Also see Reviewer m5ik, Q1(a) for more details on the general technical contribution compared with existing analysis. The revision summary, Key change 1, summarizes the two parts and their manuscript locations. ## W2. Original-loss guarantees are expected, while first-order baselines can be deterministic; no high-probability guarantee is given Our original-loss guarantees take expectation over query directions, comparison outcomes, and any internal randomization, for an oblivious loss sequence and comparator sequences independent of learner randomization. The base first-order surrogate bounds hold pathwise, but the conversion to the original losses uses conditional expectations. The abstract and Tables 1-2 now identify the original-loss guarantees as expected, and Section 2 distinguishes them from the pathwise surrogate bounds. The paper does not provide a high-probability original-loss regret theorem. For adaptive regret, the maximum is taken over fixed intervals after expectation. This does not control the expectation of the largest interval regret selected after observing a realized run. Remark 1 now states this order explicitly and retains the distinction between our full-horizon bounds and strongly adaptive bounds in the interval length.

Dear Reviewer,

As the discussion period is nearing its end, we would appreciate hearing if you have any remaining questions or concerns regarding our response. We would be happy to provide further clarification.

Thank you for your time and consideration.

Reviewer_DmTvOpenReview ↗
Rating
2(−1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses the problem of online convex optimization with noisy preference feedback. The paper applies a spherical gradient estimator and a curvature approximator function for convex and strongly convex losses, with proven guarantees in expected regret for the convex and strongly convex cases.

Critical strengths

Interesting problem and result.

The regret of the smoothed loss is approximated with a linear term and bounded, and this extends to the original loss. It works for fixed, moving and per-interval comparators, considering adversarial regret in loss values under preference only feedback

The overall results sit on an ellegant lemma 1, where the sphere-to-ball identity is applied to the link composed with the loss difference before the link is linearized. This fact that the identity is applied before linearization allows for matrix A cancellation, thus tightening the bounds.

Critical weaknesses

The paper writing should be improved. The contributions section mentions many symbols not defined yet at that point and this hinders comprehension.

Novelty seems to be small, as the bounds are proven elsewhere as seen in Tab 1. The paper contribution resides on the link bias staying inside the existing analyses.

The analysis needs γ\gamma to be known and ρ′(0)\rho'(0) to be non zero, excluding sign only feedback and flat links, and the Bradley Terry temperature is in general not known. For example the (not mentioned) paper https://proceedings.mlr.press/v139/saha21b/saha21b.pdf proves that adversarial dueling optimization is impossible with sign feedback. This would help to define where the results of the paper will hold.

There are no experiments in the paper, despite the LLM RLHF and DPO motivation. Given the results in expected regret, it would be informative to see at least experimentally in a couple of examples how variance behaves.

Questions for authors

What are the bound improvements over Flaxman et al. 2005, Agarwal et al. 2010 (strongly convex), Saha and Tewari 2011 (smooth functions), Hazan and Levy 2014?

About the (not mentioned) JMLR paper https://jmlr.org/papers/v22/20-763.html: the dynamic bound matches the known one-point value-feedback rate of Zhao et al 2021. Looks like comparison feedback with a known link yields no rate change relative to value feedback. So, what is the novelty in this direction?

4 comments
AuthorsOpenReview ↗

Response to Reviewer DmTv - Part 1

Thank you for the review and for highlighting the matrix-cancellation argument. We first address the two questions, then the remaining points in the weaknesses.

Q1. What are the bound improvements over Flaxman et al. (2005), Agarwal et al. (2010), Saha and Tewari (2011), and Hazan and Levy (2014)?

The main difference is the observation model. Those results use numerical function values, while our learner observes only a noisy binary comparison, without either function value or their numerical difference. Extracting a usable gradient signal requires controlling the bias induced by the nonlinear comparison link. The value-feedback bounds serve as reference rates for placing the comparison-feedback guarantees in context, and should not be treated as benchmarks we directly improve upon.

The relationships in horizon dependence are as follows, with fixed problem parameters and logarithmic factors suppressed where appropriate:

ReferenceValue-feedback resultRelation to our guarantee
Flaxman et al. (2005)One-point convex static regret O(T3/4)O(T^{3/4})We obtain the same exponent using one noisy comparison per round.
Agarwal et al. (2010)Two-point convex and strongly convex rates O(T)O(\sqrt T) and O(log⁡T)O(\log T), in horizon dependenceThese use two numerical value observations and are faster reference rates under that protocol.
Saha and Tewari (2011)One-point smooth convex static regret O~(T2/3)\widetilde O(T^{2/3})Our smooth comparison-feedback guarantee has the same exponent, with additional nonlinear-link bias control.
Hazan and Levy (2014)One-point smooth, strongly convex static regret O~(T)\widetilde O(\sqrt T)We obtain this exponent with comparisons by controlling the link error in shrinking exploration geometry.

Thus we are not claiming improved exponents over these value-feedback results. The improvements within our comparison-feedback framework concern the additional structure of the losses: strong convexity or smoothness improves the general convex bound, and their combination yields the O~(T)\widetilde O(\sqrt T) static guarantee. The Introduction now explains the feedback distinction, and Appendix A gives these static-rate comparisons explicitly.

Q2. The dynamic bound matches Zhao et al. (2021). What is the novelty if a known link yields no change in rate relative to value feedback?

Zhao et al. (2021) study numerical value feedback, while our learner receives only one noisy comparison bit between two queried actions. Even with a known local link slope, a single bit does not reveal the numerical loss difference. Their value-based estimator cannot be used directly: the comparison mean is a nonlinear transformation of that difference, so the reduction must control the resulting bias in the loss-based regret.

Our dynamic result recovers the T3/41+PTT^{3/4}\sqrt{1+P_T} dependence, with fixed problem parameters suppressed, using this comparison protocol and without knowing the comparator path length. The result shows how a first-order dynamic-regret method can be used with a single shared comparison signal while controlling its error. Appendix A now discusses Zhao et al. explicitly as a reference across feedback models. Section 6 states that we do not claim minimax optimality or establish a matching dynamic lower bound.

W1. Symbols in the contributions are introduced too late

The abstract now defines the domain diameter and comparator path length before the rate expression. The contribution summary defines PTP_T, ℓT\ell_T, and the curvature parameter σ\sigma before using them, and the two titled paragraphs before Contributions state the added guarantees with concise mathematical notation: the shared-surrogate gradient relation and the conditional bias norm bound. Their symbols are defined locally, with references to the detailed results in Sections 3 and 5.

AuthorsOpenReview ↗

Response to Reviewer DmTv - Part 2

W2. The technical contribution appears to be keeping link bias within an existing analysis

The rate comparisons are addressed in Q1-Q2. The general reduction first supplies one shared surrogate with ∇qt(w)=g^t+σ(w−wt)\nabla q_t(w)=\widehat g_t+\sigma(w-w_t), so experts at different predictions use the same comparison. Under strong convexity, its curvature and exp-concavity hold for every realized bit, including for nonsmooth original losses. Theorem 1 bounds expected original-loss regret by expected surrogate regret plus the explicit error penalty. The additional smooth-loss analysis makes nonlinear-link error compatible with the exploration geometry and curvature. For ellipsoidal exploration, the estimator includes At−1A_t^{-1}, but the bias bound is $ |\mathbb E_t\widehat g_t-\bar g_t|_2 \le \frac{2M_3G^3}{\gamma(d+2)} \delta^2\operatorname{tr}(A_t^2). $

The inverse matrix cancels before the remainder is bounded, leaving an error that decreases with the ellipsoid. A feasible-comparator argument then retains the strong-convexity term and accommodates boundary comparators without evaluating losses outside the domain around them. Together these properties yield a harmonic geometric sum under strong convexity, with its learning-rate prefactor retained in the analysis. The revised Introduction and Section 5.1 now explain the obstacles and the corresponding bias and comparison arguments; Equation (12) displays their joint consequence with curvature explicit. Section 3.1 credits the standard surrogate ingredients, and Section 5.2 retains the attribution of the regularized-Hessian method to Hazan and Levy (2014).

For the detailed comparison with Saha et al. (2025), including the shared spherical identity and the differences in the subsequent regret analysis, please also see our response to Reviewer m5ik, Q1(b).

W3. Known nonzero slope, unknown temperature, and the sign-feedback impossibility result

The nonzero local slope ensures that sufficiently local comparison probabilities encode the magnitude of a small loss difference. The generic estimator uses γ=−ρ′(0)\gamma=-\rho'(0) to calibrate this signal, and the strongly convex and ellipsoidal methods use this scaling in their updates or tuning. Unknown Bradley-Terry temperature is therefore a substantive limitation of those procedures. Assumption 1 now states that γ\gamma is known, and Section 2 explains this calibration and the exclusion of sign-only feedback and zero-slope links. The full link formula need not be known beyond the stated derivative bounds.

Thank you for pointing us to Saha, Koren, and Mansour (2021), Dueling Convex Optimization, now discussed in Appendix A. Their noisy sign channel is invariant to positive rescaling of loss differences, and their objective is final-output optimization of an average loss. Our regular link has a known nonzero local derivative, so the channel and objective differ. Their impossibility result does not contradict our regret guarantees; it does not imply impossibility for every flat smooth link.

W4. No experiments, particularly on variance, despite the RLHF/DPO motivation

We have added numerical illustrations in the two-page Appendix G (pp. 38–39), including explicit across-run dispersion statistics in Table 4. Each configuration uses 64 independent runs on one fixed synthetic loss sequence, with a simulated Bradley-Terry oracle. At T=106T=10^6, d=4d=4, and γ=2\gamma=2, the across-run standard-deviation-to-mean ratios are:

Method and its loss familySD / mean regret
ORGD, cone3.7%
SC-OGD, cone plus quadratic10.1%
Ellipsoidal method, smooth Huber6.0%
Ellipsoidal method, smooth strongly convex quadratic53.2%

Each row uses its own loss family. The last row shows substantial dispersion. With 64 runs, the standard error of the mean is SD/8, so small standard-error bars alone would obscure the variability of an individual run. These statistics provide a numerical illustration of the distinction; they are not high-probability regret guarantees or proofs of asymptotic rate tightness.

Figure 1(a,b) shows static regret for these four synthetic configurations. A small boundary-optimum example in Figure 1(c) compares spherical and ellipsoidal exploration on the same smooth loss, illustrating the geometry relevant to Section 5.1. Appendix G specifies the losses, simulated comparison oracle, algorithm parameters, randomization and evaluation protocol, comparator calculations, and software environment. The experiments are controlled convex simulations. The RLHF/DPO motivation concerns the availability of pairwise preferences and continuous tuning; these illustrations do not model end-to-end neural-network training.

See also the Revision Summary, Key changes 1–3, for the shared contribution, feedback-comparison, and experimental-revision overview.

I thank the authors for their response. I find the text of the response very difficult to read. Also the paper writing maintains the critical weakness of opaque writing. Simulations were done in place of experiments with real data, even if a couple of simple problems. Simulated data is important to prove a point or illustrate a specific property of the method, but does not replace the unexpected behavior of real data. My positive assessment was based on a trust that the authors could fix the problems and clarifications of novelty I pointed out on my review, as I deemed them easy to address and I really like this problem and found the solution interesting. After the rebuttal I feel the paper is not ready yet for publication.

AuthorsOpenReview ↗

TLDR version of Q1Q2 response + experiment on real data (HelpSteer2)

Thank you for the follow-up. We greatly appreciate your confidence. We have uploaded a revised PDF with exmeriment on real human evaluation data and would keep this reply short.

Q1 and Q2 (bound improvements and novelty)

We do not claim faster rates. These are different access models, so the value-feedback rates are reference points, not benchmarks under equal conditions. With one comparison per round, our bounds match, up to logarithmic factors, the rates known for one loss value per round: those of Flaxman et al. (2005), Saha and Tewari (2011) and Hazan and Levy (2014), and the one-point dynamic regret of Zhao et al. (2021). They do not reach the faster rates that use two loss values of the same loss per round, namely those of Agarwal et al. (2010) and the two-point dynamic regret of Zhao et al. (2021). Dueling feedback is more restrictive: two noisy loss values with a matching noise model can simulate one comparison, so lower bounds carry over from value feedback while upper bounds do not. A comparison never reveals a loss value, only one noisy bit about a loss difference through a nonlinear link, so value-based estimators cannot be used directly. The novelty is reaching the one-value rates under this more restrictive model. The rewritten Introduction states where a direct extension of value-feedback techniques fails and what we do instead.

Real data and variance

Appendix G.3 adds an experiment on HelpSteer2 dataset, whose losses come from human ratings of language-model responses (6,713 human preference pairs). The comparisons are simulated, because logged comparisons cannot be queried again at new points. But the dataset comes from human evaluation and would reflect realistic distribution in practical scenario. Figure 2 shows regret and its variability: by T=106T=10^6 every method has 12–20% of the regret of the fixed decision w=0w=0, and from T=104T=10^4 on the run-to-run standard deviation stays between 18% and 48% of the mean.

Novelty and Writing

The Introduction is rewritten. It states where a direct extension of existing techniques fails and what we do instead. Under changing losses, an unbiased preference gradient targets the wrong point, so we treat each comparison as a biased gradient of the loss and bound the bias (Lemma 1). Expert methods need a gradient for every expert, and the shared linear surrogate of Improved Ader has no curvature, so we use a quadratic surrogate that is strongly convex and exp-concave for every comparison. Under ellipsoidal exploration, the link error grows as the ellipsoid shrinks, so we apply the averaging identity before linearizing the link, which cancels At−1A_t^{-1} (the step you highlighted) and gives a smooth strongly convex rate that Proposition 3 shows is optimal up to logarithmic factors.

We thank the reviewer for the feedback and are happy to address any remaining questions if possible

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

This paper studies online convex optimization under dueling feedback (i.e., giving two points, wt+w_t^+ and wt−w_t^-, the outcome of observing wt+w_t^+ as better is ρ(ft(wt+)−ft(wt−))\rho(f_t^(w_t^+)-f_t(w_t^-)), where ρ\rho has a known strictly-negative derivative at 00). The authors give T3/41+PT/DT^{3/4}\sqrt{1+P_T/D} bounds for dynamic regret / static regret / adaptive regret (BTW, DD is never defined in abstract and intro), and improvements for strongly convex / smooth / strongly convex+smooth losses.

Critical strengths

This exact model, adversarial convex losses, a bit of dueling feedback, and dynamic regret has not been considered before, and hence the results complement the literature.

Critical weaknesses

The results are quite boring and incremental. The T3/4T^{3/4} rate long existed in one-point BCO (Flaxman 05), whose estimator is basically the same as this paper, but those rates are later known to be sub-optimal (with many different ways of attaining T\sqrt T regret). It's hence hard to believe this paper is optimal (esp it's simply a tradeoff between OGD's T/δ\sqrt T/\delta and the δT\delta T bias). The so-called "expected interval regret" is basically just dynamic regret + adaptive regret, and the same (dynamic regret+adaptive regret) rate T3/41+PTT^{3/4}\sqrt{1+P_T} also already appeared in one-point BCO as well (Zhao 21).

The only "technical" new thing is moving from one point to dueling. But I don't really see how this approach differs from existing ones on dueling (especially, the authors claim "The sphere-to-ball identity is classical for one-point estimators, but never applied under the link" for their key Lemma 1, but apologies if I missed something really obvious, I don't quite succeed in identifying its difference from Sara 25's Lemma 3).

The writing is also extremely poor. Don't quite see the benefit of introducing a bunch of existing jargons/terminologies new names, e.g., "expected interval regret", "link distortion", "comparison-to-surrogate transfer", "regret transfer", without clearly defining/distinguishing them.

To me, this paper is only acceptable if the authors could justify (near-)optimality of their results and/or technical contributions.

Questions for authors

See weaknesses.

7 comments
AuthorsOpenReview ↗

Response to Reviewer m5ik - overview

Thank you for the detailed review. We understand that your main concern is whether the results establish a substantive technical contribution and how their optimality should be assessed. Q1 explains the additional technical contribution beyond the shared spherical identity and compares with Saha 25' Leamma 3 specifically, and Q2 clarifies that bandit rates serve as reference points rather than direct benchmarks and that optimality is open for further studies.

AuthorsOpenReview ↗

Response to Reviewer m5ik - Part 1 - Q1(a) General contribution and technical obstacle

Q1. What does the analysis add beyond existing dueling estimators, particularly Saha et al. (2025), Lemma 3?

Q1(a). General contribution and technical obstacle

We obtain adversarial loss-based regret guarantees on a continuous domain from one noisy comparison per round, charging both queried actions and supporting fixed, moving, and interval comparators. The contribution concerns this combination of feedback, loss metric, and comparator scope. Existing continuous-dueling results include stationary objective-regret connections (Kumagai, 2017) and nonstationary preference regret against per-round optimizers (Lu et al., 2022); these do not supply the combination addressed here.

A direct combination of the existing guarantees does not establish this result. Progress toward a fixed objective's minimizer does not by itself bound cumulative regret when the objective changes every round, and preference regret is measured after the nonlinear link rather than in the original losses. Moving to a first-order regret framework therefore requires additional arguments connecting the comparison signal, the queried losses, and the comparator. The following three issues explain why the tools do not immediately combine and how we make them compatible:

  • A comparison direction alone does not provide the surrogate structure needed by the base regret guarantee. Lemma 1 controls the estimator norm and its O(δ)O(\delta) conditional bias for convex Lipschitz losses, where δ\delta is the query radius. A linear surrogate would discard curvature. We use qt(w)=⟨g^t,w⟩+σ2∥w−wt∥22q_t(w)=\langle\widehat g_t,w\rangle+\frac\sigma2\|w-w_t\|_2^2, where wtw_t is the query center and σ≥0\sigma\ge0 is the known curvature lower bound. An expert predicting wt,jw_{t,j} computes ∇qt(wt,j)=g^t+σ(wt,j−wt)\nabla q_t(w_{t,j})=\widehat g_t+\sigma(w_{t,j}-w_t) from the same comparison. For σ>0\sigma>0, curvature and exp-concavity hold for every realized bit, even when the original losses are nonsmooth. Theorem 1 then bounds expected regret at both queries by expected surrogate regret plus Csphδ∣I∣C_{\mathrm{sph}}\delta|I| on each fixed interval II, with CsphC_{\mathrm{sph}} defined in Section 3.3. Projecting an arbitrary comparator path preserves its path-length bound. These properties support strongly convex updates and expert aggregation within the one-comparison budget; the standard surrogate ingredients are credited in Section 3.1.
  • The smooth-loss guarantees require additional bias control in shrinking geometry. Under smooth losses and the additional third-derivative link bound, a direct estimate of the nonlinear remainder can retain ∥At−1∥op\|A_t^{-1}\|_{\mathrm{op}}, which may grow as the exploration ellipsoid shrinks. Canceling this matrix before bounding the remainder gives ∥Bt∥2=∥Etg^t−gˉt∥2≤2M3G3γ(d+2)δ2tr⁡(At2)\|B_t\|_2=\|\mathbb E_t\widehat g_t-\bar g_t\|_2\le\frac{2M_3G^3}{\gamma(d+2)}\delta^2\operatorname{tr}(A_t^2) in Equation (11). Here BtB_t is the conditional bias relative to the smoothed-loss gradient and AtA_t is the exploration matrix. The bound makes this extra comparison-feedback error contract with the geometry already used by value-feedback FTRL.
  • The learner's exploration geometry need not be feasible around a boundary comparator. A direct comparison of smoothed learner and comparator losses can require evaluations outside the domain. Moving the comparator inward to accommodate the same perturbation can introduce a first-order loss error, which does not provide the desired squared-geometry bound. We instead apply smoothness and strong convexity at the same feasible learner perturbation and compare directly with the unperturbed comparator. This preserves curvature and keeps the error proportional to δ2tr⁡(At2)\delta^2\operatorname{tr}(A_t^2).

Together, these arguments establish the following per-round inequality under the additional smoothness and third-derivative link assumptions, for every fixed u∈Ku\in\mathcal K, including boundary points: Et[ft(wt+)+ft(wt−)2−ft(u)]≤Et⟨g^t,wt−u⟩−σ2∥wt−u∥22+cd,σδ2tr⁡(At2).\mathbb E_t\left[\frac{f_t(w_t^+)+f_t(w_t^-)}{2}-f_t(u)\right] \le \mathbb E_t\langle\widehat g_t,w_t-u\rangle-\frac{\sigma}{2}\|w_t-u\|_2^2 + c_{d,\sigma}\delta^2\operatorname{tr}(A_t^2). Here cd,σc_{d,\sigma} is the explicit coefficient in the per-round inequality in Lemma 2. The key compatibility property is that curvature and feasibility are retained while the combined error has the squared-geometry form needed by the shrinking-Hessian analysis. Under strong convexity, ∥At∥op2≤1/(ησt)\|A_t\|_{\mathrm{op}}^2\le1/(\eta\sigma t) gives a harmonic geometric sum, with its 1/η1/\eta retained in the analysis, supporting the O~(T)\widetilde O(\sqrt T) static guarantee. The shared-surrogate construction also underlies the spherical reduction and its static, dynamic, and adaptive consequences, while the displayed squared-error bound belongs specifically to the smooth analysis.

AuthorsOpenReview ↗

Response to Reviewer m5ik - Part 2 - rest of questions and weaknesses

The two titled Introduction paragraphs now state these two parts explicitly. The first includes the shared-surrogate gradient relation, its per-bit properties, and Theorem 1's regret penalty, then points to the Saha discussion after Lemma 1. The second defines the bias in Equation (11), explains the inverse-matrix and boundary-feasibility obstacles, and identifies Lemma 2 / Equation (12) and Theorem 6 as the additional smooth-loss analysis. See also the General response, Key change 1, for the common overview and manuscript locations.

Q1(b). Specific comparison with Saha et al. (2025), Lemma 3

Their Lemma 3 proves conditional progress toward a fixed smooth objective's minimizer. Its proof contains the same spherical first-moment identity used in our Lemma 1, up to scaling and sign convention. In that specialization, our gradient-plus-bias decomposition follows by rescaling and adding and subtracting the derivative at zero. Section 3.2 now credits this shared step in a separate comparison paragraph, and we have removed “never applied under the link.” Published paper

Our Lemma 1 treats nonsmooth convex Lipschitz losses and feasible ellipsoidal exploration, with an explicit spherical bias bound. Their link class allows flat links, whereas ours requires a known nonzero slope and bounded curvature, so the assumptions differ in both directions.

For the feasible-comparator step in Q1(a), a concrete distinction is that their derivation of Eq. (5), on PDF page 6, uses losses at the perturbed optimum w∗±rVw^*\pm rV. Our comparison instead uses the unperturbed comparator and retains the strong-convexity term. The trace-bias estimate and resulting regret reduction in Q1(a) are subsequent analysis built on the shared identity.

Q2. How should the rates be compared with bandit convex optimization, and are they optimal?

The bandit bounds provide reference rates under a different observation model. In particular, Zhao et al. (2021) receive numerical function values, whereas our learner receives one noisy binary comparison and observes neither queried value nor their numerical difference. A comparison bit has a mean that is a nonlinear function of the loss difference. Their value-based estimator is therefore unavailable in our setting, and obtaining original-loss regret requires controlling the additional link-induced bias under changing losses.

Our dynamic bound recovers the same dependence on the horizon and comparator path length as their one-point value-feedback bound, with fixed problem parameters suppressed. Similarly, the convex static T3/4T^{3/4} exponent is a classical reference rate. The contribution is obtaining these guarantees under comparison-only observations, together with the analysis needed to control their error. The Introduction and Appendix A now explain this role of the bandit rates, with the explicit Zhao et al. comparison in Appendix A.

We do not claim that the general convex or dynamic bounds are minimax optimal. Balancing the terms in an upper bound determines its tuning, which does not establish a matching lower bound. Section 6 now states explicitly that no matching lower bounds are established here for the general convex, nonsmooth strongly convex, smooth convex, or dynamic guarantees.

For a reference-by-reference comparison of the static rates, please also see our response to Reviewer DmTv, Q1.

Q3. Why introduce “expected interval regret” instead of using the standard regret notions separately?

The interval formulation lets us prove the regret reduction once and recover static, dynamic, and adaptive regret through the corresponding choices of interval and comparator, instead of repeating three separate proofs. It is a notational convenience for the standard benchmarks, not a new regret measure. The Introduction and Section 2 now make this purpose explicit.

W1. Undefined notation and overlapping terminology

We use “link bias” for the estimator's mean error relative to the smoothed-loss gradient, defined next to Lemma 1. “Regret reduction” consistently means bounding expected original-loss regret by surrogate regret plus explicit bias, smoothing, and projection errors, as stated before Theorem 1. In the smooth analysis, Lemma 2 is simply the per-round regret bound used with FTRL. We removed “link distortion” and the separate “comparison-to-surrogate transfer” and “query-to-surrogate transfer” labels, and replaced the overlapping “regret transfer” terminology throughout the manuscript. These terminology edits preserve the mathematical bounds and assumptions. The abstract, Introduction and contribution summary now defines paratmeter before appearing in statements.

Comments on the paper

3 comments
AuthorsOpenReview ↗

revision summary

We thank the reviewers for their careful reading and constructive feedback. We have clarified the technical contribution and attribution, the feedback model and guarantee scope, and the presentation, and added numerical validations. All added or replacement manuscript text is blue. The key changes are:

  1. Clarified the technical contribution and made relation with existing techniques explicit: We integrated the technical novelty discussion into two Introduction paragraphs before Contributions, covering the general regret reduction and the additional analysis under smoothness. Both paragraphs credit existing ingredients and clarify what our analysis adds, with a pointer to the detailed Saha comparison after Lemma 1. (m5ik Q1, n4hN W1, and DmTv W2; Introduction p. 2; Sections 3 and 5)

  2. Clarified feedback comparisons, assumptions, and optimality limits: Value-feedback bandit bounds are reference rates across different observation/feedback setting: our learner observes one noisy bit, without access to either queried value or their numerical difference. They are provided to contextualize our results. We claim neither direct improvement over the cited value-feedback results nor minimax optimality. We now explicitly state the known nonzero local-slope requirement, the unknown-temperature limitation, and the sign-only/zero-slope exclusions, and discuss the relevant impossibility result. (m5ik Q2, n4hN Q2, and DmTv Q1–Q2/W3; Introduction; Section 2; Appendix A; Section 6)

  3. Added numerical validation and variability measurements: We report 64 independent learner/oracle runs per configuration and distinguish across-run SD from SE of the mean. One compact figure shows the four static configurations and a small same-loss boundary comparison. The appendix supplies the simulation and implementation details. These are finite-horizon validations, without tightness or high-probability claims. (DmTv W4; Appendix G, pp. 38–39; Figure 1; Table 4)

  4. Simplified terminology and made the guarantee qualifications explicit: We use 'expected regret on an interval' for the unified regret notion and clarifies its convenience purpose that helps unify proof. We removed unnecessary 'new names'. Arbitrary comparators use utu_t, and notation is defined before use. (m5ik Q3/W1, n4hN Q1/Q3/W2, and DmTv W1; abstract; Introduction; Section 2; Tables 1–2; Sections 3 and 5)

AuthorsOpenReview ↗

second round revision summary

We appreciate reviewers' feedback, and we have added new results in green. Text revisions from both rounds are in blue.

New results (green)

  • High-probability bounds: Proposition 1 (end of Section 3) bounds the realized regret of both queries, on every interval, with probability at least 1−p1-p. Proposition 2 (end of Section 4) gives high-probability versions of Theorems 2–5 (ORGD, Dynamic ORGD, SC-OGD and IFLH). They have the same horizon exponents as the expected bounds. Proofs are in Appendix H.
  • Lower bound: Proposition 3 (end of Section 5) shows that under a logistic link on the unit ball, every algorithm has regret Ω(min⁡T,dT/γ)\Omega(\min\\{T, d\sqrt T/\gamma\\}). This matches Corollary 2 in TT up to logarithmic factors, and also in dd and γ\gamma for γ≤1\gamma\le 1. The proof is in Appendix I. We also add an explicit discussion on optimality at the end of Section 1.
  • Table 1: two new columns, high-probability bounds and lower bounds. High-probability bounds for the ellipsoidal method are marked as open.

Text revisions (blue)

  • Introduction revised to present, in order:
    • the motivation and practical application of the access model
    • why spherical smoothing and expert aggregation do not extend directly to comparisons;
    • the changes that make them work:
      • the averaging identity is applied before the link is linearized;
      • a shared quadratic surrogate has curvature that is fixed before the comparison;
      • under shrinking ellipsoids, the bias is O(δ2tr⁡(At2))O(\delta^2\operatorname{tr}(A_t^2)) against unperturbed comparators;
    • the contributions, the optimality context from the related bandit convex optimization, and the relation to prior work.
  • Appendix A adds
    • an example where averaged comparisons favor the point with the larger cumulative loss;
    • a comparison with the lower bounds of Kumagai (2017) and Jamieson et al. (2012).
  • References to equation numbers are added throughout proofs. Each appendix title clarifies what it proves, and the main text points to each proof.
  • Notation: two symbols in the high-probability proof differ from our earlier replies, to avoid clashes with symbols already in the paper, including the variable called λ\lambda in our replies to reviewer n4hN is now ζ\zeta, and ata_t is now written directly as wt−vtw_t - v_t.

added experiments on real data: human rating dataset (HelpSteer2)

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.