仅需简单归约，动态遗憾竟达极小极大最优！
From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences
📖 AI 总结
这篇论文研究非平稳在线学习中的动态遗憾最小化问题，即在线学习器如何与随时间变化的比较器序列竞争。以往针对强凸和指数凹损失取得最优遗憾界的方法通常依赖复杂的分析。作者提出一个简洁框架，将动态遗憾最小化归约为切换遗憾最小化，从而可直接调用已有具备切换遗憾保证的算法来推导动态遗憾界。其核心思路是为任意比较器序列构造一个辅助随机序列，该序列在每一轮无偏、方差可控且切换次数有限，再结合适当的替代损失，将动态遗憾分解为对该随机序列的期望切换遗憾与可控方差之和。理论上，对强凸和指数凹损失，作者得到Õ(T^{1/3}P_T^{2/3})的动态遗憾界，其中T为时间跨度、P_T为比较器序列的路径长度；对一般凸损失，该归约同样恢复O(√(T(1+P_T)))的界。这些结果均与三类损失各自的极小极大最优结果吻合，表明该框架具有广泛的适用性。
🔑 关键词速览
| 动态遗憾 (Dynamic Regret) | 衡量在线学习器与随时间变化的比较器序列之间累积性能差距的指标。 |
| 切换遗憾 (Switching Regret) | 衡量在线学习器与允许有限次切换的比较器序列之间累积性能差距的指标。 |
| 强凸损失 (Strongly Convex Loss) | 具有强凸性质的损失函数，通常能带来更快的收敛速率。 |
| 指数凹损失 (Exp-concave Loss) | 满足指数凹性质的损失函数，常用于在线学习中以获得对数遗憾界。 |
| 路径长度 (Path-length) | 比较器序列中相邻元素之间距离的总和，用于量化序列的时变程度。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅