An Equivalence Between Static and Dynamic Regret Minimization
Authors: Andrew Jacobsen
Francesco Orabona
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
dynamic regret
non-stationary
parameter-free
Primary area: online_learning
TL;DR: We provide a simple framework for minimizing dynamic regret using algorithms designed for static regret

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.

An Equivalence Between Static and Dynamic Regret Minimization
Andrew Jacobsen" Università degli Studi di Milano Politeenico di Milano jaaaandddeeeaasssenn....e jacobsen..nn...e.. com
Francesco Orabona
KAUST
francesco@orabona.co com
contact@andrew-
Abstract
We study the problem of dynamic regret minimization in online convex opti- mization, in which the objective to minimize the difference between the cu- mulative loss of an algorithm and that of an arbitrary sequence of compara- tors. 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 show that for linear losses, dynamic regret minimization is equivalent to static regret minimization in extended decision space. Using this simple observa- tion, we show that there is a frontier of lower bounds trading off penalties due 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, also prove for the first time that adapting the squared path-length of an arbitrary sequence of comparators to achieve regret Rr ur) S (
u,+1 []]] is impossible. However, using our framework introduce alternative notion of variability based locally- smoothed comparator sequence ,,,..., ū7, and provide an algorithm guarantee- ing dynamic regret of the form (u1....... wr) < O(VTE, ã uu+1ll²), while still matching the worst case the usual path-length dependencies up polylogarithmic terms.
Introduction
This paper introduces new techniques for Online Convex Optimization (OCO), framework for designing and analyzing algorithms which learn on-the-fly from stream of data [14, 51, 5, 31, 6]. Formally, consider rounds of interaction between the learner and their environment. In each round, the learner chooses w. W from convex feasible W Rd the environment reveals G-Lipschitz convex loss function & W - R, and the learner incurs a loss of (ww,). The classic objective in this setting is minimize the learner's regret relative any fixed benchmark W:
(y)
Σ -((w)))((u))).))
In this paper, we study the more general problem of minimizing the learner's regret relative to any sequence of benchmarks uI....,uy uT E W [17, 18]:
R ur
Σ (l((w.)) le(1)))
"ork done while visiting Optimal Lab at KAUST.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

This objective is typically referred to dynamic regret, distinguish it from the special case where the comparator sequence is fixed un _... ur (referred to as static regret). We focus in particular on the special case of Online Linear Optimization (OLO), in which (((w) = (g.- w) for some 9r. R Note that OCO problems
always be reduced to OLO via the well-known inequality
fe(w,) - (z) I (g,, wi u) for 9. E (w,()) where de, (w)) is the subdifferential set of & at we [see, e.g., 36], throughout this paper we will focus the OLO setting.
Intuitively, the sequence of comparators u1,..... ur varies too much, should impossible to achieve low dynamic regret. On the other hand, we know it is possible to achieve sublinear regret the sequence of comparators is constant, í.e., U1 = case. Hence, we need way to quantify the complexity, or variability, of the comparator sequence. The most commonly used notion of complexity in this regard the path-length the comparator sequence [17, 18], defined
uT, because this simply the static
Pl
U uz-1/1
It is possible to show that Online Gradient Descent has a dynamic regret of O(D D( in bounded domains, where 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(v DP! GVT) and shown to be minimax optimal by Zhang et al. [46].
Notice that the path-length bounds scale with rather pessimistic constant of D sup wW ||w w'll A better bound would instead scale with the squared path-length:
P
U4 2111
which be significantly smaller? than the penalty in the bound above: P 1| S DP How-
ever, guarantees scaling with P!l-11 not well understood in general compared with the more common pIl-11 bounds, and have only been obtained by restricting the comparator sequence to u, = argmin (ww) 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 Ö( maxe, ||u u P (T) in the worst case [20, 25, 47]. Of particular interest, Jacobsen and Cutkosky [20], Zhang et al. [47] achieve bounds of the form
Rr( UT) S
pll Σ
|| - will
which avoids the pessimistic multiplicative penalty of max,, ||e, - uu ||. but results 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 as about
Ein l1 In fact, it not clear in general how potential trade-offs that may result from adapting to different measures of variability.
(u ...,...... uT) So (VP!
Contributions. In this paper, we show how 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(V |!ll11 ΣT [l..11 is not possible in general (Section 3), We do this by proving
Note that the bound of Zhang et al. [46] trivially implics a squared path-length dependence since P! TPI so one can obtain a bound of O(v DP! (lT) S ((D)/2(P) 1AAGT//))///)////)) However, this bound is not interesting because it does not remove the dependence on and it better than the existing
v /PP!! GVT bound.

---

novel lower bound showing that there is 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 trade- off's 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 (II-I,, ll-) 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 with
pll-11 (u1 -........ ur) Σ u a a|
where u!" (T) is a local average of the comparator sequence at a timescale of T (see Section 4.1). Similar
to P7 I12 this variability measure maintains the property that it matches the worst-case guarantees
based on path-length up to polylogarithmic terms, i.e., P/.-11 I Ō(maxt,t |/, - ue || P|.-I). These are the first guarantees for general OCO that fully decouple the variance and variability penalties for dynamic regret without explicitly incurring pessimistic max,, |/u, - ur| 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-dimensiooal "signal" which is decomposed into frequency domain representation using a dictionary of features. Then, for each feature vector the dictionary, 1 1-dimensional parameter-free [32, 28] algorithm used to learn how well that feature correlates with the losses. This allows one to compete with an arbitrary comparator sequence, so long as can be represented in terms of the chosen dictionary of features. We take similar but slightly more general approach. Our framework also represents the comparator sequence as a nigh-dimensional signal, but we instead use this signal to define an equivalent static regret problem, a perspective that allows 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 Etn supwew! (ea(w) le+1 (w)) [3, 22, 4] or deviation of the comparator from a given dynamical model EEn lee, - (u,-)) )l [16]. Alternative variance
penalties have also been studied in the dynamic setting, such as the small-loss penalties Σt=1 (u,)) or gradient variation penalties Σi suP [[V[[(w) - Vl++ (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 also an often ignored connection between measures of comparator variability and the function classes studied in non non-parametric regression. In particular, considering the case that the losses are (x(x) (x uz} )2 then the sequence of comparators ui...., ur with bounded path length Cr and bounded squared path length (C7)² corresponds to the sequence with discrete total variation bounded by Cr and the discrete Sobolev class with bound Ct, 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 e maxm are denoted by Ary for i = I..... and j = 1,..., m. Similarly, the elements of a vector u E 12d are u, for = 1,...,d. d. The Kronecker product of matrices A E Rmxxn and B E IRpx is the block matrix defined by
A1,1 AI. B
A 18 B ==
Am, B Ama
3

---

Algorithm Dynamic-to-Static Reduction
Input Domain W S R2, Online Learning Algorithm A with domain W
for 1::1 T::Tor do
Get w (w, ...... ".: w E W from A
Play we w (1) W and observe 9, E (w,)
Pass 9: er 9, (0] 0 9, 0
) W to
indices te]d((-1)+1dd)
end
We let e, denote the hhh standard basis vector RT and Ia the d x identity matrix. For square matrix A, Diag (A) is the diagonal matrix that contains the elements of the diagonal of A. For positive definite matrix M, we define the weighted norm ||x||| M V(z, Mæ).. For matrix A m=x, denote its Frobenius norm by || == v E Σラ A The vec operator is the mapping defined by stacking the columns of matrix A in vector. We will denote by || p.P the entry-wise p-norm of A, i.e., | == []vec(A)]]p.
dynamic-to-static reduction
In this section, present a general reduction from dynamic regret to static regret. The key idea is to embed the comparator sequence a high dimensional space W where the number of rounds, so that competing with a fixed comparator ū E W 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 of minimizing the static regret.
Our reduction is shown in Algorithm We simply embed the linear losses 9r high-dimensional space by setting
9. = c 2 9: = (0) OJ 9: O TT)
Indices E(d(t- 1)+1.d()
where E R is the 4th standard basis vector of R and O, E I& denotes the vector of zeros. We pass these losses to the online learning algorithm A, which predicts with a vector w, E W", Finally, set w. E Rd equal to the hh "component" of w, and play wt.
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 i = (ui,..., ur) in W we will denote the concatenation of ú into a single vector in W as
ũ -T @ u, (u
uF)T
Then, the following proposition shows that the dynamic regret of Algorithm w.rl any sequence = (ui.... ur) is equal to the static regret of A w.r. û.
Propusition 1. Let W S Rd and let A be an online learning algorithm with domain WT. Then, for any sequence य (ui, ........ uT) WT, Algorithm I guarantees
T
T
(ū) = Σ
(g. w. - u1)
Σ
Tr
i
1)
Seg (
1=1
Proof. The proof is immediate from Equations (2) and (3). In fact, observe that the cumulative loss of the comparator sequence is precisely
(
Σ (g un)
:
Σ e
g
e; x ut
Σ Des
We get a similar relationship for the algorithm's cumulative loss. Hence, we have Rr ΣT (g:, w. ut) ET= (g., W. ū) RT (T).

---

It is important 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: Ei=1 (((wx) -
Remark 1.
- Ee(w,) S E (g.. we - - = Sea (ū) for 9r E (we))
While our reduction is exceptionally simple, its utility should not be understated. Proposition is regret equivalence - we lose nothing by taking this perspective, yet allows us to immediately apply all the usual techniques and approaches from the static regret setting. For instance, given any dual norm pair (II-II, [I-11.), it is well-understood how develop algorithms which adapt simultaneously to the comparator norm ||ū]]] and to the gradient variance Σt=1 | to guarantee
(u = Sea
I
| I ET 10.1.
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 ü [c.g.. 26, 27, 32, 9, 12. 20, 8, 21, 48]. In this way, have effectively reduced the problem of minimizing dynamic regret to the problem of selecting a dual-norm pair that meaningfully measures the "diffieulty" of the sequence in i and the losses 9,- In particular, (II-II II-lI.) should be chosen with the following considerations in mind:
1. |لت|ا should produce meaningful measure variability of the comparator sequence U1...., UT. For instance, will show in Proposition 2 that the squared path-length arises from a particular weighted norm applied to u.
2. [lel.. should not "blow up". Ideally | ll. should match the magnitude of the true losses 9: up to polylog factors.
3. (1--I should be chosen with computational considerations in mind. For instance, to apply an FTRL-based algorithm to the losses D. E R efficient implementation will typically require ||-II_ to have sparse subgradients. In general, an ideal dual-norm pair should facilitate updating only Ollo T) variables at a time, so to match the Odd log 7') 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 (II-Il II.II.), creating a tension between the first two considerations.
3 Lower bounds for unconstrained dynamic regret
In the static regret setting, there 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 9r- For example, in Online Mirror Descent [29, 42] one can get regret guarantee that depends on the maximum diameter of the feasible set with respect to norm || |l. while the linear losses are measured using the dual norm || ||_. The equivalence in Proposition suggests that a similar tension exists for the dynamic regret.
Given the structure of our reduction, it makes sense focus on the weighted norms Il and Il-lM-1. where M is a symmetric positive definite matrix. In particular, the next theorem shows that there is fundamental trade-off between variability penalty || M and variance penalty G (T-M)) related to the losses. The proof is provided Appendix A. and based on a lower bound to the tail of Rademacher chaos of order 2.
5

---

Theorem 1. Let the number of rounds T 2 To. where To is universal constant. Let A be an online learning algorithm, and suppose guarantees Rr (D) S Ger for any sequence of linear losses 91 .1.....9r E R satisfying l9el S Let M RXXT be any symmetric positive definite
matrix, denote M = 1MMM_ Diag (M-') and VT == Tr(M II
||.- Suppose that
|M 133 2 7 max; (, Then, for any P satisfying To S log2 .PVr S T, there is
20r
sequence of losses .I...., ,TT E IR and u (ui....,uT) E IB" satisfying | M - /P such that we have
(r( 2 GET + [IXMM (
PVT 2CT
M
log2
Let us first briefly discuss the conditions on M. First, note that the restriction that M pos- itive definite and symmetric simply specifies that Il-l|M defines valid norm. The condition || |F |M Diag (M-*) ||r is less straight forward interpret, but it essentially states that the total "variance" M is at least as much as that of any of its columns. on a technical level this assumption leads to the restriction that P satisfies log2 (v CVPVr//ee < T. This is a natural re- striction which encodes the fact that if P is too large relative to T (i.e., when log2(v/V /2er) 2 T), one can ensure "low" regret by simply playing w; 0 every round:
(T(ū)= = - (g.> u,) I max ||u, GT S G max || log2 (VPVT/2c).
and hence the only lower bounds in such settings are trivial ones and it suffices to consider only P satisfying log PPVr/22) < T. We will see in Proposition 2 that the matrix that produces the squared path-length satisfies this condition, and can be seen that symmetric matrices with equal column sums (as is the case in Proposition 3) satisfy this condition well.
The result of Theorem 1 shows that there 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 small variability penalty in all situations without also accepting large subgradient variance penalty. The next proposition shows that i) the squared path-length can be represented by particular choice of the weighted norm || M. and ii) the fundamental tension between [u]l and its corresponding variance penalty Tr (MM prevents any algorithm
from attaining the ideal variability dependence of || (v
EL |u, uu+ u.+1l1)) Ilp). In fact,
the corresponding variance penalty is G Tr(M = (GTT2), resulting in 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 finite- difference operator Σ E R.T the matrix with entries
if==j
Ei
fi==-11.
otherwise
Let S = = and M = S Is. Then, M satisfies the assumptions of Theorem I and
T 2 + | M |
Tr 1M- T(T+1)
Σ
uu u
and
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 vacuous guarantee. However, we will show in Section 4.1 that is possible adapt to measure of variability which is similar in spirit to the squared path-length, yet only incurs Tr(M-1 -1) Olog T) variance penalty.
Remark 2. The matrix M Proposition uniquely exposes the the squared path-length up to the bias term |uT|] 11 Such a bias term must appear because the static regret setting, wherein un = uT the variability measure || M must still reduce dependence on ||ul]. otherwise

---

Algorithm 2: Dynamic regret OLO through 1-dimensional reduction [9]
Input 1-d Parameter-free OLO algorithm A, positive definite symmetric matrix M E gd x
Initialize 0 11 0 E RdT =
for / 1 do
Get 3g E from A
Play we 3 and observe g:
Send (Ü,, 9.) to A as the t loss
Set 0 0++1 0: M 9:
Set Vi- V, 9: M-1
1
P1_1
Viti
Set U141
1 A 1 10-11lm-)
// (Projected) Scale-free FTRL update
V Vi+1
end
the guarantee would violate existing S2 [2[[[u]| show in Appendix A.3 that any other choice of bias would similarly lead Tr [M-1) 2 ()(T),, so Proposition 2 along with our lower bound in Theorem I are sufficient to show that adapting to squared lath- requires accepting vacuous guarantee.
VT) lower bounds for static regret. More generally,
4 Dynamic regret for unconstrained OLO via weighted norms
So far, we've seen that there exists frontier of lower bounds trading off a variability penalty, measured by | lvr and a loss variance penalty, measured by Tr(M-), and that the tension between these two quantities makes impossible 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 simple framework for achieving lower bounds along the frontier described by Theorem 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 1-dimensional reduction of Cutkosky and Orabona [9] to extend the algorithm to durl-norm pair (II-ll I1=I1 M 1). The generic procedure is summarized in Algorithm 2 for convenience.
Theorem Let E RxTT be symmetric positive definite matrix, M = 33 L and e > There is an algorithm A such that for any 91:-...97 .T E IRd satisfying [geel2 - G for all and any
sequence ū (u),.... ur) E RdT the dynamic regret is bounded
1)
| VVT +1)
U j
V/ VTT
RT(ū)= < 0 BE + | M V log
v Bog
Be
cB
where Vr = ET= 1
and B = G ||S-- 'la,,. M
For the proof, we will need the following technical lemma.
Lemma 1. Let S TTXT be symmetric positive definite matrix and let M S 3 Is. For
t= 1..,..,,7 T, T.
let 9, Rd and let g. e; @ 9r- Then, have [@g M l|g.l1 Su.
Proof: Using the mixed-product property (A & B) & D) AC Ø BD and the transpose property
(A B) = A @ T of the Kronecker product, we have that
G.. .g.) (c, g.. S I g.) (c, @ 9,, Sc, 9.) (c] @ g. (Sc, @ g.)
e, Se, 2 g. g. = Sz 1|
Proof of Theorem 2. Applying Proposition 1, we have Rr(ū)=
= Σ 9r. ū) Seg
Since M is symmetric and positive definite, (II- M |l (-1))=-) valid dual-norm pair. By Lemma 1,
7

---

have 10 11 G -
00,00 6 Hence, let A be any algorithm which
guarantees a parameter- free regret w.r.t. II-I)) on losses satisfying @ 1-lll-= S B. Note that any parameter-free algorithm can be extended handle arbitrary dual-norm pairs by leveraging the one-dimensional reduction of Cutkosky and Orabona [9, Section 3], that reduces the OLO problem to unconstrained l 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)
( 1) eB
Ü VVTA +1) log |
BE + | (T(ū)= S0
Vr log
where VT Ei= @ell M and AT log"
T
19 11 M- 162)
S Olog T).
Note in particular that by Lemma 1, have Ei= 9 B G'Tr(S-)), so this bound matches the lower bound from Section up to polylogarithmic terms." Thus, any valid choice M will be on the lower bound frontier of Section
-
| < S
4.1 Trading-off Variance and Variability
Leveraging the algorithm characterized by Theorem we now show that indeed possible to choose M such that Σi= 1l penalty which is still similar in spirit to the squared path-length.
only Oloog (T) Σt= || (1])) ), in exchange for variability
Inspired by the Haar OLR algorithm of [47], we apply Theorem 2 using
H, where H,, is
the unnormalized Haar basis matrix of order n [log, 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 | M and lø 1 1M The proof can be found in Appendix B.3.
Proposition 3. Let log2 T and H, be the unnormalized Haar basis matrix of order n. For any t E ii O.... log, J. let N, = T/T and let I(T) ....,I!!. be partition of [T] into intervals of length r. Define the average comparutor in interval I((T) to at -,EEE uc and define the squared path-length at time-scale < T to be
I'7
N-/2
P(ū,T) == Σ
(T)
2i-1
2i 2
and P(ū,T)
=111( (1)
Then, setling S = H, H and M = S 8 La we have
loga (T)
2 M
S
7
P(ū,2") < ||u1| + log (T) max P(ū. 7).
1
4
4
| 2 M-1 = 11 (1 log T)
Summarizing, by applying Algorithm with S = H, ensure regret
([11
N-/2
( < Ō
[1a113 + max Σ
u 1
Σ
11g.
2
This is the first fully decoupled guarantee for general dynamic regret which incurs no pessimistic multiplicative penalties of the form max,, ||u, ur ||. That is, the terms depending the com- parators and the terms depending on the gradients appear in separate sums. Moreover, observe that
Note that the lower bound stated for d in which case Tr(S-1) Tr

---

this measure of variability can immediately be related to the standard (firs--odderhnn--qquaee)) path-length using the local averaging lemma of Zhang et al. [47] (Lemma D.7). We have
No /2
N2
1
log2"
T
max
(7) 21
S
D2 max D
Σ
u2i-1 1 12
(r)
(7)
< 0 D2 D
12, ue+ills l12
<0(D*+DPp)
where D = max,,
21
I max,, ||4 - uull- Thus, applying Algorithm with dual-
norm pair [|l "H. 111l-1111 H m.
"
still guarantees worst-case regret
9 He <ō ( + DPr) Ei= l1 11
(T(ū)) S
Ü H. H..."
which matches the guarantees of prior works, up to polylogarithmic terms.
Importantly, with M H. H @ Ia the dual-norm pair (II- - leads to updates that can be implemented efficiently, 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 (1)
(T RTTT form orthogonal basis with the property that for any [h (1("), * 0
for only + log2 T indices i (see Proposition 5). Hence, (H" @ La)g, = (HT @ (a) & 9:) = (H ex) @ 9., is block vector with only 1 + log, I' active blocks, requiring that we update only Od log T') indices maintain each of the variables needed implement Algorithm 2. We provide the full details of this computation in Appendix B.4, which we summarize below in Proposition 4.
Proposition 4. The algorithm characterized by applying Theorem 2 with S = H HH can be implemented with O (dlog T) per-round computation.
5 Recovering Variance- Variability Coupling Guarantees
Our main focus throughout the paper has been on designing algorithms that achieve regret bounds of the form (T S O (Vf(ui..... (g .r)) 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 slightly different form, containing gradient-companan correlation penalty:
T-1
RT(ū) 50
Ue u -ll
Σ
Ige 1l
|lue ull
Variance/Variabiiiiy coupling
for 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, matches the reference point य. This can be very powerful property when one has a priori access to a benchmark model (represented by ū) which can be expected to predict well average, that we accumulate the variance penalties only when facing atypical/unexpecten 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 composite regularizer they add to the update to cancel out certain unstable terms in the analysis, and the analysis Zhang et al. [47] recovers a guarantee of a similar form using rather difficult analysis of the frequency-domate representation of ù after projecting onto the Haar basis vectors. So far there no unifying explanation of the principles leading to these sorts of guarantees.

---

Our equivalence in Proposition instead shows that guarantees of the form Equation (4) can in- stead be understood through the lens of reward-regret duality, a standard tool used to design al- gorithms the static regret setting. The reward-regret duality states that in order to guarantee regret of the form (T((w) < f(u) for all u E W, it suffices to design an algorithm that guarantees -En ( wi) 2 (- (- 9²) for any 91.....97 9r. Using Proposition 1, we immediately have the following analogous design principle for dynamic regret. Proof is deferred to Appendix C.I.
Theorem 3. Let Wealthr := - (āt, ins) denote the "wealth" of an algorithm A and let (f. be a Fenchel conjugate pair. Then A guarantees Wealthy 2 f7{ Sppl-E-11 9t) for any sequence 91:-..-9T if and only if Rr(ū)) S fr(ū) for any sequence ři (U1,-.. U,) in W.
where ū = (u) [u]_...uT]] u T is the concatenation of the sequence ū into vector.
So, suppose we would like to design an algorithm that guarantees for any sequence ū = (U),.... WT) and any 9 (g...... .r) regret of the form
(T( V (T()))V(ūi,
for some (T( and (ū) = Vr(ūū Then, since v Vab = min 27 + 31, any such algorithm
must have (ū) I [r(ū)
24 + (T) for every 7j 2 0. So, via Proposition and the the reward-regret
duality of Theorem 3, we have that the desired guarantee is equivalent to guaranteeing for all 2 0 a wealth lower bound of
Wealth, -
Σ
g. w.) 2
fr(() 2n
7 ]vr()] 2
(-g fi -2ng
2n
91:T 2n
2n
where f7. and Vi. are the Fenchel conjugates of fT and VT respectively, and (fi 0 f2) denotes the infimal convolution [34, 19] of fi and fz:
(f1 O f2)(2) = inf (z) + fz(= -
Thus, the variance/variabilityy coupling guarantees observed in Equation (4) can be interpreted as achieving wealth lower-bounds for potential functions involving infimal convolution.
The above discussion provides 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 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.
6 Conclusion
In this paper, we have shown way to reduce the problem of dynamic regret minimization to the static one. We proved a novel frontier of lower bounds showing 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 guarantee that scales with EI | u1+1l? without incurring a variance penalty of (GT)) We developed simple framework for achieving guarantees along the lower bound frontier, and used it to develop the first algorithm making non-trivial varianie/variabilityy 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 coupled variance/variabiiityy penalty, such as Equation (4). Also, our lower bound in Section 3 illustrates the variaiie-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 not readily extend to arbitrary weighted We look forward to exciting development in these future directions.
norms and
10

---

Acknowledgments
We thank Yu-Xiang Wang for the discussion on the function classes studied in non-parametric regression theory.
References
[1] Dheeraj Baby and Yu-Xiang Wang. Online forecasting of iida-varriation-bunneeddd sequences. In Advances in Neural Information Processing Systems, volume 32, 2019.
[2] Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Conference on Learning Theory, pages 359-409 PMLR, 2021.
[3] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- lions Research, 63(5): 2015. doi: 10.122870pre:2215..4000
[4] Nicolò Campolongo and Francesco Orabona. A closer look at temporal variability in dynamic online learning, 2021.
[5] Nicolò Press, 2006.
and Gabor Lugosi. Prediction, learning, and games. Cambridge University
[6] Nicolò Cesa-Bianchi and Francesco Orabona. Online learning algorithms. Annual Review of Statistics and Its Application, 8:165-190, 2021.
[7] Jui Chang and Shahin Shahrampour. On online optimization: Dynamic regret analysis of strongly convex and smooth problems. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 6966-6977 2021.
[8] Keyi Chen, Ashok Cutkosky, and Francesco Orabona. Implicit parameter-free online learning with truncated linear models. In International Conference Algorithmic Learning Theory, pages 148-175. PMLR, 2022.
[9] Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 3/ Conference On Learning Theory, volume 75 of Proceedings Machine Learning Research, pages 1493-1529. PMLR, 06-09 Jul 2018.
[10] Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O'Donnell. On the Fourier tails of bounded functions over the discrete cube. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 437 446, 2006.
[11] Bogdan J Falkowski. Generalized haar spectral representations and their applications. Nanyang Technological University. Singapore, 1998.
[12] Dylan J. Foster, Alexander Rakhlin, and Karthik Sridharan. Online learning: Sufficient statistics and the burkholder method. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages
PMLR, 06-09 Jul 2018.
[13] Gene H Golub and Charles F Van Loan. Matrix compulations. JHU press, 2013.
[14] Geoffrey J. Gordon. Regret bounds for prediction problems. In Proc. of the twelfth annual conference on Computational learning theory (COLT), pages 29-40, 1999.
[15] Andras Gyorgy and Csaba Szepesvari. Shifting regret, mirror descent, and matrices. In Maria Florina Balean and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2943-2951, New York, New York, USA, 20-22 Jun 2016. PMLR.
[16] Eric C. Hall and Rebecca M. Willett. Online optimization in dynamic environments, 2016.

---

[17] Mark Herbster and Manfred K Warmuth. Tracking the best regressor. In Proceedings of the eleventh annual conference on Computational learning theory, pages 24-31, 1998.
[18] Mark Herbster and Manfred K Warmuth. Tracking the best linear predictor. Journal of Machine Learning Research, ((21-330):1001166) 2001.
[19] Jean-Baptiste Hiriart-Umutyy and Claude Lemaréchal. Fundamentals of convex analysis. Springer Science & Business Media, 2004.
[20] Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 4160-4211. PMLR, 02-05 Jul 2022.
[21] Andrew Jacobsen and Ashok Cutkosky. Unconstrained online learning with unbounded losses. In International Conference on Machine Learning (ICML). PMIR, 2023.
[22] Ali Jadbahaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online Opti- mization Competing with Dynamic Comparators. In Guy Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 398-406, San Diego, California, USA, 09-12 May 2015, PMLR.
[23] Charles Royal Johnson. Positive definite matrices. The American Mathematical Monthly, 77(3): 259-264, 1970.
[24] Wouter M Koolen, Alan Malek, Peter L Bartlett, and Yasin Yadkki.. Minimax time series prediction. In Advances in Neural Information Processing Systems, volume 28, 2015.
[25] Haipeng Luo, Mengxiao Zhang, Peng Zhao, and Zhi-Hua Zhou Corralling larger band of bandits: A case study on switching regret for linear bandits. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3635-3684 PMLR, 02-05 25- Jul 2022.
[26] Brendan Memahan and Matthew Streeter. No-regret algorithms for unconstrained online convex optimization. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[27] H. Brendan McMahan and Francesco Orabona. Unconstrained online linear learning in Hilbert spaces: Minimax algorithms and normal approximations. Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, volume of Proceedings of Machine Learning Research, pages 1020-1039, Barcelona, Spain, 13-15 Jun 2014. PML..
[28] Zakaria Mhammedi and Wouter M. Koolen. Lipschitz and comparator-norm adaptivity online learning. In Conference on Learning Theory, pages 2858-2887 PMLR, 2020.
[29] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley, New York, NY, USA, 1983.
[30] Ryan O'Donnell and Yu Zhao. Polynomial bounds for decoupling, with applications. arXiv preprini arXiv: /5/2001603 2015.
[31] Francesco Orabona. modern introduction to online learning. arXiv preprint 191.11111,.,3213.
2019. Version 6.
[32] Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, page 577-585, Red Hook, NY, USA, 2016. Curran Associates Inc.
[33] Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:50- - 69, 2018. ISSN 0304-3975. doi: https://doi..rr//0.. 6016// 11.01. Special Issue ALT 2015,
12

---

[34] R. Tyrrell Rockafellar. Convex Analysis. Princeton University Press, 1970.
[35] Veeranjaneyulu Sadhanala, Yu-Xin Yu-Xiang Wang, and Ryan Tibshirani. Total variation classes beyond Id: Minimax rates, and the limitations of linear smoothers. In Advances in Neural Information Processing Systems, volume 29, 2016.
[36] Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2), 2011.
[37] Radomir S. Stanković and Bogdan J. Falkowski. The Haar wavelet transform: its status and achievements. Computers & Electrical Engineering, 29(1):25 -4,444, 2003. ISSN 0045-7906.
[38] Willi-Hans Steeb and Tan Kiat Shi. Matrix calculus and Kronecker product with applications and C++ programs. World Scientific, 1997.
[39] Josef Stoer, Roland Bulirsch, Bartels, Walter Gautschi, and Christoph Witzgall. Introduction to numerical analysis, volume 2. Springer, 1980.
[40] Matthew Streeter and Brendan McMahan. Less regret via online conditioning. arXiv preprint arXiv 2010.
[41] David F Walnut. An introduction to wavelet analysis. Springer Science & Business Media, 2013.
[42] Manfred Warmuth and Arun Jagota. Continuous and discrete-time nonlinear gradient de- scent: Relative loss bounds and convergence. In Electronic proceedings of the 5th International Symposium on Artificial Intelligence and Mathematics, 1997.
[43] Henry Wolkowiez and George PH Styan. Bounds for eigenvalues using traces. Linear algebra and its upplications, 29:471-506, 1980.
[44] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. Maria Florina Balcan and Kilian Q Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 449-457, New York, New York, USA, 2016. PMLR.
[45] Lijun Zhang, Tianbao Yang. Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou Improved dynamic regret for non-degenerate functions. In Guyon, U. Luxburg, S. Bengio, Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[46] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou Adaptive online learning dynamic environments. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 1330-1340, 2018
[47] Zhiyu Zhang, Ashok Cutkosky, and Yannis Paschalidis. Unconstrained dynamic regret via sparse coding. Advances in Neural Information Processing Systems, 36, 2024.
[48] Zhiyu Zhang, Heng Yang, Ashok Cutkosky, and Ioannis C Paschalidis. Improving adaptive on- line learning using refined discretization. In International Conference Algorithmic Learning Theory, pages 1238- PMLR, 2024.
[49] Peng Zhao, Yan-Feng Xie, Lijun Zhang, and Zhi-Hua Zhou. Efficient methods for non-stationary online learning. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 11573-11585. Curran Associates, Inc., 2022.
[50] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. Journal of Machine Learn- ing Research, 1--9 2024.
[51] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936, 2003.
13

---

A 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 decoupling theory and key lemma (Lemma 2). Proof of our main result is in Appendix A.1.
Consider function f [-1, 1] + R, defined as
f(x) = Σ ALsIiiy
Define A the matrix with elements A.j. this section we will use the following notations for quantities related to polynomial induced by the quadratic form + (xr, Ax) (see page 6 of O' D'nnelll and Zhao [30])
Var[s] Σ A = 11.1//.
Inf:[s] Σ (A Az.))
One of the key difficulties in deriving the lower bound is that squared weighted norms + (æ, Ax) introduce dependencies between the coordinates æ, 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 universal constant C such that the following holds. Suppose G {+1] R is a polynomial of degree most and assume Varlg) 1. Let t 2 and suppose that [nf,[g] I C-242 for all E [d]. Then
P (1g(()) t} exp (-C4641og2)
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 matrix A.
Lemma 2. Let A be online learning algorithm, and suppose A guarantees Rr(0) GeT for any sequence of linear losses g1.... gT E R satisfying Sel S Let A E RR be any symmetric positive definite matrix, and let B A Diag (A). Then, there is universal constant C > 0 such |
there is a sequence of losses ,1, E R such that that for any 1 S q E C 2222 Ej=1 Bi,"
91
2 G (TT(A) + IIA Diag (A) r]
and
RT(0)) 2 GeT [1 -1-2400 240"²²7
Proof. Let Y1...., Yr be independent Rademacher random variables and set g: = G Yr, so that [Rr(0)] E Et= 9:W, 0. Then, using the regret equivalence of Proposition and condi- tioning any event with IP {E}} 0, we have
E [0)]
Rr) P (E) + E (r) go P (E))
(O)(EP)))) Ger (1 PP-PPP (E)))
where the last line uses the fact that A guarantees (0) Ger for any 91..... gr satisfying Igel < for all t. Re-arranging, we have
E (R) Ger (1 P )
(5)
14

---

Next, let D; et Yt. for all & and consider the event
3 Σ 91
(g ........991 .T 1I
Tr(A) + + Diag (A)ll
for 0. We proceed by lower bounding the probability of this event.
Observe that
T
Σ
91 = G2 Σ
A.j
= G²
Tr(A)+ + Σ Y.Y,A,
12
Denote B = A - Diag (A) and note that f(Y,, YT) Eis Big is polynomial of degree
at most 2 and variance Var[s] = - B3 = A Diag (A) BI Moreover, since A is symmetric we have [nf = プド= Bij + B Σ B2 for any It follows that we let g J(Y) ,(Y) 3 BlI then g is polynomial of degree at most 2, Var[g] = 1, and for any
i [T] we have Inf 2Σ B for any S q S
Hence by Theorem 4, there is a universal constant C' such that it holds that
B
||
C. max: 23 B3
P PU 2 1 B (1 (g( Y 2 a) exp (-402 = 2 2- 40
Now observe that TP (8) TP (1Y) 2 | by construction, Equation (5) can be bound as
E [ 2 GeT
[1- 1 [{E}]
GET (1-240²0))
which implies the existence of sequence 91.....9T .T IR such that RT (0) 2 GET 220240
and
Σ 91
Ga
(T(()) + + G² (T<(A) + +111 -Dia (A)
A
B
for any 1 15
C
maxx Ej= B
A.1 Proof of Theorem
In this section we prove our main lower bound. Theorem 1. Let the number of rounds T 2 To, where To is universal constant. Let A be an online learning algorithm, and suppose A guarantees (T) S GeT for any sequence of linear losses .1......rr E R satisfying lgel S Let M Tx be any symmetric positive definite matrix, denote M = - Diag (M-1) and V1 == Tr(M I|
||.. Suppose that
||M 132 2 IT max; E, Then, for any P satisfying To < log2
/PVr < T, there is 2cr
sequence of losses gl...., IR, and ū (ul....,uT) E IR" satisfying ü M = /P such that we have
Ω Ger + G [MM ( M
VPVr 2θT
log
Proof. Denote A - and B
Diag (A). By Lemma there is a universal constant C
B it holds that
and sequence 91....,97 gr R such that for any S
C c max, ET B3
T
2
Σ
g
2 G [T((A) + A Diag (A)
15

---

and
RT((0) 2 Ger [ 2102
Hence, choosing comparator sequence U1,..., Wr E R to satisfy and ù = (U1,.... ur) = AE
RT, we have x = || = vP and
E 91
R1 (u1 Ui....., ur) Rr(0)-
[=1
GVP
9t
+ Rr
GV P (Tr(A) + A Diag (A)ll + RT((0)
Ger G. (T)(A) 9 A Diag (A)lla] 2e
(P(TT(A)+1B111
Now, for P satisfying To = 40 & logz
T we may choose
2cr
(P(T+(A)+ BlI
log2
25r
q
4C
Indeed, observe that this choice satisfies
S 599
| F
as required:
2 max, ΣT B
v (((T(A))||Bll
log2
2er
B
S 9=
4C2 3
4C2
2 max: Σ/ Big
where the final inequality the assumption BB 12 max, Eis Bij > 4. Hence, we have that
G
2 I 2 (VPII(()) + B S 2 P(Tt(A) + | Blp
that the overall the regret be lower-bounded
I
Br(ui...., Sr(, UT) 2 GET + G
P ([T((A) + [[]]]]]
G = Ger +
log* (VP(Tr(A) + B |B1l-//2cc
P Tr(A) + |
2
VTo
A.2 Proof of Proposition 2
Proposition 2. (Adapting to Squared Path-length Requires Superlinear Regret) Define the finite- difference operator Σ E g the matrix with entries
if f-i=j-1.
Di
0
otherwise
Let S EE and M - I Then, M satisfies the assumptions of Theorem and
T
T(T + +1)
| M
||
u 1
and
Tr (T(M-)
2
16

---

Proof. We first show the properties that |
|
Σ l|ee u441 l2 and
Tr(E-1E-1)= Σz= ΣーΣΣー Σ
T
-1+1= T(++1) and show that M satisfies the
conditions of Theorem at the end. Observe that
La
d
0
0
U1
U2
0
I
Ia
0
03
Σ
Luju
0
0
1a
-Id
ur
uT
UT
0
0
0
Ia
UT
and since Σ
@ [a)
Ia)
Σ)
& la = M, we have
| M
ū.
Σ
T
& Ia) E & Ia) (( & I.)ū, (Σ @ I.)i)
|| 1
uu u.+1 11
Using the inverse property of the Kronecker product, also have
M = Σ Σ 23 la
ΣΣ @ = E-=E- 8 la.
and by Lemma we have that is the upper-trianguun matrix all I's, that is, the matrix with entries
{
if otherwise
0
and likewise, Σ-
T is lower-triangular matrix of 1's. In other words, for any / we have
P
Σ
2
Σ
-T--1-
2
ist
So, summing over t we have
T T --++1=
T(T+1)
ThE Σ
2
Now we show that M satisfies the conditions of Theorem 1. S - @ Ia is clearly symmetric since it is the Kronecker product of two symmetric matrices. Observe that for any æ o 0 E Rd we have Σx + 0 by positive definiteness of Σ (Lemma 8) and thus (æ, Se) Ea Ex) > O. Thus, M S I is the Kronecker product of symmetric positive definite matrices. so M is symmetric positive definite [see, e.g., 38, Chapter 2).
Lastly, let B -I Diag (Σ 1--Eー-]
-T). We are to show that B F
I E,
B3 for any i.
First observe that calculation of ΣΣ - - Jee is generalized to
Σ
I max (i, +1,
ij
k=1
for any i, j. and likewise Bij max (j. i) + for * j and 0 otherwise, from which is easily
seen that max, E, B3, Σ, B so for any we have
T
BB
B < Σ
Bi
Σ
-
T(222 -3 1).
j=2
17

---

On the other hand,
B = ΣΣ B - (T2 -)
6
TT (2T -2) = TT
TT
(27 37 37 - -2 2)
(2T
- -7 +
2 6
2 6
2 6
Σ B.y
2 2
j
for any where the last line applies the inequality in the previous display.
A.3 Sufficiency of Proposition 2
The choice M in Proposition 2 uniquely exposes the squared path-length up to the constant offset term ||uT| In this section we demonstrate that the choice of offset term in Proposition does make any significant difference for the claim that adapting to the squared path-length requires incurring Tr(M 2 S2(7²) 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 E TRT be arbitrary non-zero vector and let B E RTXT be a symmetric matrix with eigenvalues (B) (B) S... S (B). Then
Tr((B + wo 2) |0 + Σ
1
t=2 AB
Lemma Let E E RXX denote the finte-difference matrix defined in Proposition 2 and let Σ E. Σ. Then, for any T 1, we have
Amax (M
Tr(M
where Amax (M is the maximal eigervalue of M-
Now, Consider the I-dimensional setting and note that for any positive definite M we can find unique E such that M E.E, Hence,
j (ū, M (Eū, Eū).
so without loss of generality focus on Σ for which
Eü, Σu) = (v, ū) + Σ 1u - up
where * 0 E T Note such constant offset term is unavoidable: it is what captures the static ur u. Proposition considers v = (O...., 1)
regret guarantee in the case where i1
to get 7 13 ||u|| + Ele l 4 though below we will show that any vector would still lead to Tr(M (TT)).
is clear that the only way construct expressions of the form above is via matrices satisfying
U1 U2
Ug
Eú = c
UT-1 WT
(0, U
"Note that any such M is unique. Indeed, if there positive definite matrices Mi Txx and M2 E Rxx such || = (v, ū)2 + pl 113 = || M, and hence Mi M2 since Mi and M2 positive definite.
R", then (ū, (M, M2)ū) =
18

---

where e (-1,1) and the order of the rows indices of the vector 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
0
0
1
-1
0
0
0
0
==
0
0
1
U1
1/2
03
04
UT
VT
A + vo Moreover, A A is symmetric matrix with a unique zero so M - = A
eigenvalue (corresponding to vectors in the span of 1 = (1...., 1) E RR",, so applying Lemma 3,
Tr(M = Tr( AAAAAAATo u0 )) 2 ||/|
(
A)
t=
Now, define V0 = (O.....0., 0) RRT and observe that Mo = A A vovo is precisely the matrix studied in Proposition 2. We have via the interlacing property of rank-1 updates to symmetric
matrices that \ A) S oM [13, Theorem 8.1.8), overall we have
T
I
Tr(M 2 Σ 2 {e(M))
Σ ((
1=2
=Tr(Mo))
A
2 TT(Mo Tr(M5')
10
TM = T(T + +)
= 10
10
2
where the last inequality applies Lemma 4 to bound Amax Amax(M (Mot) and recalls Tr(Ma*) T(T+1) from Proposition
Hence, the variance penalty will still be ?(T²) regardless of the choice of bias (v, u) 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 2 2(T²), leading to vacuous regret upper bound.
A.3.1 Proof of Lemma 3
Lemma 3. Let v R be an arbitrary non-zero vector and let B BTxT be a symmetric matrix with eigenvalues A < x²(B) ... & Xr (B). Then
Tr((B + aa ao T)- 2 |0|
t=2 AB
Proof. Let A = B + T. Since B is symmetric, we have via the interlacing property that there is an dj...., ar 2 0 such that E az ||aa| and (A(A) XB + [see, egg. Theorem 8.1.8 in 13]. Hence,
T Tr((B + vo = = Σ
T
1(A1
((AA)
[=1
T
1
min
+ 0z
a1....y 20
X B) + a;
1=1
Σ >g a=||o|
t=1
19

---

To analyze the constrained optimization in the last line, let 01,...,07 Lagrangian
0, B E Ik, and define the
T
T
T +
Σ - 11ol²)
L(a1..... ar, 01, (I,...,,T,.31)
=
A
+ at
1=1
1=1
1=1
For any t, we have
ÔL oa.
-1
1
(B)
+ a1
0t =
at VB at
AB
Plugging this into the dual 1..,,..,.0
ar,
mina
L(a1, aT. 01,01,... 01,,..,,........................ or,, 3) we have
T
D(a aT, = Σ
04 Σ
at
-x
+3
Σ v3 ar
Ax(B) - -1/01/
VB -
T
T
T
VB
B 04 +
Σ
(3
at)
+
aa (B) - B ||01|
V3 a1
t=1
t=1
t=1
T
2
3 04
+
(ol B) (B) -3110112
t=1
1=1
The derivatives of the dual w.rl Oi are
-1 (B)
Da:
v 10-00 04
Observe that for (B) 0, we have 8D
S 0, so D is decreasing 01 so the vラ-ai
dar
dual maximized when 01 O. Using the relation a1 v3-ai (B) above we have
a1 - AB vB Equating the other derivatives for t
have (B)
= \B(B) =
a2
0: =
Vt
where we used the relationship a,
1 ツラーai
A (B) from above. Finally, the optimal B is such that
EL at
1
||a|2
so overall we have
/3
1 T
Σ
min eu
AB)+ar
V3
01
Ar (B)
+
V3
Σ
1=1
t=2
||
X (B)
2=2
A.3.2 Proof of Lemma 4
Lemma 4. Let Σ E RTX denote the finitedifference matrix defined in Proposition 2 and let
M = Σ E Σ. Then, for any T > 1, we have
9
Amnuxe (M
Tr(M ))
10
where Amaxe
(M-1) \max((
is the maximal eigenvalue of M
Proof. The matrix -1 - is symmetric and positive definite, hence has real eigenvalues. The eigenvalues 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):
Tr (M-)
Tr M
M 1
Tr M (M)) 1)
27
Amax (M-))
+
(T (--1) 1)
T
T
T
20

---

Next, observe that by Lemma matrix E-1 is upper-triangular matrix of all 1's, that
[M 10 = ΣーΣー
Kj
Σ RE(T]
Liz 5k
kE
Σ
[ (k)
2 T max {i,}} + 1,
kE(T]
Hence,
T(T
Tr (M(M)) Σ
M -
Σ
2
1=1
t=1
t=1
Moreover,
T
Tr TT(M-1 (1TM-)) TTMM-MM-)
Σ
M ME--TM-
M- 1
M
M M
T
T
(M )2
Σ
(T max {t,k) 1)²
t= k=1
k=
T(T + 1)2 +2)
12
Thus,
Tr M (M-M
Tr M 1)
27
(T + 1)²(T +
(T (T+1))
T
T
12
4
(T + 1)²
T 2
4
3
(T + 2
-1
4
3
Overall, Amax (M-) is bounded by
Tr ( [M 1)
(T + 1)2
Amax (M 1)
V (T-
T
4
T+1
(T (T+1)((T 1] 1)
2v3
T(T +1)
T 1
1
2/3
v3
T(T +1)
T(T + 1) 1
T(T + 1)
9
Tr(M
2/3
2
4
2
10
where the last line observes that 1
1
<
1
<
T
4
for T 2 2 and the fact that J
= 0.83 <
TO
B Proofs for Section 4 (Dynamic regret for unconstrained OLO via weighted norms)
B.1 Details on the I-Dimensional Reduction
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 (II-Il |I M-1) well as its regret guarantee.
21

---

For concreteness, choose adaptive FTRL with AdaGrad-norm stepsizes [40] 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 @ lg
Using Cutkosky and Orabona [9, Theorem 2], we have that the regret of Algorithm 2 equal to
Rr (ū)
( x| MM) + || M Fy
Edfirsction
Vū E R
||
where R& is the regret of A over a sequence of G-Lipschitz linear losses and Rdirection is the regret of (scale-free) adaptive FTRL with feasible set equal to the unitary ball defined by || Ml
Choosing the algorithm A to be [20, Algorithm 1J. we have
| M ( ))
| M VVTA
G5c T R (ll)) SO
Vr log
+1 V 6 log
Be
cB
where Vr = Ei=1 Tell 1al--- and AT = log (E
18 /62) S Olog" T)..
Lt=1
Focusing now on the regret of the direction learner, define the distance generating function (()) $|00"1
M. Using [31, Theorem 4.3], we have that & is I-strongly convex w.r.l M. Hence, using the regret guarantee of Scale-free FTRL, i.e. Theorem of Orabona and Pál [33], for any p such that |0l| A I 1 the regret of the direction learner is
T Σ
(
T Σ
DDirection RT
1)
S
2
M + 2.75
1...l + 3.5 max
1 So
EST
Applying this with ē
and combining with the previous two displays leads to the bound
stated in the proof of Theorem 2.
B.2 The Haar Matrices and their Properties
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,, Throughout this section we assume for simplicity that T is a power of 2.
(Tg) and E [T/r], the Haar basis vector at timescale T and location is the vector in IR with entries
Definition 1. For any T E (2'
1
ifl 1)
if 1,
0
otherwise
The Haar basis vectors are often arranged into the columns a matrix as follows:
H,, = (T)
(no h
h
(T/2)
h2
(T/2)
h
(T/4)
h2
(T/4)
hg
(T/4)
h4 (T/44
h
where hg = (1, T)T E RT. This matrix referred to as the (unnormalized) Haar basis matrix of order log, (T). is well- that Hn has the following equivalent recursive form [38, 11,
Ho =1),
H Hn-1 (i) 12--1 2 (-1))
(7)
So, for instance, we have
i
(-1) = (1) ())
(1)) =
( 1))
H = Ho z
20
x
(1)
1
1
0
0
H2 = (i
1
1
1
1 0
(1))
-1
0
1
1
0
1
1111
-1
22

---

and For purposes, will primaly work in terms of the matrices H rather than the basis vectors h The main utility of defining the basis vectors (T( that their definition easily implies the following useful result, which states that the Haar basis vectors sparsely supported w.r. time. Proposition 5. Let log2 T and let H TxT be the unnormalized Haar basis matrix of order n. Then for any t [T]. there at most + log T indices for which n,,, # 0.
The proof follows immediately from Definition (i.e., any can fall into only of the intervals covered each the (T') time-scales) and accounting for the additional column ho all I'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. Lei A, B, and C be matrices of appropriate dimensions such that the product ABC exists. Then, vec ABCC = (CT & A)vec(B. B).
The following three lemmas will be used to prove the guarantees of the algorithm characterized in Section 4.1 (Propositions and 4).
Lemma 5. Let n (T), = U1) E RT, and let H, be the unnormalized Haar basis matrix of order n.. Then
H H 1 12a-1V 12
H
where
U1 + U2
U1
U2
+
U3 04
=
UT-1 1 VT
WT UT
Proof. From Equation (7), we have that
& ())
(1))²
1
H 2 (1 1)
H. u
H
Ign-1
120-1 2 (1 -1)
H (1
1)
[12 & (1
-1)
Moreover, leveraging Proposition 6 we have
vec
(1
1)
U1
U3
VT
1/2
U4
VT
H e
(1
-1)
U1
U3
VT-1
Hn-1
VT
vec
(v) +
03
+
U4
VT + UT) H
vec
(U)
U2
13
0T-1
VT
1
H H
Iza 10n-100
Lemma 6. Let H,, be the unnormalized Haar basis matrix of order n. Then, H H. satisfies
(1 Ign-1 @ (1 -1) 1
H. H
H -
(8)
H H + 12m-1
H H O2n-1
1gn-1.)
(9)
Opn
where 125-1 and 02 are 2n-1 x 2 matrices of I and 0's respectively.
23

---

Proof. For brevity, let denote B,, H,H,, The first equality follows from elementary properties of block matrices and the Kronecker product: using the recursive form of Ha, we have
Bn = H n
())
I 2 @ (-1)
8 (1
1)
Hn-
2
I 2 (1 -1)
1
(-) 1 @ -1)
Hn-1 x
11 @ (1 1) 12-11 8
1
1
-1) (-)) (1 -1)
-Hp- R
x
i
(1 1) + I 2-- 8
(1 1 + I 2n 2
1 -1)
=Hn-HH n-1 2
(-1 1)
(1 1
(-1
-1)
= Bn &
+ 12- 1 @
1
To get the second expression, let proceed by induction. We have Bg (1) and
Bi = H = t : ( 1) T Next, let us assume that Bn satisfies
2 0 =
B 11
01 Bo
=
01
10+111
B, BBn-1 + 12
02n-1
Opn-1
Bn-1 1gn-1)
Then, applying the recursive form Equation (8) for B we have
But1 = Bn & 111 + 1nn & (1) 1
Bn-1 + 12n-1
B Bn-1 + I 1gn-1/ )
Ogn-1
11) + 2 8
(-1 i))
02n-1
2
1
1
(1
111)
1
Bn-1 8
I
1
+
12 8
0pn
B Bn-1 8 i) + 1 20 1 8 (i !) 1)
O2n
-1 -)
I 2 8
0n
(11-)))
O2"
I 8
B + 12" O2"
O2n Bn + 12",)
(1 1 1
(1
where the last line observes that 11
12" and that after adding the two block matrices,
the top left and bottom right blocks are both
B B & (1
1 1) +I &
(1 ) 12- B,, + 12",
via Equation (8). Hence, the stated result follows by induction.
Now using this, we have the following bound the norm of the high-dimenssonal surrogate losses.
Lemma 7. Let n = log2(T) er be the g standard basis vector of TR."" and for 9t E Rdd ler g. = e, 8 9, E Rd Let Hn be a Haar matrix of order n and let B = Hn @ la be it's block extension sequence in Rdd. Then, we have
g BB
(log T 1) l1g.112
24

---

Proof.
Using Lemma have that
g. BBT
H H et
11g.1l
Moreover, using Equation (9) can easily seen that the diagonal entries of H,,,, are logg 7 ++1, 1, so we have
1 BB
$ (1 + logz T) |
B.3 Proof of Proposition 3
Proposition 3. Let n log, T and Hn, be the unnormalized Haar basis matrix of order n. For
any E {2' : 0, logg T. let N, = TT/T and let I ....,IN. be partition of [T] into
intervals of length Define the average comparator in interval I.TT) to be (() - EEETs and define the squared path-length at time-scale T to be
P(ū,T):=
U U2
(T)
(T)
and P(ū,T) = [ (T) = =1
Then, setting S [ and M = S & La we have
log, (T)
1
| M I |
P(ū,2') S | +
log (T) max P(ū,, r),
4
1=0
9 Pell-m |1 + log T)
Proof. The proof of the claim @ 2 M-1 Lemma 7.
9 1
19.12 [log(() + 1] is provided in
To see the form i 2 let us first write
ü M ü. HH H u, H 18)
H 2
The result then follows by showing that
2u
(1 12) u (T/2)
ū (T/4) i (T44)
(T/4) Ui TT/4)
Ug
H 01
(10)
41 U2
11 44
ur Wr
so that
H
(T/2)
02
(T/2)
+ 21
(T/4)
002
(T/4)
+
(T/1)
(T/4)
4
2
4
P(T)
P(T/2)
P(T/4)
1
+
u2
122 +
|lu3
u4ll
+....
|
uT
-P(1)
where for brevity have dropped the argument ū on P(ū,
25

---

Equation (10) is best shown via example; the general is mostly tedius exercise which
provide at the end. Assume = 4, then the Haar matrix of order ni logg (T) = is
1
1
1
0
v
0
2
0
0
H2
1
1
-1
0
2
2
v2
0
2
0
0
1
-1
0
1
0
0
0
2
V2
-1 -1)
0
0
0
v
v2
=:D;
It is well-known that for any T the columns of H Hoogy(T)
(T) form orthogonal basis of TR? [41, Chapter
6. 1.11, which implies that H2 is orthonormal. So, H2
H and
H₂¹ (H₂
D2
H
0
1
2
2
Hall-ai
0
7
7
1
2
0
0
V2
V2
V2
0
0
which leads Equation (10) after applying the Kronecker product:
Ta
Ia
Ia
Ia
wi - t
2ū
Fa
T4
T
(T/2)
ú (T/2)
4
u
I
0
0
Mi u2
2
2
U1
Iú
La
WT
uu 2
U3 UA
More generally, start with = 1 begin again by factoring
H D H 2
where now H, is the normalized Haar basis matrix of order n logg and
D2 = Diag
VT. VT. VT/ T/4 V2...., v2
2
2n-1
The result then attained by unrolling the recursion for H given by Lemma 5 and factoring in the normalization factors D
2 The result for > is then immediately implied by observing that the block matrix H. Id will act upon the vector components of RdT in identical way to how H. acts upon vector of scalars.
B.4 Proof of Proposition
H can be Proposition The algorithm characterized by upplying Theorem with = (H, H implemented with O (d T) per-round computation.
Proof. Note that the losses passed the I-dimensional parameter-fie free algorithm are (wr, (.) (Ü., @ gt), and since @ g, has only d active indices we compute the I-dimensional learner's losses in (d). As such, the I-dimensional learner can be implemented in O(d) per-round computa- tion.
For the direction learner, we are show that each of the relevant variables can be maintained using only O dd T') per-round computation.
Using Proposition 3, we immediately have V4+1 V; + | 2y- V++1 can be maintained using only ((d) per-round computation (i.e., to compute [9,
V + (log T + 11) 1l so
For the scaling factor
P++1
observe that
M-11
0 0
+ 0 M
+2 M
M-
26

---

Hence, again have (dd) per-round computation compute we can decompose the last term as
grll M- and letting h, H et
(0r: H H 8 Ia) (e, o @g)))
0.
H H n
e & 9. H 8g.
(e) @ 9. (H @ a
e, Hnh, @ 9.
(he (g.
h; (g gr) h
hig gr: he
g:>
g, h
h4
From Proposition 5, for any the vector h, H c has only log T 1 active non-zero elements by construction of the Haar basis, so given A,, the product A,h; takes a linear combination of log T 1 vectors in Rd, for Od T) operations. Note that the variable A, also be maintained with (og operations since each term is g. which involves updating (log T) columns of using (dd log T) per-round computation.
At-1 RdxT_ Hence overall
maintain 0 0++1 M-1
Lastly, consider the variable 0.t1-
Observe that we can maintain a variable 0.+1 =
H & Ia E a=1 9, using Old T) computation:
1
0.1 = H & 1a
(HH (he.89) - 0, - -(hs @ gt),
9. =
since h, @ 9, is block vector containing log (T) + non-zeros blocks of length d. Hence,
0.1 = (H, 3 In)
g. In)
(H, 8 (H, 60 I, 9.
(H,, n & I, 0, 41.
and again via the construction of the Haar basis. each row of H, (i.e., each column of H has only log T + 1 non-zero entries, we can compute each x block 0.41 using Od T) computation. Finally, observe that in order implement the direction learner, we need only compute the tth x 1 block of 0,. Indeed, since for each f, the vector 9. e, @ 9e has only d non-zero indices, it suffices to retrieve the corresponding indices of ü; to implement direction learner.
We note that the memory overhead of maintaining each these variables can also likely be reduced by more careful bookkeeping, and acknowledging the fact that the algorithm only really needs to retrieve the th block of w,, since the losses are 9, e, 30 9r- We omit these considerations here for brevity.
27

---

C Proofs for Section 5 (Recovering Variance-Variabiliyy Variability Coupling Guarantees)
C.1 Proof of Theorem 3
Theorem 3. Let Wealthr := - (gt, wi) denote the "wealth" of an algorithm A and let
(", be Fenchel conjugate pair. Then A guarantees Wealth7 2 s - t- 91) for any sequence 91.....91 if and onty if Rr(ū) S fr(ū) for any sequence ú = ( ur in W, where u = "..,
is the concatenation of the sequence into a vector.
Proof. Thanks to Proposition 1, the proof is essentially the same the usual one. We provide the argument here for completeness.
-- g.. Wي U) for 9. - ct &g, and ū Σ e & ty Hence, recalling the definition of the Fenchel conjugate, have
From Proposition 1, ( = R Σ
T
R
Σ
9t wT
ui) =
g W - ŭ Wealthy
gg. U)
t=1
tm
9::
f
Σ t=1
9t I sup (0, ; f7(0) fū)
Similarly, for the other direction, suppose we have Rr ù ( Jr ù for any ü. Then re-arranging, have Wealthy 2 - g.. ú fr(ū), and since this holds for any ū, we
can choose the one that tightens the bound to get Wealthr 2 supa (- Σ Te ū fT
ff( Et.9..
D Supporting Lemmas
Lemma 8. Let Σ E Rx be the finite-difeerece operator, having entries
i
Σig
fj=i+1.
otherwise
Then,
I. The inverse of E the upper-triangular matrix of 's:
Enj {1 ifj 2 i
Vi.j.
otherwise"
2. The eigenvalues of E and 1 are > = for all i E [T].
3. x + T Ex is positive definite.
Moreover, the analogous properties hold for the block matrix E Ia ddxx
Proof. The inverse of Σ is the upper- upper-triangee trianullar matrix A characterized by entries
j
Ai 0 otherwise
To see why, observe that we have Ey:r Ar. and for < T we have
(1 ii=
ΣA is Σ
En A.j AHI.
(
otherwise
4,
28

---

and likewise for [ ij. Hence ΣA AΣ and M A.
Next, since Σ and Σ are upper-triangular, their eigenvalues are equal to their diagonal entries, and hence both have eigenvalues X; = 1 for all i.
To see that the asymmetric matrix Σ is positive definite, it suffices to show that the symmetric part of Σ, ie., the matrix Es = [Σ Σ /2, is positive definite [23]. Luckily, Eş is also well-known variation of the discrete difference operator and is known to positive definite [see, e.g., Theorem 7.4.7 in 39].
For the block matrix B Σ @ La the inverse is given immediately by the inverse property of the - Ia- We also have that B Σ I and B have eigenvalues X = for all i E d since both are again upper- triengrra with I's on their main diagonal. Finally, we have positive definiteness of B using the fact that the symmetric part of @ Ia is 3 (B + B
Kronecker product: B {Σ Id)
(Σ & Ia + Σ @ Ia) [ Σ & Ia by the distributive property, hence B is the Kronecker product of two symmetric positive definite matrices, so B is positive definite [38, Chapter 2).
We borrow the following eigenvalue bound from [43]. Theorem 5. (Wolkowicz and Styan [43, Theorem 2.1]) Let A be a symmetric n X n matrix with eigenvalues (A) S ... S An (A). Then
Amax (A) Tr(A) + (n-1) 1)
Tr(A A)
(T((A) 27
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract and introduction clear state the main claims of our paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We clearly state the problem setting and the assumptions therein. We clearly state which results are optimal up to logarithmic factors. We discuss the computational complexity of our newly proposed algorithm at the end of Section 4.1. Attaining the tightest matching logarithmic dependencies in our lower bound is still an open problem, as mentioned the conclusion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
30

---

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the theorems provide the full set of assumptions. All of our main results are proven explicitly either the main text or in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
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 includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
31

---

5. Open access to data and code
Question: Does the paper provide open to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
This is a theoretical paper that studies theoretical guarantees for online learning algorithms.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ httpl//guiideS/oeeeueeeee
wereinisssnoooliiii onPolicyl for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. cc/public/guiiaiccccccccccocccce wwwpc//gggee//egeeeeeeeee httpg/dddd//ooeeuuiiiieeeeeeeeee ietteesbbmsssoooool...
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
This is a theoretical paper that studies theoretical guarantees for online learning algorithms.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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 emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

The factors of variability that the error bars 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).
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 should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful 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 the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
This is a theoretical paper that studies theoretical guarantees for online learning algorithms.
Justification:
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 'tttt make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///nerriispree http:pp:///eerrpp..cppppb/blbbpa http::/p..cpppppceccccceccceadda
Answer: [Yes]
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 reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is 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.
33

---

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

---

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, phcore thcode. com datasets
has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
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 part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
35

---

Depending 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
36


Reviews:
[{"review_id": "8HyxXFWzpv", "reviewer": "Reviewer_YDMs", "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.", "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": "The authors have adequately addressed the limitations and, if applicable, potential negative societal impact of their work.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The dynamic-to-static regret is pretty impressive. Although it is a little conceptual and less practical, it provides us with a novel way for dynamic regret minimization. \n\nThe lower bound in Theorem 1 is also meaningful by depicting the influences of the variability penalty $\\\\|\\tilde{u}\\\\|_M$ and the variance penalty $G^2 \\text{Tr} (M^{-1})$, providing guidance for consequent algorithm design.", "weaknesses": "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.\n\n1. 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.\n2. 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. \n3. 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?\n4. 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.\n\nOverall, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The authors stated that $P_T$ based dynamic regret is not favorable enough with\n> an overly pessimistic diameter quantity. \n>\n> The relationship between the current averaged squared length and the\n> desired squared length is not discussed\n\nGiven that the smoothed version of squared path-length is a new notion\nof variability, it is natural to show that it is always at least as good\nas the standard notion of variability. However, it should be clear this\nis only a sanity check and this notion can often be much better since it\ndoes not incur the pessimistic diameter penalty. \nPlease see [our global response](https://openreview.net/forum?id=hD8Et4uZ1o&noteId=2OutnXLWT0) for a detailed\ndiscussion.\n\n> The obtained regret also suffers from additional terms, which is not\n> favorable enough in the full information setup. Do previous works?\n\nAll prior works which achieve dynamic regret guarantees in unbounded\ndomains do indeed incur additional logarithmic penalties, even in the\nfull information setting. See Jacobsen & Cutkosky (2022,2023) and Zhang et al. (2023). \nSimilar to the static regret\nsetting, such logarithmic penalties appear to be the price paid for\nachieving adaptivity to an arbitrary comparator sequence. Such penalties\nare known to be **necessary** in online learning with unbounded domains,\nsee the lower bound in Orabona (2013), and recently proved in the\nstochastic setting as well by Carmon & Hinder (2024). \nWorks which assume a bounded domain, such as Zhang et al (2018) can\navoid this additional term because they are leveraging prior knowledge\nabout the comparator sequence, ie, that $\\\\|u_{t}-w_{1}\\\\|\\le D$ for all\nt. In this work, we focus on achieving novel guarantees in the\nunbounded setting, though our reduction in Proposition 1 is applicable\nin the bounded setting as well.\n\n> the computational complexity of the reduction is not discussed\n\nThe computational complexity is related to the choice of $M$, and is one\nof the main considerations that one must consider when choosing $M$.\nThis is discussed on page 4, lines 136-138. In fact, one of the key\nproperties of the $M$ we choose in Proposition 3 is that it supports\nsparse updates, requiring $O(d\\log T)$ per-round computation to update\nthe algorithm, matching the computational complexity enjoyed by\nprior works in this setting. This is discussed on page 8, starting on\nline 243.\n\n> proposition 2 only shows that choosing a specific M does not suffice\n\nThis is a very good point, thanks for raising it. The choice of $M$\nuniquely exposes the squared path length up to a constant offset term,\nbut it is easy to see that the offset term does not make any difference\nfor our claim. To see why, consider the 1-dimensional setting and note\nthat for any positive definite $M$ there is a unique $\\Sigma$ such that\n$M=\\Sigma^{\\top}\\Sigma$. Hence, without loss of generality we can focus\non $\\Sigma$ satisfying \n$$\n  \\\\|\\tilde u\\\\|\\_{M}^{2}=\\langle\\tilde u,M\\tilde u\\rangle=\\langle \\Sigma\\tilde u, \\Sigma\\tilde u\\rangle = \\langle v,\\tilde u\\rangle^{2} + \\sum_{t=2}^{T}\\\\|u_{t}-u_{t-1}\\\\|^{2},\n$$\nfor some $v\\in\\mathbb{R}^{T}$ and such that $M=\\Sigma^{\\top}\\Sigma$ is\npositive definite. Note that the constant offset term is unavoidable: it\nis what captures the static regret guarantee in the case where\n$u_{1}=\\ldots=u_{T}=u$. Proposition 2 considers $v=(0,\\ldots,0,1)$ \nto\nget\n$\\\\|\\tilde u\\\\|^{2}\\_{M}=\\\\|u_{T}\\\\|^{2}+\\sum\\_{t=2}^{T}\\\\|u\\_{t}-u\\_{t-1}\\\\|^{2}$,\nthough below we will show that any vector $v$ would still lead to\n$Tr(M^{-1})=\\Omega(T^{2})$.\n\nIt is clear that the only way to construct expressions of the form above\nis via matrices $\\Sigma$ satisfying\n$$\\Sigma\\tilde u=c\\begin{pmatrix}u\\_{1}-u\\_{2}\\\\\\\\ u\\_{2}-u\\_{3}\\\\\\\\\\vdots\\\\\\\\u\\_{T-1}-u\\_{T}\\\\\\\\ \\langle v,\\tilde u\\rangle\\end{pmatrix},$$\nwhere $c\\in\\{-1,1\\}$ and the order of the rows indices of the vector can\nbe permuted without loss of generality. In particular, the only matrices\nthat can produce these expressions (again noting that the rows can be\npermuted without loss of generality) are of the form \n$$\n\\Sigma = c\\begin{pmatrix}1&-1&0&0&\\dots&0&0\\\\\\\\\n            0&1&-1&0&\\dots&0&0\\\\\\\\\n            0&0&1&-1&\\dots&0&0\\\\\\\\\n            \\vdots& & &\\ddots&&&\\\\\\\\\n            0&0&0&0&\\dots&1&-1\\\\\\\\\n            \\hline\\\\\\\\\n            v\\_{1}&v\\_{2}&v\\_{3}&v\\_{4}&\\ldots&v\\_{T-1}&v\\_{T}\n          \\end{pmatrix}\n  =:\n  c\\begin{pmatrix}\n    \\Delta\\\\\\\\\n    \\hline\\\\\\\\\n    v^{\\top}\n  \\end{pmatrix},\n$$\nso $M=\\Delta^\\top\\Delta + v v^\\top$.\nAdding a rank-1 update to $\\Delta^{\\top}\\Delta$ will increase its\neigenvalues $\\lambda_{i}=\\lambda_i(\\Delta^{\\top}\\Delta)$ by some\n$a_{i}\\ge 0$, such that $\\sum_{i}a_{i}=\\\\|v\\\\|^2$. Moreover, there is a\nunique zero eigenvalue of $\\Delta^{\\top}\\Delta$, corresponding to the\neigenvector $(1,\\ldots,1)/T$. Therefore,\n$Tr(M^{-1})=1/a_{1}+\\sum_{i>1}\\frac{1}{\\lambda_{i}+a_{i}}$. This implies\nthat the worst-case choice of $a_{1},\\dots,a_{T}$ is given by a convex\nconstrained optimization problem which yields $a_{i}=0$ for $i>1$ and\n$a_{1}=\\\\|v\\\\|^2$ via the KKT conditions. Hence, the worst-case choice of\n$v$ is the one which increases only the eigenvalue corresponding to the\nuniform eigenvector, so the worst case choice of $v$ is proportional to\nthe uniform eigenvector and\n$Tr(M^{-1})\\ge \\Omega(\\frac{1}{\\\\|v\\\\|^2}+\\sum_{i>1}\\frac{1}{\\lambda_{i}})\\ge \\Omega(\\sum_{i>1}\\frac{1}{\\lambda_{i}(M_{0})})$,\nwhere $M_{0}$ is the matrix from Proposition 2, obtained by setting\n$v=(0,\\dots,0,1)$. Notably, from the proof of Proposition 2 it can be\nseen that even if we dropped the largest eigenvalue of $M_{0}^{-1}$, we\nwould still have $Tr(M^{-1}_0)\\ge \\Omega(T^{2})$. Hence, any of the\nmatrices which produce the squared path-length dependence must incur the\nsame $\\Omega(T^{2})$ variance penalty up to constant factors. We will\nexpand this reasoning into a more formal proof in the paper and we can\nprovide additional details if needed, but the above claims can be easily\nverified numerically.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6W5hiKvCIy", "reviewer": "Reviewer_28Fn", "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. \n\nThey 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.\n\nThey 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).", "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?\n- 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": "The authors have addressed limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "While simple, their reduction is quite elegant and insightful. This conceptual contribution is also nicely complemented by the authors employing it to achieve a new lower-bound (that can be matched via existing methods). The presentation is clear and intuitive.", "weaknesses": "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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Do you believe there are any implications of your reduction that are\n> particularly useful from a practical/deployment perspective, or do you\n> see the contribution as being a strictly conceptual one?\n\nWe believe that the most important implication is that the reduction\nallows us to use any present and, more importantly, future result from\nstatic online learning, to solve dynamic regret problems. For example,\nthe algorithm that we show in Section 4.1 has the same computational\ncomplexity as previous ones (such as Zhang et al. (2018), Jacobsen &\nCutkosky (2022), and Zhang et al. (2023), to name a few) so it has the\nsame applicability as these works.\n\nPractically speaking, in many real-world problems the \"solution\" to the\nproblem (represented, e.g., by the ideal model parameters) can change\nover time, due to unpredictable changes in environment or underlying\ndata-generating process. These changes to the solution are captured by\nthe time-varying comparator in dynamic regret. A major benefit of these\ncomparator-adaptive dynamic regret guarantees is that the algorithm\n*automatically adapts* to this changing comparator sequence, without\nrequiring *any* prior knowledge whatsoever about this sequence or how it\nis changing. We believe this is an exceptionally powerful property which\nis indeed useful from a practical/deployment perspective.\n\n> Do you have any additional intuition for the locally-smoothed\n> path-length quantity? For example, how smoothed would one generally\n> expect this quantity to be?\n\nDue to space constraints, please see our [global response here](https://openreview.net/forum?id=hD8Et4uZ1o&noteId=2OutnXLWT0) for a\ndetailed discussion of these concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DiYo1PBugZ", "reviewer": "Reviewer_Rnvn", "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.", "questions": "Please refer to the weakness part.", "limitations": "This paper is theoretical in nature, and I do not identify any potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- This paper provides a simple yet effective reduction from the dynamic regret minimization problem to the static regret minimization problem. Subsequently, the techniques developed for comparator-adaptive methods can be applied to the dynamic regret minimization problem.\n- The paper offers a new analysis of the lower bound for dynamic regret minimization, revealing the intrinsic trade-off between the variability of the comparator sequence and the gradient norm.\n- A new type of squared dynamic regret bound is introduced in this paper, based on this novel perspective.", "weaknesses": "- 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.\n\n- 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.\n\n-  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.\n\nOverall, 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.\n\nReference: Zhiyu Zhang, Ashok Cutkosky, and Ioannis Ch. Paschalidis. Unconstrained dynamic regret via sparse coding, 2023.\n\n===post-rebuttal===\nMy 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The abstract claims that \\\"we show that dynamic regret minimization is\n> equivalent to static regret minimization in an extended decision\n> space.\\\" This claim is somewhat misleading to me, as the proposed\n> reduction only applies to the online linear optimization problem (or\n> OCO with linearized surrogate loss). It is unclear if the proposed\n> reduction holds for a broader range of dynamic regret minimization\n> problems, such as those involving exp-concave or strongly convex loss\n> functions.\n\nThe proposed reduction can be applied to any convex losses, including\nstrongly convex and exp-concave losses, by bounding\n$\\sum_{t=1}^{T}\\ell_{t}(w_{t})-\\ell_{t}(u_{t})\\le \\sum_{t=1}^{T}\\langle g_{t},w_{t}-u_{t}\\rangle= R_{T}^{\\text{Seq}}(\\tilde u)$\nvia convexity.\n\nWe can also be more precise, obtaining an **equality for convex\nlosses**, by observing that $$\\begin{aligned}\n  \\sum_{t=1}^{T}\\ell_{t}(w_{t})-\\ell_{t}(u_{t})=\\sum_{t=1}^{T} \\langle g_{t},w_{t}-u_{t}\\rangle-D_{\\ell_{t}}(u_{t}\\|w_{t})\\end{aligned}$$\nby definition of Bregman divergences. Since this is an equality, any\npossible improvements that one might hope to leverage in settings with\ncurvature are reflected in the terms $-D_{\\ell_{t}}(u_{t}\\|w_{t})$, while\nour reduction can be applied to the first term,\n$\\sum_{t=1}^{T}\\langle{g_{t},w_{t}-u_{t}}\\rangle=R_{T}^{\\text{Seq}}(\\tilde u)$.\nAs is usually the case, one should design their algorithm in such a way\nthat these curvature terms $-D_{\\ell_{t}}(u_{t}\\|w_{t})$ are properly\nleveraged in the end. For instance, for strongly-convex losses in the\nstatic regret setting, Algorithm 6 of Cutkosky & Orabona (2018) provides\na reduction for OLO which makes a guarantee that implies logarithmic\nregret when the curvature terms satisfy\n$-D_{\\ell_{t}}(u\\|w_{t})\\le -\\frac{\\alpha}{2}\\\\|u-w_{t}\\\\|^{2}$ (that is,\nwhen the losses are $\\alpha$-strongly convex). A similar reduction could\npotentially be applied here and would be an interesting direction for\nfuture investigation.\n\n> A similar reduction was presented in Section 2.2 of Zhang et al.,\n> 2023. It would be helpful if the authors provided a more detailed\n> comparison of the two reductions. In the related work section, the\n> paper states, \\\"We take a similar but slightly more general\n> approach.\\\" A more detailed explanation of how Proposition 1\n> generalizes previous work would be beneficial. Specifically, it would\n> be useful to clarify whether the proposition can be derived by\n> selecting a specific dictionary in Zhang et al., 2023. A more detailed\n> discussion in Section 2 of this paper would be advantageous.\n>\n> \\[\\...\\] it might be beneficial to explicitly state that previous work\n> has already somewhat demonstrated equivalence between the dynamic\n> regret minimization and static regret minimization problems.\n\nThe key difference is that we provide a general equivalence between\nstatic and dynamic regret that *any strategy* can be plugged into, while\nZhang et al. (2023) provide a reduction which prescribes a particular\nstrategy which allows the user to leverage static regret minimizers for\ndynamic regret. That is, our Proposition 1 holds regardless of what\nstrategy you end up choosing to set $w_{t}$, and simply shows that\nwriting the dynamic regret in a different way leads to static regret in\na different decision space. Because there is no restriction on how\n$w_{t}$ is set, our proposition actually captures the approach of Zhang\net al. (2023) as a special case. Note that this also demonstrates that\nthere is no choice of dictionary in the framework of Zhang et al. (2023)\nfrom which Proposition 1 can be derived --- Proposition 1 is strictly\nmore general.\n\nIn contrast, the approach proposed by Zhang et al. (2023) requires that\nthe designer commit to choosing $w_{t}=\\mathcal{H}\\_{t}x\\_{t}$ for some\nmatrix $\\mathcal{H}\\_{t}$ and where the coordinates of $x_{t}$ are\nseparate 1-dimensional learning algorithms. Because their approach\nprescribes a strategy that the user must design around, their approach\n*does not* imply an equivalence between dynamic and static regret, but\nrather provides a reduction that allows one to leverage a particular\nclass of static regret algorithms to design dynamic regret algorithms.\nThis potentially limits the types of guarantees that can be achieved\nusing the approach; for instance, the algorithm achieving the smoothed\npath-length result in Section 4.1 can not be represented in their\nframework, since it does not use separate coordinate-wise 1-dimensional\nupdates.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eBH1a9Z8Ym", "reviewer": "Reviewer_QTaB", "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.", "questions": "See weaknesses", "limitations": "Authors did discuss the limitation and potential future works.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The main contribution of this paper is demonstrating the equivalence between dynamic regret and static regret in extended space, which is quite interesting. This allows the authors to present a new lower bound and prove a new upper bound for dynamic regret. Although I am not very familiar with the literature on dynamic regret, I believe the result is significant if it is correct, especially in comparison to previous results stated in this paper.", "weaknesses": "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.\n\nMy 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> My question: The lower bound is\n> $\\tilde\\Omega (\\max\\_{M}G\\\\|\\tilde u\\\\|\\_{M^{-1}}\\sqrt{\\mathrm{Tr}(M)})$,\n> and the upper bound essentially is\n> $\\tilde O(\\min\\_{M}G\\\\|\\tilde u\\\\|\\_{M^{-1}}\\sqrt{\\mathrm{Tr}(M)})$.\n\nThere seems to be a misunderstanding of the quantification of $M$ in the\nlower and upper bounds. The lower bound holds for *any* $M$ satisfying\nthe conditions, not just for the worst-case $M$. Similarly our upper\nbound holds for any valid choice of $M$ rather than just the best one.\nSo the upper and lower bounds do indeed match.\n\nTo clarify the ideas, it might be useful to compare it, for example,\nwith online mirror descent with $p$-norms: there exist upper and lower\nbounds that both hold for any $p$, not just with the best/worst ones.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kObb0FyDdF", "reviewer": "Reviewer_yAJf", "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.\n\nIn Theorem 1, the paper establishes a lower bound, indicating that squared path-length incurs a linear penalty, making adaptation to squared path-length impossible.\n\nFurthermore, 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 \n$\\|\\cdot\\|_{M}$. \n\nIn Section 4.1, the authors discuss the suitable choice for $M$. By setting $M=(HH^{\\top}) ^{−1}$, where \n$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.", "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": "The authors addressed the limitations of their work.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The message of the paper is clear, and the theoretical results are solid, consisting of a collection of small steps and observations that lead to important and surprising conclusions. The paper is extremely well-written and a pleasure to read.", "weaknesses": "I do not see any particular weaknesses in the paper.\n\nMinor point: There are typos in lines 164 to 167. $V$ should be $V_T$ and $\\epsilon$ should be $\\epsilon_T$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review, we are glad you enjoyed reading our\npaper!\n\n> I would like to know which measures of variability the authors expect\n> to obtain with different choices of that yield reasonable and\n> significant regret bounds.\n\nSo far the literature mostly revolves around the (unsquared) path-length\nas the measure of variability. One of the exciting things about this\nwork is that it opens the door for many unexplored directions in terms\nof the variability measure, and provides a convenient framework for\nstudying new notions of variability and their trade-offs. In this work,\nwe focused on achieving results related to squared path-length, but it\nmay be possible to achieve results scaling with more general distance\nmetrics, for instance by leveraging the notion of group norms. The\nvariance-variability coupling guarantees in Section 5 are also a very\nopen and almost entirely unexplored direction that we would like to\ninvestigate further.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kA3aup50Ct", "reviewer": "Reviewer_bfmX", "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.", "questions": "1. Does the high-dimensional embedding reduction also hold for adpative regret (to static regret)?\n2. Can we directly design a unified algorithm (best-of-both-worlds) without knowing the types of regret based on this reduction?", "limitations": "\\", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "- The paper establishes a novel equivalence between static and dynamic regret minimization. This theoretical contribution provides a unified framework for analyzing and designing algorithms for dynamic regret minimization, leveraging the well-established techniques for static regret.\n\n- By establishing the trade-off between penalties due to the variance of the losses and the variability of the comparator sequence, the paper provides deep insights into the inherent limitations and trade-offs in dynamic regret minimization. This understanding is crucial for developing more effective algorithms and sets a foundation for future research in the area.\n\n- The introduction of the locally-smoothed squared path-length reduces variance penalties, balances adaptability by smoothing out noise, and facilitates the decoupling of regret terms, leading to more practical and robust dynamic regret bounds.", "weaknesses": "- 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.\n\n- 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. \n\n- 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.\n\n- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> My major concern is the main titile could be somewhat overclaimed, as\n> the proposed reduciton is restricted in OLO\n\nWe actually believe that our title is carefully worded to avoid\noverclaiming: we do indeed present *an* equivalence between static and\ndynamic regret --- it is one which holds in a particular context, and\nour abstract and introduction state very clearly the scope of this work.\nNote also that, as discussed in [this comment](https://openreview.net/forum?id=hD8Et4uZ1o&noteId=CJxEDImAbf), the equivalence\ncan be applied more generally for OCO.\n\nThat said, we do not think this is a big issue either way: we can add\n\"for Linear Losses\" to the title if it solves the major concern of the\nreviewer.\n\n> The approach involves embedding the comparator sequence into a\n> higher-dimensional space, which could significantly increase\n> computational complexity. Related concerns should be discussed,\n> particularly in terms of implementing the proposed methods in\n> large-scale or real-time applications.\n\nComputational complexity is indeed one of the main considerations when\nchoosing the dual norm pair $(\\\\|\\cdot\\\\|,\\\\|\\cdot\\\\|_{*})$ (i.e., choosing\nthe matrix $M$ in the context of Theorem 2), and we do discuss it on\npage 4, line 136. Moreover, the computational complexity of the\nalgorithm achieving the smoothed square path-length bound (characterized\nin Proposition 3) is discussed on page 8.\n\nWe can add some additional discussion regarding the related\nimplementation concerns. Note that these concerns are shared by all\nother dynamic regret algorithms achieving a non-trivial dependence on\nthe comparator variability, as our algorithm can be implemented with the\n*same* computational $O(d\\log T)$ per-round complexity as prior works,\nas discussed on page 8.\n\n> Does the high-dimensional embedding reduction also hold for adpative\n> regret (to static regret)?\n\nNo, adaptive regret involves making guarantees over all sub-intervals\nsimultaneously, while the proposed reduction explicitly considers the\ntotal loss over the entire interval $[1,T]$. These are quite separate\nnotions of performance and there is no known general equivalence between\nthem.\n\n> Can we directly design a unified algorithm (best-of-both-worlds)\n> without knowing the types of regret based on this reduction?\n\nIf by types of regret you are referring to static vs. dynamic regret,\nthe answer is *yes*: in fact, our guarantee in Theorem 2 captures static\nregret as a special case. If by types of regret your are referring to\nadapting to various different measures of variability (e.g., Theorem 2\nwith different choices of $M$), *the answer is also yes*: see the last\npart of our [global response here](https://openreview.net/forum?id=hD8Et4uZ1o&noteId=2OutnXLWT0) for details.\n\n> The reasons for choosing this locally-smoothed square path-length is\n> not clear. If I get it right, path-lengthes sharing similar\n> local-smoothness would all fullfill the requirements. Meanwhile, this\n> locally-smoothed square path-length is too detailed such that it may\n> loose empirical intuitions or physical meanings to some extent.\n\nDue to space constraints, please see our [global response here](https://openreview.net/forum?id=hD8Et4uZ1o&noteId=2OutnXLWT0)\nfor a detailed discussion of these concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their thoughtful comments and taking the time to carefully read our paper. Below, we address
some of their common questions.

A common point contention in the reviews was the significance of the
average squared path-length dependence guarantee achieved in Proposition
3. We provide additional discussion about these concerns below, but we
would first like to stress that **the power of our approach lies in its
generality**. Indeed, our lower bound shows more generally that *there
exists a fundamental trade-off between the comparator variability
penalty and the gradient variance penalty*, so there is no one measure
of variability that is strictly better across all problem instances.
This is similar to the trade-off existing in terms of dual norms in
online mirror descent. We are not aware of any other paper on dynamic
regret pointing out these fundamental trade-offs, and this result is due
to our simple equivalence with static regret. Our general result in
*Theorem 2 provides a framework for achieving any of these trade-offs*,
simply by changing the choice of weighting matrix $M$. In Proposition 3,
we provided as an example one instance of the more general result
because we believe it is a reasonable compromise to the square
path-length, but we stress that our result is much more general than
this one example. Achieving more favorable trade-offs via cleverly
crafted weighting matrices $M$ is an important direction for future
work. Moreover, as we show below, given multiple different choices of
$M$ we can always easily ensure the best of their guarantees.

**Motivation of averaged squared length/intuition.** It is important to
understand that we proved that it is impossible to adapt to the squared
path-length $P_{T}^{\\|\cdot\\|^{2}}$ without making the regret guarantee
vacuous. More fundamentally, the lower bound says that this is the wrong
quantity to consider, so we must look for some achievable compromise.
The average squared path-length is one such reasonable compromise for
the following reasons:

1\) It is never be worse (up to polylog factors) than the usual
path-length $P_{T}^{\\|\cdot\\|}$;

2\) The algorithm which achieves adaptivity to the averaged square
path-length can be implemented in the same $O(d\log T )$ per-round
complexity enjoyed by prior works;

3\) It shares a similar physical meaning to the squared path length.

It should be clear why points 1 and 2 are important, so let's now focus
on point 3. The averaged squared path length is nothing else than the
sum of the squared path length at different time scales, see line 232.
In this view, the averaged squared path length includes the squared path
length, but it seems to inflate it just enough to avoid the vacuous
result given by our lower bound (i.e., Proposition 2). Now, one might
wonder by how much this is inflated, and 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. So, ignoring the log
factor, we are essentially substituting the squared path length at time
scale 1, with the maximum over $\tau$ of the squared path length at time
scale $\tau$. Thus, the original squared path length measures the drift
only at high frequency, while the averaged path length measures the
drift in all frequencies, like a more holistic measure of drift.
Moreover, this measure can be very close (or even equal!) to the squared
path-length in some instances. Indeed, consider a comparator sequence
which alternates between $a$ and $b$: on each of the timescales
$\tau=2^{i}$, the averages on each of the intervals of length $\tau$
will be $\bar u_{i}=(a+b)/2$. Hence the average square path-length at
timescale $\tau$ is $0$ for any $\tau$ except for $\tau=1$ so the two
measures are *exactly* equivalent here. However, it is impossible
compare favorably with the square path-length across *all* possible
problem instances due to the fundamental trade-off discussed above.
Nevertheless, we show below that one can easily combine the guarantees
achieved by different choices of $M$.

Finally, we would also like to point out that Proposition 3 is the
*first square path-length bound of any kind* that holds for arbitrary
comparator sequences, so we believe the result is of interest to the
community despite the fairly reasonable compromises discussed above.

**Best-of-Both Worlds Guarantees.** As discussed above, our lower bound
demonstrates a trade-off such that no $M$ can lead to uniformly better
guarantees across all problem instances. Luckily, given any two
instances of the algorithm in Theorem 2, call them $A$ and $B$, with
difference choices of the matrix $M$, we can always achieve the better
of their two guarantees using the standard iterate-adding argument of
Cutkosky (2018). The idea is simple: observe that for any choice of $M$,
Theorem 2 provides an algorithm guaranteeing
$R_{T}(0,\ldots,0)\le O(\epsilon)$. Hence, letting $w_{t}^{A}$ and
$w_{t}^{B}$ denote the outputs of algorithms $A$ and $B$ on round $t$,
suppose we play $w_{t}=w_{t}^{A}+w_{t}^{B}$. Then our dynamic regret is
$$\begin{aligned}
  R_{T}(\vec{u})= \sum_{t=1}^{T}\langle g_{t},w_{t}^{A}+w_{t}^{B}-u_{t}\rangle = R_{T}^{A}(\vec{u})+R_{T}^{B}(0,\ldots,0)\le O(R_{T}^{A}(\vec{u})+\epsilon),\end{aligned}$$
and similarly, we have
$R_{T}(\vec{u})\le O(\epsilon + R_{T}^{B}(\vec{u}))$. Since both of
these hold, overall we have
$R_{T}(\vec{u})\le O(\epsilon + \min\{R_{T}^{A}(\vec{u}),R_{T}^{B}(\vec{u})\})$.
The argument immediately extends to combining the guarantees of $N$
algorithms at the cost of only an $O(\epsilon N)$ penalty. Moreover, the
parameter $\epsilon$ in Theorem 2 appears only in $O(\epsilon)$ and
$\log(1/\epsilon)$ terms, so we can safely scale it by $1/N$ so that
combining $N$ algorithms requires only an $\log N$ penalty.

Meta-review: 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.
Decision: Accept (poster)