aiqbench analysis
This research addresses the adversarial online convex optimization problem under dueling feedback, where only binary preferences between points are observed rather than full gradient information. By reducing this limited feedback scenario to approximate gradients, the authors establish new regret bounds that enable standard first-order methods in previously unexplored settings. The work advances theoretical understanding of learning algorithms operating with minimal data signals, which is relevant for resource-constrained AI systems and recommendation engines relying on pairwise comparisons.
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 $\mathcal{O}(T^{3/4})$ static, adaptive, and dynamic regret. Under additional structure, we obtain improved rates of $\mathcal{O}(T^{2/3})$ for smooth objectives and $\mathcal{O}(\sqrt{T \log T})$ for strongly convex functions.
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 $\mathcal{O}(T^{3/4})$ static, adaptive, and dynamic regret. Under additional structure, we obtain improved rates of $\mathcal{O}(T^{2/3})$ for smooth objectives and $\mathcal{O}(\sqrt{T \log T})$ for strongly convex functions.
Machine Learning (cs.LG)
arXiv:2608.15050 [cs.LG]
(or arXiv:2608.15050v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2608.15050 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 196 words
Related coverage
Capacity-Constrained Online Convex Optimization with Delayed Feedback
arXiv · Jun 12, 2026
Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions
arXiv · Jul 23, 2026
Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
arXiv · Jun 9, 2026
Online Convex Optimization with Sublinear Noisy Probes
arXiv · Jun 15, 2026