On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning
Authors: Naram Mhaisen
George Iosifidis
Venue: ICML 2025 poster (2025)
Keywords: Online Convex Optimization
FTRL
Dynamic Regret
Optimism
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We show how FTRL with specific choices of linearization can recover dynamic regret guarantees.

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 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.

On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning
Naram Mhaisen George Iosifidis
Abstract
ft : RR" -R, and the learner incurs fxxz). The objec- tive is finding set of actions f2x for some horizon T, that perform well under the functions {ff(-)){= which is non-trivial since a, committed before fe(-) is revealed. Under the most stringent criteria, the learner's performance is measured by the dynamic regret Ry:
We revisit the Follow the Regularized Leader (FTRL) framework for Online Convex Optimiza- tion (OCO) over compact sets, focusing on achiev- ing dynamic regret guarantees. Prior work has highlighted the framework's 's limitations in dy- namic environments due to its tendency pro- duce "lazy" iterates. However, building in- sights showing FTRL's ability to produce "agile" iterates, we show that it can indeed recover known dynamic regret bounds through optimistic com- position of future costs and careful linearization of past costs, which can lead to pruning some of them. This new analysis of FTRL against dy- namic comparators yields principled way in- terpolate between greedy and agile updates and offers several benefits, including refined control over regret terms, optimism without cyclic depen- dence, and the application of minimal recursive regularization akin to AdaFTRL. More broadly, we show that it the "lazy" projection style of FTRL that hinders (optimistic) dynamic gret, but the decoupling of the algorithm's 's state (linearized history) from its iterates, allowing the state to grow arbitrarily, Instead, pruning synchro- nizes these two when necessary.
T RT Σ f()))) fe(u)),
where {ur]== ) E X' is any set of comparators with desirable costs that we wish to benchmark against. The dynamic re- gret 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 Pr.
Pr
u - well-
(1)
The path length quantifies the variation in the comparator sequence, with larger values indicating more dynamic environment and a more challenging learning setting.
1.1. Background and Motivation
Algorithms with 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 gener- alized assignment (Aslan et al., 2024), but also machine learning problems such as the design of (enhanced) ADAM optimizer (Ahn 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: ue = u, Vt, the strategy of minimizing witnessed costs at each t ad- mits linear regret, indicating a failure in learning (Shalev- Shwartz, 2012, See 2.2). Hence, careful regularization is needed avoid overfitting past data, which is the fundamen- tal 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 O(VT) (Orabona, 2022, Sec. 5). Further, it has been shown that when the reg- ularization made data-dependent, the regret bounds will
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 time- slotted game between a learner and potentially adversarial environment. At slot t, the learner selects an action æ; from convex set X. Then, the environment reveals cost
Faculty of Electrical Engineering, Mathematics and Com- puter Science, TU Delft, Netherlands. Correspondence to: Naram Mhaisen <n.mhaieen @ tudelft.nl>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
indeed be sub-linear and, more importantly, data-dependent. This is desirable, albeit challenging, objective.
appeared in (Jadbabaie et al., 2015), who used vari- ant of the Optimistic OMD (OOMD) (two-step variant). This formulation requires that gr is defined before calcu- lating 2t, which is only possible for linear functions (re- call 9: E (z:() This "cyclic dependency" issue was only addressed recently in (Scroccaro et al., 2023), who obtained bounds that depend on a quantity similar to ET, (y)-))l) where yr are
Pata-dependent bounds are preferable because they are parametrized by the actual problem instance, {f((-))Z rather than crude universal bounds on this instance. Le., on the Lipschitz constant L and the horizon T. While this complicates the analysis, leads more custom algorithms in which the "casiness" of an instance is reflected in the bound. For example, AdaGrad-style bounds (Duchi et al., 201 and follow-ups. achieve static regret of the form ((VTT) where Gr = =i= II2 9: E 0z,( is the sub-gradients norm trajectory. This form of bounds is de- sirable since they scale with the lengths ||gell and hold for any value T rather than being dependent on the worst case L value and on single pre-provided T' Yet, they maintain the order-optimal bound (O( (O()T)) in all cases. Similarly, (Chiang et al., 2012) achieves ((VVT) for smooth func- is the gradient variation trajectory, which, again, is never more (VTT) but tighter for slowly-varying functions.
Dr = Σn=1 V points generated by online algorithm.
As for FTRL, the first dynamic regret guarantee has been established by (Ahn et al., 2024), showing Rf = (PP1/372/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 O (PFVT) VT) dependence, for any 3 E [0, 1]. This gap raises an intriguing question re- garding the performance of FTRL under the dynamic regret metric, particularly given that FTRL can be equivalent to OMD under specific regularization and linearization choices (MeMahan, 2017, Sec. 6), suggesting its potential appli- cability in dynamic environments. However, the extent to which FTRL admits meaningful dynamic regret guarantees remains an open problem.
tions where VT " مو= max [ - V
A more general problem-dependent quantity is the accumu- lated prediction error (Rakhlin & Sridharan, 2013; 3; Mohri & Yang. 2016); suppose the learner receives a prediction fe()) for the cost function fe(-) prior to deciding æ,, with no guarantees on its accuracy, the quantity of interest is:
Conceptually, the versatility of FTRL arises from its richer state representation, where the "state" refers to the vector used to determine the next iterate, T1+1. In OMD, the state of the algorithm merely the current feasible point, xe. In contrast, the state in FTRL is some mapping of all previous cost functions. In the most common case, this mapping is simply the cumulative gradient, 91:t = -E== 9r. This same versatility, which stems from retaining all past costs, introduces a key drawback: retaining all past costs can hinder adaptation when the costs are nonstationary.
Ep
2 G
6, = -gell-
where 9. E (ax)) Clearly, we can choose fe()) to be 0 or fi-1()), recovering the dependence on GT and Vr respectively. Algorithms whose regret depends Er are called optimistic and are crucial for achieving best-of-both- worlds-style guarantees: constant regret in predictable envi- ronments 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 be key in the more general delayed OCO problem (Flaspohler et al., 2021), well as the related OCO with memory problem (Mhaisen & Iosifidis, 2024). Given their significance, we focus on developing "opti- mistic" algorithms in this work. That is, algorithms that receive and use predictions of future costs and have regret bounds parametrized by Er.
Specifically, it has been demonstrated that FTRL iterates that use such mapping fail to achieve sublinear dynamic regret even for constant path lengths (Jacobsen & Cutkosky, 2022, Thm. 2). In essence, the aggregation of past costs ob- scures the switching patterns in the data (i.e., in {fr ()) which are crucial for the iterates to adapt appropriately, par- ticularly when competing with moving comparators. Since most FTRL variants in the literature aggregate past gra- dients, FTRL is often considered unsuitable for dynamic environments (Chen et al., 2024). However, these findings do not dismiss the potential of all FTRL variants. On the contrary, they give insight into how to design variants that adapt to changing comparators, a key motivation behind the pruning mechanism we analyze here.
While (optimistic) data dependence is well understood for both OMD and FTRL frameworks under the static re- gret metric, the story is different when it comes to dy- namic regret. For OMD, the current prevalent form of optimistic problem-dependent dynamic regret bounds first
This paper seeks to address the ambiguity regarding FTRL's performance under dynamic regret. Clarifying this issue is not only intellectually compelling but also important for
More precisely, for diffcrentiable functions, we recover Vi= Σ [f.( - V (1l- < Vr.
2

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
establishing more refined problem-dependent bounds, as we demonstrate in the sequel. It will also help explain the notable performance gap between lazy (i.e., typically FTRL) and greedy (i.e., typically OMD) methods in dynamic set- tings. Furthermore, we introduce a new set of FTRI-native analysis tools, expanding its applicability in dynamic envi- ronments and paving the way for dynamic regret guarantees in other OCO settings (e.g., delayed feedback or memory constraints), where FTRL is often the framework of choice.
!ghalll
Vrr( mid)
Vr(-giv))
AlPael
Ft+11 Vrä Pi.d
1.2. Methodology and Contributions
Figure 1: Effect of dual state size on iterates agility. We consider two slots < t', where gradients switch direction: g- 1==(-1,00 0) for T S t, and g. = (1, 0) for >>t. Top: Stan- dard FTRL accumulates large state gı., and the update via Vr*(g becomes insensitive to the change in direc- tion; both I and gı.e' map to the same iterate. Bottom: A well-maintained state P1:t remains bounded, and hence its mapping stays close to X' enabling By to start aligning quickly with the new better iterate direction 0).
As noted earlier, certain forms of FTRL are equivalent to OMD, suggesting that dynamic regret guarantees should hold in these cases. The equivalence arises when the update minimizes the regularized linearized history, which is the starting point of this paper. Specifically, let rr(-) be data- dependent strongly convex regularizer that evolves with t, potentially depending on past costs and actions. Then, the standard linearized FTRL update is
Tt+ 1++1 = argmin (gia,
(gim, x) + (z). .EX'
(3)
The simple yet key observation is that with the extra flexibil- ity provided by g the state of the algorithm need not be the simple aggregation gıst- Rather, some of the summands can be attenuated or pruned by carefully selecting gf from the cone (xx()))) This is possible since Nxx (2r) contains all (scaled) negative subgradients of the expression in (4) when De lies on the boundary of X 2; bd( (from the opti- mality conditions for constrained problems, see e.g.. (Beck, 2017, Thm. 3.67)). In words, when an iterate leaves the fea- sible set and is thus projected back, we can choose to prune the state that led to this situation and replace it with an alter- native state pi:t. that induces the same iterate but is smaller in norm. This construction is crucial, as we later show that the norm of the state is the key bottleneck for FTRL when competing with time-varying comparators. Fig. illustrates how different state constructions behave upon a switch in cost direction; note that the FTRL update, with a fixed r(-) can be expressed as the projection of (r*(- where (+)) is the conjugate r(-) (see def. in Appendix A.4).
X' = RR" and rx(x)) is proximal', this update is equivalent to the OMD update which uses (-: as the mirror map. This is proven in (MeMahan, 2017, Thm. 11), even for the more general case of composite costs.
Here, we consider the optimistic version of this update. That is, we append the prediction (x+ to the sum in (3). This will later allow us to have proplem-dependent bounds that are modulated by ET. Secondly, we focus on compact sets X' C F". A primary design choice in our method is to incorporate the constraint as additional indicator function to each prediction. This is equivalent to modeling each cost function as a composite function: fe(z) + [x).. The indicator part is then always assumed to be "predicted" perfectly. Nonetheless, the linearization of the past composite costs is now different. Namely, our proposed update becomes:
Our main contribution is formalizing this intuition pro- vide dynamic regret analysis of Optimistic FTRL, lead- ing to a new variant, Optimistic Follow the Pruned Leader (OptFPRL). This variant achieves zero dynamic regret when predictions are perfect. This is because the quality of predictions controls all regret terms, including Pr. To our knowledge, this is the first variant to explicitly have such full dependence on prediction accuracy without oracle tuning. In the general case, OptFPRL also maintains the minimax optimal rate of ((V(1 + P+)T) when Pr is known. We also present version that does not require prior knowledge of Pr, but assumes observability, while still maintaining dependence on prediction errors.
Ft+11 = argmin
(Pr.: Pr.:: x) + (ax(
+ ftt((x) + Ix(x), (4)
with the state vector Pitt calculated as the aggregation of
Pt- = g: + g(= g: E (xt)), gf E 01x(xx)) = (xx
where Nxx(xr) the normal cone at æ, and is defined as
Nx = وg (g.v - x) < 0, Vy E X}. AA proximal regularizer (.)) is minimized at x..
Next, since Opt.PRL follows an FTRL-style analysis, it
3

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
well-suited to incremental regularization in the manner of AdaFTRL (Orabona & Pál, 2018). In this scheme, we set the regularization recursively, incrementing it by, roughly, the regret by time t had we followed It. VT 1 t (local regret). This is different from the more common approach, which sets this regularization as an upper-bound on this local regret. While the two are nearly equivalent the worst case, the former allows for more refined bounds by applying only the minimal necessary regularization at each slot. Unlike prior optimistic dynamic regret algorithms, this style of regularization offers more granular bound.
gradient queries (Zhao al., 2024). Overall, knowing Pr in advance, or assuming it is observable online, allows us to tune the regularization (or learning rate for OMD) with this knowledge, getting the better dependence /Pr. Without such assumptions, we can use the meta-learning framework, which learns online the best such regularizatioon/larinn rate under smoothness assumptions.
Setting aside the order of dependence on Pr for a moment, we examine the quantity Er. The aforementioned studies suffer the shortcoming hinted at in the introduction: to make ET small, we require knowledge of V f((xx) at the start of time slot t, which is generally not feasible* even if access to V f((-) was provided (i.e., perfect prediction). This is because ae remains unknown at the start of - is the very point being determined. While the bounds are still optimistic, they are not informative for the predictor design. In the literature, this "cyclic" issue was only identified in (Scroccaro et al., 2023, Sec. 1.B). Thus, the authors in- troduce another related quantity Dr, defined earlier, and obtain O + Pr) + )Dr)).+ 4 In the FTRL variants we propose, we do not have the cyclic issue because we do not require linearizing the predictions fc(-).
In summary, we investigate FTRL's dynamic regret over compact sets, and identify the unbounded growth of the state as the main bottleneck. By leveraging a simple and general mechanism, pruning past gradients, we gain a new degree of freedom that enables improved optimistic bounds.
2. Related Work
Optimism and (dynamie) regret. The pursuit of data dependence has been a central theme in online learning research since the introduction of AdaGrad (Duchi et al., 2011; McMahan & Streeter, 2010). This has eventually led to the development of Optimistic FTRL (e.g., (Mohri & Yang, 2016)). For comprehensive survey of data- dependent online learning, we refer readers to (Joulani et al., 2020). However, these studies focus on static regret. Al- though the dynamic regret metric has been part of the OCO framework since its introduction, the first data detandep dynamic regret bound only appeared in (Jadbabaie et al., 2015). The authors established general bound, from which the result O(v ((7(P; + E) + 1) can be derived, where Pj is specific to the sequence of minimizers comparators {u, = argming ft ). but in fact the bounds hold for any sequence whose path is observable online. This is done via a specialized doubling trick for mon-monotone quantities. By removing the assumption of observable path lengths (i.c., considering all sequences simultaneouslyy) dynamic regret bounds typically lose the sublinear dependence on Pr. For instance, in (Jadbabaie et al., 2015), the bound becomes O((P+1))VET +I).
The aforementioned studies based on OMD, particularly on the "two-steps" variant of (Chiang et al., 2012), where the learner selects two points in each iteration, an intermediate one and the actual action. This distinction from our work is not merely technical. For instance, in the related "OCO with delay" setting, prior work has established guarantees for Optimistic FTRL and the one-step version of Optimistic OMD proposed in (Joulani et al., 2020, See. 7.2). However, similar guarantees are not yet known for the two-step variant of OMD (Flaspohler et al., 2021), and it remains unclear whether the same analysis can be extended to them.
variant
Additionally, focusing again on optimism, a common limita- tion in the aforementioned studies is that the Pr quantity in the bounds is unaffected by the predictions. That is, the Pr term may appear independently of any controllable quan- tity such as Er, leading to bounds of O(Pr) even under perfect predictions (or zero gradient variation). While this may partly reflect limitations in the existing analyses rather than the algorithms themselves, the current bounds do not fully capture the interaction between prediction quality and path length. In contrast, OptFPRL analysis reveals that Pr. or more precisely, each || || uell. is multiplied by the prediction error (e.g., <, or / F.). Thus, the effect of Pr can be attenuated when predictions are accurate.
To address this, (Zhang et al., 2018) proposed a meta- learning framework that achieves ( Pr)) for any sequence, which is shown to be minimax optimal. This framework was made data-dependemt in (Zhao et al., 2020), who obtained O( (VV(V + Pr + 1)(1= + Pr) bound, among others. In this framework, multiple sub-learners are em- ployed, each implementing Online Gradient Descent (OGD) with a different (doubling) learning rate, tuned for various ranges of Pr. These sub-learners are then "tracked" by a variant of the Hedge meta-algorithm. This two-layer ap- proach was later unified within the framework of Optimistic OMD and made more efficient in terms of the number of
Unless all functions are originally linear. Note that lineariza- tion does not solve this issue, as it is performed after the learner has committed to its action.
"The authors also derive bounds based on "temporal variation", but we do not consider this quantity here.
'Or / /rr, assuming a known budget or an observable sequence with doubling trick.
4

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
OMD, FTRL, and (linearized) history. The interplay be- tween OMD and FTRL has received increasing attention in recent years. (Fang et al., 2022) studied modified ver- sion of OMD under the static regret metric and showed its equivalence to Dual Averaging, a time-adaptive instance of FTRL, up to some terms in the normal cone. In this paper, we show that it is precisely these normal cone terms that become critical to achieving dynamic regret guarantees. For dynamic regret, (Jacobsen & Cutkosky, 2022) provides comprehensive study via "centered" OMD, which incorpo- rates FTRL-Ilike centering properties. Their focus is primar-
Algorithm 1 Optimistic Follow the Pruned Leader (OptFPRL)
Input: Compact set X, strategy for selecting o,, Vt. Output: {
1: set 21 arg min, f1(x)) + Ix(x)
2: for 1 = 1,2,.... do
3: Use action x
4: *(fe(-) is revealed)*
5: Incur cost f( and compute 9r E (2(())))
6: Compute ğ. E (z)) and the error et llge gr(
7: Calculate the parameter or using Et.
8:
Set g. according to (5).
ily on unbounded domains, where such centering is essential.
9:
Compute the (pruned) vector p. - Dr + gi-
While their work integrates FTRL features into OMD, we take the opposite approach: extending native FTRL results to dynamic settings. This approach reveals failure modes of FTRL in non-stationary environments and offers princi- pled solutions. Specifically, we investigate how modulating FTRL's state, in bounded domains, leads to regret bounds that are fully modulated by prediction accuracy.
10:
Receive prediction f.+1()).
11: Compute x;++1 by solving (4) without Lx(+).
12: Set x++1 = [I(=
13:
end for
of slots without correlation. Lastly, an interesting reduction from dynamic to static settings is explored in (Jacobsen & Orabona, 2024), which revealed fundamental tradeoff between gradient variability and the comparator sequence's ss complexity measures (e.g., the path length considered here).
In fact, our update is mostly related to the following form J++1 argmin + x)) x) + r(x) + [x(x).
gi E (1+41))))
which appears in (McMahan, 2017) under the name "FTRL Greedy", and was studied under the static regret metrie, Be- yond explicitly modeling the -oaddredient selection from the cone, which allows controlling when and what to prune, we extend this formulation by incorporating: (i) function predictions, (fi) reddiction-adaptive regularization, and (iii) recursive regularization inspired by AdaFTRL. These mod- ifications require different analysis tools, especially under the dynamic regret metric.
3. OptFPRL
In this section, we present the proposed algorithm and char- acterize its dynamic regret. The routine of OptFPRL. is described in Alg. 1. It takes input the compact convex set X, along with a strategy for determining the regulariza- tion parameters og based on information available up to and including slot f.
The initial action is based on the first prediction. Then, upon executing each 2, (line 3), the true cost f(()) revealed and the subgradient g: is computable (line 5). In line 6, we evaluate the prediction error é,, which is used in line 7 to update the regularization parameter o, of the regularizer r.()) according to some pre-determined strategy.
FTRL variants that reduce dependence on history have re- cently been proposed by (Zhang et al., 2024; Ahn et al., 2024) using geometric discounting of all past costs, which is specifically designed for the metric of "discounted" re- gret and its applications. Interestingly, however, Ahn et al. (2024) also observes that such manipulation of FTRL's 's state can endow it with certain (not necessarily optimal) dynamic regret guarantees. Though their method differs, the core in- sight aligns with ours: limiting FTRL's memory is essential for adapting to non-stationarity.
We use scaled Euclidean regularizers of the form
(x(x)) = 0z ||0|| Vt 2 1. 2
The regularizers are set such that rı is 1-strongly convex w.r.t. the scaled Euclidean norm || - lle = Vor.al whose dual norm is || lle.- = 1/voTill |I I|. hence we refer to o, also as the "strong convexity" parameters.
We also note the existence of other approaches for model- ing "optimism" in OCO, other than seeking Ex dependence, such as the Stochastically Extended Adversary (SEA) model (Sachs al., 2022) that was studied in (Chen et al., 2024) for OMD with dynamic comparators. In addition, there exists the "correlated hints" interpretation of optimism (Bhaskara & Munagala, 2023), where the prediction quality is mea- sured by their correlation with the actual cost. This later line of work assumes strongly convex domains and obtains a O(11 + Pr) log" (T)/B) bound, where B is the number
Next, we select of according to the following: for t 1, set of - if c1 0, and gf = 0 otherwise. For all t > 2:
de -- (Pa--1+ + g. + (1)- if & X
(5)
otherwise,
where 2tt is the unconstrained iterate obtained by solving (4) in RD (i.e., without the indicator function).
5

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
To see why we can always set of such, note that when at & X, then at bd(X') (the projection of a point out- side compact convex set lies on the boundary). Hence, (xx) contains vectors other than O. In particular, it con- tains - -P + G. + 01st-1aa) and in fact all positive multiples of this vector. This follows directly from the opti- mality condition for the constrained iterate in (4), (see, e.g.. (Beck, 2017, Thm. 3.67)), and the definition of the normal cone. For the second case, 0 is always valid subgradient of the indicator function since, in this case, xt 2, X.
Theorem 3.1. Under Settings Alg. I run with the regu- larization strategy in (6) produces points (xx (ma)?=, such that, for any T, the dynamic regret RT satisfies:
Rx S (5.8R + (1/2) HT
= (1(
Remarks. We observe from (7) that all terms in the regret bound are modulated by the prediction errors. When the predictions are perfect, the bound reduces to zero (regardless of Pr), and gracefully degrades as prediction errors grow. Note that by Cauchy-Schwarz and the boundness of X, the hybrid term can be bounded as Hr S V2RVFT Pr. Therefore, the overall bound is never worse than O((1 + (r),E)), matching known OMD results when Py is not accounted for, and tighter when predictions are accurate. In the static comparator case (Pr- = 0), the bound recovers the standard O(y /Er) result.
Intuitively, this choice of linearization ensures an alternative state Pi:r (instead of 91.z). The former shall stop growing in norm compared to the latter beyond a certain t, since the action will hit the boundary of X, starting the pruning thereafter. This will be formalized in the analysis, where we show that ||PLall cannot grow faster than the regularization, which is added by optimistically (i.e., x VFy). This is not true in general for an arbitrary choice of linearization, particularly for the default choice of using only gt-
We note that of need not be non-zere zen- at every time slot where æ:! & X. Instead, pruning of the accumulated state can be delayed for fixed number of steps k; resulting in hybrid state of the form P1:k- + 9k:t This is discussed further in Appendix A.4.
3. 3.1.2. REGULARIZATION WITH PRIOR Pr KNOWLEDGE
In many cases, Pr can be provided to the algorithm a priori as a measure of the comparator's complexity (c.g., (Si-Salem et al., 2024; Yang et al., 2016; Besbes et al., 2015)). That is, we wish to compete against any sequence whose path length is at most the provided value of Pr. With this given target, we can adjust the regularization account for the expected nonstationarity and obtain better bounds, outlined next:
In lines 10, 11, a prediction for the next cost is received, and the next unconstrained iterate is updated. Lastly, a feasible point is then recovered via a Euclidean projection into X.
Next, we characterize the dynamic regret of OptFPRL un- der different regularization strategies.
P P 2R Pr, 01 = =061,
2/22P42
(8)
o, = (oo(VVE (VE,- V
3.1. Dynamic Regret of OptFPRL
Vt 22
In this section, we explore different strategies for setting the regularization parameters ot, and analyze the resulting dynamic regret bounds. We begin by outlining the general setting shared across all regularization strategies.
Theorem 3.2. Under Settings Alg. 1 run with the regu- larization strategy in (8) produces points (x,) ) such that, for any T, the dynamic regret Rr satisfies:
Settings 1. Let X' C Rd be a compact, convex set such that ||>:|| || < R for all æ E X. Let (.(()).()))) be any sequence of L-Lipschitz convex functions. Define the path length Pr as in (1), the cumulative prediction error Fy as in (2), and the hybrid term HT = -E= cell cellue+1 urll
R
RPT 2
RT - 42
V HHT
8
= o (1+ Pri
Remarks. This regularization strategy preserves the full modulation by prediction errors while also matching the minimax-optimal bound Rr = 2 (((((1 (I+ + Pr)T) (Zhang et al., 2018, Thm. 2) even when all predictions fail. This type of bound is new for FTRL-style algorithms. Further- more, in its full dependency on Er (i.e., without Pa or constant terms that are independent of Er), it represents a refinement even compared to OMD. More broadly, access to a prior bound on Py enables tailoring the regularization to the expected nonstationarity, allowing us to safeguard the minimax rate while still adapting to prediction accuracy.
3.1.1. PG-ASSIC REGULARIZATION
The first regularization strategy we consider is the standard optimistic one, which sets o, such that dia & / VEr:
a
σ1 = =661,
4R'
(6)
VE
F.
-
Er
E1-1)
Vt 2
'Technically, the projection is w.r.t. scaled Fuclidean, the result is the same.
|| 1- ||e- Since ||.
is
6

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
3.1.3. REGULARIZATION WITH UNKNOWN Pr
3.1.4. RECURSIVE REGULARIZATION
If Pr is unknown but observable, it can be estimated online alongside E,. However, since /Ee/P, is no longer nec- essarily monotonic, we should safeguard against negative regularization coefficients. First, define the augmented seen path length at as:
In this subsection, we employ the regularization strategy of AdaFTRL (Orabona & Pál, 2018), which sets the strong convexity parameters recursively, ensuring the minimal re- quired regularization. Namely, we do not set d such that oer X vE, as in the strategies discussed earlier, and prior works on optimistic dynamic regret. Instead, we set or & 6, - ho::-1 (x++ + (pr, 2t) ming (ho:t-1(2) (2) + x)), where h-(-) is the regularized loss: h2(+) = (pr. +) + (-)). This choice of ar is such that 01 X c S VEg.
P = 2R P. = 2R + Σ 71 u,
We adopt a regularization strategy that attempts to track v ET /Pr by its online estimate /E,/P, while using max(:,) operator to ensure non-negative regularization.
In other words, we increase the strong convexity exactly in proportion to the (regularized) cumulative loss observed at (denoted as 6,), rather than an upper bound on that loss. Since the added strong convexity essentially determines the regret bound, this leads to tighter bounds overall that are no worse than the ones derived earlier. Namely, we use the following regularization strategy:
σ61
2V2R'
01
VPI
(9)
E 0.V P.
E1-1
ot max
0.
V
Pt-1
Vt 2 2.
Theorem 3.3. Under Settings 1, Alg. run with the regu- larization strategy in (9) produces points {at Yu such that, for any T the dynamic regret RT satisfies:
1 a 8R
a, = ade; 51 = (g1, min min(g .)) #Ed
8, (1)e) + (Pt: zi)
(10)
min (hao-1(2) + (pt.))))) #EX
Vt 2 2.
R4 S R.5V Pj + HT + V R2/2 Ar
=0 (1+
PT)
ET + AT)
where
Theorem 3.4. Under Settings I, Alg. 1 rrun with the reg- ularization strategy in (10) produces points {ar)i=1 such that, for any T, the dynamic regret Rr satisfies:
T
Er-1 Pr
Fr
Ar
Σ
|
uull
Pr
1=1 +E|(+
{ (
E-
E P
11t
St
|
P/-1
0
Rr S 1.1 1118
Σ 4R
S1sel alllllu1111111 -uell 0l 11T
Remarks. Note that this bound resembles that of Theo- rem 3.2, except for the additional term Ar, which arises due to the potential monooonntyy of the estimated quan- tity / /E/P. If this sequence were monotonic and non- decreasing, Ar would vanish since [t]+ would be empty. This case allows us to recover the bound of Theorem 3.2 without requiring prior knowledge of Pr- In contrast, in the worst-case scenario, where the sequence alternates di- rection at every round, we obtain A7 = ((VET(PP + 1)) (see Appendix 1.3. leading to the looser bound in Theo- rem 3. A comparable correction term to Ar also appears in the optimistic OMD framework (Scroccaro et al., 2023, Remark 2.19), and likewise depends on monotonicity, reach- ing Pr the worst case. The above-mentioned bound is, however, more interpretable.
S <33.7R+ Pr) Pr) Er
Hr O
Remarks. Since the 6, terms are often smaller than their upper bound, this minimal regularization approach is par- ticularly advantageous in dynamic environments, where regularization terms sum is nested within the primary sum over [T]. While this tuning strategy has been employed pre- viously in static settings for optimistic learning (Flaspohler et al., 2021), it has not yet been leveraged for optimism in dynamic settings". Nonetheless, the recursive nature of this regularization adds a technical challenge since the ac- cumulated strong convexity does not have a closed-form expression in terms of / EE, Fortunately, this recursion is still shown to be bounded by ((VE,) via tools developed in the AdaFTRL framework.
A workaround to this monotonicity issue is a doubling- trick variant (Jadbabaic et al., 2015), which, however, intro- duces a slight -obblem-inddeeddenne through a multiplica- tive (log T) factor, and an additive (log T /Pr) factor that persists even under perfect predictions.
"We note, however, the related coppora-variation based dy- namic regret bound in Implicit OMD (Campolongo & Orabona, 2021), where the structure of "function changes", rather than "pre- diction errors", is exploited.
7

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
4. Tools for FTRL's Dynamic Regret Analysis
(I) is result of generalization of a common tool in OCO which bounds the difference in the value of strongly con- vex function (ho,)(-) when evaluated at a "partial"* mini- mizer (æt) versus the global minimizer (say. y, and hence Ft+1 also), which we state below.
In this section, we present the primary analytical tools used to derive the regret bounds of the previous section. These results extend traditional FTRL analyses incorporate both optimism and dynamic comparators. First, we bound the regret via linearization:
Lemma 4.2. Let each function ho:e()) be 1-strongly convex w.r.t. a norm || -le defined as in Lemma 4.1. Let at argming 10:)-1(2) + f((z). Then, we have the inequality
T
T E(pr, (pr, ut),
RT= = sa(() - Si(()) S
1 2 11. 9e 1.
1=1
t=1
hn,( - ( - -r,(
where Je(()) fe(x)) + Lx(x)). The inequality follows directly from the convexity of je(+). noting that Pt E (z)) by definition of p: (recall Pt- = gi + g with gi af((z)). dIx(xx))..
The second term of the min is in fact a crude regularization- independent bound on the per-slot loss of æ, compared to the omniscient 21+1- We detail both bounds in Appendix B.
Our analysis begins with generalization of the main FTRL lemma (McMahan, 2017, Lem. 5).
(II) follows directly from the first-order inequality for con- vex functions applied to ha.)(). Note that is exactly the |pirll term that explains the potential failure of FTRL in dynamic environments, even with constant path length. Specifically, trivial bound on this norm is linear in t and hence is super-linear in I' even with one switch in the com- parators. This is precisely the "vulnerability" that is ex- ploited in the impossibility result in (Jacobsen & Cutkosky, 2022, Thm. 2). Next, we show how pruning can tie this |P || term to the regularization parameters Tir (which we control), thus ensuring its sub- lub-linearity.
Lemma 4.1. (Strong Dynamic Optimistic FTRL). Let (f.(), u, be an arbitrary set of functions, pre-
dicted functions, and comparators within X, respectively. Let (-) be non-negative regularization functions
funcciooo such that
D++1 = argmin ha: (x) + f241
is well-defined, where ho(x)) [x(x)), and Vt 2 1: x)) + (pr,)) (x)), Pt E (a:()
he(x:) =
Lemma 4.3. (Optimistically Bounded State) Let (p:)T= be sequence of vectors such that each p. = gi + gi where g: E 0f((z.). and gt E 0Ix(x;) is chosen according to the construction in (5). That is, Pt corresponds to the linearization of the composite function fe(-)+ + (+()) around
Then, the algorithm that selects the actions I++1, Vt achieves the following dynamic regret bound:
T
RT 1
ho.t (xx)) (2 ree (2x,)
Bt. Then, for any t, the following holds:
| S Ro + Cc.
hoxe hox((uet1) - (use + re(u))
Proof. First, we begin by showing that
(
For any t, x E X = ||Piall S 50a-1R c. (11)
The regret is thus decomposed into three main parts. Part (I) measures the penalty incurred due to not knowing 9: when deciding zg. The second part (II) measures the penalty incurred due to the non-stationarity of the environment (change of comparators). The last part, re( (,)) is a user- influenced quantity that reflects the amount of regularization introduced and will be traded off against the other terms in the bound that benefit from more regularization.
Since a:e E X, we know that x; = [xx]')) = xt (The projection of a point within the set is itself), and hence x, is a minimizer of the unconstrained update rule too:
xF = argmin (1 x) + +r (a) + f(()) (12) =ER=
From the first-order optimality condition for unconstrained problems (c.g., (Beck, 2017, Thm. 3.63)), we know that 0 is an element of the subdifferential of (12) at zt. Thus, ag. (x.) such that
Next, we describe the upper bounds:
1
(I) < min
2 gg g. 90 2R
0 = Pia-1 + 01t-11 + gr
(II) < (1|P + RO |1u+11 - well
= Pia-1 10 gt.
(13)
ssee, e.g., (Shalev-Shwartz, 2012, Sec. 2.4), for more details on linearization.
Recall that o; does not minimize hort, but a related function.
8

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
and we have that the norm of the state Pia satisfies
4 4V Er + R VEr
Pi:t- 1 + P:ll
(b)
+ 2
Es 11l11411 u.ll + Hr
|p:r11 + gell
01:t-11: 18t
9. + gell
1
10 || + |19 Dell
5.8R ET + VEr PT Pr HT 2
(c)
01 | || + Et S 01:-1 R +c,
where (a) follows from the boundedness of X, the state bound in Lemma 4.3, and the fact that di:t-1 S 01: the equality follows from the definition of || l|+, and the telescoping structure of 01:; (b) follows from applying Lemma D.3 to the Σ. min(,;)) term, which bounds the sum of the non-increasing quantities, and substituting the expression for σ; (c) uses that VE, is non-decreasing.
where (a) holds because of 0 (from (5) & at x (b)
from (13), and (c) from the set size.
Next, we show that when at & X' the state is forced via pruning to be bounded:
For any 1, att $ X' = |paal 01.--R ex- (14)
When x $ X. the pruning condition is activated, which ensures that
Overall, after using the results developed in Sec. 4, ob- taining the exact results of the theorems mainly hinges on available tools from the OCO literature on bounding the sum of non-increasing functions.
P
P1.t = P1.-- + gt PP1--1
gt -
9: g: 01
g!
Proof sketch of the other theorems. The proofs of the other theorems follow similar main steps, and are detailed in the Appendix. When the a parameter is normalized by v /Pr, it can seen from (16) that the Pr term will also be divided by the same, recovering the result of Theorem 3.2.
Thus, |P::e||
= [ 9.- 01s-1 xrl
S 9g: - gel + 01:-11 x
S 4 + 0 R.
The lemma statement follows by (11) and (14).
For Theorem 3.3, write the sum σ1:1 in (15) as the non- monotone / /E//p; /Er-1/P(_, provided that we add the corrective term Ar defined earlier. The former tracks the de- sired quantity / /Er/pz, which is what is required (and was used in Theorem 3.2) to recover the v EE Pr dependence. The corrective sum Ar handled independently.
4.1. Regret Bound Derivation
We show the proof of Theorem 3.1 since it illustrates how the presented tools come together to obtain the results. It also provides a sufficient basis for sketching the proofs of the remaining theorems.
Lastly, for Theorem 3.4, we start again from Lemma 4.1, but instead of using the upper bound of the term (I), use the 6, terms. This results in a recursion whose solution is fortunately available among AdaFTRL lemmas.
Proof of Theorem 3.1. We begin from the main lemma, Lemma 4.1, with the bounds on (I) and (II) terms:
T
min (5l0r 2.. + re((us)
5. Conclusion
Rr &
This paper introduced an optimistic FTRL variant with new data-dependent dynamic regret guarantees, extending classi- cal FTRL results and advancing our understanding of this foundational framework in non-stationary environments. These bounds are explicitly tied to the accuracy of predic- tions, offering refined performance guarantees in dynamic settings. The gist of our proposal lies in a simple pruning rule that modulates the memory (or state) of FTRL based on the quality of the obtained decisions, preventing the ac- cumulation of redundant (negative) gradients that align with iterates on the boundary of the decision set. This technique can be extended to more flexible pruning strategies that control pruning magnitude or introduce additional pruning (16) conditions, enabling a spectrum of algorithms ranging from fully "lazy" to fully "agile" iterates.
(RRoi + +I[p)=el) ||uc]] will)
(15)
min 2 (91991 g..li-1..: 2Rc, +
11
R2
((2 + +G) 11141-1uu
T
2 2Rer/
R22
min
+ Lo Frr
2 Ex1
(2Ro E, + +0) |luet1- -uell

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
Acknowledgements
Duchi, j., Hazan, E., and Singer, Y. Adaptive subgradient
methods for online learning and stochastic optimization. JMLR, 12(11)2121-2219, 2011.
This work was supported by the Dutch National Growth Fund project "Future Network Services", and by the European Commission through Grants No. 101139270 "ORIGAMI" and No. 101192462 "FLECON-6G".
Fang, H., Harvey, J., Portella, V. S., and Friedlander, M. Online mirror descent and dual averaging: keeping pace in the dynamic case. JMLR, 23 1--3, 2022.
Impact Statement
Flaspohler, G. E., Orabona, F., Cohen, J., Mouatadid, S., Oprescu, M., Orenstein, P., and Mackey, L. Online learn- ing with optimism and delay, In Proc. of ICML, 2021.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Hazan, E. Introduction Online Convex Optimization. MIT Press, 2022.
References
Jacobsen, A. and Cutkosky, A. Parameter-free mirror de- scent. In Proc. of COLT, 2022.
Ahn, K., Zhang, Z., Kook, Y., and Dai, Y. Understanding adam optimizer via online learning of updates: Adam is ftrl in disguise. In Proc. of ICML, 2024.
Jacobsen, A. and Orabona, F, An equivalence between static and dynamic regret minimization. In Proc. of NeurlPS, 2024.
Aslan, F., Iosifidis, G., Romero J. A., Garcia- Saavedra, A., and Costa-Perez, X. Fair resource allo- cation in virtualized o-ran platforms. Proc. ACM Meas. Anal. Comput. Syst., 8(1), 2024.
Jadbabaie, A., Rakhlin, A., Shahrampour, S., and Sridha- ran, K. Online optimization: Competing with dynamic comparators. In Proc. of AISTATS, 2015.
Joulani, P., György, A., and Szepesvári, C. A Modular Analysis of Adaptive (non-)Convex Optimization: Op- timism, Composite objectives, Variance Reduction, and Variational Bounds. Theor. Comput. Sci., 808: 108:188 2020.
Auer, P., Cesa-Bianchi, N., and Gentile, C. Adaptive and Self-Confident On-Line Learning Algorithms. Journal of Computer and System Sciences, 64(1):48-75, 2002.
Bai, Y., Zhang, Y.-J,, Zhao, P., Sugiyama, M., and Zhou, Z.- H. Adapting to online label shift with provable guarantees. In Proc. of NewrlPS, 2022.
McMahan, H. B. A Survey of Algorithms and Analysis for Adaptive Online Learning. J. Mach. Learn. Res., 18(1): 3117-3166, 2017.
Beck, A. First Order Methods in Optimization. SIAM- Society for Industrial and Applied Mathematics, 2017.
McMahan, H. B. and Streeter, M. Adaptive bound optimiza- tion for online convex optimization. In Proc. of COLT, 2010.
Besbes, O., Gur, Y., and Zeevi, A. Non-stationary stochastic optimization. Operations research, 1224-14227 2015.
Mhaisen, N. Opt - FPRL, 2025. URL WRLhttps://github. OPtFFRRL
Bhaskara, A. and Munagala, K. Competing against adap- tive strategies in online learning via hints. In Proc. of AISTATS, 2023.
Mhaisen, N. and Iosifidis, G. Optimistic online non- stochastic control via ftrl. In Proc. of IEEE CDC, 2024.
Mhaisen, N., Sinha, A., Paschos, G., and Iosifidis, G. Op-
Campolongo, N. and Orabona, F. A closer look at temporal variability in dynamic online learning, arXiv:2102.07666, 2021.
timistic no-regret algorithms for discrete caching. Proc. ACM Meas. Anal. Comput. Syst. 6(3):1-28, 2022.
Mohri, M. and Yang, S. Accelerating Online Convex Opti- mization via Adaptive Prediction. In Proc. of AISTATS, 2016.
Chen, S., Zhang, Y.JJ., Tu, W.-W., Zhao, P., and Zhang, L. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. JMLR, 25 (178):1-62, 2024.
Orabona, F. A Modern Introduction to Online Learning. arXiv: 19/2. 2022.
Chiang, C.-K., Yang, T., Lee, C.-J., Mahdavi, M., Lu, C.-J., Jin, R., and Zhu, Online optimization with gradual variations. Proc. of COLT, 2012.
Orabona, F. and Pál, D. Scale-free online learning. Theoret- ical Computer Science, 716:50-61 690 2018.
10

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
Rakhlin, A. and Sridharan, K. Optimization, Learning, and Games with Predictable Sequences. In Proc. of NeurlPS, 2013.
Sachs, S., Hadiji, H., van Erven, T., and Guzmán, C. Be- tween stochastic and adversarial online convex optimiza- tion: Improved regret bounds via smoothness. In Proc. of NeurlPS, 2022.
Scroecaro, Z.,, Kolarijani, S., and Esfahani, M. Adap- tive composite online optimization: Predictions in static and dynamic environments. IEEE Trans. on Automatic Control, (115))2906-222111 2023.
Shalev-Shwartz, Online Learning and Online Convex Optimization. FnT in Machine Learning, 4(2):107-194, 2012.
Si-Salem, T., Özcan, G., Nikolaou, I., Terzi, E., and loan- nidis, S. Online submodular maximization via online convex optimization. In Proc. of AAAI, 2024.
Tsai, C.-E., Lin, Y.-T., and Li, Y.-H. Data-dependen bounds for online portfolio selection without lipschitzness and smoothness. In Proc. of NeurIPS, volume 36, 2024.
Yang, T., Zhang, I.., Jin, R., and Yi, J. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In International Conference on Machine Learning, pp. 449-457, PMLR, 2016.
Zhang, L., Lu, S., and Zhou, Z.-H. Adaptive online learning in dynamic environments. In Proc. of NeurlPS, 2018.
Zhang, Z., Bombara, D., and Yang, H. Discounted adaptive online learning: Towards better regularization. In Proc. of ICMI, 2024.
Zhao. P.,
Zhang, Y.-.., Zhang, L., and Zhou, Z.-H. Dy- namic regret of convex and smooth functions. In Proc. of NeurIPS, volume 33, 2020.
Zhao, P., Zhang, Y.J.,, Zhang, L., and Zhou, Z.-H. Adap- tivity and -tn-stationatit:: reeeeend dynamic regret for online convex optimization. JMLR, 25(98):
1-52, 2024.
Zinkevich, M. Online Convex Programming and General- ized Infinitesimal Gradient Ascent. Proc. of ICML, 2003.

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
Contents
A. OptFPRL
Below, we restate the main ingredients of OptFPRL using more detailed presentation.
A.1. Update Rule
Recall the notation a1: = Ets ay, The update rule of OptFPRL is:
11 = argmin {(
Pi:t
(1a
( +
Tx(aa) }
(17)
State vector
Incremental regularizers
Prediction
Set constmint
where each p. is the sum of the linearization of the cost function fe((t;) and some choice from the cone . (2;)
Pr 9: gi. ge @f(())). of (1x(xx)) = -x)
(18)
A.2. Regularizer
We use the scaled Euclidean regularizer,
(x( = 0t 2
- |
where o is the strong convexity parameter that will be set in every version of the algorithm. Note that the sum ria(-) is 01:--Strongly convex with respect to ||. or equivalently 1-strongly convex with respect to || = Vorall |l-
A.3. Pruning
Here, present mechanism for selecting the vectors gf from the cone (xx) Define the unconstrained iterate a!". which is obtained by solving the update rule without the indicator function
argmin (P1., x) rxr(())) fx)
Pruning will depend on whether this iterate belongs to the set X or not.
The unconstrained iterate ætt always exists and is unique due to the strong convexity of r1.(-). However, its membership in X' depends on the exact degree of strong convexity. When die O, we consider x.t $ X, as the minimizer of an unconstrained linear function does not exist.
select of as follows: for 1, set gi = - 6 = 01 = 0, and gi = otherwise. For all t 2:
{ - (PIa-1 + gr o a & X'
g.
(19)
otherwise.
Recall that this is valid choice because when z.! & X, then æ, (d)).. Hence, (x((z) contains elements other than 0, and in particular - (P14-1 9. 012-1w;). This is direct result of the optimality condition for the constrained iterate (17), see, e.g., (Beck, 2017, Thm. 3.67). For the second case, 0 is always a valid subgradient of the indicator function since in this case 2h Rt E X.
Due to the FTRL/OMD connections, detailed in the related work, the update rule can be made equivalent to the "one-step optimistic MD" formulation in (Joulani et al., 2020), under the consistent pruning in (19) using the flexible qe(-) terms in their Ada-MD update.
A.4. perppeeesee
To provide dual view of the proposed FTRL. variant, we look at the update step through the lens of dual maps.
12

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
First, recall the definition of the convex conjugate r* of closed convex function r(:):
= sup(a. y) r(z)
The update of FTRL can be expressed using the above definition applied to potentially time-varying r(-). Namely, the standard FTRL update can be expressed as:
RL a [+1 = arg min (g1a, æ) + (ox( = Vro:(
where r0.() is the conjugate of the cumulative regularizer (-=(-), restricted to X' via ro = Ix. From this viewpoint, FTRL maintains the state as cumulative gradients dual space.
The update of OptFPRL can be interpreted as:
1++1 arg min (P.:, x) + To:e(2) = Vro.t( (P11) Vr (Vr -t-ket)s
where / 7 k denotes the most recent step at which we chose to prune. The last equality holds by the definition of g (assuming no predictions). Intuitively, we retain explicit gradient history only since the last pruning step t k, while summarizing earlier history implicitly via the dual mapping of æz-k. The crux of the paper is showing that the way history split (explicitly tracked after pruning, and implicitly captured before) is what controls dynamic regret.
A.5. Regret Characterization
Define the dynamic regret metric against any set of comparators {ui) as:
T RT Σ - - f(())))((u))) = [x()) - -((,)) - Σ Pr. az -2),
T
T.
(20)
where je(x)= +xx The inequality holds by the linearization principle of convex functions Schale--hwwrrt 2012, Sec. 2.4), noticing that we indeed have P. E (a,( due the definition of p: (18), and the fact that the subdifferential of the sum contains the sum of the subdifferentials (e.g.. (Orabona, 2022, Thm. 22)).
B. Missing Proofs for Section 4
B.1. The Strong Dynamic Optimistic FTRL Lemma
Lemma 4.1. (Strong Dynamic Optimistic FTRL). Let ft()).(())) (.)),,)T W. be an arbitrary set of functions, predicted functions, and comparators within X, respectively. Let rz(-) be non-negative regularization functions such that
E++1 = argmin ha=(()) + se+1(a))
x
well-defined, where ho(x)) Tx(x),, and VI 2
(x) (x = (pr, x) re())) Pe E Oj((z.).
Then, the algorithm that selects the actions x441, Vt achieves the following dynamic regret bound:
R S T
(
T
hus ho: (x re( +
ho:(uu
hore (use) + re(ws)-
(1)
Proof.
T Σ hr(w)) - Ehi(un (Tr((ur)
tm1
tm1
13

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
T
(1t) - ho:t-1 (xx1))
(ate) - hove 1 + fT+1(UT)
(axe(
103e)
(ou( (T(I(UT)
hoa 1
T
T-1
ho: (1re+1)
ho.T(ur) (TTI(UT) +
Σ
hox (wr)
Σ
hoa hox(uett)
T
T-1
(a:)(at))
hou (204+)
hooT(00+11 + (xT++1) +
Σ ho (na(
Σ
haa (an((1))1))
[=
T
T-1
Σ
(o:((
(ou( - - (ooa(u)44))) Σ
FT+1(2T+1)
t=1
t=1
The inequality holds because of the update rule for each 2++1 for any t. I.e.,
bur((rr+1)+ + f1+1(1041) S hor((u)) + fr+1(ur).
Also, (o -
Writing he of the LHS explicitly we get
(pr, + re(es) - (pes uz) rr(uu)) fr+i(ut)
(hon((x)) - hor (2)+1))))))) + Σ (ho.(U)+1) - ho:((u))) - -
F(+1(0T41)
Since (+)1(-) does affect the algorithm, we can set it to O. Rearranging:
T (p Pp. xi) (pc, un) $ Σ (hox(0))) - (2:((2)41) - re( + re((())) + Σ (hox(ur+1) - ho.e(u)))
T-1
Noting that by (20), the LHS upper-bounds the regret, we get the result.
B.2. Bounding the First Part (I):
We bound (I) haa (h:a(x.)) (xx) - Nox (1)+1) re (xre) ) in two ways, which results in the min(;,) term. We present in this subsection
Lemmas B.2 and 4.2, corresponding to each argument of the min(..-).
First, we begin with Lemma B.1, which provides an additional characterization the iterate æ, as the minimizer not only of the original update rule, but also of related linearized expression.
Lemma B.1. For any 2t E X, Dz = arg min, (x:)-1(x)) + fe(x:) = æ, = arg min hoa-1(x:) + (gi. x)) + (g! x). where H. E (xx))) and gi is selected according to (19).
Proof. We are given that x2 = arg min ha:-1 (x) + Fe (x)) Thus, from the optimality condition for constrained problems (Beck, 2017, Thm. 3.67)), the negative (sub)gradient must belong to the normal cone at ayy
Vhaa-1 ÿ. E (xx)
(By definition of ğ.).
(21)
Next, examine the optimality condition for hor-1( (x) + (ā.. + (gt a)) and show that sa satisfies it. For y to be minimizer of (x) + (ğ., x) + (gf, x), it must satisfy:
-hhr-i g. - Nx(y).
14

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
Substituting æy in the above get
Vh1--1(21)) 9: - gl Nxx(xz).
(22)
Now, note that according to the linearization choices in (19), we have that either (i): gi = 0, or (ii): gf = -(p1a-1 + Gr + 01) In case (i), (22) reduces the given (21), meaning that æ; satisfies (22).
In case (ii), Note that -p + G. 01:--1 1 (x)) V--Vha--1 (xx)) Gr. and hence (22) reduces to 0 Mx( which is
always true. Thus, 2; satisfies (22) in this case too.
It follows that Ds satisfies the optimality condition for ha=--((:)) + (g), σ)) + (gl, æ) and hence is minimizer thereof.
Lemma B.2. Let each function ho:(.) be 1-strongly convex with respect norm || ||e defined as in Lemma 4.1. J. Let Zt = argming (x) + ft()). Then, we have the inequality
hoa( hoa((x+1)) Tz (xx,) S 2Rc,
Proof.
(a:) hox((8211) (x:))) = ho:--1 (2:)) + (pe, hox (1044 ((+1) (1(+1))
ho--1 (mt) (pi, x..) hoa- (a++1) (pr, (
1o=-1(x;;) + (p,, xt)
ho.t- (B:) (P:.ye).
(23)
where (a) follows by dropping the negative - rx (2 term and (b) by defining y: = arg mitl 1 + (p:, a). Then,
ho.-1( + (pt, xt) - ho:- (3)) - (p:, 3/0
hoa- 1 (xt) + (g: + g xx) + (pe: xz.) 11:t-1(91)) (pi. v1) (g: + g! xt))
(c)
har-1 (3)) + (g. + g y.) + (pr, v.) - -hot- (y:) -P:, vv) - (g. + gl. x.)
(g. + 9 Vt xx) + (p. yo) (pt, 32 yt) (g. + gl yt)
(p. ğ: gi. at y.) (g. gr. F. ya) S 2 g. ğell 2
where we added & subtracted (ğ: + gi wt) in the first equality, and (c) holds because æ, is the minimizer of hox=1( + (g + gf: æ) (shown by Lemma B. Overall, we obtain
hoa (xxe) (0:(())1)) rx(e))) (een)-re((p)))) < 2
(24)
To produce the other argument in the min(-,)) we use the following lemma.
Lemma 4.2. Let each function hoa(-) be 1-strongly convex with respect to norm l|e defined as in Lemma 4. Let
2; argming 110=-1(x)) + fe( Then, we have the inequality
1 1g: g. 1
hoa( (xx) (0::((41))-)))) rx(x)) ( S
2
Proof.
hoze (2x4) ho:e (2)(+)))))))))))))) (xxe))
Since hoa is strongly convex, the minimizer of the two expressions in the lemma statement always exist and unique. In the case Tie 0, abuse notation by writing argmin" instead of e argmin" ". This is not prohlematic because do not require the equivalence of the minimizers.
15

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
ho:-- ( (pt, 2)) ho- (1141)
2041?
Te (1(41)
ho:e-1 (zz) (p), hoa- (21+1)
(c+1)
ha---1 (ax) + (P:, xzi) hou-- (V:) Up): = argmin argminnoa=- + (Pr, a))
x
Where again the inequality follows by dropping the non non-positive -r((-). Next, we invoke Lemma D.1 with
$1 (x) = ho:- 1 (x) x))
Φ2 Φ2(x)) (x) ho.t 1 (ar) + (pi, 27) higt (x) + (gt: a.) (gt x) =x((2) + (g: gr, a))
(x))
Under these definitions, we indeed have that
2t argmin ho:-- fx)
(Lem B.1) argmin ho:-- (2:) + (ā.. m) + (g!, .x) = arg min (x) = yi-
and thus selecting y' of Lemma D.I as yt. the result of the same (Lemma D.1) gives:
(xxe + (pr: v.) (1.1-1(11)) (pr, v1) S $ g1 gr 30.li-1,
(25)
noticing that 0v((x;) 9:- g-- From (25) and (24), have that
(I) min Hll.- -e 2Ber
(26)
B.3. Bounding the Second Part (II):
The second part does not have the structure exploited in the first one (u, and u441 are arbitrary). Hence, we must resort to the strong convexity property to obtain
hoa(ue+1) (14) (g:, U1+11 - ue))
01
|1+11
uell
2
qall |uu+1 well
T1:
|
us 10l1
where
ge E Qhoa(ur+1)
Nonetheless, will still exploit problem properties to bound ||qr]]:
Oh):( Pia + Σ 0, + NN(x),,
which gives
q: P1a +
U,441
where we chose the vector from Nxx (w1+1). Hence, the length of qe satisfies:
1qill I || Σ ox 1141l ||
| and u+t1ll $ | Ro
16

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
Overall
host (1t41) (1,) S (1p1æll Roya) |14+1
|1+1
u4 112
(27)
From (27) it follows that
01: m (I[Pi:ll + Ro || uell
|1411 - uel1
(28)
2
< (IlP::ll + Rov:)) ||4411 uell
(29)
Note that the negative term in (28) admits a tight lower bound of O and will therefore be omitted. Next, we derive a bound on the state vector's length |pt:e|l-
Lemma 4.3. (Optimistically Bounded State) Let {prYi=1 be a sequence of vectors such that each p: = g: + gi where g, (z.)), and g! E (x+) is chosen according to the construction (5). That is, P. corresponds the linearization of the composite function fe(-) + Ix(+) around xt. Then. for any the following holds:
||P:l S Røia-1 1 + ct-
Proof. The proof of this lemma stated in the paper.
C. Missing Proofs for Section
Recall the problem parameters described by the following settings: Settings Let c Rd be a compact, convex set such that ||ж||| < for æ E E Let (AO),))) be any sequence of L-Lipschitz convex functions, and define the following quantities.
The cumulative-squared prediction error: Ep
E
6 4= llg. -gel
T-1
The path length:
Pr =
|1411 - uell
T-1
The prediction-weighteed path length:
Hx
Σ
Cell Cellu411 uell
C.1. Proof of Theorem 3.1
Consider the following regularization strategy
1
and σel, oi = (oo(VVE. (VE--VEs VE-- Vt 2 2.
(30)
4R'
Theorem 3.1. Under Settings 1, Alg. 1 run with the regularization strategy in (30) produces points {x.)T= such that, for any T, the dynamic regret Rr satisfies:
Er H = O (1+
Rr S
Proof. We begin by substituting the bounds of (I) and (II), from (26) and (29), respectively, back in the result of Lemma 4.1:
T
T- ( (Rovæ + (|ppellll 11at1 u.ell)
g. - 3:112110, 2)(e) + rr((u)))
Rr <
min
+
min
1
2 9:: T. 112-1,0.
1, 28e:)
+ ri(ui)
(2Ro + Ex) ||ue11 uell)
17

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
R
min
2 9:
Telli-1,0:
2Rc,)
LT
+
(2 + 4) || u.ll)
2
R2
T-1
min
2R
01T
+
Σ
(e + (2) |ee+1 uull)
20
R2
T-1
min
2eex
+ 2
FT +
Σ
SeRoVEi+ty | - well)
20 Er-1
T-1
R
4V2RV
ET
+
ET
+
v
Belluce11
uell + HT
2
t=1
- 5.8R ET + ZV ET
1
u1411 - + HT
= 5.88V ET + 2 Er /VErPr + HT
where (a) follows by Lemma 4.3 which bounds ||Pi:ell and by the fact that 0 S o.., (b) by bounding each || in Ts ru(ee) by R. (c) by Lemma D.3, which is common tool bound the sum of a decreasing function (on 1;-1), with the choice of
and (d) by the fact that VE, non-decreasing.
Remark C.I. On the growth rate of the hybrid term HT.
Note that by Cauchy-Schie Sauwhy-Schwarz, we have that
T-1
HT Σ a uulu1+11 - woll t=1
Σ
Σ
U++1
u1l2 V2R,
U1+1 uell v2R ETLEEE-11 Pr.
1=1
Hence, Hr is also O Er))
C.2. Proof of Theorem 3.2
Consider the following regularization strategy:
1
=
where Pf is the augmented path length: Pf = 2R + Pr.
2 /R
(31)
01 = 061 01 = (VEL- vt 2.
Theorem 3.2. Under Settings 1, Alg. run with the regularization strategy in (31) produces points {xt)T=1 such that, for any T, the dynamic regret RT satisfies:
RPT 2
R < 4/ 4//2R
Er + HT = ( (P))
8
Proof. Similarly to Theorem 1, we begin by substituting the bounds of and (II), from (26) and (29), respectively, back in the result of Lemma 4.1:
9: g..1 + +r((ue))
Rr
min
+
( RRov + (|p |11411 u.il))
min
9g: g. 12: 2Rer)
+ ri((u))
+
(2R + <e) || - well)
2
R2
min
g: 2 1. 2REa
OUT
+
(2R 6x) |1011 u.
2
18

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
R
min
2Rc
+
OLT
+
(2 + +.) || 2eel)
-
2
t=
min
7
2R
R
PT
+
Σ
(2Ro F + te) l -mel) will)
20 E1-1
2
t=l
R²
R
AVR
Pf PT
FT
V
Pu + tet |
4 1/22PP
/2RP7
(4)
R
T
11+11 ulll
2 AVR PTET+
+
V
ET +
+ HT
VPT
AVR P PT 8
R
FT
+
V22
R.
P.T-1
Pt. PPr
+ HT
< <AVR PT +
VET +
R
V
R
V ET E Pr HT
R
R
4/ RP +
PT
v E + HTT
8
2
R
R 2
< AVR(2R+ Pr)
+
+
PP
Pr]
Vr HT
= =0 -I(+V/PAVEE PT)
where (a) follows by Lemma 4.3 which bounds ||P..ll. and by 01--1 S T14, (b) by bounding each ||wel| in tr(w),, T by R, (c) by lemma D.3, with the choice of a 2//2RP/' (note that this choice still satisfies the Lemma's condition since
P4 2 (d) also used that used 2R < P/ (e) used that E, is non-decreasing, and finally the O(-) expression follows from Remark C.1.
Remark C.2. On guaranteeing / FP Vu,
To obtain a minimax bound that holds uniformly over all comparator sequences (i.e., without assuming prior knowledge of their path length, and without assuming that they are observable online), one can instantiate O(log I') sub-lcarners, each with a halving a starting from 1/VT. Then, using the meta-learner of (Zhao et al., 2020), the minimax bound can be recovered. The gist of this approach is that eventually 3 an expert such that VPr, (i) 2 1/vPr 1/20(0.
(()
C.3. Proof of Theorem 3.3
Define the augmented seen path length at t as:
P. = 2R +
|r+1 -u
and consider the following regularization strategy
σEl
Ex P!
E1-1
0 = 2/2R'
0==
=
Vp
oe o==o
max
0,
Pi
V22 2.
(32)
Theorem 3.3. Under Settings 1, Alg. run with the regularization strategy in (32) produces points {xr1T= such that, for any T, the dynamic regret RT satisfies:
RT < 5.5VR Ry
ET + HT + 1122 AT = - ( /Pr) ET +A)
where
A7 - Σ t=1
V
Fr-1
Pr
P
E
|14+1 - well.
-uell
[ + with
22 {
E
Ex pr
0
+
19

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
Before proceeding to prove the theorem, will make of the following two lemmas, which we present independently streamline the presentation.
Lemma C.3. The squared norm 1|9:
g: f 00:-11
g: 22
00:-16 can be written as:
|gg -t 11o. = 0,
1
P 2 66
|19: 9 1
121 1
F
Proof. Recall first that the dual norm of
|| 11+-1,,
||
The first part immediate from ||=||o,
v
En Pb
a
voou-1
since Fgg = and Pdj 2R. For the second part:
1g
Dcll
11g: - 3.
01.--1
VPi
2
max (0,
V
Pr
E.
Fr
E
E
E1-1 P
Pr
where the inequality follows by dropping the max in the denominator.
Lemma C.4. The strong convexity parameter d1a in (32) be written the cumulative term V
Eg P.
plus corrective
term:
E Ph
E -
E
Tee =
(
+
P
Pr
TE(d]
Proof.
d61
E
E
O1d
P
max
0,
P
pr
T=2
Ex
P
E
E
P
P
P
Pr-1
V
Pr
TE/E
where the last equality holds from the definition of [I]+ That is, for the slot r when the max evaluates to 0, we write it as Now, by telescoping
(V P
(VE=_
E
E.
Pt
E
E
E
Ex
Σ
σ
P
P
Pi
+
P'
P
+E(l++
E
E
E
Σ
+
T
P
Pr
TE|M-
Proof of Theorem 3.3. We begin by substituting the bounds of (I) and (II), in (26) and (29), respectively, back the result of Lemma 4.1:
T-1
RT
<
Σ
min
1 - gg ge
11.12-1.0 2Rez) + re(uu))
+
Σ
((Ro + ||ppa))))
||u -well)
2
20

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
T
min
2 9:
2ilii-1,;:Re,
+ tr((u))
+
((2 + ce) 11 u.ll)
1
WN
R2
T-1
min
2 9: 0.:1:-1,0:220
o1r
+
Σ
2 2 u441 uell + HT
2
1
T
min
2R
2
U1+1 - uell + HT
20 v E--
T
min
2Rer
+
2Ro
Uc+1 - uell + HT
20 /
P
FT-1
Frr
+ 2Ro
Σ
Σ
|1141 well
P
Pr
1=1 TElE
EAT
2R Ft.
E
Pr min
2Ro
U1+1 - uell + HT + 2Ro AT
20 E
VP
P
67
T Σ
||ur+1 uell
Pr min
V2RG,
+ 2Ro V Ex
+ HT + AT
20 EI-1
VPI
t=1
3 24VR Ps + 1
R
FT
T
|1+11 Uell
+ HT + V 2
R
Ar
V 2R + Σ 11 -1-l
(1)
T
|1+11 uell
R
2 AVT PT + Fr
+ HT + V
Ar
Et= || - urll
2
② &AVR / PT + V2R PT + HT + V
R
Ar
2
R +4+ 22VR Er + Hr + V Ar
where (a) follows by Lemma 4.3 which bounds |P ll. and the fact that 014-1 S d (b) by bounding each |/ || in re (u,), 1 < T by R, (c) by using Lemma C.3 for the first sum, and by selecting" 11 WT+1 such that || ur > R which allows us to append the & T term to the second sum as the summand with index T, (d) by using Lemma C.4 to re-write Ti: (e) since P is non-decreasing, (f) from P 2 2R, (g) by a = 1/2/28 and Lemma D.3, (h) by the fact that 2R Me++1 uell, Vt. and finally (i) by Lemma D.2 with az |1+1 uzll-
C. BOUNDING THE AT TERM
In this subsection, show that the term Ar cannot be worse than the result of Theorem in all cases.
E-
E
(v
E
E
Ar
Σ
Σ
||
uell
Σ
||uct1
uell Σ
P
V
P
P/-1
P
1=1
+
TE(t]+
Ex
Er P
|1+11 will Σ
V
P/-
V
+
|1411 - uel
Σ
V..
1
1
P
V
P
+
I1 Note that u1+1 does not affect the algorithm and hence we can set without loss of generality
21

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
1
11+11 - Uh IvE
Σ
P T-1
Pt
FE(T++
IA
- 1011-- Er
P 7-1
T=2
1
|u--1 - -ull1
V
P4
P!
18
14411 1ir11-ellVEy E.l
Pí
FTT
T
U1+1 - uell
P
PT (V
Pl
where (a) is from F,, 2 -1 for all 7 by definition; (b) holds similarly because E, is non-decreasing on (or l); (c) holds because P/ < P. for all (for any slot f) and hence we can add additional positive terms and create the entire sum from 2 to T I, instead of only the partial sum of terms in [t]+; (d) holds by writing the telescoping sum; (e) holds by dropping the last term which is negative; and finally in (f) we used the fact that Er 2 E,, Vt.
C.4. Proof of Theorem 3.4
Consider the following regularization strategy
o 8R i σt oö.
(33)
6 = (g), m1) - min (g), x);; 6, = ho--- + (pe, 24)) - min (ho=--((x) + (pi, x)), 2; mex
=ex
Clarification the term "recursive": In previous regularization strategies, the strong convexity at time t, d1: can be oe E
expressed in closed form as 0ia o This follows from defining each to be exactly O(VE, v E
of However, when oe defined more generally as a scalar ad,, where & can take any value [0, a 2 E compact form. Instead, Tir is now recursively defined as a + σ6,, As discussed, this ensures minimal regularization, impacting both the algorithm's 's behavior and the analysis.
)}. we lose this
Theorem 3.4. Under Settings 1, Alg. 1 run with the regularization strategy in (33) produces points {xt)7 such that, for any T, the dynamic regret RT satisfies:
Rr 1
Σ 1=1
S1 4R
|1+11
-u + H1
Hr 0 Ou+
Proof. We begin from the result of Lemma 4.1 but without substituting the upper bound on part (I), in order to characterize more tightly via the &, terms. For the term (II), we use the upper bound from (29):
T
T-1
Rr S Σ (houe (2:(()))1) + re(uu)) - r2()))) +
Σ
(Rooa + || [| uell)
(a)
Σ (ao)( rx(())) hot ( - re (x(44))) (p,, 0.+1) + re(ui)
1m1
22

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
12 + +.) 114c11 - uell)
(a02-1(0s) (p) (2001 2e+1) rr(()))
(2R + (() leeeee - uell)
(0) T
Σ
(d + +rr(())) +
(2Ro + 11211 - uell)
1=1
R20
+
8
11T
+
Σ
2o /0 11411 uel1 + HT
2
t=1
(c)
T-1
3 1.1 :1.T
Σ
61.
uell Hr
(34)
4R
where (a) follows by Lemma 4.3 which bounds P1: Il. and by the fact that 01:-1 S 01:ts (b) by dropping the non-negative
-11( (c) by the definition of & (d) by bounding each ||u,]] in rr(e),),, < T by R. (e) since 1/88².
C.4.1. BOUNDING THE RECURSION
Note for each 6 we have that
6, 2
The above follows from Lemma B.2. Specifically, note that ò, is equal to the expression in (23). In addition, we know from Lemma 4.2 that
6, S 2013-1
by noticing that 5g is the LHS in the inequality (25). Substituting the strong convexity term die for the choices made in this section (33), we get
4R
8e S
51:-11
Overall,
4R22
8, < min
2Ree: 81
We can now invoke the auxiliary Lemma D.4 on the last term with 0₂ 2Re,, A, = 61 to get that for any 1
S1 S 2V/RVEE
Going back to (34), we get
17V3
T-1
V3
R₂ <
R
ET +
Σ
E
U:41
-uill + HT
8
2
t=1
17v3
v3
R
Ex +
VEPP Hr
23

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
D. Auxiliary Lemmas
Lemmas/theorems here are (specialized) results from the literature with potentially modified notation.
Lemma D.1. (McMahan, 2017, Lemma 7) Given a corvex function (-) with a minimizer yı = argmin, $1 (v) and function (z(-) = (1(-) + v-() that is 1-strongly convex w.E.t some norm || ||. Then,
(2(11) 22(10) - b
for any y', and any (sublgradient b e (1)()))
Lemma D.2. (Auer el al., 2002, Lemma 3.5) For any dt 2 2 14 E (T]
T
T
a
I 2
Σ
at:
O11
1=1
with the convention that U
0.
Lemma D.3. (Orabona, 2022, Section 7.6) Let R be positive real numbers that satisfy S
b 0. Then, for any 26
1
2 0, VI
[T]:
T
of
V2
T
min
bo:
20
t=1
Proof. The proof of this lemma closely follows the argument presented in the cited section. However, due to the inclusion of the term b in the second part of the min, we adapt the proof accordingly to account for this difference.
00
af
min
bat
min
blaat
20
V
Σ -
az
2
am
T
a
(a)
2
min
4b2ot
2
0²
Σ ==
a
t=
a7
ab
1
2
(8)
1
Σ
2 b a
V2
2
ob
34 1 a2
16 a7
+
2
t=l
4b2
Σ a2
20
E+=1
a
where (a) follows by min(a, b) S 1o.+1% and (b) used the assumption on a to append of to the sum. The result then
2
follows by lemma D.2.
Lemma D.4. (Orabona & Pál, 2018, Lemma 7) Let a, 2 0, Vt e [T]. and A, be a sequence of positive numbers satisfying the recurrence
of
A A min at A
with Ao = 0. Then, for any T, we have that
T
AT
24

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
E. Comparison with the Literature
We summarize the key differences between our work and the relevant existing results on optimistic dynamic regret. The selected references represent the best known regret bounds (there are many other works that focus on different aspects, such as efficiency, unbounded domain, etc, but have the same structure as these bounds). is important note that some of these works derive bounds in terms of quantities other than the gradient prediction error, such as the extended "temporal variation" in (Scroccaro et al., 2023) or the "comparator loss" in (Zhao et al., 2024). For the sake of consistency, we restrict the comparison to bounds involving ET, choosing Er in cases where a min(Er,)) term is present in the literature. Extending FTRL-based algorithms to handle comparator loss and temporal variations, dynamic regret bounds remain open. Lastly, in the comparison below, "best-case" refers to the scenario where Er = 0, corresponding to perfect predictions.
Bounds without tuning for Pr:
(Jadbabaic et al., 2015) Obtains a bound of
+ 1), which is O(P)) in the best case.
(Scroccaro et al., 2023) Obtains bound of (((P=+ which (Pr) in the best case.
where Dr = Σ V VVi((--))
(Zhao et al., 2024) Obtains bound (VV(VV + PT + 1)(1 Pr)), which is ((Pr) in the best case. Note that all Pr appear under the root. Hence, this bound still matches the optimal min-max bound of vT(I+ Pr) in the worst case.
This work achieves a dynamic regret bound of Rr = (((1 + /rr, which is in the best case.
Bounds with online Pr estimation:
(Jadbabaie et al., 2015) Obtains a bound of
+ 1)), which is ((log(T))Pr) in the best case.
(Scroccaro et al., 2023) Obtains bound of O / (Pr 1) where O is the sum of corrective terms O,, which are added to the learning rate to ensure monotonicity, and holds that in the perfect gradient prediction case 0r = (1 + Pr) and the regret bound is also ((P)).
(Zhao et al., 2024) Maintains the same bounds since, as detailed in the main paper, this meta learning framework provides bounds that hold simultaneously for all Pr. The bound is O( O(V(Vr + Pr + 1) Pr)), which is (PP)) in the best case.
This work achieves a dynamic regret bound of O(LI+ ET + Ar), which is 0 in the best case.
F. Numerical Examples
In this section, we present numerical examples comparing the performance of three standard implementations of OCO algorithms across multiple non-stationary environments (sequences of cost functions). The algorithms considered are:
FTRL with adaptive Euclidean regularization, which corresponds to a lazy projected Online Gradient Descent (OGD) but with Adagrad style tuning (McMahan, 2017, See. 3.5)
OMD with data-adaptive learning rates, which corresponds to greedy projection OGD (Orabona, 2022, Sec. 4.2).
Our proposed algorithm, OptFPRL, with the vanilla tuning strategy (i.e., in Sec. 3.1).
The implementation code for the algorithms, along with the code reproduce all experiments, is available the following repository: (Mhaisen, 2025). Since the FTRL and OMD variants used in our experiments neither assume prior knowledge of PT nor attempt to estimate it online, we compare them to OptF using the tuning strategy described in Sec. 3.1 to ensure a fair evaluation. In scenarios where no predictions are used, the predicted functions fed to the algorithms are set to zero. This allows us to understand their performance initially, independent of prediction quality. Even without predictions, the proposed algorithm outperforms the two benchmarks in many scenarios, demonstrating its performance in dynamic environments.
25

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
Numerical setup. X' = (ær R | s 2) [((x)) (et, x), T 5000, with
Scenario 1: C1...., C1000 1,
C1000.....
C5000 1.
Scenario 2: C1....., C1000 1, C2000. C2000
1,
C3500
C3750
1, = =1 otherwise.
Scenario 3: C1 C1000 = C2000 25000 = 5,
C3500
C3750 = 10, C = otherwise.
Scenario 4: C₁ alternates between and 11 every 50 steps.
Scenario 5: C₁ alternates between and -0.1 every 50 steps.
Scenario 6: C₁ alternates between and - every 50 steps; Predictions ē
1i E [7]
0.11
FIRL
FFR..... CuSPRR.
FTRI,
Ope
000,
Average regnet R.
Ref
Avarnge raghot Ro
Horizon T
Horizon
Hortzon T
(a) Scenario 1
(b) Scenario
(c) Scenario
25
PTCL PTRL
DMD
OPFFR
0MD 500 010, ..
CaFFRR .. C.
OMD, m.
OMD.....
2
naghes Ric
1.5
Avrerage
Horizon
(d) Scenario
(e) Scenario 5
(f) Scenario 6
Figure 2: Average dynamic regret over time across various non-stationary scenarios. Dashed lines indicate time slots where the computed iterate differs from the comparator o;
The observed behavior across different scenarios in the above figure aligns with theoretical expectations. In Scenario where the cost function shifts at 1000, standard FTRL struggles to adapt due to its reliance on accumulating all past costs. This inertia makes it slow to respond and leads to continued suboptimal actions until = 2000, resulting in high regret. contrast, OMD reacts immediately to the shift, adjusting its actions accordingly. Similarly, OptFPRL adapts directly, resulting in lower regret.
In Scenario where cost directions change multiple times with increasing magnitudes, the limitations of FTRL become evident. The average regret fails to diminish, demonstrating its inability handle such non-stationarity. While both OMD and OptFPRL respond to these variations, OptFPRL achieves lower regret. The advantages of OptFPRL are more pronounced in Scenario 4, which involves high-frequency cost changes. That said, the observed difference between the implemented versions of OMD and Opt FPRF is primarily due to the parameter tuning of each algorithm. The tested configurations use the theoretically optimal learning rate 7), for OMD and regularization parameter d, for OptFPRL, but different choices may lead to considerably different behavior. In contrast, the poor performance of vanilla FTRL cannot be mitigated by tuning theoretically motivated parameters- its failure more fundamental, as discussed the main text.
26

---

On the Dynamic Regret of FTRL: Optimism with History Pruning
We also highlight scenario in which OptFPRL performs the worst (Scenario 5): high-frequency switches with alternating magnitudes (large and small). This setting is deliberately designed to exploit our method's extra agility, forcing "undue" frequent adjustments. As expected, OptFPRL exhibits higher regret in this case, consistent with the theoretical results. Nonetheless, this tradeoff is inherent to the design and provides insights into potential extensions that balance agility and stability.
Lastly, we highlight in Scenario 6 the role very high-quality predictions in the performance of the optimistic versions of the three algorithms ((Jadbabaie et al.. 2015) for OMD and (Joulani al., 2020, Sec. 7.1) for FTRL). We plot the average regret under predictions constructed the original functions plus adversarial noise. Specifically, the adversarial noise is set the negative of the original cost functions, with magnitude decaying quickly 1/(0.It), becoming negligible by = 100. As noted in the paper, standard FTRL can be easily "trapped", accumulating redundant gradients and failing to track the comparators. Optimistic OGD and our OptFPRL react immediately when losses change direction.
27


Reviews:
[{"review_id": "lIkRzkrgG8", "reviewer": "Reviewer_2ZjR", "summary": "The paper presents a new optimistic algorithm, Follow-The-Pruned-Leader (FPRL) that aims to achieve dynamic regret in $O(\\sqrt{P_TE_T})$, where $E_T$ measures the prediction error. The key insight is to avoid simply stacking previous gradients as they make the standard Follow-the-Regularized-Leader (FTRL) less adaptive to dynamic environments. It is done by \"pruning\" past gradients when their updates become too \"large\". They achieve $O(\\sqrt{P_T E_T})$ when $P_T$ is known in advance or the comparison  sequence is observable, but also universal regret (i.e for all sequences simultaneously). Finally, all the terms in the regret scale with the prediction error, meaning that, compared to previous work who had an incompressible dependence on $P_T$, the dynamic regret of FPRL can be constant for perfect predictions.\n\n## update after rebuttal\n\nI decided to maintain my score", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for taking the time to read the paper and provide the feedback.\n\n**Claims \\& evidence**\n\n$258R$: Indeed, these details were omitted from the main text due to space constraints and accidentally left out of the appendix. We apologize for this oversight. Briefly, the claim is that the term $H_T \\doteq \\sum_t \\epsilon_t \\lVert\\boldsymbol u_{t+1} - \\boldsymbol u_t\\rVert $ is $\\mathcal{O}(\\sqrt{P_TE_T})$, and therefore never dominates  the bounds in Theorems $1$-$4$, since those are $\\Omega(\\sqrt{P_TE_T})$. We state the remark below.\n\nRemark: Let $\\epsilon_t^2$ scale as ${1}/{t^{1-\\alpha}}, \\alpha \\in (0,1]$ so that $E_T = \\Theta(T^{\\alpha})$. Similarly, let $\\lVert \\boldsymbol{u}_{t+1} - \\boldsymbol u_t  \\rVert$ scale as  $\\frac{1}{t^{1-\\beta}}, \\beta \\in (0,1]$ so that $P_T = \\Theta(T^{\\beta})$. Then, we get that $H_T  = \\sum_t {1}/{t^{(1-\\alpha)/2\\ +1-\\beta}} = \\Theta(T^{\\beta +\\ \\alpha/2\\ -1/2})$ and it holds $\n{\\beta +\\ \\alpha/2\\ -1/2}\\ \\leq\\ (\\alpha+\\beta)/{2},\\quad \\forall \\alpha, \\beta \\in [0,1).$\nThe RHS is the growth rate of $\\sqrt{P_TE_T}$.\n\n\n**Weaknesses**.\n\n**On the circular dependency**. Incorporating non-linearized  $\\tilde f_t(\\cdot)$ is offered as an option to avoid circular dependencies, but it is not required for the update to be well-defined.  When efficiency is a priority, linearized FTRL, like OOMD, can follow the standard practice by setting  $\\tilde {\\boldsymbol g_t} = \\nabla \\tilde f_t(\\boldsymbol x_{t-1}) $ (i.e., linearizing the predicted function around the previous iterate), as done in prior work (e.g., see $\\tilde{\\boldsymbol g_t}$  Flaspohler et al., 2021). Hence, we maintain linearized forms and computational efficiency at the cost of having the somewhat less-informed quantity $\\sum_t \\lVert \\nabla f_t(\\boldsymbol x_t) - \\nabla \\tilde f_t(\\boldsymbol x_{t-1})\\rVert^2$ instead of $E_T$, as you correctly note. Moreover, in many cases, avoiding non-linearization does not compromise efficiency (see Questions)\n\n\n**Questions**.\n\n**Linearization \\& Efficiency**. In fact, including  $\\tilde f_t(\\cdot)$ does not always compromise efficiency. For example, when $\\tilde f_t(\\cdot)$ are weighted $\\ell_2$-norms, the complexity remains the same as OMD (i.e., closed form in $\\mathbb R^n$ + Bregman projection). Nonetheless, for general convex predictions, solving a convex subproblem is indeed required. In such cases, practitioners retain the option to linearize (around the previous iterate). \n\n**on** $\\sigma_{1:t}=0$. This condition addresses the situation when $\\boldsymbol x^{\\text{uc}}_t$ does not exist. In other words, we simply specify that if such a point does not exist, it is treated as lying outside $\\mathcal{X}$, ensuring the update step formula remains well-defined.\n\n**Recommended experiment**.\nWe repeat Scenario 4 from the paper, but now comparing the optimistic variants of OGD, FTRL, and our proposed OptFPRL. We plot the regret $R_T$ under predictions constructed as the original functions plus adversarial noise. Specifically, the adversarial noise is set as the negative of the original cost functions, with magnitude decaying quickly as $1/(0.1t)$, becoming negligible by $t \\approx 100$.\n\nThe resulting figure, along with algorithm implementations and the full code to reproduce these results, is available at the doubly-anonymized link: https://anonymous.4open.science/r/11679-3538.\n\nAs noted in the paper, standard FTRL can be easily “trapped,” accumulating redundant gradients and failing to track the comparators. Optimistic OGD and our OptFPRL react immediately when losses change direction. Indeed, achieving constant regret under perfect predictions primarily serves as a sanity check for scale-freeness, rather than the central advantage. This objective was set to preserve the scale-freeness property observed in OMD while developing FPRL. The main benefit of FTRL-based formulation lies in its flexibility to arbitrarily choose and, potentially center differently, regularizers, enabling a ``compressible\" dependence on $P_T$, as opposed to having fixed mirror maps that time varying weights (i.e., learning rates).\n\n**Other comments**.\nThank you for the careful reading, we will make sure to fix the typos.\n\n$\\bullet$ Appendix $180$. True, the minimizer in $\\mathcal{X}$ ($h_0=I_{\\mathcal{X}}$).\n\n$\\bullet$ Appendix $638$. $\\delta_t \\rightarrow \\epsilon_t$.\n\n$\\bullet$ $421$L. $R_T \\rightarrow R_T\\leq$.", "claims_and_evidence": "Yes, They provide proofs for all their claims along with simulation experiments the improvement of their method.\n\nHowever, the claims regarding the remark 258R-270R is not detailed in appendix contrary to the authors claims.", "methods_and_evaluation_criteria": "They use dynamic regret as a criteria which is standard.", "theoretical_claims": "I checked all proofs, all except the proof of Theorem 3.3 that I did not read. I skimmed through the one of Theorem 3.4. \nNo issues on what I read in terms of proof, but there is some comments that must be addressed, notably on the cyclic dependency (See weaknesses).", "experimental_designs_or_analyses": "Yes, the experimental design makes sense and highlight the strength and weaknesses of their method. It would have been good to also have experiments showing how the regret converges for perfect predictions while other methods that have a linear dependency on $P_T$ keep increasing. This would be in a very dynamic environment, like scenario 4 of Appendix F", "relation_to_broader_scientific_literature": "- The algorithm builds on previous FTRL / OptFTRL work but contribute a new idea of choose smartly a subgradient from $I_\\mathcal{X}$ (indicator function of the set) to have a more adaptive algorithm. Their update has some similarity with (McMahan, 2017)\n- Their dynamic  regret guarantee improves the current best ones, i.e Zhao et al., 2024 by having a regret that goes to a constant when the predictions are perfect.", "essential_references_not_discussed": "None that I can think of.", "other_strengths_and_weaknesses": "Strengths:\n- The experiments really highlight the benefit of their method\n- The regret derivation is easy to follow and the main body explain the core ideas pretty well\n\n\nWeaknesses:\n- Some math equations are hard to follow because of typos and alignments.\n- Computation cost (see next weakness)\n- The authors mention avoiding the circular dependency, but I am unsure (if we want to stay computationally efficent). OOMD linearize first in order to minimize computation cost, and since $x_t$ is unknown, the linearization is often done around $\\tilde x_t$ (an intermediate value that does not depend on $f_t$). Here $x_t$ depends on $\\tilde f_t$, thus we cannot linearize around $x_t$ to make the computation. So, if we wanted to stay computationally efficient and linearize the prediction, it will be around $x_{t-1}$ leading to the same issue noted by Scroccaro et al. (2023).", "other_comments_or_suggestions": "A bit too many typos and math alignments that are wrong: (I use L for the left column and R for the right)\n1. the notation $z_{1:t} := \\sum_{\\tau=1}^t z_\\tau $ where $z$ is any sequence is never formally introduced. (yes it appears in line 72R but not as a definition).\n2. The function $h$ is used in line 307R-310R before being introduced in line 367L).\n3. Appendix 180: I think it should be $x_t  = \\arg\\min_{x\\in\\mathcal{X_t}}$ instead of for any $x_t \\in \\mathcal{X}, \\dots$. As the condition (5) in line 185 is true only if $x_t$ is the minimizer of $\\mathcal{X}$, but I might be wrong\n4.  Math Alignment issues ( the equal or inequality signs appear mid lines, making it hard to read):\n- Appendix 324-326\n- 385R-389R\n- Appendix 165 . That $\\tilde f_{T+1}$ term is too isolated\n5. Typos\n- 265R ($E(T^)$ (missing the power and the parenthesis is raised\n- Appendix 638 $\\delta_t$ appears in its own upper bound\n- Appendix 660 $<p_t, x> \\to <p_t, x_t>$\n- 421L . \"we have $R_T$\" followed by equations. Maybe it should be \"$R_T$ is upper bounded by:\" or $R_T$ should be in the equation below.", "questions_for_authors": "1. What is the difference in computation time between this method and OMD. Does the method benefits from using an optimization on $\\tilde f_{t+1}$ when OOMD focuses on the linear approximations.\n2. (Repeat on the experiment) Does the regret converges for perfect predictions while other methods that have a linear dependency on $P_T$ keep increasing. (The regret, not the average regret).\n3. See third weakness. Any comment ?\n4. In appendix 103, you say, when $\\sigma_{1:t} = 0$ but it does not seem to be used in that proof. Is that a typo?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VjmOsJBWUd", "reviewer": "Reviewer_ecer", "summary": "This work revisits the Follow-The-Regularized-Leader (FTRL) framework and explores how to utilize FTRL to derive dynamic regret bounds. The key finding in this paper is to predict with the modified loss $f_t(x) + I_{X}(x)$ rather than $f_t(x)$, where $I_X(x)$ is the indicator function. When the unprojected decision $x_t^{uc}$ in the FTRL framework deviates from the domain $X$, the introduction of the indicator function $I_X$ serves as a  \"corrective mechanism\", thus enabling the derivation of dynamic regret bounds. \n\nThis paper considers two cases: when the path length $P_T$ is known and when $P_T$ is unknown in previous but the comparator $u_t$ at each round can be perceived. For the former case, an $O((1+P_T)\\sqrt{E_T})$ bound is established, where $E_T$ is a data-dependent factor. As for the latter case, the authors achieve an $O((1+\\sqrt{P_T})\\sqrt{E_T} + A + \\min\\{P_T + E_T^\\prime\\})$ bound, where $A$ could be  $O((1+P_T)\\sqrt{E_T})$ at the worst case.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading the paper and providing feedback.\n\n**Claims \\& missing reference**.\nWe agree that it is important to discuss carefully Ahn et al. “Adam is FTRL in …”; we indeed cite this paper and mention that it uses an FTRL variant that attenuates history to obtain discounted regret bounds. That said, their paper also introduces a reduction from discounted to dynamic regret, which we did not discuss in detail in the current draft. Thanks for pointing this out. Here is a brief clarification:\n\n$\\bullet$ In the bounded domain setting, their bound is $P_T^{1/3} T^{2/3}$ (From their Corollary 3.4, assuming knowledge of $P_T$), which is suboptimal due to its super-$\\sqrt{T}$ dependence.\n\n$\\bullet$ In contrast, our bounds, which also assumes $P_T$ knowledge, achieve $\\sqrt{P_T T}$ in the worst case and further establish a refined  $\\sqrt{P_T E_T}$, which is data-dependent.\n\nThis is not a limitation of their work, but rather a natural outcome of their goal: explaining ADAM via FTRL.\n\nTo clarify this, we will:\n$(i)$ explicitly attribute the first *sublinear-in-T* dynamic regret bound for FTRL to Ahn et al. (2024), and\n$(ii)$ revise the sentence in our paper to read:\n“…As for FTRL, no dynamic regret guarantees, data-dependent or otherwise, *with $\\sqrt{T}$ rate* have been established ...” \n\nWe note that their Cor. 3.5 improves the bound to $\\sqrt{P_T T}$ but only in the unbounded setting.\n\n**Weakness 1\\&3**: Note that Theorems $3.1$,$3.2$, and $3.4$, do in fact hold for all comparators (i.e., without knowing $\\boldsymbol{u}_t$). This is because in Thm. $3.1$ and $3.4$, no information on $P_T$ is used (and the price is paid accordingly). As for Thm. $3.2$, knowing $P_T$ in advance *does not* necessarily mean that we know all the comparators, but rather that we compete with sequences whose path length is at most $P_T$. Here, we followed the standard notation from the literature, but indeed, a better notation would be fixing any $B$. Then, we compete with *any* sequence whose $P_T\\leq B$ to get $\\sqrt{BE_T}$. \n\nIt is only Thm. $3.3$ that assumes observability of $\\boldsymbol u_t$ online. Yet, these need not be the minimizers of each corresponding $f_t$ (i.e., not necessarily overfitting). \n\n**Weakness 2**: \nFor observable comparators, estimating $\\sqrt{E_T / P_T}$ online is infeasible due to non-monotonicity. Our data-dependent approach recovers the $\\sqrt{E_T P_T}$ bound when $\\sqrt{P_t/E_t}$ changes direction $O(\\sqrt{P_T})$ times (i.e., mostly monotone). The method performs no worse than tuning strategy $1$, while offering improvements when this structure is present. In all cases, the doubling trick of Jadbabaie et al. remains applicable.\n\n**Other comments**\nThanks for spotting the typos. For the def. of $A$, it is more convenient to keep it but update the proof accordingly to have $2R\\sigma A$ instead of $A/2$.\n\n**Questions**.\n\n**Dual perspective**. To provide a dual view, we look at the update step via the lens of dual maps. Recall the standard FTRL update: \n$\n\\boldsymbol x_{t+1}^{\\text {RL}} = \\arg\\min_x \\langle \\boldsymbol g_{1:t}, \\boldsymbol x\\rangle + r_{0:t}(\\boldsymbol x)\n=\\nabla r_{0:t}^*(-\\boldsymbol g_{1:t})$,  where $r_{0:t}^*(\\cdot)$ is the conjugate of the dual map $\\nabla r_{1:t}(\\cdot)$, restricted to $\\mathcal{X}$ via $r_0 = I_\\mathcal{X}$. From this viewpoint, FTRL maintains the state as cumulative gradients in dual space. \n\nIn contrast, the OMD update, as you noted, is expressed as: $\\boldsymbol x_{t+1}^{\\text{MD}} = \\nabla r_{0:t}^*(\\nabla r_{1:t-1}(\\boldsymbol x_t) - \\boldsymbol g_t)$. \n\nOur selective pruning update can be simply interpreted as:\n$\\boldsymbol x_{t+1} = \\arg\\min_x \\langle  \\boldsymbol p_{1:t}, \\boldsymbol x \\rangle + r_{0:t}(\\boldsymbol x) = \\nabla r_{0:t}^*(-\\boldsymbol p_{1:t}) = \\nabla r_{0:t}^*(\\nabla r_{1:t-k-1}(\\boldsymbol x_{t-k})-\\boldsymbol g_{t-k:t})$,\nwhere $k$ denotes the most recent step at which we chose to prune. The last equality holds by the definition of $\\boldsymbol g_k^{I}$ (assuming no predictions).\nIntuitively, we retain explicit gradient history only since the last pruning step $t-k$, while summarizing earlier history implicitly via the dual mapping of $\\boldsymbol{x}_{t-k}$. The crux of the paper is showing that the way history is split (explicitly tracked after pruning, and implicitly captured before) is what controls dynamic regret.\n\n**Guaranteeing** $\\sqrt{P_TE_T}, \\forall u_t$. One can ``modify\" OptFPRL with the second tuning strategy (that competes with comparators of at most $P_T$ switches); we can instantiate a set of $\\Theta(\\log T)$ sub-learners, each with a halving $\\sigma$ starting from $1/\\sqrt{T}$. Then, using the meta-learner of Zhao et al. (2020), the minimax bound can be recovered. The gist of this approach is that eventually $\\exists$ an expert $i$ such that $\\forall P_T, \\sigma^{(i)} \\geq 1/\\sqrt{P_T}\\geq 1/2\\sigma^{(i)}$. This will be added to the paper as part of the discussion.", "claims_and_evidence": "In Line 105, the authors claim \"As for FTRL, to the best of our knowledge, no dynamic regret guarantees, whether problem-dependent or not, have been established in the existing literature\". While in the paper  \"Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise\" published in ICML’24, this paper shows that dynamic bounds can be obtained through the FTRL framework by adding discounted factors to the losses. Conducting a more comprehensive survey and provide a more detailed comparison with the metioned approach is necessary.", "methods_and_evaluation_criteria": "The authors present a toy numerical experiment to support their findings, which is acceptable given that this paper primarily emphasizes the theoretical understanding of the FTRL framework.", "theoretical_claims": "I checked the key proof highlighted in the main text.", "experimental_designs_or_analyses": "I checked the experimental designs, which is acceptable to support their findings.", "relation_to_broader_scientific_literature": "The similar ideas of forgetting or pruning some information of the FTRL algorithm to derive dynamic regret bounds have been proposed by [Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise, ICML’24] through adding discounted factors to the losses. This paper considers an another approach by adding indicator functions to the loss functions.", "essential_references_not_discussed": "An essential reference missing from this paper is [Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise, ICML’24], which is the pioneering work to establish dynamic regret bounds under the FTRL framework.", "other_strengths_and_weaknesses": "Strengths:\n\n- The structure of this paper is well-organized and it is easy-to-follow.\n- This paper explores an interesting direction, as the relationship and differences between FTRL and OMD is crucial to realize two fundamental online learning algorithmic designs.\n\nWeakness:\n\n- The assumption of knowning $u_t$ at each round is too strong at least for me, and optimizing the exact values of $u_t$ may lead to overfitting to the online loss functions. \n- Theorem 3.3 is not optimal at the worst case, making it less competitive to existing results.\n- The obtained results are not guaranteed to hold for any comparators.\n\nOverall, this work presents interesting views to the FTRL framework. However, I believe it could be further refined by considering more general cases of dynamic regret bounds, which would help enhance its impact.", "other_comments_or_suggestions": "- Is $\\partial$ missed in Line 100 when recalling $g_t$?\n- Is the definition of V_T on line 109 missing a squared term?\n- There is a typo ($O(T)$) at the right column in Line 266.\n- I am confused about the definition of $A$ at the right column in Line 276. Are there any typos?", "questions_for_authors": "- Can the introduction of indicator functions be understood from a primal-dual perspective? From this viewpoint, OMD performs a non-projected update in the dual space and only applies projection when transitioning back to the primal space. Could a similar perspective be applied to FTRL?\n- Is it possible to modify the proposed algorithm so that it can guarantee dynamic regret bounds for arbitrary comparators?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "npN1nz4LIy", "reviewer": "Reviewer_oZgn", "summary": "This paper investigates the Follow-the-Regularized-Leader method (FTRL) under the Online Convex Optimization (OCO) framework for dynamic regret minimization. Specifically, the authors propose a series of FTRL-based methods, deliver novel analysis and establish new dynamic regret bound, which can recover existing known results. Overall, the topic is crucial for OCO community, and the theoretical guarantees are interesting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your review and feedback.\n\n**References**.\nWe selected Chen et al. (2024) from the SEA thread as it was the first to study SEA under the dynamic regret metric. That said, we will update the related work with the suggested background references (SEA \\& others) so as to better reflect the development of dynamic regret, and include a tabular summary of bounds.\n\n**Other comments**.\n\n$\\bullet$ Line 84: You are right, the discussion appears after Remark (8);  Remark (11) was from their conference version. We will correct this in the revision.\n\n**Questions**.\n\n$\\bullet$ Regarding the inequality, this should be just $\\beta\\leq1/2+\\beta/2$ to highlight that the $H_T \\doteq \\sum_t \\epsilon_t \\lVert \\boldsymbol u_t - \\boldsymbol u_{t+1} \\rVert$ term does not dominate the $\\sqrt{P_TE_T}$ term in worst case prediction error $E_T=c E'_T= O(T)$. Note that in light of the discussion with reviewer 2ZjR (in the Remark), we will update the remark by mentioning that $H_T$ is $\\mathcal{O}\\sqrt{P_TE_T}$ \n\n**Design choice**.\nBelow, we outline the rationale behind our pruning design from three complementary perspectives: preliminary intuition, analytical basis, and suggestive related work.\n\n$\\bullet$  *Intuition*. The pruning rule is motivated by the primal-dual view in online learning over compact sets. While primal iterates stay within the compact domain $\\mathcal{X}$, dual variables (e.g., cumulative gradients) can grow unbounded in $\\mathbb{R}^n$. If projections repeatedly return the iterate to the same region, why keep accumulating dual information that no longer influences decisions? Pruning addresses this by trimming dual history when appropriate. The pruning cone adds flexibility, enabling partial or delayed resets to control stale information in the dual space. Of course, choosing to prune at each time makes the update equivalent to OMD (see related work below).\n\n$\\bullet$ *Analytical basis*. If we wish to manipulate the update $\\boldsymbol{x}_t$ to offset accumulated gradients, the natural starting point is the linearization of $f_t(\\cdot)$, as it directly shapes the update. Ideally, we seek predictions $\\tilde f_t(\\cdot)$ whose subgradients can cancel or reduce the influence of past gradients. This is precisely what the pruning cone captures: it characterizes the directions in which the update can afford to remove history, and the composition with the indicator function formalizes this capability.\n\n$\\bullet$ *Related work*.\nAs discussed in the paper, a key inspiration comes from the equivalence between OMD and FTRL, first articulated in McMahan’s survey, for unbounded domains, and for bounded domains under fixed learning rates. This equivalence was further explored by Fang et al. (2022) [Online Mirror Descent and Dual Averaging…], who extended the analysis to time-adaptive learning rates. Both works focus on non-optimistic static regret. Additionally, the comprehensive work of Jacobsen \\& Cutkosky (2022) introduced the centered mirror descent family, capturing both lazy and greedy updates by composing the indicator with either their $\\psi_t$ or $\\varphi_t$ terms. This naturally raises the question of how varying this choice across time may influence the algorithm’s behavior, and what roles predictions play in this.", "claims_and_evidence": "Yes, there are experiments to verify the proposed theoretical results.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I review the overall proof framework, and its analysis follows some existing analytical tools.", "experimental_designs_or_analyses": "There are experimental studies in the appendix to support theoretical findings.", "relation_to_broader_scientific_literature": "This work bridges the gap between dynamic regret minimization and FTRL-based methods, a topic that has been explored in several related studies (Jacobsen & Cutkosky, 2022).", "essential_references_not_discussed": "This work primarily investigates dynamic regret optimization, a highly active topic in the online learning community. I suggest that the authors include the following studies in the related work section to better illustrate the development of dynamic regret optimization.\n\n* Optimal Dynamic Regret in Exp-Concave Online Learning. 2021.\n* Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond. 2022.\n* Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees. 2024.\n\nAdditionally, I noticed that the authors mention the SEA model but only discuss the work of Chen et al. (2024), overlooking other important milestones. I suggest that the authors incorporate discussions of the following works in their introduction about the SEA model.\n\n* Between stochastic and adversarial online convex optimization: Improved regret bounds via smoothness. 2022.\n* Online Composite Optimization Between Stochastic and Adversarial Environments. 2024.\n\nFinally, since the topic of this paper is highly significant, I suggest that the authors use a table to systematically compare previous works with the contributions of this paper.", "other_strengths_and_weaknesses": "**Strengths** \n\n* This paper is well-organized, clearly written, and easy to follow.\n* This paper presents an insightful understanding for the literature. The authors provide a comprehensive explanation on the motivation behind the proposed method.\n\n**Weakness** \n\n* See in the following parts.", "other_comments_or_suggestions": "* In Line 084, there appears to be a citation error. In Chen et al. (2024), Remark 11 does not seem to discuss dynamic regret optimization for FTRL-based methods.\n* In Line 181, typos: JC22 => Jacobsen & Cutkosky, 2022\n* In Line 265, typos: $E'_T=O(T^)$ => $E'_T=O(T)$\n\nBelow are some formatting suggestions:\n\n* I recommend avoiding the multiple use of footnotes.\n* The authors place the experimental section in the appendix. I suggest considering its inclusion in the main part instead.", "questions_for_authors": "* In Line 302, what is the meaning of $1+ \\beta - 1\\leq 1/2+\\beta/2$？In addition, I suggest explicitly stating that $P_T=O(T^{\\beta})$ at this point for clarity.\n* In my view, the construction of $g_t^I $ in (5) is crucial for the analysis. The authors could further elaborate on the motivation behind this design—whether it arises from analytical requirements or is inspired by existing works.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ijWxwbIdGX", "reviewer": "Reviewer_114P", "summary": "The paper presents a FTRL variant for dynamic regret with optimism in a compact domain. The paper relies on an adaptive correction $g_t^I$ to correct stored gradient states $\\sum_t g_t$, similar as an ``adaptive restart'' of FTRL whenever is desired. This general development yields to regret bound when path length $P_T$ is known or unknown a priori, which are mimax optimal. The bound also automatically recovers optimal static data dependent regret.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read the paper and providing the feedback\n\n**Weaknesses**.\nWe appreciate the reviewer’s recognition of the clarity of the FTRL-based analysis for dynamic comparators. We understand the concern regarding its broader impact, given that the minimax dynamic regret bounds are known and achieved by other algorithms. Our motivation for introducing a new FTRL variant and analyzing it in this setting is as follows:\n\n$\\bullet$ Flexible regularization. A key strength of FTRL is its ability to use general regularizers that can vary arbitrarily between iterations. For instance, proximal regularizers centered around different points in the domain allow the algorithm to incorporate prior knowledge about potentially good points, $\\boldsymbol{\\tilde{x}}_t$, as centers. This flexibility contrasts OMD, whose stability term is a scaled version of a fixed mirror map.\n\n$\\bullet$ Flexible pruning:\nOur framework supports flexible pruning, enabling algorithmic variants between lazy and greedy methods. To see this point perhaps more clearly, the reviewer is kindly invited to take a look at the *Dual interpretation* asked by reviewer ecer. \nWhile the framework of Jacobsen and Cutkosky (2022) could, in principle, do that, we present here FTRL-native theoretical insights (Lemmas $4.1$\\&$4.3$). These results provide explicit trade-offs and open avenues for adaptively choosing pruning frequency based on iterate-stability preferences.\n\n$\\bullet$ Further insights on OMD/FTRL connections. The importance of further understanding the FTRL framework was recently highlighted by Ahn et al. (2024), who showed that the widely used Adam optimizer is essentially a form of FTRL with an exponentially decaying dual-space state. This motivates revisiting FTRL with potential modifications to how it retains this state. We see our work as a contribution in this direction, identifying when and why FTRL fails under dynamic comparators, and proposing selective pruning as a principled solution. \n\nOverall, we note that when one departs from the original versions of FTRL and OMD, it is not difficult to create variants of one algorithm that resemble (in formulas or bounds) the other. Independent of naming and definitions, our work shows that pruning the history of gradients enables dynamic regret bounds with desirable properties. It also opens new directions for exploring interpolation between laziness and greediness, which lies at the core of this very interesting FTRL vs OMD discussion.\n\n**Other comments**. \n\n$\\bullet$ 395: it is indeed an inequality and not equality.\nThanks for pointing out the typo.", "claims_and_evidence": "Yes. \nThe paper claims investigating FTRL variants for dynamic regret, which is supported by their results in section 3.", "methods_and_evaluation_criteria": "The paper use classical regret as evaluation criterion.", "theoretical_claims": "main text was checked", "experimental_designs_or_analyses": "Included in appendix F, most case works well support the hypothesis of the need of FTRL based dynamic regret. The author was also very open to discuss the worst case and give explanation.", "relation_to_broader_scientific_literature": "As claimed, fill the gap of FTRL based data dependent dynamic regret.", "essential_references_not_discussed": "Well referenced.", "other_strengths_and_weaknesses": "Strength: The paper is well written and easy to follow. The remarks under each theorem are very helpful to compare results to previous literature.\n\nWeakness: It is in general questionable the need of FTRL based data dependent dynamic regret, as there are already other algorithms can achieve the same bound. Especially seeing the development in this paper are still fragile in scenario 5.", "other_comments_or_suggestions": "with potential typo in line 395, should be <=", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents techniques for employing the FTRL algorithm family to obtain dynamic regret, which is usually only obtained via mirror descent style algorithms. While the resulting regret bounds are not in of themselves new, the techniques may shed new light on the fundamental techniques used in deriving these bounds, and so will be of interest to the ICML community.
Decision: Accept (poster)