Online Convex Optimization with Dueling Feedback

Yiyang Lu; Hareshkumar Jadav; Mohammad Pedramfar; Ranveer Singh; Vaneet Aggarwal

cs.LGAug 15, 2026

Online Convex Optimization with Dueling Feedback

Authors: Yiyang Lu, Hareshkumar Jadav, Mohammad Pedramfar, Ranveer Singh, Vaneet Aggarwal

Organizations: Purdue University · IIT Indore · Mila - Quebec AI Institute/McGill University

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 $\mathcal O(T^{3/4})$ static and adaptive regret, and $\mathcal O(T^{3/4}\sqrt{1+P_T/D})$ dynamic regret with unknown comparator path length $P_T$ . For strongly convex losses, the static and adaptive bounds improve to $\widetilde{\mathcal O}(T^{2/3})$ . For smooth losses, we presents unified dueling ellipsoidal FTRL, and proves $\widetilde{\mathcal O}(T^{2/3})$ static regret, which improves to $\widetilde{\mathcal O}(\sqrt T)$ under additional strong convexity.

Figures & tables

Loss class	Benchmark	Regret bound	Result
Convex	Static / Adaptive	$\mathcal{O}(T^{3/4})$	Theorem 2
Convex	Dynamic	$\mathcal{O}(T^{3/4}\sqrt{1+P_{T}/D})$	Theorem 3
Strongly convex	Static	$\mathcal{O}(T^{2/3}\ell_{T}^{1/3})$	Theorem 4
Strongly convex	Adaptive	$\mathcal{O}(T^{2/3}\ell_{T}^{2/3})$	Theorem 5
Smooth convex	Static	$\mathcal{O}(T^{2/3}\ell_{T}^{1/3})$	Corollary 1
Strongly convex, smooth	Static	$\mathcal{O}(\sqrt{T\ell_{T}})$	Corollary 2

Table 1: Dueling regret guarantees of this work, for fixed problem parameters. Here

\ell_{T}=1+\log T

and

P_{T}=\sum_{t=2}^{T}\|w_{t}^{*}-w_{t-1}^{*}\|_{2}

. The first four rows respectively use DTFO with OGD, Improved Ader, SC-OGD, and binary IFLH (Section 4 ), and the last two use ellipsoidal FTRL(Section 5 ). Each row uses its stated algorithm and tuning, and the first row gives both benchmarks for one run. The dynamic algorithm does not require

P_{T}

. The smooth rows additionally assume

|\rho^{\prime\prime\prime}|\leq M_{3}

and access to a self-concordant barrier. All comparators lie in

\mathcal{K}

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Reference	Setting and benchmark	Guarantee
Yue and Joachims (2009)	Fixed strictly concave utility; preference regret against its maximizer	$\mathcal{O}(T^{3/4})$
Lu et al. (2022)	Time-varying utilities in the DBGD model; preference regret against per-round maximizers	$\tilde{\mathcal{O}}(T^{3/4}\sqrt{1+C_{T}})$ Unknown $C_{T}$
Kumagai (2017)	Noisy strongly convex, smooth loss; preference regret with objective-value conversion	$\mathcal{O}(\sqrt{T\log T})$
Saha et al. (2025)	Fixed smooth convex loss; optimization error under general preferences	Sample complexity depending on accuracy and transfer function
This work (convex)	Changing convex losses; objective-value regret against arbitrary comparators	$\mathcal{O}(T^{3/4}\sqrt{1+P_{T}(U)})$ Unknown $P_{T}(U)$

Appendix

Table 2: Selected continuous dueling results. The metrics and comparator classes differ:

C_{T}

is the path length of per-round optimizers, while

P_{T}(U)

is the path length of an arbitrary comparator sequence. Rates suppress dimension, geometry, and link constants.

Explore similar work

Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback
May 25, 2026Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos +2Convex Loss \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret
Singapore University of Technology and Design · National Technical University of Athens · Archimedes, Athena Research Center, Greece +3
Online Convex Optimization with Sublinear Noisy Probes
Jun 12, 2026Simone Di Gregorio, Anupam Gupta, Stefano Leonardi +1\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Convex Optimization
Sapienza University of Rome, Italy · New York University, USA · EPFL, Switzerland
Small Gradient Norm Regret for Online Convex Optimization
Jan 20, 2026Wenzhi Gao, Chang He, Madeleine UdellInterval Regret Regret
ICME, Stanford University · SIME, Shanghai University of Finance and Economics · Department of Management Science and Engineering, Stanford University

May 25, 2026, cs.LGJ/K move · Enter open · S save

Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback

Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos, Ioannis Panageas+1

Singapore University of Technology and Design · National Technical University of Athens · Archimedes, Athena Research Center, Greece+3

Convex Loss \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Optimal Regret Hessian Bandits Adversarial Training

Open paper AskPDF arXiv

We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu and Hazan (2022) proved that, under geometric and smoothness assumptions, online gradient descent (OGD) on such nonconvex losses approximately simulates online mirror descent (OMD) on the underlying convex losses with a suitable regularizer, yielding

\mathcal{O}(T^{2/3})

regret. They left open whether the optimal

Θ(\sqrt{T})

regret from online convex optimization can be recovered in this hidden-convex setting. We answer this question affirmatively. More specifically, via a sharper discrete-time algorithmic equivalence argument, we prove that OGD achieves

\mathcal{O}(\sqrt{T})

regret under the same assumptions, matching the optimal worst-case rate for adversarial online convex optimization. We also address another open question of Ghai, Lu and Hazan (2022) by clarifying the geometry required for this algorithmic equivalence. We replace the diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition, thereby expanding the class of admissible reparameterizations. We complement our tight regret bound with a lower bound showing that the Hessian compatibility assumption is essential for OGD; when it fails, we construct a smooth reparameterization and an adversarial sequence of hidden-convex losses for which OGD suffers

Ω(T)

regret. Finally, we extend our analysis to one-point bandit feedback and prove a

\mathcal{O}(T^{3/4})

expected regret bound for bandit OGD with spherical smoothing, matching its classical rate on convex losses.

Abstract

Explore similar work

Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback

Online Convex Optimization with Sublinear Noisy Probes

Small Gradient Norm Regret for Online Convex Optimization