用可混合性提升非平稳在线学习的动态遗憾，尤其适合曲线型损失。
Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability
- 利用可混合性捕捉损失曲率，改进指数权重更新策略。
- 在d维空间下，动态遗憾降至O(d T^{1/3} P_T^{2/3} log T)。
- 分析框架更简洁，无需复杂KKT条件，适用于强曲率损失。
近年来，非平稳在线学习受到广泛关注。尽管已有显著进展，动态遗憾最小化仍主要针对凸函数，对具有更强曲率（如平方损失或逻辑损失）的函数研究不足。本文通过引入可混合性这一概念，有效捕捉损失曲率，提出一种基于固定共享更新的指数权重方法。设维度为d，比较器路径长度为P_T，该方法对可混合损失实现了O(d T^{1/3} P_T^{2/3} log T)的动态遗憾，优于先前最优结果O(d^{10/3} T^{1/3} P_T^{2/3} log T)。更重要的是，该改进源于一个简洁有力的分析框架，避免了现有工作依赖的KKT分析。
原文摘要 · Abstract (English)
Non-stationary online learning has drawn much attention in recent years. Despite considerable progress, dynamic regret minimization has primarily focused on convex functions, leaving the functions with stronger curvature (e.g., squared or logistic loss) underexplored. In this work, we address this gap by showing that the regret can be substantially improved by leveraging the concept of mixability, a property that generalizes exp-concavity to effectively capture loss curvature. Let $d$ denote the dimensionality and $P_T$ the path length of comparators that reflects the environmental non-stationarity. We demonstrate that an exponential-weight method with fixed-share updates achieves an $\mathcal{O}(d T^{1/3} P_T^{2/3} \log T)$ dynamic regret for mixable losses, improving upon the best-known $\mathcal{O}(d^{10/3} T^{1/3} P_T^{2/3} \log T)$ result (Baby and Wang, 2021) in $d$. More importantly, this improvement arises from a simple yet powerful analytical framework that exploits the mixability, which avoids the Karush-Kuhn-Tucker-based analysis required by existing work.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。