改进FTRL算法动态后悔率，通过历史剪枝实现更敏捷的更新。
On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning
- 结合未来代价乐观估计与过去代价线性化，实现动态更新。
- 在紧凑集上达到已知动态后悔界，且可控制后悔项。
- 适合关注在线优化中自适应更新的算法研究者。
我们重新审视在线凸优化（OCO）中紧致集上的随时间变化的规则领导者（FTRL）框架，聚焦于动态后悔率的保证。以往研究指出该框架在动态环境中表现不佳，因其迭代更新存在“迟滞”现象。然而，基于FTRL具备产生“敏捷”迭代的洞察，本文表明通过未来代价的乐观组合与对过往代价的精细线性化，可实现动态后悔界的恢复，并允许剪除部分历史信息。这一新分析揭示了：阻碍（乐观）动态后悔性能的并非FTRL的“迟滞”投影风格，而是其状态（线性化历史）与迭代值之间的解耦，导致状态无界增长。通过剪枝可使二者同步。该方法为迟滞与敏捷更新间提供了原则性插值机制，带来多项优势：对后悔项的精细控制、无循环依赖的乐观性，以及类似AdaFTRL的最小递归正则化。更广泛地，该研究澄清了动态优化中算法设计的关键机制。
原文摘要 · Abstract (English)
We revisit the Follow the Regularized Leader (FTRL) framework for Online Convex Optimization (OCO) over compact sets, focusing on achieving dynamic regret guarantees. Prior work has highlighted the framework's limitations in dynamic environments due to its tendency to produce "lazy" iterates. However, building on insights showing FTRL's ability to produce "agile" iterates, we show that it can indeed recover known dynamic regret bounds through optimistic composition of future costs and careful linearization of past costs, which can lead to pruning some of them. This new analysis of FTRL against dynamic comparators yields a principled way to interpolate between lazy and agile updates and offers several benefits, including refined control over regret terms, optimism without cyclic dependence, and the application of minimal recursive regularization akin to AdaFTRL. More broadly, we show that it is not the "lazy" projection style of FTRL that hinders (optimistic) dynamic regret, but the decoupling of the algorithm's state (linearized history) from its iterates, allowing the state to grow arbitrarily. Instead, pruning synchronizes these two when necessary.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。