acceptodds
Under review as a conference paper at ICLR 2027

From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

Abstract

In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, existing methods to attain optimal dynamic regret bounds for strongly convex losses and exp-concave losses remain analytically intricate or computationally demanding. In this paper, we present a simple framework that reduces dynamic regret minimization to switching regret minimization. The key idea is to construct, for any comparator sequence, an auxiliary random sequence that is unbiased at each round, with controlled variance and a manageable number of switches. Combining this construction with suitable surrogate losses, we decompose dynamic regret into the expected switching regret against the infrequently-changing random sequence and a variance-controlled approximation error. Consequently, any algorithm with a switching regret guarantee can be plugged into our framework to obtain a corresponding dynamic regret bound. In particular, by instantiating the framework with existing switching-regret algorithms, we can obtain an dynamic regret bound for strongly convex losses and for exp-concave losses, where denotes the path-length and denotes the dimension. For general convex losses, the same reduction recovers the dynamic regret bound. Notably, all our findings match the known minimax-optimal bounds, up to logarithmic factors, and the modularity of our framework makes it easy to understand and implement.

Primary area:
optimization
Keywords:
online convex optimization, dynamic regret, switching regret

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_aaCiOpenReview ↗
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

https://proceedings.neurips.cc/paper_files/paper/2025/hash/fc7f90ed14864bef5cafa89ba38f1993-Abstract-Conference.html

https://proceedings.neurips.cc/paper_files/paper/2024/hash/656678aa961a99a6a3d59bfbf88daf77-Abstract-Conference.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

Many thanks for the constructive reviews!


Q1: Clarification of the dimension dd and significance of the improved dimension dependence.

A1: Thanks for the valuable suggestion. Here, dd denotes the dimension of the decision space, i.e., X⊆Rd\mathcal{X} \subseteq \mathbb{R}^d. In applications such as online linear prediction, dd corresponds to the number of model parameters, which can be very large. Therefore, reducing the dependence on dd in regret bounds is particularly important in high-dimensional applications. We will incorporate an explicit definition of dd 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:

MethodGeneral ConvexStrongly convexExp-concave
[1]4.55s--
[2]-4.53s11.66s
[3]-5.56s11.72s
[4]--43.68s
This work4.01s4.67s10.16s

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:Tu_{1: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 PTP_T 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 PTP_T (see Lemma 1).

Beyond the path-length PTP_T, 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 PTP_T 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.

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.

Reviewer_Sb4HOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors study dynamic regret in online convex optimization. Specifically, they develop a reduction from dynamic regret to switching regret, which can be optimally exploited once a random sequence of dynamic baselines with few switches, whose expectation is close to the true one, is built. They first show how to build this sequence and then employ a standard switching regret minimiser to obtain optimal bounds for convex, strongly convex, and exp-concave losses.

Critical strengths

The idea behind the results of the paper is as simple as it is interesting. I was already aware of the link between switching and dynamic regret, but the idea that it would be possible to build a random sequence to exploit the relation is very elegant.

Overall, I also believe that the paper is quite well written, apart from a couple of aspects that I highlight in the weaknesses section.

Critical weaknesses

The main weakness is that the authors claim that their results are of particular interest since their algorithm is more efficient than existing ones. While I understand that their proofs are quite simple and elegant, I think that the comparison of efficiency should be better formalised. For instance, the authors use switching regret algorithms as black boxes, but it is not clear how their computational complexity compares with that of their dynamic regret counterparts.

It is also a little bit hard to understand how novel this approach is. For instance, is this really the first paper to study the connection between switching and dynamic regret in depth?

Questions for authors

See Weaknesses.

3 comments

Many thanks for the constructive reviews!


Q1: Comparisons of computational complexity with existing methods.

A1: Thanks for the valuable suggestion. The following table compares the total computational complexity of our method with that of existing approaches over TT rounds.

MethodGeneral ConvexStrongly convexExp-concave
[1]O(Tlog⁡T)O(T\log T)--
[2]-O(Tlog⁡T)O(T\log T)O~(d3Tlog⁡T)\widetilde{O}(d^3T\log T)
[3]-O(Tlog⁡T)O(T\log T)O~(d3Tlog⁡T)\widetilde{O}(d^3T\log T)
[4]--O(T(Cupdate+CKL))O(T (C_{\text{update}} + C_{\text{KL}}))
This workO(Tlog⁡T)O(T\log T)O(Tlog⁡T)O(T\log T)O~(d3Tlog⁡T)\widetilde{O}(d^3T\log T)
  • For general convex losses, our method employs the switching-regret algorithm RESET [5], which aggregates O(log⁡T)O(\log T) OGD experts. [1] also maintains O(log⁡T)O(\log T) OGD experts, so both methods incur O(Tlog⁡T)O(T\log T) total computational cost.

  • For strongly convex losses, our method uses IRESET [6], which aggregates O(log⁡T)O(\log T) OGD experts and incurs a total computational cost of O(Tlog⁡T)O(T\log T). [2, 3] use adaptive-regret algorithms to aggregate OGD experts, and their efficient versions maintain O(log⁡T)O(\log T) experts per round, yielding the same O(Tlog⁡T)O(T\log T) total computational cost.

  • For exp-concave losses, we run IRESET [6] with O(log⁡T)O(\log T) ONS experts, requiring O~(d3Tlog⁡T)\widetilde{O}(d^3T\log T) total computation with O~(d3)\widetilde{O}(d^3) cost per ONS update. Similarly, [2,3] also maintain O(log⁡T)O(\log T) ONS experts, resulting in O~(d3Tlog⁡T)\widetilde{O}(d^3T\log T) total cost. In [4], each round involves updating a Gaussian-mixture distribution and then performing a KL projection:

    $P'_{t+1}(u)\propto P_t(u)\exp\left(-\frac{\gamma}{2}\widetilde f_t(u)\right),\quad \widetilde P_{t+1} =\arg\min_{Q\in\mathcal M}\mathrm{KL}\left(Q|P'_{t+1}\right),$

    where M\mathcal M is the constrained family of Gaussian-mixture distributions. Let $C_{\mathrm{update}} $ and CKLC_{\mathrm{KL}} be the costs of the distribution update and KL projection, respectively. Implementing these steps, particularly the KL projection, poses non-trivial computational challenges, and an efficient implementation for exp-concave losses remains unclear. We therefore denote their total cost as O(T(Cupdate+CKL))O(T(C_{\mathrm{update}}+C_{\mathrm{KL}})) in the table.

It should be highlighted that while our method has computational costs comparable to those of [1, 2, 3], it provides an elegant and unified framework for deriving dynamic regret bounds for all three types of losses with improved dependence on the dimension dd.


Q2: Novelty.

A2: We would like to emphasize that, to the best of our knowledge, our paper provides the first unified black-box reduction converting switching-regret guarantees into dynamic-regret bounds for all three types of losses. In the literature, [5] also derives dynamic regret bounds for the switching-regret algorithm RESET under general convex losses, but this requires modifying its original analysis. In contrast, our reduction uses only switching-regret guarantees in a black-box manner, without reanalyzing the internal structure or modifying the updates of the underlying algorithms, and also applies to strongly convex and exp-concave losses.


[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] Online convex optimisation: The optimal switching regret for all segmentations simultaneously. 2024.

[6] Logarithmic switching regret for online convex optimization. 2026.

I thank the Authors for the responses. I will keep my current score.

We sincerely appreciate your recognition and support! We will clarify the points raised during the discussion in the final version.

Reviewer_to3pOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

By constructing a reduction to switching regret minimisation, the paper provides a simple and elegant analysis for controlling universal dynamic regret, especially for losses with curvature. The framework greatly simplifies prior analyses and opens the door to simple algorithms for dynamic regret minimisation.

Critical strengths

The paper provided a simple analysis to a hard problem and establishes a foundational principle that one only needs to control the switching regret to automatically control the dynamic regret. I believe this work can inspire future research like problem-dependent bounds on universal dynamic regret minimisation.

Critical weaknesses

I do not have any major concerns.

Their proposed low-switching comparator makes the analysis seamlessly go through. However, it is unclear why one can expect the existence of such a sequence from an intuitive standpoint. Does it have a deeper implication to non-parametric regression or function approximation?

Questions for authors

In addition to exp-concavity, the losses they consider need to have bounded lipschitz constants for the proposed regret bounds to be meaningful. This can be a bit unattractive for log loss which is used in universal portfolio optimization. The gradients of log loss spikes up near origin. There is a recent paper about universal dynamic regret for online portfolio selection: https://arxiv.org/abs/2609.34643 Can you comment if the simpler analysis you developed can be applicable / extended naturally to the above case?

In the manuscript, please consider explaining why the proposed surrogate losses can upperbound the regret wrt original losses. This can make the paper more reader-friendly and self-contained.

3 comments

Many thanks for the constructive reviews!


Q1: Intuition behind the unbiased low-switching sequence and its connection to non-parametric regression or function approximation.

A1: Thanks for the insightful comment. The motivation comes from the need to control the approximation error in a switching-to-dynamic reduction. Specifically, we aim to approximate a moving comparator by a sequence with few switches while keeping the approximation error small. For the smooth surrogate losses in (8), an unbiased random approximation cancels the first-order term in expectation, leaving only a second-order error controlled by the variance. This motivates us to construct a random sequence that is simultaneously unbiased and infrequently changing. To achieve this, we keep the random sequence unchanged with high probability when the comparator moves only slightly and occasionally reset it to a suitable point. If we retain the previous value with probability 1−pt1-p_t and reset it to ata_t otherwise, unbiasedness requires (1−pt)ut−1+ptat=ut(1-p_t)u_{t-1}+p_ta_t=u_t. This relation determines the reset point ata_t, whose value compensates for the small update probability so that the mean still matches the comparator utu_t. We choose ptp_t based on the movement magnitude and an approximation scale to balance the expected number of switches against the variance. The construction therefore combines infrequent updates with first-order error cancellation in expectation.

We believe there is a connection between this intuition and function approximation. Specifically, if we view the comparator sequence as sampled values of a function, our construction provides a randomized piecewise constant approximation to these values. The number of switches measures how often the approximation changes, while the variance measures its expected squared error. A similar trade-off between the number of constant pieces and the approximation error also arises in nonparametric regression. A key property of our construction is that the approximation remains unbiased at every time step, so its expectation matches the original value.


Q2: Applicability to portfolio log loss with unbounded gradients.

A2: Thanks for the thoughtful consideration. In our analysis, the Lipschitz assumption is used to control approximation errors and apply the switching regret guarantees, and the construction of the auxiliary random sequence does not depend on it.

For portfolio log loss with unbounded gradients, [5] shows that an O~(T1/3PT2/3)\widetilde{O}(T^{1/3}P_T^{2/3}) dynamic regret bound cannot hold uniformly under the standard path length. Instead, [5] introduces the Jensen–Shannon (JS) path length and obtains an O~(T1/3PJS2/3)\tilde{O}(T^{1/3}P_{\mathrm{JS}}^{2/3}) bound by combining fixed-share updates with a mixability-based analysis using Dirichlet comparator distributions. Based on these ideas, we extend our reduction to portfolio log loss by using Dirichlet marginals to bound the expected approximation error and maximal coupling to control the expected number of switches. Combining these bounds with the interval regret guarantee in [5, Proposition 6] and balancing the two terms recovers the dynamic regret bound in terms of the JS path length, without assuming bounded gradients. We have also added a preliminary extension to the appendix of the revised version (see the section Extension to Portfolio Log Loss, highlighted in red).


Q3: Please consider explaining why the surrogate regret upper-bound the original regret.

A3: Thanks for the helpful suggestion. We will include the detailed derivations in the revised version to make it clearer.


[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] Universal dynamic portfolios. 2026.

I thank the authors for the response. I will maintain my score.

I encourage the authors to summarize the portfolio extension in the main text, explicitly presenting it as a simpler coupling-based derivation of Zhang et al. (2026)’s guarantees. Please distinguish the new proof from the prior work’s enabling ingredients, including its Dirichlet comparator construction, variation bound, and portfolio algorithm, rather than presenting the recovered rates as new. This would give the prior work the credit it deserves while also highlighting the present paper’s contribution.

Many thanks for your valuable suggestions! We will incorporate them into the final version.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.