- Rating
- 4(+1)
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The authors propose a new method for theoretical analysis of the regret of online prediction algorithms where the optimal predictor is allowed to change. This setting is not new, but the authors report order-wise improved regret bounds compared to prior literature.
Critical strengths
The paper is very well written. For a work like this which basically proposes a new idea for how to prove regret bounds, it is very important to give the reader a good intuitive understanding as well as a convincing technical argument. From what I can see, the authors are doing a really good job at this. I am not an expert on the topic of dynamic regrets and was able to easily understand the problem, the idea applied to solve it, and how it works on a high level. I also checked part of the detailed technical proofs and had the impression that they are sound. I have done a quick literature search on the topic and did not find any omissions in the literature survey that would impact on the novelty/significance of the paper's contributions.
Critical weaknesses
The biggest weakness in my opinion is that the significance of the reported improvements is not very well argued. While the overview table in Section 1 does a good job at comparing and contrasting with results from prior work, it remains unclear why the reported improvements are significant. In particular, I would strongly suggest the authors make the following additions to the paper:
W1) Discuss more explicitly why the order-wise improvements reported in the table in Section 1 matter. As far as I can see, the only clear improvement over all the prior works is the dependence on dimension d. I view it as symptomatic that d is not even defined in the introduction (I have to admit I am still not fully sure of which space it is the dimension). I think a definition should be added, as well as a discussion of what values d can typically take in relevant problems and how the improvement impacts the usefulness of the regret bound.
W2) In their comparison to prior work, the authors also emphasize that their approach is "efficient", resp. implementable, and more so than at least some of the prior works. In my opinion, such claims should always come accompanied with a numerical case study. That would also provide an opportunity to give non-asymptotic regret bounds at least for an example to see how the various bound compare at "realistic" values of time horizon and dimension.
If space does not allow for these additions, I think all or part of Section 5 could probably be moved to the appendix. As I said, I really like the paper overall, so if the authors address these points in a way I find satisfactory, I am happy to increase my score.
Questions for authors
For my main questions to the authors, see W1 and W2 above. A few additional things:
Q1) I think there is probably a sup/max missing in eq. (1).
Q2) There seems to be a body of literature on dynamic regret that uses metrics other than the path length, such as for example the "episode length" (and quite possibly a bunch of other things as well). Also, there are other ways to restrict the loss, e.g., linear losses. While I understand that the scope of the literature survey needs to be somewhat limited in a research paper, I still believe that providing a bit of an overview and a discussion of what specific advantages a focus on the path length has would increase the value of the paper. A few examples of papers I came across that are not mentioned in the literature survey:
https://proceedings.mlr.press/v206/baby23a.html
I want to emphasize however, that I do not have a good overview of this topic and have not come across any missing references that would impact on the novelty/significance of the present paper's contributions.
2 comments
Thank you for the reply. I would suggest that you add the (relatively minor) clarifications and additional literature discussions to the paper as outlined in your response (I couldn't find those added yet while looking through the revised version).
However, I've seen you've already added a numerical comparison. Since that being missing was my main concern, I'll raise my score even though the other, more minor revisions are still outstanding.
Many thanks for the constructive reviews!
Q1: Clarification of the dimension d and significance of the improved dimension dependence.
A1: Thanks for the valuable suggestion. Here, d denotes the dimension of the decision space, i.e., X⊆Rd. In applications such as online linear prediction, d corresponds to the number of model parameters, which can be very large. Therefore, reducing the dependence on d in regret bounds is particularly important in high-dimensional applications. We will incorporate an explicit definition of d in the introduction of the revised version.
Q2: Numerical evidence for computational efficiency and finite-time guarantees.
A2: Thanks for the thoughtful advice. Theoretically, our detailed comparison in A1 to Reviewer Sb4H shows that our method has the same order of time complexity as [1,2,3], whereas the cost of [4] is difficult to quantify due to its complex Gaussian-mixture updates and KL projections. Empirically, we have added numerical comparisons with prior methods to the section Experiments of the revised version (highlighted in red), and also report the running times in the following table:
The results demonstrate the computational efficiency of our method: its running times are comparable to those of [1,2,3] for general convex and strongly convex losses, and it requires about 77% less time than [4] for exp-concave losses.
Q3: Clarification of the dynamic regret definition in Eq. (1).
A3: Thanks for the helpful suggestion. Eq. (1) follows a standard definition of dynamic regret in Online Convex Optimization (OCO) [1,2,3,4], where dynamic regret is measured against an arbitrary comparator sequence u1:T, and no supremum or maximum is required.
Q4: Broader literature coverage and motivation for focusing on path length.
A4: Thanks for the thoughtful comments. We focus on the path-length PT because it directly measures the total movement of an arbitrary comparator sequence, capturing both gradual drift and abrupt changes. It is also widely used in OCO [1,2,3,4], so that we can compare our dynamic regret bound with those of other methods. Moreover, this metric fits our reduction naturally, since the expected number of switches in the auxiliary sequence is provably bounded in terms of PT (see Lemma 1).
Beyond the path-length PT, there are some studies investigating other metrics to dynamic regret. Specifically, [5] studies second-order path variation, which measures how the differences between consecutive comparator values change over time. [6] develops a reduction from dynamic regret to static regret using a Reproducing Kernel Hilbert Space (RKHS), with theoretical guarantees in terms of PT for linear losses and the RKHS norm of comparators for strongly convex and exp-concave losses. [7] studies episodic reinforcement learning and establishes dynamic regret bounds that depend on the episode length (the number of steps per episode) and the cumulative changes in the comparator across episodes. These studies offer complementary perspectives on dynamic regret. We will include a detailed discussion in the revised version.
[1] Adaptive online learning in dynamic environments. 2018.
[2] Optimal dynamic regret in exp-concave online learning. 2021.
[3] Optimal dynamic regret in proper online learning with strongly convex losses and beyond. 2022.
[4] Non-stationary online learning for curved losses: Improved dynamic regret via mixability. 2025.
[5] Second order path variationals in non-stationary online learning. 2023.
[6] Dynamic regret reduces to kernelized static regret. 2025.
[7] Near-optimal dynamic regret for adversarial linear mixture MDPs. 2024.