Strongly Adaptive Online Learning with Time-Varying Movement Costs

arXiv:2610.32740v1 [cs.LG] 23 Oct 2026

Strongly Adaptive Online Learning with Time-Varying Movement Costs

Andrew Jacobsen Università degli Studi di Milano Politecnico di Milano contact@andrew-jacobsen.com

Emmanuel Esposito Università degli Studi di Milano emmanuel@emmanuelesposito.it

Hao Qiu National University of Singapore qiuhaosai@gmail.com

Mengxiao Zhang University of Iowa mengxiao-zhang@uiowa.edu

Abstract We study strongly adaptive regret for Online Convex Optimization (OCO) with time-varying movement costs, a setting that evaluates a learner’s performance over arbitrary sub-intervals. This framework captures complex sequential decision-making problems where both the environment and the cost of switching decisions fluctuate over time. We propose a novel algorithm which, data-dependent regret bound of q for any intervalP[a, b] ⊆ [T ], achieves a  2 2 e O (D + DP[a,b] ) t∈[a,b] (∥gt ∥ + λt ∥gt ∥) , where D is the diameter of the decision domain, P[a,b] is the path length of the comparator sequence over [a, b], gt is the gradient of the loss, and λt is the movement-cost coefficient at round t. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of this development, we further establish the first strongly-adaptive guarantees under delayed feedback. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.

1

Introduction

Online convex optimization (OCO) [Cesa-Bianchi and Lugosi, 2006, Hazan, 2016, Orabona, 2019] is a fundamental framework for sequential decision making under uncertainty. At each round, a learner selects a decision wt in a convex decision set W before observing the current loss function ft : W → R, and then incurring the corresponding loss ft (wt ). The objective is to design algorithms whose cumulative loss is close to that of a benchmark comparator sequence chosen in hindsight. Classic (static) regret guarantees compare the learner’s performance against a single fixed comparator over the entire time horizon, and are therefore most appropriate in stationary environments. However, many modern applications are inherently non-stationary: the best decision may evolve over time, the environment may undergo abrupt shifts, and the performance on short or intermediate time intervals can be just as important as performance over the full horizon. Several regret notions have been developed to capture such non-stationarity settings. Dynamic regret [Zinkevich, 2003, Zhang et al., 2018] takes a global perspective by comparing the learner against a PT time-varying comparator sequence over the entire horizon, RT (u1:T ) ≜ t=1 ft (wt ) − ft (ut ). This allows the benchmark to change over time and provides a natural way to quantify performance in drifting environments. By contrast, strongly-adaptive regret [Daniely et al., 2015] requires the learner 40th Conference on Neural Information Processing Systems (NeurIPS 2026).

to achieve low static regret simultaneously on every contiguous time interval. Rather than focusing only on aggregated performance, strongly adaptive regret P measures how well the learner adapts locally to changes at arbitrary time scales: R[a,b] (u) ≜ t∈[a,b] ft (wt ) − ft (u). More generally, Zhang et al. [2020] extends this definition to studyP simultaneous dynamic regret and strongly-adaptive regret minimization, and defines R[a,b] (ua:b ) ≜ t∈[a,b] ft (wt ) − ft (ut ), which captures both the classic definition of strongly-adaptive regret as well as dynamic regret as a special case. Another crucial challenge in OCO is that changing decisions can itself be costly. For example, in optimal control [Goel and Wierman, 2019], video streaming [Joseph and de Veciana, 2012], and geographical load balancing [Lin et al., 2012], frequent changes may incur switching costs, transaction costs, or instability penalties, and these costs themselves may vary in time. This motivates OCO with time-varying movement costs, where the learner is charged not only the loss but also a time-varying movement penalty associated with the decision. This raises the following question: Can we design algorithms for OCO with time-varying movement costs that achieve strongly adaptive regret against arbitrary time-varying comparator sequences? Contributions. In this paper, we answer this question affirmatively by developing the first stronglyadaptive algorithms for OCO with time-varying movement costs. Our main technical ingredient is a reduction that decomposes the regret of a mixture predictor into two components: the movement-cost regret of a base expert and the movement-cost regret of a meta-algorithm for the sleeping experts problem. This reduction allows us to combine interval-based specialists with a new algorithm forq sleeping experts with movement costs, yielding strongly adaptive regret bounds of the form  P 2 2 e O (D + DP[a,b] ) t∈[a,b] (∥gt ∥ + λt ∥gt ∥) simultaneously over every interval [a, b], where D is the diameter of the feasible domain, P[a,b] is the drift of the comparator within interval [a, b], and gt and λt are the gradient and the movement cost coefficient respectively at round t. Our result improves upon the state-of-the-art work studying time-varying movement costs [Qiu et al., 2026], which obtains only dynamic regret guarantees, while our work obtains strongly-adaptive and dynamic regret guarantees simultaneously. Moreover, even when specialized to the case of a fixed movement cost and a fixed comparator sequence, our results improve upon the best-known guarantees from prior work in this setting (see Section 4 for a detailed discussion). Similar to Qiu et al. [2026], we further demonstrate that OCO with movement costs provides a useful primitive for handling delayed feedback in strongly-adaptive online learning. The key observation is that the number of missing gradients at each round can be viewed as a time-varying movementcost scale, which allows OCO with delayed feedback to be reduced to the movement-cost setting. Leveraging a refined version of this reduction for interval regret, we obtain the first strongly adaptive  q
 e G (D2 + DP[a,b] ) |b − a| + d[a,b] regret bound of O for OCO with delayed feedback, where tot [a,b]

dtot is the total cumulative delay restricted to interval [a, b]. While existing studies of delayed feedback have mainly only focused on dynamic regret [Wan et al., 2024, Qiu et al., 2026], our result establishes simultaneous strongly-adaptive and dynamic regret guarantees for delayed feedback. We also extend our reduction to online learning with time-varying memory, showing that memorydependent losses can be handled through the same movement-cost perspective even when memory lengths change arbitrarily over time. In particular, we obtain a strongly adaptive regret bound of  r P [a,b]
2 [a,b] e O (D2 + DP[a,b] ) H 2 |b − a| + HG t∈[a,b] bt where bt = min {bt , t − a} is the interval-clipped memory length, G is the coordinate-wise Lipschitz constant, and H bounds the gradient norm of the unary losses. While existing studies of OCO with memory have mainly focused on dynamic regret [Zhao et al., 2023, Qiu et al., 2026], our result simultaneously provides strongly adaptive and dynamic regret guarantees for OCO with memory. Related work. Our work is closely related to three primary lines of research: (i) dynamic and adaptive regret, (ii) OCO with movement costs, and (iii) OCO with delayed feedback. As fundamental performance measures for non-stationary environments, dynamic and adaptive regret have been extensively studied. However, in the presence of movement costs, existing work typically achieves either dynamic or strongly adaptive regret, but rarely address complex time-varying scenarios with strongly adaptive guarantees. Specifically, Zhang et al. [2022] study strongly adaptive regret restricted 2

to fixed movement costs, while Zhang et al. [2021a], Mhaisen and Iosifidis [2026], and Qiu et al. [2026] focus exclusively on dynamic regret for fixed and time-varying movement costs, respectively. Beyond movement costs, delayed feedback presents another major challenge in non-stationary OCO. Wan et al. [2024] establish dynamic regret guarantees under delays. Subsequently, Qiu et al. [2026] proposed the first reduction from movement costs to delayed feedback, and a related idea was concurrently developed by Ryabchenko et al. [2026] in the context of bandit feedback. Relatedly, OCO with movement costs also extends to OCO with memory, a setting where prior works [Zhao et al., 2023, Qiu et al., 2026] have again focused on dynamic regret for both fixed and time-varying memory lengths. Due to the space limitations, we defer additional related work to Appendix A. Notations. Throughout the paper, we use Z+ to denote the set of positive integers and [m] ≜ {1, . . . , m} for any m ∈ Z+ . By a slight abuse of notation, we often refer to a time interval between rounds a, b ∈ Z+ with a ≤ b as [a, b] = {a, . . . , b}, which contains only the integer values between a and b. We denote the subdifferential set of a convex function f : W → R at some point w ∈ W as ∂f (w). We write 0 for the all-zero vector in the appropriate dimension, 1 {x ∈ A} denotes the indicator function for a set A, and we use ∥ · ∥ to denote the Euclidean norm unless otherwise specified. The ℓ1 norm is denoted ∥ · ∥1 . For two vectors u, v ∈ Rd , denote the coordinatewise product as u ⊙ v, whose i-th coordinate is ui vi . For a finite set S, we use |S| to denote the cardinality of S. The Bregman divergence with respect to a differentiable function ψ : W → R is Dψ (x | y) ≜ ψ(x) − ψ(y) − ⟨∇ψ(y), x − y⟩. Define ∆N −1 as the N -dimensional probability e to suppress simplex, and we denote ∆S for the probability simplex over a finite set S. We use O(·) b all log(·) terms and use O(·) to suppress only constant and log log(·) terms.

2

Problem Setting

We study online convex optimization with time-varying movement costs over a nonempty, closed, convex decision set W ⊆ Rd . We assume throughout that the domain is bounded with diameter D = supx,y∈W ∥x − y∥, and we assume without loss of generality that 0 ∈ W. The interaction between the learner and the environment lasts for T ∈ Z+ rounds. On each round t ∈ [T ], the learner chooses a decision wt ∈ W, then the environment selects a convex loss function ft : W → R, and the learner incurs a cost of ft (wt ) + λt ∥wt − wt−1 ∥. At the end of the same round t, the learner observes a subgradient gt ∈ ∂ft (wt ) and the next movement-cost coefficient λt+1 . For every (nonempty) time interval [a, b] ⊆ [T ], we measure performance by the movement-cost dynamic regret: R[a,b] (ua:b , λa:b ) ≜

X

(ft (wt ) − ft (ut )) +

b X

λt ∥wt − wt−1 ∥ ,

t=a+1

t∈[a,b]

where ua:b = (ua , . . . , ub ) is any comparator sequence in W. For ease of notation, when the interval is / [a + 1, b] so that we may write Pclear from context we will typically P define λt = 0 for t ∈ λ ∥w − w ∥, or simply λ ∥w − w ∥. Similarly, for notational convenience we t t t−1 t t t−1 t∈[a,b] t define pre-interval iterates wa−1 = wa and ua−1 = ua wherever relevant. Pb For a comparator sequence ua:b , we define its path length over [a, b] as P[a,b] ≜ t=a+1 ∥ut −ut−1 ∥. [a,b]

For any time interval [a, b], define λmax ≜ maxt∈[a,b] λt , as the largest movement-cost coefficient over [a, b]. This one-sided movement-cost regret follows the stronger objective considered in prior works on OCO with movement costs [Zhao et al., 2023]. In contrast, a symmetric notion of dynamic regret would also charge the comparator for its movement. More precisely, if we define X h

i R[a,b] (ua:b , λa:b ) ≜ ft (wt ) + λt ∥wt − wt−1 ∥ − ft (ut ) + λt ∥ut − ut−1 ∥ , t∈[a,b]

then it clearly holds that R[a,b] (ua:b , λa:b ) ≤ R[a,b] (ua:b , λa:b ) ≤ R[a,b] (ua:b , λa:b ) + λ[a,b] max P[a,b] . Therefore, controlling the one-sided regret R[a,b] (ua:b , λa:b ) immediately implies a guarantee for the symmetric regret as well, so we will focus on controlling the stronger one-sided regret R[a,b] (ua:b , λa:b ). Throughout this work we will also make the following standard assumptions. 3

Assumption 2.1. (Boundedness) Given G, λ, D > 0, the movement coefficients satisfy λt ∈ [0, λ], the domain W satisfies supx,y∈W ∥x − y∥ ≤ D, and the convex loss functions f1 , . . . , fT : W → R are G-Lipschitz, i.e., each ft satisfies |ft (x) − ft (y)| ≤ G∥x − y∥ for all x, y ∈ W. Throughout the paper, we assume for simplicity that the bound on the movement coefficients λ ≥ λt is known a priori, though in practice this factor can be estimated up to a constant factor using a standard doubling argument.

3

Strong Adaptivity with Time-Varying Movement Costs

In this section, we introduce a general algorithm for obtaining strongly adaptive regret guarantees with time-varying movement costs. At a high level, our approach is a reduction to sleeping experts with movement costs and is based on a meta-base algorithm design. Each base learner is responsible for one interval in a geometric covering of the entire time horizon, and the meta-algorithm assigns weights over the currently active base learners. Specifically, we decompose the movement-cost regret of the final predictor into two parts: the regret of a base learner, which includes the movement cost incurred by that base learner, and the regret of the meta-algorithm, which includes the movement cost of changing the meta-algorithm’s weights. This decomposition allows us to treat the meta-level problem as a sleeping-experts problem with its own movement costs. We proceed in three steps. First, we introduce a general reduction from the strongly adaptive regret for OCO with time-varying movement costs to a meta-base regret decomposition of sleeping experts. Then, in Section 3.1, we design and analyze the required meta-algorithm for sleeping experts with movement costs. Finally, in Section 4, we combine this meta-algorithm with interval-specific base learners and a first-order adaptive-blocking reduction to obtain our strongly adaptive regret guarantee. We begin by adapting the standard meta-base decomposition to the case of time-varying movement costs. Suppose that on round t the meta-algorithm outputs a distribution pt ∈ ∆N −1 over N (i) experts, and each expert i ∈ [N ] outputs a decision wt ∈ W. The learner then plays the convex P (i) combination wt ≜ i∈[N ] pt,i wt . The following lemma shows that the regret of this mixture predictor decomposes into a base regret term and a meta-regret term. The meta-loss vector contains not only the linearized loss of each expert, but also a one-step-ahead movement term for that expert. This one-step shift is what allows the movement cost of the mixture predictor to be assigned cleanly between the base and meta levels. P (i) Lemma 3.1. Let Assumption 2.1 hold. Suppose on each round t ∈ [T ] we play wt = i∈[N ] pt,i wt , (i)

where wt ∈ W is the output of expert Ai on round t and pt ∈ ∆N −1 is the output of a metaalgorithm AMeta . Then for any i ∈ [N ] and any sequence u1 , . . . , uT ∈ W, RT (u1:T , λ1:T ) ≤

T D T E X X (i) (i) (i) gt , wt − ut + λt ∥wt − wt−1 ∥ + ⟨ℓt , pt − ei ⟩ + Dλt ∥pt − pt−1 ∥1 , t=1

|

t=1

{z

}

A =:RT i (u1:T ,λ1:T )

|

{z

Meta (e ,λMeta ) =:RT i 1:T

}

where gt ∈D∂ft (wt ),EλMeta = Dλt , and the surrogate loss vector ℓt ∈ RN is defined coordinate-wise t (j) (j) (j) by ℓt,j := gt , wt + λt ∥wt − wt−1 ∥, ∀j ∈ [N ]. The full proof is deferred to Appendix B.1. Note that in comparison to the regret decomposition in Qiu et al. [2026]—which aggregates decisions by summing the outputs of various experts and hence requires comparator-adaptive base algorithms in unconstrained domains—our framework is designed for the more general constrained setting with arbitrary base algorithms Ai . In other words, our regret decomposition also applies to arbitrary convex feasible sets, ensuring that the learner’s decisions remain valid. While this result is fairly simple, we believe that this decomposition is already of independent interest: it is relatively straight-forward to derive guarantees matching the ones derived in Qiu et al. [2026] but in constrained settings using this decomposition, which was not possible using their aggregation-via-iterate-adding approach. To obtain strongly-adaptive guarantees, we further extend Lemma 3.1 to the sleeping-experts setting with movement costs. We instantiate the experts as interval specialists, where each expert Ai is active 4

only on a prescribed interval, and the meta-algorithm is required to compete with any active expert on that interval. Let α ∈ {0, 1}T ×N denote the activation matrix, where αt,i = 1 if expert Ai is active on round t and αt,i = 0 otherwise. For any comparator distribution u ∈ ∆N −1 over experts, we define the sleeping-experts regret with movement costs, with respect to the activation matrix α, as T X X
RTα (u, λ1:T ) ≜ αt,i ui ⟨ℓt , pt ⟩ − ℓt,i + λt ∥pt − pt−1 ∥1 . (1) t=1 i∈[N ]

The next lemma shows that the meta-base decomposition yields an interval guarantee whenever the competing expert is active on that interval. Lemma 3.2. Under the same assumptions as Lemma 3.1, let [a, b] ⊆ [T ] and let the active rounds of Ai coincide with interval [a, b], i.e., αt,i = 1 {t ∈ [a, b]} for all t ∈ [T ]. Then for any sequence ua:b = (ua , . . . , ub ) over W, Ai R[a,b] (ua:b , λa:b ) ≤ RTα (ei , λMeta 1:T ) + R[a,b] (ua:b , λa:b ) . The proof is deferred to Appendix B.2. This lemma reduces the problem of strong adaptivity to two separate tasks: designing a sleeping-experts meta-algorithm and developing robust base learners for intervals, both of which incorporate movement costs. We address the meta-algorithm design first in Section 3.1. 3.1

Sleeping Experts with Movement Costs

Using the specialists reduction from Lemma 3.2, we know we can obtain strongly-adaptive guarantees for movement-cost regret if we can control the movement-cost sleeping-experts regret RTα (u, λ1:T ) defined in Equation (1). In particular, observe that if we can obtain an adaptive bound of the form   X sX 2 e RTα (u, λ1:T ) = O ui αti (⟨ℓt , ei − pt ⟩ + λ2t ) , (2) i∈[N ]

t∈[T ]

then given a specialist AI defined only on the interval I =q [a, b], the meta-regret will automatically  P 2 α 2 e restrict to that same interval—that is, RT (eI , λ1:T ) = O t∈[T ] αt,I (⟨ℓt , ei − pt ⟩ + λt ) ≤ qP  2 2 e O t∈[a,b] ⟨ℓt , ei − pt ⟩ + λt , so that the specialists decomposition in Lemma 3.2 leads to p e |b − a|) regret overall. Our approach leverages a reduction to OLO similar to Jun et al. [2017], O( but our approach differs from theirs as we are able leverage FTRL-based arguments similar to Jacobsen and Cutkosky [2022] rather than challenging betting arguments; this is a key distinction, as it is not obvious how to extend the betting-based approach of Jun et al. [2017] to incorporate adaptive b t+1,i . movement costs or coordinate-wise Lipschitz hints L The required adaptive sleeping-experts algorithm that is also robust to movement costs is provided by Algorithm 1. One can show that it does indeed guarantee a regret bound as stated in Theorem 3.3 below. Theorem 3.3. Suppose that ∥ℓt ∥∞ ≤ G∞ and λt ≤ λ for all t. Then for any u ∈ ∆N −1 , Algorithm 1 with L = 2G∞ + 5λ guarantees v  √ !   X u uX ui VTλ+1,i α 2 2 e RT (u, λ1:T ) ≤ O Γ(ϵ) + ui t αti (ℓti − ⟨ℓt , pt ⟩) + λt log +1 , ϵi L i∈[N ]

where Γ(ϵ) = L 1 +

P

i ϵi

t∈[T ]

.

Proof and full statement of the bound can be found in Appendix C.1. The guarantee matches the desired bound in Equation (2) and it is, to our knowledge, the first second-order regret guarantee for sleeping experts, and further handles time-varying movement costs while adapting to the corresponding coefficients λt . Our bound can be seen as a generalization of the one obtained by the CBCE b t+1 , algorithm of Jun et al. [2017] to account for movement costs, leverage Lipschitz-bound hints L and achieve data-adaptive logarithmic penalties. In fact, as we show in Appendix C.2, our bound is qP  2 e somewhat stronger than the more familiar O ti ui ⟨ℓt , ei − pt ⟩ (KL(u|ϵ) + 1) bound of Jun et al. [2017], as our result can be shown to imply this bound via Cauchy-Schwarz inequality. 5

Algorithm 1 Adaptive Sleeping Experts with Movement Costs Input: L > 0, value ϵi > 0, ∀i ∈ [N ], activation map t 7→ αt,i supported on [ai , bi ] for each i ∈ [N ] Initialize: z1 = 0 ∈ RN i h Rz + ηV dx Define: ψ(z; V, β) = 3 0 min0<η≤1/L log(x/β+1) η for t = 1, . . . , T do ⊙αt Play pt = ∥zztt⊙α if ∥zt ⊙ αt ∥1 ̸= 0 and pt = ∥ααtt∥1 otherwise t ∥1 Observe loss vector ℓt ∈ RN , movement coefficient λt+1 ≥ 0 for i = 1, . . . , N do Define ℓλti = αti (⟨ℓt , ei − pt ⟩ − λt ∥pt − pt−1 ∥1 ) + αti (1 − αt+1,i )2λt+1 , ∀i ∈ [N ] Pt (i) (i) λ Set λt+1 = 2αti αt+1,i λt+1 , Vt+1,i = 4L2 + τ =1 (|ℓλti | + λt+1 )2 , ϵi L and βt+1,i = √ λ , ∀i ∈ [N ] λ Vt+1,i log2 (Vt+1,i /L2 )  i hP t λ λ z + ψ(z ; V , β ) ℓ Update zt+1,i = arg minz∈[0,1] i i t+1,i t+1,i s=1 si

4

Main Result

In this section we present the mainresult a strongly-adaptive algorithm  for movementq of the paper: P 2 2 e cost dynamic regret achieving O (D + DP[a,b] ) t∈[a,b] (∥gt ∥ + λt ∥gt ∥) regret for every time interval [a, b] ⊆ [T ] simultaneously. We first introduce one additional reduction. A direct application of Theorem 3.3 P in the context of the specialists reduction in Lemma 3.2 naturally leads to boundsP depending on t (∥gt ∥2 + λ2t ). For time-varying movement costs, the sharper quantity is instead t (∥gt ∥2 + λt ∥gt ∥), which can always be bounded in terms of the former quantity via AM-GM inequality, but can be significantly tighter when ∥gt ∥ ≪ λt on average, meaning cases where the learner’s actions eventually become sufficiently close to being optimal while movements tend to be quite expensive. Moreover, as shown by Qiu et al. [2026], obtaining the first-order dependence on a time-varying sequence of λt is crucial for obtaining optimal guarantees in the delayed feedback setting, which we later discuss in Section 5.1. To obtain this dependence, we use an adaptive first-order blocking strategy inspired by the approach of Qiu et al. [2026] and provided in Algorithm 5. The algorithm groups consecutive rounds into epochs and passes the aggregate gradientPof each completed epochP to the base learner. Note that the blocking condition we use is based on t ∥gt ∥ rather than the ∥ t gt ∥ used by Qiu et al. [2026]. This is crucial in the strongly-adaptive setting because P an arbitrary interval [a, b] may begin or end in the middle of an epoch, and the non-monotonic ∥ t gt ∥ condition makes it difficult to ensure that these partial epochs do not ruin the bound. The following lemma formalizes the key property of this blocking reduction needed in the main analysis. It shows that the regret on an arbitrary interval can be reduced to regret over the full epochs contained in that interval, up to a lower-order boundary term. The proof of this lemma can be found in Appendix F . Lemma 4.1. Let Assumption 2.1 hold. Let (Iτ )τ be the set of intervals defined during the execution of the blocking reduction (Algorithm 5), and let E[a,b] = {τ : Iτ ⊆ [a, b]} denote the set of complete epochs contained within [a, b]. For any comparator sequence (ut )t∈[a,b] in W, Algorithm 5 with any base algorithm A guarantees that X eτ ∥w R[a,b] (ua:b , λa:b ) ≤ 3(D + P[a,b] )(G + λ[a,b] ⟨e gτ , w eτ − u eτ ⟩ + λ eτ − w eτ −1 ∥. max ) + τ ∈E[a,b]

where u eτ ∈ arg minu∈{ut :t∈Iτ } ∥u∥ is any minimum-norm comparator in epoch τ ∈ E[a,b] , w eτ eτ are respectively the action played by A and the movement coefficient in epoch τ , and and λ P geτ = t∈Iτ gt with gt ∈ ∂ft (wt ) for all t ∈ [T ]. Now applying this reduction on top of the specialists reduction in Section 3 with the sleeping-experts algorithm of Section 3.1, we are ready to derive the main result. We proceed by constructing a set of experts {AI : I ∈ I} such that AI is active only on interval I ∈ I, where I is the standard set of 6

Algorithm 2 Strongly-Adaptive Online Learning with Time-varying Movement Costs Input: values L > 0, Geometric covering intervals I, algorithm AI for each I ∈ I, meta-algorithm AMeta defined on ∆I with parameters ϵI for each I ∈ I 1 Initialize: Initialize A[a,b] and initialize AMeta with ϵ[a,b] = a2 (1+⌊log for each [a, b] ∈ I, 2 a⌋) e τ = 1, λτ = 0, w eτ = 0, geτ = 0, Hτ = 0, α eτ = (ατ,I )I∈I , sτ = 1 for t = 1, 2, . . . do Play wt = w eτ , observe gt ∈ ∂ft (wt ) and λt+1 Update geτ ← geτ + gt and Hτ ← Hτ + ∥gt ∥ if Hτ > λt+1 then eτ +1 = λt+1 , α Set λ eτ +1 = (αt+1,I )I∈I , sτ +1 = t + 1 eτ +1 ) to AI and retrieve w(I) for each I ∈ Active(t) ∩ Active(sτ ) Send (e gτ , λ t+1 D E  (I) (I) (I) eτ +1 ) to AMeta where ℓeτ,I = α eτ ∥w Send (ℓeτ , Dλ eτ,I geτ , w eτ +λ eτ − w eτ −1 ∥ P (I) Update w eτ +1 = I∈I pτ +1,I wτ +1 , Hτ +1 = 0, geτ +1 = 0, and τ ← τ + 1

geometric covering intervals [Daniely et al., 2015]: [  k I= [i2 , (i + 1)2k − 1] : i = 1, 2, . . .

.

k∈{0,1,...}

The set of active intervals at time t is then Active(t) = {I ∈ I : t ∈ I}, and we will set αt,I = 1 {I ∈ Active(t)} as the activation indicator. For our purposes here, it is sufficient to take each AI to be an instance of adaptive (sub)-gradient descent applied on interval I (see Appendix E). Note that an expert is updated only if they are active and were also active at the start of the epoch; this avoids contaminating the feedback of an expert A[a,b] with feedback from outside [a, b]. Composing these results leads to the design of Algorithm 2 with the following strongly-adaptive guarantee. Theorem 4.2. Let Assumption 2.1 hold and let L = D(2G + 9λ). Algorithm 2 applied with base algorithms AI implementing Algorithm 4 and AMeta implementing Algorithm 1 guarantees, for any [a, b] ⊆ [T ], any ua , . . . , ub ∈ W, and any λa , . . . , λb ∈ [0, λ], that b (D + P[a,b] ) log2 (b)(G + λ) R[a,b] (ua:b , λa:b ) ≤ O (

)! q q λ 2 2 2 + min (D + DP[a,b] )(G + Gλ)|b − a| log(b), (D + DP[a,b] )V[a,b] log(b) , λ where V[a,b] =

P

t∈[a,b] (∥gt ∥

2

+ λt ∥gt ∥) and P[a,b] =

Pb

t=a+1 ∥ut − ut−1 ∥.

The proof of Theorem 4.2 can be found in Appendix G. Observe that the bound achieves the minimum of two similar terms, one involving a worst-case penalty scaling with the interval length P λ |b − a| and one involving a data-adaptive penalty V[a,b] = t∈[a,b] (∥gt ∥2 + λt ∥gt ∥). The worstcase p bound recovers the best-known
strongly-adaptive static and dynamic guarantees of order O G (D2 + DP[a,b] )|b − a| log(b) in the standard OCO setting where the movement coefficients are λt = 0 for all t [Jun et al., 2017, Zhang et al., 2021b]. Moreover, when movement penalties are present our bound improves upon the bound of Zhang etp al. [2022], which incurs a sub-optimal penalty of log(b) rather than the best-known dependency of log(b). q  P On the other hand, our adaptive bound O (D2 + DP[a,b] ) t∈[a,b] ∥gt ∥2 + λt ∥gt ∥ log(b) extends the best-known data-adaptive bound achieved in Qiu et al. [2026] to hold on every sub-interval, p but incurs an additional log(b) penalty over the non-adaptive guarantee. Despite this, our bound still improves upon the state-of-the-art strongly-adaptive Zhang et al. [2022] achieves an interq bound:  P e val static regret guarantee of R[a,b] (u, λa:b ) ≤ O λ ∨ G [a,b] ∥gt ∥ log (b) , which our bound is a strict improvement of even for a fixed comparator. Our bound is further adaptive to a time-varying sequence of movement coefficients, and obtains optimal dynamic regret guarantees on any [a, b], both of which are non-trivial to achieve using the framework of Zhang et al. [2022]. 7

5

Applications

In this section, we derive strongly adaptive regret guarantees for two further problem settings: OCO with delayed feedback and OCO with time-varying memory. These results are obtained via extended reductions of the respective problems to OCO with time-varying movement costs, and generalize the reductions of Qiu et al. [2026] to hold on arbitrary sub-intervals. 5.1

Strongly Adaptive Regret with Delayed Feedback

We first study strongly adaptive regret for OCO with delayed feedback. The online protocol proceeds as follows. On each round t ∈ [T ], the learner chooses a decision wt ∈ W, while the environment simultaneously selects a convex loss function ft : W → R. The learner then suffers loss ft (wt ). In contrast to the standard OCO setting, however, the gradient gt ∈ ∂ft (wt ) is not necessarily observed immediately. Instead, it is revealed only at the end of round t + dt , where dt ≥ 0 denotes an arbitrary delay that is unknown to the learner. Without loss of generality, we assume that t + dt ≤ T for every t ∈ [T ], so that all feedback is received by the end of the time horizon. The learner’s performance on an interval
[a, b] ⊆ [T ] is measured by the strongly adaptive regret P del R[a,b] (ua:b ) = t∈[a,b] ft (wt ) − ft (ut ) , where ua:b = (ua , . . . , ub ) is any comparator sequence in this interval. We use the superscript “del” to emphasize that the regret is evaluated in the OCO setting with delayed feedback. For each round t, let ot ≜ {τ ∈ Z+ : τ + dτ < t} ⊆ [t − 1] denote the set of past rounds whose gradients have already been observed before round t. We further define mt ≜ [t − 1] \ ot as the set of past rounds whose gradients are still outstanding before round t, and define σ = maxt |mt |. With this setup, the delayed-feedback protocol can be equivalently described by saying that, at the end of round t, the learner receives the batch of newly available gradients {gτ }τ ∈ot+1 \ot . The following lemma in fact shows that the regret on any time interval [a, b] under delayed feedback can be bound P in terms of the undelayed movement-cost regret against the batch losses geτ = t∈Iτ gt . Lemma 5.1. Let Assumption 2.1 hold and let [a, b] ⊆ [T ] be any interval. Then del R[a,b] (ua:b ) ≤ G(2D + P[a,b] )σ +

b X

⟨ht , wt − ut ⟩ +

t=a

where ht =

b X

λt ∥wt − wt−1 ∥,

t=a+1

P

τ ∈ot+1 \ot gτ and λt = G|mt |.

The result generalizes the analogous reduction from Qiu et al. [2026] to hold on an arbitrary subinterval [a, b], and requires additional care to handle boundary conditions unique to the stronglyadaptive setting. A direct application of Theorem 4.2 then leads to the following guarantee for the delayed feedback setting. Theorem 5.2. Let Assumption 2.1 hold and let H ≥ G(σ + 1) and P let λ ≥ Gσ. Initializing Algorithm 2 with L = D(2H + 9λ), and feeding it gradients ht = τ ∈ot+1 \ot gτ and movement coefficients λt = G|mt |, guarantees that for any [a, b] ⊆ [T ] and any ua , . . . , ub ∈ W that   q
del e (D + P[a,b] )Lσ,a + G (D2 + DP[a,b] ) |b − a| + d[a,b] R[a,b] (ua:b ) ≤ O , tot [1,a−1]

where Lσ,a = H ∨ G σ + dmax

and P[a,b] =

Pb

t=a+1 ∥ut − ut−1 ∥.

The proofs of both Lemma 5.1 and Theorem 5.2 can be found in Appendix H.1. To the best of our knowledge, Theorem 5.2 yields the first guarantees under q strongly adaptive regret and dynamic [a,b]
2 delayed feedback. The dominant term G (D + DP[a,b] ) |b − a| + dtot has the standard delay[a,b]

dependent form, with |b − a| corresponding to the length of the interval and dtot measuring the total delay restricted to that interval. In the absence of delays, this recovers the standard strongly-adaptive
p Pb [a,b] e G (D2 + DP[a,b] )|b − a| . Here, d[a,b] and dynamic guarantees O denotes the tot = t=a dt [a,b]

interval-restricted total delay, where dt = min{dt , b − t} clips each delay at the endpoint b. Thus, Pb [a,b] dtot ≤ t=a dt , and the strongly adaptive bound depends only on the delay mass relevant to the 8

interval [a, b].qBy contrast, Wan et al. [2024] and Qiu et al. [2026] only obtain a dynamic regret 

 PT e bound of O D2 + DPT T + dt , which is not strongly adaptive over every interval t=1

[a, b] ⊆ [T ]. Remark 5.3. The result in Theorem 5.2 requires prior knowledge of λ ≥ Gσ = G maxt |mt |, which may not be known in practice. However, this parameter can be estimated up to a constant factor using the standard doubling argument discussed in Section 2, applied after the delays-to-movement-costs reduction (Lemma 5.1). 5.2

Strongly Adaptive Regret with Time-Varying Memory

In this section, we establish strongly adaptive regret guarantees for OCO with time-varying memory. The interaction follows the standard T -round protocol. In each round t, the learner chooses a decision wt ∈ W. At the same time, the environment selects a loss function ft : W bt +1 → R, which depends on the current decision together with the preceding bt decisions, where bt ∈ {0, . . . , t − 1} denotes the memory length at round t. We assume that the full sequence of memory lengths {bt }Tt=1 is known to the learner in advance, and define the maximum memory length by B ≜ maxt bt . The learner then suffers the loss ft (wt−bt :t ), where wt−bt :t ≜ (wt−bt , . . . , wt ), and subsequently observes the entire loss function ft . The learner aims to minimize strongly adaptive regret against an arbitrary comparator sequence over any interval. This regret is defined as
P mem R[a,b] (u1:T ) ≜ t∈[a,b] ft (wt−bt :t ) − ft (ut−bt :t ) for any interval [a, b] ⊆ [T ]; note that it takes the entire comparator sequence u1:T as argument since the loss at some round might depend on points relative to rounds before the start of the interval. [a,b]

≜ min{bt , t − a}. For an interval [a, b], we also define the clipped memory length at round t by bt [a,b] Thus, bt counts only the portion of the memory window that lies within the interval [a, b]. We also define the maximum original memory length over [a, b] as B[a,b] ≜ maxt∈[a,b] bt , and the maximum [a,b]

[a,b]

clipped memory length on [a, b] as bmax ≜ maxt∈[a,b] bt

[a,b]

. By definition, bmax ≤ B[a,b] .

Following Anava et al. [2015], Zhao et al. [2023], we place the following structural assumptions on the loss functions: we assume that the losses are coordinate-wise Lipschitz, and that the induced unary losses fbt (w) ≜ ft (w, . . . , w) are convex and H-Lipschitz. Assumption 5.4 (Coordinate-wise Lipschitzness). For every t ∈ [T ], the loss function ft is coordinate-wise G-Lipschitz for some G ≥ 0. That is, for any x = (x0 , x1 , . . . , xbt ) and Pbt y = (y0 , y1 , . . . , ybt ) in W bt +1 , |ft (x0 , . . . , xbt ) − ft (y0 , . . . , ybt )| ≤ G i=0 ∥xi − yi ∥ . Assumption 5.5 (Properties of unary losses). The induced unary loss fbt is convex. Moreover, the gradients of the unary losses are uniformly bounded: there exists H > 0 such that supw∈W ∥∇fbt (w)∥ ≤ H for all t ∈ [T ]. Note that by Assumption 5.4, we may assume without loss of generality that H ≤ G(B + 1). The following lemma reduces regret on any interval to an instance of OCO with time-varying movement costs plus some additive lower-order terms. Lemma 5.6. Let [a, b] ⊆ [T ] be any interval. Then

mem 2 2 R[a,b] (u1:T ) ≤ GP[a,b] (b[a,b] max ) + 2GDB[a,b] +

b X t=a

PT  where ht = ∇fbt (wt ), ξt = s=t I t ≥ s − bs + 1

⟨ht , wt − ut ⟩ +

b X

λt ∥wt − wt−1 ∥ ,

t=a+1

t − s − bs , and λt = Gξt .

The lemma plays a role analogous to that of Lemma 5.1 from Section 5.1, reducing the OCO with memory problem to a certain OCO with movement costs problem. Applying Theorem 4.2 in this movement costs problem leads to the following guarantee. 9

Theorem 5.7. Initializing Algorithm 2 from Theorem 4.2 with Lipschitz constant H and λ ≥ GB 2 , and feeding it gradients ht = ∇fbt (wt ) and movement coefficients λt = Gξt where ξt is defined as in Lemma 5.6, guarantees for any [a, b] ⊆ [T ] and any u1 , . . . , uT ∈ W that ! r n o p
(1) (2) 2 mem e (D + P[a,b] ) H + G(H ∨ G)B + (D2 + DP[a,b] ) min V R (u1:T ) ≤ O ,V , [a,b]

[a,b]

[a,b]

  Pb P (1) where P[a,b] = t=a+1 ∥ut − ut−1 ∥, and we define V[a,b] = O (H + GB 2 ) t∈[a,b] ∥ht ∥ , and P n o P (2) [a,b]
2 2 2 4 V[a,b] = O ∥h ∥ + HG min B |b − a|, B + b . t t∈[a,b] t∈[a,b] t The proofs of both Lemma 5.6 and Theorem 5.7 are deferred to Appendix H.2. The main term in the P (1) bound depends on the minimum of two different variance penalties, V[a,b] = O(GB t∈[a,b] ∥ht ∥) P (2) [a,b] and V[a,b] = O( t∈[a,b] ∥ht ∥2 + HG(bt )2 ). Recalling that H ≤ G(B + 1) by Assumption 5.4, the first branch of the minimum yields a bound of v ! u b u X mem 2.5 t e R (u ) = O (D + P )G(1 + B ) + B G(D + P ) ∥h ∥ , [a,b]

1:T

[a,b]

t

[a,b]

t=a

e which recovers the O(B

q

DG

P

t∈[a,b] ∥ht ∥) bound of Zhang et al. [2022] as a special case when 3 2.5

P[a,b] = 0 (and modestly improves the memory dependence from B to B in the lower-order term). On the other hand, considering the other branch of the minimum, our result recovers, up to logarithmic factors and additive lower-order terms, the optimal dependence on the memory length and comparator path length established by Zhao et al. [2023]. In particular, our regret bound scales as  q  mem e B HG(D2 + DP[a,b] )|b − a| + GB 2 (D + P[a,b] ) R[a,b] (u1:T ) = O simultaneously over all intervals [a, b] ⊆ [T ]. Unlike Zhao et al. [2023], our guarantees are strongly adaptive, extend to arbitrary time-varying memory lengths, and admit refined data-dependent bounds involving the actual unary gradients and interval-clipped memory lengths.

6

Discussion

In this work, we presented new strongly-adaptive guarantees for dynamic regret with time-varying movement cost. Using this result we derive the first strongly-adaptive guarantees under delayed feedback and for OCO with time-varying memory. We leave a few interesting directions open for future work. We remark P that our sleeping experts guarantee obtains the ideal first-order movement costs dependency t∈[a,b] ∥gt ∥2 + λt ∥gt ∥ w.r.t. the losses of the underlying problem, but our blocking argument does not seem to extend straightP 2 forwardly to the analogous first-order dependency t∈[a,b] αti ⟨ℓt , pt − ei ⟩ + αti λt |⟨ℓt , ei − pt ⟩| in the “pure” sleeping-experts with movement costs problem. The core difficulty in achieving this bound is that the sleeping-experts reduction does not readily permit separate coordinate-wise movement costs. We also remark that our applications exhibit certain penalties related to information not [1,a−1] contained in the interval of interest, such as the maximum delay dmax before the start of the interval [a, b] in OCO with delayed feedback. In a similar vein, our approach also relies on prior knowledge of a global bound λ ≥ maxt λt , which in turn leads to a prior knowledge requirement on σ ≥ maxt |mt | and B ≥ maxt bt in the delayed feedback and memory settings respectively. Improving these global quantities to be strictly interval-local would be an interesting direction for future work.

Acknowledgments and Disclosure of Funding EE and AJ acknowledge the EU Horizon CL4-2022HUMAN-02 research and innovation action under grant agreement 101120237, project ELIAS (European Lighthouse of AI for Sustainability). HQ is supported by the Singapore National Research Foundation (NRF) under its AI Visiting Professorship programme. 10

References O. Anava, E. Hazan, and S. Mannor. Online learning for adversaries with memory: Price of past mistakes. Advances in Neural Information Processing Systems, 28, 2015. N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006. N. Chen, G. Goel, and A. Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In Conference On Learning Theory, pages 1574–1594. PMLR, 2018. A. Cutkosky. Parameter-free, dynamic, and strongly-adaptive online learning. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2250–2259, Virtual, 2020. PMLR. URL http://proceedings.mlr.press/v119/cutkosky20a.html. A. Daniely, A. Gonen, and S. Shalev-Shwartz. Strongly adaptive online learning. In International Conference on Machine Learning, pages 1405–1411. PMLR, 2015. E. Esposito, S. Masoudian, H. Qiu, D. van der Hoeven, N. Cesa-Bianchi, and Y. Seldin. Delayed bandits: When do intermediate observations help? In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 9374–9395. PMLR, 2023. G. Goel and A. Wierman. An online algorithm for smoothed regression and lqr control. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2504–2513. PMLR, 2019. G. Goel, N. Chen, and A. Wierman. Thinking fast and slow: Optimization decomposition across timescales. ACM SIGMETRICS Performance Evaluation Review, 45(2):27–29, 2017. E. Hazan. Introduction to online convex optimization. Foundations and Trends® in Optimization, 2 (3-4):157–325, 2016. doi: 10.1561/2400000013. E. Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. In Electronic colloquium on computational complexity (ECCC), volume 14, 2007. E. Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th annual international conference on machine learning, pages 393–400, 2009. M. Herbster and M. K. Warmuth. Tracking the best expert. Machine learning, 32(2):151–178, 1998a. M. Herbster and M. K. Warmuth. Tracking the best regressor. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, pages 24–31, 1998b. D. van der Hoeven and N. Cesa-Bianchi. Nonstochastic bandits and experts with arm-dependent delays. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 2022–2044. PMLR, 2022. D. van der Hoeven, L. Zierahn, T. Lancewicki, A. Rosenberg, and N. Cesa-Bianchi. A unified analysis of nonstochastic delayed feedback for combinatorial semi-bandits, linear bandits, and mdps. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 1285–1321. PMLR, 2023. A. Jacobsen and A. Cutkosky. Parameter-free mirror descent. In P.-L. Loh and M. Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 4160–4211. PMLR, 2022. URL https://proceedings. mlr.press/v178/jacobsen22a.html. V. Joseph and G. de Veciana. Jointly optimizing multi-user rate adaptation for video transport over wireless systems: Mean-fairness-variability tradeoffs. In 2012 Proceedings IEEE INFOCOM, pages 567–575. IEEE, 2012. P. Joulani, A. György, and C. Szepesvári. Online learning under delayed feedback. In International Conference on Machine Learning, pages 1453–1461. PMLR, 2013. 11

P. Joulani, A. György, and C. Szepesvári. Delay-tolerant online convex optimization: Unified analysis and adaptive-gradient algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016. K.-S. Jun, F. Orabona, S. Wright, and R. Willett. Improved Strongly Adaptive Online Learning using Coin Betting. In A. Singh and J. Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 943–951. PMLR, 20–22 Apr 2017. URL https://proceedings.mlr.press/ v54/jun17a.html. Y. Li, G. Qu, and N. Li. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. IEEE Transactions on Automatic Control, 66(10):4761–4768, 2020. M. Lin, Z. Liu, A. Wierman, and L. L. Andrew. Online algorithms for geographical load balancing. In 2012 international green computing conference (IGCC), pages 1–10. IEEE, 2012. S. Masoudian, J. Zimmert, and Y. Seldin. A best-of-both-worlds algorithm for bandits with delayed feedback. In Advances in Neural Information Processing Systems, volume 35, pages 11752–11762. Curran Associates, Inc., 2022. doi: 10.52202/068431-0854. B. McMahan and M. Streeter. Delay-tolerant algorithms for asynchronous distributed online learning. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. N. Merhav, E. Ordentlich, G. Seroussi, and M. J. Weinberger. On sequential strategies for loss functions with memory. IEEE Transactions on Information Theory, 48(7):1947–1958, 2002. N. Mhaisen and G. Iosifidis. Partially lazy gradient descent for smoothed online learning. In The 29th International Conference on Artificial Intelligence and Statistics, 2026. URL https: //openreview.net/forum?id=hIAkL2BYCI. F. Orabona. A modern introduction to online learning. CoRR, abs/1912.13213, 2019. URL https://arxiv.org/abs/1912.13213v9. H. Qiu, E. Esposito, and M. Zhang. Exploiting curvature in online convex optimization with delayed feedback. In Proceedings of the 42nd International Conference on Machine Learning, volume 267, pages 50448–50479. PMLR, 2025. H. Qiu, A. Jacobsen, E. Esposito, and M. Zhang. Parameter-free dynamic regret: Time-varying movement costs, delayed feedback, and memory. In Forty-third International Conference on Machine Learning, 2026. URL https://openreview.net/forum?id=xnj5CyzVVW. K. Quanrud and D. Khashabi. Online learning with adversarial delays. Advances in Neural Information Processing Systems, 28, 2015. A. Ryabchenko, I. Attias, and D. M. Roy. Capacity-constrained online learning with delays: Scheduling frameworks and regret trade-offs. In Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 4973–5014. PMLR, 2025. A. Ryabchenko, I. Attias, and D. M. Roy. A reduction from delayed to immediate feedback for online convex optimization with improved guarantees, 2026. URL https://arxiv.org/abs/2602. 02634. T. S. Thune, N. Cesa-Bianchi, and Y. Seldin. Nonstochastic multiarmed bandits with unrestricted delays. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. Y. Wan, W.-W. Tu, and L. Zhang. Online strongly convex optimization with unknown delays. Machine Learning, 111(3):871–893, 2022. Y. Wan, C. Yao, M. Song, and L. Zhang. Non-stationary online convex optimization with arbitrary delays. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pages 49991–50011. PMLR, 2024. 12

M. J. Weinberger and E. Ordentlich. On delayed prediction of individual sequences. IEEE Transactions on Information Theory, 48(7):1959–1976, 2002. T. Yang, L. Zhang, R. Jin, and J. Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In M. F. Balcan and K. Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 449–457, New York, New York, USA, 2016. PMLR. URL https://proceedings.mlr.press/v48/yangb16.html. L. Zhang, S. Lu, and Z.-H. Zhou. Adaptive online learning in dynamic environments. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 1330–1340, 2018. L. Zhang, S. Lu, and T. Yang. Minimizing dynamic regret and adaptive regret simultaneously. In International conference on artificial intelligence and statistics, pages 309–319. PMLR, 2020. L. Zhang, W. Jiang, S. Lu, and T. Yang. Revisiting smoothed online learning. Advances in Neural Information Processing Systems, 34:13599–13612, 2021a. L. Zhang, G. Wang, W.-W. Tu, W. Jiang, and Z.-H. Zhou. Dual adaptivity: A universal algorithm for minimizing the adaptive regret of convex functions. Advances in Neural Information Processing Systems, 34:24968–24980, 2021b. M. Zhang, Y. Wang, and H. Luo. Contextual linear bandits with delay as payoff. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 76246–76272. PMLR, 2025. Z. Zhang, A. Cutkosky, and I. Paschalidis. Adversarial tracking control via strongly adaptive online learning with memory. In G. Camps-Valls, F. J. R. Ruiz, and I. Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 8458–8492. PMLR, 28–30 Mar 2022. URL https://proceedings.mlr.press/v151/zhang22f.html. P. Zhao, Y.-H. Yan, Y.-X. Wang, and Z.-H. Zhou. Non-stationary online learning with memory and non-stochastic control. Journal of Machine Learning Research, 24(206):1–70, 2023. J. Zimmert and Y. Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3285–3294. PMLR, 2020. M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936, 2003.

13

A

More Related Works

In this section, we provide more detailed discussion of relevant related works. Dynamic and adaptive regret. Dynamic regret has been extensively studied as a measure of performance in non-stationary OCO. The extension of regret to handling a sequence of comparators dates back to Herbster and Warmuth [1998a,b] in the regression and learning-from-expert-advice settings. Zinkevich [2003] extended the scope to the more general√OCO setting, and showed that online gradient descent can obtain RT (u1:T ) = O((D + PT ) T ) dynamic regret, where PT PT = t=2 ∥ut − ut−1 ∥ is the path-length of pthe comparator sequence. Yang et al. [2016] later showed that the bound can be improved to O( (D2 + DPT )T ) given prior knowledge of PT , and Zhang et al. [2018] was the first to obtain this bound without prior knowledge of PT . Another important line of work studies adaptive regret. Hazan and Seshadhri [2007] first introduced adaptive regret defined as thepmaximum regret over any contiguous interval, and later obtained an adaptive regret bound of O( T log3 T ) for convex losses and O(log2 T ) for exp-concave losses [Hazan and Seshadhri, 2009]. A key limitation of adaptive regret is that its guarantee is expressed in terms of the horizon T , rather than the length of the interval under consideration. Consequently, the bound can be uninformative on short intervals. To address this drawback, Daniely et al. [2015] introduced strongly adaptive regret. This stronger criterion measures regret explicitly as a function of the interval length, and is therefore more suitable for evaluating performance √ on both short and long intervals. The algorithm proposed by Daniely et al. [2015] achieves an O( τ log T ) regret for each interval of length τ ∈ [T ] simultaneously. Subsequent work [Jun et al., 2017, Zhang et al., 2020] improved √ this guarantee by introducing new meta-algorithms, reducing the strongly adaptive regret to O( τ log T ). OCO with movement costs. OCO with movement costs, also known as smoothed online convex optimization [Goel et al., 2017, Chen et al., 2018, Goel and Wierman, 2019, Li et al., 2020], has received considerable attention in recent years. In this framework, on round t the learner incurs both the loss ℓt (wt ) as well as a movement cost λ∥wt − wt−1 ∥ for deviating from its decision in the previous round. A closely related formulation is OCO with memory [Merhav et al., 2002], in which each loss may depend on a history of past decisions. Stability plays a central role in this setting, and many algorithms achieve it by reducing the problem to OCO with movement costs [Anava et al., 2015]. Online learning with delayed feedback. Delayed feedback has been extensively studied in online learning. Early work by Weinberger and Ordentlich [2002], Joulani et al. [2013] developed blackbox reductions from OCO with delayed feedback to standard OCO, obtaining regret bounds of √ order O( T + dmax T ), where dmax denotes the maximum delay. For convex losses, Quanrud and Khashabi [2015] √ improved this dependence by adapting online gradient descent, achieving a regret bound of O( T + dtot ), where dtot is the total cumulative delay, which can be significantly smaller than dmax T . There is also a parallel line of work that focuses on obtaining adaptive regret guarantees and fast rates in delayed-feedback settings [McMahan and Streeter, 2014, Joulani et al., 2016, Wan et al., 2022, Qiu et al., 2025]. Feedback delays also led to the development of specialized techniques for a broad range of problem settings related to multi-armed bandits [Thune et al., 2019, Zimmert and Seldin, 2020, Masoudian et al., 2022, Van der Hoeven and Cesa-Bianchi, 2022, Esposito et al., 2023, Van der Hoeven et al., 2023, Zhang et al., 2025, Ryabchenko et al., 2025].

B

Proofs for Section 3 (Strong Adaptivity with Time-Varying Movement Costs)

B.1

Proof of Lemma 3.1

In this section we prove a general specialists reduction for the movement-cost regret. The reduction is over [1, T ], and we later specialize the result to sub-intervals [a, b] in Lemma 3.2. P (i) Lemma 3.1. Let Assumption 2.1 hold. Suppose on each round t ∈ [T ] we play wt = i∈[N ] pt,i wt , (i)

where wt

∈ W is the output of expert Ai on round t and pt ∈ ∆N −1 is the output of a meta14

algorithm AMeta . Then for any i ∈ [N ] and any sequence u1 , . . . , uT ∈ W, T D T E X X (i) (i) (i) RT (u1:T , λ1:T ) ≤ gt , wt − ut + λt ∥wt − wt−1 ∥ + ⟨ℓt , pt − ei ⟩ + Dλt ∥pt − pt−1 ∥1 , t=1

t=1

{z

|

}

A =:RT i (u1:T ,λ1:T )

{z

|

Meta (e ,λMeta ) =:RT i 1:T

}

where gt ∈D∂ft (wt ),EλMeta = Dλt , and the surrogate loss vector ℓt ∈ RN is defined coordinate-wise t (j) (j) (j) by ℓt,j := gt , wt + λt ∥wt − wt−1 ∥, ∀j ∈ [N ]. Proof. By convexity of ft for all t ∈ [T ] (Assumption 2.1), we know that for any i ∈ [N ] RT (u1:T , λ1:T ) =

T X

(ft (wt ) − ft (ut ) + λt ∥wt − wt−1 ∥)

t=1

≤

T X

(⟨gt , wt − ut ⟩ + λt ∥wt − wt−1 ∥)

t=1

=

T X

*  gt ,

t=1

=

n X



+ (j)

pt,j wt − ut

+ λt ∥wt − wt−1 ∥

j=1

T D T T D E X E X X (i) ℓet , pt − ei + λt ∥wt − wt−1 ∥, gt , wt − ut + t=1

t=1

t=1

D E (j) where gt ∈ ∂ft (wt ) and define ℓet ∈ RN as ℓet,j ≜ gt , wt for j ∈ [N ] . Moreover, observe that the movement costs can be bounded as  X  (j) (j) ∥wt − wt−1 ∥ = pt,j wt − pt−1,j wt−1 j∈[N ] (j)

(j)

pt,j (wt − wt−1 ) +

X

(j) (j) pt,j ∥wt − wt−1 ∥ +

X

=

X

≤

X

j∈[N ]

j∈[N ]

j∈[N ]

≤

X

(j)

(pt,j − pt−1,j )wt−1 (j)

∥wt−1 ∥ · |pt,j − pt−1,j |

(triangle inequality)

j∈[N ] (j) (j) pt,j ∥wt − wt−1 ∥ + D · ∥pt − pt−1 ∥1 ,

j∈[N ]

so summing over t, T X

λt ∥wt − wt−1 ∥ ≤

t=1

T X X

(j)

(j)

pt,j λt ∥wt − wt−1 ∥ +

t=1 j∈[N ]

T X

Dλt ∥pt − pt−1 ∥1 .

t=1

Hence, we are able to bound RT (u1:T , λ1:T ) as follows: RT (u1:T , λ1:T ) T D T D E X E X (i) gt , wt − ut + ℓet , pt − ei ≤ t=1

+

t=1 T X X t=1 j∈[N ]

T hD (∗) X

=

(j) (j) λt pt,j ∥wt − wt−1 ∥ +

T X

Dλt ∥pt − pt−1 ∥1

t=1

T E i X (i) (i) (i) gt , wt − ut + λt ∥wt − wt−1 ∥ + [⟨ℓt , pt − ei ⟩ + Dλt ∥pt − pt−1 ∥1 ]

t=1

t=1

(j) (j) where (∗) is by the definition of ℓt,j ≜ ℓet,j + λt wt − wt−1 for all j ∈ [N ].

15

B.2

Proof of Lemma 3.2

In this section we prove our specialists reduction for an arbitrary sub-interval [a, b]. The result follows via a special case of Lemma 3.1. Lemma 3.2. Under the same assumptions as Lemma 3.1, let [a, b] ⊆ [T ] and let the active rounds of Ai coincide with interval [a, b], i.e., αt,i = 1 {t ∈ [a, b]} for all t ∈ [T ]. Then for any sequence ua:b = (ua , . . . , ub ) over W, Ai R[a,b] (ua:b , λa:b ) ≤ RTα (ei , λMeta 1:T ) + R[a,b] (ua:b , λa:b ) .

Proof. Applying Lemma 3.1 over the interval I = [a, b] where expert Ai is active, we have Ai Meta R[a,b] (ua:b , λa:b ) ≤ R[a,b] (ua:b , λa:b ) + R[a,b] (ei , Dλa:b ) .

Note that because Ai is active only on rounds t ∈ [a, b], The meta regret is equivalent to X Meta R[a,b] (ei , λMeta ⟨ℓt , pt − ei ⟩ + Dλt ∥pt − pt−1 ∥1 a:b ) = t∈[a,b]

=

T X

  αti ⟨ℓt , pt − ei ⟩ + Dλt ∥pt − pt−1 ∥1

t=1

=

T X X

[αtj eij (⟨ℓt , pt ⟩ − ℓtj ) + Dλt αtj eij ∥pt − pt−1 ∥1 ]

t=1 j∈[N ]

=

T X X

[αtj eij (⟨ℓt , pt ⟩ − ℓtj + Dλt ∥pt − pt−1 ∥1 )]

t=1 j∈[N ]

= RTα (ei , Dλ1:T ). Hence, X

Ai ft (wt ) − ft (ut ) ≤ R[a,b] (ua:b , λa:b ) + RTα (ei , Dλ1:T ) .

t∈[a,b]

C

Proofs for Section 3.1 (Sleeping Experts with Movement Costs)

C.1

Proof of Theorem 3.3

Theorem 3.3. Suppose that ∥ℓt ∥∞ ≤ G∞ and λt ≤ λ for all t. Then for any u ∈ ∆N −1 , Algorithm 1 with L = 2G∞ + 5λ guarantees ! hq i X α VTλ+1,i log (ui ΛT +1,i + 1) ∨ L log (ui ΛT +1,i + 1) , RT (u, λ1:T ) = O Γ(ϵ) + ui i∈[N ]

where VTλ+1,i = O λ +

T X

h

2

αti ⟨ℓt , ei − pt ⟩ + λ2t

i

! ,

t=1

q ΛT +1,i =

VTλ+1,i log2 (VTλ+1,i /L2 )



Γ(ϵ) = L 1 +

X

ϵi L  ϵi

i∈[N ] α Proof. Let ztα denote the vector with entriesP zti = αti zti . Note that pt ∈ ∆N −1 since pbt := α α zt /∥zt ∥1 satisfies pbti ≥ 0 for all i ∈ [N ] and i∈[N ] pbti = 1.

16

First, we show that that the sleeping-expert regret of the choices pt = ztα /∥ztα ∥ is equivalent to the regret of the choices zt against the losses ℓbt ∈ RN with components ℓbti = αti (ℓti − ⟨ℓt , pt ⟩ − λt ∥pt − pt−1 ∥1 ). Indeed, we have

RTα (u, λ1:T ) :=

T X X

αti ui (⟨ℓt , pt ⟩ − ℓti + λt ∥pt − pt−1 ∥1 )

t=1 i∈[N ] T (a) X

=

D E − ℓbt , u

t=1 T D E (b) X = ℓbt , zt − u + ⟨zt , αt ⟩ λt ∥pt − pt−1 ∥1 t=1

D E where (a) is by definition of ℓbt , and (b) adds and subtracts ℓbt , zt and observes that D E X ℓbt , zt = αti (ℓti − ⟨ℓt , pt ⟩ − λt ∥pt − pt−1 ∥1 )zti i

! =

X

αti ℓti zti − ⟨ℓt , pt ⟩

X

i

αti zti

− ∥pt − pt−1 ∥1

i

X

αti λt zti

i∈[N ]

!  X ztα = αti ℓti zti − ℓt , α αti zti − λt ∥pt − pt−1 ∥1 ⟨αt , zt ⟩ ∥zt ∥1 i i X X = αti ℓti zti − αti ℓti zti − λt ∥pt − pt−1 ∥1 ⟨αt , zt ⟩ = −λt ∥pt − pt−1 ∥1 ⟨αt , zt ⟩ . X

i

i

Note that the above is true even if ∥ztα ∥1 = 0, since this can happen only when αti zti = 0 for all i ∈ [N ], in which case the equality would still hold if we set pt arbitrarily in this case. Moreover, observe that since pt = ztα /∥ztα ∥1 , we have T X

λt ∥pt − pt−1 ∥1 ⟨αt , zt ⟩ =

t=1

T X

α λt ztα − zt−1

t=1

≤

T X

λt

t=1

≤

T X t=1

≤

T X

λt

1

!   ∥ztα ∥1 α α α zt−1 ∥zt − zt−1 ∥1 + 1− α ∥zt−1 ∥1 1 !   α ∥z ∥ 1 t α α ∥ztα − zt−1 ∥1 + 1− α zt−1 ∥zt−1 ∥1 1

α 2λt ∥ztα − zt−1 ∥1 =

t=1

=

∥ztα ∥1 α ∥ ∥zt−1 1

T X X

T X t=1

2λt

X

|αti zti − αt−1,i zt−1,i |

i∈[N ]

2λt αt−1,i αti |zti − zt−1,i | + 2λt (1 − αti )αt−1,i zt−1,i ,

i∈[N ] t=1

where the last line observes the following three cases for αti supported on [ai , bi ]: (a) for t ∈ [ai + 1, bi ], we have αti = αt−1,i so |αti zti − αt−1,i zt−1,i | = αti |zti − zt−1,i |, (b) on rounds t ≤ ai , we have |αti zti − αt−1,i zt−1,i | = 0 since zti = 0 for t ≤ ai , and (c) for t = bi + 1 we have |αti zti − αt−1,i zt−1,i | = αt−1,i zti while for t > bi + 1 we have |αti zti − αt−1,i zt−1,i | = 0, so more generally we have |αti zti − αt−1,i zt−1,i | = (1 − αti )αt−1,i zt−1,i for t ≥ b + 1. Thus, plugging this 17

back in above, RTα (u, λ1:T ) ≤

T D T X E X X ℓbt , zt − u + 2 λt αt−1,i αti |zti − zt−1,i | + λt (1 − αti )αt−1,i zt−1,i t=1

=

t=1 i∈[N ]

" T X X

T X

ℓλti (zti − ui ) +

t=1

i∈[N ]

# 2αt−1,i αti λt |zti − zt−1,i |

t=1

|

(i)

{z

}

(i)

e (ui ,λ =:R T 1:T )

+

X

ui

i∈[N ]

T X

2(1 − αt+1,i )αti λt+1

(3)

t=1

(i)

where we define λt = 2αt−1,i αti λt for brevity and ℓλti = ℓbti + (1 − αt+1,i )2λt+1 αti = αti (ℓti − ⟨ℓt , pt ⟩ − λt ∥pt − pt−1 ∥1 ) + 2(1 − αt+1,i )αti λt+1 . Observe for any i ∈ [N ] and t ∈ [ai , bi ], we have |ℓλti | ≤ αti |⟨ℓt , ei − pt ⟩| + αti λt ∥pt − pt−1 ∥1 + (1 − αt+1,i )αti λt+1 ≤ 2αti (∥ℓt ∥∞ + λt + λt+1 ) ≤ 2αti (∥ℓt ∥∞ + 2 max λs+1 ) ≤ 2(G∞ + 2λ) s∈[ai ,bi ] s≤t

(i)

so for L = 2G∞ + 5λ we have L ≥ |ℓλti | + λt+1 on each round, so we can apply Theorem D.1 with (i) L = 2G∞ + 5λ to the losses x 7→ ℓλti x and movement coefficient λt separately in each coordinate i ∈ [N ] to get q e(i) (ui , λ(i) ) ≤ O b ϵi L + u i V λ R T +1,i log (ui ΛT +1,i + 1) T 1:T ! + Lui log (ui ΛT +1,i + 1) , where VTλ+1,i = O

T X

! (i) (|ℓλti | + λt+1 )2

λ2bi +1 +

=O

ΛT +1,i =

! αti (ℓti − ⟨ℓt , pt ⟩)

2

+ αti λ2t

,

t=1

t=1

q

T X

VTλ+1,i log2 VTλ+1,i /L2 ϵi L

.

Plugging this back into Equation (3) and summing over i ∈ [N ] yields RTα (u) = O

X

ui

hq

VTλ+1,i log (ui ΛT +1,i + 1) ∨ L log (ui ΛT +1,i + 1)

i

i∈[N ]

+L

X

ϵi +

i∈[N ]

X i∈[N ]

! T X ui (1 − αt+1,i )αti λt+1 , t=1

and the stated result follows by observing that for P αti is supported on [ai , bi ], it holds that (1 − αt+1,i )αti = 1 only on round bi so the last term is 2 i ui λbi +1 ≤ 2λ = O(L) for u ∈ ∆N −1 . C.2

Relation to Jun et al. [2017]

In this section we show that our result in Theorem 3.3 recovers the best-known result for the standard sleeping experts setting as a special case, while also incorporating movement costs and obtaining Lipschitz adaptivity. In particular, the following result shows that that Theorem 3.3 matches the regret guarantee of CBCE up to lower-order terms [Jun et al., 2017, Corollary 1]. 18

Corollary C.1. Let π ∈ ∆N −1 be supported on [N ] and set ϵi = πi for each i ∈ [N ]. Then under the same assumptions as Theorem 3.3, for any u ∈ ∆N −1 , Algorithm 1 guarantees v !# " u λ  uX V (u) T +1 α e t +1 RT (u, λ1:T ) ≤ O ui VTλ+1,i KL(u|π) + log L2 i∈[N ]

P λ where we define V T +1 (u) = i ui VTλ+1,i , while VTλ+1,i and BTλ +1,i are defined as in Theorem 3.3. Proof. From Theorem 3.3, we have RTα (u, λ1:T ) = O L

X

X

πi +

i

ui

q VTλ+1,i log (ui ΛT +1,i + 1)

i∈[N ]

! +L

X

ui log (ui ΛT +1,i + 1)

i∈[N ]

=O L+

sX

ui VTλ+1,i

i∈[N ]

X

ui log (ui ΛT +1,i + 1)

i∈[N ]

! +L

X

ui log (ui ΛT +1,i + 1)

i∈[N ]

√ λ VT +1,i log2 (VTλ+1,i /L2 ) where ΛT +1,i = and the last line applies the Cauchy-Schwarz inequality. πi Now observe that for any u, β ≥ 0 and ϵ > 0, we can bound   u  u   ϵ ϵ  uβ + 1 = u log + u log β + ≤ u log + u log (1 + β) 1 + u log ϵ ϵ u ϵ u u  ϵ = u log + u log (1 + β) + u log 1 + u  uϵ  ≤ u log + u log (1 + β) + ϵ, ϵ where we have used u log (1 + ϵ/u) ≤ ϵ and β + uϵ ≤ (1 + β)(1 + uϵ ) for β, ϵ, u > 0 and observed that the inequality is trivially true when u = 0 or β = 0. Therefore, we have X ui log (ui ΛT +1,i + 1) i∈[N ]

≤

X

 ui log

i∈[N ]

ui ϵi

= 1 + KL(u|ϵ) +



X

+

√ ui log

i∈[N ]

X

√

ui log

VTλ+1,i log2 (VTλ+1,i /L2 ) +1 L

VTλ+1,i log2 (VTλ+1,i /L2 ) +1 L

 +1



i∈[N ]

P ≤ 1 + KL(u|ϵ) + log 

i ui

q VTλ+1,i log2 (VTλ+1,i /L2 ) L

 + 1 ,

where the last line applies Jensen’s inequality. Hence, plugging this back in above yields v  P  √ λ uX u VT +1,i i∈[N ] ui α λ b +1 RT (u, λ1:T ) = O L + t ui VT +1,i 1 + KL(u|π) + log L i∈[N ]

 P  ! √ λ VT +1,i i∈[N ] ui + L 1 + KL(u|π) + log +1 L v q  P  u λ uX u V T +1,i i∈[N ] i u  e =O ui VTλ+1,i 1 + KL(u|π) + log  + 1 , t L i∈[N ]

19

Applying Jensen’s inequality to bound log  λ  1 log V (u) yields the stated guarantee. T +1 2

D

P

i ui

q

VTλ+1,i



≤ log

qP

λ i ui VT +1,i



=

Parameter-free OLO with Movement Costs

In this section we provide an extension of the parameter-free algorithm of Jacobsen and Cutkosky [2022] to handle movement costs. The result is a straight-forward extension of the original analysis by using the movement-costs-via-stability analysis of Qiu et al. [2026]. The result is provided for completeness. Algorithm 3 Parameter-free FTRL for OLO with Movement Costs Input: value L, ϵ > 0 Initialize: w1 = 0 ∈ W Define:   Z ∥w∥ log (x/β + 1) min ψ(w; V, β) = 3 + ηV dx 1 η 0 0<η≤ L

for t = 1, . . . , T do Pt−1 Set Vtλ = 4L2 + τ =1 (∥gτ ∥ + λτ +1 )2 and βt = √ λ ϵL Vt log2 (Vtλ /L2 ) DP E t−1 λ Play wt = arg minw∈W τ =1 gτ , w + ψ(w; Vt , βt ) Observe gt ∈ ∂ft (wt ) and movement coefficient λt+1 Theorem D.1. Let Assumption 2.1 hold. Then for all u ∈ W, Algorithm 3 with L ≥ ∥gt ∥ + λt+1 for all t guarantees " #! q λ RT (u, λ1:T ) ≤ O ϵL+∥u∥ VT +1 log (∥u∥ΛT +1 + 1) ∨ L log (∥u∥ΛT +1 + 1) , √ λ

VT +1 log2 (VTλ+1 /L2 ) . ϵL

where ΛT +1 =

Proof. By convexity of ft , we have that T T X X RT (u, λ1:T ) = ft (wt ) − ft (u) + λt ∥wt − wt−1 ∥ ≤ ⟨gt , wt − u⟩ + λt ∥wt − wt−1 ∥, t=1

t=1

where gt ∈ ∂ft (wt ). Now applying the standard FTRL regret template to the first term (see, e.g, Orabona, 2019, Lemma 7.1), we have T T X X RT (u, λ1:T ) ≤ ψT +1 (u) + Ft (wt ) − Ft+1 (wt+1 ) + ⟨gt , wt ⟩ + λt ∥wt − wt−1 ∥, t=1

where Ft (w) =

DP t−1

τ =1 gτ , w

E

t=1

+ ψt (w) and ψt (w) =

ψ(w; Vtλ , αt ).

Moreover, since wt ∈

arg minw∈W Ft (w), we have T X

Ft (wt ) − Ft+1 (wt+1 ) + ⟨gt , wt ⟩

t=1

=

T X

Ft (wt ) − Ft (wt+1 ) + (ψt − ψt+1 )(wt+1 ) + ⟨gt , wt − wt+1 ⟩

t=1 T (a) X

=

⟨∇Ft (wt ) + gt , wt − wt+1 ⟩ − DFt (wt+1 |wt ) + (ψt − ψt+1 )(wt+1 )

t=1 T (b) X

≤

⟨gt , wt − wt+1 ⟩ − Dψt (wt+1 |wt ) + (ψt − ψt+1 )(wt+1 ),

t=1

20

where (a) uses the definition of Bregman divergence to write f (x) − f (y) = ⟨∇f (x), x − y⟩ − Df (y|x) and (b) uses the first-order optimality condition for wt ∈ arg minw∈W Ft (w) to bound ⟨∇Ft (wt ), wt − wt+1 ⟩ ≤ 0 and the fact that Bregman divergences are invariant to linear terms, so DFt (x|y) = Dψt (x|y) for any x, y ∈ W. Plugging this back into the regret bound and re-indexing the movement costs, we have RT (u, λ1:T ) ≤ ψT +1 (u) +

T  X t=1

+

T X

wt − wt+1 gt + λt+1 , wt − wt+1 ∥wt − wt+1 ∥

− Dψt (wt+1 |wt )

(ψt − ψt+1 )(wt+1 )

t=1

≤ ψT +1 (u) +

T X t=1

(∥gt ∥ + λt+1 )∥wt − wt+1 ∥ − Dψt (wt+1 |wt ) + (ψt − ψt+1 )(wt+1 ) . {z } | =:δt

For ∥gt ∥ + λt+1 ≤ L for all t, the latter term can be bound borrowing the stability analysis of Jacobsen and Cutkosky [2022, Theorem 6]: T X t=1

δt ≤

T T X X (∥gt ∥ + λt+1 )2 2α p t (∥gt ∥ + λt+1 )2 = 2ϵL ≤ 4ϵL , V λ log2 (Vtλ /L2 ) Vtλ t=1 t t=1

h i λ where the last line applies Lemma I.3. Finally, letting f (x) = minη≤1/L log(x/α+1) + ηV T +1 , we η have that Z ∥u∥ ψT +1 (u) = 3 f (t) dt ≤ 3∥u∥f (∥u∥) 0 "s    # ∥u∥ ∥u∥ VTλ+1 log ≤ 3∥u∥ + 1 ∨ L log +1 . αT +1 αT +1 The stated bound follows factors and observing that VTλ+1 = P  by hiding P doubly logarithmic  T T 2 2 2 O =O t=1 (∥gt ∥ + λt+1 ) t=1 ∥gt ∥ + λt . PT We state also for completeness the analogous result to the above achieving the ideal t=1 ∥gt ∥2 + λt ∥gt ∥ dependence, which results by applying the blocking reduction Qiu et al. [2026, Algorithm 3] with Algorithm 3 as the base algorithm. We do not use this result explicitly here, p but it is of indepen
e ∥u∥ P ∥gt ∥2 + ∥gt ∥λt dent interest since the result of Qiu et al. [2026] obtains the optimal O t static regret only as a special-case of the optimal dynamic regret guarantee, which requires O(d log(T )) per-round computation to obtain. The following result provides the optimal static regret guarantee using the usual O(d) per-round computation. The proof is immediate by Qiu et al. eτ +1 ≤ G + 2λ, by definition of the blocking reduction. [2026, Lemma B.1], and the fact that ∥e gτ ∥ + λ Theorem D.2. Let Assumption 2.1 hold and set L ≥ G + 2λ. Then for all u ∈ W, applying Algorithm 5 with Algorithm 3 guarantees  q  RT (u, λ1:T ) ≤ O Lϵ + ∥u∥ VTλ+1 log (∥u∥ΛT +1 + 1) ∨ L log (∥u∥ΛT +1 + 1) b hides constants and doubly-logarithmic factors and where O(·) √ λ ΛT +1 =

VT +1 log2 (VTλ+1 /L2 ) , ϵL

T X λ VT +1 = O ∥gt ∥2 + ∥gt ∥λt t=1

21

! .

E

Adaptive Gradient Descent with Movement Costs

In this section, we present a q simple baseline algorithm that achieves a dynamic reP 2 2 gret bound of O((D + P[a,b] ) t∈[a,b] (∥gt ∥ + λt+1 )), which can be improved to   qP 2 O (D + P[a,b] ) t∈[a,b] ∥gt ∥ + λt ∥gt ∥ using the blocking reduction of Algorithm 5. Note that since we will obtain all intervals [a, b] simultaneously, it can be shown that this q this bound onP 2 implies the optimal (D + DP[a,b] ) t∈[a,b] (∥gt ∥2 + λt+1 ∥gt ∥) on each sub-interval simultaneously as well (Cutkosky [2020, Theorem 7]). Algorithm 4 is based on Online Gradient Descent (OGD) [Zinkevich, 2003] with an adaptive learning rate choice.

Algorithm 4 Adaptive Gradient Descent with Time-varying Movement Costs Input: Convex domain W ⊂ Rd , parameter α > 0 Initialize: w1 ∈ W for t = 1, . . . , T do Play wt ∈ W, observe gt ∈ ∂ft (wt ) and λt+1 α Set ηt+1 = √Pt 2 τ =1 (∥gτ ∥+λτ +1 )

Update wt+1 = ΠW (wt − ηt+1 gt ) end

The following theorem provides the regret of the movement-cost-adaptive gradient descent procedure. Theorem E.1. For any sequence u1:T = (u1 , . . . , uT ) ∈ W T , Algorithm 4 guarantees

v u T u X D + DPT ∥gt ∥2 + λ2t+1 , RT (u1:T , λ1:T ) ≤ + α t2 α t=1 

where PT =

2

PT

t=2 ∥ut − ut−1 ∥.

Proof. The algorithm can be interpreted as an instance of mirror descent with ψt+1 (w) = 2η1t+1 ∥w∥2 , and wt+1 = arg minw∈W ⟨gt , w⟩ + Dψt+1 (w|wt ). By the first-order optimality condition, we know that for any w ∈ W

⟨gt + ∇ψt+1 (wt+1 ) − ∇ψt+1 (wt ), w − wt+1 ⟩ ≥ 0.

Picking w to be ut and re-arranging, we have ⟨gt , wt+1 − ut ⟩ ≤ ⟨∇ψt+1 (wt ) − ∇ψt+1 (wt+1 ), wt+1 − ut ⟩. Therefore, for gt ∈ ∂ℓt (wt ) for all t, we have 22

that

RT (u1:T , λ1:T ) ≤

T X

⟨gt , wt − ut ⟩ + λt ∥wt − wt−1 ∥

(Assumption 2.1)

t=1

=

T X

⟨gt , wt+1 − ut ⟩ +

t=1

≤

T X

T X

⟨gt , wt − wt+1 ⟩ +

t=1

T X

λt ∥wt − wt−1 ∥

t=1

⟨∇ψt+1 (wt ) − ∇ψt+1 (wt+1 ), wt+1 − ut ⟩ +

T X

⟨gt , wt − wt+1 ⟩ +

T X

λt ∥wt − wt−1 ∥

t=1

t=1

T (a) X

T
X
Dψt+1 (ut |wt ) − Dψt+1 (ut |wt+1 ) + (∥gt ∥ + λt+1 )∥wt − wt+1 ∥ − Dψt+1 (wt+1 |wt )

≤

t=1 T (b) X

≤

t=1

Dψt+1 (ut |wt ) − Dψt+1 (ut |wt+1 ) +

≤

T X ηt+1 t=1

t=1 T (c) X

t=1

2

(∥gt ∥ + λt+1 )2 ∥gt ∥)

v u T uX Dψt+1 (ut |wt ) − Dψt+1 (ut |wt+1 ) + αt ∥gt ∥2 + λ2t+1

t=1

t=1

where (a) uses the equality ⟨∇f (a) − ∇f (b), b − u⟩ = Dψ (u|a) − Dψ (u|b) − Dψ (b|a) and reindexes the movement costs (recalling λT +1 = λ1 = 0); (b) uses Dψt+1 (x|y) = 2η1t+1 ∥x − y∥2 and applies Fenchel-Young inequality, and (c) uses the definition of ηt+1 and the fact that,

2 ηt+1 ∥gt ∥ + λt+1 q
2 Pt t=1 2 τ =1 ∥gτ ∥ + λτ +1

T X

T X

(∥gt ∥ + λt+1 )2 q
2 Pt t=1 2 τ =1 ∥gτ ∥ + λτ +1 v v  u t−1 u t T u uX X X

2 2 t ≤α ∥gτ ∥ + λτ +1 − t ∥gτ ∥ + λτ +1  ≤α

t=1

τ =1

v u T uX  ≤α t ∥g ∥ + λ t

τ =1

 t+1

2

.

t=1

23

For the first summation of the above equation, direction calculation shows that T X
Dψt+1 (ut |wt ) − Dψt+1 (ut |wt+1 ) t=1

=

T X

T
X
Dψt (ut |wt ) − Dψt+1 (ut |wt+1 ) + Dψt+1 (ut |wt ) − Dψt (ut |wt )

t=1

t=1

= Dψ1 (u1 |w1 ) − DψT +1 (uT |wT +1 ) +

T X

(Dψt (ut |wt ) − Dψt (ut−1 |wt ))

t=2

+

T  X t=1

1 1 − 2ηt+1 2ηt



∥wt − ut ∥2

v u D t ≤ ψt (ut ) − ψt (ut−1 ) − ⟨∇ψt (wt ), ut − ut−1 ⟩ + (∥gt ∥ + λt+1 ) α t=2 t=1 v u T T X X D2 u t (∥g ∥ + λ )2 ≤ ⟨∇ψt (ut ) − ∇ψt (wt ), ut − ut−1 ⟩ + t t+1 α t=1 t=2 v v u T u T 2 uX X DPT u D t t (∥g ∥ + λ )2 2 ≤ (∥gt ∥ + λt+1 ) + t t+1 α α t=1 t=1 v u T X D2 + DPT u t (∥g ∥2 + λ )2 . ≤ t t+1 α t=1 T X

T 2 uX

Hence, overall we have v u T uX D2 + DPT RT (u1:T , λ1:T ) ≤ + α t (∥gt ∥ + λt+1 )2 α t=1 v  2 u T u X D + DPT ∥gt ∥2 + λ2t+1 , ≤ + α t2 α t=1 

where the last line uses the elementary inequality (a + b)2 ≤ 2a2 + 2b2 .

F

Adaptive First-order Reduction

In this section, we provide a modest refinement of the first-orderPreduction of Qiu et al. [2026] which P allows us to convert t ∥gt ∥2 +λ2t dependencies into the better t ∥gt ∥2 +λt ∥gt ∥ dependencies over any sub-interval [a, b]. The reduction is shown in Algorithm 5, and the following lemma provides the key property of the aggregate losses induced by the reduction. The P main difference from P the reduction of Qiu et al. [2026] is we use a blocking condition based on t ∥gt ∥ rather than ∥ t gt ∥. This is useful because the latter condition can make bounding losses over partial epochs difficult, which becomes relevant in the strongly-adaptive setting, where an interval [a, b] may begin mid-way through a given epoch. The following provides a modest generalization of the blocking argument of Qiu et al. [2026] to account for the fact that an arbitrary [a, b] may not align with the blocks defined by Algorithm 5. Lemma 4.1. Let Assumption 2.1 hold. Let (Iτ )τ be the set of intervals defined during the execution of the blocking reduction (Algorithm 5), and let E[a,b] = {τ : Iτ ⊆ [a, b]} denote the set of complete epochs contained within [a, b]. For any comparator sequence (ut )t∈[a,b] in W, Algorithm 5 with any base algorithm A guarantees that X eτ ∥w R[a,b] (ua:b , λa:b ) ≤ 3(D + P[a,b] )(G + λ[a,b] ) + ⟨e gτ , w eτ − u eτ ⟩ + λ eτ − w eτ −1 ∥. max

τ ∈E[a,b]

24

Algorithm 5 Adaptive First-order Reduction e Denote w e first decision, τ = 1, geτ = 0, Hτ = 0. Initialize: Online learning algorithm A. e1 to be A’s for t = 1, 2, . . . do Play wt = w eτ , then receive gt and λt+1 Update geτ ← geτ + gt and Hτ ← Hτ + ∥gt ∥ if Hτ > λt+1 then eτ +1 = λt+1 Set λ eτ +1 ) to Ae , and receive w Send (e gτ , λ eτ +1 Set Hτ +1 = 0, geτ +1 = 0 τ ←τ +1

where u eτ ∈ arg minu∈{ut :t∈Iτ } ∥u∥ is any minimum-norm comparator in epoch τ ∈ E[a,b] , w eτ e and λP τ are respectively the action played by A and the movement coefficient in epoch τ , and geτ = t∈Iτ gt with gt ∈ ∂ft (wt ) for all t ∈ [T ]. Proof. Let I1 , . . . , In be the epochs defined by the execution of Algorithm 5 and denote Iτ = {sτ , . . . , eτ } for each τ ∈ [n]. Given an arbitrary [a, b], we first decompose the interval into the set of complete epochs. Let E[a,b] = {τ : Iτ ⊆ [a, b]} be the set of complete epochs contained within [a, b], and denote the set of partial epochs as P[a,b] = [n] \ E[a,b] . Then by convexity of ft , we have X X ft (wt ) − ft (ut ) ≤ ⟨gt , wt − ut ⟩ t∈[a,b]

t∈[a,b]

=

X X

X

⟨gt , wt − ut ⟩ +

τ ∈E[a,b] t∈Iτ

X

⟨gt , wt − ut ⟩ .

τ ∈P[a,b] t∈Iτ ∩[a,b]

The partial epochs can each be bound using the blocking condition: X X X X ⟨gt , wt − ut ⟩ ≤ D ∥gt ∥ τ ∈P[a,b] t∈Iτ ∩[a,b]

τ ∈P[a,b]

≤

X

t∈Iτ ∩[a,b]



min{eτ −1,b−1}

D G +

X



∥gt ∥ ≤ 2D(G + λ[a,b] max ),

t=sτ

τ ∈P[a,b] [a,b] where λmax = maxt∈[a,b] λt . Hence, overall we can bound

X

⟨gt , wt − ut ⟩ ≤ 2D(G + λ[a,b] max ) +

X X

⟨gt , wt − ut ⟩ .

(4)

τ ∈E[a,b] t∈Iτ

t∈[a,b]

Focusing on the second term, we first replace the remaining comparator sequence with an epochspecific sequence (e uτ )τ with each u eτ ∈ Iτ for each τ , as follows: X X X X X X ⟨gt , wt − ut ⟩ = ⟨gt , w eτ − u eτ ⟩ + ⟨gt , u eτ − ut ⟩ τ ∈E[a,b] t∈Iτ

τ ∈E[a,b] t∈Iτ

=

X

τ ∈E[a,b] t∈Iτ

⟨e gτ , w eτ − u eτ ⟩ +

τ ∈E[a,b]

=

X X

X

X X

⟨e gτ , w eτ − u eτ ⟩ +

τ ∈E[a,b]

⟨gt , ueτ − ut ⟩

τ ∈E[a,b] t∈Iτ

| X X

+

⟨gt , u eτ − ut ⟩

τ ∈E[a,b] t∈Iτ

{z

=:A

⟨gt , u eτ − ueτ ⟩,

τ ∈E[a,b] t∈Iτ

|

{z

=:B

25

}

} (5)

where in the first line we’ve used the fact that wt = w eτ for t ∈ Iτ and the last-line adds and subtracts ueτ , the last comparator in each epoch τ . To bound A observe that * + eτ X X X A= gt , us − us−1 τ ∈E[a,b] t∈Iτ

X

=

s=t+1

eτ X

eτ X

⟨gt , us − us−1 ⟩

τ ∈E[a,b] t=sτ s=t+1

X

=

eτ X

s−1 X

⟨gt , us − us−1 ⟩

τ ∈E[a,b] s=sτ +1 t=sτ

X

≤

eτ X

τ ∈E[a,b] s=sτ +1

X

≤

eτ X

s−1 X

! ∥gt ∥ ∥us − us−1 ∥

t=sτ

λs ∥us − us−1 ∥ ≤ λ[a,b] max P[a,b]

τ ∈E[a,b] s=sτ +1

Ps−1 where the last line observes that t=sτ ∥gt ∥ ≤ λs for any s ∈ [sτ , eτ ] and over-approximates P τ ∈E[a,b] PIτ ≤ P[a,b] . The term B can be bounded by X X B= ⟨gt , u eτ − ueτ ⟩ τ ∈E[a,b] t∈Iτ

=

X

⟨e gτ , u eτ − ueτ ⟩

τ ∈E[a,b]

≤

X

∥e gτ ∥∥e u τ − u eτ ∥

τ ∈E[a,b]

≤

X

(G + λτ )∥e uτ − ueτ ∥ ≤ (G + λ[a,b] max )P[a,b]

τ ∈E[a,b]

where the last line uses that ∥e gτ ∥ ≤ G + λτ by definition of the blocking condition and uses triangle Pτ −1 inequality to bound ∥e u − ueτ ∥ ≤ PIτ for any τ , and then over-approximates τba +1 PIτ ≤ P[a,b] . Therefore, plugging the bounds for A and B back into Equation (5), we have X X X ⟨gt , wt − ut ⟩ ≤ ⟨e gτ , w eτ − u eτ ⟩ + (G + 2λ[a,b] max )P[a,b] , τ ∈E[a,b] t∈Iτ

τ ∈E[a,b]

so overall, combining with Equation (4) we have X X ft (wt ) − ft (ut ) ≤ 2(D + P[a,b] )(G + λ[a,b] ⟨e gτ , w eτ − u eτ ⟩ . max ) + τ ∈E[a,b]

t∈[a,b]

The stated result follows by adding in the movement costs into the bound and observing that Pb P [a,b] e eτ − w eτ −1 ∥ + Dλmax to bound t=a+1 λt ∥wt − wt−1 ∥ ≤ τ ∈E[a,b] λτ ∥w X t∈[a,b]

ft (wt ) − ft (ut ) +

b X

λt ∥wt − wt−1 ∥ ≤ 3(D + P[a,b] )(G + λ[a,b] max ) +

X

⟨e gτ , w eτ − u eτ ⟩ .

τ ∈E[a,b]

t=a+1

P We will Palso need the following key bound. The result shows that batching based on t ∥gt ∥ rather than ∥ t gt ∥ preserves the key second-order-to-first-order property that drives our approach. Lemma F.1. For every τ ∈ [n], Algorithm 5 guarantees that  X e2 ≤ ∥e g τ ∥2 + λ 2∥gt ∥2 + 4λt ∥gt ∥ . τ +1 t∈Iτ

26

P e Proof. First observe that by definition of the reduction we have that λ = λsτ +1 ≤ t∈Iτ ∥gt ∥, P τ +1 and similarly for any τ we have by triangle inequality that ∥e gτ ∥ ≤ t∈Iτ ∥gt ∥, so both ∥e gτ ∥2 and
P 2 e2 can be bound in terms of λ τ +1 t∈Iτ ∥gt ∥ . Hence, !2 X X X X 2 2 e ∥e gτ ∥ + λ ≤2 ∥gt ∥ =2 ∥gt ∥2 + 2 ∥gt ∥∥gs ∥ τ +1

t∈Iτ

=2

X

t∈Iτ 2

∥gt ∥ + 4

t∈Iτ

≤2

X

X

∥gt ∥

t∈Iτ

∥gt ∥2 + 4

t∈Iτ

X

t∈Iτ s∈Iτ ,s̸=t

X

∥gs ∥

s∈Iτ ,s<t

λt ∥gt ∥ .

t∈Iτ

The following lemma provides a bound on the movement coefficients and aggregate losses incurred via the blocking reduction of Algorithm 5. Lemma F.2. Let τ ∈ [n] be an arbitrary epoch defined by the execution of Algorithm 5, and let Iτ = [sτ , eτ ] be the active rounds of epoch τ . Then X eτ +1 ≤ λ ∥gt ∥ ≤ λeτ + ∥geτ ∥ t∈Iτ

eτ +1 = λs Proof. The fact that λ ≤ τ +1 Moreover, observe that X

∥gs ∥ ≤

s∈Iτ

P

t∈Iτ ∥gt ∥ follows directly from definition of the algorithm.

eX τ −1

∥gs ∥ + ∥geτ ∥ ≤ λeτ + ∥geτ ∥,

s=sτ

where we’ve used the fact that prior to round eτ + 1 we had algorithm.

Peτ

s=sτ ∥gs ∥ ≤ λeτ by definition of the

Finally, the following lemma observes that under the blocking reduction, for any [a, b] we can always assume that λt ≤ bG without loss of generality. Lemma F.3. Under the blocking reduction of Algorithm 5, we may assume without loss of generality that λt ≤ G(t − 1) for any t. P Proof. By construction Algorithm 5 only plays on rounds where λt ≤ t∈Iτ ∥gt ∥ for some epoch τ , and we only pay the movement costs associated with rounds where we transition to the next epoch. Pt−1 But on round t, the largest possible value of the RHS is s=1 ∥gs ∥ ≤ (t − 1)G. Therefore, any round t with λt > G(t − 1) can never have triggered the a new epoch, so on these rounds we have wt = wt−1 and a movement cost of λt ∥wt − wt−1 ∥ = 0. Therefore under the blocking reduction, we may assume without loss of generality that no such events occur.

G

Proofs for Section 4 (Main Result)

In this section we prove our main result. The theorem is restated below for convenience. Theorem 4.2. Let Assumption 2.1 hold and let L = D(2G + 9λ). Algorithm 2 applied with base algorithms AI implementing Algorithm 4 and AMeta implementing Algorithm 1 guarantees, for any [a, b] ⊆ [T ], any ua , . . . , ub ∈ W, and any λa , . . . , λb ∈ [0, λ], that b (D + P[a,b] ) log2 (b)(G + λ) R[a,b] (ua:b , λa:b ) ≤ O (

)! q q λ log(b) + min (D2 + DP[a,b] )(G2 + Gλ)|b − a| log(b), (D2 + DP[a,b] )V[a,b] , λ where V[a,b] =

P

t∈[a,b] (∥gt ∥

2

+ λt ∥gt ∥) and P[a,b] = 27

Pb

t=a+1 ∥ut − ut−1 ∥.

Proof. We prove the main theorem in three main steps. We first show in Proposition G.1 that b] which is a geometric covering interval, we have dynamic regret of order  on any [a, q 2 e (D + P[a,b] ) P O t∈[a,b] ∥gt ∥ + λt ∥gt ∥ . We then extend the result to an arbitrary [a, b] using the standard argument due to daniely in Proposition G.2. Finally, we apply a mild q  variation of P 2 e Cutkosky [2020, Theorem 7] to obtain O (D + P[a,b] ) t∈[a,b] (∥gt ∥ + λt ∥gt ∥) on any interval [a, b]. Composing these steps proves the theorem. The following proposition shows that we obtain the correct general "shape" of the regret bound whenever we are considering an interval [a, b] which is one of the geometric covering intervals. Proposition G.1. Let I denote the set of geometric covering intervals. Under the assumptions of Theorem 4.2, for any [a, b] ∈ I, Algorithm 2 guarantees   s X  1 b (DΩ[a,b] + P[a,b] )(G + λ) + DΩ 2 + P[a,b] R[a,b] (ua:b , λa:b ) ≤ O ∥gt ∥2 + λt ∥gt ∥ [a,b] t∈[a,b]

b hides constants and doubly-logarithmic factors. where Ω[a,b] = O (log (b + 1)) and O(·) Proof. Algorithm 2 is constructed by applying the blocking reduction of Algorithm 5 followed by the expert/meta-regret decomposition in Lemma 3.1. We begin by applying the blocking reduction decomposition of Lemma 4.1. Let n be the total number of Pepochs defined during the execution of Algorithm 5, and for each τ ∈ [n] let Iτ = [sτ , eτ ], geτ = t∈Iτ gt , and let u eτ = arg mint∈Iτ ∥ut ∥ be an arbitrary minimum-norm comparator in Iτ . Then applying Lemma 4.1, we have that X R[a,b] (ua:b , λa:b ) = ft (wt ) − ft (ut ) + λt ∥wt − wt−1 ∥ t∈[a,b]

X

≤ 3(D + P[a,b] )(G + 2λ[a,b] max ) +

eτ ∥w ⟨e gτ , w eτ − u eτ ⟩ + λ eτ − w eτ −1 ∥, (6)

τ ∈E[a,b]

|

{z

}

e e ′ ′ (e R [a ,b ] ua′ :b′ ,λa′ :b′ )

where E[a,b] = {τ : Iτ ⊆ [a, b]} =: {a′ , . . . , b′ } is the set of complete epochs contained within [a, b], and the latter term defines the regret in a problem taking place over the complete epochs. Let P (I) (I) (I) w eτ = I∈I peτ,I w eτ where w eτ = wsτ and peτ,I = psτ ,I are the outputs of AI and AMeta on epoch τ (round sτ ), and observe that since the epochs are consecutive and α eτ,J = 1{sτ ∈ J}, we have α eτ,J = 1{τ ∈ [a′ , b′ ]},

τ ∈ [1, b′ ].

Thus, Lemma 3.2 applies to the epoch-level problem with horizon T = b′ , so letting AJ be the expert assigned to J = [a, b] ⊇ [sa′ , eb′ ] we have E X D (J) ea′ :b′ ) ≤ eτ ∥w e[a′ ,b′ ] (e R ua′ :b′ , λ geτ , w eτ(J) − u eτ + λ eτ(J) − w eτ −1 ∥ τ ∈E[a,b]

|

(J)

{z

}

e ′ ′) e ′ ′ (e =:R ua′ :b′ ,λ a :b [a ,b ]

X

+

α eτ,J

D

E  eMeta ∥e ℓeτ , peτ − eJ + λ pτ − peτ −1 ∥1 τ

(7)

τ ∈[1,b′ ]

{z

| eMeta = Dλ eτ and ℓeτ,I = where α eτ,i = αsτ ,i , λ τ

}

eMeta ) eMeta R (e ,λ 1:b′ [1,b′ ] J

D

(I)

geτ , w eτ

E

(J)

(I)

eτ ∥w +λ eτ (J)

(I)

−w eτ −1 ∥ for each I ∈ I,

and for notational simplicity we define in the analysis w ea′ −1 = w ea . The first term is bounded by 28

Theorem E.1 with α = D: 



′

b X

e(J)′ ′ (e 2D + ′ ′ e ′ ′ R [a ,b ] ua :b , λa :b ) ≤

∥e uτ − u eτ −1 ∥

s

X

2

τ =a′ +1

e2 ∥e gτ ∥2 + λ τ +1

t∈[a,b]

s X ≤ 2(2D + P[a,b] ) ∥gt ∥2 + 2λt ∥gt ∥, ,

(8)

t∈[a,b]

Pb′ Pb where the last line applies Lemma F.1 and bounds τ =a′ +1 ∥e uτ − u eτ −1 ∥ ≤ t=a+1 ∥ut − ut−1 ∥ via triangle inequality and over-approximating. To bound the meta-regret, we first observe that D E (I) eτ ∥w ∥ℓeτ ∥∞ ≤ max| geτ , wτ(I) + λ eτ(I) − w eτ −1 ∥| I

eτ ) ≤ D(G + 2λ) =: GMeta ≤ D(∥e gτ ∥ + λ ∞ via Lemma F.2. Moreover, by definition we have that Meta eMeta = Dλs λ . τ +1 τ +1 ≤ Dλ =: λ

Hence, setting L = 2GMeta + 5λMeta = D(2G + 9λ), we satisfy the conditions of Theorem 3.3 for ∞ each index I, so applying the guarantee yields v  ! ! u q q u Vbλ′ +1,i Vbλ′ +1,J e eMeta b Γ(ϵ) + tV λ′ R + 1 + L log + 1 , [1,b′ ] (eJ , λ1:b′ ) ≤ O b +1,J log ϵJ L ϵJ L where ! Γ(ϵ) = L 1 +

X

ϵI

I∈I ′

b X

Vbλ′ +1,J = 4L2 +

(J)

2 e (ℓeλτ,J + λ τ +1 ) ,

τ =1

and we recall the definitions D E  eMeta ∥e eMeta , ℓeλτ,J = α eτ,J ℓeτ , eJ − peτ − λ pτ − peτ −1 ∥1 + (1 − α eτ +1,J )2λ τ τ +1 e(J) = 2e eMeta . λ ατ,J α eτ +1,J λ τ τ +1 We proceed by bounding the terms VTλ+1 . ′

Vbλ′ +1,J = 4L2 +

b X

(J)

2 e (ℓeλτ,J + λ τ +1 )

τ =1 ′

= 4L2 +

b X

 2 eMeta + 2λ eMeta α eτ,J 2∥ℓeτ ∥∞ + 2λ τ τ +1

τ =1





= O L2 + (λMeta )2 +

X

eMeta )2  ∥ℓeτ ∥2∞ + (λ τ +1

τ ∈E[a,b]

 = O L2 +

 X

e 2 ) D2 (∥e gτ ∥2 + λ τ +1

τ ∈E[a,b]

 = O L2 + D2

 X t∈[a,b]

29

∥gt ∥2 + λt ∥gt ∥ 

(9)

where we’ve used L = O(G∞ + λMeta ), applied Lemma F.1 in the second-to-last line, and overapproximated the resulting partial sum. Moreover, choosing ϵ[a,b] = 1/(a2 (1 + log2 a)) for each [a, b] ∈ I, we have   X X X Γ(ϵ, u) = L ϵI + uI λbI +1 ≤ L 1 + ϵ[a,b]  I∈I

I∈I

[a,b]∈I

 = L 1 +

 X [a,b]∈I

1  ≤ 3L a2 (1 + log2 a)

P PT 1 where we’ve used that I=[a,b]∈I a2 (1+⌊log ≤ a=1 a12 ≤ π 2 /6 ≤ 2 by construction of the 2 a⌋) geometric covering intervals. Plugging these bounds back into the meta-regret bound yields v  √ u X VTλ+1,J e1:b′ ) = O eb′ Meta(eJ , λ b L + Du t R + 1 (∥gt ∥2 + λt ∥gt ∥) log LϵJ t∈[a,b]

√ + L log b L+D =O

VTλ+1,J +1 LϵJ

s X

! !

(∥gt ∥2 + λt ∥gt ∥)ΩJ + LΩJ ,

(10)

t∈[a,b]

√ where the last line defines ΩJ = Ω[a,b] = log

VT +1,J +1 LϵJ

 = O(log(b + 1)) for J = [a, b].

Thus, plugging Equations (8) and (10) back into the full regret bound in Equation (7) yields !  s X 1 2 2 ea′ :b′ ) = O e[a′ ,b′ ] (e b LΩ[a,b] + DΩ R ua′ :b′ , λ + P[a,b] ∥gt ∥ + λt ∥gt ∥ [a,b]

t∈[a,b]

and plugging this into Equation (7), R[a,b] (u[a,b] , λ[a,b] ) ≤ 3(D + P[a,b] )(G + 2λ[a,b] max ) !  s X 1 2 2 b ∥gt ∥ + λt ∥gt ∥ + O LΩ[a,b] + DΩ[a,b] + P[a,b] t∈[a,b]



 

1 2

b (DΩ[a,b] + P[a,b] )(G + λ) + DΩ =O [a,b] + P[a,b]

s X

∥gt ∥2 + λt ∥gt ∥

t∈[a,b]

where we’ve recalled that L = O(G + λ). Next we extend the previous proposition to hold on an arbitrary [a, b] ⊆ [1, T ]. Proposition G.2. Under the same conditions as Proposition G.1, for any [a, b] ⊆ [1, T ] R[a,b] (u[a,b] , λ[a,b] ) is bounded above by b O

DΩ[a,b] log(b − a) + P[a,b] (G + λ) ( )! s  p X 2 + DΩ[a,b] + P[a,b] G(G + λ)|b − a| ∧ log(b − a) ∥gt ∥ + λt ∥gt ∥ 

1 2

t∈[a,b]

were Ω[a,b] = O(log(b + 1)). 30

Proof. Using Lemma I.2, we have that there exists a partition of [a, b] into disjoint intervals I−p , . . . , I0 , I1 , . . . , Iq such that |I−i |/|I−i+1 | ≤ 12 for each i ≥ 1 and |Ii |/|Ii−1 | ≤ 12 for i ≥ 2. Note that this also implies that there are at most p + q + 1 = O(log(b − a)) total intervals in the partition. Denote each interval by Ik = [sk , ek ] and observe that X R[a,b] (ua:b , λa:b ) = ft (wt ) − ft (ut ) + λt ∥wt − wt−1 ∥ t∈[a,b]

=

q X X

ft (wt ) − ft (ut ) + λt ∥wt − wt−1 ∥

k=−p t∈Ik

=

q X

ek X

k=−p

t=sk

ft (wt ) − ft (ut ) +

≤

! λk ∥wt − wt−1 ∥ +

t=sk +1

q X

λsk ∥wsk − wsk−1 ∥

k=−p

{z

| q X

ek X

}

=:RIk

RIk + Dλ(p + q + 1).

k=−p

Hence, applying Proposition G.1 to bound each RIk and recalling that p + q + 1 = O(log(b − a)), we can bound q X b Dλ log(b − a) + R[a,b] (ua:b , λa:b ) ≤ O (DΩIk + PIk )(G + λ) k=−p q X

+

1 2

(DΩ[a,b] + P[a,b] )

sX

! ∥gt ∥2 + λt ∥gt ∥

t∈Ik

k=−p

DΩ[a,b] log(b − a) + P[a,b] (G + λ)

b ≤O

1 2

+ (DΩ[a,b] + P[a,b] )

q sX X k=−p

! ∥gt ∥2 + λt ∥gt ∥

t∈Ik

The last term we can bound in two different ways. On one hand, via Cauchy-Schwarz inequality we have v u q sX q X X X u ∥gt ∥2 + λt ∥gt ∥ ≤ tlog (b − a) ∥gt ∥2 + λt ∥gt ∥ k=−p

t∈Ik

k=−p t∈Ik

s X = log (b − a) ∥gt ∥2 + λt ∥gt ∥. t∈[a,b]

On the other hand, using the properties that |I−i+1 |/|I−i | ≤ 12 and |Ii |/|Ii−1 | ≤ 12 we can bound   q q sX 0 X X X p |Ik | + |Ik | ∥gt ∥2 + λt ∥gt ∥ ≤ G(G ∨ λ)  k=−p

t∈Ik

k=−p

k=1

∞ X p p 1 ≤ 2 G(G ∨ λ) (2−i |b − a|) 2 ≤ 8 G(G ∨ λ)|b − a|. k=0

Combining the two bounds, we have b R[a,b] (ua:b , λa:b ) ≤ O 1 2

DΩ[a,b] log(b − a) + P[a,b] (G + λ)

+ (DΩ[a,b] + P[a,b] ) min

 p

G(G + λ)|b − a|,



s

log(b − a)

X t∈[a,b]

31

!  . ∥gt ∥2 + λt ∥gt ∥ 

Finally, qP the following proposition shows that since we have O((D + T 2 P[a,b] ) t=1 ∥gt ∥ + λt ∥gt ∥ dynamic regret on every simultaneously, we also have the q P optimal O( (D2 + DP[a,b] ) t∈[a,b] ∥gt ∥2 + λt ∥gt ∥) on any sub-interval as well. Proposition G.3. Under the same conditions as Proposition G.2, Algorithm 2 guarantees b (D + P[a,b] ) log(b)2 (G + λ) R[a,b] (ua:b , λa:b ) ≤ O ( q

+ min s

(D2 + DP[a,b] )G(G + λ)|b − a| log (b), )!

(D2 + DP[a,b] )

X

∥gt ∥2 + λt ∥gt ∥ log (b)

,

t∈[a,b]

b = G + λ. By Lemma I.1 there is a partition I1 , . . . , IK of [a, b] such Proof. For brevity denote L that D ≤ PIk ≤ 2D for each k and K ≤ 1 + P[a,b] /D. Denoting each interval by Ik = [sk , ek ], we have X X X R[a,b] (ua:b , λa:b ) ≤ ⟨gt , wt − ut ⟩ + λt ∥wt − wt−1 ∥ k∈[K] t∈Ik

=

t∈Ik

X

X

k∈[K]

t∈Ik

⟨gt , wt − ut ⟩ +

X

! λt ∥wt − wt−1 ∥

t=sk +1

| +

ek X

{z

}

=:RIk

λsk ∥wsk − wsk−1 ∥

k∈[K]

X

≤

RIk + KDλ

k∈[K]

b we have so applying Proposition G.2 to bound each of the RIk and recalling λ ≤ L, b KDλ + R[a,b] (ua:b , λa:b ) ≤ O

X

b (DΩIk log(b − a) + PIk ) L

k∈[K]

X

1 2 Ik

(DΩ

 ! s q  X b + PIk ) min LG|I log(b − a) ∥gt ∥2 + λt ∥gt ∥ k |,   t∈Ik

k∈[K]

b KDΩ[a,b] log(b − a)L b ≤O 1 2

+ DΩ min

 X q 

k∈[K]

!  X s X b LG|I log(b − a) ∥gt ∥2 + λt ∥gt ∥ k |,  k∈[K]

t∈Ik

b KDΩ[a,b] log(b − a)L b =O  ! s q  X b + DΩ[a,b] min K LG|b − a|, K log(b − a) ∥gt ∥2 + λt ∥gt ∥   1 2

t∈[a,b]

32

b = G + λ: and recalling K ≤ 1 + P[a,b] /D and L

b (D + P[a,b] )Ω[a,b] log(b − a)(G + λ) =O ( + min s

q (D2 + DP[a,b] )G(G + λ)|b − a|Ω[a,b] , )!

(D2 + DP[a,b] )Ω[a,b] log(b − a)

X

∥gt ∥2 + λt ∥gt ∥

t∈[a,b]

b (D + P[a,b] ) log(b)2 (G + λ) =O ( + min s

q (D2 + DP[a,b] )G(G + λ)|b − a| log (b), )!

(D2 + DP[a,b] )

X

∥gt ∥2 + λt ∥gt ∥ log (b)

,

t∈[a,b]

where we have used that Ω[a,b] = O(log (b + 1))) (which we bound by O(log(b)) for brevity).

H

Proofs for Section 5 (Applications)

H.1

Details for Delayed Feedback

To facilitate the presentation of our results, we begin by introducing some standard notation for OCO with delayed feedback. For each round t, let ot ≜ {τ ∈ Z+ : τ + dτ < t} ⊆ [t − 1] denote the set of past rounds whose gradients have already been observed before round t. We further define mt ≜ [t − 1] \ ot as the set of past rounds whose gradients are still outstanding before round t. Under this notation, the delayed-feedback protocol is equivalently described by saying that, at the end of round t, the learner receives the batch of newly available gradients {gτ }τ ∈ot+1 \ot . We also define σmax ≜ maxt∈[T ] |mt | to be the maximum number of outstanding gradients at any round, and PT dtot ≜ t=1 dt to be the total delay over the time horizon. We now extend the above notation so as to capture dependencies on the sequence of delays restricted to a certain time interval [a, b] ⊆ [T ]; this is of course required in order to state our strongly adaptive regret guarantees. In particular, for [a,b] [a,b] [a,b] [a,b] every t ∈ [T + 1], we let ot = ot ∩ [a, b], mt = mt ∩ [a, b], and σmax = maxt∈[a,b] |mt | denote the respective quantities restricted to interval [a, b]. We also introduce the interval-restricted [a,b] delays as dt = min{dt , b − t} for every t ∈ [a, b], and the total delay for the same interval as P [a,b] [a,b] b dtot = t=a dt . Lemma H.1. For any sequence of delays,

[a,b] [1,a−1] 2 ) . t∈[a,b] |mt | · |ot+1 \ ot | ≤ 2dtot + 3(dmax

P

33

[1,a−1]

Proof. Begin by observing that |ma | ≤ dmax . Now, using similar calculations as in the proof of Qiu et al. [2026, Lemma D.1], we can show that X X |mt | · |ot+1 \ ot | = |mt | · (1 + |mt | − |mt+1 |) (|ot+1 \ ot | = |mt | + 1 − |mt+1 |) t∈[a,b]

t∈[a,b]

=

X

X

b X

|mt | +

X

(|mt | − |mt−1 |)|mt | + |ma |2

t=a+1

t∈[a,b]

≤2

(|mt | − |mt−1 |)|mt |

t=a+1

t∈[a,b]

≤

b X

|mt | + |ma |2 − |mb | · |mb+1 | +

|mt | + |ma |2

t∈[a,b]

≤2

X

|mt | + (d[1,a−1] )2 , max

t∈[a,b]

where the second inequality uses the fact that |mt | ≤ |mt−1 | + 1. Focusing on the sum from the first term at the right-hand side, we can bound it from above as X X X [a,b] [a,b] |mt | = |mt | + (|mt \ mt |) t∈[a,b]

t∈[a,b]

=

X

t∈[a,b] [a,b] |mt | +

t∈[a,b]

=

X X

[a,b]

|mt

|+

X

X

(min{t + dt , b} − a + 1)

t∈ma [a,b]

|mt

|+

X

(t ≤ a − 1 for t ∈ ma )

dt

t∈ma

t∈[a,b]

≤

(|mt \ [a, b]|)

t∈[a,b]

t∈[a,b]

≤

X

[a,b]

| + |ma |d[1,a−1] max

[a,b]

| + (d[1,a−1] )2 max

|mt

t∈[a,b]

≤

X

|mt

t∈[a,b] [a,b]

= dtot + (d[1,a−1] )2 . max Finally, combining all the above inequalities, we conclude the proof. The following lemma now provides a reduction from delayed feedback to OCO with movement costs. The result generalizes the reduction of Qiu et al. [2026] to hold on arbitrary intervals. Lemma 5.1. Let Assumption 2.1 hold and let [a, b] ⊆ [T ] be any interval. Then del R[a,b] (ua:b ) ≤ G(2D + P[a,b] )σ +

b X

⟨ht , wt − ut ⟩ +

t=a

where ht =

b X

λt ∥wt − wt−1 ∥,

t=a+1

P

τ ∈ot+1 \ot gτ and λt = G|mt |.

Proof. Let F[a,b] = {t ∈ [a, b] : t + dt ≤ b} denote the set of rounds whose feedback is received by the end of the interval. By convexity and Assumption 2.1, we have X del R[a,b] (ua:b ) ≤ ⟨gt , wt − ut ⟩ t∈[a,b]

≤

X

[a,b]

⟨gt , wt − ut ⟩ + GD|mb+1 |,

t∈F[a,b]

34

[a,b]

[a,b]

where mb+1 = mb+1 ∩ [a, b]. Indeed, the second inequality follows because [a, b] \ F[a,b] = mb+1 . Now, for each t ∈ F[a,b] , the gradient gt is revealed by round b, so applying Qiu et al. [2026, Lemma 5.1] over the time range [a, b] yields X

b b X X [a,b] [a,b] ⟨gt , wt − ut ⟩ ≤ ⟨e gt , wt − ut ⟩ + G |mt |∥wt − wt−1 ∥ + Gσmax P[a,b] , t=a

t∈F[a,b]

t=a+1

[a,b] [a,b] [a,b] gτ and σmax τ ∈ot+1 \ot [a,b] displays and using |mt | ≤ |mt | gives

where get =

P

del R[a,b] (ua:b ) ≤

[a,b]

= maxt∈[a,b] |mt

|. Hence, combining previous two

b b X X ⟨e gt , wt − ut ⟩ + G |mt |∥wt − wt−1 ∥ t=a

t=a+1

[a,b] [a,b] + Gσmax P[a,b] + GD|mb+1 |

≤D

b X

∥e g t − ht ∥ +

t=a

b b X X ⟨ht , wt − ut ⟩ + G |mt |∥wt − wt−1 ∥ t=a

t=a+1

[a,b+1] + G(D + P[a,b] )σmax

Now, let T[a,b] = {t < a : a ≤ t + dt ≤ b} = ma \ mb+1 be the set of rounds before the beginning of the interval [a, b] such that their arrival time falls inside that same interval. For each t, also define S [a,b] [a,b] [a,b] [a,b]
Ft = ot+1 \ ot and Ft = ot+1 \ ot . Observe that T[a,b] = t∈[a,b] Ft \ Ft and thus, by the triangle inequality, b b X X ∥e g t − ht ∥ = t=a

X

gτ ≤

t=a τ ∈F \F [a,b] t t

X

=

b X

X

∥gτ ∥

t=a τ ∈F \F [a,b] t

t

∥gτ ∥ ≤ G|T[a,b] | = G|ma \ mb+1 | .

t∈T[a,b]

Then, plugging the above inequalities into the first math display yields the claim: del R[a,b] (ua:b ) ≤

b X

⟨ht , wt − ut ⟩ + G

t=a

b X

|mt |∥wt − wt−1 ∥

t=a+1

[a,b+1] + G(D + P[a,b] )σmax + GD|ma \ mb+1 |.

(11)

a,b+1 The stated result follows by bounding σmax ≤ σ and |ma \ mb+1 | ≤ |ma | ≤ σ.

We finally have all the main ingredients to prove the strongly adaptive regret upper bound for OCO with delayed feedback. Theorem 5.2. Let Assumption 2.1 hold and let H ≥ G maxt |ot+1 \ ot |. Initializing Algorithm 2 P from Theorem 4.2 with Lipschitz constant H, and feeding it gradients ht = τ ∈ot+1 \ot gτ and movement coefficients λt = G|mt |, guarantees for any [a, b] ⊆ [T ] and any ua , . . . , ub ∈ W that del b (D + P[a,b] ) log (b)2 Lσ,a R[a,b] (ua:b ) ≤ O

q +G [1,a−1]

where Lσ,a = H ∨ G σ + dmax

! [a,b]
(D2 + DP[a,b] ) |b − a| + dtot log (b)

and P[a,b] =

Pb

35

t=a+1 ∥ut − ut−1 ∥.

,

Proof of Theorem 5.2. We first apply the delays-to-movement-costs reduction of Lemma 5.1, which yields X

del R[a,b] (ua:b ) ≤ G(2D + P[a,b] )σ +

|

λt ∥wt − wt−1 ∥

t=a+1

t∈[a,b]

where we recall that ht =

b X

⟨ht , wt − ut ⟩ + {z

}

e[a,b] (ua:b ,λa:b ) =:R

P

τ ∈ot+1 \ot gτ and λt = G|mt |. Note that each vector ht satisfies

∥ht ∥ ≤ G|ot+1 \ ot | ≤ G(|mt | + 1) ≤ G(σ + 1) ≤ H e[a,b] (ua:b , λa:b ) is the regret by the triangle inequality and Assumption 2.1. Moreover, observe that R over [a, b] for the time-varying movement-costs problem with linear losses given by ht and movement coefficients given by λt = G|mt | ≤ Gσ. Consequently, we can apply Theorem 4.2 to obtain that, for any interval [a, b] ⊆ [T ], e[a,b] (ua:b , λa:b ) ≤ O b (D + P[a,b] ) log(b)2 (H + Gσ) R s +

! (D2 + DP[a,b] )

X

∥ht ∥2 + λt ∥ht ∥ log (b)

.

t∈[a,b]

P Next, we bound the data-dependent terms t∈[a,b] ∥ht ∥2 + λt ∥ht ∥. First, observe that X |ot+1 \ ot | = |ob+1 \ oa | ≤ |b − a + 1| + |ma | ≤ |b − a + 1| + d[1,a−1] . max t∈[a,b]

Moreover, we can also show that X [a,b] |mt | · |ot+1 \ ot | ≤ 2dtot + 3(d[1,a−1] )2 max t∈[a,b]

via Lemma H.1. Using both of these facts allows us to derive that X X
∥ht ∥2 + λt ∥ht ∥ ≤ G2 |ot+1 \ ot | |ot+1 \ ot | + |mt | t∈[a,b]

t∈[a,b]

X

2

≤G

|ot+1 \ ot | 2|mt | + 1

t∈[a,b] 2

≤ 7G



[a,b]

|b − a + 1| + dtot + (d[1,a−1] )2 max



.

Therefore, s

(D2 + DP[a,b] )

X

∥ht ∥2 + λt ∥ht ∥

t∈[a,b]

 q  [a,b] [1,a−1]
≤ O G (D2 + DP[a,b] ) |b − a| + dtot + (dmax )2  q  [a,b]
[1,a−1] 2 = O G (D + DP[a,b] ) |b − a| + dtot + G(D + P[a,b] )dmax . Combining everything together finally yields del b (D + P[a,b] ) log (b)2 [H ∨ G(σ + d[1,a−1] R[a,b] (ua:b ) ≤ O )] max

q +G [1,a−1]

Defining Lσ,a = H ∨ G(σ + dmax

! [a,b]
(D2 + DP[a,b] ) |b − a| + dtot log (b)

) completes the proof. 36

,

H.2

Details for Time-Varying Memory

In this section we provide additional details for our results on OCO with time-varying memory. The following two lemmas provide inequalities basically proving that the memory dependencies relative to rounds beyond the current interval [a, b] are sufficiently small and do not largely affect the overall guarantees when fully restricting to [a, b] only. Lemma H.2. For any sequence of memory sizes and any time interval [a, b] ⊆ [T ], X [a,b]
2 bt − b t ≤ B[a,b] . t∈[a,b]

Proof. Let T[a,b] = {t ∈ [a, b] : t − bt ≤ a − 1} be the set of rounds in the interval [a, b] whose unclipped memory begins strictly before the first round a of the interval. Note that, for any t ∈ [a, b], [a,b] we have that bt − bt > 0 if and only if t ∈ T[a,b] . Furthermore, observe that the cardinality of T[a,b] satisfies T[a,b] =

b X

b X  I t ≤ a − 1 + B[a,b] = B[a,b] .

I{t − bt ≤ a − 1} ≤

t=a

t=a

Therefore, b X t=a

[a,b]

bt − bt

X

=

[a,b]

bt − b t

2 ≤ T[a,b] B[a,b] ≤ B[a,b] .

t∈T[a,b]

Lemma H.3. For any sequence of memory sizes and any b ∈ [T − 1], T X   2 bs − (s − b) + ≤ B[b+1,T ] , s=b+1

where [·]+ = max{·, 0} denotes the positive real part. Proof. By direct calculations, we can show that T T X X  
bs − (s − b) + = bs − (s − b) I{b ≥ s − bs } s=b+1

s=b+1

≤

T X

B[b+1,T ] − (s − b) I{b ≥ s − B[b+1,T ] }

s=b+1 b+B[b+1,T ]

≤

X

B[b+1,T ] − (s − b)

s=b+1 B[b+1,T ]

≤

X

B[b+1,T ] − i

i=1 2 ≤ B[b+1,T ] .

The first main result we require is an extension of Qiu et al. [2026, Lemma 5.6] to the analogous memory-to-movements reduction over any time interval. Lemma 5.6. Let Assumptions 5.4 and 5.5 hold, and let [a, b] ⊆ [T ] be any interval. Then mem 2 2 R[a,b] (u1:T ) ≤ GP[a,b] (b[a,b] max ) + 2GDB[a,b] +

b X t=a

PT  where ht = ∇fbt (wt ), ξt = s=t I t ≥ s − bs + 1 37

⟨ht , wt − ut ⟩ +

b X

λt ∥wt − wt−1 ∥ ,

t=a+1

t − s − bs , and λt = Gξt .

 Pb [a,b] [a,b] Proof of Lemma 5.6. For any t ∈ [a, b], let ξt ≜ s=t I t ≥ s − bs + 1 We then use the fact that Assumption 5.4 holds to show that ft (wt−bt :t ) − fbt (wt ) ≤ G

[a,b]

t − s − bs

.

bt X ∥wt − wt−i ∥ i=0 [a,b]

bt

X

≤G

[a,b]

∥wt − wt−i ∥ + GD bt − bt

i=0 [a,b]

bt

i−1 XX

≤G

[a,b]

∥wt−j − wt−j−1 ∥ + GD bt − bt

i=0 j=0 [a,b]

bt

≤G

X

[a,b]

(bt − i + 1)∥wt−i+1 − wt−i ∥ + GD bt − bt

i=1

and thus, summing over t ∈ [a, b], we have b X

ft (wt−bt :t ) − fbt (wt )

t=a [a,b]

≤G

b bX t X

(bt − i + 1)∥wt−i+1 − wt−i ∥ + GD

t=a i=1

=G

=G

b X

t=a+1

s=t [a,b]

ξt

!  I t ≥ s − b[a,b] +1 s

≤G

s − b[a,b] s

t−

∥wt − wt−1 ∥ + GD

b X

[a,b]

bt − b t

t=a

∥wt − wt−1 ∥ + GD

b X

[a,b]

bt − b t

t=a

t=a+1 b X

[a,b]

bt − b t

t=a

b X

b X

b X

[a,b]

ξt

2 ∥wt − wt−1 ∥ + GDB[a,b] ,

t=a+1

where the last steps follows by Lemma H.2. Using similar ideas as in the proof of Qiu et al. [2026, Lemma 5.6], we can also show that, for each t ∈ [a, b], [a,b] = ξt

b X  I t ≥ s − b[a,b] +1 s

t−

s − b[a,b] s

=

s=t

b X 

t − s − b[a,b] s

 +

s=t [a,b]

bmax −1 [a,b] b h i X X
b[a,b]
2 max bmax + 1 [a,b] [a,b] ≤ bmax − (s − t) ≤ bmax − i = ≤ b[a,b] , max 2 + s=t i=0

(12)

where [·]+ = max{·, 0} denotes the positive part of any given real number, and the last inequality [a,b] holds because bmax is a non-negative integer. Combining the above inequalities then yields b X

ft (wt−bt :t ) − fbt (wt ) ≤ G

t=a

b X

[a,b]

ξt

2 ∥wt − wt−1 ∥ + GDB[a,b]

t=a+1

≤G

b X t=a+1

38

2 ξt ∥wt − wt−1 ∥ + GDB[a,b] ,

[a,b]

≤ bt for all t ∈ [a, b]. Via a similar derivation, we

where the last inequality holds because bt additionally have that b X

ft (ut−bt :t ) − fbt (ut ) ≤ G

t=a

b X

[a,b]

ξt

2 ∥ut − ut−1 ∥ + GDB[a,b]

t=a+1

≤ GP[a,b] b[a,b] max

2

2 + GDB[a,b] .

Finally, combining the various inequalities shown so far, we can derive that mem R[a,b] (u1:T ) =

b X

b b
X
X
fbt (wt ) − fbt (ut ) + ft (wt−bt :t ) − fbt (wt ) − ft (ut−bt :t ) − fbt (ut )

t=a

≤

b X

t=a

⟨ht , wt − ut ⟩ +

t=a

≤

b X

b X

t=a

ft (wt−bt :t ) − fbt (wt ) +

t=a

⟨ht , wt − ut ⟩ + G

t=a

b X

ft (ut−bt :t ) − fbt (ut )

t=a b X

ξt ∥wt − wt−1 ∥ + GP[a,b] b[a,b] max

2

2 , + 2GDB[a,b]

t=a+1

which concludes the proof. We can finally leverage this technical result to prove the main strongly adaptive regret guarantee for the setting of OCO with time-varying memory. Theorem 5.7. Initializing Algorithm 2 from Theorem 4.2 with Lipschitz constant H and λ ≥ GB 2 , and feeding it gradients ht = ∇fbt (wt ) and movement coefficients λt = Gξt where ξt is defined as in Lemma 5.6, guarantees for any [a, b] ⊆ [T ] and any u1 , . . . , uT ∈ W that ! r n o p
(1) (2) mem 2 e (D + P[a,b] ) H + G(H ∨ G)B + (D2 + DP[a,b] ) min V , R (u1:T ) ≤ O ,V [a,b]

[a,b]

[a,b]

  Pb P (1) where P[a,b] = t=a+1 ∥ut − ut−1 ∥, and we define V[a,b] = O (H + GB 2 ) t∈[a,b] ∥ht ∥ , and P n o P (2) [a,b]
2 2 2 4 V[a,b] = O . t∈[a,b] ∥ht ∥ + HG min B |b − a|, B + t∈[a,b] bt Proof of Theorem 5.7. As the initial step, we apply Lemma 5.6. For any interval [a, b] ⊆ [T ], this gives mem R[a,b] (u1:T ) ≤ GP[a,b] b[a,b] max

2

2 + 2GDB[a,b] +

X

b X

⟨ht , wt − ut ⟩ +

|

λt ∥wt − wt−1 ∥ ,

t=a+1

t∈[a,b]

{z

}

e[a,b] (ua:b ,λa:b ) ≜R

(13) where we define the movement coefficients as λt ≜ Gξt ≤ GB 2 , whereas ht = ∇fbt (wt ) satisfies e[a,b] (ua:b , λa:b ) is the regret over [a, b] for the time∥ht ∥ ≤ H by Assumption 5.5. Observe that R varying movement-costs problem with linear losses given by ht and movement coefficients given by λt . Applying Theorem 4.2 to this time-varying movement-costs problem yields e[a,b] (ua:b , λa:b ) = O b (D + P[a,b] ) log (b)2 (H + GB 2 ) R s +

! (D2 + DP[a,b] )

X t∈[a,b]

39

(∥ht ∥2 + λt ∥ht ∥) log (b)

,

(14)

It remains to bound the cumulative interval-local movement coefficients. On one hand, observe that for λt = Gξt ≤ GB 2 and ∥ht ∥ ≤ H ≤ G(B + 1) (by Assumption 5.4), we can always bound X X ∥ht ∥2 + λt ∥ht ∥ ≤ (H + GB 2 ) ∥ht ∥ (15) t∈[a,b]

t∈[a,b]

|

{z

}

(1) =:V[a,b]

On the other hand, we can alternatively bound X X X ∥ht ∥2 + λt ∥ht ∥ ≤ ∥ht ∥2 + GH ξt . t∈[a,b]

t∈[a,b]

(16)

t∈[a,b]

By the definition of ξt , and using similar calculations as in the proof of Qiu et al. [2026, Theorem 5.7], we have b b X T X X
ξt = I{t ≥ s − bs + 1} t − (s − bs ) t=a

t=a s=t

=

T min{b,s} X X s=a

=

I{t ≥ s − bs + 1} t − (s − bs )

t=a min{b,s}

T X

X

t − (s − bs ) ,

s=a t=max{a,s−bs +1}

where empty sums are treated as zero. We split the last expression into the terms with s ≤ b and s > b. For a ≤ s ≤ b, we have min{b, s} = s, and hence s s X X

bs (bs + 1) ≤ b2s . (17) t − (s − bs ) ≤ t − (s − bs ) = 2 t=s−bs +1

t=max{a,s−bs +1}

For s > b, we have min{b, s} = b. The corresponding sum is nonzero only if s − bs + 1 ≤ b, or equivalently bs > s − b. In this case, the summand ranges over at most the values 1, . . . , bs − (s − b). Therefore, [bs −(s−b)]+ b X X
 2 t − (s − bs ) ≤ i ≤ bs − (s − b) + . i=1

t=max{a,s−bs +1}

Combining the two bounds gives b X

ξt ≤

t=a

b X

T X 

b2s +

s=a

2 bs − (s − b) + .

s=b+1

To further bound the two terms in Equation (18), direct calculation shows that X X [a,b]
2 X [a,b]
2 b2t ≤ 2 bt +2 bt − bt t∈[a,b]

t∈[a,b]

≤2

X

t∈[a,b]

 2 X

2 [a,b] [a,b]  bt + 2 bt − b t t∈[a,b]

t∈[a,b]

≤2

X

[a,b]
2 4 bt + 2B[a,b] ,

t∈[a,b]

where we used Lemma H.2 at the last step. For the second term in Equation (18), T T X X  2     bs − (s − b) + ≤ max bs − (s − b) + · bs − (s − b) + s=b+1

s∈[b+1,T ]

s=b+1

T X   ≤ B[b+1,T ] bs − (s − b) + s=b+1 2 ≤ B[b+1,T ] · B[b+1,T ] 3 = B[b+1,T ] .

40

(18)

relying once more on Lemma H.3. Hence, we can bound X X λt ∥ht ∥ ≤ HG ξt t∈[a,b]

t∈[a,b]

! X

≤ HG

3 b2t + B[b+1,T ]

t∈[a,b]

X

≤ 2HG

[a,b]
2

bt

3 4 + HGB[b+1,T + 2HGB[a,b] ]

t∈[a,b]

X

≤ 3HGB 4 + 2HG

[a,b]
2

bt

.

t∈[a,b]

We can also naively bound X

λt ∥ht ∥ ≤ HG

t∈[a,b]

X

ξt ≤ HGB 2 |b − a + 1|.

t∈[a,b]

Hence, X

∥ht ∥2 + λt ∥ht ∥

t∈[a,b]

 

 

[a,b] ≤ ∥ht ∥2 + min HGB 2 |b − a + 1|, 3HGB 4 + 2HG (bt )2   t∈[a,b] t∈[a,b]

X

X

{z

|

(19)

}

(2)

=:V[a,b]

Therefore, combining Equations (17) and (19), we have n o (1) (2) min V[a,b] , V[a,b] . Plugging this back into Equation (14) yields

P

t∈[a,b] ∥ht ∥

e[a,b] (ua:b , λa:b ) = O b (D + P[a,b] ) log(b)2 (H + GB + R r +

(D2 + DP[a,b] )

h

√

(1) (2) V[a,b] ∧ V[a,b]

i

+ λt ∥ht ∥

≤

HGB 2 ) !

log(b),

and likewise plugging this into Equation (13) yields the stated guarantee: h i √ mem b (D + P[a,b] ) H + GB + GB 2 + HGB 2 log2 (b) R[a,b] (u1:T ) = O r +

(D2 + DP

! n o (1) (2) [a,b] ) min V[a,b] , V[a,b] log(b)

h i p b (D + P[a,b] ) H + G(H ∨ G)B 2 log2 (b) =O r +

I

(D2 + DP

! n o (1) (2) [a,b] ) min V[a,b] , V[a,b] log(b)

Supporting Lemmas

The following lemma follows from Cutkosky [2020, Theorem 7], and is provided for completeness; √ we extract the key partition from their argument, the existence of which lets us improve P[a,b] b − a p dependencies to P[a,b] (b − a) dependencies. 41

Pb Lemma I.1. For any [a, b] and comparator sequence ua , . . . , ub in W with t=a+1 ∥ut −ut−1 ∥ ≥ D, there is a disjoint set of sub-intervals I1 , . . . , IK such that the following hold: SK 1. [a, b] = k=1 Ik 2. PIk ≤ 2D, ∀k ∈ [K] and PIk ≥ D for k ∈ [K − 1] 3. K ≤ 1 +

P[a,b] D

Proof. The proof follows the same argument to Cutkosky [2020, Theorem 7], which constructs the partition using an iterative greedily construction, and is included for completeness. Let Ik = [sk , ek ] for any k ∈ [K]. Starting from s1 = a, let e1 be the smallest index such that P[a,e1 ] ≥ D. This implies that P[1,e1 −1] ≤ 2D, hence we have D ≤ P[1,e1 ] ≤ 2D. Let s2 = e1 + 1 and let e2 be the first round such that P[s2 ,e2 ] ≥ D (If no such e2 exists then we may set e2 = b). Continuing on this way until we hit the right end-point of the interval ensures that for all k ∈ [K − 1] we have D ≤ PIk ≤ 2D. Hence, we have X P[a,b] ≥ PIk ≥ D(K − 1), k∈[K]

and re-arranging, we have the last property: 1+

P[a,b] ≥ K. D

The greedy construction can also be easily seen to ensure that

S

k∈[K] Ik = [a, b].

We borrow the following standard lemma due to Daniely et al. [2015], which shows that the geometric covering intervals imply the existence of a partition which has a certain doubling property. Lemma I.2 (Adapted from Daniely et al., 2015, Lemma 1.2). For any interval [r, s] ⊆ [T ], it can be partitioned into two sequences of disjoint and consecutive intervals, denoted by I−p , . . . , I0 ∈ D and I1 , . . . , Iq ∈ D, such that |I−i | / |I−i+1 | ≤ 1/2, ∀i ≥ 1 and |Ii | / |Ii−1 | ≤ 1/2, ∀i ≥ 2 . The following provides a standard inequality used to bound the stability terms in the proof of Theorem 3.3, and borrowed from Jacobsen and Cutkosky [2022]. Pt−1 Lemma I.3 (Jacobsen and Cutkosky, 2022, Lemma 9). Let Vt ≥ 4L2 + s=1 ∥gs ∥2 where ∥gt ∥ ≤ L for each t ∈ [T ]. Then T X ∥gt ∥2 ≤2 √ Vt log2 t=1

42

NeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: Each of the claims in the abstract are supported by new regret guarantees for which we provide detailed proofs. Guidelines: • The answer [N/A] means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 2. Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Limitations and open questions of our results are discussed in Section 6. Guidelines: • The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate “Limitations” section in their paper. • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory assumptions and proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] 43

Justification: The assumptions are stated explicitly in Section 2 or directly in the theorem statements. The part about loss functions with time-varying memory requires specialized assumptions, which are explicitly stated and referred to in the respective Section 5.2. Guidelines: • The answer [N/A] means that the paper does not include theoretical results. • All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 4. Experimental result reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [N/A] Justification: This paper does not include experiments. Guidelines: • The answer [N/A] means that the paper does not include experiments. • If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code 44

Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [N/A] Justification: This paper does not include experiments requiring code. Guidelines: • The answer [N/A] means that paper does not include experiments requiring code. • Please see the NeurIPS code and data submission guidelines (https://neurips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //neurips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results? Answer: [N/A] Justification: This paper does not include experiments. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment statistical significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [N/A] Justification: This paper does not include experiments. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) 45

• The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates). • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [N/A] Justification: This paper does not include experiments. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper). 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: The authors have reviewed the NeurIPS Code of Ethics and confirmed that the research conducted in the paper conforms to it. Guidelines: • The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics. • If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [N/A] Justification: The paper is a foundational work concerning online optimization theory; we do not anticipate any direct negative societal consequences. Guidelines: • The answer [N/A] means that there is no societal impact of the work performed. • If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact. 46

• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)? Answer: [N/A] Justification: The paper poses no such risks. Guidelines: • The answer [N/A] means that the paper poses no such risks. • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [N/A] Justification: The paper does not use existing assets. Guidelines: • The answer [N/A] means that the paper does not use existing assets. • The authors should cite the original paper that produced the code package or dataset. • The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset. • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 47

• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset’s creators. 13. New assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [N/A] Justification: The paper does not introduce new assets. Guidelines: • The answer [N/A] means that the paper does not release new assets. • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [N/A] Justification: The paper does not involve crowdsourcing nor research with human subjects. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [N/A] Justification: The paper does not involve crowdsourcing nor research with human subjects. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 48

16. Declaration of LLM usage Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required. Answer: [N/A] Justification: The core development of this research does not involve LLMs as any important, original, or non-standard components. Guidelines: • The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components. • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.

49

Related documents

• Strongly Adaptive Online Learning with Time-Varying Movement Costs#1448256
• Convex Optimization Is Free When Accuracy Is Expensive#1130006
• Small Gradient Norm Regret for Online Convex Optimization#1049744
• Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm#1202425
• Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds#1356918