Research map / Bandits and online learning / Online convex optimization and games
On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows optimistic FTRL can achieve problem-dependent dynamic regret bounds over compact sets by pruning the linearized history (state) via normal-cone subgradients, yielding the OptFPRL algorithm.
Problem
FTRL was thought unsuitable for dynamic regret because its aggregated linearized history grows unboundedly and makes iterates lazy; no optimistic, data-dependent dynamic regret guarantees existed for FTRL over bounded domains.
Approach
Use the normal cone of the compact set to select boundary subgradients that prune the FTRL state whenever the unconstrained iterate leaves the set, keeping the state norm bounded by the regularization; combined with optimistic predictions and recursive (AdaFTRL-style) regularization to get bounds scaling with prediction error and path length.
Key results
- Theorem with P_T-agnostic regularization gives R_T <= (5.8R + P_T/2) sqrt(E_T) + H_T, i.e. O((1+P_T) sqrt(E_T)), vanishing with perfect predictions.
- With prior P_T knowledge, regret O((1+sqrt(P_T)) sqrt(E_T)), matching minimax O(sqrt((1+P_T)T)) even when predictions fail.
- Recursive regularization yields R_T <= (3.7R + P_T) sqrt(E_T) + H_T = O((1+P_T) sqrt(E_T)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Prune the accumulated FTRL state using normal-cone terms | FTRL · OCO dynamic regret | dynamic regret upper bound | Helped |
| Use optimistic predictions so the regret bound depends on prediction error | OptFPRL · OCO dynamic regret, perfect predictions | dynamic regret upper bound: zero | Helped |
| Tune regularization using prior P_T rather than P_T-agnostic regularization | OptFPRL · OCO dynamic regret, known P_T | dynamic regret upper bound: \mathcal{O}\left((1+P_T)\sqrt{E_T}\right) -> \mathcal{O}\left((1+\sqrt{P_T})\sqrt{E_T}\right) | Helped |
| Estimate P_T online instead of providing it in advance | OptFPRL · OCO dynamic regret, unknown but observable P_T | dynamic regret upper bound: A_T; in the worst case, A_T = \mathcal{O}(\sqrt{E_T}(P_T + 1)) | Mixed |
| Set regularization recursively using local regret instead of an upper bound based on prediction error | OptFPRL · OCO dynamic regret | dynamic regret upper bound: (3.7R+P_T)\sqrt{E_T} + H_T | Helped |
Surprising findings
- Standard FTRL with aggregated gradient state can fail to achieve sublinear dynamic regret even at constant path length, but pruning restores it.
Limitations
- Unknown-P_T variant incurs an extra additive term A_T that can reach O(sqrt(E_T)(P_T+1)) in the worst case due to non-monotonicity.
- Analysis restricted to compact domains and Lipschitz convex losses with Euclidean regularizers.
- Purely theoretical; no empirical experiments reported in the text.
Experimental setup
Metrics: dynamic regret bound
Baselines: Optimistic OMD (two-step) Ader-style meta-learning dynamic regret FTRL dynamic regret (Adam analysis)
Builds on: FTRL Optimistic FTRL AdaFTRL Optimistic OMD FTRL Greedy
Closest papers by meaning
- Dynamic Regret in Online Convex Optimization with Indicator Switching Costs (NeurIPS 2026 · similarity 0.92)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.92)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.91)
- Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points (NeurIPS 2026 · similarity 0.89)
- Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously (NeurIPS 2024 · similarity 0.88)
- Online Linear Regression in Dynamic Environments via Discounting (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.