arXiv：cs.LG（机器学习，全量分类）· Yibo Wang, Wenhao Yang, Sifan Yang, Wei Jiang, Yuanyu Wan, Lijun Zhang·· 17 小时前AI 评分29
从切换遗憾到动态遗憾：一种基于无偏随机序列的简单归约方法
From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences
AI 导读
该论文提出一种简单框架，将动态遗憾最小化归约为切换遗憾最小化，通过对任意比较器序列构造每轮无偏、方差可控且切换次数有限的辅助随机序列，结合替代损失将动态遗憾分解为期望切换遗憾与受控方差之和。
正文
Abstract:In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, attaining optimal bounds for strongly convex and exp-concave losses often involves intricate analysis. In this paper, we present a \textit{simple} framework that reduces dynamic regret minimization to switching regret minimization. As a result, we can derive dynamic regret bounds by using off-the-shelf algorithms with switching regret guarantees. The key idea of our reduction is to construct, for \textit{any} comparator sequence, an auxiliary random sequence that is unbiased at each round, with the controlled variance and a manageable number of switches. Combining this construction with suitable surrogate losses, we can decompose dynamic regret into the expected switching regret against the random sequence and its controlled variance. Theoretically, for strongly convex and exp-concave losses, we establish the $\widetilde{O}(T^{1/3}P_T^{2/3})$ dynamic regret bounds, where $T$ denotes the time horizon and $P_T$ denotes the path-length of the comparator sequence. Moreover, for general convex losses, the same reduction also recovers the $O(\sqrt{T(1+P_T)})$ dynamic regret bound. Notably, all our findings match the minimax optimal results for these three types of losses, highlighting the versatility of our proposed framework.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2609.20968 [cs.LG] |
| (or arXiv:2609.20968v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2609.20968 arXiv-issued DOI via DataCite |
Submission history
From: Yibo Wang [view email]
[v1]
Thu, 17 Sep 2026 18:25:43 UTC (57 KB)
[v2]
Thu, 1 Oct 2026 15:38:18 UTC (58 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org