用配对比较反馈实现在线凸优化，首次获得理论保证。
Online Convex Optimization with Dueling Feedback
- 将配对偏好转化为近似梯度，适配经典优化方法。
- 达到首次提出的 $\mathcal{O}(T^{3/4})$ 静态与动态后悔界。
- 在光滑或强凸条件下，性能提升至 $\mathcal{O}(T^{2/3})$ 或 $\mathcal{O}(\sqrt{T \log T})$。
我们研究带有配对比较反馈的在线凸优化问题，其中学习者仅能观察到两个查询点之间的二元偏好。尽管在离散或随机设置下配对反馈已被充分理解，但对抗性凸设定仍无人探索。本文提出一种简单归约方法，将配对反馈转化为近似梯度，从而可使用标准一阶方法。我们证明该归约下后悔界可传递，首次获得此设定下的理论结果，包括 $\mathcal{O}(T^{3/4})$ 的静态、自适应与动态后悔。在额外结构假设下，光滑目标可达 $\mathcal{O}(T^{2/3})$，强凸函数则为 $\mathcal{O}(\sqrt{T \log T})$。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。