Dynamic Regret Reduces to Kernelized Static Regret
Authors: Andrew Jacobsen
Alessandro Rudi
Francesco Orabona
Nicolò Cesa-Bianchi
Venue: NeurIPS 2025 poster ()
Keywords: dynamic regret
online learning
parameter-free
non-stationary
kernels
reproducing kernel hilbert space
RKHS
Primary area: theory
TL;DR: We frame dynamic regret minimization as a static regret problem in an RKHS

Abstract: We study dynamic regret in online convex optimization, where the objective is to achieve low cumulative loss relative to an arbitrary benchmark sequence. By observing that competing with an arbitrary sequence of comparators $u_{1},\ldots,u_{T}$ in $\mathcal{W}\subseteq\mathbb{R}^{d}$ can be reframed as competing with a  *fixed* comparator *function* $u:[1,T]\to \mathcal{W}$,  we cast dynamic regret minimization as a *static regret* problem in a *function space*. By carefully constructing a suitable function space in the form of a Reproducing Kernel Hilbert Space (RKHS), our reduction enables us to recover the optimal $R_{T}(u_{1},\ldots,u_{T}) = \mathcal{O}(\sqrt{\sum_{t}\\|u_{t}-u_{t-1}\\|T})$ dynamic regret guarantee in the setting of linear losses, and yields new scale-free and directionally-adaptive dynamic regret guarantees. Moreover, unlike prior dynamic-to-static reductions---which are valid only for linear losses---our reduction holds for *any* sequence of losses, allowing us to recover $\mathcal{O}\big(\\|u\\|^2_{\mathcal{H}}+d_{\mathrm{eff}}(\lambda)\ln T\big)$ bounds when the losses have meaningful curvature, where $d_{\mathrm{eff}}(\lambda)$ is a measure of complexity of the RKHS. Despite working in an infinite-dimensional space, the resulting reduction leads to algorithms that are computable in practice, due to the reproducing property of RKHSs.

Dynamic Regret Reduces to Kernelized Static Regret
Andrew Jacobsen' Università degli Studi di Milano Politecnico di Milano
Alessandro Rudi"
Bocconi University
alessandro rudi @sdabocconi.
contactBandre--jaobsee.ccmm com
Francesco Orabona
King Abdullah University of Science and Technology (KAUST)
Thuwal, 23955-6900, Kingdom of Saudi Arabia
francescoooraboaa.com
Nicolò Cesa-Bianchi
Università degli Studi di Milano Politecnico di Milano
nicolo. ces. iinee--bbbanniiiuiiiiii it
Abstract
We study dynamic regret in online convex optimization, where the objective is to achieve low cumulative loss relative to an arbitrary benchmark sequence. By observing that competing with arbitrary sequence of comparators U1..... Wr in W C Rd can be reframed as competing with a fixed comparator function u [1, - W, cast dynamic regret minimization a function space. By carefully constructing a suitable function space in the form Reproducing Kemel Hilbert Space (RKHS), our reduction enables
static regret problem in
recover the optimal Rr(u1,... UT) O(VE, ||, u (T) dynamic regret guaran- tee in the setting of linear losses, and yields new scale-free and directionally- adaptive dynamic regret guarantees. Moreover, unlike prior dynamic-to-statiee reductions- which are valid only for linear losses-or our reduction holds for any sequence of losses, allowing us recover ([[u]] 2/ dotr In 7') bounds when the losses have meaningful curvature, where dea((A) is measure of complexity of the RKHS. Despite working in an diinite-dimeniionll space, the resulting reduc- tion leads to algorithms that are computable in practice, due to the reproducing property of RKHSs.
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 [10, 11, 18. 39, 59]. Formally, consider T rounds of interaction between a learner and the environment. In each round, the learner chooses we W from convex W C Rd the environment reveals convex loss function é, W + IR, and the learner incurs a loss of & (wy)) The classic objective in this setting is minimize the learner's regret relative any fixed benchmark u E W:
RT(u) =
T (T=((((we)) (())))
Equul contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(t))
Transform
3 5
2
5
Figure I: Transformation from sequence of comparators to function. Many functions may implement the transformation. Section we will see that under mild assumptions on the chosen function space H we can always find a function H such that u(t) Me for all and ||u| Ae - Ei= l|ue Mc-1ll).
In this paper, we study the more general problem of minimizing the learner's 's regret relative to any sequence of benchmarks u1...., ur W/ [21, 22, 59]:
RT Rr(u1..... WT) = Σ ( ky
This objective is typically referred to as dynamic regret, to distinguish it from the special case where wr (referred
the comparator sequence is fixed regret captures a notion of non-stationann stastiaaion in learning problems. Problem instances where in = wr model classic problem settings, wherein there is fixed "solution" whose performance we want to emulate, while a time-varying comparator sequence models problem settings where the learner needs continuously adapt changing environment in which the solution is varying The complexity of given comparator sequence is typically characterized by its path-length:
static regret). Intuitively, dynamic
PT = >r= ||u wt-1ll
Clearly, if the path-length is large there is hope to obtain low dynamic regret. The goal is thus to obtain performance guarantees that gracefully adapt to the level of -on-stationarit. For instance, in the setting of G-Lipschitz losses and bounded domain D supa.yew || - y/I. the minimax optimal dynamic regret guarantee is of the order of ((G/(D2 + DP)) which scales naturally with the complexity of the benchmark sequence and recovers the optimal O(GDVT) static regret guarantee when the comparator is fixed. In unbounded domains (e.g., W = Rd) these bounds would be vacuous, so the guarantee should instead be adaptive M == max; ||ue|]- In this case an analogous guarantee of (G (M2 + MP) can be achieved at the expense of additional logarithmic terms. Throughout the paper focus the unbounded setting.
Contributions. In this work we introduce a new framework for reducing dynamic regret mini- mization static regret minimization. Our key insight that competing with sequence u1.-.-3 WT in W can be equivalently framed as competing with some fixed function u(-) such that u(t) = me for all f. In this view, we effectively transform dynamic regret minimization over a domain W C Rd into static regret minimization problem over domain of functions, depieted graphically in Figure 1.
The choice of the function space is crucial, as controls the trade-offs of the resulting algorithm. To complete the construction, we carefully design rich family of function spaces which embed comparator sequence way that (1) optimizes the inherent trade-offss of the function class to achieve optimal dynamic regret guarantees and (2) ensures that the resulting algorithm is computable in practice, despite being stated as an dimenti-ad optimization problem. Indeed, the family design is instance of a Reproducing Kernel Hilbert Space (RKHS). well-studied class of functions endowed with the familiar structure of a Hilbert space. The reduction to learning in an RKHS is particularly natural in the context of online learning- the vast majority of modern online learning theory developed for static regret minimization in Hilbert spaces, so our reduction enables the use of the familiar online learning toolkit while also allowing between dynamic regret minimization, kernel methods, and signal processing theory.
draw upon deep connections
In the linear losses setting, our construction enables us to achieve the optimal dynamic regret guar- antees of (MMMPT) up to poly-logarithmic terms. Notably, the resulting algorithm is naturally horizon independent, and is easily extended to a scale-free version. These are the first algorithms

---

that obtain the optimal vPr dependence without prior knowledge of the horizon T natively, without resorting to the doubling trick. Our reduction also enables us derive new directionally-adappii guarantees, which scale as Ō V den (A) (A)
[|ul + E (ge. ui²²), where Ilulfza and denl (A) are measures of the complexity of the comparator function and complexity of the function class H re-
spectively.
Interestingly, because reduction only involves viewing the comparator sequence through a dif- ferent lens, it holds for any sequence of loss functions, contrasting prior works which are valid only for linear losses [26, 55]. We show that this allows us to account for loss curvature and ob- tain O(A || + datt log T) dynamic regret in the context of strongly-conee exp-coneave, and improper linear regression settings.
Related Works. Our work is most directly related to a recent thread of research in the linear loss setting initiated by Zhang et al. [55]. Their strategy approaches dynamic regret from a signal processing perspective, wherein the comparator sequence is stacked into high -igh-dimensionll "signal" vec (u1, Wr) E ReT and 1-dimensional static regret algorithms are employed to learn the coefficients of basis of features which decompose that signal, leading to O (7MMPTT) dynamic regret via a carefully chosen dictionary of features. Jacobsen and Orabona [26] generalize this perspective by designing static regret algorithms that applied directly in this high-dimensional space, and derive the O (r)PPTT) bound by choosing a suitable dual-norm pair in this space, such that ||||| = O (. Our work further extends this perspective by interpreting the comparator sequence samples of function in RKHS H. and designing algorithms which obtain suitable static regret guarantees in function space. The reduction of Jacobsen and Orabona [26] can in fact be understood special case of our framework by choosing the discrete RKHS H. associated with the Dirac kernel.
More broadly, the concept of dynamic regret originally introduced by Herbster and Warmuth [21, 22]. Later, Zinkevich [59] showed that OGD naturally obtains (PPvTT) dynamic regret and Yang et al. [52] showed that (VDDPTT can be achieved when prior knowledge of Pr is avail- able. The first to achieve the ((VDP,T) rate without prior knowledge of Pr was Zhang et al. [53]. who also proved a matching lower bound, and the analogous bound of O(vMP)7) has been achieved up to logarithmic terms in unbounded settings [23, 24, 33, 55]. There have also been several refinements to the result, replacing the T factor with data-dependen quantities such as Ein 19. 1l² or Σ. supa. /u f (x)) [9, 14, 19]. Going beyond linear losses, various improve- ments in adaptivity can be obtained when the losses are smooth or exp-concave, such as replacing the T factor with E, (ue) or E, sup.. [[ 1 [56-58]. In the squared loss setting (w)) 1 (yr (a-ww) w minimax optimal rates of RT ... úr) = (C22/111/3) have been obtained where Cr = Et= 0 - is the path-length of the benchmark predictions [3-5, 29, 44, 54].
2 Preliminaries
Notations. Hilbert spaces are denoted by upper case calligraphic letters. Given a Hilbert space H. we denote the associated inner product by (- We denote L(H, W)) the space of linear operators from H to W. L(H, W) is itself Hilbert space when equipped with the Hilbert- Schhiid inner product, (A, B) HS Tr (A* B), where A L(W, H) is the adjoint of A. The subdifferential set of a function f at x is denoted by 0f(z). We will occasionally abuse notation and write (xx) to mean arbitrary element of (x)). We will denote by [T] the set (1.2..... T).. The Fourier transform of a function Q is denoted [zQ](z)= = fg Q(w)e 2miow des and, when clear from context, will generally abbreviate [(Q[(x) ((x).
(h: R} be Hilbert space of functions a on compact set T. The space H. is a RKHS [1] if there exists positive definite function k T x T + I. such that k((,ar)) E H for all x E T, that has the reproducing property, i.e. we have ((x) = (f, ()) H for all f E H and E T. The function k is called the kernel function associated with H and the function (xx) k(s x) is called the feature map. It is known that the kernel function uniquely characterizes the RKHS H. A kernel is universal if it can approximate any
Reproducing Kernel Hilbert Spaces. Let
3

---

Algorithm 1: Kernelized Online Learning
Input:
Domain W C R2 feature map 6: + H. algorithm A defined on L(H, W)
for l 1: T do
Receive W, E L(H, W) from A and play wi = Wio(!) E W
Observe loss function & W + I and incur loss (x(wr)
Send 4: W + & ((t) to A as the thh auxiliary loss
end
real-valued continuous function on T to arbitrary accuracy. Many of the standard kernel functions are universal, including the Gaussian RBF kernel, the Matérn kernel, and inverse multiquadratic kernel. All kernels considered in this work are universal kernels. For detailed introduction to kernel methods, see, e.g., Berlinet and Thomas-Agnan [6], Paulsen and Raghupathi [42], Schölkopf and Smola [45], Wendland [51].
We will often be interested in functions taking values in W C RR, In this case the usual RKHS ma- chinery extends in a straight-forward way via a coordinate-wist wise extension. Indeed, we can represent w : 77- IR tuple = (Wi,.... ................................ wa) such that wy E H. for each i.2 This naturally leads to an operator-based version of the reproducing property:
w(t) =
ux)(t) ((w1, ((t)) (wa, o()))) Wé(()= E W.
where W T.HH, W). The space I.HH, W) is itself a Hilbert space when equipped with the Hilbert- Schmidt norm, and under the coordinate-wise extension above we have ||W = || = E |/: Moreover, observe that when d this setup simply reduces back to the usual setup, wherein |W = |!l and w(t)= = (w, (f))
For notational clarity we will refer to functions w(-) E H and their values w(t) E W with lower- case letters, and their representation W E L(H, W) using the upper-case. We will typically use the notation we in place of wtt) when referring to the evaluations of w()) at discrete time-points / (T].
3 An Equivalence Between Static and Dynamic Regret
In this section, we present the main tool that we will use to develop dynamic regret guarantees for online learning. The key idea is interpret the comparator sequence - uT UT E W as the evaluations of a function u(-) at the discrete time-points & E [T], allowing us to re-frame dynamic
regret minimization as static regret minimization in function space.
Note that most existing work in online learning revolves around learning in Hilbert spaces, not gen- eral function spaces, so if we hope to leverage these existing tools we should embed the comparator sequence in a Hilbert space of functions. In particular, our approach will be to embed the compara- tor sequence in Hilbert space H. of functions representable by reproducing kernel k(s. t) and feature map o T - H. Note that this is always possible by selecting a universal kernel on T. Our reduction is conceptually shown in Algorithm and the following theorem shows that the dynamic regret w.r.t. comparator sequence u,,..., Uy in W is equivalent to static regret w.r.t. a function ((-) E H on the auxiliary loss sequence f, W + (W))))))
Theorem 1 (Dynamic Regret via Kernelized Static Regret). Let 'T be compact set, W C Rd., let H be an RKHS with associated feature map T - ((W) = (W o(t)). Let WI....,Wo Wr be an arbitrary sequence in L(H. and suppose that on each round we play w, Wio(t) W. Then, for any comparator sequence U1.... UT in W and U E W) satisfying
H. and for any W E L(H, W) let
Ut)() for a,
RT(wi,.... WT) (e((w)) le(we))
-Z())
1ml
Note that the reduction holds for any operator U E T.H, W) which interpolates the comparator sequence, ", = Uo(t) Vt. Hence, we can always let u(-) H be the minimum norm function in H which interpolates these points, and take U to be its representation in L(H, W). In fact, since k is
This connection can be made more formally via Riesz representation theorem, Appendix A for details.

---

universal kerne,, we can assume that u(-) E Htl approximates any continuous function on T S [1. T] arbitrary accuracy, so the assumption that u(-) lives an RKHS H. does not actually restrict the functions that we can compare against in a significant way. We will see concrete example of an RKHS H which reconstructs arbitrary comparator sequences in later sections (e.g., Theorem 4).
Our reduction bears a strong resemblance to the reduction recently proposed by Jacobsen and Orabona [26], which works by embedding the comparator sequence in E by simply "stacking" the comparator sequence into one long vector, ū = vec (u,,... WT) E R In fact, we show in Appendix B that our framework precisely recovers the reduction Jacobsen and Orabona [26] by choosing the discrete RKHS V. associated with the Dirac kernel. However, notice in particular that this means that their reduction is inherently tied to finite- dimeessninnii features, whereas ours enables -iineie-dimesiinall features. As we will see in Section 4, this distinction is key to obtaining the optimal path-length dependencies in a horizon-independent manner. Moreover, note that the regret equality in Jacohsen and Orabona [26] holds only in the context of linear losses, (w() - (gt, w),, whereas in our framework the regret equality holds for any sequence of losses fi. fr. We will see that this distinction is important in Section f-for example, our reduction allows us to preserve the curvature of the losses needed to obtain O[]uu] + deft (A) In T") bounds when the original losses l are strongly convex or exp-concave, where delf (A) is a measure of complexity of the RKHS.
Linear Losses
We first consider the setting of online linear optimization. In this setting, round t the learner receives linear loss (((w) = (gt, w)w so recalling the reduction in the previous section defines the auxiliary loss as l; W E L(H. W) - (()))() E R. we have
(W) (g,, Wo(l)) for @(t), W) (G,, W)hs;
where G. = gr 8 (t) E L(H, W) is the rank one operator such that (g. (h))) = (0(t), ge for any h H. As such, it is important that the base algorithm facilitates application of the kernel trick to avoid explicitly evaluating the feature map ((t), which may be infiniteddimensional in general. To help make things concrete and provide intuitions, the following example shows that many of the common algorithms based on Follow the Regularized Leader (FTRL) with a radially- symmetric regularizer the fundamental regularizers in online learning, such as quadratic regularizers and the "lincarithmic" [41] regularizers 1 [l) z || / log( [| /a + 1) associated with the comparator caaparator-addative regret guarantees that the key result of this section (Proposition 1) will be derived from.
(( are amenable to the kernel trick. This class captures many of
Example 1. (Kernel Trick for Kernelized FTRL) Let 91 91...., gT be a sequence in W and let G. Σ
G., V₁ = E ||Grl| let & (-(:; Vi) be a comvex function with differentiable Fenchel conjugate V and consider the following FTRL update:
& o(t) E L(H. (CHH.W)ro t. Let
O₂
W. = argmin min (0t, W) + (r([W V.) = Vo (IlOellns: VV)) = WEL(H(W))
(1))(( Vi)
110ellu
Then, V = -'-= I1g. ln k(t,t) t) (Lemma 10), |10, 2 = E.j k(s, s') (ge.9w)n (Lemma 9), and on round t, Algorithm 1 plays
wc Wto(t) (17)((10el] Vi) 00: IHS
k(s, t)g..
The example shows that many common instances of FTRL can be kernelized without explicit com- putation of the feature map. The example also demonstrates an important consideration when apply- ing static regret decompositions of this nature: the update described above would require ((t) time and memory to implement in general, while existing algorithms for dynamic regret can often be im- plemented using OIn T') computation and memory [23, 53, 55, 58]. Luckily, there is already a deep and well-developed literature on efficient approximations for kernel methods that can be leveraged to translate the algorithms developed from the kernelized OCO point-of-view into more practically implementable algorithms [see, e.g., 31, 47]. Since these extensions are already well-understood and since implementating these details would not yield any new insights in the current paper, we will not consider them further here, focusing instead on the theoretical development.
5

---

Now that we have seen how to translate an algorithm's 's updates to the kernelized setting, we turn now how translate its static regret guarantees into dynamic regret guarantees. The following result shows that an algorithm's s kernelized static regret guarantee translates in straight-frwward way to dynamic regret guarantee the original problem. The proof immediate by applying Theorem and computing ||GEllus- = l1g. @ o(t]l = 11 llw vk(ttt) by Lemma 10.
Theorem 2. Let A be online learning algorithm defined on Hilbert space V. Suppose that for any sequence of convex loss functions h1,..., hy on V. A obtains a bound on the static regret (hr)llll for any comparator U E V I, where (W, E (W,) for all t. If we apply A in L(H,W) with I1-Ily = Il-llss then for any sequence u1...., uT in W and U L(H.W) satisfying u1 = U@(t)for all Algorithm I with A guarantees
of the form (U) < Br (1] h1 (W1 willll......
and some function BT R T21
Rr(u1,.... ur)) & Br (II [ns. liillyy //1,, 1), (l..llllllww/(...))
where gr E (dl((re) for all t, and k(;;,) :) is the reproducing kernel associated to the space H.
The value of the lemma is that it enables us to immediately translate static regret guarantees from OLO to guarantees in our RKHS formulation of dynamic regret, wherein the complexity of the comparator sequence is measured by the RKHS norm || = ||u]] zd. For instance, if we simply apply the standard (sub)gradient descent guarantee to Theorem 2 we get
|| 2d
(T UT) (U) S
+
" Σ
ge Iww k(t,t).
2n
Optimally tuning 7 yields ( ur) S ||u||
ET= 11: k(t, t), so achieving the op- timal O (VPTT) has effectively been reduced to the problem of designing kernel such that? [|u]] V Σ 1| = Ö(PPr) while controlling Att, t). We will see in Section 4.1 that this can be accomplished by using a carefully chosen wanslation-invariint kernel.
In the above argument, the optimal choice of would require prior knowledge of || and cannot be chosen in general. Luckily, there are static regret algorithms which can adapt to the comparator norm automatically to obtain the optimal trade-off up logarithmic terms [16, 23, 35, 36, 40]. For our purposes we will refer to an algorithm A defined on Hilbert space as parameter-free for any sequence G-Lipschitz loss functions h1 ,,,...,/y hr and any U V. A guarantees
(U) = 5 | V E (he(W.))
(1)
There are many existing algorithms which satisfy this property; we provide concrete example and its updates in our framework for completeness in Appendix C.2. Using such an algorithm in Algorithm immediately yields the following regret guarantee.
Let A be a static regret algorithm for Hilbert spaces satisfying Equation (1), For any G > O, any sequence of G-Lischiitz losses f,....,&y and any sequence u1....; up in W, and U E L(H, W) satisfying un Ut(t), Algorithm 1 applied with A guarantees
Proposition 1.
Ry(u...... wr) = (U)= = -011Illas v ET= Ilael t(t,t))
(2)
where gr E (we) for all t.
4.1 Controlling the Trade-off's Induced by H
Proposition demonstrates clear trade-off between the RKHS norm ||u]| and the associated kernel ktt, t) induced by the choice of function space: smaller the RKHS norms correspond to larger function spaces, hence higher values of k(t, t). In order to obtain the optimal O ( dynamic regret, we need to design a kernel such that || llu ||ul| = O(PPr) and k(t, f) is
Here and in the following the θ notation will hide polylogarithmic factors.

---

controlled for all t. Throughout this section, we will assume for simplicity that d = but note that the extension
is straightforward via the coordinate-wise extension in Section 2.
Recall that a translation invariant kernel over IR is characterized by the Fourier transform of its spec- tral density Q [51], where Q is real non-negative integrable function. In particular, translation invariant kernel and its associated norm are
k(t,t')= = Q +t) / Q(w)e 20iilt-- 11 -
(f(w)? Q(w) dw.
(3)
where we use the short-hand notation 7 Flg] to denote the Fourier transorm of a function g(-). The intuition behind focusing on translation-invatt invariant kernels is that the associated norm provides natural connection to the v Vr dependencies we would like like to achieve. Indeed, observe that with spectral density ((w)) = 1/w, we would have via Parseval's identity and the fact that (=)( = (Ww) that
[ Wū(W) Vu((t)lu(()at suplu(t)) | |uul = JR
(4)
which is the continuous-time analogue of MPr. The key challenge is to choose an integrable Q(w) which suitably trades off the comparator norm || and the magnitude of the associated kernel entries k(t,, t). Unfortunately, these trade-offs are non-trivial using standard cunslation-ivaaiian kernels, shown in the following example.
Example 2 (Existing kernels lead to sub- sub-optimal trade-offs [5I]. first glance, the spline kernel seems like a natural candidate since it has [| V|Vul = [|ue- -u-11 11=) (Theorem 8). However, the spline kernel also has k(t. 1) = I, leading to suboptimal rate in Proposition 1. On the other hand, for the classical translation invariant kernels such as the Gaussian or the Matern ker- nels, we have k(t,t) (1) but || [|u][2 +Enz Cn Cnl|V"ul for en positive and summable. In this case, note that k(t, t) has the good rate but ||u|| 22 2 ||]l and [|ul] = e²T already for constant comparators on [0, T.. u(t)= = cl (t) > O, precluding the optimal rate.
Given the above, we next turn our attention to designing new kernel that will achieve the desired trade-offss. Since we need to find a delicate balance the trade-off of [|u æ and k(t, t) achieve optimal rates, in the first part of the section we first derive a result that identifies general sufficient conditions to bound the RKHS norm of a translation invariant kernel in terms of the continuous path- length [|Vull, = (t)((t) (Theorem 3). Then, in Proposition 2, we design an explicit kernel satisfying such conditions, leading show that under mild conditions (which are satisfied by the kernel in the Proposition 2), it is always possible to find an u(.)) E H such that u(t) u, for all and Vulllza OiE, ||ue U4-1 llw), so achieving dynamic regret scaling with ||ul| = Vullll,,, recovers the usual path-length. The proof of the following theorem can be found in Appendix E.I
trade-off of O O(VI[Vul T). Finally, in Theorem 4
Theorem 3. Let Q R + R, be an integrable strictly positive even function on R \ {0} and such that R(x) == 2T (x + (2/2T) ((())) is also integrable for some m E N, m 2 1. Let k be defined in terms of Q as in Eq. (3). Then l is a translation invariant universal kernel with l(tt,)) < 1 for all 1 E R.. The RKHS H associated to k contains the space of finitely supported functions with bounded derivatives up to order 2m, and moreover, for any T and any 2m-times
differentiable function f that is supported on [0, T + 1).
lf S c(T)) fll If - 2 fllz^,
where e(T) == =[[F[R]] (1 If R is monotonically decreasing on (0, oo), then,
2n (T 1)² [- R(x)ada + n
2 R(x) dx
c(T)) inf as0
VT
With this hand, the following proposition provides an example of spectral density Q which will leads to the desired dependency ||u]| V[I (.) up to poly-logarithmic terms. Proof can be found in Appendix E.4.
7

---

Proposition 2. Let Q: IR + R, be defined as
1/4 log log
Q(w) = |o (1+ [w|//>2>)) log(" + (w] log log(a + 1w]-
Then apply Theorem 3 with 1: the function io defined in terms of Q as in Eq. (3) is translation invariant kernel with k(t, & 8T², Vt E R; the associated RKHS norm satisfies
1 S è² |Vlll IlS - Il (In(1 + T)) In In(1 + +T)),
for any f that is 2-times differentiable and supported in [0, + 1). where T > 2 and c S (2Te)².
A notable property of the kernel characterized by Proposition 2 is that it is horizon independent, requiring no upper bound on T to control || and k(t, This is a non-trivial property to guaran- tee using existing methods without resorting to the doubling trick, which well-known to perform poorly in practice. The intuitions behind the choice of Q(w) follow from the discussion above: we would like set Q(w)) = 1/|w| so that ||u]| relates the path-length via Equation (4), but this would not be a valid choice because Q(w) = 11/ww| is not integrable. Proposition adds small bit of additional regularization to ensure that (ww) is integrable while remaining close to 1//w// We
provide additional intuition on the choice of regularization in Appendix D.
A subtlety that we have glossed over thus far is that the continuous path-length, [ C (lVu(t) dt, does not necessarily compare favorably to the classic discrete path-length Pr E. ||ue ut-1 llw since the function may vary wildly between the interpolated points. The next theorem shows that we can always find function such that Vull = (Prr.. Proof can be found in Appendix E.2.
Theorem 4. Let v1,..., E Rd and let H be the RKHS associated to kernel l contain finitely supported functions with bounded derivatives up order 2m, with N. exists a function u E H supported on [0, T + 1), such that u(t) 0t for all E [T] and
1. Then there
Vulli & Clleillw + C. l0, - 2t-
||u - ull 1. S C" max lellww
with C, C' depending only on m and given explicitly the proof.
The theorem demonstrates that the continuous path-length be bound by the usual discrete path-length under mild assumptions on the RKHS that are satisfied by the translation invariant kernel with spectral density Q chosen according to Theorem immediately see that the RKHS characterized by the kernel in Proposition 2 satisfies the con- dition of the theorem, and has RKHS norm satisfying ||ul| = O( I|u - V2ullz.>) = Õ(M² + M Ei= ---- -4 where M = max, [|u]|
Based on this observation, we
Optimal Path-length Dependencies. Applying our reduction Proposition with the transla- tion invariant kernel characterized by Proposition 2, followed by Theorem 4 to bound ||Vull O(VM² + Pr) immediately yields the following dynamic regret guarantee for OLO.
Theorem 5. Let G > 0 and apply the algorithum characterized in Proposition with the kernel with spectral density described by Proposition 2. Then for any T > 3, and any sequence 91..... 9r satisfying l1gel w S G and sequence u1....,Ur
W C R.d, the dynamic regret is bounded as
Ur
RT(u WT) = (V
where M max, |luell and Pr ET² llue uc-l
As observed in Section 4, the kernel that produces this result is horizon independent, so the algorithm described above requires no prior knowledge of T. This is in fact the first dynamic regret algorithm we are aware of that achieves the optimal VPr dependence in the absence of prior knowledge of without resorting to a doubling trick. Likewise, in Appendix C.3 we show that these guarantees extend immediately to scale-free guarantees using the gradient-clipping argument of [12]. These are the first scale-free dynamic regret guarantees that we are aware of that achieve the optimal vPr dependencies.
8

---

Curved Losses
An advantage of our reduction over the dynamic-to-static reduction of Jacobsen and Orabona [26] is that, by preserving the curvature of the losses, our reduction allows us to apply (quasiseccnd-orddr methods like Online Newton Step (ONS) [20].
Exp-concave Losses The following proposition shows that exp-concave losses retain the crucial property required to apply ONS under our reduction (proof in Appendix F).
Proposition 3. Let le W + R. be B-exp-concave function, let H be an RKHS with feature map ((t) E H. and define Ee (W) = L. (()W)(t) for W E L(H,W). Then for any X.Y E L(H,W).
3 (V((), X Y) HS
((x) - &Y0 & (V((x),X Y) HS 2
Note that this is precisely the curvature assumption that is required run Kernliized ONS (KONS) [7, 8J. Hence, applying our reduction Theorem 1 with KONS to the loss sequence li..... er leads immediately to the following dynamic regret guarantee, adapted from Calandriello et al. [8, Theorem 1].
Theorem 6. Let Ei....,eT lr be a sequence of 3-exp-concave losses. For any sequence U1...., WT W and U E L(H, W) satisfying = for all t. Algorithm applied with KONS guarantees
In (2,32 kmax (amx
Rr(u1,..... ..p ur) = o | + dea 330kkmax
B
where G 2 [V)) all w W, kimax max; t(t,t), dott(A) Tr (KT(KT + 1)) and Kr (V:), (lz(w,)) k(i, k(i, E RTT
In the previous section, we observed a direct trade-off between the complexity of the comparator- measured in terms of = term measuring the complexity of the RKHS, max, k(t, l). Here we again see trade-off in measures of complexity, but now the complexity of the RKHS is charac- terized by the effective dimension dett (A). Loosely speaking, the effective dimension represents the number of "non-new negligabee directions" spanned by the features @(1), ((T), characterized by the number of eigenvectors of Kr associated with non-negligable eigenvalues relative to A.
Strongly-convex Losses Interestingly, for strongly-convex losses it can be shown that an analo- gous curvature condition to Proposition holds under our reduction as well, leading to an analogous result to Theorem 6. Indeed, the main difference is that in the strongly-conve setting, one uses the feature covariance XI E (t)) & @(t) to define weighted norm while KONS the covariance matrix of the product kernel associated with features o(t) = gr @ @(). Applying a similar argument then leads to guarantee which is analogous to Theorem 6 (see Appendix F.1 for more details).
Online Linear Regression Similar results also apply the context of online regression. In that setting, at the start of round / the learner first observes context H, E T, then predicts a Dt E R. and incurs a loss & (7) 2 (Ve 2 this setting, our reduction recovers kernelized online regression, by letting De
((z))) where f L(H, I) and o(x,) E H is the feature map associated with H. Applying the Kernelized Vovk-Azoury- Warmuth forecaster [2, 27, 50] guarantees regret of the same form as above. The result follows from Jézéquel et al. [27, Proposition and Proposition 2].
Proposition 4. Let W = R and for all let (((ū) = ( - .) Then for any sequence (I1, y1), .... (IT, yT) T W and any benchmark sequence Ú1..... dr in R and u H. sat-
isfying V. = (u, o(x+)) for all t, the Kernelized VAW Forecaster guarantees
eT eTk2
Σ (e,(0))) - (.())) A A1ll1 + dott (A)y log (e+
mmax
where kmax = max; k(t,t) t) and y max; v²-
is known that the dependence on der( (A) for kernel ridge regression is optimal [30], demonstrating that these trade-offs are unimprovable in the context of dynamic regret well.

---

In each of the results above, the main trade-off is between the comparator norm X A|ull effective dimension (A). As an illustrative example. the following shows that the linear spline kernel can achieve non-trivial squared path-length guarantees, which were recently shown to be unattainable in the OLO setting [26].
H and the
Example 3. The linear spline kernel 1=), min(s, 1) has well-known RKHS norm of | [V P- La = [ dt. Moreover, in Appendix F.2 we show that we can bound [| S O(V E. Ut - -i- == Cr and that the effective dimension is dest (A) = ((T/VX) (Theorems 8 which matches
and 9 respectively). Optimally tuning X leads to Bor(j..... 30 O the minimax optimal rate for forecasting in the class of discrete Sobolev sequences of bounded variation [3, 44j. Note that can be tnnd without date-depnndent prior knowledge using mixture- of-experts and simple clipping argument [25, 341.
In the special case of the 1-dimensional squared loss (v) [v= 2) it is possible to achieve R = Ö(r1/s where CT = E. - -t-11 is the (unsquared) path-length of the benchmark predictions, and this bound is minimax optimal among the class of discrete TV-bounded sequences, which is more general than the Sobolev class in the example above [3, 54]. Designing a kernel with suitable effective dimension achieve this trade-off has proven non-trivial and is left as a direction for future work.
Directional Adaptivity
An exciting benefit of reducing to static regret is that we can leverage more "exotic" static regret guarantees to uncover new and interesting trade-offs in dynamic regret, essentially for free. For example, in recent years there has been an interest in algorithms which adapt to the directional covariance between the comparator and the losses [13, 15, 16, 37, 49], to guarantee
RT RT(u) (w) -0(V di (e,, w//x)
These bounds recover the usual Ö( |ul|l v V [1.)lbr..) bounds in the worst case, but could be significantly smaller if the comparator tends to be orthogonal the losses. Passing from dynamic regret to static regret via Theorem 1, the following proposition shows that guarantees of this form translate into dynamic regret guarantees which naturally decouple the comparator variability || I
from the a per-round directional variance penalty Eim (9t. ue/w The full statement and proof of this result can be found Appendix G.
Proposition 5. Let f.....,ey Ey be an arbitrary sequence of G-Lipschitz convex loss functions over W. There exists an algorithm such that for any sequence of u1,..., wr in W and U E L(H,W) satisfying u, = Ut( for all t, the dynamic regret R Rr((u,,..,, uT) is bounded by
LT) |IUSSS + Σt= (on w/// In (e edmax (KT) ö( ((Lndar(A) + V daa [
where ge E (wr)..) L G² max, k(l,t), KT (1 hilt, s))eE and dett (A) Tr(KT(AI (K) 1))
7 Discussion
In this paper we developed a general reduction from dynamic regret to static regret based on em- bedding the comparator sequence as function in RKHS. We showed that the optimal vPr path-length dependence of can be obtained via a carefully designed translation-invarian kernel. We also developed new scale-free and direetionalll-adaptiv guarantees for online linear optimization and ||ul| + dea (A) In T bounds for losses with curvature.
There are many promising directions for future work. As noted in Section 4, if implemented naively, the algorithms described here could be prohibitively expensive to run in practice. Future work should study how to best leverage kernel approximation techniques or sparse dictionary methods to achieve the standard (d T) per-round computation without ruining the desired regret bounds. We also anticipate many interesting directions for future work by investigating the rich intersections between online learning, kernel methods, and signal processing that our reduction brings to light.
10

---

Acknowledgments and Disclosure of Funding
AJ and NCB acknowledge the financial support from the FAIR project, funded by the NextGener- ationEU program within the ENRR-PE-AL scheme (M4C2, investment 1.3, line on Artificial Intel- ligence), the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society), funded by the NexIGeneraaiinEUU program within the PNRR scheme (M4C2, investment 1.1), the EU Horizon CLA-202--HUMAN-D research and innovation action under grant agreement 101 120237, project ELIAS (European Lighthouse of AI for Sustainability), and the One Health Action Hub, University Task Force for the resilience of territorial ecosystems, funded by Università degli Studi di Milano (PSR 202I-GSA-Linca 6). AR acknowledges support from the European Research Council (grant REAL 947908).
References
the [1] Nachman Aronszajn. Theory of reproducing kernels. Transactions the American mathemat- ical society, 1950.
[2] K. S. Azoury and M. K. Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine Learning, 2001.
[3] Dheeraj Baby and Yu-Xiang Wang. Online forecasting of saaa-variation-oundeee sequences. In Advances Neural Information Processing Systems, 2019.
[4] Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning- In Conference on Learning Theory. PMLR, 2021.
[5] Dheeraj Baby and Yu-Xiang Wang. Second order path variationals in non-stationary online learning. In Francisco Ruiz, Jennifer Dy, and Jan-Willens van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics. PMLR, 2023.
[6] Alain Berlinet and Christine Thomas Agnan. Reproducing kernel Hilbert spaces in probability and statistics. Springer Science & Business Media, 2011.
[7] Daniele Calandriello, Alessandro Lazaric, and Michal Valko. Efficient second-order online kernel learning with adaptive embedding. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wal- lach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems. Curran Associates, Inc., 2017.
[8] Danicle Calandriello, Alessandro Lazaric, and Michal Valko. Second-orde kernel online con- optimization with adaptive sketching. In Doina Precup and Yee Whye Teh, editors, Pro- ceedings of the 34th International Conference on Machine Learning. PMLR, 2017.
[9] Nicolò Campolongo and Francesco Orabona. A closer look at temporal variability in dynamic online learning, arXiv preprint arXiv:2 (at.::20022676666 2021.
[10] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge univer- sity press, 2006.
[11] Nicolò Cesa-Bianch Bianchi and Francesco Orabona. Online learning algorithms. Annual Review of Statistics and Its Application, 2021.
[12] Ashok Cutkosky. Artificial constraints and hints for unbounded online learning. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learn- ing Theory. PMLR, 2019.
[13] Ashok Cutkosky. Better full-matrix regret via parameter-free online learning. Advances in Neural Information Processing Systems, 2020.
[14] Ashok Cutkosky. Parameter-free, dynamic, and strongly-adaptive online learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning. PMLR, 2020.
[15] Ashok Cutkosky and Zakaria Mhammedi. Fully unconstrained online learning. The Thirty- eighth Annual Conference Neural Information Processing Systems, 2024.
[16] 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, edi- tors, Proceedings of the 31st Conference On Learning Theory. PMLR, 2018.
11

---

[17] CARLOS M Da Fonseca and VICTOR Kowalenko. Eigenpairs of a family of tridiagonal matrices: three decades later. Acta Mathematica Hungarica. 2020.
[18) Geoffrey J. Gordon. Regret bounds for prediction problems. In Proc. of the twelfth annual conference on Computational learning theory (COLT), 1999.
[19] Eric C. Hall and Rebecca M. Willett. Online convex optimization in dynamic environments. IEEE Journal of Selected Topics in Signal Processing, 2015.
[20] E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimiza- tion. Machine Learning. 2007.
[21] Mark Herbster and Manfred K Warmuth. Tracking the best regressor. In Proceedings of the eleventh annual conference on Computational learning theory, 1998.
[22] Mark Herbster and Manfred K Warmuth. Tracking the best linear predictor. Journal of Machine Learning Research, 2001.
[23] 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. PMLR, 2022.
[24] Andrew Jacobsen and Ashok Cutkosky. Unconstrained online learning with unbounded losses. In International Conference Machine Learning (ICML). PMLR, 2023.
[25] Andrew Jacobsen and Ashok Cutkosky. Online linear regression in dynamic environments via discounting. In International Conference on Machine Learning (ICML). PMLR, 2024.
[26] Andrew Jacobsen and Francesco Orabona. An equivalence between static and dynamic regret minimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[27] Rémi Jézéquel, Pierre Gaillard, and Alessandro Rudi. Efficient online learning with kernels for adversarial large scale problems. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
[28]
David W Kammler. A first course in Fourier analysis. Cambridge University Press, 2007.
[29]
Wouter M Koolen, Alan Malek, Peter L Bartlett, and Yasin Abbasi- Yadkori. Minimax time series prediction. In Advances in Neural Information Processing Systems, 2015.
[30] Tor Lattimore. A lower bound for linear and kemel regression with adaptive covariates. In The Thirly Sixth Annual Conference Learning Theory. PMLR, 2023.
[31] Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan A. K. Suykens. Random features for kernel approximation: A survey on algorithms, theory, and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[32] Laszlo Losonczi. Eigenvalues and eigenvectors of some tridiagonal matrices. Acta Mathemat- ica Hungarica, 1992.
[33] 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. PMLR, 2022.
[34] Jack J. Mayo, Hedi Hadiji, and Tim van Erven. Scale-free unconstrained online learning for curved losses. In Proceedings of Thirty Fifth Conference on Learning Theory, 2022.
[35] Brendan Memahan and Matthew Streeter. No-regret algorithms for unconstrained online con- vex optimization.
F. Pereira, C. J. C. Burges, Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems. Curran Associates, Inc., 2012.
[36] H. Brendan McMahan and Francesco Orabona. Unconstrained online linear learning in Hilbert spaces: Minimax algorithms and normal approximations. In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory. PMLR, 2014.
[37] Zakaria Mhammedi and Wouter M. Koolen. Lipschitz and comparator-norm adaptivity in online learning. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference Learning Theory. PMLR, 2020.
[38] Frank WJ Olver. NIST handbook of mathematical functions. Cambridge university press, 2010.
12

---

[39] Francesco Orabona.
A modern introduction to
online learning.
arXiv preprint
drXiv:1912.13213. 2019.
[40] Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. In Pro- ceedings of the 30th International Conference on Neural Information Processing Systems. Cur- Associates Inc., 2016.
[41] Francesco Orabona and Dávid Pál. Parameter- free stochastic optimization of variationally coherent functions. arXiv preprint 2XXi:22102.002366 2021.
[42] Vern Paulsen and Mrinal Raghupathi. An introduction to the theory of reproducing kernel Hilbert spaces. Cambridge university press, 2016.
[43] DE Rutherford. Some continuant determinants arising in physics and chemistry. Proceedings of the Royal Society of Edinburgh Section A: Mathematics, 1948.
[44] Veeranjaneyulu Sadhanala, Yu-Xiang Wang, and Ryan J Tibshirani. Total variation classes beyond 1d: Minimax rates, and the limitations of linear smoothers. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems. Curran Associates, Inc., 2016.
[45] Bernhard Schölkopf and Alexander Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
[46] Elias M Stein and Guido Weiss. Introduction to Fourier analysis on Euclidean spaces. Prince- ton university press, 1971.
[47] Shiliang Sun, Jing Zhao, and Jiang Zhu. A review of Nyström methods for large-scale machine learning. Information Fusion, 2015.
[48] Ernest Oliver Tuck. On positivity of fourier transforms. Bulletin of the Australian Mathemati- cal Society, 2006.
[49] T. van Erven and W. M. Koolen. MetaGrad: Multiple learning rates in online learning. In
D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and Garnett, editors, Advances Neural Information Processing Systems 29, Curran Associates, Inc., 2016.
[50] V. Vovk. Competitive on-line statistics. International Statistical Review, 2001.
[51] Holger Wendland. Scattered data approximation. Cambridge university press, 2004.
[52] Tianbao Yang. Lijun Zhang. Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning. PMLR, 2016.
[53] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environ- ments. In Proceedings the 32nd International Conference on Neural Information Processing Systems, 2018
[54] Yu-Jie Zhang, Peng Zhao, and Masashi Sugiyama. Non-stationary online learning for curved losses: Improved dynamic regret via mixability, 2025.
[55] Zhiyu Zhang, Ashok Cutkosky, and Yannis Paschalidis. Unconstrained dynamic regret via sparse coding. Advances Neural Information Processing Systems, 2024.
[56) Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems. Curran Associates, Inc., 2020.
[57] Peng Zhao, Yan-Feng Xie, Lijun Zhang, and Zhi-Hua Zhou. Efficient methods for non- stationary online learning. In Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural information Processing Systems. Curran Associates, Inc., 2022.
[58] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and con-stationarity: Problem-dependdnt dynamic regret for online convex optimization. Journal of Machine Learn- ing Research, 2024.
[59] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), 2003.
13

---

A Additional Functional Analysis Background
In this section we briefly recall some additional definitions and background from functional analysis, which will be useful for understanding the proofs of our results but were not relevant for the main text.
Additional Notations. The dual space of a normed space H is the space of bounded linear func- tionals 7- [LH, R), and the associated norm the dual norm llll| > g() for any
E H" An operator T H + W is Hilbert-Schmidi if for any orthonormal basis {4,}, of H we have [T 2 HS == |hh by < co. The space L(H., W) is itself Hilbert space with inner product (A, B) HS = E; (Ah;, Bhi)
A Brief Review of Reproducing Kernel Hilbert Spaces. A linear functional ip L(H. R) is bounded if there exists a constant M such that [(p(z)] & M || for all E H. A reproducing kernel Hilbert space (RKHS) is Hilbert space H of functions h : X R for which the evaluation functional 8z + h(x) is bounded for all x E X. For any such space, Riesz representation theorem tells that for any x X there is unique h₂ E H such that (h) (h, kz) x for all E H. The function k(x, x²) = (x') is called the reproducing kernel associated with H. The reproducing kernel is often expressed in terms of the feature map x(x) K2 H as k(x,,²) (ő(z), (()))H
We will often be interested in functions taking values in W RR. In this case the preceding discussion can be extended in straightforward way by considering coordinate-wis, extension. In particular, observe that in this setting an operator W E L(H, W) can be represented as a tuple (W...... Wa) such that W; E L(H, IR) HC for each i [d]. Riesz representation theorem then tells us that there is a W/ E H such that (h) = (w, h1) for any E H. so using the reproducing property we have (e(())) tuple (W1.... ... Hd and we write
(w,, p(t)) x (t).). Hence, each W L(H, W) is identified by
w=))) ((w1,)(t))z (())) ..... (wa, (()))x) (Wi(6(t)), .... Wa(o(t)) Wo(() W.
Note the that space L(H, W) is itself a Hilbert space when equipped with the Hilbert-Schmidt norm, which in the coordinate-wise extension above can be expressed as || I = || =
|| 2. This can be seen by definition of the Hilbert-Schmidt norm: let {h. J be an orthonor- mal basis of H. then
|
[Whhllw
Σ [I)
..... Wa(h:))l
Σ 11w poonn, ho)) .... (wa, hi) w
{wj, hi)
Σ
Σ
(wo hi)
f=1
5=1
|| 11 == |1
where the last line uses Parseval's identity.
B Recovering Jacobsen and Orabona [26]
In this section demonstrate that the reduction in Jacobsen and Orabona [26] is equivalent to the special case our framework. Note that we assume linear losses in this section because the reduction of Jacobsen and Orabona [26] is only defined for linear losses (or by linearizing the losses & via convexity).
Let e E R be the 1th standard basis vector and consider Algorithm I with H = RT, (A, (A, Tr (A T B), kernel feature map (tt) e, E R.T. and linear losses W + (G,, W) for G. =
14

---

&e gie," E B Then for any sequence ui...., in R let U = (u) ur) E BaXT
and observe that we can write u, U (t). Moreover,
T
T
(e,, uz) =
Σ Ub(t))
= Σ Tr (o(t)a
Σ Tr ((a)(())) U)
T
(9.0(1))
HS Σ (G, U)
Similarly, suppose A is an online learning algorithm and let We (w(())
w RdxT
(1) Then
denote its output round t. Suppose round we play wi Wio(t) wi
T
(e. wp)
Lg Wio(t)) 'rr (dig) Tw,) (9r0(1)), Wi)
Σ (Gr, Wi)
Thus,
T Rr(u1..... WT) Σ (g w. wn) Σ (G W. U) RT)
To see why this is precisely equivalent to the reduction of Jacobsen and Orabona [26], observe that their reduction is simply phrased in terms of the "flattened" versions of each of the above quantities, and can be interpreted as working in the dimessiimennnional RKHS over H. = Rd with (a, y) # (z, y) being the canonical inner product FT" In particular, they instead define
w
ū = vec (U)
=
:
E R dT
Wr = vec (W₂)
=
E BRT
Jt = vec (G²)
= 9t
E
R
WT
wi (T)
and run an algorithm defined on H. = RdT against the losses T.. As shown in their Proposition 1, under this setup it holds that 2i (gt, uz) follows that
Eim (T. W. ū) from which it immediately
Theorem
T
Ry(u1.... wr)
Gr. Wt U'as = (U)
7 (et wt ū) Ry (7).
Jucobsen and Orabona [26, Proposition 1]
15

---

C Proofs for Section (Linear Losses)
C.1 Proof of Theorem
Theorem 2. Let A be an online learning algorithm defined on Hilbert space V. Suppose that for any sequence of convex loss functions hi,..., hr on V. A obtains a bound on the static regret Ii,,,ll,V,,a,,aaa
of the form (U) I Br (]]V I| (Wi)llv........ ..llv..... (Whr(W)))lv) for any comparator U E
and some function Br R T+1 + I, where Vha(W) E (W; for all t. If we apply A in 20
y = L)H,W) with I1-lly = Il-llss then for any sequence uI:-.,, in W and U E ((H,W) satisfying un = (@(t))oo all t. Algorithm 1 with A guarantees
Rr(u,,.... wr) - Br (II (ns. 1lil v (),, ((L,)))..,lloooww///A..... ((rrll///(,TTT))
where Or E (w)(wr) for all t, and (((;)) is the reproducing kemel associated to the space H.
Proof. We note that L(H, W) a separable Hilbert space for separable H. and W. Moreover, & is differentiable, with derivative
V&((W- V&, @ (()) L(H, W),
where @ is the tensor product. Then applying algorithm A to the loss sequence (Et),, we obtain
Ry(U)) s ((IUillc(.,w (w;) @()))ll().))) (wT) & ((T))l The proof is concluded by noting that (r(u,..... ur) = Ry (U) by Theorem I, and that (wx) (())) [V (l)(()))
since w E L(U, y) a rank one operator and so /ll = ||l||//|//| for any u, u E and U, V Hilbert spaces. Finally, note that (()(t) = (o(t), d(t) = k(t,t).
Remark 1. Note that the result of Theorem applies more generally to algorithms that use dual- weighted-norm pairs (II-II I1- since this amounts to transforming the decision space W + M M&W, W, the losses G2 + - G,, and preserving the original inner product structure. We expect the theorem should also generalize to arbitrary dual-norm pairs on W, but this will require some additional care to interpret the norm [1-llw-
C.2 Concrete Example of Proposition
Algorithm Kernelized Instance of Jacobsen and Cutkosky [23, Algorithm 4]
Input: Lipschitz bound G > 199 wl for all t, Value >> 0
Initialize: w1 0, Go G max; / /k(t, t). V1
4G
S
=0
Define: (SS
VV (V/G)))
cGo
exp
36V
g2
1
if
Go
VV (V/G()))
eGo
exp
3Gg
6V Go
1
otherwise
for 1: do
Play Wc, receive subgradient dt
Set V = Vi + llgellew &(t, t)
Set S2 S + k(t, t) Ilgellw
+ - k(s, (dt.ge)w
Ei k(s, (S V(-1)
Update Wi+11
Set1
end
There are many examples of algorithms which would produce the static regret guarantee stated in Proposition this section, we briefly provide an example which attains the result of the stated form, and provide the full regret guarantee and update in our framework.
16

---

Let us consider the algorithm characterized by Jacobsen and Cutkosky [23, Theorem 1] in an un- constrained setting. Their algorithm can be understood as particular instance of FTRL, and so we can develop its kernelized version using the same reasoning as Example 1. Indeed, applying their algorithm in the space [(H, W) with inner product (., 1) against losses G. = 9r 6 ((t) leads to updates of the form
W E.= Go
Eg.,
Vo-1 V
v
E'= G2
HH
HS
where V 4G0 + E.= ||G and (S, V) defined Algorithm Moreover, we have Ei (g). 92) k(i, j) via Lemma and Lemma 9 respectively, and in the context of reduction Algorithm the updates w W1+1Ø(1 + 1)
V4+1 4G/ + E.=1 || k(s, and E G. HS
Σ1 - G)
+ 1)
ΣG,,
Σ
G2
.V-1
E.= Go HS
HH
Es= ki(8, l)ge
v
k(i,5) (gi. Iilws 4G +
k(s, 8) 11
E k(i, (ge, gidw
leading to the procedure described Algorithm 2. Notice that, as mentioned in Section 4, this naive implementation requires (t)) time and memory to update on round due to having to re-weight the sum E'=1 ksss, t)g, and compute Σ k(s, (gt, (x) in practice would ideally imple- ment additional measures to reduce the complexity, such as implementing Nystrom projections or choosing suitably sparse kernel.
Now applying Algorithm 2 with Theorem 2, we immediately get the following regret guarantee from Jacobsen and Cutkosky [23, Theorem 1].
Proposition Let f,....,yy be G-Lipschitz convex loss functions and let gr E de,(we) for all For any uI, , ur in W and E L(H, satisfying = for all I, Algorithm 2 guarantees
uT) = (U)
< 4Goe + 6 |U|| HS max {
(irss In
|Ill|S + +1) aT+1
1l aT+1
+ +1)}
Go In
where Vr+1 4G8 + EL 19 llw k(t, t) and cor+1
cGo
Vr log" (Vr41/
C.3
Scale-free Guarantees
Now that we have seen how to obtain the optimal path-length dependencies on Lipschitz losses, we can extend these guarantees to be scale-free by simply changing the base algorithm. In particular, there are algorithms which are adaptive to both the comparator norm and the effective Lipschitz constant, L = max V (w:))ll Algorithms which scale with Lr rather than given upper bound G 2 LT are referred to as scale-free. We first consider the setting in which the domain is constrained W = {w E Rd [wlll D).
Proposition 7. There exists an algorithm which guarantees that for any sequence wi...., ur in W = { Rdd wwll $ D).
RT(u1..... uT) Ō [Tr(nnxx lluellw + D) + |1 12 Σ leellw k(t,
where L, max, 1|9. llw=
'More generally, this assumption amounts to assuming prior knowledge on a bound D 2 ||uellyo for all which the learner can leverage by projecting to the same set, regardless of any boundedness of the underlying problem's domain.
17

---

The result follows by constraining lwwllw S D and applying the gradient-clipingg argument of Cutkosky [12].' Indeed, if we've constrained our iterates to satisfy || S D, then we can replace the gradients 9r the the clipped gradients 9r 9t min max
j to get
a wlw
= O.. ue) w
(g Dc. wi wew
S (r wT) max 119a llw (D + max [|uellw)
following the same telescoping argument as Cutkosky [12]. With this in hand, we can sim- ply apply reduction Algorithm 1 with the losses G. gr @ ø(t), which now have an priori bound on at the start of round t: | HS I max 1laellw vk(t,) L. S Lr- Hence, even without prior knowledge of a G 2 ll we can obtain Rr(w,,.... wr) S
δ | |Iulls V max, Il ktt, t) + Ei= 1 k(t,t))
To see why this is difficult using existing techniques, note that nearly all existing algorithms which achieve the optimal vPr dependence do so by designing an algorithm which guarantees dynamic regret of the form
RT(WI,,... WT) = Ō Pr
+
from which GVPrT regret is obtained by tuning 17. The tuning step is done by run- ning several instances of the base algorithm in parallel for each 1) in some set S and combining the outputs-typically using a mixture-of-expprts algorithm like Hedge. Note however that the set S requires prior knowledge of the Lipschitz con- stant G. There is no straightforward way to adapt to this argument without resorting to unsatisfying doubling strategies, which are well-known perform poorly in practice. Instead, using our frame- work we avoid these issues entirely by simply applying a scale-free static regret guarantee to get the LT | HS vT dependence, and then designing kernel which ensures | /MPr.
/2//GTT
More generally, when the domain W is not uniformly bounded, it is still possible achieve scale-free bound at the expense of an Ly max, [[wllw penalty, again using the same argument as [12]. One simply starts by replacing the comparator sequence Uis..., uT with a new one satisfying
u. Iw, ue where W:
W ::Ilwll S v - 11a.llww
Then one can show that
T
Rr(u,.... uT)
Σ
(ge, Wi uow = Σ (ge, we
ūel + + (gt. ūr uew
s 0 (ui...... ūT) + max
||ue lluali))
2
Applying the same clipping argument as above and observing that Pr. = Ee 11 Tr -e- 5 O(P + max; [[ell we get the following result.
Proposition 8. There exists an algorithm such that for any u1,..., ur in W C Rdd,
Rr(ui,.... WT) Ō ( Lr max Ilueli 11
T
Σ
11 k(t,
where LT = max, [[gellw / ttt
'Note that constraining the final outputs We is trright-forward in our framework; one can simply apply standard cooomstriined---coontrrriii reduction in W [14, 16] prior applying our dynamic-to-statie reduc- tion.
'The exception being Zhang et al. [55], which uses similar high-dimenseen dinensimoni embedding as [26]. but neither works obtain the optimal vPr while being scale-free.
18

---

D Intuitions on the Spectral Density Q(w)
In this section provide some additional high-level intuitions that motivate the choice of ((w) in Proposition 2.
Recall that we would like to choose ((w) = 1/ww], since this choice yields continuous-time analogue of the PT dependence that want achieve: ||u] [ s max, [a(() || [/ The key
issue is that this choice of ((w)) is not integrable, diverging as w -> 0 and w + oc. We fix these
issues by adding small amount of additional regularization, setting
(ww) Ro(w) Roo
W
where Roo (w) R 1/(1 |=/2) is a function that ensures integrability in the asymptotic regime, and Ro(w) R 1/ log( + ///\///) logg(
(log(1 + 1//\//l) ensures that Q is well-behaved
near zero. It clear that Roo (w) ensures integrability in the asymptotic regime since when w is large we have Q(w) 2 (w)(w) near zero Roo (w) se 1 and we have
s 1/|w/? which is integrable away from zero. On the other hand,
(w( |
Q(w)=
|w) log([w) - 1/2) log" 2 log( ( 11/2)
which after change of variables
= log (w 1/22 integrates near zero as 1 [ (()) 2 /// Q(w)do Hoacvo (log(()) dt 0(1)
(1)
for an appropriately chosen c.
E Proofs for Section 4.1 (Controlling the Trade-offs Induced by H)
E.1 Proof of Theorem 3
Theorem 3. Let Q R + R. be integrable strictly positive even function on R \ {0} and such that R(x)= == 2 (ar(1 + (t//mm] (2m (m))(xx)) is also integrable for some m E N, m 2 1. Let k be defined in terms of Q as in Eq. (3). Then I is a translation invariant universal kernel with k(t,,)) S [|Q]l for all t E RR. The RKHS H associated to k contains the space of finitely supported functions with bounded derivatives up order 2m, and moreover, for any T and any 2m-times differentiable function f that is supported on [0, T + II.
1f S c(T) M If - 2 fllt=,
where e(T) = =[[ [P[R]|L( (1--11444) R monotonically decreasing on (0, oo), then,
c(T) S inf 2m (T + 1)² (- R(x)adx + R(x) dx
VT >
a>o
Proof. Consider function that is supported on [0, r] for some O. To bound the norm above
in terms of the L norm we use the fact that for any u, U. w E (B) @ L L'RRR) we have F[V*u] (2mi)*a, for & E N, Flu F[u+w]= = We, where * is the convolution operator, and that by the Plancherel theorem we have Sa ((w) = fg u())e(()dt and so, in particular, Sa
fa u()((v A (f)dt. Moreover, note that, by construction R is an integrable real odd function, so its Fourier transform R is an odd purely imaginary function. So, we have
| / 12 ((w)
wf(ww
2m
(1+
B(w) R(w)dw
2xi
(2m))2m
vs(-t) (V5 - (2m * (t)
V/(-1) ((S - 2m f) * (1)dl
< |V/I|n|1( - f2m + R (-)00)))))
19

---

where in the last two steps we used the fact that f is bounded in [0, and the Hölder inequality. Since also T is supported on r], we have
- ~2m R ([-100))))))))))))))))))))))))))
lf(t) 2m (am f(t)] - t)|dt
sup - J
V 2m fll ((
(1-,,)))
The last step is finding bound that is easy to compute for c(T) = || We start noting that since R is odd
R((1) = / Radeeemint da 2i S R(x) sin (2niir//)d
and, in particular also R is an odd function. The characterization we propose for c(T) is a direct consequence of the fact that the sine transform of R is non-negative (also known Polya criterion, which we recall in Lemma and is applicable since R is positive and decreasing on (0, oo)). Now, by expanding the definition of R and using the non-negativity of the sine transform, we have
S R(t)ldt 2 /'" |R(t)ddt =
R(x) sin sin(2rrttda dt 1
2 f-' Io R(x) sin(2nxt)drdtt Lod R(x) (f. sin(2nzzt)dt dx
sin (TTx)²
2 R(x)
dr.
To conclude, let a > O, since sin(2)] S min(|2], 1) for any E R
sin )T
dx ! R(x)
sin? (TTØ)
sin 2 (TTzz)
R(x)
dx
R(x)
dx m
wE
क Ioa R(x)xdx + 1 R(x) dx.
a The stated result then follows by choosing = T T +
E.2 Proof of Theorem 4
Before proving Theorem 4 need auxiliary results
Lemma 1. Given m E with m 2 1 and T > O there exists a function by that is 2m-times differentiable and that is identically equal to 0 on 10, and that identically equal to on the interval TY. Moreover, for any 2m-times differentiable function f, with derivatives in (P(S) for p [1, oc] and interval S C IR, we have
(8(2m + +3/2))4+1
(fbr))))r))))) S
22/23/2
max OShSk
Proof. Consider the function
B 21 + 2m)
(1 4x 2)
VTl(1 + 2m))
where I the gamma function. Then B is supported on 1-1/2,1/2), integrates 1, and is 2m
times differentiable everywhere. Its Fourier transform (see [46], Thm. 4.15) is
2
2m+112
((w) T(3/2 + 222m (T/w])
T |||
where Jn is the Bessel function of order v [46]. Since J, is analytic on [0. 00) for v > and
Jz( = ([2) when |z| + O and also Jz(z) = (221122 for 2 + oc, then in L O L and
analytic. We build by follows
(r((t) = [/ B(x 1/2) B(x - T 1/2)dr.
20

---

Btt1
Bit {)
8(c
by(()
/ [xxx
B(x -oxx---
T]dx
2.0
1.75
1.5
1.50
2.25
1.00
-1.0
-0.5
Figure 2: Plots demonstrating the functions used in the construction of (t) for m and = 5. The function (xx) is simple bump function, designed such that fg Bxx)dr = 1, shown on the left. The center demonstrates how we can combine translations of (xx) to get function with two bumps which will eventually cancel when integrated over [0, 1]. leading the function br shown on the right.
This function by construction is 2m-times differentiable everywhere, moreover it is identically equal to 0 on (0, T+) and identically equal to on [0, T". To help with intuitions, we show an example of the functions (xx), B(x )) B(x - T), and br(() for m and T = 5 in Figure 2. The Fourier transform by is
1 B(w)e niu (ww)e-m(111 (1-e e
(w(w) = 2niw
Now we define utt) : f(t)br (t). By construction, u is equal to fr on [1, 2'I since by is identically 1 this interval, let Z = S 10, T 1], we have
| |vuull \V*u|lLo(2)
Σ
4
bt
hm
IP(2)
max oSiSk
|
fll
V
h=0
Now, given the Fourier transform of by.
22m+h-1/2 1/2
brll> s (2 brlll - I 2m)
-2m-h+3/ | 2m 3/24h J2m (T|W)))
Using the fact that [=][ min(2"22 1-13) (see [38], Eq. 10.14.2, 14.4). for any 2 2 0, for any >> 0, we have
J2m- (/2n-// du = 2
(22m+1/((T22))
J2m++12((Tzz) dr 22m+3/2-b
dx +
W -m 33/4h
22m+3/2-2
a
x 22m+1/22 - 1/2
(2m + 1/2) 1/3 x2m+3/2-h dx
2
dx +
222+3/2-hi h| [m -3/2)
2- 122+1/22
2a 2a-(2m (2m-A+1/22)
h2' + 3/2) (2m - h + 1/2) + 1/2)1/3
Optimizing in we obtain
||W 2m 3/2-3/ Jzm 1/2 (2/T//))l 5 2m + 3/22)
2m 1/2
1/2
leading to
22h+2
2(8m 11/2
1Vbbrllee < 2m 22m--+3/2
I(2m 3/2) 2m/ <
n 2m h
21

---

this leads to
max USiSk
|
[()
|
h=0
2(8m + 6)1/2
I+
8m +
+66
| fl)
π 2m+3/2
max 0515k
To conclude, note that
(88m + 6)2/2
8m + 6)* 1
gk+1 - 3/2)
S
π 2m2+3/2
22m+3/2
Lemma 2. Let f be such that its Fourier transform f and its weak derivative Vf are both L?, then
||]) S - (
Proof. For any > O,
Ifll & +
Now by the Hölder inequality we have
[) Ilf 11,)) [1 /aal:///______laao/////////a//a. v2(l)fll(?((0.))
where ((x) is the constant function 1. Similarly,
[[ffll =
|| |atll/////uuaaal/////// httpa//llllllaaaaaooooooo///ooa. 22/e|lfa|
since |1/=|| S. 1/22dr 2/t.. This leads to
[I I /2(Villflla> + 1/Vi(/fallaa).
Optimizing on we obtain,
1f S 21
The first case is concluded by applying the Plancherel theorem for which || = lllÍlz and || = [[F[sæ]][>> and by the fact that F[[(x)=)(w) V((W).
Theorem 4. Let UI....,UT Rd and let H. be the RKHS associated to kernel k contain finitely supported functions with bounded derivatives up to order 2m, with exists a function u E H supported on [0, T + 1], such that u(t) = Ut for all E [T' and
N, > 1. Then there
Vulle Clleillw CE
l1v we-lllw,
||u vamull C' max [eellw-
(
with C, C' depending only on m and given in explicitly the proof.
Proof. We will build follows
(tt) = (t)bbr
where by a m + 1-times differentiable function that supported on [0, T 1 [1, TJ. while f is function that interpolates i.e. f(t) for t E T.). We build as follows. Consider the following function, that is product of two sinc functions
+ 1] and that is equal to
sin(Tx) 2in( π
S(x)
S satisfies S(0) = and S(t) = 0 on f \ {0). Now we can build f as follows
f(t) Σ
St f).
t=
22

---

By construction, for all t E {1..... T the following holds
f(t) = Σ vt C) = Σ
vrói=e =
Vt.
Note that, by construction f is a band-limited function with band [-3/4,3/4] that interpolates the given points.
Step Bounding /
Now we bound pointwise [V)()) with [o(x) - o(x - 1)/. The Fourier
transform f of u is equal to
f(w) = Σ ere 2xitw ((w) g(w))
1=1
8m1 2rlw and where is Fourier Transform of S. Note that S is band-limited, i... S is equal to 0 on R [- 3/4]. In particular.
where g(w) = Ei
Vo e R. B(w) = |ا - 3/4| - |ا 1/4| - w + 1/41 + l +3/4/,
Now passing by the Fourier transform of Vf. we obtain
1 2
M(w) = S(w) w01 (((+w9)) w
F[Vf](w) = -ww [(w) MW),, [(w) == g(w)
1 w2
I :bOtu
Note that (ww) bounded, continuous and supported in 3/4,3/4), since S supported in [-3/4,3/4] and w(l+w") is bounded and analytic such interval. So have T-
= = = F=1 [[w) (L * M) (z),
where * is the convolution operator and M = F- [M L = (D). Now note that
B(w) =- g(w) 1 2ti
T
2midw
T
2 1)w
Σ
1 w
+ wz
u1
1 + w²
t=1
E=1
@2niew
Σ
(ve 12-1) w
+ 11
w2
2=
Since the inverse Fourier transform of 22nw /(1 + w²) >) is e |x-a| for any E R, we have
L(x):= :- F-1 g(w) 1 @2Tii
T
(x) = π
(ve v2-1)e 251/2-4 + viTe 22/2-11
1 w2
2=2
By Young's 's inequality for the convolution, we have that [l// S || 12+ ||l|| for any integrable functions f.g. so our case
|V I + Mll
|| ||
ST|IMi 12 Σ live we- salllle-2n1p 10llee-200-000 20/0-81 11 + n T||M||
||
1| I||le
x- 12
To conclude we have 10 111 = lle-2x #l 1x- 1/T and we need to bound the T norm of M. Note that (ww) admits weak derivative, since it is the product of bounded analytic function on the support and S that admits a weak derivative that is the following
vS(w)= = sign(w - 3/4) sign(w - 1/4) - sign(w + 1/4) + sign(w + +/44).
In particular, we have for every w
w(1 + w2)
M (w)l = ((w)
I 1 (1-3443/4((4)
1 - 2
23

---

VM(w | ( w(ll w
@2irnw + (ww) ① w(1 w²)
22 x 113/43//((4)
dw 22
Using Lemma we can bound || I as follows,
M 2
M
8M
1/2 22 Le
obtaining
T
[Vfle s 22 llw + 2
110 - 12 1t-1ll
(5)
1=
Step 2. Bounding | fll... Let E N and k 2 1. Since (ww) S(w/4) is equal to 1 on [-1,
and it is supported on [-3,3], we have that [(w) Fourier transform of convolutions, we have that for all 1 E R.
[(w)((w) So, by using the properties of the
f(t) F (i)(t) = F (2)(()
(F [2] F [f]) (Z + (t),
where Z(1) = 441) for E IR is the inverse Fourier transform of Z. So we have
|| flL = / [Z * fl 11(V* Z) * fllo= S <| Z |
Now, we have
|
sup tE
Σ
S1 1) S (max
[elllw) sup EE
|S(1 E)|-
(6)
[E(T]
t=1
Since [S(() S 1/(1 + 2(²) for any & E R, we have
T
sup
S(( - 0) S sup
Σ
1 28 S 4.
2(t - 8)2
EER
t=1
EE
LEZ
iEZ
To conclude this section, using Lemma and since FIV = w/ w (/ (2Ti)/
2v2 (2T) I 2
32+h 4
| -
1/2
(x + kb/2) $ 3.
So, for any ls E N (including 0, since we have Eq. (6)
| f1l S | Zl le= S 12 max ||ellll
Step 3. Building by and computing the final norms. Lemma 1 constructs function by that is 2m-times differentiable and that is identically equal to 0 on IR \ (0, + 1) and that is identically equal on [], moreover it proves that for any 2m-times differentiable function that has the derivatives (S)S integrable for some p E [0, oc] and some interval S C R, we have
V (fbr)ller(5) Ck.m OShSk
|| (ll=---000T++)
Define u(t)= == (t) By construction u equal to fr on [0, T] since by is identically 1 on this interval, and so in particular
u(()= (())br(() = f(() ve, wl (I.....)),
+ 1). By applying the result above, together with moreover u(() = (())br(() = 0 for E TR (0, Eq. (7)
- v -= < ||u|| 1 + ull < 12(1 + O2m, max |[elll.
Applying the same lemma, with Eq. (5) we have
[|Vullna S 20 |ell + +21m ΣT 1/2 - 1--llww
This completes the proof.
24

---

E.3 Proof of Lemma 3
Here, we recall a classical result about the positivity of the sine transform of a positive decreasing function (see e.g. [48] Eq. 4).
Lemma 3. Let R be an integrable, positive and strictly decreasing on (0, oo). Then, for any we have
J R(x) sin(2xxl)dz 2 0.
Proof.
Since sin(2 (1/2)) = sin (272) for each = E [j.j + 1/2] and j E N, we have
R(x) sin (in
R(x) (in(2
j=0
20
0
7
sin (2T0)d0
1=0
1 20
1/2
11+ R(( + 1/2 + 0 t
(in(2
2 0,
where the last step is due to the fact that is decreasing, so R((j+((//)))) R(Gj +0)/t+1/21
20 L
for any j E N, 0 E [0, 1/2] and that sin (2x00) 2 0 on the integration interval 0 E [0, 1/2).
E.4 Proof of Proposition 2
Proposition 2. Lel Q: IR- + R. be defined as
1/4 log log
Q(w) = Ww (1 + [w23/422) log(z + (w] log log(= a + -w]-
Then we can apply Theorem 3 with m = 1: the function k defined in terms of Q as in Eq. (3) is translation invariant kernel with k(t, t) S 8 Vt I2; the associated RKHS norm satisfies
1 S è² |V5ll I| v (In(1 + T) In In + +T))
for any I that is 2-times differentiable and supported in [0, T + 1}, where T > 2 and e S (2rr)?.
Proof. Step 1. Characterization of Q. The function Q is even, strictly positive and analytic on \ [0]. To study its integrability define the auxiliary function S: [0, oo) + [0, 20) as
log log π S(z) = 2 log log( ( + 1/2²)
is concave, strictly increasing, on (0, oc) and with S(0) = 0 and lim S(z) = 1/2. So its derivative 5" corresponding to
8/2 log log म
S'(z) (1 + π2*) log( ==)) log" log( + 2-
is positive and strictly decreasing (0, 20) and since 0 < 2m, the function (-)s/2m is concave, and we have (1 + (Iwl/2m) 2m s/2m
> 2 .m (1 + ()) so
L= sup Q(w) = sup WER (1 + (Tw) / 2m 2a/2m
+ T [
211-2 sup
+ π Tl
Bunl mmll 1+e
WEll ((w))
wER 1 + (|w) 2T))
n
(8)
So Q(w)= < ((W)) for any w E and since S' is positive and integrable, then Q is integrable too and we have
| Q(w)dw & 2L l S'(z)dz = 2L( lim S(z) - 5(0) = I..
$2L.
2-450
25

---

To conclude this first step, since Q is integrable it admits a Fourier transform Q and since it is also positive, k(t, E') == Q(t t') for t, t' E R is translation invariant kemel. In particular, ktt,t) Q(0) f2 Qww)dw I L. for any R.
Step 2. Characterization of R and explicit bound for |F[R]|[|[-TT] The second condition to apply Theorem 3, concerns the function R defined as
2x
2m R(x) == x01 + 2mm [2)))
Note that is an odd function, since r odd, while both 1+ (2)) 2mm and ((x) are even. Moreover,
R analytic on \ {0} since ((x) is analytic on the same domain and xx1 (a/ (er22)2mm) is analytic on the whole axis. Expanding the definition of Q in R, we obtain
R(w) = Co log + |س| *) log (log(T + [)]
(1 + (w/2T )am) Roa-s
where = 4T/(s (srg/ssloglig log T). From which we observe that is also positive and strictly decreasing on (0, oo) since, log( + |x]--),, log(log(T + |x)==*))² and 1/ + (w/2x) 2m are strictly
positive and strictly decreasing on (0, oc). So we can apply the bound on | ((]REEE(-- in Theorem 3, obtaining, for any a > 0
c(T) = |1 S 2TT2 1-" R(x)ado + 2 0c R(x) dx.
/.
To bound such integrals, we first simplify R. Let 8,y > O, since the following functions are bounded, non-negative, with a unique critical point that is a maximum, by equating their derivative to zero we obtain
log 2 (log(2)) (2/7)2e-3,
log (2)
1 1+7 2 t1
sup x>
log
(z)
sup 225
23
so we have for any > 0,
Co logg( a 5) log π + x 2)2
R(z)
(1+ + (z/2T) 2m
2m
(log(T (IT + x *)) log 1+7 (n + x
Co( + 99
log'(n + (+++TT=00 x
(T (
(1+ (x/2x)2m)) 2m 2m--
S (1(,7) (I + 53
(1 + (x) 2m 2m
where Ci control the integral of interest by using the bound above. First, we will split it in two regions of interest. For the first term, letting 3 <
3-7 Co 16C
()) S 57-28-1- Now we can
T [-" R(z)adæ s <T>xC((3.7)
T
201= rdr
(1 + (t/2m 2m
/
< <T²7C((8,7)
(T + x ==8) )xdxx
+ Ti B00
-3 T2a²
2
2 - Bs
For the second term, we have
noc R(x))
dx 5 (1(
(T + 5
2m-2 dx 2m
x01 + (x/2 )mm)
Ci (B,7))
T a
x11 + x 2m $ //TT(22))))))) (2m))2m-s)) dx
C1 (B,7))
2n
T
+ a 30
(3,
100
x + a- -8x
dr +
2x 22m 11am+1-90 ( dr
C1
2T
Ci(,,)) 7)
( +
29
log
+
( + aa a--a0 /2m - s).
26

---

So (T) is bounded by
a2²
9
a 38
+ 8 + a log( 2x
2n + -a -8
c(T) - 72 +7
+
a
2
2 - Bs
TT2 117
xT2 g1+ +2m s)
By choosing a = 1 /T, 3 = log(T)) 7 = 1/ (oog(oog()) we have
To = 1, a = T log(T) = e, g = (log(T)) loggglgg))) e, and, since 8 2 1 (by assumption), 2m - 8 = 1 (by definition of m)) and T > 3 (by assumption), we
have
2 2Te 2( e*) log (
2T + e*
(T) - Co log(()) log" (T)
- +
π
π 72m - 8)
2 + 2 + 2(T 22) log((T)
2e
s Co (T) log" log(T)
+
+2
π
s (4m2 log
( (T) log (T).
F Proofs for Section 5 (Curved Losses)
Proposition 3. Let le : W + IP be a B-exp-concave function, let H be an RKHS with feature map ((t) E H. and define & (W) = l.( (()(())) for W E T(H,WW) Then for any X.Y E I(H,W),
3 (vi(x), X -Y) Y)HS
?((X) - (Y) (Vl( Y)
HS
2
Proof. Let (t(t) and y Y (t).. By definition and 8 8-exp-concavity of b,, we have (((x) - (V) 4(x) 4(v) S (V((x), v) (Vl(()), x v/wv
[Ve())) (X Y)o(t) 8 (Vl((z). Y)d(t))
3 (v)(z) @ ((),, - Y)
(VG(z) @ 6(1) (X Y)) -
Observing that vi(x)= = V4((2) 2 (() E W) completes the proof.
F.1 Strongly-convex Losses
In this section we show how to apply our static-to-dynamic reduction in the context of strongly- convex losses. Interestingly. the algorithm ends up being essentially the same as the Kernelized- ONS algorithm of [27], but with weighted norm defined in terms of the feature covariance operator, Σ, AI + 3 E ((s) @ o(s). The following lemma shows how to connect the instantaneous regret on round to the kernelized linear losses Is & Φ(t) and is analogous to Proposition 3.
Proposition 9. Let la W + be a B-strongly-conve function, let H be an RKHS with associated feature map @(t) E H. and define ( ((t)) for W E L(H, W). Then for any X,Y E L(H, W),
B ((X-Y)(di)) & (())), Y'us, where (b(1) 8 6(l) H + H is the operator with action (e(() @ o(()) (0(1), h) (()).
(x) (YY (T(X),x- X HS
Proof. Let x. (t) and y = Yot(). and observe that by f-strong--onvexity of & in W we have
?((X)= - (Y) = 4(x) - (v)) - (V((x),x x - v)w 2 || -
= (V((()) (X - -Y)(()) 2 ((X - -Y)o(t) (X Y)o(t)
(*) (V(((x) @ (1)) Y)us ((X Y)o(t) @ ((), - -Y)
(Vū((t), HS ((X - Y)o(t) @ (()), (X-Y))
where (+) uses Lemma 8 and the last line observes that Vl((2) 8 dtt) v((X).
27

---

Using this result it is straight-forward to see that the usual ONS arguments work in this setting. For instance, by running mirror descent with regularizer the (W)) (WE,, W) Hs where D, + 3 Ex= o(t) @ o(t), we have the following regret guarantee. Theorem 7. (K-ONS for Strongly-convex Losses) Let fi....,
......,, lr be a sequence of 3-strongly convex losses. Lef X >> O and for all I, define En = + === ((s) @ ((s) and [[WIl (WE,, W) for W E L(H, W). Suppose that on each round A updates
W(+1=
arg min (G,,W) + 2 IW W.I... WEL(H.W)
starting from W1 E L(H. W). Then for any u1...., uT in W and U L(H, W) satisfying u(t) = Ut(t) for all t, Algorithm applied with A guarantees
x
G
den (2/8) In (e+ e.dmmx (KT))
Rr("1,- "., ur)
|UT HS
2B
A
where Ky = (()(s), (())))))ee))) and don (A) = Tr (Kr(At+ + Kr))
Proof. Applying Theorem followed by Proposition 9, we have
T
(r = - Rr) =
(w,) -(, (U)
1=1
3 ((W, - ()((() @ (()), W, U)
Ge W.- U')
2
1
UU W441l B (W, - ()(()) ((t)), W. U)HS
|10 wille.
2
T
1
+
(G W₁ - W1+1HHS
|| - Well3. 1eell.
2
T
T +
IIU - Woll._,,
IU W we.1l1.
Σ
llolliw 1
2
2
2 1=1
1=1
G2
|101 HS
+ Σ
||t(t)
2
1=1
G²
deff (2/B) In (e+ eBAmax (KT)
2
U Hs
+
23
where (a) applies the standard bound for online mirror descent, (b) observes that
1/ | - 11z [ [(x - ())(t) e o0)) (x)))
1
2 ((x - Y)E,-1, - Y)
1
||X YI
2
and uses Fenchel- Fenchel-Young inequality to bound
(G,, W. W.4 us 2
1 | w.ll S 1
1
G
11 119 [2
HS
and (c) uses a mild generalization of the usual log- -eg-ddeermmnnatt lemmi (Lemmas 6 and 7) and defines defines Kr ((0(s), ((t))))s.tem))
Note that in the static regret setting, it is possible to avoid the dependence on the comparator norm entirely and pay only the logarithmic penalty-we do not expect such an improvement to be possible here since it would violate known 2(Pr) lower bounds for strongly-convex losses [52].
28

---

F.2 Additional Details for Example 3
In this section we provide some extra details showing that for the RKHS H. associated with kernel k(t, s) = min(s, s, t), we can bound ||ul = Vull2 - ( 1|4 u " (Theorem 8) and datt (A) O(T/VA) (Theorem 9). We begin with the bound on the continuous squared path-lenth | 1.2-
Theorem 8. Let H. be the RKHS associated to the kernel k(s, t) min(s, t) on [0. Then for any 01 Ur E R there exists function u E H such that u(t) Ut for all t E [T] and
||]| = Vull SC
Σ 2=
U
o 1lw + Cllvalliv
with C S 5
Proof. We assume without loss of generality that ER since the result extends immediately to Idd via the coordinate-wise extension mentioned in Section For brevity we will define U2 = 0 for
I & {1,..., T so that we can write Σim /0 - 12 + |m E, 1
Note that the RKHS associated with kernel k(s,t) {I E = f f E L (see, e.g., Example 23 of Berlinet and Thomas-Agnan [6] with m 1). Now suppose we define
min(s,t) is H.
0}, with associated norm Ilfl ||
(=))
u(t) = Σ u,sine(t- -) i)
where sinc(z) = sin( /T.. Then u. and u' are square integrable and u(0) = 0, so u E H. Moreover, the norm associated with H. is [| 1 = [IVf(=)) /| that the constructed function u(l) has |/ull 1 O 1 12-1
fl[ so we need only show
Denote vt)) = >; 0, i) = i and observe that we can write u(t) DT1 T (t). so using the fact that the Fourier transform of sinc is the rectangle function 1 3 (w) I I(w E 1- | H1} (see, e.g., Kammler [28]), have i(w) U sinc(w) ((w) 4. (w). Thus,
(()sinc((t -t) 1) (u*
I / /Ivu(t)Pdtt ( = / (l
via Parseval's identity. We proceed by relating T(w) to the DFT of the difference sequence, Ao(t) = - and then applying Parseval's inequality for sequences to get (\Au(w)) & Ell E 12.
Observe that the DFT of the difference sequence is
Ao(w) = Σ (ve, Vt- 1)e 2rriwt
(1 e- 22Ti Σ Ure - miut = -(1-e - 2Ti
(2-e-22mi)tin (ww))
Thus,
| f 1 w² (9(0(w)))
w2
1/2 11 e nio Au(()) 2 di
Now observe that using the identity 1 cos(x) (z) = 2 sin 2 (x/2) we have
|| - e 2 2 = (1 e -in Tiw )l - )iw) ) = 2 e
-i Riw The
= 2(1 cos(w)) = 4sin 2 (w//2w
29

---

then, using w²/ ssin((w/2) S 5 on
[-2 2'
we have
13 4sin (w/2)
Vullz=
An(w))/dw
5
Au(w) Σiau(t))
-
5
Σ
11 11-1/
4
where the last line applies Parseval's identity for sequences.
Next, the following theorem shows that the effective dimension the linear spline kernel is indeed OTT/VX).
Theorem 9. Let Kr TxT be the matrix with entries [Kr]s min(i, Then
dest (A) = Tr (K+(A+ +T) s TP
2v
Proof. By Lemma 12, the inverse of matrix Kr with entries [Krlk = min(i, is the tri-diagonal matrix of the form
2
1
0
-1 1
2
-1
0
0
-1
-1
K7
0
0
-1
2
0
0
...
The cigenvalues of matrices of this form are well-known [17, 43] and have closed form expres- sion:
2kT
))
\e(K)') = cos
4 ssin
(2T + 1)
2T 11+1
where the second equality uses the identity 1 - cos(I)
= 2 2ii 2ainn((//2) (a/2). Moreover, using the fact
that sin(x) is concave on [0, 7/2) we can bound sin( bounded
2 2x, so the eigenvalues of Ky," can be
22k2
k² T
Xu (K = ssnn
2T +1
π2
(2T + 1)2
Thus, via direct calculation of the effective dimension dett(A) = Tr ((TT(M++T)T* + =
(KGr) we have
(K+))+
Ae(KT)
1
(A)(()
Σ
(Kr)
\/T((KT)
1+ (Mx
T
(a) T v
1 <
dr
I I+ du
1 Xk2
1+ A
Vā
(8)
T
(c)
arctan(r)
x=
2v
where (a) makes change of variables = T/ Xu, (b) uses the fact that f²t 1 du arctan(x)
and (c) uses |aretan(z)] < 7/2 for all z.
30

---

G Proofs for Section 6 (Directional Adaptivity)
In this section provide the full statement and proof of Proposition 5.
Proposition 10. Lel f1,..., by be a sequence of G-Lipschitz losses and for I, gr. E (lr(w)) and define G2 = @ Φ(t) E L(H,W) W), Go = G /mmax, k(t, t) and En = (> + Gb) E G₁ ?
G.. Let (Il-lle (1-,le,)) be dual-norm pair charucterized by ||W]|. VW, E) WHs Let > O, and for all t let V = 4GB + Σ || O4
(V and set vh(W) =
rGp
k [lWll minng1/Go [nle/artl) + nVv] dx.
G., w) + (W) and we play Wi = Wi(()). Then for ui...... ur in W and U L(H, W) satisfying ii = U U for all t,
Suppose on each round we set W. = arg minm
=-( cGo + (ott()) (x+ ||
T
In e+ edmax (KT)
Σ
Wee, uz)²
where Ky (s) k((1,)) 8) sETT, and dest (A) Tr (KT(A+ (XT())+T7)-))
Proof. The result follows as a special case of Theorem 10 with sequence of non-decreasing norms characterized by [W]], = V(W, E,W) and Lipschitz constant Go = G /mxx k(t, t) 2 (W:)) for all t. First, observe that
U)s (g. @ ot). (g., Uo(t)) (ge, weiw
hence from the static regret guarantee of Theorem 10, we get
(T)
eGo + 111111114
T
T
= θ
eGo + V
(A+ (a++G3) I
+ Σ
Go U'Hs
Σ
|GGelle.
t=1
[=1
= cGo + / (a+08) ||U| +
Σ
(ge, uz)
Σ
1=1
1=1
Moreover, observing that
||Grll.. = ( Gr, (Go,
(A+ Gb) I (a+Ca++++ Σ G. Gs
G₁ S
Gts A + Σ
G2 & G.
0.).
have via Lemma 7 that
Σ Gelle, < (A) In (e+ edmax((K))
A
where Kr is the gram matrix with entries [Krks = Ac(Kr) Tr (Kr(AI + kT) Σ [FZ)
(g6. k(,,)) and (e)(() =
Hence the dynamic regret RT(UI,.... WT) RT) can be bound above by
(gts u.)2 In [+ Amax (KT)
δ cGo + V desr(a) GA+ +
A
O
'eer, the tensor product G. @ Gt is the map such that for V E L(H,W), (G. @ G.)(V (G,, Vhus G. E L(H, Note that En is self-adjoint operator.
31

---

G.1 Directional Adaptivity via Varying-norms
For completeness we provide a mild generalization of the static regret algorithm of [23] leverage an arbitrary sequence of increasing norms. A similar technique has been used to get full-matrix parameter-free rates by [13].
The analysis remains mostly the same as Jacobsen and Cutkosky [23], but their analysis of the stability term bounds - Du, (we+1 (wn)) via lemma that assumes that a/e (wr) (.([ll)))) for w Rd, To obtain full-matrix version of their result, we would instead like have (.(lwull)) where Il- is a weighted norm w.r.t. to the inner product (s w) on an arbitrary Hilbert space W. In what follows, drop the dependence on W for brevity and simply write +)
We first state and prove the main result of this section. The proof will rely on a few technical lemmas, which state and prove at the end of the section in Appendix G.I.I.
Theorem 10. Let W be a Hilbert space and let (:--) denote the associated inner product, let I| ....,, |1-1|+11 be arbitrary sequence of non-decreasing norms on W, and let l1-llo
V(.))) & Il- for all t. Let li....,lr by be convex functions over W satisfying llgell.. S G
for all and gi E (e,(w))- Let <,> 0, O. V 4G2 1 a Vv. (VV////)
and set (h(w) = So sblulll min [m(e//at1) + nVi] dx, and on each round update w441 arg min (Eon1 ys:w) w) + virti()))
"
Then all a E W,
RT(u)= Ō ( Ge +|ul|
||
VT cG
+1) v G'n
|ull VVT cG
+11]
|llll
Virln
where Ō(.) hides constant and log(log) factors (but not factors)...
Proof. Begin by applying the standard FTRL regret template (see, e.g., Orabona [39, Lemma 7.1):
T
T
Rr(u)= = (e: wi - u) S (1)+
Σ
Fe(we)) - Fe+1(We+1) + (gt, we)
1=1
where F((w) (((n))({)+))) 1-1
Do: w0) )s:w)
(w)) Observe that the summation be written
(((w)) Fe+i Fe+i(we+1) + (gt, wx)
(gr, wi we+1) + (w,))) F.(we41) + (1h. U/+ 12+1) (w)-)
(ge, we w(+1) + (VF((ue), w. we+1) - Dr, (We41/we)) + (1hx (
T
(gt, we - we+1) - Dr, (we+a/we)= + (1/2 (wee1)
16
I1atlle, || we+t lle Dyp (we+ilwr) (1++1 - -bee(we+)),
where (a) uses the definition of Bregman divergence to write f(a) - ((b) (V)(a),a a b) (b(b) (b) uses the fact that w. = arg minwew Fi(w), hence (VFr(w)), w. w++1) S 0 by the first-order optimality condition, and (c) uses the fact that Bregman divergences invariant to linear
terms, so from the definition of F; we have Dr, (+I-) D&, (-I.). Moreover, since .I.., l1.1/7 is a non-decreasing sequence of norms, we can bound the terms
(V++1 (w) V V wIle) 2 ((wll))))))) v wlll
= ((wwl))
32

---

so overall the regret is bounded by
T
Rr(u)= S (u)+ +
Σ
Ilalle,,
1 - Wetille - ( (wo+1lluz) - A (1wweeal)))
From here, the rest the proof follows using the same arguments as [23], but using our Lemma to bound Do, (w(+1/we) 2 2 I|wl - -Wt+1ll (1( instead of their Lemma
G.1.1 A Stability Lemma for Weighted Norms
In this section generalize the stability lemma of Jacobsen and Cutkosky [23] to weighted norms || / (x, Mr). This is the main technical detail needed for the proof of Theorem 10 that is not covered by the proof their static regret algorithm. Throughout this section we assume the domain W is Hilbert space with associated inner product (-,-). The following helper lemma follows via a straight-
but somewhat tedious computation.
Lemma 4. Let g W + R be convex function and let f(x) Vg(x). Then for x E W s.t.
g(x) O we have
Vg(x)
V2g(z) Vg(z) @ Vg(x) (²)(x) 2f(x) 4f(x)3
Vf(x) = 2f(x)
and
where & denotes the tensor product.
Using this, we have the following Hessian bounds for ellipticallyssymmerric functions:
Lemma 5. Let M E L(H, H) be a positive definite linear operator and assume M is self-adjoint w.ra. (. Let M = / (x, Mx) the weighted norm induced by M and let <b(w)= = v ([[w]] [l] for some convex function
IR + R. Then for any W bounded away from O and any W.
('((wulla)))
(u, ( 2 min ("([w)))))
[|ul
Moreover, if V() concave and non-negative, then for any w E W bounded away from and E W.
(u, V (Ww)) 2 4 ("([ ||ll
Proof. The proof follows a similar argument to Orabona and Pál [41, Lemma 23). Let us first
compute the gradients of [(x) = || = / (x, Mæ). Let g(x) = (æ,, Mx) and observe that if M
self-adjoint w.r.t. () we have Vg(x) = 2M and v2g(x) 2M. Hence, applying Lemma
have
V = 2Mw
Mw
2 [wila
-wll
2M 4.w & Mw
Mw & Mw M
V2 f(w) = 2 wwlas
|| as
|wll
Using this, we have
Mw V ((wwwllar)
= [Vllwll)) V ||wllr V ())
and
V2 = V (V ||w]aar V. ((((well))))
2 |owlla v ('(lw]l + w² [([[w/]) ax) (V [w
V [[w]lar)
(Mw & Mw) + ((([wwlaas) |/
(Mw @ Mw) I M
Twlll
[V"
((([[w]lar)
(((llllaa) M
(Mu @ Mw) +
=:8 3MM @ .uw) + 7yM.
33

---

Hence, for any u E W we have
(u, (ww))) (u, (3M @ Mw + 7M)
= 3 (u, Mw) + |/lll1
Now decompose = w + v for some e such that (Mw, v) - O; such a v always exists for positive definite M. Then
(u, ((w))) = 3 (w + w, Mw) + + |/0- + wlll.s = 3 Ilwoll + [Illllas + 11v1l3s
Ve' ('(1woll
|1w0l + M ('(lwllass) (Iwllla + llullas
1wll
Ve' ('((l20
1|01130
1| a
TT' (((lloll
} (110 + Ilullas
min
} /Iullir
min
| M
where the last step uses the fact that and u orthogonal w.r.t M.
For the second statement of the lemma, we need only show that v (l)) [|w]lar 2 w² ("([w]) This is indeed the case by concavity and non-negativity of v-):):
V (((l)r)) |
(2((0) 4 ("([[]] M M M- -0)
2 (([lw[laa))
w M
H Supporting Lemmas
The following lemma is a straight- generalization of the usual log determinant lemma (see, e.g. [10, Lemma 11.11J), taking a bit of extra care to handle determinants of potentially infinite- dimensional linear operators.
Lemma 6. Let H be Hilbert space and for all let vi E H. Suppose it 6 Uz H -> H defines bounded linear operator for all t and suppose A A + & ve for any 2 starting from
Ao 1. Then
(u, (vv))) = =1 Det (A,-1)
Det (A,)
Proof. Observe that for any t, we have A, = Ar-1 + @ so re-arranging terms, factoring, and taking determinants of both sides we have
Det (A.) Det (I A,- 8 v.) = Det (Ar-1).
(10)
Note that each of these determinants well-defined in terms of the Fredholm determinant: each of the three terms above a trace-class perturbation the identity operator. Moreover, observe that A (vt & Uz) a rank-one operator having single eigenvalue equal to = (ve, A, v.). Indeed, for any w E H we have A (vr @ (w) = (Ue, w) A, Ur hence, for = A, Un we have
A (vz @ (w)) = 1 @ (A, vx) = (ve, A, v.) A, 00 = Aw.
Therefore, from the standard rank-one perturbation identity for the determinant we have Det (1 - A, v, @ v.) = (vr, A, 'v),. so re-arranging Equation (10) yields
(ve, A =1 Det (A,-1) Det (At)
34

---

Lemma 7. Let H. be a Hilbert space. For all t let Gt E 'H be a bounded linear operator and define
S. = Al + E.=1 G2 @ G, for X > 0. Then
Σ ST S dn e+ edmax
A
where Kr ((g k(t,, sE and dert (A) TT (Kr(M + Kr)-
Proof. First apply Lemma 6 with 2t Gi/VA followed by the elementary inequality 1 S In (1/z) to get
T Σ
(G,, G.)
Σ
Gr (5t/2)
Det (Si-1/A)
Det (St/2)
Det (St/A)
In
Del (Sa-1/A)
1=1
Det (1+ Σt= G2 2 Gt A
In
1+
In |+ do(KT)
where the last line uses the well-known fact that the gram matrix Ky- ((ge, 9s) k(t,, s and the empirical covariance operator Σ G2 & G, have the same eigenvalues. Moreover, following Jézéquel et al. [27, Proposition 2] we can use the inequality In (1 + x) = + In In (1++2 x)) to
expose a dependence on the effective dimension dest (A) = Tr (Kr(Al + KT)- as follows:
Σ (((TT) tml
11 >n(KT) (1+A((k))
}
SG SG,
1 + In
X (e(TT)
Amax Amaxx(K)) (ox))(K))))) )
Xe(KT)
< + In
1+
+ (e(i))
1 in
1+ Amax((Kr)
)
(Kr(M + 11)
I In (1+ (m)o((KT))
do
(e+ edmax(K'n)
dn
Lemma 8. Let H be a separable RKHS with associated feature map o(t) E H and let x E H. satisfy rrtt = (t) for some X L(H, W). Then
| = (X(((t) & ((t)), X) HS
where o(t) 2 d(t) H + H. is the linear operator with action (ø(t) @ o(t)) (o(t), o(t).
35

---

Proof. Let h1, he.... be an orthonormal basis of H. By definition of the Hilleer-Schhiil inner product, we have
(x((() @ (()), uss E (X(((1) o(t)), Xhdw
Σ (o(t), ba (Xo(t), Xhi)w
Σ (o(1), hi) (x))) hi)
(o(t), Xx(())x = (X)())
x) = 1
where X : W + H. is the adjoint of and (+) uses Parseval's identity.
Lemma 9. Ler W S Id and let H be an RKHS with associated feature map é. For all t e [T]
let G. 9t @ é(t) E L(H. W) denote the rank-one operator mapping Gi(h) = (ø(t), h) e W.
Then for any
Σ G2
Σ k(s,s') (gs.))/')
HS
Proof. Let htth,, be an orthonormal basis of H. Observe that for any h H. (E'= G.) (M)
Et- (d(s), ht) Is. Hence, by definition the Hilbert-Schhidt norm,
2
Σ G2
Σ
Gc - = (o()), harn Ior Σ (old'), hi)
HS
w
W
ΣΣ (o(s). midne (8(s'), harme (0., (.).
Σ 1e) w E (K((), hid (0(5')
Σ (0..9w)) (e
where the last line observes that for orthonormal basis hy have E, (6(s), ha) (0(s"), hinu (Ø(s), (s)))) = k(s,
The following theorem shows how to compute the norm of G, = St @ Φ(t). which is the auxiliary loss for OLO under framework. Here state the result in terms of 9t W for generality, but note that in the main text we implicitly invoke Riesz representation theorem to write g, E W, G, E L(H, W), and ||&ell = lldll tk)
Lemma 10. Let H a RKHS with associated feature map e(l) and let W be a Hilbert space. Let 4, W + R be a differentiable function and for any W E L(H,,W) let &(W) = &WWo(t) Then for any W E L(H, 90 (W(()),, and G. 9t @ @(t) (W).
||Galles = lll. k(t,t),
where k(s,t) (((ss))(t))))))))))))))))))))))) h is the kernel associated with H and II-llw is the dual norm of ll-lww-
Proof. We have via Lemma 11 that
G G= 2 @(t) E ( S W)",
36

---

where E (Wo(t) S W By Riesz representation theorem, we can identify 9t E W such that for any w E W. (w) (ge, w> and likewise we can identify G, L(H, W) with rank-one operator G, E L(H, W) with action (h) = (o(t), h) St. Hence, we have by definition of the Hilbert-Schmidt norm that any orthonormal basis {hi}: of H.
||GllHs = Σ GGrhilww
= Σ (o(t), (o)t),.)) ll
-1l wl, |o(t)
where the last line again uses Riesz representation theorem to write ll ll and then uses E; (o(t), h2) = ([)()) by Parseval's identity. Morcover, since <(t) are the features of an RKHS with kernel k, have
[lo(t) o())) k(t,t).
Lemma 11. Let H be a RKHS with feature map 6(1) E H. and let W be Hilbert spuce. Let W & be convex function and let (W) l o(t)) for W L(H, Then for any W E L(H, and any gr E (W o(t)) CW"
= & 6(1) E (W) E L(H,W)"
where G. L(H, W).
L(H, W)" is the functional with action G.(W) (gt, W Wo(t)) for all W
Proof. Let W E L(H, W), w. Wo(l) E W, and let ge E Olr(w:) S W". Define G. @ d(1) E L(H, W) the functional on L(H, W) with action
G.(W) = (9t, W Wo(t)) AW L(H,W).
Now observe that for 9i E 0e, (w:), for any w W we have
(ww) 2 & (w:) (gt, w wx)w (.WW (()) + (gt, -W0(() hence for any V L(H, W) we can take Vo(() to get
l(Vo(t)) 2 (W ((t) + (ge. Vo(t)= W (d(()) ( + (gc, (V - -W)o(t)
that is,
ī(V) ((W) + Gc(V W).
so G. g: x(t)= E (W) C W).
For completeness, the following lemma provides the inverse of matrix with entries Ki min(i,j) j). A similar result can be seen in the proof of Jacobsen and Orabona [26, Lemma 4], where a variant of the matrix K appears an intermediate calculation.
Lemma 12. Let K E RxT be a matrix with entries KJ min Then K-1 tri-diagonal matrix of the form
2
-1
0
0
0
0
2
-1
0
0
0
-1
-1
0
0
K-1
0
0
-1
2
0
0
0
0
0
0
2
-1
0
0
-1
1
37

---

Proof. It can easily be checked that K has Cholesky decomposition K = U where U is the upper-triangular matrix of 1's. Hence, K- U- A-1---U00 (UT)-) Moreover, the inverse of U is the first-order fiiieediiferreces operator with entries
if = j
Mi
j++
otherwise
Indeed, (UE) = E URLA = - + U3 = 1 for i = j and zero otherwise. Computing
K-1 ΣΣ yields the tri-diagonal matrix the stated form.
38

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and introduction accurately summarize tributions: we present a reduction from dynamic regret minimization to static regret min- imization in RKHS. We design a class of function spaces which allow to obtain optimal regret guarantees Section 4. and our result easily generalizes to scale-free updates using well-known clipping techniques (Appendix C.3). We show that our approach enables to leverage loss curvature obtain ||u|| + der (A) (T) dynamic regret Section 5. Finally, we show how to obtain directionally adaptive dynamic regret guarantees in Sec- tion 6.
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 can be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the computational difficulties inherent to the RKHS approach approach in Section 4, and provide direction to well-known ways to address these issues from the RKHS literature. In Section 5 we discuss that we were unable find kernel with effective dimension which will enable the optimal 1 p for the class of TV bounded sequences. We detail explicitly which specific classes of loss functions results hold for (Lipschitz convex losses in Sections and 6, exp-concave losses, strongly-convex, and regression losses in Section 5).
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 encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
39

---

If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
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 penalize honesty concerning limitations.
will be specifically instructed
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: For each theoretical result, we explicitly state all necessary assumptions and provide complete proofs in the main text or appendix. The arguments are self-contained or discussed earlier in the relevant section.
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 or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relics upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: We do not include experimental results in this work, the current focus is on proving the theoretical guarantees and exploring potential applications.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), relcasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
40

---

(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily 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 to access this model for reproducing the results way produce 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 thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Since this paper does not include experimental results, there no data or code provided for reproduction.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httts://nipt) cc/
for more details.
While we 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 including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /niis. cttpublic/guiiaccc hetliic/gguie//eeee / ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
The authors should provide scripts to reproduce
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: As this paper does not include experimental results, there are no training or test details provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
41

---

7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: As this paper does not include experimental results, error bars statistical significance are reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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 the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not 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 execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: As the paper does not include experimental results, there is no information provided regarding computational resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 the paper (e.g.. preliminary or failed experiments that didn't 't 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://neuripp:: http.//c/bb.ccccchcccciieeeeeeee
Answer: [Yes]
Justification: The research conducted in this paper fully conforms to the NeurIPS Code Ethics. There are no ethical concerns related to data collection, experiments, or other aspects of the work, as it focuses purely theoretical analysis.
Guidelines:
42

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on theoretical advancements online learning algorithms and does not have direct societal applications. As such, it does not explicitly discuss poten- tial positive or negative socictal impacts. The work foundational in nature and does not involve technologies that could be misused present ethical concerns in its current form.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal 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 spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that 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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper focuses theoretical algorithmic advancements in online learning and does not involve the release of models, data, or other resources that could pose risks for misuse. Therefore, safeguards necessary, there is high-risk data models associated with the work.
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 allow for controlled use of the model, for example by quiring 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.
43

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification: This paper does any external assets such as code, data, or models. All work presented is original and theoretical, and no third-party assets were incorporated.
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, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of the pack- age should be provided. For popular datasets, paperswi swwthcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: This paper does not introduce any assets such datasets, code, mod- els. The work is purely theoretical, and no new assets were created or released as part of this research.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: The 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.
44

---

Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage 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 the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: http:ppp.....ooeeeeeeee///////// for what should or should not be described.
45


Reviews:
[{"review_id": "vwKyql1vrm", "reviewer": "Reviewer_HHCS", "summary": "The paper proposes a clean reduction that turns dynamic-regret minimization in online convex optimization into a static-regret problem in an RKHS. By lifting each comparator sequence into an operator and pairing it with an auxiliary loss, the authors show that the learner’s dynamic regret equals the static regret. Leveraging this view, they (i) match the optimal rate (up to poly-logarithmic terms) in the linear case without horizon knowledge and (ii) demonstrate that the framework extends to exp-concave losses and yields directionally adaptive guarantees with little additional effort.", "questions": "1. What intuition drives the logarithmic spectral density in Proposition 2, and how sensitive are the regret bounds to alternative kernels?\n2. Given poly-log terms hidden in the bounds, can you provide explicit constants with a short discussion?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The work is principled and technically solid, and the manuscript is generally well written, though clarity suffers in places and empirical evidence is missing.\n\n---\n\n### Strengths\n\n- Neat idea: treat the discrete comparator sequence as a finite-sample realization of an underlying static function. This approach is sensible, though not entirely new given decades of work on kernel embeddings.\n- The technique reduces the original problem to static online operator learning in an RKHS, subsuming prior “stacking’’ tricks and allowing infinite-dimensional features. In doing so, it achieves optimal regret without prior knowledge of the horizon, which is implicitly captured by the RKHS construction.\n- The construction naturally extends beyond linear loss functions to tackle second-order problems such as online Newton step or directional covariance.\n\n### Weaknesses\n\n- Although well written overall, several improvements would enhance readability:\n    - Because the paper is dense, a high-level overview of the results and their significance, with a concise summary of the proof techniques, would help.\n    - Given the notation- and equation-heavy presentation, more intuition for key terms (e.g., the spectral density $Q(w)$ in Proposition 2) would be desirable.\n    - Minor issues: $g_t$ (line 60) and ${y}^\\circ$ (line 90) appear without proper introduction; inconsistency between $\\mathcal{H}^d$ and $\\mathcal{H}$ in line 60.\n- The paper discusses practical implications but provides no empirical study to show whether the kernel construction preserves the theoretical edge. Even a simple numerical experiment, however naïvely implemented, would significantly strengthen the manuscript.", "was_revised": false, "final_justification": "", "rebuttal": "> What intuition drives the logarithmic spectral density in Proposition 2\n\nThe key intuition is to observe that the ideal choice of density would\nbe $Q(w)=1/|w|$. Indeed, we would have (loosely speaking)\n$$\\begin{aligned}\n \\\\|u\\\\|\\_{H}^{2}=\\int\\frac{ |\\hat u(w)|^{2}}{Q(w)}dw= \\int |w|  \\hat u(w) \\overline{\\hat u(w)}dw \\le \\int |\\nabla u(t)| |u(t)|dt \\le \\max\\_{t}|u(t)| \\\\|\\nabla u\\\\|\\_{L^{1}}, \\end{aligned}$$\nwhere we've used Plancherel theorem\n$\\int \\hat f(w)\\overline{\\hat g(w)}dw=\\int f(t)\\overline{g(t)}dt$ and\nthe fact that $|F^{-1}\\[w \\hat u(w)\\](t)|\\le |\\nabla u(t)|$. Notice that\nthe final bound is precisely the continuous-time analogue of what we're\nlooking for: $\\max\\_{t}\\\\|u\\_{t}\\\\|P\\_{T}$.\n\nHowever, $Q(w)=1/|w|$ is not a valid choice because it is not\nintegrable: indeed, $\\int 1/|w|\\ dw$ diverges at 0 and $\\infty$. To fix\nthis, we instead set $Q(w)=R\\_{\\infty}(w)R\\_{0}(w)/|w|$, where\n$R\\_{\\infty}(w)=1/(1+w^{p})^{s}$ is a \"tapering function\", which helps\ncontrol $Q(w)$ in the asymptotic regime, and\n$R\\_{0}(w)=1/\\log(1+w^{-1/2})\\log\\log(1+w^{-1/2})$ which ensures that $Q$\nis well-behaved near zero. The intuition behind $R\\_{0}(w)$ is that near\n$0$ we have\n$Q(w)\\approx R\\_{0}(w)/w \\approx \\frac{1}{w\\log(w^{-1/2})\\log^{2}\\log(w^{-1/2})}$,\nwhich after a change of variables $t=\\log(w^{-1/2})$ integrates near\nzero as\n$\\int\\_{0}^{\\epsilon}Q(w)dw \\approx \\int\\_{\\log(1/\\epsilon)}^{\\infty}\\frac{1}{t\\log^{2}(t)}dt= O(1)$.\nWe can add a discussion of these intuitions to the appendix.\n\nTogether these two additional bits of regularization make $Q$\nintegrable, yet only increase the associated norm $\\\\|u\\\\|\\_{H}$ by a small\namount, letting us achieve almost the same result as the ideal\n$Q(w)=1/|w|$.\n\n> how sensitive are the regret bounds to alternative kernels?\n\nIt is possible to design other kernels which achieve $\\sqrt{P\\_{T}T}$,\nthough generally alternative kernels will fail to be horizon\nindependent. For instance, it can be shown using our general\ncharacterization in Section 4.1 that setting\n$Q(w)\\approx|w|^{p}/\\sqrt{1+w^{2}}$ can also guarantee $\\sqrt{P\\_{T}T}$\ndynamic regret, so long as you set the exponent $p$ correctly. The\ncorrect value of $p$ is a function of $T$, making the result horizon\ndependent. We believe the ability of our proposed kernel to avoid prior\nknowledge of T represents a significant and new insight to the\nfoundations of dynamic regret.\n\nMore generally, in the OLO setting there is a very explicit trade-off in\nterms of the RKHS norm $\\\\|u\\\\|\\_{H}$ and the variance penalties\n$\\sum\\_{t}\\\\|g\\_{t}\\\\|^{2}k(t,t)$, both of which depend on the choice of\nkernel. Kernels with small $k(t,t)$ will tend to make $\\\\|u\\\\|\\_{H}$ large\nand vice-versa. It is important to carefully balance these two terms\nwhen designing the kernel. An analogous trade-off occurs between\n$\\\\|u\\\\|\\_{H}^{2}$ and $d\\_{\\text{eff}}(\\lambda)$ in the curved losses\nsetting.\n\n> Given poly-log terms hidden in the bounds, can you provide explicit constants with a short discussion?\n\nA more complete statement of the bound in Proposition 1 would be\n$R\\_{T}(u)\\le O(\\\\|u\\\\|\\_{H^{d}}\\sqrt{\\sum\\_{t} \\\\|g\\_{t}\\\\|^{2}k(t,t)\\Lambda\\_{T}(u)})$,\nwhere e.g.\n$\\Lambda\\_{T}(u)=\\log\\left(\\frac{\\\\|u\\\\|\\_{H^{d}}\\sqrt{\\sum\\_{t} \\\\|g\\_{t}\\\\|^{2}k(t,t)}\\log^{2}(T)}{\\epsilon}+1\\right)$\n(The precise form of $\\Lambda\\_T(u)$ depends on the choice of base\nalgorithm; see Proposition 6 in Appendix C.2 for a concrete example).\nThe penalty $\\Lambda\\_{T}(u)$ is seen as the price of adaptivity to the\ncomparator sequence, and is incurred by all prior works which minimize\ndynamic regret without prior knowledge of $M\\ge \\max\\_{t}\\\\|u\\_{t}\\\\|$ (see,\ne.g., Jacobsen & Cutkosky (2022), Zhang et. al. (2023), Jacobsen &\nOrabona (2024)).\n\nAside from this, additional logarithmic factors can appear due to the\nchoice of kernel. The algorithm in Section 4 is significantly more\nadaptive than prior works since it does not require the horizon $T$, and\nthis comes at the cost of a multiplicative $\\log(T)\\log\\log(T)$ penalty\nin the bound (see Proposition 3). We conjecture that it is possible to\nincur only the $\\Lambda\\_{T}(u)$ penalty above when leveraging\nprior-knowledge of $T$, but leave this question for future work."}, {"review_id": "PYtKoVEvEt", "reviewer": "Reviewer_qB8Z", "summary": "This paper proposes a reduction that frames dynamic regret minimization as a static regret problem in a function space, specifically a RKHS, allowing the application of many well-established static regret minimization results. Moreover, by combining parameter-free methods for static regret minimization with a carefully designed translation-invariant kernel, this paper achieves a dynamic regret of $\\tilde{O}(\\sqrt{P_T T})$ up to poly-logarithmic terms. Furthermore, this paper demonstrates the applicability of the reduction by introducing several results in static regret minimization, such as scale-free and directionally adaptive guarantees, as well as curved losses, thereby achieving the first corresponding bounds.", "questions": "-\tIn Section 4.1, line 220, the author introduces translation-invariant and Fourier transforms to achieve the trade-off. I find myself puzzled about the reasoning behind presenting the trade-off in this manner. It would be better if the authors could elaborate further on the intuition behind this approach.\n\n-\tIn Theorem 6, the $d_{eff}$ terms might be somewhat challenging for readers to fully grasp. It would be helpful if the authors could provide additional explanation or offer more physical intuition behind these terms.", "limitations": "See Weakness above", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n-\tUsing reduction to apply static regret results to dynamic regret appears quite promising, and this paper demonstrates its feasibility.\n\n-\tThis paper achieves $T$-free dynamic regret (without requiring the doubling trick) as well as scale-free dynamic regret.\n\n-\tCompared to existing works [1, 2] that are limited to linear losses, this paper further extends to curved functions and explores the dynamic regret in this context.\n\n\n[1] Andrew Jacobsen and Francesco Orabona. An equivalence between static and dynamic regret minimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.\n\n[2] Zhiyu Zhang, Ashok Cutkosky, and Yannis Paschalidis. Unconstrained dynamic regret via sparse coding. Advances in Neural Information Processing Systems, 36, 2024\n\n**Weaknesses**\n\n-\tIn the abstract, the dynamic regret of $O(\\sqrt{P_T T})$ actually includes some poly-logarithmic terms, as presented in Theorem 5. Moreover, since it is obtained using a parameter-free approach, the reader may find it difficult to remove the corresponding poly-logarithmic factors due to the lower bounds of parameter-free methods. It would be greatly appreciated if the authors could clarify the poly-logarithmic dependency in the abstract to avoid unnecessary misunderstandings.\n\n-\tThe current version of the paper does not appear to provide an analysis of the efficiency issues that may arise when implementing kernel methods in practice, nor does it discuss the potential impact of employing approximate calculations on the results. Some readers might be concerned about whether these factors represent additional costs introduced by the dynamic-to-static reduction. It would be helpful if the authors could include some discussion regarding the complexity of the problem and the practical implications involved.", "was_revised": true, "final_justification": "I recommend accepting this paper.", "rebuttal": "> In Theorem 6, the $d\\_{eff}$ terms might be somewhat challenging for readers to fully grasp. It would be helpful if the authors could provide additional explanation or offer more physical intuition behind these terms.\n\nThe effective dimension $d\\_{eff}(\\lambda)$ is a generalization of the\nusual notion of dimension. Consider first a finite-dimensional RKHS $H$:\nif $H$ has dimension $d$, it means that there is an orthonormal basis\n$(\\psi\\_{i})\\_{i=1}^{d}$ such that any $f\\in H$ can be written\n$f(x)=\\sum\\_{i=1}^{d}\\alpha\\_{i}\\psi\\_{i}(x)$. Here the notion of dimension\nis the same as the familiar one from linear algebra: the dimension is\nthe number of \"directions\" you can move in, with the directions\ncharacterized by the basis elements $\\psi\\_{i}$.\n\nIn general an RKHS can be infinite dimensional, so there may be\ninfinitely many directions we can move in. However, we can still\ncharacterize how many of these directions are \"significant\". One\nimportant basis of an RKHS is obtained as the eigenfunctions of an\nintegral operator related to the kernel, and the effective dimension\nmeasures how many of these eigenfunctions are associated with a\n\"non-neglible\" eigenvalue $\\sigma\\_{1}\\ge\\sigma\\_{2}\\ge\\ldots\\ge 0$. That\nis, let $t\\_{0}$ be the first $t$ such that $\\sigma\\_{t}< \\lambda$, then\n$$\\begin{aligned}\n  d\\_{\\text{eff}}(\\lambda)=\\sum\\_{n}\\frac{\\sigma\\_{n}}{\\sigma\\_{n}+\\lambda} = \\sum\\_{n < t\\_{0}}\\frac{\\sigma\\_{n}}{\\sigma\\_{n}+\\lambda}+\\sum\\_{n\\ge t\\_{0}}\\frac{\\sigma\\_{n}}{\\sigma\\_{n}+\\lambda} \\le t\\_{0}+\\sum\\_{n\\ge t\\_{0}}\\frac{\\sigma\\_{n}}{\\lambda}.\\end{aligned}$$\nThe first term counts how many $\\sigma\\_{n}$ are non-negligable relative\nto the regularization parameter $\\lambda$, and represents the number\n\"important\" directions we can move in. The regularization parameter\n$\\lambda$ controls the trade-off between the remainder term\n$\\sum\\_{n\\ge t\\_{0}}\\sigma\\_{n}/\\lambda$ (the remaining small\n$\\sigma\\_{n}$'s) and the variability penalty, $\\lambda\\\\|u\\\\|^{2}\\_{H}$.\nHence, one should aim to design a kernel such that the spectrum is\ncontrolled and the remainder term can be suitably traded-off against\n$\\\\|u\\\\|\\_{H}^{2}$. We will add additional discussions to aid the reader's\nintuitions.\n\n> In Section 4.1, line 220, the author introduces translation-invariant and Fourier transforms to achieve the trade-off. I find myself puzzled about the reasoning behind presenting the trade-off in this manner. It would be better if the authors could elaborate further on the intuition behind this approach.\n\nThe basic idea is that if we could set $Q(w)=1/|w|$, then using\nproperties of Fourier transforms (namely, that\n$\\int \\hat f(w)\\overline{\\hat g(w)}dw=\\int f(t)\\overline{g(t)}dt$ and\n$|F^{-1}\\[w f(w)\\](t)|\\le\\|\\nabla f(t)|$ ) we would naturally relate the\nRKHS norm associated with a translation-invariant kernel to the\npath-length: $$\\begin{aligned}\n  \\\\|u\\\\|\\_{H}^{2}=\\int\\frac{ |\\hat u(w)|^{2}}{Q(w)}dw= \\int |w|  \\hat u(w) \\overline{\\hat u(w)}dw \\le \\int |\\nabla u(t)| |u(t)|dt \\le \\max\\_{t}|u(t)| \\\\|\\nabla u\\\\|\\_{L^{1}},\\end{aligned}$$\nwhich is the continuous-time version of the $\\max\\_{t}\\\\|u\\_{t}\\\\|P\\_{T}$\ndependence that we want to show. However, this doesn't quite work\nbecause $Q(w)=1/|w|$ isn't integrable (the integral blows up at 0 and at\n$\\infty$). To fix this, we add extra terms to regularize $Q(w)$ when\n$w\\to 0$ and as $w\\to\\infty$. See our [response to Reviewer HHCS](https://openreview.net/forum?id=4LSulRbbeL&noteId=5BLJtt4cvd) for details."}, {"review_id": "0CZAB1r9Oq", "reviewer": "Reviewer_5L4F", "summary": "This paper studies dynamic regret in online convex optimization, where the objective is to achieve low cumulative loss relative to an arbitrary benchmark sequence. The authors frame dynamic regret minimization as a static regret problem in a function space. By carefully constructing a suitable function space in the form of a Reproducing Kernel Hilbert Space (RKHS), their reduction enables us to recover the optimal dynamic regret guarantee in the setting of linear losses. The main contribution of this work lies in the fact that, unlike previous dynamic-to-static reductions which are limited to linear losses, the proposed reduction is applicable to any sequence of losses. As a result, it delivers theoretical result in exp-concave and improper linear regression settings.", "questions": "Overall, the main contribution of this paper lies in extending the reduction technique to support any sequence of losses, rather than being limited to linear losses. I view this as an important step forward. However, the following concerns arise regarding the proposed method and its theoretical implications: \n\n1. As shown in Algorithm 1, compared to standard OCO algorithms, the kernelized online learning procedure requires maintaining decision variables and gradients in a higher-dimensional space, which results in increased space complexity. How do the authors assess the practical value of this reduction in light of this cost?\n2. For exp-concave functions, the proposed reduction yields an $O(d_{\\text{eff}}(\\lambda)\\ln T)$ regret bound that includes a term $d_{\\text{eff}}(\\lambda)$, which represents the complexity of the RKHS. Could the authors clarify how large this term might be, and whether it dominates the regret bound?\n3. The authors argue that their reduction holds for any sequence of losses. If that is the case, is it possible to obtain a dynamic regret bound that depends on the path length for strongly convex functions? Prior dynamic-to-static reduction [1] could not leverage strong convexity due to their restriction to linear losses. \n\n[1] Jacobsen et al. An equivalence between static and dynamic regret minimization. NeurIPS, 2024.", "limitations": "This dynamic-to-static reduction increases the space complexity, which may limit its practicality in real-world applications.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: The paper is clearly written and makes a significant step forward in reducing dynamic regret to static regret. \n\nWeaknesses: Existing reduction techniques that transform dynamic regret into static regret generally rely on an expanded function space. As a result, these approaches tend to incur high space complexity. Specifically, while the original OCO problem operates in a $d$-dimensional space, the current reduction effectively lifts the problem to a $d\\times T$-dimensional space. It is unclear whether this space complexity could become a practical concern (as discussed in Questions).", "was_revised": true, "final_justification": "The authors have acknowledged the computational and memory drawbacks introduced by their algorithm. Nonetheless, I also recognize the significance of the proposed reduction technique. Therefore, following the rebuttal discussion, I am inclined to recommend acceptance of this paper.", "rebuttal": "> As shown in Algorithm 1, compared to standard OCO algorithms, the kernelized online learning procedure requires maintaining decision variables and gradients in a higher-dimensional space, which results in increased space complexity. How do the authors assess the practical value of this reduction in light of this cost?\n\nWe acknowledge that the naive implementation of kernel methods could\nlead to undesirable overhead; in this work we have made no attempt to\noptimize computation and memory overhead so as to focus on developing\nthe base results of the framework, and we are up-front about this\nlimitation in the main text. However, as noted in the main text there is\na large body of work studying efficient implementions of kernel methods\nwhile incuring acceptable performance trade-offs. Indeed, both the\nkernelized ONS and kernelized VAW forecaster discussed in section 5 have\nefficient approximations with well-studied guarantees (Calandriello et\nal. (2017a,2017b), Jezequel et al. (2019)). We are confident that the\noverhead can be improved in the OLO setting as well, but given the\nnon-trivial nature of the topic we believe this issue is beyond the\nscope of the current paper.\n\n> For exp-concave functions, the proposed reduction yields an regret bound that includes a term $d\\_{eff}$, which represents the complexity of the RKHS. Could the authors clarify how large this term might be, and whether it dominates the regret bound?\n\nThe effective dimension is the main penalty that trades-off with\n$\\\\|u\\\\|\\_{H}^{2}$ in the curved losses setting; it is necessary to keep\nboth terms in mind when designing the kernel, because lowering one tends\nto raise the other. How large it can be is tied to the specific kernel.\nWe provide a simple example in Example 3 of how $\\lambda\\\\|u\\\\|^{2}\\_{H}$\nand $d\\_{\\text{eff}}(\\lambda)$ can be traded-off to give\n$S\\_{T}^{2/3}T^{2/3}$ bounds, where $S\\_{T}=\\sum\\_{t}\\\\|u\\_{t}-u\\_{t-1}\\\\|^{2}$\nis the *squared* path-length. See also our [response to Reviewer qB8Z](https://openreview.net/forum?id=4LSulRbbeL&noteId=6C3wGyBMTE) for\nadditional discussion and intuitions about the effective dimension.\n\n> The authors argue that their reduction holds for any sequence of losses. If that is the case, is it possible to obtain a dynamic regret bound that depends on the path length for strongly convex functions? Prior dynamic-to-static reduction \\[1\\] could not leverage strong convexity due to their restriction to linear losses.\n\nYes, the argument is essentially the same as it is for exp-concave\nlosses. To see why, observe that under strong convexity what you get is\n$$\\begin{aligned}\n  \\ell\\_{t}(W\\_t\\phi(t))-\\ell\\_{t}(U\\phi(t)) &\\le \\langle g\\_{t},W\\_{t}\\phi(t)-U\\phi(t)\\rangle_W - \\frac{\\alpha}{2}\\\\|(W\\_{t}-U)\\phi(t)\\\\|^{2}\\_{W}\\\\\\\\\n  &= \\langle g\\_{t}\\otimes\\phi(t), W\\_{t}-U\\rangle\\_{HS}-\\frac{\\alpha}{2}\\langle(W\\_{t}-U)(\\phi(t)\\otimes\\phi(t)),W\\_{t}-U\\rangle\\_{HS}.\\end{aligned}$$\nThus, following a standard mirror-descent-based argument you would want\nto set divergence $D\\_{\\psi\\_{t}}(X|Y)=\\frac{\\alpha}{2}\\\\|X-Y\\\\|^{2}\\_{t}$,\nwhere\n$\\\\|W\\\\|\\_{t}^2=\\langle W(\\lambda I +\\sum\\_{s=1}^{t}\\phi(s)\\otimes\\phi(s)), W\\rangle\\_{HS}$,\nsince the negative term above will lead to the divergences telescoping\nto $\\frac{\\alpha\\lambda}{2}\\\\|U\\\\|^{2}\\_{HS}$, and the remaining stability\nterms get bounded as $O(d\\_{eff}(\\lambda)\\log{T})$ using a generalization\nof the log-determinant lemma (Jezequel et al., 2019). Note that in the\nstandard static regret setting, it is possible to remove the the leading\ncomparator-norm penalty and pay only a $O(\\log{T})$ stability penalty;\nsuch improvements are not possible here, as removing the $\\\\|U\\\\|^2\\_{HS}$\nterm would imply algorithms which can violate existing\n$R\\_{T}(u\\_{1},\\ldots,u\\_{T})\\ge \\Omega(P\\_{T})$ lower bounds for\nstrongly-convex losses (Yang et al. 2016).\n\nFrom the above, we see that the strongly-convex case is essentially the\nsame as the exp-concave case in terms of both the approach and the\nguarantee. The main difference from applying K-ONS is that K-ONS uses\nthe covariance operator of a product kernel which additionally\nincorporates the gradients\n$\\bar{k}(i,j)=\\langle g\\_{i},g\\_{j}\\rangle k(i,j)$ (Calandriello et al.\n2017). Thank you for the insightful question!"}, {"review_id": "Jw02ebilRV", "reviewer": "Reviewer_viCE", "summary": "The authors study dynamic regret in online convex optimization, where the learner competes against a sequence of comparators in a convex set $\\mathcal{W}$. Their key idea is to reinterpret the comparator sequence as a fixed _function_ from $[1,T]$ to $\\mathcal{W}$, thereby reformulating the dynamic regret problem as a static regret problem in a _function space_. Specifically, they consider this function space to be a Reproducing Kernel Hilbert Space (RKHS) associated with a kernel $k(\\cdot, \\cdot)$. Under this framework, the $t$-th step of the online learning algorithm can be implemented in time $O(t)$ via the kernel trick, and a static regret bound in the RKHS yields a dynamic regret bound for the original problem. By choosing $k$ to be a carefully designed translation-invariant kernel, the algorithm achieves optimal path-length dependence without requiring knowledge of the time horizon. Additionally, they show that kernelized ONS with the spline kernel $\\min\\\\{s,t\\\\}$ achieves the optimal regret rate for exp-concave online learning.", "questions": "## Clarifying Questions\n- In the introduction of RKHS in Section 2, the authors denote the domain of functions in $\\mathcal{H}$ as $\\mathcal{X}$. If I understand correctly, in the context of this paper, $\\mathcal{X}$ corresponds to the interval $[1,T]$. it would be helpful to make this more explicit. I also suggest using a more consistent notation such at $\\mathcal{T}$. \n- In Example 1, the FTRL update involves the function $\\Psi_t(\\cdot; V_t)$, but the argument is given as the scalar $\\|W\\|_{HS}$ rather than the Hilbert space element $W$ itself. Could the authors clarify why this is the case? \n- In Section 4.1, the authors focus on translation-invariant kernels. My understanding is that in such cases, $k(t,t) = k(0,0)$, which simplifies the tradeoff between $\\|u\\|_{\\mathcal{H}^d}$ and $k(t,t)$. However, is this restriction strictly necessary for the analysis, or could other kernel families also be used?\n- The construction of $Q$ in Proposition 2 appears somewhat mysterious. Could the authors provide more intuition or motivation behind this particular choice?\n-In Sections 5 and 6, the online learning algorithms in the RKHS do not appear to fall under the FTRL framework described in Example 1, as they seem to depend on the full gradient outer products rather than just the scalar quantity $\\sum_{s=1}^{t-1} \\\\|G_t\\\\|^2_{\\mathrm{HS}}$. Could the authors clarify how these algorithms are implemented in practice?\n\n## Typos\n- In several places, $\\\\|u\\\\|\\_{\\mathcal{H}}$ should be corrected to $\\\\|u\\\\|\\_{\\mathcal{H}^d}$.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths\n- The core idea of the paper is highly original and conceptually elegant. It extends the dynamic-to-static reduction framework of Jacobsen and Orabona (2024) by lifting the problem to an RKHS, enabling the use of advanced tools from static regret minimization and RKHS theory to establish state-of-the-art dynamic regret bounds in a unified way. \n- The paper is generally well written and easy to follow. While the RKHS framework can be abstract and mathematically dense, the authors provide a reasonable introduction and maintain clean, consistent notation throughout.\n\n## Weaknesses\n- A practical limitation, acknowledged by the authors, is that the current implementation requires $O(t)$ time and memory at round $t$, whereas existing dynamic regret algorithms often admit $O(\\ln T)$ time and memory. time and space implementations. Although the authors mention the possibility of using approximate kernel methods to improve efficiency, it remains unclear whether these approximations can preserve the same regret guarantees.\n- Conceptually, while the paper successfully recovers state-of-the-art dynamic regret bounds in several settings, it falls short of exceeding them or establishing genuinely new regret guarantees. The only exception appears to be Proposition 5, but the regret bound is not fully instantiated—specifically, the kernel function is left abstract, and the connection to path-length-based guarantees is not made explicit.", "was_revised": true, "final_justification": "The authors have clarified my technical questions, and thus I decided to maintain my rating and recommend acceptance.", "rebuttal": "> In the introduction of RKHS in Section 2, the authors denote the domain of functions in H as X. If I understand correctly, in the context of this paper, X corresponds to the interval $[1,T]$. it would be helpful to make this more explicit. I also suggest using a more consistent notation such at\n\nYes you are correct, you can think of $\\mathcal{X}$ as being $[1,T]$.\nMore generally $[1,T]\\subseteq\\mathcal{X}$ since we often want to define\nthe kernel outside of this interval for technical reasons. We will make\nthis and the notation more clear.\n\n> In Example 1, the FTRL update involves the function $\\Psi_t(\\cdot;V_t)$, but the argument is given as the scalar rather than the Hilbert space element itself. Could the authors clarify why this is the case?\n\nThe form in this example is given as $\\psi(\\\\|w\\\\|)$ simply because most\nparameter-free algorithms can be characterized as an FTRL algorithm with\na regularizer of this form (see e.g. Jacobsen & Cutkosky 2022). We use\nthis same type of algorithm to derive the guarantee in Proposition 1, by\napplying it in our kernelized reduction, so the example was meant to\nillustrate how such an algorithm would be implemented concretely. We\nwill highlight this connection more clearly.\n\n> In Section 4.1, the authors focus on translation-invariant kernels. My understanding is that in such cases, $k(t,t)=k(0,0)$ , which simplifies the tradeoff between $\\\\|u\\\\|\\_{H}$ and $k(t,t)$ . However, is this restriction strictly necessary for the analysis, or could other kernel families also be used?\n\nTranslation invariant kernels were chosen as an example to show that you\ncan recover the usual $\\sqrt{P\\_{T}T}$ bound in this framework, and in\nparticular because there is a natural connection between the RKHS norm\nand path-length when using a translation-invariant kernel (see our\nresponse [to Reviewer HHCS](https://openreview.net/forum?id=4LSulRbbeL&noteId=5BLJtt4cvd) for details).\n\nHowever, as you point out, the true potential of the framework is that\nit opens the door to studying new and interesting ways to characterize\nthe comparator's complexity by measuring it in terms of the rich class\nof RKHS norms, and indeed this norm need not be associated with a\ntranslation-invariant kernel. One example can be seen in Example 3 of\nSection 5, where the norm is measured using the linear spline kernel and\nyields a *squared* path-length $S\\_{T}=\\sum\\_{t}\\\\|u\\_{t}-u\\_{t-1}\\\\|^{2}$\nbound rather than the usual $\\max\\_{t}\\\\|u\\_{t}\\\\|P\\_{T}$.\n\nAs another example, suppose you have prior knowledge that the comparator\nis periodic (e.g. you're forecasting energy demand, which naturally\nrises and falls during a 24h cycle, for instance). It is possible to\naccount for this prior-knowledge via the RKHS norm $\\\\|u\\\\|\\_{H}$ and pay\nonly the path-length of a *single period*, rather than over the whole\nhorizon (comprised of *many* periods). As a simple illustrative example,\nconsider an alternating comparator sequence\n$(u\\_{t})\\_{t}=(0,1,0,1,0,1,\\ldots)$. The sequence has path-length $T$ but\nis interpolated by a triangle function over $[0,2]$ extended\nperiodically, which can be understood as a function in the periodic\nSobolev space $H=H^{1}\\_{per}([0,2])$ and has\n$\\\\|u\\\\|\\_{H}^{2}=\\int\\_{0}^{2}u(t)^{2}dt + \\int\\_{0}^{2}u'(t)^{2}dt = O(1)$\nand $k(t,t)=O(1)$.\n\n\n> -In Sections 5 and 6, the online learning algorithms in the RKHS do not appear to fall under the FTRL framework described in Example 1, as they seem to depend on the full gradient outer products rather than just the scalar quantity . Could the authors clarify how these algorithms are implemented in practice?\n\nThe algorithm in section 6 can also be understood as an FTRL algorithm\nsimilar to the one in Example 1. The outer products come into the mix\nbecause they are used to define a weighted norm. The implementation is\nanalogous, except you replace $||W||^{2}\\_{HS}$ with a weighted version,\n$\\\\|W\\\\|\\_{t}^{2}=\\langle W,\\Sigma\\_{t} W\\rangle\\_{HS}$ where\n$\\Sigma\\_{t}\\approx\\sum\\_{s=1}^{t}G\\_{t}\\otimes G\\_{t}$ (analogous to the\n$\\sum\\_{s=1}^{t}g\\_{t}g\\_{t}^{\\top}$ weighted norm used in \"full-matrix\nAdaGrad\").\n\nThe kernelized versions of both ONS and the VAW forecaster in Section 5\nhave known closed-form updates; we defer to Calandriello et al. (2017b, page 3) and Jézéquel et al. (2019,\npage 4) for concrete implementation details, but note here that they share the same crucial property as Example 1: the updates can be computed without explicit evaluation of the feature map $\\phi(t)$.\n\n\n> The construction of in Proposition 2 appears somewhat mysterious. Could the authors provide more intuition or motivation behind this particular choice?\n\nThe basic idea is that if we could set $Q(w)=1/|w|$, then using\nproperties of Fourier transforms (namely, that\n$\\int \\hat f(w)\\overline{\\hat g(w)}dw=\\int f(t)\\overline{g(t)}dt$ and\n$|F^{-1}\\[w f(w)\\](t)|\\le|\\nabla f(t)|$) we would naturally relate\n$$\\begin{aligned}\n  \\\\|u\\\\|\\_{H}^{2}=\\int\\frac{ |\\hat u(w)|^{2}}{Q(w)}dw= \\int |w|  \\hat u(w) \\overline{\\hat u(w)}dw \\le \\int |\\nabla u(t)| |u(t)|dt \\le \\max\\_{t}|u(t)| \\\\|\\nabla u\\\\|\\_{L^{1}},\\end{aligned}$$\nwhich is the continuous-time version of the $\\max\\_{t}\\\\|u\\_{t}\\\\|P\\_{T}$\ndependence that we're after. However, this doesn't quite work because\n$Q(w)=1/|w|$ isn't integrable (the integral blows up at 0 and at\n$\\infty$). To fix this, we add extra terms to regularize $Q(w)$ when\n$w\\to 0$ and as $w\\to\\infty$. See our [response to Reviewer HHCS](https://openreview.net/forum?id=4LSulRbbeL&noteId=5BLJtt4cvd) for more\ndetails."}]

Author rebuttal:

Meta-review: This work proposes a novel way to tackle dynamic regret in OCO by reducing it to static regret for an online game in an RKHS. The reduction extends prior work by going beyond linear losses. The resulting algorithms are made computationally tractable by using a kernel trick. The main technical novelty seems to be in designing the right type of shift-invariant kernel. This allows the authors to also take advantage of the curvature of losses, e.g., in special cases the authors are able to preserve exp-concavity of losses and apply an Online Newton-step algorithm in the designed RKHS.

Main concerns raised by reviewers were on the practicality of the algorithm given that the computational and memory complexity will scale with the time-horizon, which is expected due to the kernelization, lack of empirical evaluation and clarity in the writing. This is a theoretical work and it's main contribution is in the reduction to static regret in an RKHS, as such the reviewers have agreed that the practicality issues and lack of empirical evaluation is not a significant enough drawback. I recommend this paper for acceptance and urge the authors to improve the writing as suggested during the reviewing process
Decision: Accept (poster)