An Equivalence Between Static and Dynamic Regret Minimization

My major concern is the main titile could be somewhat overclaimed, as the proposed reduciton is restricted in OLO

We actually believe that our title is carefully worded to avoid overclaiming: we do indeed present an equivalence between static and dynamic regret --- it is one which holds in a particular context, and our abstract and introduction state very clearly the scope of this work. Note also that, as discussed in this comment, the equivalence can be applied more generally for OCO.

That said, we do not think this is a big issue either way: we can add "for Linear Losses" to the title if it solves the major concern of the reviewer.

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

Computational complexity is indeed one of the main considerations when choosing the dual norm pair $(\\|\cdot\\|,\\|\cdot\\|_{*})$ (i.e., choosing the matrix $M$ in the context of Theorem 2), and we do discuss it on page 4, line 136. Moreover, the computational complexity of the algorithm achieving the smoothed square path-length bound (characterized in Proposition 3) is discussed on page 8.

We can add some additional discussion regarding the related implementation concerns. Note that these concerns are shared by all other dynamic regret algorithms achieving a non-trivial dependence on the comparator variability, as our algorithm can be implemented with the same computational $O(d\log T)$ per-round complexity as prior works, as discussed on page 8.

Does the high-dimensional embedding reduction also hold for adpative regret (to static regret)?

No, adaptive regret involves making guarantees over all sub-intervals simultaneously, while the proposed reduction explicitly considers the total loss over the entire interval $[1,T]$. These are quite separate notions of performance and there is no known general equivalence between them.

Can we directly design a unified algorithm (best-of-both-worlds) without knowing the types of regret based on this reduction?

If by types of regret you are referring to static vs. dynamic regret, the answer is yes: in fact, our guarantee in Theorem 2 captures static regret as a special case. If by types of regret your are referring to adapting to various different measures of variability (e.g., Theorem 2 with different choices of $M$), the answer is also yes: see the last part of our global response here for details.

The reasons for choosing this locally-smoothed square path-length is not clear. If I get it right, path-lengthes sharing similar local-smoothness would all fullfill the requirements. Meanwhile, this locally-smoothed square path-length is too detailed such that it may loose empirical intuitions or physical meanings to some extent.

Due to space constraints, please see our global response here for a detailed discussion of these concerns.

My question: The lower bound is $\tilde\Omega (\max\_{M}G\\|\tilde u\\|\_{M^{-1}}\sqrt{\mathrm{Tr}(M)})$, and the upper bound essentially is $\tilde O(\min\_{M}G\\|\tilde u\\|\_{M^{-1}}\sqrt{\mathrm{Tr}(M)})$.

There seems to be a misunderstanding of the quantification of $M$ in the lower and upper bounds. The lower bound holds for any $M$ satisfying the conditions, not just for the worst-case $M$. Similarly our upper bound holds for any valid choice of $M$ rather than just the best one. So the upper and lower bounds do indeed match.

To clarify the ideas, it might be useful to compare it, for example, with online mirror descent with $p$-norms: there exist upper and lower bounds that both hold for any $p$, not just with the best/worst ones.

Thank you for the positive review, we are glad you enjoyed reading our paper!

I would like to know which measures of variability the authors expect to obtain with different choices of that yield reasonable and significant regret bounds.

So far the literature mostly revolves around the (unsquared) path-length as the measure of variability. One of the exciting things about this work is that it opens the door for many unexplored directions in terms of the variability measure, and provides a convenient framework for studying new notions of variability and their trade-offs. In this work, we focused on achieving results related to squared path-length, but it may be possible to achieve results scaling with more general distance metrics, for instance by leveraging the notion of group norms. The variance-variability coupling guarantees in Section 5 are also a very open and almost entirely unexplored direction that we would like to investigate further.

The abstract claims that "we show that dynamic regret minimization is equivalent to static regret minimization in an extended decision space." This claim is somewhat misleading to me, as the proposed reduction only applies to the online linear optimization problem (or OCO with linearized surrogate loss). It is unclear if the proposed reduction holds for a broader range of dynamic regret minimization problems, such as those involving exp-concave or strongly convex loss functions.

The proposed reduction can be applied to any convex losses, including strongly convex and exp-concave losses, by bounding $\sum_{t=1}^{T}\ell_{t}(w_{t})-\ell_{t}(u_{t})\le \sum_{t=1}^{T}\langle g_{t},w_{t}-u_{t}\rangle= R_{T}^{\text{Seq}}(\tilde u)$ via convexity.

We can also be more precise, obtaining an equality for convex losses, by observing that $\begin{aligned} \sum_{t=1}^{T}\ell_{t}(w_{t})-\ell_{t}(u_{t})=\sum_{t=1}^{T} \langle g_{t},w_{t}-u_{t}\rangle-D_{\ell_{t}}(u_{t}\|w_{t})\end{aligned}$ by definition of Bregman divergences. Since this is an equality, any possible improvements that one might hope to leverage in settings with curvature are reflected in the terms $-D_{\ell_{t}}(u_{t}\|w_{t})$, while our reduction can be applied to the first term, $\sum_{t=1}^{T}\langle{g_{t},w_{t}-u_{t}}\rangle=R_{T}^{\text{Seq}}(\tilde u)$. As is usually the case, one should design their algorithm in such a way that these curvature terms $-D_{\ell_{t}}(u_{t}\|w_{t})$ are properly leveraged in the end. For instance, for strongly-convex losses in the static regret setting, Algorithm 6 of Cutkosky & Orabona (2018) provides a reduction for OLO which makes a guarantee that implies logarithmic regret when the curvature terms satisfy $-D_{\ell_{t}}(u\|w_{t})\le -\frac{\alpha}{2}\\|u-w_{t}\\|^{2}$ (that is, when the losses are $\alpha$-strongly convex). A similar reduction could potentially be applied here and would be an interesting direction for future investigation.

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

$\...$ it might be beneficial to explicitly state that previous work

has already somewhat demonstrated equivalence between the dynamic regret minimization and static regret minimization problems.

The key difference is that we provide a general equivalence between static and dynamic regret that any strategy can be plugged into, while Zhang et al. (2023) provide a reduction which prescribes a particular strategy which allows the user to leverage static regret minimizers for dynamic regret. That is, our Proposition 1 holds regardless of what strategy you end up choosing to set $w_{t}$, and simply shows that writing the dynamic regret in a different way leads to static regret in a different decision space. Because there is no restriction on how $w_{t}$ is set, our proposition actually captures the approach of Zhang et al. (2023) as a special case. Note that this also demonstrates that there is no choice of dictionary in the framework of Zhang et al. (2023) from which Proposition 1 can be derived --- Proposition 1 is strictly more general.

In contrast, the approach proposed by Zhang et al. (2023) requires that the designer commit to choosing $w_{t}=\mathcal{H}\_{t}x\_{t}$ for some matrix $\mathcal{H}\_{t}$ and where the coordinates of $x_{t}$ are separate 1-dimensional learning algorithms. Because their approach prescribes a strategy that the user must design around, their approach does not imply an equivalence between dynamic and static regret, but rather provides a reduction that allows one to leverage a particular class of static regret algorithms to design dynamic regret algorithms. This potentially limits the types of guarantees that can be achieved using the approach; for instance, the algorithm achieving the smoothed path-length result in Section 4.1 can not be represented in their framework, since it does not use separate coordinate-wise 1-dimensional updates.

it is still unclear to me how the proposed reduction can be applied to minimize the dynamic regret bound for exp-concave or strongly convex functions.

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

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

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

I think there may be some misunderstanding from the authors regarding my previous response. My intention was never to criticise the paper for not achieving improved dynamic regret for exp-concave functions. Rather, it is taken as an example to illustrate that some parts of the paper are overstated, as evidenced by the claim I referenced earlier. Nevertheless, I appreciate the authors' efforts in making the revisions.

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

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

Do you believe there are any implications of your reduction that are particularly useful from a practical/deployment perspective, or do you see the contribution as being a strictly conceptual one?

We believe that the most important implication is that the reduction allows us to use any present and, more importantly, future result from static online learning, to solve dynamic regret problems. For example, the algorithm that we show in Section 4.1 has the same computational complexity as previous ones (such as Zhang et al. (2018), Jacobsen & Cutkosky (2022), and Zhang et al. (2023), to name a few) so it has the same applicability as these works.

Practically speaking, in many real-world problems the "solution" to the problem (represented, e.g., by the ideal model parameters) can change over time, due to unpredictable changes in environment or underlying data-generating process. These changes to the solution are captured by the time-varying comparator in dynamic regret. A major benefit of these comparator-adaptive dynamic regret guarantees is that the algorithm automatically adapts to this changing comparator sequence, without requiring any prior knowledge whatsoever about this sequence or how it is changing. We believe this is an exceptionally powerful property which is indeed useful from a practical/deployment perspective.

Do you have any additional intuition for the locally-smoothed path-length quantity? For example, how smoothed would one generally expect this quantity to be?

Due to space constraints, please see our global response here for a detailed discussion of these concerns.

The authors stated that $P_T$ based dynamic regret is not favorable enough with an overly pessimistic diameter quantity.

The relationship between the current averaged squared length and the desired squared length is not discussed

Given that the smoothed version of squared path-length is a new notion of variability, it is natural to show that it is always at least as good as the standard notion of variability. However, it should be clear this is only a sanity check and this notion can often be much better since it does not incur the pessimistic diameter penalty. Please see our global response for a detailed discussion.

The obtained regret also suffers from additional terms, which is not favorable enough in the full information setup. Do previous works?

All prior works which achieve dynamic regret guarantees in unbounded domains do indeed incur additional logarithmic penalties, even in the full information setting. See Jacobsen & Cutkosky (2022,2023) and Zhang et al. (2023). Similar to the static regret setting, such logarithmic penalties appear to be the price paid for achieving adaptivity to an arbitrary comparator sequence. Such penalties are known to be necessary in online learning with unbounded domains, see the lower bound in Orabona (2013), and recently proved in the stochastic setting as well by Carmon & Hinder (2024). Works which assume a bounded domain, such as Zhang et al (2018) can avoid this additional term because they are leveraging prior knowledge about the comparator sequence, ie, that $\\|u_{t}-w_{1}\\|\le D$ for all t. In this work, we focus on achieving novel guarantees in the unbounded setting, though our reduction in Proposition 1 is applicable in the bounded setting as well.

the computational complexity of the reduction is not discussed

The computational complexity is related to the choice of $M$, and is one of the main considerations that one must consider when choosing $M$. This is discussed on page 4, lines 136-138. In fact, one of the key properties of the $M$ we choose in Proposition 3 is that it supports sparse updates, requiring $O(d\log T)$ per-round computation to update the algorithm, matching the computational complexity enjoyed by prior works in this setting. This is discussed on page 8, starting on line 243.

proposition 2 only shows that choosing a specific M does not suffice

This is a very good point, thanks for raising it. The choice of $M$ uniquely exposes the squared path length up to a constant offset term, but it is easy to see that the offset term does not make any difference for our claim. To see why, consider the 1-dimensional setting and note that for any positive definite $M$ there is a unique $\Sigma$ such that $M=\Sigma^{\top}\Sigma$. Hence, without loss of generality we can focus on $\Sigma$ satisfying

for some $v\in\mathbb{R}^{T}$ and such that $M=\Sigma^{\top}\Sigma$ is positive definite. Note that the constant offset term is unavoidable: it is what captures the static regret guarantee in the case where $u_{1}=\ldots=u_{T}=u$. Proposition 2 considers $v=(0,\ldots,0,1)$ to get $\\|\tilde u\\|^{2}\_{M}=\\|u_{T}\\|^{2}+\sum\_{t=2}^{T}\\|u\_{t}-u\_{t-1}\\|^{2}$, though below we will show that any vector $v$ would still lead to $Tr(M^{-1})=\Omega(T^{2})$.

It is clear that the only way to construct expressions of the form above is via matrices $\Sigma$ satisfying $\Sigma\tilde u=c\begin{pmatrix}u\_{1}-u\_{2}\\\\ u\_{2}-u\_{3}\\\\\vdots\\\\u\_{T-1}-u\_{T}\\\\ \langle v,\tilde u\rangle\end{pmatrix},$ where $c\in\{-1,1\}$ and the order of the rows indices of the vector can be permuted without loss of generality. In particular, the only matrices that can produce these expressions (again noting that the rows can be permuted without loss of generality) are of the form

so $M=\Delta^\top\Delta + v v^\top$. Adding a rank-1 update to $\Delta^{\top}\Delta$ will increase its eigenvalues $\lambda_{i}=\lambda_i(\Delta^{\top}\Delta)$ by some $a_{i}\ge 0$, such that $\sum_{i}a_{i}=\\|v\\|^2$. Moreover, there is a unique zero eigenvalue of $\Delta^{\top}\Delta$, corresponding to the eigenvector $(1,\ldots,1)/T$. Therefore, $Tr(M^{-1})=1/a_{1}+\sum_{i>1}\frac{1}{\lambda_{i}+a_{i}}$. This implies that the worst-case choice of $a_{1},\dots,a_{T}$ is given by a convex constrained optimization problem which yields $a_{i}=0$ for $i>1$ and $a_{1}=\\|v\\|^2$ via the KKT conditions. Hence, the worst-case choice of $v$ is the one which increases only the eigenvalue corresponding to the uniform eigenvector, so the worst case choice of $v$ is proportional to the uniform eigenvector and $Tr(M^{-1})\ge \Omega(\frac{1}{\\|v\\|^2}+\sum_{i>1}\frac{1}{\lambda_{i}})\ge \Omega(\sum_{i>1}\frac{1}{\lambda_{i}(M_{0})})$, where $M_{0}$ is the matrix from Proposition 2, obtained by setting $v=(0,\dots,0,1)$. Notably, from the proof of Proposition 2 it can be seen that even if we dropped the largest eigenvalue of $M_{0}^{-1}$, we would still have $Tr(M^{-1}_0)\ge \Omega(T^{2})$. Hence, any of the matrices which produce the squared path-length dependence must incur the same $\Omega(T^{2})$ variance penalty up to constant factors. We will expand this reasoning into a more formal proof in the paper and we can provide additional details if needed, but the above claims can be easily verified numerically.