Online Convex Optimization with Dueling Feedback

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(T3/4) static and adaptive regret, and mathcal O(T3/4√1+PT/D) dynamic regret with unknown comparator path length PT. For strongly convex losses, the static and adaptive bounds improve to widetildemathcal O(T2/3). For smooth losses, we presents unified dueling ellipsoidal FTRL, and proves widetildemathcal O(T2/3) static regret, which improves to widetildemathcal O(√ T) under additional strong convexity.