On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning
This work provides a principled method for improving FTRL in dynamic settings, offering benefits like refined regret control and optimism without cyclic dependence, but it is incremental as it builds on prior insights about agile iterates.
The paper tackles the problem of Follow the Regularized Leader (FTRL) in Online Convex Optimization (OCO) for dynamic environments, showing that it can achieve known dynamic regret bounds by using optimism with history pruning, which synchronizes the algorithm's state and iterates to avoid arbitrary growth.
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 greedy 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.