Dynamic Regret Reduces to Kernelized Static Regret

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

Yes you are correct, you can think of $\mathcal{X}$ as being $[1,T]$. More generally $[1,T]\subseteq\mathcal{X}$ since we often want to define the kernel outside of this interval for technical reasons. We will make this and the notation more clear.

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?

The form in this example is given as $\psi(\\|w\\|)$ simply because most parameter-free algorithms can be characterized as an FTRL algorithm with a regularizer of this form (see e.g. Jacobsen & Cutkosky 2022). We use this same type of algorithm to derive the guarantee in Proposition 1, by applying it in our kernelized reduction, so the example was meant to illustrate how such an algorithm would be implemented concretely. We will highlight this connection more clearly.

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?

Translation invariant kernels were chosen as an example to show that you can recover the usual $\sqrt{P\_{T}T}$ bound in this framework, and in particular because there is a natural connection between the RKHS norm and path-length when using a translation-invariant kernel (see our response to Reviewer HHCS for details).

However, as you point out, the true potential of the framework is that it opens the door to studying new and interesting ways to characterize the comparator's complexity by measuring it in terms of the rich class of RKHS norms, and indeed this norm need not be associated with a translation-invariant kernel. One example can be seen in Example 3 of Section 5, where the norm is measured using the linear spline kernel and yields a squared path-length $S\_{T}=\sum\_{t}\\|u\_{t}-u\_{t-1}\\|^{2}$ bound rather than the usual $\max\_{t}\\|u\_{t}\\|P\_{T}$.

As another example, suppose you have prior knowledge that the comparator is periodic (e.g. you're forecasting energy demand, which naturally rises and falls during a 24h cycle, for instance). It is possible to account for this prior-knowledge via the RKHS norm $\\|u\\|\_{H}$ and pay only the path-length of a single period, rather than over the whole horizon (comprised of many periods). As a simple illustrative example, consider an alternating comparator sequence $(u\_{t})\_{t}=(0,1,0,1,0,1,\ldots)$. The sequence has path-length $T$ but is interpolated by a triangle function over $[0,2]$ extended periodically, which can be understood as a function in the periodic Sobolev space $H=H^{1}\_{per}([0,2])$ and has $\\|u\\|\_{H}^{2}=\int\_{0}^{2}u(t)^{2}dt + \int\_{0}^{2}u'(t)^{2}dt = O(1)$ and $k(t,t)=O(1)$.

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

The algorithm in section 6 can also be understood as an FTRL algorithm similar to the one in Example 1. The outer products come into the mix because they are used to define a weighted norm. The implementation is analogous, except you replace $||W||^{2}\_{HS}$ with a weighted version, $\\|W\\|\_{t}^{2}=\langle W,\Sigma\_{t} W\rangle\_{HS}$ where $\Sigma\_{t}\approx\sum\_{s=1}^{t}G\_{t}\otimes G\_{t}$ (analogous to the $\sum\_{s=1}^{t}g\_{t}g\_{t}^{\top}$ weighted norm used in "full-matrix AdaGrad").

The kernelized versions of both ONS and the VAW forecaster in Section 5 have known closed-form updates; we defer to Calandriello et al. (2017b, page 3) and Jézéquel et al. (2019, page 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)$.

The construction of in Proposition 2 appears somewhat mysterious. Could the authors provide more intuition or motivation behind this particular choice?

The basic idea is that if we could set $Q(w)=1/|w|$, then using properties of Fourier transforms (namely, that $\int \hat f(w)\overline{\hat g(w)}dw=\int f(t)\overline{g(t)}dt$ and $|F^{-1}$ w f(w) $(t)|\le|\nabla f(t)|$) we would naturally relate

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?

We acknowledge that the naive implementation of kernel methods could lead to undesirable overhead; in this work we have made no attempt to optimize computation and memory overhead so as to focus on developing the base results of the framework, and we are up-front about this limitation in the main text. However, as noted in the main text there is a large body of work studying efficient implementions of kernel methods while incuring acceptable performance trade-offs. Indeed, both the kernelized ONS and kernelized VAW forecaster discussed in section 5 have efficient approximations with well-studied guarantees (Calandriello et al. (2017a,2017b), Jezequel et al. (2019)). We are confident that the overhead can be improved in the OLO setting as well, but given the non-trivial nature of the topic we believe this issue is beyond the scope of the current paper.

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?

The effective dimension is the main penalty that trades-off with $\\|u\\|\_{H}^{2}$ in the curved losses setting; it is necessary to keep both terms in mind when designing the kernel, because lowering one tends to raise the other. How large it can be is tied to the specific kernel. We provide a simple example in Example 3 of how $\lambda\\|u\\|^{2}\_{H}$ and $d\_{\text{eff}}(\lambda)$ can be traded-off to give $S\_{T}^{2/3}T^{2/3}$ bounds, where $S\_{T}=\sum\_{t}\\|u\_{t}-u\_{t-1}\\|^{2}$ is the squared path-length. See also our response to Reviewer qB8Z for additional discussion and intuitions about the effective dimension.

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.

Yes, the argument is essentially the same as it is for exp-concave losses. To see why, observe that under strong convexity what you get is

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.

The effective dimension $d\_{eff}(\lambda)$ is a generalization of the usual notion of dimension. Consider first a finite-dimensional RKHS $H$: if $H$ has dimension $d$, it means that there is an orthonormal basis $(\psi\_{i})\_{i=1}^{d}$ such that any $f\in H$ can be written $f(x)=\sum\_{i=1}^{d}\alpha\_{i}\psi\_{i}(x)$. Here the notion of dimension is the same as the familiar one from linear algebra: the dimension is the number of "directions" you can move in, with the directions characterized by the basis elements $\psi\_{i}$.

In general an RKHS can be infinite dimensional, so there may be infinitely many directions we can move in. However, we can still characterize how many of these directions are "significant". One important basis of an RKHS is obtained as the eigenfunctions of an integral operator related to the kernel, and the effective dimension measures how many of these eigenfunctions are associated with a "non-neglible" eigenvalue $\sigma\_{1}\ge\sigma\_{2}\ge\ldots\ge 0$. That is, let $t\_{0}$ be the first $t$ such that $\sigma\_{t}< \lambda$, then

I thank the authors for their response and clarification, and I have decided to keep my score.

What intuition drives the logarithmic spectral density in Proposition 2

The key intuition is to observe that the ideal choice of density would be $Q(w)=1/|w|$. Indeed, we would have (loosely speaking)