arXiv:2602.02634cs.LG2026-02被引 4

将延迟反馈在线优化转化为即时反馈,显著提升性能上限。

A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees

  • 构建连续时间模型,分离学习与延迟影响,实现自适应延迟处理。
  • 带噪凸优化中,延迟相关项从 $O( ext{min}ig\\/sqrt{T d_{\text{max}}},(Td_{\text{tot}})^{1/3}\big\$ 改进为 $O(\sqrt{d_{\text{tot}}})$。
  • 适用于高延迟场景下的在线学习算法设计,尤其适合强凸问题。

我们提出一种基于归约的框架,用于处理延迟反馈的在线凸优化,可恢复并改进现有第一阶与贝叶斯凸优化结果。该方法引入连续时间模型,使遗憾分解为与延迟无关的学习项和延迟引起的漂移项,从而实现延迟自适应归约:将任意在线线性优化算法转化为能处理轮次相关延迟的算法。在贝叶斯凸优化中,我们显著改进了遗憾界,延迟相关项达到当前最优的一阶率。在第一阶反馈下,通过更简洁统一的分析复现了现有最优遗憾界。定量上,对于贝叶斯凸优化,我们获得 $O(\sqrt{d_{\text{tot}}} + T^{3/4}\sqrt{k})$ 遗憾,将延迟相关项从之前工作的 $O(\text{min}\{\sqrt{T d_{\text{max}}},(Td_{\text{tot}})^{1/3}}\}$ 提升至 $O(\sqrt{d_{\text{tot}}})$。在强凸条件下,得到 $O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\} + (T^2\ln T)^{1/3} k^{2/3})$,将延迟相关项从之前的 $O(d_{\text{max}} \ln T)$ 改进为 $O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\})$,其中 $σ_{\text{max}}$ 为最大未完成观测数,可能远小于 $d_{\text{max}}$。

原文摘要 · Abstract (English)

We develop a reduction-based framework for online learning with delayed feedback that recovers and improves upon existing results for both first-order and bandit convex optimization. Our approach introduces a continuous-time model under which regret decomposes into a delay-independent learning term and a delay-induced drift term, yielding a delay-adaptive reduction that converts any algorithm for online linear optimization into one that handles round-dependent delays. For bandit convex optimization, we significantly improve existing regret bounds, with delay-dependent terms matching state-of-the-art first-order rates. For first-order feedback, we recover state-of-the-art regret bounds via a simpler, unified analysis. Quantitatively, for bandit convex optimization we obtain $O(\sqrt{d_{\text{tot}}} + T^{\frac{3}{4}}\sqrt{k})$ regret, improving the delay-dependent term from $O(\min\{\sqrt{T d_{\text{max}}},(Td_{\text{tot}})^{\frac{1}{3}}\})$ in previous work to $O(\sqrt{d_{\text{tot}}})$. Here, $k$, $T$, $d_{\text{max}}$, and $d_{\text{tot}}$ denote the dimension, time horizon, maximum delay, and total delay, respectively. Under strong convexity, we achieve $O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\} + (T^2\ln T)^{\frac{1}{3}} {k}^{\frac{2}{3}})$, improving the delay-dependent term from $O(d_{\text{max}} \ln T)$ in previous work to $O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\})$, where $σ_{\text{max}}$ denotes the maximum number of outstanding observations and may be considerably smaller than $d_{\text{max}}$.

在线学习延迟反馈凸优化遗憾界

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。