arXiv:2606.11711cs.LGstat.ML2026-06被引 1

在资源有限时,如何高效处理延迟反馈的在线优化问题。

Capacity-Constrained Online Convex Optimization with Delayed Feedback

  • 设计随机调度器与加权损失机制,应对追踪能力受限的延迟反馈。
  • 首次给出容量约束下凸与强凸损失的后悔界,首阶反馈仅需 C=Ω(log T)。
  • 适用于资源受限场景,尤其适合实时系统与在线推荐等应用。

传统在线凸优化(OCO)在反馈延迟时通常假设学习者可无限追踪所有未完成轮次,但实际中追踪资源有限,未跟踪的反馈将永久丢失。本文研究在硬容量约束下的延迟在线凸优化,即任意时刻最多只能追踪 $C$ 个未完成轮次。为建模延迟信息,提出一种半透明模型:学习者无需预知延迟,而是在运行中在线观察延迟过期事件,符合经典无约束延迟设定。通过将问题转化为新的“延迟加权”OCO,设计随机调度策略并重要性加权观测结果。针对该基础问题,提出并分析了延迟加权FTRL及其带限版本,建立了显式刻画时变权重与延迟反馈交互关系的后悔界。结合调度器,首次获得容量约束下凸与强凸损失的后悔保证,涵盖一阶与带限反馈。对于一阶反馈,当容量 $C = Ω("log T$) 时,可恢复标准延迟OCO率,仅差对数因子;对于带限反馈,后悔率受 $(1 + σ_{\text{max}}/C)$ 的幂次调节,其中 $σ_{\text{max}}$ 为任意时刻最大待处理观测数,当 $C < σ_{\text{max}}$ 时后悔界平滑退化但仍保持亚线性。

原文摘要 · Abstract (English)

Online learning with delayed feedback typically assumes that the learner can track all pending rounds until their feedback arrives. In practice, tracking resources are finite, and feedback from untracked rounds is permanently lost. In this paper, we study delayed online convex optimization (OCO) under a hard capacity constraint, where at most $C$ pending rounds can be tracked at any time. To model delay information, we introduce a semi-clairvoyant model that refines the clairvoyant assumption from prior work: rather than requiring delays to be known at prediction time, the learner observes delay expirations online, consistent with the classical unconstrained delayed setting. Our approach proceeds via a reduction to a novel ``delayed and weighted'' OCO problem, using a scheduler that randomizes tracking decisions and importance-weights the resulting observations. For this base problem, we propose and analyze Delayed-Weighted FTRL and its bandit analogue, establishing regret bounds that explicitly characterize the interaction between time-varying weights and delayed feedback. Combining these base learners with our schedulers yields the first regret guarantees for capacity-constrained OCO under convex and strongly convex losses, for both first-order and bandit feedback. For first-order feedback, capacity $C = Ω(\log T)$ suffices to recover standard delayed OCO rates up to logarithmic factors. For bandit feedback, the regret rates are modulated by powers of $(1 + σ_{\text{max}}/C)$, where $σ_{\text{max}}$ is the maximum number of pending observations at any time. This allows the regret bound to degrade gracefully when $C < σ_{\text{max}}$, while remaining sublinear.

在线学习延迟反馈凸优化后悔界

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