提出可自适应折扣因子的在线优化算法，统一处理不同遗忘速度。
Discounted Online Convex Optimization: Uniform Regret Across a Continuous Interval
- 用多个梯度下降实例并行应对不同折扣率，通过DNP算法动态聚合结果。
- 实现对任意λ∈[0,1)连续区间的统一$O(√{\log T / (1-λ)})$折扣后悔界。
- 适合非平稳环境下的在线学习，尤其适用于未知历史权重衰减场景。
在非平稳环境中，近期数据比远期数据更重要，因此引入了λ-折扣后悔（discounted regret）以渐进遗忘旧信息。当折扣因子λ已知时，适当步长的在线梯度下降可达到$O(1/√{1-λ})$的折扣后悔。然而，在真实场景中λ往往未知。本文正面回答这一开放问题：通过新分析证明平滑在线梯度下降（SOGD）可在整个连续区间λ∈[0,1)上实现统一的$O(√{\log T / (1-λ)})$折扣后悔。核心思路是维护多个针对不同λ的OGD实例，并通过名为折扣-正态-预测器（Discounted-Normal-Predictor, DNP）的在线预测算法依次聚合输出。分析表明，即使两个专家在不同折扣因子下运行，DNP仍能有效组合其决策。
原文摘要 · Abstract (English)
Reflecting the greater significance of recent history over the distant past in non-stationary environments, $λ$-discounted regret has been introduced in online convex optimization (OCO) to gracefully forget past data as new information arrives. When the discount factor $λ$ is given, online gradient descent with an appropriate step size achieves an $O(1/\sqrt{1-λ})$ discounted regret. However, the value of $λ$ is often not predetermined in real-world scenarios. This gives rise to a significant open question: is it possible to develop a discounted algorithm that adapts to an unknown discount factor. In this paper, we affirmatively answer this question by providing a novel analysis to demonstrate that smoothed OGD (SOGD) achieves a uniform $O(\sqrt{\log T/1-λ})$ discounted regret, holding for all values of $λ$ across a continuous interval simultaneously. The basic idea is to maintain multiple OGD instances to handle different discount factors, and aggregate their outputs sequentially by an online prediction algorithm named as Discounted-Normal-Predictor (DNP) (Kapralov and Panigrahy,2010). Our analysis reveals that DNP can combine the decisions of two experts, even when they operate on discounted regret with different discount factors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。