提出无需调参的动态后悔界，适配时变移动成本与延迟反馈。
Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory
- 设计新算法，实现可自适应比较器的动态后悔界。
- 后悔上界为√((M²+MP_T)(T+∑λ_t))，首次支持时变移动成本。
- 适用于延迟反馈和记忆时变场景，对算法设计有普适意义。
本文研究无约束在线凸优化（OCO）中的动态后悔，允许移动成本系数λ_t随时间任意变化。提出一种新算法，首次建立该设置下的比较器自适应动态后悔界，保证后悔上界为˜𝒪(√((M²+MP_T)(T+∑λ_t)))，其中P_T为比较器序列在T轮内的路径长度，M为比较器的最大范数。当所有λ_t=0时，该结果退化为标准静态与动态后悔最优率。通过两个应用验证结果通用性：含延迟反馈的OCO与含时变记忆的OCO。我们证明两者均可转化为时变移动成本问题，尤其为延迟反馈场景建立了具有独立价值的新归约方法。关键发现是：后悔界中对移动成本的一阶依赖，是实现最优比较器自适应动态后悔保障的核心因素。
原文摘要 · Abstract (English)
In this paper, we study dynamic regret in unconstrained online convex optimization (OCO) with movement costs. Specifically, we generalize the standard setting by allowing the movement cost coefficients $λ_t$ to vary arbitrarily over time. Our main contribution is a novel algorithm that establishes the first comparator-adaptive dynamic regret bound for this setting, guaranteeing $\widetilde{\mathcal{O}}(\sqrt{(M^2+MP_T)(T+\sum_t λ_t)})$ regret, where $P_T$ is the path length of the comparator sequence over $T$ rounds and $M$ is the maximal comparator norm. Our result recovers the optimal adaptive rates for both static and dynamic regret in OCO as the special case where $λ_t=0$ for all rounds. To demonstrate the versatility of our results, we consider two applications: OCO with delayed feedback and OCO with time-varying memory. We show that both problems can be translated into time-varying movement costs, establishing a novel reduction specifically for the delayed feedback setting that is of independent interest. A crucial observation is that the first-order dependence on movement costs in our regret bound plays a key role in enabling optimal comparator-adaptive dynamic regret guarantees in both settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。