- 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 instead of for the comparator sequence, as the star notation may incorrectly suggest that must be a per-round minimizer.
6 comments
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 , Lemma 1 supplies the estimate , and all experts receive the shared surrogate gradient at their own predictions . For a known curvature lower bound , 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 on a fixed interval , where is the query radius and 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 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.
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 ut instead of wt∗ for an arbitrary comparator sequence
We now use ut and U 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.