Online Convex Optimization with Dueling Feedback

arXiv:2608.15050v1 Announce Type: new Abstract: 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.

Source: arXiv cs.LG | 2026-08-18