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

Naram Mhaisen, George Iosifidis · 2025

Read On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning by Naram Mhaisen, George Iosifidis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22899.txt.

Introduction

Naram Mhaisen and George Iosifidis revisit a classic online learning method in this 2025 paper. The method, Follow the Regularized Leader, picks each step by weighing all past costs plus a steadying term. In changing settings it was thought too lazy to track shifting targets well.

The pair show the method can match known bounds for shifting targets after all. The trick blends guesses about future costs with a careful linear summary of past costs, dropping some of them. Pruning keeps the method's memory in step with its choices instead of letting it grow without bound. The view also yields finer control over regret terms and a light recursive variant.

Catalog record

CREATORNaram Mhaisen, George Iosifidis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-22899

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning Naram Mhaisen, George Iosifidis Abstract 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. 1 Introduction This paper addresses the Online Convex Optimization (OCO) problem ( Zinkevich, 2003 ; Shalev-Shwartz, 2012 ; Hazan, 2022 ) , a popular paradigm for sequential decision making under uncertainty. OCO is regarded as a time-slotted game between a learner and a potentially adversarial environment. At slot t , the learner selects an action \bm{x}_{t} from a convex set \mathcal{X} . Then, the environment reveals a cost f_{t}:\!\mathcal{X}\!\subset\!\mathbb{R}^{n}\!\to\!\mathbb{R} , and the learner incurs f_{t}(\bm{x}_{t}) . The objective is finding a set of actions \{\bm{x}_{t}\}_{t=1}^{T} , for some horizon T , that perform well under the functions \{f_{t}(\cdot)\}_{t=1}^{T} , which is non-trivial since \bm{x}_{t} is committed before f_{t}(\cdot) is revealed. Under the most stringent criteria, the learner’s performance is measured by the dynamic regret \mathcal{R}_{T} : \displaystyle\mathcal{R}_{T}\doteq\sum_{t=1}^{T}f_{t}(\bm{x}_{t})-f_{t}(\bm{u}_{t}), (2) where \{\bm{u}_{t}\}_{t=1}^{T}\in\mathcal{X} is any set of comparators with desirable costs that we wish to benchmark against. The dynamic regret is thus simply the performance gap between the learner and the comparator sequence. A key complexity measure associated with the comparators is its path length P_{T} , \displaystyle P_{T}\doteq\sum_{t=1}^{T-1}\|\bm{u}_{t+1}-\bm{u}_{t}\|. (3) The path length quantifies the variation in the comparator sequence, with larger values indicating a more dynamic environment and a more challenging learning setting. 1.1 Background and Motivation Algorithms with a sub-linear regret guarantee have been behind recent state-of-art advances not only in classical computer science problems such as caching ( Mhaisen et al., 2022 ) , portfolio management ( Tsai et al., 2024 ) , and generalized assignment ( Aslan et al., 2024 ) , but also in machine learning problems such as the design of (enhanced) ADAM optimizer ( Ahn et al., 2024 ) , sub-modular optimization ( Si-Salem et al., 2024 ) , and supervised learning with shifting labels ( Bai et al., 2022 ) among others. However, even in the static settings where the comparator is fixed: \bm{u}_{t}=\bm{u},\forall t , the strategy of minimizing witnessed costs at each t admits linear regret, indicating a failure in learning ( Shalev-Shwartz, 2012 , Sec 2.2) . Hence, careful regularization is needed to avoid overfitting past data, which is the fundamental idea behind the two main algorithmic families for OCO: Follow the Regularized Leader (FTRL) and Online Mirror Descent (OMD). It is known that both frameworks achieve an order optimal static regret bound of \mathcal{O}(\sqrt{T}) ( Orabona, 2022 , Sec. 5) . Further, it has been shown that when the regularization is made data-dependent , the regret bounds will indeed be sub-linear and, more importantly, data-dependent. This is a desirable, albeit challenging, objective. Data-dependent bounds are preferable because they are parametrized by the actual problem instance, \{f_{t}(\cdot)\}_{t=1}^{T} , rather than crude universal bounds on this instance. I.e., on the Lipschitz constant L and the horizon T . While this complicates the analysis, it leads to more custom algorithms in which the “easiness” of an instance is reflected in the bound. For example, AdaGrad-style bounds ( Duchi et al., 2011 ) , and follow-ups, achieve static regret of the form \mathcal{O}(\sqrt{G_{T}}) where G_{T}\!=\!\sum_{t=1}^{T}\|\bm{g}_{t}\|^{2} , \bm{g}_{t}\in\partial f_{t}(\bm{x}_{t}) is the sub-gradients norm trajectory. This form of bounds is desirable since they scale with the lengths \|\bm{g}_{t}\| and hold for any value T rather than being dependent on the worst case L value and on a single pre-provided T . Yet, they maintain the order-optimal bound ( \mathcal{O}(\sqrt{T}) ) in all cases. Similarly, ( Chiang et al., 2012 ) achieves \mathcal{O}(\sqrt{V_{T}}) for smooth functions where V_{T}\!\doteq\!\sum_{t=2}^{T}\max_{\bm{x}}\|\nabla f_{t}(\bm{x})-\nabla f_{t-1}(\bm{x})\|^{2} is the gradient variation trajectory, which, again, is never more \mathcal{O}(\sqrt{T}) but tighter for slowly-varying functions. A more general problem-dependent quantity is the accumulated prediction error ( Rakhlin and Sridharan, 2013 ; Mohri and Yang, 2016 ) ; suppose the learner receives a prediction \tilde{f}_{t}(\cdot) for the cost function f_{t}(\cdot) prior to deciding \bm{x}_{t} , with no guarantees on its accuracy, the quantity of interest is: \displaystyle E_{T}\doteq\sum_{t=1}^{T}\epsilon_{t}^{2},\quad\epsilon_{t}\doteq\|\bm{g}_{t}-\bm{\tilde{g}}_{t}\|, (4) where \tilde{\bm{g}}_{t}\in\partial\tilde{f}_{t}(\bm{x}_{t}) . Clearly, we can choose \tilde{f}_{t}(\cdot) to be 0 or f_{t-1}(\cdot) , recovering the dependence on G_{T} and V_{T} 1 1 1 More precisely, for differentiable functions, we recover V^{\prime}_{T}=\sum_{t=1}^{T}\|\nabla{f}_{t}(\bm{x}_{t})-\nabla{f}_{t-1}(\bm{x}_{t-1})\|^{2}\leq V_{T} . , respectively. Algorithms whose regret depends on E_{T} are called optimistic and are crucial for achieving best-of-both-worlds-style guarantees: constant regret in predictable environments and sub-linear in all cases, delivering adaptability without sacrificing robustness. Interestingly, the application of optimistic algorithms extends beyond enabling the use of untrusted predictions in the OCO problem; they have been shown to be key in the more general delayed OCO problem ( Flaspohler et al., 2021 ) , as well as the related OCO with memory problem ( Mhaisen and Iosifidis, 2024 ) . Given their significance, we focus on developing “optimistic” algorithms in this work. That is, algorithms that receive and use predictions of future costs and have regret bounds parametrized by E_{T} . While (optimistic) data dependence is well understood for both OMD and FTRL frameworks under the static regret metric, the story is different when it comes to dynamic regret. For OMD, the current prevalent form of optimistic problem-dependent dynamic regret bounds first appeared in ( Jadbabaie et al., 2015 ) , who used a variant of the Optimistic OMD (OOMD) (two-step variant). This formulation requires that \bm{g}_{t} is defined before calculating \bm{x}_{t} , which is only possible for linear functions (recall \bm{g}_{t}\in\partial f_{t}(\bm{x}_{t}) ). This “cyclic dependency” issue was only addressed recently in ( Scroccaro et al., 2023 ) , who obtained bounds that depend on a quantity similar to E_{T} , D_{T}\doteq\sum_{t=1}^{T}\|\nabla f_{t}(\bm{y}_{t-1})-\nabla\tilde{f}_{t}(\bm{y}_{t-1})\| , where \bm{y}_{t} are points generated by an online algorithm. As for FTRL, the first dynamic regret guarantee has been established by ( Ahn et al., 2024 ) , showing \mathcal{R}_{T}=\mathcal{O}(P^{1/3}T^{2/3}) for bounded domains. While this guarantee is not data-dependent and suboptimal in T , it suffices for the authors’ goal of explaining the behavior of the Adam optimizer. For bounded domains, to our knowledge, no prior work has established dynamic regret guarantees for FTRL, problem-dependent or not, with \mathcal{O}(P^{\beta}_{T}\sqrt{T}) dependence, for any \beta\in[0,1] . This gap raises an intriguing question regarding the performance of FTRL under the dynamic regret metric, particularly given that FTRL

Read the complete text