Online Convex Optimization with Dueling Feedback

We study online convex optimization with dueling (pairwise comparison) feedback, where the learner observes only a binary preference between two queried points. While dueling feedback is well understood in discrete or stochastic settings, the adversarial convex setting has remained unexplored. 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 the first results for this setting, including O(T^{3/4}) static, adaptive, and dynamic regret. Under additional structure, we obtain improved rates of O(T^{2/3}) for smooth objectives and O(\sqrt{T \log T}) for strongly convex functions.