An Equivalence Between Static and Dynamic Regret Minimization

Authors: andrew  jacobsen
francesco  orabona
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 15:26:50

Abstract: We study the problem of dynamic regret minimization in online convex optimization, in which the objective is to minimize the difference between the cumulative loss of an algorithm and that of an arbitrary sequence of comparators. While the literature on this topic is very rich, a unifying framework for the analysis and design of these algorithms is still missing. In this paper we show that /for linear losses, dynamic regret minimization is equivalent to static regret minimization in an extended decision space/. Using this simple observation, we show that there is a frontier of lower bounds trading off penalties due to the variance of the losses and penalties due to variability of the comparator sequence, and provide a framework for achieving any of the guarantees along this frontier. As a result, we also prove for the first time that adapting to the squared path-length of an arbitrary sequence of comparators to achieve regret $R_{T}(u_{1},\dots,u_{T})\le O(\sqrt{T\sum_{t} \\|u_{t}-u_{t+1}\\|^{2}})$ is impossible. However, using our framework we introduce an alternative notion of variability based on a locally-smoothed comparator sequence $\bar u_{1}, \dots, \bar u_{T}$, and provide an algorithm guaranteeing dynamic regret of the form $R_{T}(u_{1},\dots,u_{T})\le \tilde O(\sqrt{T\sum_{i}\\|\bar u_{i}-\bar u_{i+1}\\|^{2}})$, while still matching in the worst case the usual path-length dependencies up to polylogarithmic terms.

Main paper: 
 introduction: 
 This paper introduces new techniques for Online Convex Optimization (OCO), a framework for designing and analyzing algorithms which learn on-the-fly from a stream of data [14, 51, 5, 31, 6] . Formally, consider T rounds of interaction between the learner and their environment. In each round, the learner chooses w t ∈ W from a convex feasible set W ⊆ R d , the environment reveals a G-Lipschitz convex loss function ℓ t : W → R, and the learner incurs a loss of ℓ t (w t ). The classic objective in this setting is to minimize the learner's regret relative to any fixed benchmark u ∈ W: R T (u) := T t=1 (ℓ t (w t ) -ℓ t (u)) .In this paper, we study the more general problem of minimizing the learner's regret relative to any sequence of benchmarks u 1 , . . . , u T ∈ W [17, 18] : R T (u 1 , . . . , u T ) := T t=1 (ℓ t (w t ) -ℓ t (u t )) .This objective is typically referred to as dynamic regret, to distinguish it from the special case where the comparator sequence is fixed u 1 = • • • = u T (referred to as static regret). We focus in particular on the special case of Online Linear Optimization (OLO), in which ℓ t (w) = ⟨g t , w⟩ for some g t ∈ R d . Note that OCO problems can always be reduced to OLO via the well-known inequality ℓ t (w t ) -ℓ t (u) ≤ ⟨g t , w t -u⟩ for g t ∈ ∂ℓ t (w t ), where ∂ℓ t (w t ) is the subdifferential set of ℓ t at w t [see, e.g., 36], so throughout this paper we will focus on the OLO setting.Intuitively, if the sequence of comparators u 1 , . . . , u T varies too much, it should be impossible to achieve low dynamic regret. On the other hand, we know it is possible to achieve sublinear regret if the sequence of comparators is constant, i.e., u 1 = • • • = u T , because this is simply the static case. Hence, we need a way to quantify the complexity, or variability, of the comparator sequence. The most commonly used notion of complexity in this regard is the path-length of the comparator sequence [17, 18] , defined asP ∥•∥ T := T t=2 ∥u t -u t-1 ∥ .It is possible to show that Online Gradient Descent has a dynamic regret of O((D + P∥•∥ T )G √T ) in bounded domains, where D is an upper bound on the diameter of the feasible set and G is the Lipschitz constant of the losses [51] . This bound was improved to O( DP∥•∥ T G √ T) and shown to be minimax optimal by Zhang et al. [46] .Notice that the path-length bounds scale with a rather pessimistic constant of D = sup w,w ′ ∈W ∥w -w ′ ∥. A better bound would instead scale with the squared path-length:P ∥•∥ 2 T := T -1 t=1 ∥u t -u t-1 ∥ 2 ,which can be significantly smaller 2 than the penalty in the bound above:P ∥•∥ 2 T ≤ DP ∥•∥T . However, guarantees scaling with P ∥•∥ 2 T are not well understood in general compared with the more common P ∥•∥ T bounds, and have only been obtained by restricting the comparator sequence to u t = argmin w∈W ℓ t (w) or under additional assumptions such as strong-convexity [44, 45, 7] .In this paper, we focus on the challenging case that the domain is unbounded, where recent works have achieved the dynamic regret O max t,t ′ ∥u t -u t ′ ∥ P ∥•∥ T T in the worst case [20, 25, 21, 47] . Of particular interest, Jacobsen and Cutkosky [20] , Zhang et al. [47] achieve bounds of the formEQUATIONwhich avoids the pessimistic multiplicative penalty of max t,t ′ ∥u t -u t ′ ∥, but results in a coupling between the gradient and variability penalties. It is unclear if it is possible to obtain a guarantee which cleanly separates the variability and variance penalties, to achieve dynamic regret scaling asR T (u 1 , . . . , u T ) ≤ O P ∥•∥ 2 T T t=1 ∥g t ∥ 2 .In fact, it is not clear in general how to reason about potential trade-offs that may result from adapting to different measures of variability.Contributions. In this paper, we show how to reformulate the dynamic regret miniminization problem as an equivalent static regret problem (Section 2). This equivalence allows us to use results for the static regret setting to prove both upper and lower bounds for dynamic regret.In our first application of this equivalence, we show that the ideal guarantee scaling the with squared path-length O P ∥•∥ 2 T T t=1 ∥g t ∥ 2 is not possible in general (Section 3). We do this by proving a novel lower bound showing that there is a fundamental trade-off between the penalties incurred due to comparator variability and penalties incurred due to loss variance, leading to a new frontier of dynamic regret lower bounds.Our second application is to provide a framework for achieving any of the variance/variability tradeoffs along the lower bound frontier, up to polylogarithmic terms (Section 4). Our framework allows us to develop dynamic regret algorithms by simply choosing suitable dual-norm pairs (∥•∥ , ∥•∥ * ) in the static regret problem. Along with our matching lower bound, this framework provides a concrete way to reason about different measures of comparator variability and the trade-offs they entail, and to design algorithms achieving those trade-offs.While our lower bound demonstrates that the ideal squared path-length guarantee cannot be achieved, using our framework we show that it is possible to achieve an alternative guarantee that scales withEQUATION, where ū(τ)i is a local average of the comparator sequence at a timescale of τ (see Section 4.1). Similar toP ∥•∥ 2 T, this variability measure maintains the property that it matches the worst-case guarantees based on path-length up to polylogarithmic terms, i.e.,P ∥•∥ 2 T ≤ O(max t,t ′ ∥u t -u t ′ ∥ P ∥•∥ T ). These are the first guarantees for general OCO that fully decouple the variance and variability penalties for dynamic regret without explicitly incurring pessimistic max t,t ′ ∥u t -u t ′ ∥ penalties. Related Work. Our approach is inspired by the Haar OLR algorithm of Zhang et al. [47] . In that work, dynamic regret is approached by interpreting the comparator sequence as a high-dimensional "signal" which is decomposed into a frequency domain representation using a dictionary of features. Then, for each feature vector in the dictionary, a 1-dimensional parameter-free [32, 28] algorithm is used to learn how well that feature correlates with the losses. This allows one to compete with an arbitrary comparator sequence, so long as it can be represented in terms of the chosen dictionary of features. We take a similar but slightly more general approach. Our framework also represents the comparator sequence as a high-dimensional signal, but we instead use this signal to define an equivalent static regret problem, a perspective that allows us design algorithms for dynamic regret by simply choosing suitable dual-norm pairs. Other prior works in the general OCO setting have also studied various alternative forms of variability such as the temporal variability T -1 t=1 sup w∈W |ℓ t (w) -ℓ t+1 (w)| [3, 22, 4] or deviation of the comparator from a given dynamical model T -1 t=1 ∥u t -Φ t (u t-1 )∥ [16] . Alternative variance penalties have also been studied in the dynamic setting, such as the small-loss penalties T t=1 ℓ t (u t ) or gradient variation penalties T t=1 sup w∈W ∥∇ℓ t (w) -∇ℓ t+1 (w)∥ [15, 49, 21, 50] . It is also possible to achieve a smaller regret with stronger assumptions on the losses [2] . It is important to note however that almost all prior works, with the exception of Jacobsen and Cutkosky [20] , Luo et al. [25] and Zhang et al. [47] , study dynamic regret only in the easier bounded domain setting.There is also an often ignored connection between measures of comparator variability and the function classes studied in non-parametric regression. In particular, considering the case that the losses are ℓ t (x) = (x -u t ) 2 , then the sequence of comparators u 1 , . . . , u T with bounded path length C T and bounded squared path length (C ′ T ) 2 corresponds to the sequence with discrete total variation bounded by C T and the discrete Sobolev class with bound C ′ T , respectively. In this setting, the minimax rates are known [24, 35] and Koolen et al. [24] obtain the minimax regret for the Sobolev classes, while Baby and Wang [1] for both classes with slightly stronger assumptions. However, these results are not directly related to this paper because we consider linear losses.Notations. We will use the following definitions and notations. The elements of a matrix A ∈ R n×m are denoted by A ij for i = 1, . . . , n and j = 1, . . . , m. Similarly, the elements of a vector u ∈ R d are u i for i = 1, . . . , d. The Kronecker product of matrices A ∈ R m×n and B ∈ R p×q is the block matrix defined byEQUATIONt , . . . , w(T ) t ) ∈ W T from A Play w t = w (t) t ∈ W and observe g t ∈ ∂ℓ t (w t ) Pass g t = e t ⊗ g t = (0 ⊤ d , . . . , 0 ⊤ d , g ⊤ t indices i∈[d(t-1)+1,dt] , 0 ⊤ d , . . . ) ⊤ ∈ W T to A endWe let e t denote the t th standard basis vector of R T and I d is the d × d identity matrix. For a square matrix A, Diag (A) is the diagonal matrix that contains the elements of the diagonal of A. For a positive definite matrix M , we define the weighted norm ∥x∥ M := ⟨x, M x⟩. For a matrix A ∈ R m×n , we denote its Frobenius norm by∥A∥ F := m i=1 n j=1 A 2 i,j. The vec operator is the mapping defined by stacking the columns of a matrix A in a vector. We will denote by ∥A∥ p,p the entry-wise p-norm of A, i.e., ∥A∥ p,p := ∥vec(A)∥ p . 
a dynamic-to-static reduction: 
 In this section, we present a general reduction from dynamic regret to static regret. The key idea is to embed the comparator sequence in a high dimensional space W T , where T is the number of rounds, so that competing with a fixed comparator u ∈ W T in this high-dimensional space is equivalent to competing with a sequence of comparators in the original space W. In this way, we can reduce the problem of minimizing the dynamic regret to the one of minimizing the static regret.Our reduction is shown in Algorithm 1. We simply embed the linear losses g t in a high-dimensional space by settingEQUATIONwhere e t ∈ R T is the t th standard basis vector of R T and 0 d ∈ R d denotes the vector of zeros. We pass these losses to the online learning algorithm A, which predicts with a vector w t ∈ W T . Finally, we set w t ∈ R d equal to the t th "component" of w t , and play w t .We show that the dynamic regret of the resulting algorithm will be equal to the static regret of the algorithm A. In particular, for any sequence ⃗ u = (u 1 , . . . , u T ) in W we will denote the concatenation of ⃗ u into a single vector in W T asEQUATIONThen, the following proposition shows that the dynamic regret of Algorithm 1 w.r.t any sequence⃗ u = (u 1 , . . . , u T ) is equal to the static regret of A w.r.t u.Proposition 1. Let W ⊆ R d and let A be an online learning algorithm with domain W T . Then, for any sequence⃗ u = (u 1 , . . . , u T ) ∈ W T , Algorithm 1 guarantees R T (⃗ u) = T t=1 ⟨g t , w t -u t ⟩ = T t=1 ⟨ g t , w t -u⟩ =: R Seq T ( u) .Proof. The proof is immediate from Equations ( 2) and (3). In fact, observe that the cumulative loss of the comparator sequence is preciselyT t=1 ⟨g t , u t ⟩ = g 1 . . . g T , u 1 . . . u T = T t=1 e t ⊗ g t , T t=1 e t ⊗ u t = T t=1 g t , u .We get a similar relationship for the algorithm's cumulative loss. Hence, we haveR T (⃗ u) = T t=1 ⟨g t , w t -u t ⟩ = T t=1 ⟨ g t , w t -u⟩ = R Seq T ( u).Remark 1. It is important to note that the regret equivalence holds in the context of linear losses. However, our reduction can still be leveraged for arbitrary convex losses by first applying the standard reduction to OLO:T t=1 ℓ t (w t ) -ℓ t (u t ) ≤ T t=1 ⟨g t , w t -u t ⟩ = R Seq T ( u) for g t ∈ ∂ℓ t (w t ).While our reduction is exceptionally simple, its utility should not be understated. Proposition 1 is a regret equivalence -we lose nothing by taking this perspective, yet it allows us to immediately apply all the usual techniques and approaches from the static regret setting. For instance, given any dual norm pair (∥•∥ , ∥•∥ * ), it is well-understood how to develop algorithms which adapt simultaneously to the comparator norm ∥ u∥ and to the gradient varianceT t=1 ∥ g t ∥ 2 * to guarantee R T (u 1 , . . . , u T ) = R Seq T ( u) ≤ O ∥ u∥ T t=1 ∥ g t ∥ 2 * .Such algorithms are commonly referred to as "parameter-free", or "comparator adaptive", because they achieve this adaptation by completely removing the parameter that depends on the unknown comparator u [e.g., 26, 27, 32, 9, 12, 20, 8, 21, 48] . In this way, we have effectively reduced the problem of minimizing dynamic regret to the problem of selecting a dual-norm pair (∥•∥ , ∥•∥ * ) that meaningfully measures the "difficulty" of the sequence in u and the losses g t . In particular, (∥•∥ , ∥•∥ * ) should be chosen with the following considerations in mind:1. ∥ u∥ should produce a meaningful measure of variability of the comparator sequence u 1 , . . . , u T . For instance, we will show in Proposition 2 that the squared path-length arises from a particular weighted norm applied to u.2. ∥ g t ∥ * should not "blow up". Ideally ∥ g t ∥ * should match the magnitude of the true losses g t up to polylog factors.3. (∥•∥ , ∥•∥ * ) should be chosen with computational considerations in mind. For instance, to apply an FTRL-based algorithm to the losses g t ∈ R dT , efficient implementation will typically require ∥•∥ * to have sparse subgradients. In general, an ideal dual-norm pair should facilitate updating only O(log T ) variables at a time, so as to match the O(d log T ) per-step computation enjoyed by existing dynamic regret algorithms. We will see one such example in Section 4.1.In the next section, we show that there is in fact a fundamental trade-off between the penalties induced by the dual-norm pair (∥•∥ , ∥•∥ * ), creating a tension between the first two considerations. 
lower bounds for unconstrained dynamic regret: 
 In the static regret setting, there is a well-known trade-off between the way in which we measure the complexity of the comparator u and the way in which we measure the complexity of the linear losses g t . For example, in Online Mirror Descent [29, 42] one can get a regret guarantee that depends on the maximum diameter of the feasible set with respect to a norm ∥ • ∥, while the linear losses are measured using the dual norm ∥ • ∥ * . The equivalence in Proposition 1 suggests that a similar tension exists for the dynamic regret.Given the structure of our reduction, it makes sense to focus on the weighted norms ∥•∥ M and ∥•∥ M -1 , where M is a symmetric positive definite matrix. In particular, the next theorem shows that there is a fundamental trade-off between a variability penalty ∥ u∥ M and a variance penalty G 2 Tr(M -1 ) related to the losses. The proof is provided in Appendix A.1 and it is based on a lower bound to the tail of Rademacher chaos of order 2.Theorem 1. Let the number of rounds T ≥ T 0 , where T 0 is a universal constant. Let A be an online learning algorithm, and suppose A guarantees R T (0) ≤ Gϵ T for any sequence of linear losses g 1 , . . . , g T ∈ R satisfying |g t | ≤ G. Let M -1 ∈ R T ×T be any symmetric positive definite matrix, denote M -1:= M -1 -Diag M -1 and V T := Tr(M -1 ) + ∥ M -1 ∥ F . Suppose that ∥ M -1 ∥ 2 F ≥ T 2 max i j ( M -1 ij ) 2 .Then, for any P satisfying T 0 ≤ log 2√ P V T 2ϵ T≤ T , there is a sequence of losses g 1 , . . . , g T ∈ R, and u = (u 1 , . . . , u T ) ⊤ ∈ R T satisfying ∥ u∥ M = √ P such that we haveR T (u 1 , . . . , u T ) ≥ Ω   Gϵ T + G P Tr(M -1 ) + M -1 F log 1 2 2 √ P V T 2ϵ T   .Let us first briefly discuss the conditions on M . First, note that the restriction that M be positive definite and symmetric simply specifies that ∥•∥ M defines a valid norm. The condition on∥ M -1 ∥ F = ∥M -1 -Diag M -1 ∥ F is less straight forward to interpret, but it essentially states that the total "variance" of M -1is at least as much as that of any of its columns. on a technical level this assumption leads to the restriction that P satisfies log 2 √ P V T /2ϵ T ≤ T . This is a natural restriction which encodes the fact that if P is too large relative to T (i.e., when log 2 ( √ P V /2ϵ T ) ≥ T ), one can ensure "low" regret by simply playing w t = 0 on every round:R T (⃗ u) = - T t=1 ⟨g t , u t ⟩ ≤ max t ∥u t ∥ G T ≤ G max t ∥u t ∥ log 2 P V T /2ϵ ,and hence the only lower bounds in such settings are trivial ones and it suffices to consider only P satisfying log √ P V T /2ϵ ≤ T . We will see in Proposition 2 that the matrix that produces the squared path-length satisfies this condition, and it can be seen that symmetric matrices with equal column sums (as is the case in Proposition 3) satisfy this condition as well.The result of Theorem 1 shows that there is a frontier of lower bounds which trade off penalties related to variability of the comparator sequence and penalties related to the variance of the subgradients. That is, one can not guarantee a small variability penalty in all situations without also accepting a large subgradient variance penalty. The next proposition shows that i) the squared path-length can be represented by a particular choice of the weighted norm ∥ u∥ M , and ii) the fundamental tension between ∥ u∥ M and its corresponding variance penalty Tr(M -1 ) prevents any algorithm from attaining the ideal variability dependence of ∥ u∥ M = T -1 t=1 ∥u t -u t+1 ∥ 2 . In fact, the corresponding variance penalty is G 2 Tr(M -1 ) = O(G 2 T 2 ), resulting in a vacuous guarantee. Proof of the proposition can be found in Appendix A.2. Proposition 2. (Adapting to Squared Path-length Requires Superlinear Regret) Define the finitedifference operator Σ ∈ R T as the matrix with entriesΣ ij =    1 if i = j -1 if i = j -1 0 otherwise . Let S = Σ ⊤ Σ and M = S ⊗ I d .Then, M satisfies the assumptions of Theorem 1 and∥ u∥ 2 M = ∥u T ∥ 2 2 + T -1 t=1 ∥u t -u t+1 ∥ 2 2and Tr M -1 = T (T + 1) 2 .Proposition 2 shows that adapting to the squared path-length of an arbitrary comparator sequence necessarily requires incurring a linear penalty, so adapting to the squared path-length is impossible without facing a vacuous guarantee. However, we will show in Section 4.1 that it is possible to adapt to a measure of variability which is similar in spirit to the squared path-length, yet only incurs a Tr(M -1 ) = O(log T ) variance penalty. Remark 2. The matrix M in Proposition 2 uniquely exposes the the squared path-length up to the bias term ∥u T ∥ 2 . Such a bias term must appear because in the static regret setting, wherein u 1 = . . . = u T = u, the variability measure ∥•∥ M must still reduce to a dependence on ∥u∥, otherwise Algorithm 2: Dynamic regret OLO through 1-dimensional reduction [9] Input 1-d Parameter-free OLO algorithm A, positive definite symmetric matrixM ∈ R dT ×dT Initialize θ 1 = v 1 = 0 ∈ R dT , V 1 = 0 for t = 1 : T do Get β t ∈ R from A Play w t = β t v t and observe g t Send ⟨ v t , g t ⟩ to A as the t th loss Set θ t+1 = θ t -M -1 g t Set V t+1 = V t + ∥ g t ∥ 2 M -1 Set v t+1 = θt+1 √ Vt+1 1 ∧ √ Vt+1 ∥ θt+1∥ M -1// (Projected) Scale-free FTRL update end the guarantee would violate existing Ω(∥u∥ √ T ) lower bounds for static regret. More generally, we show in Appendix A.3 that any other choice of bias would similarly lead to Tr M -1 ≥ Ω(T 2 ), so Proposition 2 along with our lower bound in Theorem 1 are sufficient to show that adapting to squared path-length requires accepting a vacuous guarantee. 
dynamic regret for unconstrained olo via weighted norms: 
 So far, we've seen that there exists a frontier of lower bounds trading off a variability penalty, measured by ∥ u∥ M , and a loss variance penalty, measured by Tr(M -1 ), and that the tension between these two quantities makes it impossible to adapt to the squared path-length of the comparator sequence without accepting a vacuous regret guarantee. A natural next question is whether there are choices of M which lead to a more favorable trade-off of these two quantities. In this section, we provide a simple framework for achieving lower bounds along the frontier described by Theorem 1, and an instance which successfully achieves an improved variance/variability trade-off. The guarantees on the lower bound frontier can be achieved using any parameter-free algorithm along with the 1-dimensional reduction of Cutkosky and Orabona [9] to extend the algorithm to dual-norm pair(∥•∥ M , ∥•∥ M -1 ). The generic procedure is summarized in Algorithm 2 for convenience.Theorem 2. Let S ∈ R T ×T be a symmetric positive definite matrix, M = S ⊗ I d , and ϵ > 0.There is an algorithm A such that for any g 1 , . . . , g T ∈ R d satisfying ∥g t ∥ 2 ≤ G for all t and any sequence ⃗ u = (u 1 , . . . , u T ) ∈ R dT , the dynamic regret is bounded asR T (⃗ u) ≤ O   Gϵ + ∥ u∥ M   V T log ∥ u∥ M √ V T Gϵ + 1 ∨ G log ∥ u∥ M √ V T ϵG     , where V T = T t=1 ∥ g t ∥ 2 M -1 and G = G S -1 ∞,∞ .For the proof, we will need the following technical lemma. Lemma 1. Let S ∈ R T ×T be a symmetric positive definite matrix and let M = S ⊗ I d . For t = 1, . . . , T , let g t ∈ R d and let g t = e t ⊗ g t . Then, we have∥ g t ∥ 2 M = ∥g t ∥ 2 2 S tt .Proof. Using the mixed-product property (A ⊗ B)(C ⊗ D) = AC ⊗ BD and the transpose property(A ⊗ B) ⊤ = A ⊤ ⊗ B ⊤ of the Kronecker product, we have that ⟨ g t , M g t ⟩ = ⟨e t ⊗ g t , [S ⊗ I d ] e t ⊗ g t ⟩ = ⟨e t ⊗ g t , Se t ⊗ g t ⟩ = (e ⊤ t ⊗ g ⊤ t )(Se t ⊗ g t ) = e ⊤ t Se t ⊗ g ⊤ t g t = S tt ∥g t ∥ 2 .Proof of Theorem 2. Applying Proposition 1, we haveR T (⃗ u) = T t=1 ⟨ g t , w t -u⟩ = R Seq T ( u). Since M is symmetric and positive definite, (∥•∥ M , ∥•∥ M -1 ) is a valid dual-norm pair. By Lemma 1, we have ∥ g t ∥ 2 M -1 = ∥g t ∥ 2 2 S -1 tt ≤ G 2 S -1 ∞,∞ := G 2 .Hence, let A be any algorithm which guarantees a parameter-free regret w.r.t. (∥•∥ , ∥•∥ * ) on losses satisfying ∥ g t ∥ M -1 ≤ G. Note that any parameter-free algorithm can be extended to handle arbitrary dual-norm pairs by leveraging the one-dimensional reduction of Cutkosky and Orabona [9, Section 3], that reduces the OLO problem to a unconstrained 1d problem plus an OLO problem in the unitary ball defined by the primal norm. For instance, applying Jacobsen and Cutkosky [20, Algorithm 1] with the one-dimensional reduction one can easily show (see details in Appendix B.1)R T (⃗ u) ≤ O   Gϵ + ∥ u∥ M   V T log ∥ u∥ M √ V T Λ T Gϵ + 1 ∨ G log ∥ u∥ M √ V T Λ T ϵG     , where V T = T t=1 ∥ g t ∥ 2 M -1 and Λ T = log 2 ( T t=1 ∥ g t ∥ 2 M -1 /G 2 ) ≤ O(log 2 T ).Note in particular that by Lemma 1, we haveT t=1 ∥ g t ∥ 2 M -1 = T t=1 S -1 tt ∥g t ∥ 2 ≤ G T t=1 S -1 tt = G Tr(S -1), so this bound matches the lower bound from Section 3, up to polylogarithmic terms. 3Thus, any valid choice of M will be on the lower bound frontier of Section 3.Leveraging the algorithm characterized by Theorem 2, we now show that it is indeed possible to choose M such thatT t=1 ∥ g t ∥ 2 M -1 is only O(log (T ) T t=1 ∥g t ∥2 ), in exchange for a variability penalty which is still similar in spirit to the squared path-length.Inspired by the Haar OLR algorithm of [47] , we apply Theorem 2 using S = H n H ⊤ n , where H n is the unnormalized Haar basis matrix of order n = ⌈log 2 T ⌉. The Haar wavelet transform and its basis matrix are common tools in the signal processing literature; we recall the basic definitions and facts for convenience in Appendix B.2. With this choice, we have the following bounds on ∥ u∥ M and ∥ g t ∥ u t , and define the squared path-length at time-scale τ < T to beP (⃗ u, τ ) := Nτ /2 i=1 ū(τ) 2i-1 - ū(τ) 2i 2 2, andP (⃗ u, T ) = ū(T ) 1 2 2 = ∥ū∥ 2 2 . Then, setting S = [H n H ⊤ n ] -1 and M = S ⊗ I d , we have ∥ u∥ 2 M ≤ ∥ū∥ 2 2 + 1 4 log 2 (T ) i=0 P (⃗ u, 2 i ) ≤ ∥ū∥ 2 2 + 1 4 log (T ) max τ P (⃗ u, τ ), ∥ g t ∥ 2 M -1 = ∥g t ∥ 2 2 (1 + log T ) .S = [H n H ⊤ n ] -1 we ensure regret R T (⃗ u) ≤ O      ∥ū∥ 2 2 + max τ Nτ /2 i=1 ū(τ) 2i+1 - ū(τ) 2i 2 2   T t=1 ∥g t ∥ 2 2    .This is the first fully decoupled guarantee for general dynamic regret which incurs no pessimistic multiplicative penalties of the form max t,t ′ ∥u t -u t ′ ∥. That is, the terms depending on the comparators and the terms depending on the gradients appear in separate sums. Moreover, observe that this measure of variability can immediately be related to the more standard (first-order/non-squared) path-length using the local averaging lemma of Zhang et al. [47] (Lemma D.7). We have∥ u∥ 2 M ≤ ∥ū∥ 2 2 + log 2 T 4 max τ Nτ /2 i=1 ū(τ) 2i-1 - ū(τ) 2 i 2 2 ≤ O   D2 + max τ D Nτ /2 i=1 ū(τ) 2i-1 - ū(τ) 2 i 2   ≤ O D2 + D T -1 t=1 ∥u t -u t+1 ∥ 2 ≤ O D2 + DP T ,whereD = max τ,i ū(τ) i - ū(τ) i+1 ≤ max i,j ∥u i -u j ∥. Thus, applying Algorithm 1 with dual- norm pair (∥•∥ H -⊤ n H ⊤ n , ∥•∥ HnH ⊤ n ) still guarantees worst-case regret R T (⃗ u) ≤ O ∥ u∥ H -⊤ n H -1 n T t=1 ∥ g t ∥ 2 HnH ⊤ n ≤ O ∥ū∥ 2 2 + DP T T t=1 ∥g t ∥ 2 2 ,which matches the guarantees of prior works, up to polylogarithmic terms.Importantly, with M = H -⊤ n H -1 n ⊗ I d the dual-norm pair (∥•∥ M , ∥•∥ M -1) leads to updates that can be implemented efficiently, in requiring only O(log T ) variables to be updated on each round. This is because the Haar basis matrices are locally supported -the columns of H n = h (1) . . . h (T ) ∈ R T ×T form an orthogonal basis with the property that for any t, [h (i) ] t ̸ = 0 for only 1 + log 2 T indices i (see Proposition 5) . Hence, (H ⊤ ⊗ I d ) g t = (H ⊤ ⊗ I d )(e t ⊗ g t ) = (H ⊤ e t ) ⊗ g t , 
recovering variance-variability coupling guarantees: 
 Our main focus throughout the paper has been on designing algorithms that achieve a regret bounds of the form R T (⃗ u) ≤ O f (u 1 , . . . , u T )V (g 1 , . . . , g T ) for some functions f and V , which cleanly separates the penalties associated with difficult loss sequences from the penalties associated with difficult comparator sequences. However, the first works to achieve unconstrained dynamic regret guarantees uncovered guarantees of a slightly different form, containing a gradient-comparator correlation penalty:EQUATIONfor some reference point ū [20, 47] . Guarantees of this form allow some degree of coupling between the variability and variance penalties. This can be appealing in certain situations. For instance, guarantees of the form above have the appealing property that the variance penalty completely disappears on any rounds where the comparator u t matches the reference point ū. This can be a very powerful property when one has a priori access to a benchmark model (represented by ū) which can be expected to predict well on average, so that we accumulate the variance penalties only when facing atypical/unexpected conditions.The prior works achieving a coupling guarantee do so using rather mysterious means. For instance, the guarantee of Jacobsen and Cutkosky [20] achieves the coupling guarantee almost by coincidence, as it appears in response to a composite regularizer they add to the update to cancel out certain unstable terms in the analysis, and the analysis of Zhang et al. [47] recovers a guarantee of a similar form using a rather difficult analysis of the frequency-domain representation of u after projecting onto the Haar basis vectors. So far there is no unifying explanation of the principles leading to these sorts of guarantees.Our equivalence in Proposition 1 instead shows that guarantees of the form Equation ( 4) can instead be understood through the lens of reward-regret duality, a standard tool used to design algorithms in the static regret setting. The reward-regret duality states that in order to guarantee regret of the form R T (u) ≤ f (u) for all u ∈ W, it suffices to design an algorithm that guarantees -T t=1 ⟨g t , w t ⟩ ≥ f * (-T t=1 g t ) for any g 1 , . . . , g T . Using Proposition 1, we immediately have the following analogous design principle for dynamic regret. Proof is deferred to Appendix C.1. Theorem 3. Let Wealth T := -T t=1 ⟨ g t , w t ⟩ denote the "wealth" of an algorithm A and let (f, f * ) be a Fenchel conjugate pair. Then A guarantees Wealth T ≥ f * T -T t=1 g t for any sequence g 1 , . . . , g T if and only if R T (⃗ u) ≤ f T ( u) for any sequence ⃗ u = (u 1 , . . . , u T ) in W, where u = (u ⊤ 1 , . . . , u ⊤ T ) ⊤ is the concatenation of the sequence ⃗ u into a vector.So, suppose we would like to design an algorithm that guarantees for any sequence ⃗ u = (u 1 , . . . , u T ) and any ⃗ g = (g 1 , . . . , g T ) regret of the formR T (⃗ u) ≤ f T ( u)V T ( u), for some f T ( u) and V T ( u) = V T ( u; ⃗ g). Then, since √ ab = min η≥0 a 2η + η 2 b, any such algorithm must have R T (⃗ u) ≤ f T ( u) 2η + η 2 V T ( u)for every η ≥ 0. So, via Proposition 1 and the the reward-regret duality of Theorem 3, we have that the desired guarantee is equivalent to guaranteeing for all η ≥ 0 a wealth lower bound ofWealth t = - T t=1 ⟨ g t , w t ⟩ ≥ f T (•) 2η + η 2 V T (•) * -g 1:T = f * T -2η g 1:T 2η □ 2ηV * T g 1:T 2η ,where f * T and V * T are the Fenchel conjugates of f T and V T respectively, and (f 1 □ f 2 ) denotes the infimal convolution [34, 19] of f 1 and f 2 :(f 1 □ f 2 )(z) = inf {f 1 (y) + f 2 (z -y)} .Thus, the variance/variability coupling guarantees observed in Equation ( 4) can be interpreted as achieving wealth lower-bounds for potential functions involving infimal convolution.The above discussion provides a general characterization of variance/variability coupling guarantees, though it is admittedly less clear how difficult it is to design algorithms from this perspective due to the rather complicated potential function that appears. Nonetheless, we believe that this provides a valuable perspective and insight that could be of general interest. An important direction for future work is to develop useful tools for working with potential functions of this form.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: [NA] Justification: This is a theoretical paper that studies theoretical guarantees for online learning algorithms.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion: 
 In this paper, we have shown a way to reduce the problem of dynamic regret minimization to the static one. We proved a novel frontier of lower bounds showing a fundamental trade-off between penalties on the comparators and penalties on the variance of the gradients. In particular, we have shown that it is not possible to achieve a guarantee that scales withT -1 t=1 ∥u t -u t+1 ∥ 2 withoutincurring a variance penalty of O(GT ). We developed a simple framework for achieving guarantees along the lower bound frontier, and used it to develop the first algorithm making a non-trivial variance/variability decoupling guarantee against arbitrary comparator sequences. Our framework is simple but powerful, allowing one to fully utilize the rich literature of static regret algorithms for online learning.We conclude by noting some directions for future work. There is a lot of exciting potential to explore different measures of variability induced by different choices of the matrix M , as well as going beyond weighted norms. As mentioned in Section 5, developing a useful toolset for potential functions involving infimal convolution is an important next-step for developing and understanding guarantees with a coupled variance/variability penalty, such as Equation ( 4). Also, our lower bound in Section 3 illustrates the variance-variability trade-off, but achieving the correct logarithmic dependencies proved to be very challenging -many of the standard tools for proving lower bounds in unconstrained settings revolve around anti-concentration results that do not readily extend to arbitrary weighted norms and higher-dimensions. We look forward to exciting development in these future directions.A Proofs for Section 3 (Lower bounds for unconstrained dynamic regret)In this section, we provide proof of our main lower bound result from Section 3. We first introduce a technical tool from the literature on decoupling theory and a key lemma (Lemma 2). Proof of our main result is in Appendix A.1.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: This is a theoretical paper that studies theoretical guarantees for online learning algorithms.Guidelines:• The answer NA 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. 
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: [NA] Justification: This is a theoretical paper that studies theoretical guarantees for online learning algorithms.Guidelines:• The answer NA 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.) • 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. 
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: [NA] Justification: This is a theoretical paper that studies theoretical guarantees for online learning algorithms.Guidelines:• The answer NA 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). 
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? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a theoretical paper that studies theoretical guarantees for online learning algorithms. As stated in the guidelines, this is foundational research and it is not tied to particular applications, let alone deployments.• 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. • 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. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: This paper does not release new assets.Guidelines:• The answer NA 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. 
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: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA 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. 
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: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA 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. 
 
 Appendix: f : [-1, 1] d → R, defined as f (x) = i,j A i,j x i x j ,Define A the matrix with elements A i,j . In this section we will use the following notations for quantities related to a polynomial induced by the quadratic form x → ⟨x, Ax⟩ (see page 6 of O'Donnell and Zhao [30] )Var[f ] = i,j A 2 i,j = ∥A∥ 2 F , Inf i [f ] = d j=1 (A 2 i,j + A 2 j,i ) .One of the key difficulties in deriving the lower bound is that squared weighted norms x → ⟨x, Ax⟩ introduce dependencies between the coordinates of x, which breaks the usual lower bound arguments which rely on anti-concentration of independent Rademacher random variables. Instead, we must leverage an anti-concentration result that holds for polynomials of random variables. Theorem 4 (Theorem 3 of Dinur et al. [10] ). There is a universal constant C such that the following holds. Suppose G : {±1} d → R is a polynomial of degree at most 2 and assume Var[g] = 1. Let t ≥ 1 and suppose that Inf i [g] ≤ C -2 t -2 for all i ∈ [d]. Then P {|g(x)| ≥ t} ≥ exp -C 2 t 2 4 log 2 .Using this anti-concentration result, the following key lemma provides a general lower bound on the wealth obtainable by any algorithm, subject to the weighting imposed by a matrix A. Lemma 2. Let A be an online learning algorithm, and suppose A guarantees R T (0) ≤ Gϵ T for any sequence of linear losses g 1 , . . . , g T ∈ R satisfying |g t | ≤ G. Let A ∈ R T ×T be any symmetric positive definite matrix, and let B = A -Diag (A). Then, there is a universal constant C > 0 such that for any1 ≤ q ≤ ∥B∥ F C 2 maxi T j=1 B 2 ij, there is a sequence of losses g 1 , . . . , g T ∈ R such that   g 1 . . . g T    2 A ≥ G 2 [Tr(A) + q ∥A -Diag (A)∥ F ] and R T (0) ≥ Gϵ T 1 -2 4C 2 q 2 .Proof. Let Y 1 , . . . , Y T be independent Rademacher random variables and set g t = G Y t , so thatE [R T (0)] = E T t=1 g t w t = 0.Then, using the regret equivalence of Proposition 1 and conditioning on any event E with P {E} > 0, we have0 = E [R T (0)] = E R T (0) E P {E} + E R T (0) E c P {E c } ≤ E [R T (0)|E] P {E} + G ϵ T (1 -P {E}) ,where the last line uses the fact that A guarantees R T (0) ≤ Gϵ T for any g 1 , . . . , g T satisfying |g t | ≤ G for all t. Re-arranging, we haveEQUATIONNext, let g t = e t ⊗ g t for all t and consider the eventE =    T t=1 g t 2 A = (g 1 , . . . , g T ) ⊤ 2 A ≥ Tr(A) + q ∥A -Diag (A)∥ F   for some q > 0. We proceed by lower bounding the probability of this event.Observe thatT t=1 g t 2 A = G 2 i,j Y i Y j A ij = G 2   Tr(A) + i,j̸ =i Y i Y j A ij   . Denote B = A -Diag (A) and note that f (Y 1 , . . . , Y T ) = i,j Y i Y j B ij is a polynomial of degree at most 2 and variance Var[f ] = i,j B 2 ij = ∥A -Diag (A)∥ 2 F = ∥B∥ 2 F . Moreover, since A is symmetric we have Inf i [f ] = T j=1 B 2 ij + B 2 ji = 2 T j=1 B 2 ij for any i. It follows that if we let g(Y ) = f (Y ) √ ∥B∥ 2 F = f (Y ) ∥B∥ F, then g is a polynomial of degree at most 2, Var[g] = 1, and for anyEQUATIONF. Hence by Theorem 4, there is a universal constant C such that for any1 ≤ q ≤ ∥B∥ F C 2 maxi T j=1 B 2 ij it holds that P {f (Y ) ≥ q ∥B∥ F } = P {g(Y ) ≥ q} ≥ exp -4C 2 q 2 log 2 = 2 -4C 2 q 2 .Now observe that P {E} = P {f (Y ) ≥ q ∥B∥ F } by construction, so Equation ( 5) can be bound asE R T (0) E ≥ Gϵ T 1 - 1 P {E} = Gϵ T 1 -2 4C 2 q 2 ,which implies the existence of a sequence g 1 , . . . , gT ∈ R such that R T (0) ≥ Gϵ T 1 -2 4C 2 q 2 and T t=1 g t 2 A ≥ G 2 [Tr(A) + q ∥B∥ F ] = G 2 [Tr(A) + q ∥A -Diag (A)∥ F ] ,for any1 ≤ q ≤ ∥B∥ F C 2 maxi T j=1 B 2 ij .A.1 Proof of Theorem 1In this section we prove our main lower bound. Theorem 1. Let the number of rounds T ≥ T 0 , where T 0 is a universal constant. Let A be an online learning algorithm, and suppose A guarantees R T (0) ≤ Gϵ T for any sequence of linear losses g 1 , . . . , gT ∈ R satisfying |g t | ≤ G. Let M -1 ∈ R T ×T be any symmetric positive definite matrix, denote M -1 := M -1 -Diag M -1 and V T := Tr(M -1 ) + ∥ M -1 ∥ F . Suppose that ∥ M -1 ∥ 2 F ≥ T 2 max i j ( M -1 ij ) 2 .Then, for any P satisfying T 0 ≤ log 2√ P V T 2ϵ T ≤ T , there is a sequence of losses g 1 , . . . , g T ∈ R, and u = (u 1 , . . . , u T ) ⊤ ∈ R T satisfying ∥ u∥ M = √ P such that we have R T (u 1 , . . . , u T ) ≥ Ω   Gϵ T + G P Tr(M -1 ) + M -1 F log 1 2 2 √ P V T 2ϵ T   .Proof. Denote A = M -1 and B = A -Diag (A). By Lemma 2, there is a universal constant C and a sequence g 1 , . . . , g T ∈ R such that for any1 ≤ q ≤ ∥B∥ F C 2 maxi T j=1 B 2 ij , it holds that T t=1 g t 2 A ≥ G 2 [Tr(A) + q ∥A -Diag (A)∥ F ] and R T (0) ≥ Gϵ T 1 -2 4C 2 q 2 .Hence, choosing comparator sequence u 1 , . . . , u T ∈ R to satisfy and u = (u 1 , . . . , uT ) ⊤ = - √ P A T t=1 g t ∥ T t=1 g t ∥ A ∈ R T , we have ∥ u∥ A -1 = ∥ u∥ M = √ P and R T (u 1 , . . . , u T ) = R T (0) - T t=1 g t , u = G √ P T t=1 g t A + R T (0) ≥ G P [Tr(A) + q ∥A -Diag (A)∥ F ] + R T (0) ≥ Gϵ T + G P [Tr(A) + q ∥A -Diag (A)∥ F ] -Gϵ T 2 4C 2 q 2 . Now, for P satisfying T 0 := 4C 2 ≤ log 2 P [Tr(A)+∥B∥ F ] 2ϵ T ≤ T we may choose q = log 2 √ P [Tr(A)+∥B∥ F ] 2ϵ T 4C 2 .Indeed, observe that this choice satisfies1 ≤ q ≤ ∥B∥ F C 2 maxi T j=1 B 2 ijas required:1 ≤ q = log 2 √ P [Tr(A)+∥B∥ F ] 2ϵ T 4C 2 ≤ T 4C 2 ≤ ∥B∥ F C 2 max i T j=1 B 2 ij ,where the final inequality uses the assumption∥B∥ 2 F /2 max i ij B 2 ij ≥ T 4 .Hence, we have thatGϵ T 2 4C 2 q 2 ≤ G 2 P [Tr(A) + ∥B∥ F ] ≤ G 2 P [Tr(A) + q ∥B∥ F ],so that the overall the regret can be lower-bounded asR T (u 1 , . . . , u T ) ≥ Gϵ T + 1 2 G P [Tr(A) + q ∥B∥ F ] = Gϵ T + G 2 P Tr(A) + ∥B∥ F log 1 2 P [Tr(A) + ∥B∥ F ]/2ϵ T √ T 0 .A.2 Proof of Proposition 2 Proposition 2. (Adapting to Squared Path-length Requires Superlinear Regret) Define the finitedifference operator Σ ∈ R T as the matrix with entriesΣ ij =    1 if i = j -1 if i = j -1 0 otherwise . Let S = Σ ⊤ Σ and M = S ⊗ I d .Then, M satisfies the assumptions of Theorem 1 and∥ u∥ 2 M = ∥u T ∥ 2 2 + T -1 t=1 ∥u t -u t+1 ∥ 2 2and Tr M -1 = T (T + 1) 2 .Proof. We first show the properties that ∥ u∥2 F = ∥u T ∥ 2 2 + T -1 t=1 ∥u t -u t+1 ∥ 2 2 and Tr(Σ -1 Σ -⊤ ) = T t=1 Σ -1 Σ -⊤ tt = T t=1 T -t + 1 = T (T +1) 2, and show that M satisfies the conditions of Theorem 1 at the end.Observe that(Σ ⊗ I d ) u =       I d -I d 0 0 • • • 0 I d -I d 0 • • • 0 0 I d -I d • • • . . . . . . 0 0 0 • • • I d          u 1 . . . u T    =       u 1 -u 2 u 2 -u 3 . . . u T -1 -u T u T       , and since (Σ ⊤ ⊗ I d )(Σ ⊗ I d ) = (Σ ⊤ Σ) ⊗ I d = M , we have ∥ u∥ 2 M = u, (Σ ⊤ ⊗ I d )(Σ ⊗ I d ) u = ⟨(Σ ⊗ I d ) u, (Σ ⊗ I d ) u⟩ = ∥u T ∥ 2 2 + T -1 t=1 ∥u t -u t+1 ∥ 2 2 .Using the inverse property of the Kronecker product, we also haveM -1 = Σ ⊤ Σ ⊗ I d -1 = Σ ⊤ Σ -1 ⊗ I d = Σ -1 Σ -⊤ ⊗ I d ,and by Lemma 8 we have that Σ -1 is the upper-triangular matrix of all 1's, that is, the matrix with entriesΣ -1 ij = 1 if i ≤ j 0 otherwise ,and likewise, Σ -⊤ is a lower-triangular matrix of 1 ′ s. In other words, for any t we haveΣ -1 Σ -⊤ tt = T i=1 Σ -1 ti Σ -⊤ it = i≤t Σ -1 ti = T -t + 1 .So, summing over t we have Lastly, letTr(Σ -1 Σ -⊤ ) = T t=1 Σ -1 Σ -⊤ tt = T t=1 T -t + 1 = T (T + 1) 2 .B = Σ -1 Σ -⊤ -Diag Σ -1 Σ -⊤ . We are to show that ∥B∥ F ≥ T 2 j B 2 ij for any i. First observe that calculation of [Σ -1 Σ -⊤ ] tt is generalized to Σ -1 Σ -⊤ ij = T k=1 Σ -1 ik Σ -⊤ kj = T k=1 Σ -⊤ ki Σ -⊤ kj = j∧i k=1 1 = T -max {j, i} + 1,for any i, j, and likewise B ij = T -max {j, i} + 1 for i ̸ = j and 0 otherwise, from which it is easily seen that max i j B 2 ij = j B 2 1j , so for any i we havej B 2 ij ≤ j B 2 1j = T j=2 (T -j + 1) 2 = 1 6 T (2T 2 -3T + 1) .On the other hand,∥B∥ 2 F = i j B 2 ij = 1 6 T 2 (T 2 -1) = T 2 T 6 (2T 2 -2) = T 2 T 6 (2T 2 -3T + 3T -2) ≥ T 2 T 6 (2T 2 -3T + 1) ≥ T 2 j B 2 ij ,for any i, where the last line applies the inequality in the previous display.The choice of M in Proposition 2 uniquely exposes the squared path-length up to the constant offset term ∥u T ∥ 2 . In this section we demonstrate that the choice of offset term in Proposition 2 does not make any significant difference for the claim that adapting to the squared path-length requires incurring a Tr(M -1 ) ≥ Ω(T 2 ) penalty, and hence that Proposition 2 is sufficient to demonstrate that adapting to the squared path-length is not possible without incurring vacuous regret.To expedite the discussion, we first introduce two technical lemmas, proven in Appendices A.3.1 and A.3.2 respectively. Lemma 3. Let v ∈ R T be an arbitrary non-zero vector and let B ∈ R T ×T be a symmetric matrix with eigenvalues 0 = λ 1 (B) < λ 2 (B) ≤ . . . ≤ λ T (B). ThenTr((B + vv ⊤ ) -1 ) ≥ ∥v∥ 2 + T t=2 1 λ t (B). where λ max (M -1 ) is the maximal eigenvalue of M -1 .Now, Consider the 1-dimensional setting and note that for any positive definite M we can find a unique Σ such that M = Σ ⊤ Σ. Hence, ∥ u∥ 2 M = ⟨ u, M u⟩ = ⟨Σ u, Σ u⟩ , so without loss of generality we can focus on Σ for which⟨Σ u, Σ u⟩ = ⟨v, u⟩ 2 + T t=2 ∥u t -u t-1 ∥ 2 ,where v ̸ = 0 ∈ R T . 4 Note such a constant offset term is unavoidable: it is what captures the static regret guarantee in the case where u 1 = . . . = u T = u. Proposition 2 considers v = (0, . . . , 0, 1)to get ∥ u∥ 2 M = ∥u T ∥ 2 + T t=2 ∥u t -u t-1 ∥ 2, though below we will show that any vector v would still lead to Tr(M -1 ) = Ω(T 2 ).It is clear that the only way to construct expressions of the form above is via matrices Σ satisfyingΣ u = c       u 1 -u 2 u 2 -u 3 . . . u T -1 -u T ⟨v, u⟩      , 4 Note that any such M is unique. Indeed, if there are positive definite matrices M 1 ∈ R T ×T andM 2 ∈ R T ×T such that ∥ u∥ 2 M 1 = ⟨v, u⟩ 2 + P ∥•∥ 2 2 T = ∥ u∥ 2 M 2 for all u ∈ R T , then ⟨ u, (M 1 -M 2) u⟩ = 0 and hence M 1 = M 2 since M 1 and M 2 are positive definite.where c ∈ {-1, 1} and the order of the rows indices of the vector can be permuted without loss of generality. In particular, the only matrices that can produce these expressions (again noting that the rows can be permuted without loss of generality) are of the formΣ = c         1 -1 0 0 . . . 0 0 0 1 -1 0 . . . 0 0 0 0 1 -1 . . . 0 0 . . . . . . 0 0 0 0 . . . 1 -1 v 1 v 2 v 3 v 4 . . . v T -1 v T         =: c   ∆ v ⊤   , so M = Σ ⊤ Σ = ∆ ⊤ ∆ + vv ⊤ . Moreover, ∆ ⊤ ∆is a symmetric matrix with a unique zero eigenvalue (corresponding to vectors in the span of 1 = (1, . . . , 1) ∈ R T ), so applying Lemma 3,Tr(M -1 ) = Tr((∆ ⊤ ∆ + vv ⊤ ) -1 ) ≥ ∥v∥ 2 + T t=2 1 λ t (∆ ⊤ ∆).Now, define v 0 = (0, . . . , 0, 1) ∈ R T and observe that M 0 := ∆ ⊤ ∆ + v 0 v ⊤ 0 is precisely the matrix studied in Proposition 2. We have via the interlacing property of rank-1 updates to symmetric matrices that λ t (∆ ⊤ ∆) ≤ λ t (M 0 ) [13, Theorem 8.1.8] , so overall we haveEQUATIONEQUATIONwhere the last inequality applies Lemma 4 to bound λ max (M -1 0 ) and recalls Tr(M -1 0 ) = T (T +1) 2 from Proposition 2.Hence, the variance penalty will still be Ω(T 2 ) regardless of the choice of bias ⟨v, u⟩ 2 in the variability measure. Combined with our lower bound in Theorem 1, it follows that adapting to the squared path-length necessarily implies a variance penalty of Tr(M -1 ) ≥ Ω(T 2 ), leading to a vacuous regret upper bound.Lemma 3. Let v ∈ R T be an arbitrary non-zero vector and let B ∈ R T ×T be a symmetric matrix with eigenvalues0 = λ 1 (B) < λ 2 (B) ≤ . . . ≤ λ T (B). Then Tr((B + vv ⊤ ) -1 ) ≥ ∥v∥ 2 + T t=2 1 λ t (B).Proof. Let A := B + vv ⊤ . Since B is symmetric, we have via the interlacing property that there is an a 1 , . . . , a T ≥ 0 such that Tr((B + vv ⊤ ) -1 ) = Tr(A -1 ) = T t=1 λ t (A -1 ) = T t=1 1 λ t (A) = T t=1 1 λ t (B) + a i ≥ min a1,...,a T ≥0 T t=1 at=∥v∥ 2 T t=1 1 λ t (B) + a i .To analyze the constrained optimization in the last line, let α 1 , . . . , α T ≥ 0, β ∈ R, and define the LagrangianL(a 1 , . . . , a T , α 1 , . . . , α T , β) = T t=1 1 λ t (B) + a t - T t=1 α t a t + β T t=1 a t -∥v∥ 2 .For any t, we have∂L ∂a t = -1 (λ t (B) + a t ) 2 -α t + β = 0 ⇐⇒ a t = 1 √ β -α t -λ t (B) .Plugging this into the dual D(α 1 , . . . , α T , β) = min a1,...,a T L(a 1 , . . . , a T , α 1 , . . . , α T , β) we haveD(α 1 , . . . , α T , β) = T t=1 β -α t - T t=1 α t 1 √ β -α t -λ t (B) + β T t=1 1 √ β -α t -λ t (B) -∥v∥ 2 = T t=1 β -α t + T t=1 (β -α t ) 1 √ β -α t + T t=1 (α t -β)λ t (B) -β ∥v∥ 2 = 2 T t=1 β -α t + T t=1 (α t -β)λ t (B) -β ∥v∥ 2 .The derivatives of the dual w.r.t α t are∂D ∂α t = -1 √ β -α t + λ t (B) .Observe that for λ 1 (B) = 0, we have∂D ∂αt = -1 √ β-αt ≤ 0, so D is decreasing in α 1 , so the dual is maximized when α 1 = 0. Using the relation a 1 = 1 √ β-α1 -λ 1 (B) above we have a 1 = 1 √ β-α1 -λ 1 (B) = 1 √ β .Equating the other derivatives for t > 1 to zero we have1 √ β -α t = λ t (B) =⇒ λ t (B) + a t = λ t (B) =⇒ a t = 0 ∀t > 1where we used the relationship a t = 1 √ β-αt -λ t (B) from above. Finally, the optimal β is such thatT t=1 a t = 1 √ β = ∥v∥ 2 , so overall we have min a1,...,a T ≥0 T t=1 at=∥v∥ 2 T t=1 1 λ(B) + a i = 1 √ β -α 1 + T t=2 1 λ t (B) + a i = 1 √ β + T t=2 1 λ t (B) = ∥v∥ 2 + T t=2 1 λ t (B).Lemma 4. Let Σ ∈ R T ×T denote the finite-difference matrix defined in Proposition 2 and let M = Σ ⊤ Σ. Then, for any T > 1, we haveλ max (M -1 ) ≤ 9 10 Tr(M -1 ),where λ max (M -1 ) is the maximal eigenvalue of M -1 .Proof. The matrix M -1 = Σ -1 Σ -⊤ is symmetric and positive definite, hence has real eigenvalues.The eigenvalues of M -1 can be bound in terms of its trace as follows (see, e.g., Theorem 2.1 Wolkowicz and Styan [43] , provided for convenience in Theorem 5):λ max (M -1 ) ≤ Tr M -1 T + (T -1)   Tr M -⊤ M -1 T - Tr M -1 T 2   .Next, observe that by Lemma 8, matrix Σ -1 is an upper-triangular matrix of all 1's, so that[M -1 ] ij = Σ -1 Σ -⊤ ij = k∈[t] Σ -1 ik Σ -⊤ kj = k∈[T ] Σ -1 ik Σ -1 jk = k∈[T ] 1 {k ≥ i} 1 {k ≥ j} = T -max {i, j} + 1,Hence,Tr M -1 = T t=1 [M -1 ] ii = T t=1 (T -t + 1) = T t=1 t = T (T + 1) 2 .Moreover,Tr M -⊤ M -1 = T t=1 [M -⊤ M -1 ] tt = T t=1 t k=1 M -⊤ tk M -1 kt = T t=1 t k=1 (M -1 kt ) 2 = T t=1 t k=1 (T -max {t, k} + 1) 2 = T (T + 1) 2 (T + 2) 12 .Thus,EQUATIONT -1 3 .Overall, λ max (M -1 ) is bounded byEQUATIONEQUATIONEQUATIONTr(M -1 ),where the last line observes that 1 -1√ 3 ≤ 1 2 ≤ T 4 for T ≥ 2 and the fact that 1 √ 3 + 1 4 ≈ 0.83 ≤ 9 10 .B Proofs for Section 4 (Dynamic regret for unconstrained OLO via weighted norms)In this section, for completeness we provide the details of the 1-dimensional reduction of Cutkosky and Orabona [9] , specialized to dual weighted-norm pairs (∥•∥ M , ∥•∥ M -1 ) as well as its regret guarantee.For concreteness, we choose adaptive FTRL with AdaGrad-norm stepsizes [40] as the direction learner. For simplicity we use the scale-free version of [33] , so that the direction learner's update is slightly simpler, not requiring prior knowledge of the Lipschitz constant G ≥ ∥ g t ∥ M -1 .Using Cutkosky and Orabona [9, Theorem 2], we have that the regret of Algorithm 2 is equal toR T ( u) = R A T (∥ u∥ M ) + ∥u∥ M R direction T u ∥ u∥ M , ∀ u ∈ R dT ,where R A T is the regret of A over a sequence of G-Lipschitz linear losses and R direction T is the regret of (scale-free) adaptive FTRL with a feasible set equal to the unitary ball defined by ∥ • ∥ M .Choosing the algorithm A to be [20, Algorithm 1], we haveR A T (∥ u∥ M ) ≤ O   Gϵ + ∥ u∥ M   V T log ∥ u∥ M √ V T Λ T Gϵ + 1 ∨ G log ∥ u∥ M √ V T Λ T ϵG     , where V T = T t=1 ∥ g t ∥ 2 M -1 and Λ T = log 2 ( T t=1 ∥ g t ∥ 2 M -1 /G 2 ) ≤ O(log 2 T ).Focusing now on the regret of the direction learner, define the distance generating function ψ( x) = [31, Theorem 4.3] , we have that ψ is 1-strongly convex w.r.t ∥ • ∥ M . Hence, using the regret guarantee of Scale-free FTRL, i.e., Theorem 1 of Orabona and Pál [33] , for any v ∈ R dT such that ∥ v∥ M ≤ 1 the regret of the direction learner is1 2 ∥ x 2 ∥ M . UsingR Direction T ( v) ≤ 1 2 ∥ v∥ 2 M + 2.75 T t=1 ∥ g t ∥ 2 M -1 + 3.5 max t≤T ∥ g t ∥ M -1 ≤ O   T t=1 ∥ g t ∥ 2 M -1   . Applying this with v = u ∥ u∥ Mand combining with the previous two displays leads to the bound stated in the proof of Theorem 2.In this section we provide some useful supporting lemmas related to the Haar matrices H n . We first introduce the Haar basis vectors, which make up the columns of the matrix H n . Throughout this section we assume for simplicity that T is a power of 2. Definition 1. For any τ ∈ 2 i : i = 1 : log 2 (T ) and i ∈ [T /τ ], the Haar basis vector at timescale τ and location i is the vector in R T with entriesEQUATIONThe Haar basis vectors are often arranged into the columns of a matrix as follows:EQUATIONT /2 , where h 0 = (1, 1, . . . , 1) ⊤ ∈ R T . This matrix is referred to as the (unnormalized) Haar basis matrix of order n = log 2 (T ). It is well-known that H n has the following equivalent recursive form [38, 11, 37] :EQUATIONSo, for instance, we haveH 1 = H 0 ⊗ 1 1 I 2 0 ⊗ 1 -1 = (1) ⊗ 1 1 (1) ⊗ 1 -1 = 1 1 1 -1 , H 2 = 1 1 1 -1 ⊗ 1 1 1 0 0 1 ⊗ 1 -1 =    1 1 1 0 1 1 -1 0 1 -1 0 1 1 -1 0 -1    ,and so on. For our purposes, we will primaly work in terms of the matrices H n rather than the basis vectors h (τ ) i . The main utility of defining the basis vectors h (τ ) i is that their definition easily implies the following useful result, which states that the Haar basis vectors are sparsely supported w.r.t time. Proposition 5. Let n = log 2 T and let H n ∈ R T ×T be the unnormalized Haar basis matrix of order n. Then for any t ∈ [T ], there at most 1 + log T indices i for which [H n ] t,i ̸ = 0.The proof follows immediately from Definition 1 (i.e., any t can fall into only one of the intervals covered at each of the log 2 (T ) time-scales) and accounting for the additional column h 0 of all 1's.In what follows, we will also use the following well-known relationship between the vec operator and the Kronecker product (see, e.g., Steeb and Shi [38, Chapter 2.11] ). Proposition 6. Let A, B, and C be matrices of appropriate dimensions such that the product ABC exists. Then, vec(ABC) = (C ⊤ ⊗ A)vec(B).The following three lemmas will be used to prove the guarantees of the algorithm characterized in Section 4.1 (Propositions 3 and 4).Lemma 5. Let n = log 2 (T ), v = (v 1 , . . . , v T ) ⊤ ∈ R T ,and let H n be the unnormalized Haar basis matrix of order n. ThenH T n v = H ⊤ n-1 v + I 2 n-1 v - ,wherev + =     v 1 + v 2 v 3 + v 4 . . . v T -1 + v T     , v -=     v 1 -v 2 v 3 -v 4 . . . v T -1 -v T     .Proof. From Equation ( 7), we have thatH ⊤ n v = H n-1 ⊗ 1 1 I 2 n-1 ⊗ 1 -1 ⊤ v = H ⊤ n-1 ⊗ (1 1) I 2 n-1 ⊗ (1 -1) v = H ⊤ n-1 ⊗ (1 1) v [I 2 n-1 ⊗ (1 -1)] v .Moreover, leveraging Proposition 6 we haveH ⊤ n v =     vec (1 1) v 1 v 3 • • • v T -1 v 2 v 4 • • • v T H n-1 vec (1 -1) v 1 v 3 • • • v T -1 v 2 v 4 • • • v T H n-1     =            vec    =v ⊤ + (v 1 + v 2 v 3 + v 4 • • • v T -1 + v T ) H n-1    vec     (v 1 -v 2 v 3 -v 4 • • • v T -1 -v T ) =v ⊤ - I 2 n-1                = H ⊤ n-1 v + I 2 n-1 v - .Lemma 6. Let H n be the unnormalized Haar basis matrix of order n. Then, H n H ⊤ n satisfiesEQUATIONwhere 1 2 n-1 and 0 2 n-1 are 2 n-1 × 2 n-1 matrices of 1's and 0's respectively.Proof. For brevity, let us denote B n = H n H ⊤ n . The first equality follows from elementary properties of block matrices and the Kronecker product: using the recursive form of H n , we haveB n = H n H ⊤ n = H n-1 ⊗ 1 1 I 2 n-1 ⊗ 1 -1 H ⊤ n-1 ⊗ (1 1) I 2 n-1 ⊗ (1 -1) = H n-1 ⊗ 1 1 H ⊤ n-1 ⊗ (1 1) + I 2 n-1 ⊗ 1 -1 I 2 n-1 ⊗ (1 -1) = H n-1 H ⊤ n-1 ⊗ 1 1 (1 1) + I 2 n-1 ⊗ 1 -1 (1 -1) = H n-1 H ⊤ n-1 ⊗ 1 1 1 1 + I 2 n-1 ⊗ 1 -1 -1 1 = B n-1 ⊗ 1 1 1 1 + I 2 n-1 ⊗ 1 -1 -1 1 .To get the second expression, let us proceed by induction. We have B 0 = (1) andB 1 = H 1 H ⊤ 1 = 1 1 1 -1 1 1 1 -1 ⊤ = 2 0 0 2 = B 0 + 1 1 0 1 0 1 B 0 + 1 1 .Next, let us assume that B n satisfiesB n = B n-1 + 1 2 n-1 0 2 n-1 0 2 n-1 B n-1 + 1 2 n-1 .Then, applying the recursive form Equation ( 8) for B n+1 , we haveB n+1 = B n ⊗ 1 1 1 1 + I 2 n ⊗ 1 -1 -1 1 = B n-1 + 1 2 n-1 0 2 n-1 0 2 n-1 B n-1 + 1 2 n-1 ⊗ 1 1 1 1 + I 2 n ⊗ 1 -1 -1 1 =     B n-1 ⊗ 1 1 1 1 + 1 2 n-1 ⊗ 1 1 1 1 0 2 n 0 2 n B n-1 ⊗ 1 1 1 1 + 1 2 n-1 ⊗ 1 1 1 1     +     I 2 n-1 ⊗ 1 -1 -1 1 0 2 n 0 2 n I 2 n ⊗ 1 -1 -1 1     = B n + 1 2 n 0 2 n 0 2 n B n + 1 2 n , ,where the last line observes that 1 2 n-1 ⊗ 1 1 1 1 = 1 2 n and that after adding the two block matrices, the top left and bottom right blocks are bothB n-1 ⊗ 1 1 1 1 + I 2 n-1 ⊗ 1 -1 -1 1 + 1 2 n = B n + 1 2 n ,via Equation (8) . Hence, the stated result follows by induction. Now using this, we have the following bound on the norm of the high-dimensional surrogate losses. Lemma 7. Let n = log 2 (T ), e t be the t th standard basis vector of R T , and for g t ∈ R d let g t = e t ⊗ g t ∈ R dT . Let H n be a Haar matrix of order n and let B = H n ⊗ I d be it's block extension to sequence in R d . Then, we have∥ g t ∥ 2 BB ⊤ = (log T + 1) ∥g t ∥ 2 2 .Proof. Using Lemma 1, we have that∥ g t ∥ 2 BB ⊤ = H n H ⊤ n tt ∥g t ∥ 2 .Moreover, using Equation ( 9) it can easily be seen that the diagonal entries of H n H ⊤ n are log 2 T + 1, so we have ∥ g t ∥ 2 BB ⊤ ≤ (1 + log 2 T ) ∥g t ∥log 2 (T ) i=0 P (⃗ u, 2 i ) ≤ ∥ū∥ 2 2 + 1 4 log (T ) max τ P (⃗ u, τ ), ∥ g t ∥ 2 M -1 = ∥g t ∥ 2 2 (1 + log T ) .Proof. The proof of the claim∥ g t ∥ 2 M -1 = ∥ g t ∥ 2 HH ⊤ = ∥g t ∥ 2 2 [log 2 (T ) + 1] is provided in Lemma 7.To see the form of ∥ u∥ 2 M , let us first write∥ u∥ 2 M = u, [HH ⊤ ] -1 u = H -1 u, H -1 u = H -1 u 2 2 .The result then follows by showing thatEQUATIONso that H -1 u 2 2 = ∥ū∥ 2 2 P (T ) + 1 4 ū(T/2) 1 - ū(T/2)+ . . . + 1 4 ∥u 1 -u 2 ∥ 2 2 + 1 4 ∥u 3 -u 4 ∥ 2 2 + . . . + 1 4 ∥u T -1 -u T ∥ 2 2 = P (1),where for brevity we have dropped the argument ⃗ u on P (⃗ u, τ ).Equation ( 10) is best shown via example; the general case is mostly a tedius exercise which we provide at the end. Assume T = 4, then the Haar matrix of order n = log 2 (T ) = 2 isH 2 =    1 1 1 0 1 1 -1 0 1 -1 0 1 1 -1 0 -1    =      1 2 1 2 1 √ 2 0 1 2 1 2 -1 √ 2 0 1 2 -1 2 0 1 √ 2 1 2 -1 2 0 -1 √ 2      =: H2    2 0 0 0 0 2 0 0 0 0 √ 2 0 0 0 0 √ 2    =:D2.It is well-known that for any T the columns of H log 2 (T ) form an orthogonal basis of R T [41, Chapter 6.1.1], which implies that H 2 is orthonormal. So,H -1 2 = H ⊤ 2 and H -1 2 = ( H 2 D 2 ) -1 = D -1 2 H -1 2 = D -1 2 H ⊤ 2 =     1 2 0 0 0 0 1 2 0 0 0 0 1 √ 2 0 0 0 0 1 √ 2         1 2 1 2 1 2 1 2 1 2 1 2 -1 2 -1 2 1 √ 2 -1 √ 2 0 0 0 0 1 √ 2 -1 √ 2     =     1 4 1 4 1 4 1 4 1 4 1 4 -1 4 -1 4 1 2 -1 2 0 0 0 0 1 2 -1 2     ,which leads to Equation (10) after applying the Kronecker product:EQUATIONEQUATIONEQUATIONI d 4 I d 4 I d 4 -I d 4 -I d 4 I d 2 -I d 2 0 0 0 0 I d 2 -I d 2        u 1 . . . u T    =     u1+u2+u3+u4 4 u1+u2-u3-u4 4 u1-u2 2 u3-u4 2     = 1 2    2ū ū(T/2) 1 - ū(T/2) 2 u 1 -u 2 u 3 -u 4    .More generally, start with d = 1 begin again by factoringH -1 n = D -1 n H ⊤ n = D -2 n H ⊤ n ,where now H n is the normalized Haar basis matrix of order n = log 2 (T ) andD n = Diag   √ T , √ T 2 0, T /2, T /2 e i ⊗ g i , H n h t ⊗ g t = t-1 i=1 (e ⊤ i ⊗ g ⊤ i ) (H n h t ⊗ g t ) = t-1 i=1 e ⊤ i H n h t ⊗ ⟨g i , g t ⟩ = t-1 i=1 ⟨h i , h t ⟩ ⟨g i , g t ⟩ = t-1 i=1 h i ⟨g i , g t ⟩ , h t = t-1 i=1 h i g ⊤ i g t , h t = g t , t-1 i=1 g i h ⊤ i =:Λt h t .From Proposition 5, for any t the vector h t = H ⊤ n e t has only log T + 1 active non-zero elements by construction of the Haar basis, so given Λ t , the product Λ t h t takes a linear combination of log T + 1 vectors in R d , for O(d log T ) operations. Note that the variable Λ t can also be maintained with O(d log T ) operations since each term is g t h ⊤ t , which involves updating O(log T ) columns of Λ t-1 ∈ R d×T . Hence overall we can maintain θ t+1 M -1 using O(d log T ) per-round computation. Lastly, consider the variable θ t+1 . Observe that we can maintain a variable θ t+1 = -H ⊤ n ⊗ I d t s=1 g s using O(d log T ) computation:θ t+1 = -H ⊤ n ⊗ I d t s=1 g s = θ t -H ⊤ n e t ⊗ g t = θ t -(h t ⊗ g t ) ,since h t ⊗ g t is a block vector containing log (T ) + 1 non-zeros blocks of length d. Hence,θ t+1 = (H n H ⊤ n ⊗ I n ) t s=1 g s = (H n ⊗ I n )(H n ⊗ I n ) t s=1 g s = (H n ⊗ I n ) θ t+1 ,and again via the construction of the Haar basis, each row of H n (i.e., each column of H ⊤ n ) has only log T + 1 non-zero entries, we can compute each d × 1 block of θ t+1 using O(d log T ) computation. Finally, observe that in order to implement the direction learner, we need only compute the t th d × 1 block of θ t . Indeed, since for each t, the vector g t = e t ⊗ g t has only d non-zero indices, it suffices to retrieve the corresponding indices of v t to implement direction learner.We note that the memory overhead of maintaining each of these variables can also likely be reduced by more careful bookkeeping, and acknowledging the fact that the algorithm only really needs to retrieve the t th block of w t , since the losses are g t = e t ⊗ g t . We omit these considerations here for brevity.C.1 Proof of Theorem 3 Theorem 3. Let Wealth T := -T t=1 ⟨ g t , w t ⟩ denote the "wealth" of an algorithm A and let (f, f * ) be a Fenchel conjugate pair. Then A guarantees Wealth T ≥ f * T -T t=1 g t for any sequence g 1 , . . . , g T if and only if R T (⃗ u) ≤ f T ( u) for any sequence ⃗ u = (u 1 , . . . , u T ) in W, where u = (u ⊤ 1 , . . . , u ⊤ T ) ⊤ is the concatenation of the sequence ⃗ u into a vector.Proof. Thanks to Proposition 1, the proof is essentially the same as the usual one. We provide the argument here for completeness. From Proposition 1, R T (⃗ u) = R Seq T u) = T t=1 ⟨ g t ,R T (⃗ u) = T t=1 ⟨g t , w t -u t ⟩ = T t=1 ⟨ g t , w t -u⟩ = -Wealth T - T t=1 ⟨ g t , u⟩ ≤ - T t=1 g t , u -f * T - T t=1 g t ≤ sup θ ⟨θ, u⟩ -f * T (θ) = f T ( u) .Similarly, for the other direction, suppose we have R T (⃗ u) = R Seq T ( u) ≤ f T ( u) for any u. Then re-arranging, we have Wealth T ≥ -T t=1 g t , u -f T ( u), and since this holds for any u, we can choose the one that tightens the bound to get Wealth T ≥ sup u -T t=1 g t , u -f T ( u) = f * T (- T t=1 g t ).D Supporting Lemmas Lemma 8. Let Σ ∈ R T ×T be the finite-difference operator, having entriesΣ ij =    1 if i = j -1 if j = i + 1 0 otherwise . Then,1. The inverse of Σ the upper-triangular matrix of 1's:Σ -1 ij = 1 if j ≥ i 0 otherwise , ∀i, j .2. The eigenvalues of Σ and Σ -1 are λ i = 1 for all i ∈ [T ].x → x ⊤ Σx is positive definite.Moreover, the analogous properties hold for the block matrix Σ ⊗ I d ∈ R dT ×dT .Proof. The inverse of Σ is the upper-triangular matrix ∆ characterized by entries∆ ij = 1 if j ≥ i 0 otherwise .To see why, observe that we have Σ T,T ∆ T,T = 1 and for i < T we have Next, since Σ and Σ -1 are upper-triangular, their eigenvalues are equal to their diagonal entries, and hence both have eigenvalues λ i = 1 for all i.EQUATIONTo see that the asymmetric matrix Σ is positive definite, it suffices to show that the symmetric part of Σ, i.e., the matrix Σ S = (Σ + Σ ⊤ )/2, is positive definite [23] . Luckily, Σ S is also a well-known variation of the discrete difference operator and is known to be positive definite [see, e.g., Theorem 7.4.7 in 39].For the block matrix B = Σ ⊗ I d , the inverse is given immediately by the inverse property of the Kronecker product:B -1 = (Σ ⊗ I d ) -1 = Σ -1 ⊗ I d .We also have that B = Σ ⊗ I d and B -1 have eigenvalues λ i = 1 for all i ∈ [dT ], since both are again upper-triangular with 1's on their main diagonal. Finally, we have positive definiteness of B using the fact that the symmetric part of B = Σ ⊗ I d is 1 2 (B + B ⊤ ) = 1 2 (Σ ⊗ I d + Σ ⊤ ⊗ I d ) = 1 2 (Σ + Σ ⊤ ) ⊗ I d by(A) ≤ . . . ≤ λ n (A). Then λ max (A) ≤ Tr(A) n + (n -1) Tr(A ⊤ A) n - Tr(A) n 2 .Justification: Given the theoretical nature of this work, there are no ethical concerns to be addressed.Guidelines:• The answer NA 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).Note that the lower bound is stated for d = 1, in which case Tr(S -1 ) = Tr(M -1 ). 


Decision: This paper studies online convex optimization and investigates dynamic regret minimization by linking this measure with classic static regret. The primary motivation is to consider the unbounded online optimization setup and replace the classic path length with the squared one, which can be much smaller and more favored. The authors show that this objective seems challenging by building the reduction from dynamic regret to static regret over the extended domain. In fact, the authors provide a lower-bound argument to demonstrate the impossibility of achieving this. Instead, they propose novel algorithms to achieve dynamic regret scaling with a locally smooth squared path length, which is a new contribution to the community.

During the review stage, the paper received mixed evaluations. After extensive internal discussion among the reviewers as well as my personal check of the results, I feel those results are interesting and novel. However, as argued by several reviewers, there are indeed several critical issues that need addressing and clarifying before publication:

(1) Potential overstatement of generality: While reviewers agree that the work provides a more general reduction from dynamic regret to comparator-adaptive static bounds compared to Zhang et al. (2023), some paper claims may be overstated. For instance, the title states "an equivalence between dynamic regret and static regret," but the abstract (also elsewhere) suggests that "dynamic regret minimization is equivalent to static regret minimization in an extended decision space," which sounds like the authors have established a universal reduction from dynamic regret to static regret. Evidently, this is inaccurate as the paper does not consider other important OCO setups like exp-concave, strongly convex cases, or bandits settings. The authors should carefully revise these statements throughout the paper to prevent any misleading interpretations. Additionally, as suggested by two reviewers, the paper's title should be more rigorous -- it should reflect that the reduction targets OLO (PS: even for OLO, if more refined problem-dependent regret bounds are considered, I'm not sure if this reduction continues to perform effectively).

(2) Technical soundness of impossible of general squared path length bound: this is an interesting result, as the instance-dependent lower bound is always valuable in dynamic regret research. However, several technical aspects remain unclear, as one reviewer raised. The authors should carefully review and revise these arguments to make them more precise.

Despite these issues, the paper presents valuable and interesting results worthy of knowing to the community. Although the conference venue does not have a mandatory revision system, the authors have committed to addressing the concerns in their rebuttal document. I believe the authors will incorporate these improvements in an updated version and make the paper more accurate. Therefore, I recommend accepting this paper! The authors are requested to revise the paper by incorporating the reviewers' suggestions.

Reviews: review: paper_summary: paper_summary: This paper investigates the problem of dynamic regret minimization in unbounded domains. The authors propose a novel lossless reduction from dynamic regret minimization to static regret minimization by treating the changing comparators in dynamic regret as a fixed one in another decision space with higher dimensions. The key in the reduced static regret minimization is to choose an appropriate matrix norm which is used to transform the static regret bound in lifted domains into a meaningful dynamic regret in the original decision space. Denoting by $M$ the norm-related matrix, this work proposes a novel lower bound regarding the variability penalty $\\|\tilde{u}\\|_M$ and a variance penalty $G^2 \text{Tr} (M^{-1})$. Consequently, the authors proved that a dynamic regret depending on the squared path length is impossible. By contrast, by choosing a specific matrix norm defined by Haar basis matrices, it suffices to achieve a dynamic regret bound with the squared path length defined on some averaged comparators.
strength_weakness: strength_weakness: I have some major questions for the results regarding the squared path length and I hope that the authors can answer the questions to solve my concerns.

1. I believe that the lower bound in Theorem 1 is correct, which lower-bounds by the dynamic regret with $\\|\tilde{u}\\|_M$ and $G^2 \text{Tr} (M^{-1})$. However, I am doubtful about Proposition 2 when translating this lower bound to a dynamic regret measured by the squared path length. Proposition 2 only shows that choosing a specific $M$ does not suffice to achieve a valid squared-path-length dynamic regret. However, it does not rule out the possibility of other choices of $M$. Or, is there some one-to-one mapping between the choice of $M$ and the squared path length? In my point of view, discussions of this issue are missing and I hope that the authors could revise the paper according to it in the revised version.
2. As for upper bounds, the obtained bound (in Section 4) is less favorable than I originally expected. The squared path length is defined on some averaged comparators, which are averaged on the intervals induced by the Harr OLR algorithm. The relationship between the current averaged squared length and the desired squared length is not discussed. On the top of Page 8, the authors show that their result can recover the previous dynamic regret defined with $P_T$ (non-squared path length). However, on Page 2, the authors stated that $P_T$ based dynamic regret is not favorable enough with an overly pessimistic diameter quantity. As a result, implying $P_T$ based dynamic regret is not convincing enough, at least for me, to validate the significance of the obtained result. 
3. The obtained regret also suffers from additional $\log T$ terms, which is not favorable enough in the full information setup. Do previous works with similar setups also suffer from the same issue?
4. The dynamic-to-static reduction is novel. However, when designing algorithms, the computational complexity is not discussed at all, which is pretty important because the dimension is related to time horizon $T$ in the reduced problem. I suggest that the authors could add discussions about computational complexity in the revised version.

Overall, my main concern is that despite the novelty of the dynamic-to-static reduction, to what extent this reduction is significant is not fully discussed. I believe that this reduction is of interest to the community. However, the currently obtained results do not suffice to validate its significance.
questions: questions: A minor type maybe: In Line 24, a missing inverse operator in the matrix $S$? (i.e., $[H_n H_n^\top]^{-1}$ but not $H_n H_n^\top$?)
limitations: limitations: The authors have adequately addressed the limitations and, if applicable, potential negative societal impact of their work.
paper_summary: paper_summary: The main contribution of the paper is showing that, by `lifting' an online linear optimization (OLO) problem to a higher dimensional space, the dynamic regret in the original setting is equal to the $\textit{static}$ regret achieved in the higher dimensional setting. While simple, this clean reduction allows easier and more elegant reasoning about how to develop and analyze dynamic regret algorithms since static regret algorithms and analyses are so well studied and understood. 

They then employ this reduction to prove the existence of a trade-off between comparator variability penalty in terms of a $M$ matrix norm and $G^2 Tr(M^{-1})$, where $G$ is the Lipschitz parameter of the losses. By choosing $M$ in such a way that the comparator variability term becomes the squared path-length, they are able to show that adapting a dynamic regret rate to the squared path-length implies a supra-linear (i.e., vacuous) guarantee.

They complement the above general trade-off by providing an algorithm that is able to match the lower bounds along the frontier implied by different specifications of $M$. They instantiate this with a particular matrix setting and attain a corresponding positive result which says it is possible to instead adapt to a modified definition of squared path-length (more specifically, a locally smoothed counterpart).
strength_weakness: strength_weakness: Some weaknesses of the paper are that the focus on matrix norms in Section 3 may be a bit limited in scope and that the statement of Theorem 1 is quite convoluted. More broadly, having additional implications of the equivalence would be desirable (e.g., having a more thorough and completed version of Section 5 and/or a more comprehensive list of observations in a similar vein).
questions: questions: - Do you believe there are any implications of your reduction that are particularly useful from a practical/deployment perspective, or do you see the contribution as being a strictly conceptual one?
- Do you have any additional intuition for the locally-smoothed path-length quantity? For example, how smoothed would one generally expect this quantity to be?
limitations: limitations: The authors have addressed limitations of their work.
paper_summary: paper_summary: This paper presents a reduction from the dynamic regret minimization for Online Convex Optimization (OCO) to a static regret minimization problem over an extended domain. Using this reduction, the authors establish a lower bound that highlights the trade-off between the variation of the comparator and the variance of the gradient norm. This general lower bound indicates that a squared path-length bound is impossible. Furthermore, the authors provide a general upper bound for dynamic regret based on techniques from parameter-free online learning. By specifying $M$, the paper demonstrates that a new type of squared dynamic regret bound is achievable.
strength_weakness: strength_weakness: - One of my main concerns about the paper is that the results appear to be somewhat overstated. The abstract claims that "we show that dynamic regret minimization is equivalent to static regret minimization in an extended decision space." This claim is somewhat misleading to me, as the proposed reduction only applies to the online linear optimization problem (or OCO with linearized surrogate loss). It is unclear if the proposed reduction holds for a broader range of dynamic regret minimization problems, such as those involving exp-concave or strongly convex loss functions. If not, it would be more appropriate to explicitly mention this limitation in the title and abstract and to provide a more detailed discussion on these limitations in the main paper.

- The high-level idea of this paper is quite similar to that of Zhang et al., 2023. Both approaches convert the dynamic regret minimization problem into a static regret minimization problem in another domain, using comparator-adaptive online learning methods to minimize extended static regret. While the authors discuss this in the related work section, it might be beneficial to explicitly state that previous work has already somewhat demonstrated equivalence between the dynamic regret minimization and static regret minimization problems.

-  As mentioned earlier, a similar reduction was presented in Section 2.2 of Zhang et al., 2023. It would be helpful if the authors provided a more detailed comparison of the two reductions. In the related work section, the paper states, "We take a similar but slightly more general approach." A more detailed explanation of how Proposition 1 generalizes previous work would be beneficial. Specifically, it would be useful to clarify whether the proposition can be derived by selecting a specific dictionary in Zhang et al., 2023. A more detailed discussion in Section 2 of this paper would be advantageous.

Overall, I find the paper interesting, but I am concerned about the overstated contributions and the insufficient comparison with previous work. I would be happy to raise my score if these issues are properly addressed.

Reference: Zhiyu Zhang, Ashok Cutkosky, and Ioannis Ch. Paschalidis. Unconstrained dynamic regret via sparse coding, 2023.

===post-rebuttal===
My primary concern was the significance of the proposed framework compared with Zhang et al. (2023) and the overstatement regarding the generality of the framework. After several discussions with the authors, I am convinced that the paper offers a more flexible and general framework for handling the dynamic regret minimization problem beyond the work of Zhang et al. (2023). To reflect this, I have updated my score to 6. Nevertheless, I still encourage the authors to clarify the limitations and provide a more detailed discussion on the contributions of the proposed framework in the revision.
questions: questions: Please refer to the weakness part.
limitations: limitations: This paper is theoretical in nature, and I do not identify any potential negative societal impact.
paper_summary: paper_summary: This paper studied dynamic regret minimisation in convex optimisation. First, they proved some interesting equivalence between dynamic regret and static regret on extended decision space. Based on this observation, they showed a lower bound which implying that the hypothesis that optimal dynamic regret scales with square path length is impossible. The authors then provided an algorithm that incur regret scales with new notion of path length, which match the novel lower bound.
strength_weakness: strength_weakness: I found the writing of this paper quite difficult to follow, especially in the main sections (3 and 4). The comparison between the lower bound and upper bound could be better explained.

My question: The lower bound is $\tilde \Omega(\max_M G\sqrt{||\tilde{u}||_M \mathrm{Tr}(M) })$, and the upper bound essentially is $\tilde O(\min_M G\sqrt{||\tilde{u}||_M \mathrm{Tr}(M) })$. However, without strong duality on regret, there still seems to be a gap between the lower bound and upper bound. Correct me if I misunderstood, but I cannot find the reason why the lower bound and upper bound are tight as claimed in the paper.
questions: questions: See weaknesses
limitations: limitations: Authors did discuss the limitation and potential future works.
paper_summary: paper_summary: The paper addresses the problem of minimizing dynamic regret. The main goal is to provide a unified perspective on the problems of minimizing both dynamic and static regret. The first key contribution, presented in Proposition 1, is an interesting and straightforward observation demonstrating a general reduction from dynamic to static regret, showing the equivalence between these two notions.

In Theorem 1, the paper establishes a lower bound, indicating that squared path-length incurs a linear penalty, making adaptation to squared path-length impossible.

Furthermore, using a parameter-free algorithm in Algorithm 2, the paper achieves an upper bound that matches the previously derived lower bound for any weighted norm 
$\|\cdot\|_{M}$. 

In Section 4.1, the authors discuss the suitable choice for $M$. By setting $M=(HH^{\top}) ^{−1}$, where 
$H$ is the unnormalized Haar basis matrix, they derive in Proposition 3 an upper bound for the regret that fully decouples comparators and gradient terms.
strength_weakness: strength_weakness: I do not see any particular weaknesses in the paper.

Minor point: There are typos in lines 164 to 167. $V$ should be $V_T$ and $\epsilon$ should be $\epsilon_T$.
questions: questions: I would like to know which measures of variability the authors expect to obtain with different choices of $M$ that yield reasonable and significant regret bounds.
limitations: limitations: The authors addressed the limitations of their work.
paper_summary: paper_summary: This paper demonstrates that dynamic regret minimization can be reduced to static regret minimization by embedding the comparator sequence into a higher-dimensional space, allowing the use of static regret algorithms for dynamic settings. It establishes a trade-off between the penalties associated with loss variance and comparator sequence variability, proving that achieving regret bounds purely based on the squared path-length without additional penalties is infeasible. Additionally, the paper introduces a new measure of variability based on the locally-smoothed squared path-length, providing a more practical approach to managing dynamic regret.
strength_weakness: strength_weakness: - My major concern is the main titile could be somewhat overclaimed, as the proposed reduciton is restricted in OLO (or reduce OCO to OLO). Though I admit that analysis in non-convex problems (in bandit feedback) could be extremely hard, dynamic regret and static regret is still discussed in these problems. So may be ''DR is equal to SR in OCO'' may be more suitable.

- The approach involves embedding the comparator sequence into a higher-dimensional space, which could significantly increase computational complexity. Related concerns should be discussed, particularly in terms of implementing the proposed methods in large-scale or real-time applications. 

- The paper does not provide intuitive examples or case studies to illustrate how to obtain dynamic regret in practical problems. I believe a simple example of existing problems (for example, non-stationary OCO) allows us to compare dynamic regret obtained by this reduction with existing studies, making it easier to understand.

- I'm not fully convinced by purely theoretical results. May be adding some simple evaluations to demonstrate the dynamic regret is indeed same as static regret by the proposed reduction can provide empirical evidences.

- The reasons for choosing this locally-smoothed square path-length is not clear. If I get it right, path-lengthes sharing similar local-smoothness would all fullfill the requirements. Meanwhile, this locally-smoothed square path-length is too detailed such that it may loose empirical intuitions or physical meanings to some extent.
questions: questions: 1. Does the high-dimensional embedding reduction also hold for adpative regret (to static regret)?
2. Can we directly design a unified algorithm (best-of-both-worlds) without knowing the types of regret based on this reduction?
limitations: limitations: \

Comments: title: Thanks for the response
Thanks for the feedback
Acknowledgement of response
Comments to Rebuttal
Rebuttal acknowledgment
comment: Thank you again for taking the time to honestly engage in the discussion with us. We understand your perspective and will incorporate all the insights gained from our discussion here to improve the clarity of the main text.

> I understand that one can use other methods to achieve adaptivity to the comparator sequence, but it is clear that not just any strategy can be applied. Achieving meaningful dynamic results still requires specific techniques to minimize the converted static regret. 

As a brief final note, would like to point out that the two referenced statements referenced do not contradict. While it is true that only certain choices will lead to meaningful guarantees, this is true of *any* general framework and is not unique to ours. For instance, we hope we can agree that FTRL and mirror descent can be considered ``general frameworks'' for static regret minimization, yet not all sequences of convex regularizers lead to meaningful guarantees. This does not make these frameworks less valuable, and indeed many of the interesting questions in online learning revolve around *which choices* of regularizer lead to meaningful guarantees under which assumptions. This is analogous to the choice of strategy to be applied in our framework.
I think there may be some misunderstanding from the authors regarding my previous response. My intention was never to criticise the paper for not achieving improved dynamic regret for exp-concave functions. Rather, it is taken as an example to illustrate that some parts of the paper are overstated, as evidenced by the claim I referenced earlier. Nevertheless, I appreciate the authors' efforts in making the revisions.

> The use of comparator-adaptive algorithms is just a convenient way to achieve adaptivity to an unknown comparator norm

I understand that one can use other methods to achieve adaptivity to the comparator sequence, but it is clear that not just any strategy can be applied. Achieving meaningful dynamic results still requires specific techniques to minimize the converted static regret. While the range of algorithms that can be used might extend beyond those in Zhang et al., 2023, the earlier statement, "The key difference is that we provide a general equivalence between static and dynamic regret that any strategy can be plugged into," along with the claim, "yet it allows us to immediately apply all the usual techniques and approaches from the static regret setting," is overstated to me.
First of all, we thank the reviewer for reconsidering their criticism about exp-concave losses and strongly convex functions, we appreciate the intellectual honesty.

> the paper shares the same limitations as Zhang et al. (2023), rather than being a truly "general framework"

We might be nitpicking on the definition of ``general framework''. Does our framework recover any optimal rate for any kind of convex loss used in the dynamic regret literature? Clearly not, but it was never our aim. However, I think we can agree that we are strictly more general than Zhang et al. (2023), for the reasons we listed above, and this generality is non-trivial (for instance, it allows us to prove lower bounds that the framework of Zhang et al (2023) could not). Also, our paper and Zhang et al. (2023) focus on different aspects of the dynamic regret problem, so we do not really see why these two approaches ought to be considered as being in conflict; they both make unique and novel contributions to the literature.


> Some aspects of the presentation are confusing to me.

While in our eyes our scope and limitations were clear, it is possible we might overlooked this aspect and we appreciate the feedback to make the message of our paper sharper. As already discussed with Reviewer YDMs and bfmX, we are very happy to change the text to emphasize that we focus on linear and linearized losses in all the relevant parts of the paper, and clearly specify that we do not explicitly leverage the curvature of the losses, as well as specify that our main contribution is about a way to analyze trade-offs in measures of dynamic regret. Future work might explore the aspect of curvature, possibly following the approach we sketched above.

> I believe it is still necessary to use comparator-adaptive algorithms to achieve meaningful dynamic regret.

This is not necessarily the case; the use of comparator-adaptive algorithms is just a convenient way to achieve adaptivity to an unknown comparator norm (and thus to the variability of the comparator sequence via our reduction), but it is not necessarily the only way to achieve meaningful adaptivity to the comparator sequence. For instance, the Metagrad algorithm of van Erven \& Koolen (2016) achieves a guarantee which adapts to an unknown comparator in the static bounded domain setting but it is even stronger than the usual comparator-adaptive algorithms which are leveraged by this work and by Zhang et al. (2023). It may be possible to apply such an algorithm in our framework to get new results which would not otherwise be possible using the framework of Zhang et al (2023). Of course, this would entail additional computational considerations, but solving all these details is beyond the scope of this rebuttal and would be an interesting direction for future work.
I agree that applying the work to exp-concave losses and strongly convex functions should not be a critical point, but it does reveal that the paper shares the same limitations as Zhang et al. (2023), rather than being a truly "general framework." Some aspects of the presentation are confusing to me. For instance, the abstract claims, "we show that dynamic regret minimization is equivalent to static regret minimization in an extended decision space." without any statement on the condition. Similarly, the response states, "The key difference is that we provide a *general equivalence* between static and dynamic regret that *any strategy* can be plugged into." (I believe it is still necessary to use comparator-adaptive algorithms to achieve meaningful dynamic regret.) Furthermore, line 30 asserts, "Note that OCO problems can *always* be reduced to OLO via the well-known inequality," and lines 121-123 claim, "Proposition 1 is a regret equivalence—we *lose nothing* by taking this perspective, yet it allows us to immediately apply *all the usual techniques* and approaches from the static regret setting."

In my view, a more concise contribution would be to present a general framework to reduce minimizing dynamic regret to obtain comparator-adaptive static regret bound for OLO case. I strongly recommend that the authors clarify this point, particularly in the abstract, introduction, and reduction sections.
We can agree that the squared path-length must appear in the expression,
so what remains is why the leading term $\langle v,\tilde u\rangle^2$
must appear. In the case of static regret, wherein $u_1=\dots=u_T=u$,
there must be a term which reduces to $\\|u\\|^2$, since otherwise the
guarantee would violate the existing $\tilde\Omega(\\|u\\|\sqrt{T})$ lower
bounds for static regret. For any $v\ne 0$, the term
$\langle v,\tilde u\rangle^2$ is a strict generalization of the
$\\|u\\|^2$ term that must appear in the static case, but also captures
any possible combination of the $u_t$'s (such as $\bar{u}=1/T\sum_tu_t$)
which could appear using a weighted norm.

One can surely consider other choices of matrices that result in more
terms *in addition* to the two terms above. One might wonder if only
non-positive terms can be added, but it is easy to see that this would
make the $\Omega(T^2)$ penalty even bigger (because the matrix $Q$
corresponding to these terms would be negative semi-definite and the
eigenvalues of $M+Q$ would be smaller than the one of $M$ by Weyl's
inequality), so it is not a possibility. Thus, one can only add terms
that are non-negative or whose sign depends on the $u_i$. But, as we
wrote above, this would result in something that is not the squared path
length anymore! For example, the average squared path norm almost
contains the squared path norm, and it would be easy to make it even
bigger so that is exactly contains it, but it is clearly not the squared
path norm anymore.
> it is still unclear to me how the proposed reduction can be applied to minimize the dynamic regret bound for exp-concave or strongly convex functions. 

We are genuinely puzzled by this comment and we kindly invite the reviewer to reconsider it.
We showed above that our equivalence *can* be extended to other losses as well *just because the reviewer wondered ``if the proposed reduction holds for a broader range of dynamic regret minimization problems''*, but this was never a claim in our paper!
It seems very unfair to be penalized for something that is completely orthogonal to the contribution of our paper. It should be very clear that we focus on linear losses and linearized convex losses, but we are happy to emphasize it more in the text, to avoid any misunderstanding. 
That said, focusing on linear losses is actually very common in this literature, even in the recent paper by Zhang et al. (2023), which also applies to linear losses and has no straightforward way to achieve the optimal bound for exp-concave losses.



> Both in the main paper and the feedback, the analysis of the squared path-length bound is presented as a prominent example demonstrating the advantage of the proposed framework.

We respectfully but firmly disagree with this mischaracterization of our results: as we just agreed with Reviewer YDMs, the averaged squared path length is just an example, not the main contribution. Instead, as we wrote above, our main contribution is about *a framework that allows to reason on the trade-offs of measures of dynamic regret, both in terms of upper and lower bounds.* We also agreed with Reviewer YDMs that our text did not clearly convey this message: We apologize for it and we will improve it. Clearly, none of these trade-offs are present in the beautiful work of Zhang et al. (2023), that instead focuses on orthogonal aspects. This is evident from the fact that their framework does not enable one to prove lower bounds.
Thank you for the detailed response. However, I remain concerned about the generality of the proposed reduction as claimed by the authors. 

Regarding the first point, it is still unclear to me how the proposed reduction can be applied to minimize the dynamic regret bound for exp-concave or strongly convex functions. While one could indeed introduce an additional Bregman divergence term, the subsequent analysis required to achieve improved dynamic regret for exp-concave functions (e.g. the rate in [1]) is far from straightforward to me. In this regard, the proposed reduction does not necessarily simplify the analysis for minimizing dynamic regret but rather shifts it to an analysis focused on the comparator-adaptive static regret bound, a perspective first introduced by Zhang et al., 2023. 

As for the comparison with Zhang et al., 2023, I appreciate the authors' feedback on the generality of the proposed reduction. However, the significance of this generality remains unclear. Both in the main paper and the feedback, the analysis of the squared path-length bound is presented as a prominent example demonstrating the advantage of the proposed framework. As other reviewers have pointed out, the advantage and significance of the proposed squared path-length are still not entirely evident.

[1] Baby and Wang. Optimal Dynamic Regret in Exp-Concave Online Learning. COLT 2021.
Thanks for the timely feedback. I am happy that the authors and I have reached a certain consensus. I have only one remaining question about the choice of $M$. I do not understand why $M$ has to be in the specific form of  $\\|\tilde{u}\\|_{M}^{2} = \langle v,  \tilde{u}\rangle^2 + \sum\_{t=2}^T \\|u_t - u\_{t-1}\\|^2$? Are there other possibility of $M$ such that the squared path length can still be derived?
Thanks for your comments and further questions, this discussion is very useful for us.

> About the main contribution

The reviewer is very right and we will definitely follow their suggestion.

> About the relationship of the averaged path length with the standard squared one

Yes, this is a good catch: you are correct that $\bar P(1,\vec{u})$ is actually
slightly better than the squared path-length on its own. Our apologies for the
confusion regarding this detail.
This does not significantly change our discussion so far; with this correction
in mind, our example
shows a case where our measure is actually better than the squared path-length. Moreover, we still have the property that the averaged square path-length is
proportional to $T(b-a)^{2}$ while the usual $MP_{T}^{\\|\cdot\\|}$ dependence is proportional to $T\\|b-a\\|\max(b,a)$, and hence can also be arbitrarily better
than the dependencies appearing in prior works.

We agree with the reviewer: the $\max$ over time-scales does make it difficult to precisely
quantify the difference to the regular squared path-length.
However, this result is the first squared-path-length-like result *of any kind* which has been
achieved for arbitrary comparator sequences.
As stated earlier, we believe these are reasonable compromises to make while still achieving a result which captures a similar essence to the ideal, but impossible to achieve, result.



> About the without-loss-of-generality choice of $M$

Suppose that there are two matrices $M_1$ and $M_2$ such that for any $\tilde u$ we have
$$
\\|\tilde u\\|\_{M_1}^{2} = \langle v,\tilde u\rangle^{2} + \sum_{t=2}^{T}\\|u_{t}-u_{t-1}\\|^{2},
$$
and
$$
\\|\tilde u\\|\_{M_2}^{2} = \langle v,\tilde u\rangle^{2} + \sum_{t=2}^{T}\\|u_{t}-u_{t-1}\\|^{2}~.
$$
Given the definition of the weighted norm, this implies that $\tilde{u}^\top (M_1-M_2) \tilde{u}=0$ for any $\tilde{u}$. Given that this holds for any $\tilde{u}$, this implies that $M_1-M_2$ is the zero matrix, that is, $M_1=M_2$ (see, e.g., https://math.stackexchange.com/questions/3314271/when-does-a-quadratic-form-being-equal-to-zero-implies-the-underlying-matrix-is)
Thanks for your detailed explainations, all my concerns are correctly addressed.
Thanks for the detailed feedback. I have the following comments and questions.

1. **About the main contribution**: The authors said that the results of the (averaged) squared path length are not the main contribution of this work. However, if this is true, from my point of view, the introduction part should be reorganized to emphasize more about this kind of trade-off. The current version of the introduction part starts from the standard path length, shows that it is less favorable in unbounded domains, and introduces the desired quantity of squared path length. This would make readers certainly feel that this work aims to achieve some kind of dynamic regret in terms of the squared path length, as also summarized as the second contribution of this work on Page 2. I suggest that the authors could revise the paper to make the main contribution that you wanna claim clearer.

2. **About the relationship of the averaged path length with the standard squared one**: The authors' explanations have solved part of my concerns. From your response, I understand that Line 239 actually provides $\sum_{\tau=1}^N \bar{P}(\tau, u) \le N \max_{\tau} \bar{P}(\tau, u)$. However, there is a $\max$ operator on the RHS. While I understand that $\bar{P}(\tau=1, u)$ is similar to the desired path length, the $\max$ operator makes it hard to provide a clear relationship between the averaged path length and the squared one. Besides, when $\tau=1$, $\bar{P}(\tau=1, u)$ looks like $\\|u_1 - u_2\\|^2 + \\|u_3 - u_4\\|^2 + \cdots$. This quantity seems to be better than the squared path length by omitting terms like $\\|u_2 - u_3\\|^2$, $\\|u_4 - u_5\\|^2$, etc? Could the authors provide some further explanations about the relationship between $\bar{P}(\tau=1, u)$ and the standard squared path length? To conclude, in this comment, I understand that there is no direct relationship between the averaged path length and the standard squared one due to the $\max$ operator. Am I right?

3. **About being able to aggregate multiple algorithms**: Thanks for the reply. I agree with the authors now.

4. **About the without-loss-of-generality choice of $M$**: Sorry for the confusion. I was referring to the second point you said. I am still confused about whether this choice of $M$ is ***the only*** way to get the squared path length. If not, you cannot prove that it is impossible to achieve the squared path length dynamic regret. Some explanations of the authors are mainly heuristic but without rigorous proofs. It means that it is still possible to achieve the squared path length by choosing another unknown $M$. The authors still cannot rule out this kind of possibility, do you?

At last, thanks again for the very detailed responses.
Thank you for clarifying the practical implications! I maintain my positive score (7).
Thanks for engaging with us, we are happy to discuss these points
further.

However, before the specific points, we would like to stress once again the averaged squared path length is only an example of the generality of the framework and not our main contribution. Focusing too much on it might hide the fact that the main message of our paper is *a framework that allows to reason on the trade-offs of measures of dynamic regret, both in terms of upper and lower bounds*. As an illustrative analogy, the seminal work of Nemirovski & Yuudin (1983) introduces the mirror descent framework and its general guarantee, and then proceeds to show specific examples such as $p$-norms. The example is not the main contribution; the framework and the existence of a trade-off are the key contributions upon which a large literature of work has been developed by the community.

>\"this is only a $\log$ factor more than the square path length at the worst scale" [...] Could the authors provide some further explanations or derivations on this statement?

From its definition, the average squared path length is the sum of the squared path length at *all possible time scales*. Given that there are $O(\log T)$ time scales (line 230), in the *worst case* the averaged path length can be at most $O(\log T)$ times the path length at the worst scale (i.e., $\sum_{\tau=1}^{N}\bar{P}(\tau,\vec{u})\le N\max_{\tau}\bar{P}(\tau,\vec{u})$ where $\bar{P}(\tau,\vec{u})$ denotes the averaged square path-length at timescale $\tau$), as detailed in the global response. Note that the standard squared path length corresponds to scale $\tau=1$.

>I do not agree with the first motivation for the squared path length, which shows that it is never worse (up to polylog factors) than the usual path length

We are not sure how this could be controversial: any new measure should be at least as good (up to polylog factors) as the measure used in prior works. However, this is not a proof of superiority, as the reviewer seems to imply; this is a sanity check showing that *in the worst case*, the new variability penalty is at least as good as the one in prior works. However, there are cases where it can be significantly better: in our global response, we provide an example in which the averaged square path-length is significantly smaller precisely thanks to the diameter: the averaged squared path length is equal to the squared path length and it is $T (a-b)^2$, while the $M P_T^{\\|\cdot\\|}$ dependence, where $M$ is the diameter term, is $O(T |a-b| \max(b,a)),$ which can be arbitrarily worse.

>Being able to aggregate multiple algorithms...

Our results show there are trade-offs and the best choice of $M$ will be data-dependent, so trying to quantify gains is hopeless in general. Instead, we can easily aggregate algorithms and compete with the best matrix among a number of different ones. Is it important? We very much believe so! Once again, we would like to point out the similarity with $p$-norms: Theorem 2 in Cutkosky (2019) used the same idea to have a static regret with respect to all $p$-norm: no explicit gain is showed as well, but it should be clear the importance of his result. We show how to do this for *different measures of dynamic regret* and we are not aware of anything similar in this literature.

>I do not understand why this choice of is \"without loss of generality\" since this choice seems to rule out a large number of possible Ms. Could the authors provide more explanations on this point?

We are not completely sure we understand your question.

In case you are wondering how it is possible to decompose $M$ into a product of a matrix and its transpose, this is always true because $M$ is symmetric and positive definite. Note that only the matrix $M$ matters and not its representation through $\Sigma$.

In case you are wondering why we restrict our attention only to the matrices $M$ that result in the term $\langle v, \tilde u\rangle^{2} + \sum_{t=2}^{T}\\|u_{t}-u_{t-1}\\|^{2}$ and not to some other expression. Indeed, we proved that adding another terms to the above two terms can kill the $\Omega(T^2)$ factor: this is exactly the case of the averaged squared path length that we propose. However, any such addition would result in a measure that it is not the squared path length anymore. Hence, our claim is correct: The squared path length cannot be achieved without incurring the stated penalty.

Finally, in case you are wondering if it is possible to find two different matrices that result in $\langle v, \tilde u\rangle^{2} + \sum_{t=2}^{T}\\|u_{t}-u_{t-1}\\|^{2}$, this is possible only up to permutations of the rows of $\Sigma$, as we explained in the global response.

Please let us know if you meant something else.
Thanks to the authors for the detailed reply. I still have some follow-up questions about the authors' rebuttal, and hope that the authors could resolve my concerns.

1. I have read the global response about the motivation of the averaged squared path length. The authors said, "It turns out that in the worst case, this is only a $\log T$ factor more than the square path length at the worst scale; see first inequality in line 239". Could the authors provide some further explanations or derivations on this statement? Does it mean that the averaged path length can be upper-bounded by the desired squared path length only by a $\log T$ factor overhead?

2. I do not agree with the first motivation for the squared path length, which shows that it is never worse (up to polylog factors) than the usual path length $P_T^{\\|\cdot\\|}$. When transforming the averaged path length into $P_T^{\\|\cdot\\|}$, there is an additional term of $\bar{D}$ (see the equation in line 239). However, as the authors have said in the introduction part, this diameter quantity is overly pessimistic and thus cannot be used to validate the significance of the obtained results.

3. Being able to aggregate multiple algorithms, as stated at the end of the global response, is an advantage. However, given that we cannot identify a good enough choice of $M$ here (please refer to the next point below), how good the aggregated guarantee will be cannot be explicitly illuminated. I acknowledge that this is an advantage of the obtained result. However, this advantage seems to not be able to bring some explicit improvements compared with the current bound.

4. For my first weakness in the original review, the authors responded that "Hence, without loss of generality we can focus on 
$\Sigma$ satisfying...". I do not understand why this choice of $M$ is "without loss of generality" since this choice seems to rule out a large number of possible Ms. Could the authors provide more explanations on this point?
Many thanks for your clarification.
I would like to thank the authors for the rebuttal. For now, I will maintain my current score. I plan to discuss the paper with the other reviewers and look forward to the author's discussions with them as well. I will update my score accordingly.