# On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning

arXiv: https://arxiv.org/abs/2505.22899 · HTML: https://mlsanity.com/paper/2505.22899/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 35 references that are in the map.
- First posted on arXiv 28 May 2025.

## Builds on (most cited first, 25 of 25)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Adapting to Online Label Shift with Provable Guarantees](https://mlsanity.com/paper/2207.02121/) (2022)
- [Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise](https://mlsanity.com/paper/2402.01567/) (2024)
- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [Online mirror descent and dual averaging: keeping pace in the dynamic case](https://mlsanity.com/paper/2006.02585/) (2020)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [A closer look at temporal variability in dynamic online learning](https://mlsanity.com/paper/2102.07666/) (2021)
- [Discounted Adaptive Online Learning: Towards Better Regularization](https://mlsanity.com/paper/2402.02720/) (2024)
- [Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness](https://mlsanity.com/paper/2305.13946/) (2023)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [An Equivalence Between Static and Dynamic Regret Minimization](https://mlsanity.com/paper/2406.01577/) (2024)
- [Adaptive Composite Online Optimization: Predictions in Static and Dynamic Environments](https://mlsanity.com/paper/2205.00446/) (2022)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Fair Resource Allocation in Virtualized O-RAN Platforms](https://mlsanity.com/paper/2402.11285/) (2024)
- [Optimistic Online Non-stochastic Control via FTRL](https://mlsanity.com/paper/2404.03309/) (2024)

## Built on by (most cited first, 5 of 5)

- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [Partially Lazy Gradient Descent for Smoothed Online Learning](https://mlsanity.com/paper/2601.15984/) (2026)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)
- [SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search](https://mlsanity.com/paper/2606.01325/) (2026)
- [Dynamic Regret in Online Convex Optimization with Indicator Switching Costs](https://mlsanity.com/paper/2609.30556/) (2026)

## Abstract (arXiv)

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.