Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability
Authors: Yu-Jie Zhang
Peng Zhao
Masashi Sugiyama
Venue: ICML 2025 poster (2025)
Keywords: Online Learning
Dynamic Regret
Mixability
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability

Abstract: Non-stationary online learning has drawn much attention in recent years. Despite considerable progress, dynamic regret minimization has primarily focused on convex functions, leaving the functions with stronger curvature (e.g., squared or logistic loss) underexplored. In this work, we address this gap by showing that the regret can be substantially improved by leveraging the concept of mixability, a property that generalizes exp-concavity to effectively capture loss curvature. Let $d$ denote the dimensionality and $P_T$ the path length of comparators that reflects the environmental non-stationarity. We demonstrate that an exponential-weight method with fixed-share updates achieves an $\mathcal{O}(d T^{1/3} P_T^{2/3} \log T)$ dynamic regret for mixable losses, improving upon the best-known $\mathcal{O}(d^{10/3} T^{1/3} P_T^{2/3} \log T)$ result (Baby & Wang, 2021) in $d$. More importantly, this improvement arises from a simple yet powerful analytical framework that exploits the mixability, which avoids the Karush–Kuhn–Tucker-based analysis required by existing work.

Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability
Yu-Jie Zhang'
Peng Zhao?
Masashi Sugiyama 13
Abstract
romment. At each round t [T] (1...., the learner submits prediction w, E W from a convex set W S R while the environment simultaneously generates a convex loss function ft W + R. Then, the learner incurs a loss of fa (w,) and observes the function ft for model update. In non-stationary environments, the dynamic regret (Zinke- vich, 2003), which compares the learner's prediction with time-varying benchmark {ur
Non- Non-stationary online learning has drawn much attention in recent years. Despite considerable progress, dynamic regret minimization has pri- marily focused on convex functions, leaving the functions with stronger curvature (c.g., squared or logistic loss) underexplored. In this work, we address this gap by showing that the regret can be substantially improved by leveraging the con- cept of mixability, property that generalizes exp- concavity to effectively capture loss curvature. Let d denote the dimensionality and Pr the path length of comparators that reflects the environ- mental non-stationarity, We demonstrate that an ssponential-weighe method with fxed-share up- dates achieves an (dT p log 7') dynamic regret for mixable losses, improving upon the best- known (310/3/1/3 p2 log T') result (Baby & Wang, 2021) in d. More importantly, this improve- ment arises from a simple yet powerful analyti- cal framework that exploits the mixability, which avoids the Baanish-KunnTTuuckee required by existing work.
D-REGr((u Σ f((ws) f((.). (1)
is commonly used to evaluate algorithms and guide their design. The dynamic regret (1) is usually called the "univer- sal" dynamic regret as it holds for all comparator sequences. The universal dynamic regret not only recovers static regret by u, u arg min Σ fi (w) for all [7'. but also provides the flexibility to compare against any time- varying benchmark suited to the environment.
Over the years, dynamic regret minimization has been exten- sively studied for convex losses. Zinkevich (2003) showed that online gradient descent (OGD) with step size 1 > 0 achieves dynamic regret bound of O(1 + Pr)/n + nTT), which adapts to the path length
analysis
1. Introduction
Pr UT)
Σ uu u
Non-stationary online learning, which investigates how to learn from sequences of data in dynamic environments, has attracted considerable attention recently (Besbes et al., 2015;
reflecting the non- con-stationarity of the environments. Once the path length is known, the step size can be optimally tuned to n. = O(V(L Pr)/T). This choice yields the minimax optimal dynamic regret bound of O ((VT(1 + Pr)). How- ever, given the universality of the comparator sequence, the path length is typically unknown, making optimal tuning infeasible. This highlights a fundamental challenge dy- namic regret minimization: how to handle the uncertainty of non-stationary environments. Zhang et al. (2018) addressed this issue by proposing a two-layer method that performs grid search over possible path lengths, achieving the min- imax optimal bound without knowledge of Pr. Beyond the minimax rate, the path-length based dynamic regret bound has attracted lots of interest for achieving problem- dependent bounds that adapts to the inherent hardness of the
Zhang et al., 2018; Cutkosky, 2020; Baby Wang, 2021; Wei & Luo, 2021; Zhao et al., 2022; Li et al., 2024; Zhao al., 2024). A standard formulation for online learning is the online convex optimization (OCO) (Hazan, 2016), which involves a T-runnd process between the learner and the envi-
RIKEN AIP, Japan "National Key Laboratory for Novel Software Technology. Nanjing University, China 'The Univer- sity of Tokyo, Japan. Correspondence to: Yu-Jie Zhang <yu- jic. thanzhang @ jpk, Peng Zhao <zhaop@lamda.nj hinnda.ju.edu.cn..
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Table 1: Comparison on dynamic regret and other issues on typical curved loss functions. * denotes that the method is proper learning
when Wis is an Loo ball. f indicates that the time complexity can be improved to (log 2') with additional logarithmic factors in the regret.
Losses
Method
Regret Bound
Proper Learning
Time Complexity
1-dim squared loss (z g)²
Baby & Wang (2021, Theorem 1)
Ø(1 + p2/)
Yes
O(T))
Corollary 1
0 + T4:3
Yes
((T)
I squarrs regression (w/)
Baby & Wang (2022b, Theorem 5)
O(d+d /3
Yes
O(T)
y)²
Corollary 2
Old p
No
O(T')
Logistic regression log(1 +e yw
Baby et al. (2023, Theorem 3.1)
Yes
O(T')
Corollary 3
Old+
No
poly(7)
General
Baby & Wang (2022a, Theorem 10)
Old //d+/0/////pp1/
No (in general)*
O(T))
exp-concave loss
Theorem
Old + dr
Yes
learning problem (Zhao et al., 2020; 2024), being parameter- free (Cutkosky, 2020), and for unconstrained cases (Jacob- sen & Cutkosky, 2023; Zhang et al., 2023b).
Besides, a lower bound of Oi max Pf. log T} is established for the d-dimensional squared loss, which is strongly convex and therefore exp-concave. While the upper bound are nearly optimal in terms of I' (up to loga- rithmic factors), the O(d*) dependence on dimensionality for exp-concave losses exhibits a significant gap compared with the lower bound. More importantly, the intricacy of the KKT-based analysis makes it unclear how to extend their framework to achieve improved dependence on the dimensionality d or to extend it for general results, such as obtaining problem-dependent bounds as the convex cases.
Despite considerable progress with convex functions, learn- ing with curved losses for dynamic regret minimization remains underexplored. In online learning, curvature is of- ten captured by exp-concavity or strong convexity (Hazan et al., 2007), which imposes specific conditions on the lower bound of the Hessian matrix V fe)) of the loss. Key examples of coppconcvve losses include:
squared loss; fe(w) (w xx -=));
logistic loss: [w) log(1 + exp(-9ew xx));
Our Results. This work offers a new perspective on achiev- ing fast rates in dynamic regret minimization with curved losses by leveraging mixability (Vovk, 2001; van Erven et al., 2012) of the loss function, a concept closely related to exp-concavity and fundamental in fast-rate static regret min- imization. Our method is free from the involved KKTTbased analysis and enjoys improved regret on several curved loss functions with better dependence on the dimensionality d.
Here, X E IRd is the feature, and y, is the label for the classification or regression tasks. For static regret mini- mization, where the comparator is fixed over the time, the online Newton step (ONS) achieves logarithmic regret bound of O( log T' for n--ep-concave functions, while OGD with step size 17 (1/t)) ensures Ø log Z') regret for a-strongly convex functions (Hazan et al., 2007).
In Section 3 and Section 4, we begin with the online predic- tion problem, which is specific kind of OCO problem with the form fa f((w) {(h(w ((,,,,x)) xx), ,,))),)),..)))))))) yr), where h is predictive function and is a certain loss. When the loss & is mix- able (see Definition 2) and improper learning is allowed, we show that a continuous variant of Vovk's 's aggregating algo- rithm (Vovk, 2001) with fixed-share updates attains a nearly optimal dynamic regret bound of Ō( max (dT à P d)).
However, when it comes to the dynamic regret minimiza- tion problem, the task becomes extremely challenging. To our knowledge, even if Pr were known, it would remain unclear how to tune the step size of ONS or OGD to achieve a faster dynamic regret rate than the convex case. A recent breakthrough was achieved by Baby & Wang (2021) and further extended in Baby & Wang (2022a;b); Baby et al. (2023). The key is to introduce an offline optimal reference sequence, the behavior of which can be further character- ized through a careful analysis of the KKT condition. They then demonstrate that strongly adaptive algorithm-on that guarantees low regret over any interval-can effectively track this offline sequence, leading to a tight dynamic re- gret bound. Specifically, their method achieves a dynamic regret of Ō( max (d T d)) for exp-concave losses.
As shown in Table 1, our approach covers several impor- tant curved losses. For the 1-dimensional squared loss, it matches the dynamic regret bound of Baby & Wang (2021) under proper learning, where the learner's predictions al- ways lie within the fcasible decision set. It also extends to the least-squares and logistic regression, two key exam- ples of exp-concave online learning. Since both losses are also mixable, our method improves upon the best-known results (Baby & Wang, 2022b; Baby et al., 2023) by achiev- ing more favorable dependence on the dimensionality d. Importantly, the dynamic regret bound is derived via rela-
Baby & Wang (2021; 2022a) defined the path length with the Li norm Here, we express their results in terms of the La norm by [|x]]= S V xx|/ for better comparison.
2

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
tively simple yet effective decomposition based on the mix loss, which circumvents the need for technically involved analysis of the KKT conditions. Nevertheless, while our method offers improvements in regret, it relies on improper learning, in contrast to the proper learning methods of Baby & Wang (2022b) for the least-square regression and Baby et al. (2023), which deals with the generalized linear models.
Definition (Exp-concavityy. Let rj 0. A function f W + R is n-exp-concave over W if the function e- (w) is concave for any E W. The condition is equivalent to
_ f (Wep)) S - 19
In (Ew- (omep((-n/()))
(2)
for any distribution P over W and Wexp E [w-r(w)
In Section 5, we further demonstrate the flexibility of our ap- proach by extending it to the general OCO with exp-concave losses. We show that by incorporating additional projec- tion step, one can achieve the nearly optimal dynamic regret of Ö( max pI. d3) under proper learning. While the projection introduces non-trivia computational challenges, our result shows that one can attain a nearly optimal bound via proper learning over arbitrary convex and bounded do- main for general exp-concave losses, guarantee previously known only for specific losses such as the squared and lo- gistic losses (Baby& & Wang, 2022b; Baby et al., 2023).
The mixability (Vovk, 2001) is weaker than exp-concavity that only requires the existence of model Wmi mix that satisfies the inequality (2) instead of the specific formulation of Wexp-
Definition 2 (Mixability). Let v > 0. A loss function f : W + R is 17-mixalee if for any distribution P over the W. there always exists a mapping h P + Wmix such that
fW S In (Ew-p [o-wrwo])
(3)
The coefficient 1j in exp-concavity and mixability essentially characterizes the curvature of the loss function. A larger 1I corresponds to a stronger curvature, which turn leads to better regret guarantees. Moreover, any m-mixable loss remains 1/ miiiiale for any < 1/ S 17.
Finally, we note that our method is based on the continu- ous exponential-weight (EW) update, which offers sharper regret guarantees than gradient- based methods but are of- ten computationally more demanding. For the squared losses and least-squares regression, we have narrowed this gap by showing that a practical implementation attains the same ((T) per-round cost as the follow- wwww-tth--eading-hieeeee (FLH) procedure in Baby & Wang (2021, Fig. 2). While FLH can be further accelerated to (log T) per round via a geometric covering over the base-learners (Hazan & Se- shadhri, 2009), extending this speed-up to the EW frame- work remains open. More generally. EW methods are sometimes surprisingly effective in many challenging online learming problems. However, improving their computational efficiency remains non-trivial, as in the case of bandit con- vex optimization (Ito, 2020; Bubeck et al., 2021).
A comparison of (2) and (3) shows that the key distinction lies in how the prediction is constructed from the distribution P. Under exp-concavity. the prediction is explicitly defined as Wexp = E [w], whereas mixability merely requires the existence of some model W Wmix- Therefore, exp-concavity is a special case of mixability; any ep-cccecn function over W is least mi-mixable over W because the mixability condition (3) holds with Wmix
Wexp.
2.2. Examples of Mixable Loss
Here are two important examples of mixable loss. Example 1 (Squared Loss). For any yr [-B,
2. Preliminaries
[sq vt) = (= (=- y2))
This section introduces mixability (Vovk, 2001), a property of losses that ensures fast rates in both statistical and online learning. The concept was initially studied in the predic- tion with expert advice setting and was shown to yield a constant static regret bound (Vovk, 1998). Later, it has also proved useful for static regret minimization in online opti- mization ( (Vovk, 2001; van der Hoeven et al., 2018 8) and for excess risk minimization in statistical learning (van Erven et al., 2012). We introduce the basic concepts here. Readers are referred to Cesa- -isacBianchi & Lugosi (2006, Chapter 3) and van Erven et al. (2015) for more details.
is exp-concave over = E (-D, D).
over E R while it is 1/(2(B+ D)3)
Example 2 (Logistic Loss). For any yr E 1-1,
fu(2, = log (1 + exp(-2y1))
is 1-mixable over 2 E IK while it exp( - -exxccccncce over 2 E [].
These two losses are two important examples arising in online prediction where the learner sequentially predicts label ye based on observed input data (Vovk& & Zhdanov, 2008). To highlight the core ideas of our approach, we initially focus on this supervised setting in Section 3 and Section 4. We then extend our method to the general online convex optimization (OCO) framework in Section 5.
2.1. Mixability and Exp-concavity
Before introducing mixability, we review the related concept of exp-concavity (Hazan et al., 2007).
3

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Algorithm 1 Fixed-share For Continuous Space
W C R is convex and compact with diameter at most D,
i.e., ||w w'll2 S D for all w, w' W. Assumption 2 (Smoothness). The function f((w)
Input: mixability coefficient 1, and parameter μ E [0, 1]. I: Initialize wo E W any point in the domain W and
P Pi = (wo, Ia) as Gaussian distribution.
((h(w,x)); vt) is 8-smooth for any w E R and t [T]. Assumption 3 (Mixability). The loss function {(2,)) is m-mixable over E R for any y E y
2: forl=1, 1,2, 2, do
3: The learner submits the prediction 25 that satisfies
(4)
3.2. Generic Framework
Our method is an exponential-weight method with the fixed- share update over the continuous space. Instead of maintain- ing model parameter w, E W and predict = = >h(w,, xx), we maintain a distribution Pt of the model parameter over R The prediction 24 is made based on Pt that satisfies the mixability condition (4). Under Assumption 3 and accord- ing to the definition of mixability, a predictor satisfying (4) always exists, For the online prediction problem, Vovk (2001, Eq. (11) and (12)) Gesa-Bianchi & Lugosi (2006, Proposition 3.3) provided general optimization framework for constructing such predictors. In the cases of squared loss and logistic loss, closed-form expressions for the predictor 24 are available. Further details are provided in Section 4.
without having access to the loss function ft-
4:
The learner observes the loss function Sr for time 4.
5: The learner updates the distributions by
(u) < (u( (xin)eep(-nneee Vu e IR;
(5)
(u) (1 p) (u) + (u),
(6)
where No = (wo. Ia) is a Gaussian distribution.
6: end for
3. Proposed Method for Online Prediction
This section focuses on the online prediction problem. We begin by a generic framework for learning with mixable losses in the setting, followed by its theoretical analysis and an equivalent formulation for implementation.
The update procedure of the distribution Pe is summarized in Algorithm 1, where we initialize it with Gaussian distri- bution P1 _No Ia) at the first iteration. At each itera- tion t, the distribution Pr+1 is obtained by the exponential- weight update (5), followed by the fixed-share step (6). Al- gorithm I attains the following dynamic regret bound. Its proof sketch is given in Section 3.3.
3.1. Problem Setup
Online prediction is special case of OCO, where the learner proceeds with data pairs (x,, yt). with X, E X' C Rd de- noting the feature and y/: E TK the label. At each round t, the learner first observes X2 and then produces prediction 2 R. After that, th learner incurs loss ((2,, Bt) and subsequently observes the label y, to update the prediction.
Theorem 1. Under Assumption 1, 2 and 3, for any u, E W, Algorithm with μ = 1/T ensures
(1)
D-REGT((U)TT)) S
As a natural extension of prior work on static regret min-
where P1 = =T mn 1a-1ll2 is the path length.
imization (Rakhlin et al., 2015; Mayo et al., 2022), our goal is to minimize dynamic regret with respect to a se- quence of time-varying models in a given hypothesis space
For mixable losses, Theorem shows an Ö(d+ Pf dy- namic regret bound, which improves the Ödd dynamic regret bound established based the notion of exp-concavity (Baby & Wang, 2022a), by reducing the de- pendence on dimensionality from O 3 to Od). As will be clear in Section 4, the improvement holds for loss func- tions for the least-squares regression and the logistic regres- sion, which are both mixable and exp-concave.
H {x h(w, x) w E W). where h W x X + y is fixed predictive model and W c Rdd denotes the parameter space. For instance, in the case of linear prediction, we have h(w,x) = ww x. The dynamic regret is then defined as
T
D-REGT (fu)) = Σ E Mi)
Σ e(h(u,, xx).
Notably, Algorithm I does not require prior knowledge of the path length Pr, which quantifies the environmental non- stationarity. At first glance, this might seem surprising since, in the convex setting, existing approaches typically require two-layer online ensemble to handle the uncertainty of the unknown Py (Zhao et al., 2024). The key distinction lies in the fact that our algorithm maintains a distribution P. rather than single prediction w.- This enables the use of
where uI,.... ur E W are time-varying model parame- ters. Online prediction be cast as standard OCO by setting fe(u) = ((h(u, xx), 3t), though we allow improper learn- ing, where the prediction may fall outside the hypothesis space H (Shalev-Shwartz. & Ben-David, 2014, Remark 3.2). Besides, we have the following assumptions.
Assumption 1 (Bounded Domain). The parameter space
4

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Gaussian comparator Qt in our analysis, which automat- ically adapts non-stationary environments by virtually adjusting its variance as shown in Section 3.3. From algorithmic perspective, we further show in Section 3.4 that our fixed-share method can be interpreted as, and is actually algorithmically equivalent to, a two-layer online ensemble.
! Bounding mixability gap. By (4) in Algorithm 1, the mixability gap is non-positive. Therefore, can upper bound it by 0 and proceed with the second and third terms.
2 Bounding mixability regret. We establish the following lemma for the mixability regret when comparing against the time-varying distribution {Qr)
3.3. Analysis of Algorithm 1
Lemma Let Qt = -N(,, Ta) be a Gaussian distribu- tion. The update rule (5) and (6) with μ 1/T ensures
This part provides a proof sketch for Theorem 1, analyzing the dynamic regret of Algorithm by leveraging the notion of mixability, Our analysis avoids the reliance on the tech- nically involved KKT conditions as used in Baby & Wang (2021) and the subsequential works (Baby & Wang. 2022a). An exception is Zhang et al. (2023a), who studied the on- line covariate shift adaptation problem using the logistic loss and analyzed its dynamic regret without requiring KKT conditions. However, their analysis is restricted to a specific kind of comparator, defined as the minimizer of an unknown risk function, and additionally assumes the realizability of the comparators, which is not required by our method.
T m
T
(P()
Σ
E Cu.q..i(lu) = (2 KL(Q1IIPA)
1
"1
1=1
T
(Q:(u)- -
Pr(u) du,
ueRd
1=2
where KI.(PIIQ) = Earr In (P(u)/Q(u))-
Given the Gaussinality of the distribution Qr and the initial distribution P; =Woo,, Ia), several mathematical manip- ulations presented in Appendix A.3 show that
Proof Sketch. Let P E P be a probability distribution and PP is set of all measurable distributions. The core concept of our analysis is the mix loss m. P R
term (B) dllo((nT) Pr/o + do dlog(1/o)
m = -
1 In (Eu-p [exp (- (- ns((u))]).
where X hides constants independent of d, a, T and 17.
Bounding comparator gap. Then, move to the comparator gap. Owing to the smoothness of ft, we have
Let 2 be the final prediction at round t. The dynamic regret can be decomposed into three terms:
E Eu- Qu [f((u) (u,)]
T
T
D- D-REGT= s
Σ E121 vi)
m.(P.)
(7)
< E Eu-Q, [V)lu)), u u.)
3 un uzl1
Bdo
2
2
(A) nixability gap
where the equality is by the Gaussinality of the distribution Q.. Therefore, we have
m. (P:) - Σ Eurq [s(wi)]
T term (c)= Σ [EQ, fe(u.) <
3do
(8)
(B) mixability regret T
2
Eu Eurq, [f((w)] I(ws).
Combining the results. By combining the upper bounds for term (B) and term (C), we achieve
1=1
(c) comparator gap
D-REGT S ! ddog(1()) - Pr 17
+ HdTo² 2 + dog (
The first term is the mixability gap. which measures the gap between the original loss and the mix loss. The second term is the "mixability regret", which is the regret in terms of the mix loss m,(P;, and the expected loss over the sequence (Q.)T= The third term is called the "comparator gap" as it is the gap between the expected loss and the loss of u,
Since the parameter a only appears in the analysis, we can freely tune it to make the above dynamic regret bound tight.
When Pr S vI/T, choose o VI/T to obtain D-REGT < OdllggT)
We note that the distribution Q: only appears in the analysis and can be arbitrarily chosen to make the bound as tight as possible. Specifically, we choose Qt = N(u, o² Ia) as the Gaussian distribution with the mean u, and covariance 2² la. where a > 0 is parameter to be specified later.
When Pr 2 VI/T, we set o @(P to obtain
D-REGT S O dlogT (1+ T
We complete the proof by combining the two cases.
5

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Remark 1 (Technical Discussion). The mixability-based analysis was first developed for the prediction with expert advice (PEA) problem (Vovk, 1998), where the prediction domain W is a finite set. In the PEA setting, our analysis with fixed-share updates closely relates to that of Cesa- Bianchi et al. (2012b), which established a dynamic regret bound for the fixed-share method with convex losses. Al- though their arguments also apply to exp-concave losses, the later extension (Cesa-Biaa) Bianchi et al., 2012a) only achieved switching regret bound, specific case of dynamic regret where the comparator sequence is piecewise stationary. In the OCO setting, van der Hoeven et al. (2018, Lemma 1) an- alyzed the sesponential-iighhe method but primarily focused on the mixability regret term with respect to an unspecified and fixed Q. Technically, our results not only extend prior work with time-varying distributions Qs, but also establish path-length bound by carefully selecting Qi and analyzing the fixed-share method in continuous spaces. Our work ad- dresses a gap in the literature by providing dynamic regret guarantees for mixable losses in the OCO setting.
Algorithm 2 Follow-the-Leading -esttrnnnn-sn
Input: mixability coefficient 1 and parameter μ E [o. 1].
1: Invoke the first base-leamnr B1 with the initial decision distribution p()) = NWwe, Id).
2: Initialize base-learner pool Hi (Bi), set weight
(1) and set P1 (i(w)))))))) P1 (w). Pi
3: for / 1,2, T do
The learner submits the prediction 2, that satisfies (4).
5: The learner observes the loss function ft for time t.
6: For all base-learner B; E H4, we update by
PfR & P! (u) exp((nf((u))) Vu ER (9)
7: Initialize a new base-lcarner Bi+1 whose decision distribution is p((+1) = (Woo, Ia). 1+1 Update the weight for each base-learner B, E H, by
Pi+1 Pi (1)
E p. lexp(- (exp(-n//(u)))
(10)
9:
Update the weight for existing base-learner by
3.4. An Equivalent Implementation
(1- 1³) Pitt for B, H4 for B
(1)
Pi+1
(11)
The implementation of our method involves two key aspects: (i) how to update the distribution Pt and (ii) how to predict zi based on P; satisfying (4). This subsection provides an equivalent update rule for Pt, which has a more explicit form for implementation and helps us better understand the mechanism of the algorithm. The construction of 2 will be discussed in Section 4.
10: Update the base-learner pool: He+1 = H4 U (B++1).
(9) ((i) 11: Obtain (u+ = EB, Pit1 (u).
12:
end for
1=2 1=3
update 1.dh by (9)
The key observation is that the fixed-share Algorithm I with fixed parameter i is essentially equivalent to the follow- welllading-histoy-ttee
active base-learner
R
(FLH-type) algorithm (Hazan & Seshadhri, 2009) as summarized Algorithm 2. The equiv- alence was first made in the PEA problem (Adamskiy al., 2016), and here show the results also extend to the con- tinuous space, which leads to more clear way of updating distribution Pt. The Httpe method is summarized in Algorithm and illustrated in Figure 1.
update p." by (10), (11)
A
meta-learner
Pt Cac p(6
Figure 1: An illustration Algorithm 2, an alternative implemen- tation the fixed share method.
The following theorem establishes the equivalence between Al Algorithm 1 and Algorithm 2.
Conceptually, our method is essentially an online ensemble method (Zhao et al., 2024) consisting of two parts:
Theorem 2.
The sequence of distributions {PiYT= re- turned by the fixed-share algorithm (Algorithm 1) is iden- tical to that of the FLII-type algorithm (Algorithm 2) with the same sequence of input loss functions {fe)T= and the same parameter setting of p.
Multiple Base-learners run over different time inter- vals. For each time i, we will invoke a new base-leamnr B, with the initial distribution p(1) NN(w.. Then, at the following time i i, the distribution is updated by the exponential-weighh update (9).
(Wo. Ia).
Meta-learner assigns weight to each base-learner to aggregate their predictions. For the new base-learner B,+1, the weight is set to and for the existing base- learners, the weights are updated by the Hedge method over the "mix loss" as shown in (10). The distribution P(11 is obtained by weighted combination of the distributions of the base-learners
An interesting connection between Algorithm and the method of Baby & Wang (2021; 2022a) is that both ap- proaches employ the FLH-type algorithm to bound dynamic regrets. However, their roles in the analyses differ substan- tially. In the previous work, the strongly adaptive regret guarantee of the FLH-type algorithm is pivotal for tracking the offline optimal sequence, whereas our analysis exploits a
6

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
fixed-share update formulation combined with mixability ar- guments, thereby offering fresh perspective to achieve the nearly optimal dynamic regret bound. Furthermore, from computational perspective, although Algorithm 2 aggre- gates a set of log-concave distributions- a task typically more computationally more intensive than updating a set of models w, as in previous work-we show that for the squared loss, the distribution update can be performed in a closed form. This results in computation cost that is of the same order as that of Baby & Wang (2021; 2022a) for these losses, but with an improved dependence on d.
prediction zt can also be computed in closed form. Since our method requires maintaining base learners at time i, the total time complexity for updating p(1) and p.t and then aggregating them via (12) is O(t) per round. This computation cost is of the same order as the FLH method used by Baby & Wang (2021, Figure 2).
4.2. Instantiation to Least-Squares Regression
This subsection shows the fixed-share algorithm is also ap- plicable least-squares regression with the loss (w) (w x y )² We assume that the feature vector X E Rd is bounded as ||x|||2 S L and the label y/2 E [- B. BJ. The basic observation is that the loss function fa is essentially the 1-dimensional squared loss (2, 91) = (2 y1)² with 2 = w x,, which is ( distribution P. defined over R4, we can construct the pre- diction znix for the least-squares regression following the same rule as (12) with the mix loss m(y, Pt) defined as
4. Instantiation to Different Curved Losses
Now, we are ready to apply the generic algorithmic frame- work to different loss functions. We first consider the simple 1 I-dimensional squared loss for algorithmic illustration and then extend to the least-squares regression and logistic re- gression. We provide comparison with the results by Baby & Wang (2021; 2022a) at the end of this section.
Therefore, for any
[ (w x1 - 28
1): (13)
-2BB In
Σ pl B,E
...EE E w.
4.1. Instantiation to 1- I-Dimensional Squared Loss
The generic algorithmic framework can be directly applied
The aggregated prediction 2/tix has the following guarantee for the least-squares regression.
to the 1-dimensional squared loss f+(z) - (z y133 as it is 2-smooth and // 1 mixable for any Yt E B, B, B). Even better, we can construct the prediction zmixx with the greedy forecaster
Corollary 2. For the squared loss fi(w) = (ww" T x, y1)
& Lugosi, 2006). Specifi- cally, given a distribution P. defined over 2 = R. we can construct >miix that satisfies the mixability condition (4) by
with ||x: S T. and Y/+ E [-B, B], set / = 1/T and
Wo = 0. The mix prediction zmixx (13) ensures
maq Pr, -B) mag PP, B)
Σ Csal=
mix
, ,e)) - Σ t=1
fe(w.) < O(d aT)
mix_
(12)
4B
B
where we define [z]s min minnmase (max -B), B} the func-
where p-= - llu. Ur Me-1/12 is the path length of the comparator sequence with ||u l22 S D.
tion that clips the value to the interval [-B, B]. In the above, the mix loss is defined by
Implementations. Similar to I-dimensional squared loss, the distribution pb()) is multivariate Gaussian distribution and we have a close form update rule for 2miix, The method can be also implemented in ((t) time for each iteration t.
maq (Pt, = -23² In
Pt P B.EH.
Σ
e
28
w)
where p!(0) is the distribution maintained by the base-leamer B; and pt" is the weight from the meta-learner. A direct application of Theorem leads to the following corollary.
4.3. Instantiation to Logistic Regression
Given that logistic loss (r(2, v) = log(1 + exp(-yz) is 1-mixable for any E Rd and y E (-1,1), the generic algorithmic framework is also applicable here as the case of least squares. Specifically, for any given distribution P. over Rdd one can construct the mix prediction by
Corollary 1. For the squared loss fz) = (2 - 32 with Y [-B, B). set μ 1/T and wo = 0 in Algorithm 1. The prediction zmix ensures
T
Σ Enlr 1=1
mix - Fi(l)) < p
1=1
mix = 2
Σ
Pt (6)
Bo (o xi)l (14)
where P. Etz | 1- is the path length.
B.
Implementations. Since the squared loss is quadratic, the distribution P(()) is Gaussian, allowing for a closed- form update rule for both p!()) and pt Consequently, the
where o (=2) = 1/ (1xxxx===)) is the sigmoid function and
o (z) = In is the inverse function of the sigmoid. We have the following corollary for the logistic loss case.
7

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Corollary 3. For the logistic loss [((w) log(1 exp(-yw Tx) x)) with |xx|2 S I. and y/t E {+1,-10 set μ 1/T and wo = O. The mix prediction =fnix ensures
case, as it can be proceeded in coordinate-wise manner. In contrast, applying the KKTThased analysis to the I-2 norm without introducing additional dependence on d remains unclear. Our mixability based analysis offers a more direct way to obtaining path length bounds with the L2 norm.
T
T = o(d+)
Σ (x
mix 91) - Σ
Limitations of Algorithm I and Improvements. Although Algorithm achieves improved dynamic regret without rely- ing on KKT-based analysis, there remain several directions for improvement. First, regarding the time complexity, our method matches the O(T)) complexity of prior work for the squared losses. However, the KKT-based methods (Baby & Wang, 2021; 2022a) can reduce the complexity further to (log T) by leveraging a geometric covering of base- learners (Hazan & Seshadhri, 2009), at the expense of addi- tional logarithmic factors in the regret. Incorporating this idea into the fixed-share update is promising direction. Moreover, the guarantee provided by Algorithm I relies on the smoothness of the function ft and on allowing improper learning. In contrast, the smoothness condition is not re- quired in Baby & Wang (2022a), and the works by Baby & Wang (2022b); Baby et al. (2023) eliminated the need of im- proper learning for online prediction with the linear model, where the loss has a specific form. In Section 5, we improve our method further by removing the assumptions smooth- ness and improper learning, though the computational issue will become more challenging.
tm1
where P.- Ei=ellu ||u comparator sequence such that ||ur|l2 V D.
1 is the path length of any
Implementations. For the logistic loss, the main com- putation cost is to calculate the term E, pu [o]wwx:)], which appears both in the weight update (10) and final pre- diction (14). We do not have closed-form expression for this term. However, we can exploit the log-concavity of the density of p!() and apply a sampling technique to facil- itate computation in polynomial time (Foster et al., 2018, Appendix B). To further accelerate the computation, one might consider using the technique of Jézéquel et al. (2021), which approximates the logistic loss using second-order surrogate. In such case, p!(0) is Gaussian and sampling can be performed efficiently. However, due to the two-layer structure of the method, it is challenging to directly extend the method here. We leave the computation cost for the
logistic loss as a future work.
4.4. More Comparison with Related Work
5. Extension to General OCO
In this subsection, we provide a detailed comparison be- tween our results and best-known prior results, with a par- ticular emphasis on the three main cases of the curved loss.
This section extends our method to the general OCO without requiring specific structure of the online function in Section 3.1. Instead, we only assume the loss functions fr are exp-concave (and thus mixable) over the domain W. By using a projection step and learning with a surrogate loss, our method achieves a nearly optimal regret bound under proper learning and is free from the smoothness assumption.
For the I-dimensional squared loss, our result matches the nearly optimal guarantee Baby & Wang (2021, Theorem 1) and both methods are proper. However, our analysis does not rely on the KKT condition.
For the least-squares regression and logistic regres- sion, we improve the best-known results of Old + d Té P in Baby & Wang (2022a;b) and Baby et al. (2023) with better dependence cases, Algorithm 1 is inherently improper, as its predic- tions extend beyond the linear function class. This is less favorable compared to the specific algorithms de- signed for the least-square regression (Baby & Wang, 2022b) and the logistic regression (Baby et al., 2023), which ensure proper learning.
Besides Assumption on the boundedness if the feasible domain W, this section requires the following conditions.
d. For these two
Assumption (Exp-coneave). The online function fa is --exp-concave over the domain W for all E [T').
Assumption (Bounded Gradient). The norm of the gradi- ent of the loss function is bounded by G, i.e. [V S G for any E W and / (T).
A key obstacle in extending Algorithm the general OCO setting is that it requires the loss function be mixable over Rd. a condition often satisfied in online prediction but not in general OCO. In the latter case, exp-concavity is more standard assumption, which only guarantees mixability over a bounded domain W. This makes it challenging to con- struct a prediction w, that has a negative mixability gap, i.c., fi (w.) S - 1 In (Eu- (exp(- (n))) "
We note that the path length in Baby & Wang (2021; 2022a) is defined via the L, norm. We present their results in the Le norm for better comparison through ||x||| S vd ||x]] x||2, Vx E Rd. The reliance on the L1 norm in their analy- sis seems to stem from the inherent intricacy of handling
KKT conditions. For the L, norm, the analysis in the d- dimensional case is closely connected to the 1-dimensional
8

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Algorithm 3 Projected Fixed-share with Surrogate Loss
Specifically, we choose the set M as the family of all Gaus-
Input: exp-concavity coefficient 7). loss parameter y and fixed-share parameter μ E [0, 1].
sian mixtures whose component means and covariances
uniformly bounded. Let S a {Σ E $4 + S Xmin (2) S
1: Initialize wo W any point in W and Pi Pi (Wwo Ia) as a Gaussian distribution.
Amax (Σ) S $1} be set of symmetric positive-definite (SPD) matrices with bounded eigenvalues, where S is the set of all SPD matrices. Further denote by e - W x S the admissible parameter space for the component Gaussians and let 0 = (w, Σ) E 6. We define the constraint set as
2: for 1,
do
3: The learner submits w. = E. [w] and constructs the surrogate loss ft as (18).
4: For all E Rd, the learner updates the by
M { N(w, E)d((() T e 2(0)) (19)
P (u) x exp(( (u) arg min (L(Q))244)
(15)
(16)
where (()) is the set of all probability measures on θ. As detailed in Appendix C, the set is convex and closed in total variation, therefore a minimizer in the projection step always exists (Csiszár, 1975, Theorem 2.1). Moreover, since any P M has its mean in W, we have W, E., [w] W. which ensures proper prediction.
where P is set of distributions defined as (19).
5:
Then, the distribution is updated by the fixed share
Pu+i(u)= (1 (01-))PP Pi (N),
(17)
where No = (wos La) is Gaussian distribution.
Lemma 7 in Appendix C shows that one can ensure nega- tive mixability gap for the surrogate loss, i.e.
6: end for
2 In (Bu-p, (exp(p
To address this issue, we introduce two algorithmic mod- ificatiins as summarized in Algorithm 3. Our approach remains an exponential-weight method with fixed-share up- dates, but the distribution P; now updated with a surrogate loss (15), and projection step (16) is incorporated.
Je(EFPP, S -
which leads to the following guarantee for Algorithm 3.
Theorem 3. Under Assumptions 1, and 5, Algorithm 3 with μ 1/T ensures
Surrogate Loss. Let gi (w,)). Instead of using the original loss, we learn with the surrogate loss defined by
D-REGT S o T (1+ T PD))
F((w) = g. (w- w.) + ? [g (w- (w.w:)))? 2
(18)
for any comparator sequence UI ur E W.
where the coefficient is defined as 7 min(11/(4GD)) n)-
It is known that the regret in terms of the surrogate loss is always an upper bound for the original loss: f.W,)) fe(u,) S (w,)) - (u) for any Wr. u W (Hazan, 2016, Lemma 4.2) for exp-concave losses. Hence, it suffices for us to analyze the dynamic regret of the surrogate loss.
The proof of Theorem 3 is presented in Appendix C. The- orem 3 shows that our method achieves nearly optimal dynamic regret for the general OCO with exp-concave func- tions. Notably, the result holds under proper learning and is free from the smoothness assumption.
The surrogate loss plays a key role in eliminating the smooth- ness assumption. In Section 3.3, smoothness was used to control the comparator gap. Since the surrogate loss is quadratic, we can directly upper-bound this term by
6. Conclusion
This paper presented novel perspective learning with curved loss functions in non-stationary environments. Build- ing on the concept of mixability, we proposed simple yet versatile framework that achieves an improved dynamic re- gret bound with better dependence on d. Our analytical framework also offers additional potential, as allows the selection of different families of distributions P. and refer- ence distributions Q, for the fixed-share method, possibly enabling the algorithm to adapt to various geometric prop- erties of the space. From a computational perspective, we provided efficient implementations for the squared loss. A future direction is to develop computationally more efficient methods for the logistic loss and the general OCO setting.
term (C) S Eu~q. - Fo(u))) S do 12/2,
where we choose Q: = Nu,, I²I.). The above inequality naturally leads to a similar result to (8) in Section 3.3 when the norm of the gradient is bounded as Assumption 5.
Projection Step. The remaining challenge is that J. is not mixable over Rá, making it hard to bound the mixability gap. However, we show that such a negative mixability gap can still be ensured if Pt lies in a carefully designed distribution set M. as guaranteed by the projection step (16).

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Acknowledgements
Cesa-Bianchi, N., Gaillard, P., Lugosi, G., and Stoltz, G. Mirror descent meets fixed share (and feels no regret). In Advances in Neural Information Processing Systems 25 (NIPS), pp. 989-997, 2012b.
Peng Zhao was supported by NSFC (62361 146852, 62206125) and the Xiaomi Foundation. MS was supported by the Institute for Al and Beyond, UTokyo. The authors would like thank Yu-Xiang Wang for the insightful and helpful discussions. Yu-Jie Zhang thanks Zhiyuan Zhan and Yivan Zhang for their helpful discussions on the projection set. We also thank the reviewers for the valuable comments and suggestions, which helped improve this paper.
Csiszár, I. I-divergence geometry of probability distributions and minimization problems, The Annals of Probability, pp. 146-158, 1975.
Csiszár, and Matus, F. Information projections revisited. IEEE Transactions on Information Theory, 49(6):1474- 1490, 2003.
Impact Statement
Cutkosky, A. Parameter-free, dynamic, and strongly- adaptive online learning. In Proceedings of the 37th International Conference on Machine Learning (ICML), pp. 2250-2259) 2020.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Foster, D. J., Kale, S., Luo, H., Mohri, M., and Sridharan, K.
References
Logistic regression: The importance of being improper. In Proceedings of the 31 Conference on Learning Theory (COLT), pp. 167-208, 2018.
Adamskiy, D., Koolen, W. M., Chernov, A. V., and Vovk, V. A closer look at adaptive regret. Journal of Machine Learning Research, 17:2::1233:2 2016.
Hazan, E. Introduction to Online Convex Optimization. Foundations and Trends in Optimization, 2(3-4):157-322. 2016.
Baby, D. and Wang, Y.-X. Optimal dynamic regret in exp- concave online learning. In Proceedings of the 34th Con- ference on Learning Theory (COLT), pp. 359-409, 2021.
Hazan, E. and Seshadhri, C. Efficient learning algorithms for changing environments. In Proceedings of the 26th International Conference on Machine Learning (ICML), pp. 393 393-400, 2009.
Baby, D. and Wang, Y.-X. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In Proceedings of the 25th International Conference Artificial Intelligence and Statistics (AISTATS), pp. 1805- 1845, 2022a.
Hazan, E., Agarwal, A., and Kale, S. Logarithmic regret al- gorithms for online convex optimization. Machine Learn- ing. (9(2-3):169 199):169999222 192, 2007.
Baby, D. and Wang, Y.-.. Optimal dynamic regret in LQR control. In Advances in Neural Information Processing 2022b.
Ihara, S. Information Theory for Continuous Systems. World Scientific, 1993.
Systems 35 (NeurIPS), pp.
Ito, S. An optimal algorithm for bandit convex optimization with strongly-convex and smooth loss. In Proceedings of the 23rd International Conference on Artificial Intelli- gence and Statistics (AISTATS), pp. 2229-2239, 2020.
Baby, D., J., J., and Wang, Y.-X. Non-stationary contextual pricing with safety constraints. Transactions on Machine Learning Research, 2023, 2023.
Besbes, O.. Gur, Y., and Zeevi, A. Non-stationary stochas- tic optimization. Operations Research, -124,44244 2015.
Jacobsen, A. and Cutkosky, A. Unconstrained online learn- ing with unbounded losses. In Proceedings of the 40th International Conference on Machine Learning (ICML), pp. 14590-14630, 2023.
Bubeck, S., Eldan, R., and Lee, T. Kernel-hased methods for bandit convex optimization. Journal of the ACM, 68 (4), 2021.
Jézéquel, R., Gaillard, P., and Rudi, A. Mixability made efficient: Fast online multiclass logistic regression. In Advances Neural Information Processing Systems 34 (NeurIPS), pp. 23692-23702, 2021.
Cesa-Bianchi, N. and Lugosi, G. Prediction, Learning, and Games. Cambridge University Press, 2006.
Li, L.-F., Zhao, P., and Zhou, Z.-H. Near-optimal dynamic regret for adversarial linear mixture mdps. In Advances in Neural Information Processing Systems 37 (NeurIPS), pp. 08888-58883, 2024.
Desa-Bianchi, N., Gaillard, P. Lugosi, G., and Stoltz, G. new look at shifting regret. ArXiv preprint, arXiv: 10X.::2002.3233 2012a.
10

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Mayo, J., Hadiji, H., and van Erven, T. Scale-free uncon- strained online learning for curved losses. In Proceedings of the 35th Conference Learning Theory (COLT), pp. 4464 4497, 2022.
Zhang, Z., Cutkosky, A., and Paschalidis, Unconstrained dynamic regret via sparse coding. In Advances in Neural Information Processing Systems 36 (NeurIPS), pp. 3477- 3486, 2023b.
Rakhlin, A., Sridharan, K., and Tewari, A. Online learning via sequential complexities. Journal of Machine Learning Research, 16:155-186, 2015.
Zhao, P., Zhang, Y.J.,, Zhang, L., and Zhou, Z.-H. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp. 12510-12520, 2020.
Shalev-Shwartz, S. and Ben-David, S. Understanding Ma- chine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Zhao, P., Xie, Y.-F., Zhang, L., and Zhou, Z.-H. Efficient methods for non-stationary online learning. In Advances in Neural Information Processing Systems 35 (NeurIPS), pp. 11573-1 11585, 2022.
van der Hoeven, D., van Erven, T., and Kotlowski, W. The many faces of exponential weights in online learning. In Proceedings of the 31 Conference on Learning Theory (COLT), pp. 2067-200110000 2092, 2018.
Zhao, P., Zhang, Y.-J.. Zhang, L., and Zhou, Z.-H. Adap- tivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98): 1 52, 2024.
van Erven, T. and Koolen, W. M. Metagrad: Multiple learning rates in online learning. In Advances in Neurul Information Processing Systems 29 (NIPS), pp. 3666- 3674, 2016.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), pp. 928-936, 2003.
van Erven, T., Grünwald, Reid, M. D., and Williamson, R. C. Mixability in statistical learning. In Advances in Neural Information Processing Systems 25 (NeurIPS), pp. 1691-1699, 2012.
van Erven, T., Grünwald, P. D., Mehta, N. A., Reid, M. D., and Williamson, R. C. Fast rates in statistical and online learning. Journal of Machine Learning Research, 16:
1793-1861, 2015.
Vovk, V. A game of prediction with expert advice. Journal of Computer and System Sciences, 56(2):153-173 1998.
Vovk, V. Competitive on-line statistics. International Statis- tical Review, 69(2):213-243 2001.
Vovk, V. and Zhdanov, Prediction with expert advice for the brier game. In Proceedings of the 25th Inter- national Conference on Machine Learning (ICML), pp. 1104-1111, 2008.
Wei, C.-Y. and Luo, H. Non-stationary reinforcement learn- ing without prior knowledge: An optimal black-box ap- proach. In Proceedings of the 34th Conference on Learn- ing Theory (COLT), pp. 13300-4354 2021.
Zhang, L., Lu, S., and Zhou, Z.H. Adaptive online learning in dynamic environments. In Advances in Neural Infor- mation Processing Systems 31 (NeurIPS), pp. 1330-1340, 2018.
Zhang, Y.J., Zhang, Z.-Y,, Zhao, P., and Sugiyama, M. Adapting to continuous covariate shift via online density ratio estimation. In Advances in Neural Information Pro- cessing Systems 36 (NeurIPS), pp. 29074-299 29113, 2023a.

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
A. Omitted Proofs for Section 3
A.1. Useful Lemmas
Lemma 2. Assume the loss function f((u) is convex and B-smooth. Let Pe be the distribution returned by the fixed- share
update (6). Then, for any Ja E [0, 1}, we have In (u( S d
In
nBt 2
Proof of Lemma 2. The lemma be proved by the equivalence between the fixed-share-ty method (Algorithm 1) and the FLH-type method (Algorithm 2). Specifically, according to Theorem 2, the distribution P: returned by the fixed-share update (6) can be written as
P((u)=
Σ Pi
( P! (u),
(u),
Vu E Rd,
BiEHi
where o E [0, 1] is the weight such that EBEH. Pi The distribution p(e) (u) is updated via (9) and can further expressed as
(()(u))
(u) exp
F. (u))
Vu E Rd and B, E H4.
(20)
SuERd exp
(-F," F(( (u))du
In the above, we denote by F. (u) I|l woll + E Ss().. Let vi, arg uiRe pl (u). Given the loss function fi is 3-smooth, the first-order optimality condition implies
F i u
1 + nt
2 u Vi, Yu E Rd and B, E H4.
Then, the denominator in (20) can be lower bounded by
J.E exp (- F (u)) 2 exp( exp(-F()) (Fo(FF(
1 1/31
JUERd
exp
2
Iu
vi.112 du
d/2
= exp ( - =((((v,,))
(vi,))
2T
(21)
113t
For all Rdd and B, E H4, plugging (21) into (20) yields
(n) S exp (F()) (vi,) F(!) (u))
n3
nBt 2m
2x
where the last inequality is due to the optimality of vi.;- Given Pt P((u) is weighted combination of p!(((u) and p!o((u) 2
0, Vuu E Rd we have maxners Pu(u) < mERR (()) (u) I (nst/(2x)) We complete the proof by taking logarithm on both sides.
Lemma 3. Let P= Pu,, N(,, o² La). Besides, define N = NWoo, X21a). Then, let W = {u E Rdd P(u) 2 Q(u)]. Suppose Up wo S D and [y woll S D. Then, we have
be a Gaussian distribution with mean Up E Rd and covariance matrix 0² Ta and Q =
[ (P(u) In
1 Nuu)
ddIn(2mA2)
D
2do²
du <
+
|P 001-11111111 +
2
X2
x2
where 1P- = -SWERs PP(u) - Q(u)ldu
Proof of Lemma 3. Let z = Up We define the shifted distribution P'(xx) = o2)) Q'(x) N(u, Up o²1
and N' = N(wo up o2 1a). To prove the lemma, it is equivalent to provide an upper bound for
(P'(z) (0((z)(())))))))) In N'(2)
dz,
(22)
12

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
where W E Ra P'xx) 2 (2) is the shifted region. According the definition of multivariate Gaussian
distribution (z)
V(an2aja exp( 2x² z (wo- up)11 The term (22) can be equally written as:
1n(2 / 2
1
(P' (z) dz + 2X
(2)
1|2 (Wo upd1.dd.
ZEW
ZEW
TFRM (A)
(R)
Denote by || QQ111 SMERS (P'(z)Q((z)) (z) d2. TERM (A) be directly bounded by
d2 P Q'Il2 = d'In(2T22)
TERM (A) -
P - P
(23)
2
2
As for TERM (B), define a d-dimensional ball centered around a F2 with radius R > as ((, {z E Rd
||z all2 R). We can further partition the region W into two parts W W n B(ww- up, 2D) and Wout = W" /
We have the following decomposition:
[ (P'z))-((zz) ||z - (wo up)1
TERM (B) = 2A²
KEW,
[ (P' (()z)) 1z-- (wo- up)l
2X JEE
sul
2D
P Q11
(P' -Q'(z)) ||z - -wwo uppl3dz
X2
2X2
ZEW sul
2D2
< x2
P Q11
P'(z) 1z212dz
(24)
X2
ZEW out
where the first inequality is due to |z (wo up)l
S 2D
2D for any a W The second inequality holds since
[z (Wo up)ll2 S ||z||2 D s 2||z||2 for any W/
We can further bound the last term in (24) by
2
/
2 / |z S X2 JRd
2 P'zz)lz|Bdz
2do²
P'(z)
X2 Ex
x²
(25)
X2 ZEW,
X2
where the first inequality due to the fact Wout R.d. The last second equality because one can show that the random variable Rd follows the same distributions as z Σi= oXee,, where X, Lid. N/ 1) and e, E IRdd the one-hot vector with the i-th element being and others O. The last equality follows by (x,, 1. Plugging (25) into (24), obtain
D -IP 2
2do² X²
TERM (B) S
Q11 +
We complete the proof by combining the upper bound for TERM (A) and TERM (B).
A.2. Proof of Lemma
Proof of Lemma I. Recall the definition of mix loss
m. mx(P) = - In (Enw {e- (e-nsllu))
71
By the exponential weights update rule in (5), we know that
Pı(u) P1))(1))
in Ep, [e- [e-nf((u]]] e-nsi(u)
) In (ies(e-nflul)) (n).
In
13

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
which implies Bu In P )]
m.(()) - (ft(). by taking an expectation of both sides with respect to ~ Qt and rearranging the terms. Summing this equality over t E [T] gives:
T
T Q.lf(u)]
Σ
Mc(P)
Σ
Bu
E=
1=1
1
T
Puti(u)) )
P.(u))
Bu
In
"
KL(Q)IIP)) KL(Q. (P(2))
"
1 KL(Q)))P)) + Σ $
(KL(QI)A)) - -U(Q--1))
"
T
(u)
KL(Q + -
- -KL(-))))K - Σ Bu
1
In
(26)
P.(u))
where both the second and last equalities are by the definition of the KL-divergence. In (26), the gap between the Kl--divergence terms can be expressed as
(KL(Q+IIP)) KI.(Q--1\P.)
Bu-Qu
(P( (R/w))]
1 )
EurQu In (P(w))
(P((W))) )
(Qr(u) (u)) In
P.(u) du,
(27)
2= HERd
where the first equality is due the definition of the KL divergence such that (L( Eu-q In (Q(u)/P(u)) and Eu-q, [In (u)] Eu-Q.-1 In Qu-1(u)] for Gaussian distribution with the same mean. Furthermore, according to the fixed-share update rule (6), we know that (((u) = (N)(u) + (1 - (u).. Consequently, the final term in (26) can be bounded as
(u) Pi(u)
Pu(
In
= In
S In
I Tn
(28)
(1 - Pu + (N)(
n
-
where the last term is by the setting μ = 1/T. Plugging (27) and (28) into (26) yields
T
(p((P) - Σ Bu-qu (f((u)] < Σ /
T
T
2 (I.(Q.
(Qi(u) Qt- In
du
P((u)
t=2 uEBd
which completes the proof.
A.3. Proof of Theorem
Proof. The core concept in our analysis is the mix loss, which has been used to analyze static regret in the prediction- with-expert-advice problem (Vovk, 1998) and in online convex optimization (van der Hoeven al., 2018). Here, we show the critical role of mix loss in analyzing universal dynamic regret. For probability distribution P E P, the mixed loss m4 P + R is defined as
[c mp(P) = In (Ennr (e- (e-ns(ui))
(29)
11
where 7) the mixability parameter.
14

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Then, the dynamic regret be decomposed into three terms follow
D-REGT Σ (Z) - Σ Si(ue)
T
T + Bu Q (( -
T
((z..))))
m - + (P.).) - Σ Eu-q. [f((u]]
Σ f(li),
(30)
TERM (A)
TERM (B)
TERM (c)
where we choose Q = (u,, Ia) as a Gaussian distribution with mean u, Rd and covariance matrix La In the above, the TERM (A) is usually called the mixability gap, measuring the difference between the online function and the mixed loss. We call the TERM (B) the mixability regret, measuring the difference between the mixed loss and the loss measured on the expected comparators distributions. The TERM (C) called the comparator gap, measuring the difference between the expected comparators distributions and the true comparators.
In the following, will analyze the upper bound of each term, respectively.
① Bounding mixability gap.
According to (4) in Algorithm I, the mixability gap is at most O.
Bounding mixability regret.
Lemma 1 shows that the mixability is upper bounded by
TERM (B) S Σ J t=2 JUER"
1 Po(u)
2 + KL
(Qo(u) Qi-1(u)) in
du
(31)
(B-11)
TERM (R-1)
Analysis for Term (B-I): For upper bounding TERM (B-1), the main challenge lies in the unboundedness of the logarithmic term In(1/P:(u)). This issue arises because the probability density P: (u( can become arbitrarily small even with the fixed-share update. To address this issue, we decompose the space Rd into:
w {u add Qu(()) Qu-((u) and P((u) 1}: w = fu E Rd Qu(()) > Q--(()) and Pi(u) < <1}.
and the region W. = ( uw For points E W, we have (Q:(u) Qu-((u)) In (I/P.(u)) s 0, implying that the integral term over W, is non-positive.
Denote by QQ Q1-1l11 = fuez (Q:(u) - Qu- the total variation of the distributions Q: and Q.-1- For the integral over region ( We have
S.ewao (Qr(u) (u-1(u)) In
1 Pi(u)
/
du
JuEW!i)
(Qt-i(u)- Qu(()) In (P)(u) du
d
n
In
.1Q4 -Q-11l1
(32)
2T
where the inequality holds due to Lemma such that In P.(u) < $14
not 2n
for
Rd.
As for the integral the region m!??) have Q.(n) (u) and (No(u) Pi(u)) & 1 due to the fixed-share update rule (6). Then, we can bound the integral term by
JNewao (Qi(u) - Qu)) In Pr(u)) du <
1
(Qi(u) Qu- In
du
(NNo(u)
JueW!
ddn((2m)
D + In (1)) 11Q, Qe-1l11 2do
(33)
15

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
where the last line holds due Lemma 3. We obtain the upper bound for TERM (B-f) by combining (32) and (33) and taking the summation from & 7:
TERM (B-1) S ( In(n8TT) + D+ DI
T -
2
Σ
-
(34)
The total variation of the distributions Qi and Qt-1 can be further bounded by
|1Q Qi-Ili S (L(Q)I(Q--)
Uu u,
(35)
where the first inequality is due to the Pinsker's incquality and the last equality is due to the close form expression of KL divergence two Gaussian distribution as shown by Lemma 10. Combining (34) and (35), we obtain
1 " TERM (B-1) s 77 2
Pr ( (dIn(n8T) +D+
2d
+
n
where PT EE - ut-1ll2 is the path length.
Analysis for Term (B-II): Since Qı = (N,,,, and P1 = NNwo. Ia) are both Gaussian distributions, Lemma in Appendix D shows
2 1)
! (2+ d ")
1
do²
D
TERM (B-II)
(L(()))P))
2
(36)
Then, we obtain the upper bound for TERM (B) by combining the above results as
TERM (B) -
dIn(n33)
+ D +
Pr do do +
12
+
+
d
In
1
(37)
2
2n
Bounding comparator gap.
Since the loss function is 8-smooth, we have
B - |u =u
fu( fu())) + (V.)),) u,)
Then, taking an expectation over Q, for both sides, we have
B S fe(w:) + Euuq.llu- uol1 2 fe(u:) + 3do² 2
2
which implics
T
T Σ
2T
TERM (C)
Σ
E Eu-q. (f(()](((]]]
f((u.)
(38)
2
1=1
Plugging (37) and (38) into the decomposition (30), we have:
Pr Pr. + D-REGT < (lln(31TT + +D+1IT)
(14 133T+++++ +1
+2
d
1
do +
In
2
27
1
We can further bound the above regret bound by considering different value of Pr.
Case 1: P1 & 7 We can choose a = v1/T to obtain D-REGy & Odl
Case 2: Pr > We select a = (
(DT) < 1 to obtain D-REGT S Oddogg T T p + +dlog]
16

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
A.4. Proof of Theorem 2
Proof of Theorem 2. We denote by Pss the distribution maintained by Algorithm 1 and Pft the distribution maintain by Algorithm 2. To prove the theorem, it is equivalent to show P. th for all t [T]. For the update rule of pts, we have
{
pls ( (1) expl (f)
-u- (expl [J]](
(39)
ple ( (1 P (u) + uNo(u).
We show that the update rule of 17th is equivalent to the above update rule. Recall (. = EB. Pt 19 (u), where and p(f) is the weights and distribution of the i-th base-learner respectively. Let us define
P P (u) Σ
(0 Pitl
(1))
B,EH,
where Difz and plù is defined as (10) and (9), respectively. We have
Fit (u)
Σ
Pit1 (
BiEN
plo
(( (u) expl ffp( (u)
Σ
BEEH. EBEEH, Pt E Puupp (exp((((x(
E n (())
EB.EH, Pi P(()) ex)e (f(())))
(u)
EB,EH, pt . B p( lexp( ((())
pm exp( (exp(-nf((u))
Besides, we can further rewrite the distribution Pif1 as
(
Σ (1) ( Σ
(1 (1-
20 Piti P441 + pNo(u) + (1- (1-))Pf11() + pNo(u))
B.EH++1
B,EH,
Therefore, we can conclude that the distribution maintain by Algorithm 2 can be equivalently updated by
Pith F. joxp( [f(
12th exp(- (u))
(
(u) = 11) i+1 (u) + (Nouu).
which is identical to (39). We complete the proof by the setting pls = plt No-
B. Omitted Details for Section 4
This part provides omitted details in Section 4, including the detailed implementation of our method for squared loss and proofs of the statements in this section.
B.1. Implementations for Squared Loss
Given the squared loss is quadratic and the initial distribution Gaussian, we have close form update rule for p!() and p.
Proposition 1. The distributions p()) for the base-learner B, are Gaussian distribution N( B² for all t= 1....., T - 1, whose means and variance are given by
Wi,i + o2.0 + o
Z oi +
WL+1,
and 04.
As for the meta-algorithmm due to the Gaussinality of p()), the update of the weight (. in (10) is given by
(_ (We,i - y1
(1)
1
Pit1 O
exp
V1
oz
2B² + 1)
17

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Proof of Proposition 1. According to the update rule (9), have
p(0) (w) & P (w) e 222 (w-ve))
w1
+ (w y1)
& exp
2B²
w + const )
Wiii + yı
x exp
2
1,K
+
w² - 2
o
This represents Gaussian distribution with updated parameters:
o
+1
of +
W++1, = o 0441,
We,i oi
+ Ut
W + 7
o +1
Therefore, p(O) is Gaussian with mean W1+1, and variance B B as claimed.
B.2. Useful Lemmas
Lemma 4 (Mixability of Squared Loss). For any yr E [-Y,Y], the squared loss function lsg(z, 91) = _/(2 y1)) is 2Y2 mixable over the decision space Z R.
Proof of Lemma 4. According to Vovk (2001), the squared loss is 1 mixable over the decision space = [-Y,, Y1, i.e., for any y E [-Y,]] and over [-Y, Y], there exists a prediction 2/ such that
(z)(z', < -2X (Ewwpr ( =->))(()))
(40)
To prove the lemma, we observe that for any distribution / over IR and any in the interval [-Y, Y). the always exists distribution p' defined over [-Y,Y] Y] satisfies that
-2 In (EsmP [o- zt (oll)))))))) 22 In EEEwr [o ba (o(21)))))) ])
where Pr is modified distribution that shifts the probability mass of P outside the interval [-Y, to the boundary points. Specifically, P' retains the same density as P within (-B, B), while at the boundaries, it is defined as: P'(Y) P(Y)+ S(y,z)) Plz)dz and P-(-Y) = P(-Y)) + s(-ox.-V] P(w)dw. According to (40), there exists a prediction such that
4(2'.y) - 2 In Eewp' [e (n110)))))) < 222 In (Eopp [o 2t. (m(t.0))
thereby indicating the mixability over IR.
B.3. Proof of Corollary
Proof of Corollary To prove the corollary, sufficient to show that the prediction (12) satisfies the mixability inequal- ity (3). We show (3) is essentially the greedy forecaster (Cesa-Bine Bianchi Lugosi, 2006, Section 3.4) for squared loss, which always ensures non-positive mixability gap.
As shown by Lemma 4, the squared loss is 26 mixable over the decision space Z = R. Then, for any mixable loss, Proposition 3.3 of Binnchi & Lugasi (2006) shows that the greedy forecaster defined by
mix
arg min ER
sup vE(-B.B]
(zq y) - mea (P,y)
(41)
mixability
18

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
always ensures non-negative mixability gap, where (P. = -2B2 In (Ew~P e anz (
))
is the mix loss. Fur- thermore, as shown by Lemma 3 of Vovk (2001), the mixability gap (2. y) - mag (P. y) is a convex function for any y E IR. give a fixed 2. Therefore, the inner optimization problem in (41) always achieves its optimal value of y = B or y = B. Then, we can equivalently rewrite the above optimization problem as
arg min ZER
sup (-
(fsq(2,8) msg (P,))).
(42)
Then, is sufficient show the optimal solution of (42) is given (12). Since mag (P,y) is constant when the value of y given, the optimization problem (42) can then be reformulated as:
arg min max (2 - B)² M1, B) 1 M22, ZERd
where we define M1 mm B) and M2 m. (P. -). The inner optimization problem admits the following closed-form solution:
B). Further let 91 (z)
(z (2-B)- 8)- M1 and 92(2) (2+B)² 2-2--2 M2.
(=),, if 21,
h(2)
(a(z), otherwise,
where: 2
M1 We now consider three separate cases on the behavior of h()): 1B
When -B < z < B: For 2 E (-o0, 2. we have h(z) = (z),,, which is decreasing since 2t < B. For E (2), we have h(2) = 92 (z), which is increasing because 2 2 BB Therefore, h(z) attains its minimum at 2 27.
When zt < B: For the range (-oo,=!), =!], have l=(=) = 91 (1)= remains decreasing. and the minimum in this
B:
(z), interval is at z1. On (zt, oo), the minimum of hzz)) is at 2 B since h(-B) (2(-B) B) M22. Under
the condition =1 < - B, one can verify that h(-B) S h((2), so the overall minimum is attained at -B.
When 2 > B By symmetry to the previous case, the minimum of h22) occurs at x = B using the same reasoning.
Combining all three cases yields arg mingeR" h(z)
MMM-MM Mi
478 B' which completes the proof.
B.4. Proof of Corollary 2
Proof of Corollary 2. This corollary can be proved following the same arguments as Corollary Specifically, the mix loss for least-squares can be equivalently written
mis (P.. v) = 222 In (Ew-Ps P: [e-abe zit (w xx w-) -2B In (Egpp [e गेे (=-)))
where P the distribution over induced by Pe. Then, the arguments in the proof of Corollary 1 shows that the greedy forecaster (41) constructed based on mis (P. ensures
(=q mix .y) S -2B² In (EEpp [e 2 (t
-2B2 In EEwrr [e 29a (w (w"x, xx-=1"])
which indicates non- non-positive mixability gap and one can ensures an O(In 77) p p bound following the same argument as Theorem 1.
B.5. Proof of Corollary 3
Proof of Corollary 3. We show the mixability gap is non non- non-positive when we defined mix as (14). Let ( = 1/(1 exp(-2)). This can be shown by a direct calculation. In the case when y = 1,, 1, we have
4r(22th +1) log (1+expt ex=eep(222) = In (Ew~ (a(w T xx))) In (EwwPile 4ow (x)
For the case y = 1, we have
4r(2 mix -1 log [1 exx(2=m)))
log
4/( Ew (o(w xx)] - In (Bww 4 fu(""x)--11) xx.
Therefore, the mixability gap is exactly 0 for any dr E [+1,-110 -1}. We complete the proof by the same argument in the proof of Theorem
19

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
C. Omitted Proofs for Section 5
C.1. Properties of the Set of Distributions M
This section provides several properties about the set (19) defined as
M = ( N(w, ((w,E)dT(O)) x {0
(43)
where θ W x S and we denote by 8 = (w, E). In the above, S a {E 3 } I Amin (Σ) < Amax (Σ) S 1 is set of symmetrie positive-definite matrices with bounded eigenvalue and W C TR convex and compact domain, We present the following lemmas about the properties of the set.
Lemma 5. The M is convex and closed in topology of the total variation distance.
Proof of Lemma 5. We first check the convexity of the set. Pick two distributions Paj Saee .(W,, 2))T((( (0), Paz J (ww, Ew,2(()) in the set Al and let À E [o, 1]. Set T = Ar + (1 - A)TT. Because л is still probability measure on θ it belongs to (O)) For every Borel set A C RRd.
(A) = 1 N(w, EA) (d0) XPr, (P,,(A) (1- A)P (A),
80 PTA XPr, + (1 (1- 2) E M. Hence M is convex.
Then, we check the set is closed in topology of the total variation distance. Denote by
g (uu 8)
((2T) exp (-2(1) (u E (u w)
the density function of the Gaussian distribution N(w, Σ) with 0 = (w, E). We begin by choosing (Pr PRIn21 as an arbitrary sequence within M such that Pn convergence to a distribution P. in total variable, i.e., Pr P.IITV - 0. Because each Pn lies A by definition, can be written in mixture form as Pa
No, Σ) dTn((0) for some Fn E (()).
Since the parameter set θ W S compact, every family of mixing measures {nn)n2 C (())) is tight. By Prokhorov's theorem,
extract subsequence (Nm,)221 of (= and find a limit (()) such that
Tne = in (P)) (weak convergence).
We can also define
Pn. (u) = I g(: d) (0m (0)
and Pa. (u) / go(u)dz, (0).
Since the map 0 + g(u 0) is continuous and bounded on the compact set O we have
lim Pa. (u) Pr. (u) for all u E Rdd. R=000
(44)
In the next, show the density Pag (u) and Ps. (u) is upper bounded by integrable function ğ(u). Specifically, let [x] A max(0, 2) for any IR. For every E Rd we have
Pa (u)l f g(:: d (0) S g(u)
d/2
1 2 |||u||2 - nn3].
exp
2F
where R. a supwew |//2 < oc because W compact. The inequality follows from the bounds Ta x Σ-1
x TTa that hold for every (w, 2) O The same argument gives Pr. (u)l < g(u) for all IRd, Therefore, we have
Pr (u) Ps. (u) < 2u(
(45)
We note the dominating function g is integrable as is constant on the ball C = {u E Rd ||ul|2 S R} and decays with a Gaussian tail outside C, hence Sg gu)) du < oov' e Rdd
20

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Combining the pointwise convergence (44) and the integrable domination (45), the dominated convergence theorem yields
lim k Rd
(u) - PT. P=. (u))du 0.
(46)
Thus P.L Pr.. in L''R''' (RR). Because two probability measures with densities qı (u), 92(u) satisfy
1 ||Q - Q2 - 2 / (u) - 22 du
relation (46) implies
|| Pr. ITV = 2 1 - Pr. 11. 0.
(47)
By assumption, the original sequence {Pa]n21 converges in total variation to some limit P.. Because total variation is
metric, limits are unique; therefore P. = Px.. Finally, Pr. has already been written as the Gaussian mixture generated by weak limit n. of the mixing measures, so Pr. E E.M. Consequently, every TV-convergent sequence in A remains in A. and the is closed in the total-variation topology.
Lemma 6. For any distribution P. M, we have maxuerd (n)P(uu) S d 2
Proof of Lemma 6. According to the definition M. we have P. = N(w, (0) for some distribution n₃ on O. Then, for any u E Rd, the density can be bounded by
P((u)
/
exp
- 2
(u (u
1 (-w T w) d
(w EJEwS (2
(2 dm{(0)
(w.WIS
1
max (w.
12 (2 (T)/
where the first inequality is due to the fact that exp( S 1 for any = 2 The last inequality is due to the definition of S {Σ $t S Amiu (E) S Amax (Σ)= $ 1} and the fact that Amin (E) 2 1/T for any S. Then, have
In (u) < In
I d In
for any u E Idd, which completes the proof.
2
27
C.2. Useful Lemmas
Lemma 7. Let ((() g. (w-w.)) (g) (w wi)) where w, = E. Under Assumptions I and 5, we have
F((w.) S - In (EwwP exp ( (xp(-33((w) (-]
for any distribution Pt E A when S 1/(4GD) and w, E W.
Proof of Lemma 7. prove the lemma, sufficient to show (exppeex(((7/p))) S (xp(->//(w:)/??) for the
distribution P. M. Given the definition A (19), the distribution P. J(w.Ieee (WW,))d((() is Gaussian
21

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
mixture model, where my a distribution on O corresponding to Pt. Then, we have
Bw [exp( (xxp(=?]((w)/22] 1
Bu. (oxp (e (wt.:///oxp((0/(()))))))
(w.I)ED
2 T
- (Bi (u wi))²)
Bun,((
exp
2 B6
(w, (w)-
u)
Te Tc(d))
(W.E)
exp
2 0: (We - w)
7
g2
(gr (w wi)) Te Te((()
(W.E)E
4
(1
(wr (w)- (d(0)
Be
(w,
7 2 B1
W
Bu-N( (ww, E) (d0) 1.
(w,t)
where first inequality is due to the Gaussian exp-concavity as shown in Lemma 12 in Appendix under the condition
7/2 < 1/(5GD). The second inequality follows from the fact that e=-=² < 1 + = for any = 2 - In our case, we set 2 = - -3 (We- - w). which satisfics & 2 3/S under the condition on y and the boundedness |[ w S D for all
Wr w E W. The last inequality is due to [(w,z) du (0) = P. [w] = We-
One the other hand, due to the definition of the surrogate loss, we have exp ( - ff((w))22) = 1. We complete the proof by plugging the equality into the above displayed inequality.
The following lemma is a counterpart to Lemma I that incorporates the projection step. It shows that a similar mixability regret bound as Lemma for the surrogate loss still holds.
Lemma 8. Ler Qi = Nuu, Ia) be Gaussian distribution with mean u, E W and covariance L² E Raxd and define
M.(P) = - In (Bw-P. (exp ( 2 Filw))))-
2
7
Algorithm 3 with the update rule (15), (16) and (17) with μ 1= 1/'T ensures that the mixability regret is bounded as
Σ me(Pi) Σ Bu-q.Ifi(u))
4+ (KL(((
2 Y UER"
(Qilu) - QQ-) In
1 Pi(u)
du,
7
where KL(PIQ) = 1PE--pln (P()) refers to the Kullback-Leibh divergence.
Proof of Lemma 8. Following the same reasoning as in the proof of Lemma 1, according to the exponential-weighh update rule (15), we obtain
(P(P)) Σ (u-Qu
2
(LL(Q))P) (KL(Q.IIP-KII(QI
-
2 (L( +
2 T
Σ
7
2
+ 2
Σ /
1
2 T
[u( P.(ui)
(L( 7
(Qi(u)
Qu)) In
du +
Eunqui
E
In
7
JUER
P.(u)
1=2
2 $ (2+ (L(Q) + Σ
/
(Qi(u) Qu-1(u)) In
du
7
t=2 UERU
Po(u)
22

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
where the first inequality follows from the generalized Pythagorean theorem for KL divergence. Specifically, since the set M is convex and closed in the topology of total variation distance shown in Lemma 5, the projection P.+1 arg min (L(())))(+)) exists according to Csiszár (1975, Theorem 2.1). Furthermore, Csiszár & Matus (2003) shows that that for any Qe E M. we have KL(QeIlP)+a) 2 (L(QeIIP:+1). The last second equality follow the same reasoning in obtaining (27). The last inequality due the fixed-share step (17) with μ = 1/T, where one can show Eu-Qu-1 In (P.(w)/P((ui)] - 2/T by the same arguments in obtaining (28).
C.3. Proof of Theorem 3
Proof of Theorem 3. For 1-exx-concave loss function, Lemma 11 in Appendix D shows that the dynamie regret in terms of the original loss can be upper bounded by that in terms of the surrogate loss as
T
T
D-REGT $
Σ f((w)) - E(((u)
1=1
1=1
T
Σ ((())) - (P.)
(P)) - Σ
Eurq, f(()) +
Σ E Bunq, [f(( - E (w)))
1=1
1=1
TERM (A)
TERM (B)
TERM (c)
where mP(P) = 2 In Ew Ps exx (- (-3f((w))]] is the mix loss defined in terms of the surrogate loss.
Bounding mixability gap. For TERM (A), Lemma 7 shows the mixability gap is non-positive as TERM (A) S O.
Bounding mixability regret.
As for TERM (B), we have
TERM (B) S
4+ 2KLL(QQ))1)
Σ
T
/
(Qr(u) - Qu-1(u))
du
P:(u)
HERd
t=
2 < 2 dln ?
2
do²
D2
+
+
(Q:(u) Q-- In
du
(48)
2
2
t=2
uERd
P.(1)
where the first inequality is due to Lemma 8 in Appendix C.2, which serves as the counterpart to Lemma when the projection step is incorporated. The second inequality follows from the definitions Q1 NNu,, and Pi NWwo, Ia). together with Lemma 10.
For the last term on the right-hand side of (48), we follow the same argument as in the proof of Theorem I and decompose the integral into three regions: wx (u E Rd (u) < Qu) and Pu(u) 1). w! {u E Rd Q+(u) > 1 and (u) < 1}, and the remainder W. = Rd w!l U U Since (Q, - Q (u)) (n(1/P, I 0 for all u W. the integral over this region is non-positive. Therefore, suffices to bound the integrals over w(( and m!( For the integral over region ( We have
/ JNEWED (Qr(u)- - (u)) In
1 du S Pr(u))
T' 11Q, - QQ-1
(49)
2TT
where (49) holds by P: NNo + (1 -1) E Al and maxneR In(P:(u)) < d In T
shown in Lemma 6.
2
As for the integral over the region !2 due to the fixed-share update rule (17), the same arguments in obtaining (33) in the proof of Theorem 1 can be applied to show that
J (Qi(u) - (u) In
(d(n((TT)
+ D In ) 12: -Qu-1ll + +do2
P((u) du <
(50)
2
23

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
Then, plugging (49) and (50) back into (48) and further upper bound the total variation between Qe and Q, by the path-length shown in (35), have
TERM (B) v (d (d++2)nn?)
Pr d +1)
2D +
2d In
!
(51)
3 Bounding comparator gap. directly calculated by
As for TERM (C), given the definition of the loss function fr. the comparator gap can be
T
TERM (C) =
Σ Eu-q, Eu-Q, [Fr(u) - Fe(())
Σ Eu-Qu [Bi (u (u- un]] 2 Eune. [x (u wi))² (g7 (g](u: -w:))
t=
7 Bu-Qull8 [gg (u-ui)) --))
7 >1g Eur [I/u 11eu-uu11)) 1r12)
?do²
1= ||g
T
G2T
G
where the third equality is due to Eu-Q. [u] ue- The last second inequality is by Eu-q, (Ilu
uell2]
S (do2)/2.
Then, combining the upper bound for TERM (A), TERM (B) and TERM (C), we have
D-REGT S (d 2) D Pr d (8)
5 GG2 O
2D +
4
2d
1
+
In
7
2
7
?
0
We can further bound the above regret bound by considering different value of Pr.
Case 1: Pr S V+
We can choose
VIT to obtain D-REGT S Ogd
Case 2: Pr 2 V +.
We select a = T to obtain D-REGT S Odlogg T T Pp + dlog?).
D. Technical Lemmas
In this section, we provide several usefuu lemmas used the proof. Lemma 9 (Theorem 1.8.1 of Thara (1993)). Let Q (uug Eng) be a d-dimensional Gaussian distribution. Then the entropy of is given by
H(Q) in(2xe) In /n//
Lemma 10 (Theorem 1.8.2 of Thara (1993)). The Kullback-Leiblrr divergence between two d-dimensional Gaussian distribations P (u,, Ep) and Q = =N( Eng) is given by
Σpl E
KL(Q = In
+ TH(E, + l|u, uy u113g.1
Lemma 11 (Lemma 4.2 of Hazan (2016)). Let W C Rdd be a convex and closed set. Suppose I|u - vl12 S D holds for any u, V E W and [V](()ll z holds for any w E W. For any e-exp-concave loss, the following holds for all y S min(L/(GGD), n/2} and w, u W:
f(w) f(u) S V.(W) (w- - u) (Vf(w) (w =
24

---

Non-stationary Online Learning for Curved Loss: Improved Dyanmic Regret via Mixability
1 Consider a Gaussian distribution with Lemma 12 (Lemma 10 of Erven & Koolen (2016)). Let 0 1 S 5GD mean p W and arbitrary symmetric positive-deftnite covariance E, where W C Ted is convex and compact set. Let Cl (w) (g, w) + 1/2 w) gigl - (w). Then,
Ew-N(( exp(-[?(w))] S exp(-E,
where the domain W is bounded by D such that l|w w'll2 D for all W and ||g:|12 S G.
25


Reviews:
[{"review_id": "4ZgzXonvYQ", "reviewer": "Reviewer_xQcX", "summary": "This paper considers online convex optimization (OCO) with mixable stage cost functions. The paper proposesseveral algorithms based on exponential weights with fixed share updates to achieve an improved dynamic regret bound than the bound in (Baby & Wang 2021). The improvements are in two aspects: improvement dependence on dimension d, and a slight improvement on the log(T) term.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for very helpful comments. The main concerns are about i) presentation and ii) technical questions on the construction of mixability prediction for general functions. We first provide a concise answer and will expand the details later.\n\n- **[On Presentation]** Our paper indeed requires much improvement, and we will enhance the presentation according to your constructive suggestions. Specifically, we will: include a subsection for problem formulation, reorganize the presentation of algorithms, and expand on the implementation of key conditions, etc. These changes aim to ensure the paper is easier to read.\n- **[On mixability prediction]** For several common functions of interests (like square loss for regression, logistic loss for classification), the mixability prediction can be explicitly and efficiently constructed. For other ones, there may not have a close-form and one can obtain a feasible prediction by solving min-max optimization problems.\n\n---\n\n**Q1:** one paper presentation and assumptions \n\n> - \"paper should have a (sub)section devoted to problem formulation\" \n> - \"...do you need W to be bounded? Do you need $f_t$ to have some smoothness properties?\"\n\n**A1:** In the original submission, we stated the assumptions within the theorem statements.  For Theorem 1, it requires the loss functions to be $\\eta$-mixable and $\\beta$-smooth, along with the boundedness of the comparator domain. One potential confusion is that we allow *improper* predictions, that is,  the predictor $\\mathbf{w}_t$ can be unconstrained or take a nonlinear form—such as equations (14) or (15), which are used for least squares and logistic regression.\n\nThanks for your comments, we will revise the paper to consolidate all assumptions and the problem setting into a separate subsection at the beginning of Section 3 for improved clarify.\n\n---\n\n**Q2:** about algorithm presentation\n\n> \"first introduced Algo1, which gives no explanation on implementation issues, and only discusses how to implement it after two sections\" \n\n**A2:** The goal of Section 3.1 is to present a generic algorithmic template along with conditions that guarantee improved dynamic regret. However, we agree that deferring the discussion of specific implementations may make the algorithm less accessible. In light of this, we plan to add the following remark in Section 3.1 to provide earlier insight into the implementation:\n\n**[Revision at Section 3.1]**: *Remark 1:* Condition (4) is equivalent to the mixability condition defined in Definition 2, which ensures that for any function that is mixable over $\\mathbb{R}^d$, a predictor satisfying condition (4) always exists. In the context of online prediction with a loss function of the form $f_t(\\mathbf{w}_t) = \\ell(\\mathbf{w}_t^\\top\\mathbf{x}_t, y_t)$, where $(\\mathbf{x}_t, y_t)$ is the feature-label pair, Vovk (1999, Equations 11 and 12) and Cesa-Bianchi and Lugosi (2006, Proposition 3.3) provide a general optimization framework for constructing such predictors (which may be improper). Moreover, for the squared loss and logistic loss, closed-form constructions of the predictor are available; these are discussed further in Section 4.\n\n---\n\n**Q3**: about the condition (4)\n\n> - ... it is still challenging to see how the algorithm can be implemented for general cost functions, especially the condition (4)...\n>\n> - the computation complexity of the proposed method, especially when the cost functions are in general form.\n\nA3: As mentioned in the response to *Q2*, for the online prediction problem where $f_t(\\mathbf{w}) = \\ell(\\mathbf{w}^\\top\\mathbf{x}_t, y_t)$, Vovk (1999, Equations 11 and 12) and Cesa-Bianchi and Lugosi (2006, Proposition 3.3) provide a general min-max optimization framework for constructing predictions when $\\ell$ is a mixable loss function. However, the optimal solution to this optimization problem depends on the specific structure of the loss function. \n\n---\n\n**Q4:** \"...there is no simulation provided...\"\n\n**A4:** Dynamic regret of curved functions is a very challenging and fundamental theoretical problem in non-stationary online learning, and our primary focus has been on the theoretical aspect. Nonetheless, we are happy to include additional experiments in the revised version to further support our method.\n\n---\n\n**Q5:** the paper should also review the dynamic regret analysis for OCO with strongly convex costs\n\n**A5:** Thanks for bringing this paper to our attention. It studies dynamic regret with switching costs, which is an interesting and complementary direction to our work. We will incorporate a discussion of this paper in the next version.\n\n---\n\nAlthough the current presentation indeed has certain unclear issues, we believe the core (technical) contributions are interesting and valuable to the community. We will ensure a substantial revision to improve the clarity. Please consider updating the score if these responses have properly resolved your concerns. Thanks!", "claims_and_evidence": "This is a technical paper with no simulations. All the theorems and lemmas are clearly supported by proofs.", "methods_and_evaluation_criteria": "Yes, the proposed method is evaluated by dynamic regret, which is proper and widely used in OCO literature.", "theoretical_claims": "The proofs seem correct after a quick read.", "experimental_designs_or_analyses": "There is no simulation provided.", "relation_to_broader_scientific_literature": "This paper considers a different property, mixability,  on the OCO stage cost function than the commonly considered convexity and strong convexity. A new algorithm is proposed to leverage this different property.", "essential_references_not_discussed": "Since the mixability is closely related with strong convexity and one supporting example is quadratic loss which is strongly convex, the paper should also review the dynamic regret analysis for OCO with strongly convex costs, for example [1] discusses the fundamental lower bound of dynamic regret for OCO with strong convexity in Theorem 1.\n\n[1] Li, Y., Qu, G. and Li, N., 2020. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. IEEE Transactions on Automatic Control, 66(10), pp.4761-4768.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper explores a different property in the convex functions that enjoy applications in logistic regression. Based on this property, this paper proposes novel algorithms to exploit this property and achieve better dynamic regret bounds.\n\n2. The illustration Figure 1 is helpful for clarity.\n\n3. The discussions on implementation of the proposed algorithms on three specific examples in Section 4 is also very helpful for understanding the paper and implementing the proposed algorithms.\n\nWeaknesses\n\n1. The paper is not very easy to read in general. There is no section for problem formulation, some assumptions and problem settings are in Section 1, some in Section 2, some in Section 3. It is very difficult to read and understand the key setting and the assumptions needed for the proposed algorithm and the regret analysis.\n\n2. Though the paper discusses the implementation of the algorithms in three examples, it is still challenging to see how the algorithm can be implemented for general cost functions, especially the condition (4). \n\n3. There is no simulation provided, casting doubt on the applicability of the proposed algorithms.\n\n4. The paper could benefit from more discussions on the computation complexity of the proposed method, especially when the cost functions are in general form.", "other_comments_or_suggestions": "1. The paper should have a (sub)section devoted to problem formulation, with settings and assumptions in one place and stated explicitly. For example, do you need W to be bounded? Do you need f_t to have some smoothness properties? \n\n2. It is better to provide some overview for the algorithms in all sections. The paper first introduced Algo1, which gives no explanation on implementation issues, and only discusses how to implement it after two sections. It is very confusing for the reader at their first read.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "z4oIZohzE6", "reviewer": "Reviewer_jqG3", "summary": "This work proposes an algorithm for non-stationary online learning under mixable losses. They provide better dynamic regret bounds in comparison to the existing results in terms of the dependence on the dimension and logarithmic redundancy.\n\n## update after rebuttal\nI keep my score which remains positive.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating the novelty of our methods and for the constructive suggestions. In the revision, we will include a more detailed comparison with Baby and Wang (2021) in the introduction, highlighting the issue of proper learning and the underlying assumptions. Below, we address the questions regarding the differences in proof techniques.\n\n**Q1:** The manuscript would benefit from a more detailed comparison of the proof techniques to further legitimize your claims.\n\n**A1**: Thank you for the helpful comments. Compared with Baby and Wang (2021) and subsequent literature, our work adopts a completely different analytic framework to achieve an improved dynamic regret bound. This distinction is evident in both the algorithmic design and the theoretical analysis.\n\n- *From the perspective of algorithmic design*, the main challenge is how to adapt to non-stationary environments without prior knowledge of $V_T$. Baby and Wang (2021) and the subsequent work address this by employing a strongly adaptive algorithm to ensure adaptivity. In contrast, our method leverages the idea of fixed-share updates over a continuous space. This fundamental difference in algorithmic approach leads to a completely different proof technique in the analysis.\n\n- *On the theoretical side*, the core challenge in Baby and Wang (2021) lies in proving improved dynamic regret for a strongly adaptive algorithm. This requires using KKT conditions to characterize an offline optimal sequence and demonstrating that a strongly adaptive algorithm can track this sequence with low cost. In contrast, our analysis is based on the concept of mixability. By carefully designing the comparator distribution $Q_t$, we are able to directly establish the optimal improved dynamic regret bound.\n\nWe will clarify these points in the revision at the introduction level.", "claims_and_evidence": "I do not see any problematic claims.", "methods_and_evaluation_criteria": "I do not see any major issues with the methods.", "theoretical_claims": "The proofs seem correct.", "experimental_designs_or_analyses": "No numerical experiments.", "relation_to_broader_scientific_literature": "Improved dynamic regret bounds for mixable or exp-concave losses are valuable for the online learning literature.", "essential_references_not_discussed": "There does not appear to be missing essential references.", "other_strengths_and_weaknesses": "While the dynamic regret improvement is a strength, comparisons to the existing literature are a bit lacking. While some comparisons to Baby & Wang, 2021; 2022 are made, they should be discussed in more detail. The proper learning setting should be more clearly discussed and compared. When comparing, altering the regret dependency on dimension $d$ by relying on $L_1$ and $L_2$ norm relation should be more adequately discussed and motivated. \n\nThe results appear new and it seems the main idea is to exploit the mixability property as opposed to utilizing the primal and dual variable structure imposed by the KKT conditions. The manuscript would benefit from a more detailed comparison of the proof techniques to further legitimize your claims.", "other_comments_or_suggestions": "The paper will benefit from an earlier detailed comparison. I suggest the authors to provide a detailed comparison table in page 2 and move section 4.4 to section 1 as well. The comparison table should extend Table 1, still including the prior works, especially Baby & Wang, 2021; 2022. In addition to specific settings, compare their general regret results as well (possibly using the mixability coefficient). It should also provide differing assumptions if any.\n\nAlso, correct the typos such as \"mixablity\" in lines 204 and 208.", "questions_for_authors": "What different techniques do you use in comparison to Baby & Wang (2021; 2022) to achieve the improved dynamic regret bounds?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X9HhUZGqKm", "reviewer": "Reviewer_NuLh", "summary": "This paper studies non-stationary online convex optimization with mixable loss functions. The class of mixable function includes the exp-concave functions. This paper proposes a fixed-share algorithm for continuous space. In each round, the proposed algorithm requires to obtain a decision satisfying a certain inequality concerning loss function in the round. The paper demonstrates that such a decision can be obtained when the loss function is one of squared, least-squares, or logistic losses. The proposed algorithm achieves $O(d\\log T + (d + \\log(T / P_T)) T^{1/3}P_T^{2/3})$-dynamic regret, significantly improving existing results with respect to $d$. Furthermore, it offers a simpler and more comprehensible proof compared to previous analyses.\n\n## update after rebuttal\nThank you for your response.\nMy concerns have been addressed, so I raised my score.\n\nI would like to draw your attention to the fact that the definition of mixable functions will change, so the logarithmic function (example 3) will no longer be an appropriate example.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your very careful review and pointing out two technical problems. We have provided a detailed proof for equation (13), and clarify that our Theorem 1 indeed requires the mixability of loss functions over $\\mathbb{R}^d$. These issues will not affect the key contributions of our paper, but we acknowledge that they were not stated with sufficient precision. We will carefully revise the paper to address these imprecisions and ensure clarity.\n\n---\n\n**Q1:** the optimal solution of line 959.\n\n**A1:** Thanks for the detailed inspection of our proof. Here, we provide a more thorough explanation of why equation (13) represents the optimal solution.\n\n*Proof.* First, observe that $m_{sq}(P, y)$ is constant for a given value of $y$. Let us define $M_1 = m_{sq}(P, B)$ and $M_2 = m_{sq}(P, -B)$. The optimization problem in line 959 can then be reformulated as:\n\n$~~~~~~~\\begin{equation}\\arg\\min_{z \\in \\mathbb{R}^d} \\max\\\\{(z - B)^2 - M_1, (z + B)^2 - M_2\\\\}.\\end{equation}$\n\nDefine the functions $g_1(z) = (z - B)^2 - M_1$ and $g_2(z) = (z + B)^2 - M_2$. We have the follow close-form solution for the inner optimzation problem:\n\n$~~~~~~~\\begin{equation} h(z) = \\max\\\\{g_1(z), g_2(z)\\\\} =  \\begin{cases} g_1(z), \\& \\text{if } z \\leq z_*, \\\\\\ g_2(z), \\& \\text{otherwise}, \\end{cases}\\end{equation}$\n\nwhere $z_* = \\frac{M_2 - M_1}{4B}$. We now analyze three separate cases:\n\n1. When $-B \\leq z_* \\leq B$:\n\n   - For $z \\in (-\\infty, z_*]$, $h(z) = g_1(z)$, which is decreasing since $z_* \\leq B$.\n   - For $z \\in [z_*, \\infty)$, $h(z) = g_2(z)$, which is increasing since $z_* \\geq -B$.\n\n   Hence, the minimum of $h(z)$ is achieved at $z = z_*$.\n\n2. When $z_* < -B$:\n\n   - On $(-\\infty, z_*]$, $h(z) = g_1(z)$ remains decreasing, and the minimum in this interval is at $z = z_*$.\n   - On $(z_*, \\infty)$, the minimum of $h(z)$ is at $z = -B$ since $h(-B) = g_2(-B) = -M_2$.\n\n   Under the condition $z_* \\leq -B$, one can verify that $h(-B) \\leq h(z_*)$, so the overall minimum is attained at $z = -B$.\n\n3. When $z_* > B$: By symmetry to the previous case, the minimum of $h(z)$ occurs at $z = B$ using the same reasoning.\n\nBy combining all three cases, we can show that the optimal solution is given in equation (13). We will clarify this reasoning in the revised version of the manuscript. $\\blacksquare$\n\n---\n\n**Q2:** \".... it actually relies on stronger assumptions, ...Definition 2..., ...Theorem 1...\" ($\\mathcal{W}$ versus $\\mathbb{R}^d$). \n\n**A2:** Thanks for pointing out this issue. Theorem 1 indeed requires the mixability of loss functions over $\\mathbb{R}^d$. We apologize for the confusion caused by the imprecise statements. We now describe the assumptions and decision domain more precisely.\n\n- **On assumption:** Our assumption for Algorithm 1 is that the loss function is mixable over $\\mathbb{R}^d$, which is necessary due to the use of a Gaussian prior in the algorithm. This assumption is satisfied by several commonly used curved loss functions in online learning, such as the squared loss and logistic regression loss, as discussed in Examples 1 and 2 and elaborated on in Section 4. Moreover, while the algorithm maintains a distribution over $\\mathbb{R}^d$, we emphasize that for certain losses—such as the squared loss—the resulting final predictor $w$ can still lie within the domain $\\mathcal{W}$, as shown in Section 4.1.\n- **On decision domain:** In the generic algorithmic template, we allow the improper learning where the predictor $\\mathbf{w}_t$ is outside the domain $\\mathcal{W}$, while the comparator remains constrained within $\\mathcal{W}$. Therefore, the proposed method may be improper depending on the loss function. For the squared loss, we obtain a *proper* learning algorithm, but for least-squares regression and logistic regression, the method should be considered *improper*, as discussed in Section 4.\n\n---\n\nTo ensure that the assumptions and problem setting are clearly presented for the generic template, we will add a new subsection at the beginning of Section 3 to explicitly state the assumptions and capabilities of the learner. We will add the proofs for equation (13) in the paper. \n\nPlease consider updating the score if our responses and the additions in the revised version have adequately addressed your concerns. Thank you!", "claims_and_evidence": "The paper claims to utilize the concept of mixability for analysis. However, it actually relies on stronger assumptions. Specifically, the proposed algorithm requires $w \\in \\mathcal{W}$ that satisfies equation (4) for the loss function, which differs slightly from the inequality in the definition of a mixable function (Definition 2). Since Definition 2 deals with distributions whose support is $\\mathcal{W}$ and equation (4) handles distributions supported on $\\mathbb{R}^d$, it has not been shown that mixable functions always possess $w$ that satisfies equation (4). Moreover, Theorem 1 supposes that the diameter of $\\mathcal{W}$ is at most $D$, ensuring these inequalities do not align. Thus, as I understand it, the paper employs mixability-inspired conditions for its analysis rather than direct mixability.", "methods_and_evaluation_criteria": "The usage of dynamic regret as a performance metric for non-stationary online learning seems appropriate. The analyses indicate that the proposed algorithm achieves near-optimal performance.", "theoretical_claims": "I examined the proof sketch for Theorem 1, the proofs of Theorem 3, and Corollaries 1, 2, and 3. In Corollary 1, I am unclear on why $z$, as defined in equation (13), satisfies equation (4), potentially due to omitted critical arguments.", "experimental_designs_or_analyses": "There don't appear to be discrepancies in the design or methodology, and they are clearly explained.", "relation_to_broader_scientific_literature": "While the paper's results are limited to typical exp-concave functions, it achieves near-optimal regret bounds through highly versatile analysis using the conditions inspired by mixability.", "essential_references_not_discussed": "It appears the necessary prior works have been appropriately cited and discussed to comprehend the contributions.", "other_strengths_and_weaknesses": "Though the algorithm's optimal performance is restricted to some typical loss functions, the novel ideas and straightforward analysis constitutes a noteworthy contribution. The paper is generally well-written and accessible. However, the paper's connection to mixable functions deserves a more precise discussion.", "other_comments_or_suggestions": "- line 78 (right column): meethod -> method\n- Eq. (6): N_0(u) -> N_0\n- There is inconsistency in the order of arguments in mixed losses. In squared loss, it's denoted as $m(P, y)$, but in least-square loss as $m(y, P)$.\n- Proof of Corollary 1\n  - lines 944-945: inequality (3) -> inequality (4)\n  - line 945: (3) is essentially -> (13) is essentially\n  - line 956: give a fixed $z$ -> given a fixed $z$\n- Appendix B.3 should be integrated into Appendix A.", "questions_for_authors": "1. Could you provide a more detailed proof regarding why equation (13) satisfies equation (4)? Specifically, it is not obvious to me that equation (13) is the optimal solution of the optimization problem defined on line 959.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YlYx7BzPye", "reviewer": "Reviewer_Ukmi", "summary": "This paper shows that the fixed share algorithm is able to obtain optimal dynamic regret under mixable losses with improper online learning. They also obtain the first gradient variation based dynamic regret bounds under curved losses. The results are novel to the best of my knowledge.\n\n### Post Rebuttal ####\nI have read the authors' responses and comments by other reviewers. I think this paper definitely makes a significant progress in dynamic regret literature. I also agree with other reviewers that the presentation of the paper can be greatly improved along with a more coherent discussion regarding prior works.\n\nThe comment from authors regarding the applicability of improper to proper reduction under linear / logistic regression is not convincing enough. Note that in this case the availability of covariate before making the prediction allows us to know the gradient of the loss upto a scaling factor. This information along with exp-concavity of losses can be exploited for constructing the reduction.\n\nI believe that a careful revision that addresses the above concerns can greatly benefit the readers and can make the paper more complete and impactful. Based on this, I would like to maintain my score.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your expert comments! We will address your main concerns regarding the literature comparisons. Without a doubt, Baby and Wang pioneered the line of dynamic regret for exp-concave/strongly convex functions. While we attempted to make a comparison, we unfortunately missed two relevant references, which will be included in the revised version. Moreover, we will add a paragraph discussing the limitations of fixed-share-type methods, which is attached at the end of this rebuttal.\n\n---\n\n**Q1:** \"requires to know the form of losses beforehand\"\n\n**A1:** Thank you for pointing this out. Yes, constructing the mixability mapping requires focusing on specific loss forms. While this may be a limitation of mixability-based methods, the form of loss is often predetermined in many applications. Examples include online nonparametric regression, online classification, and LQR control, as the reviewer noted. We will clarify this in the next revision\n\n---\n**Q2:** \"current work assumes gradient Lipschitnzess for the losses\"\n\n**A2:** Thank you for the comments. In Theorem 1, we state that $\\beta$-smoothness is required to achieve the improved bound. We believe this is a mild assumption, as many curved losses, like those in Section 4, are smooth. That said, removing the smoothness assumption, as done by Baby and Wang et al. (2022), remains a quite interesting question. We will clarify this comparison in the next revision.\n\n---\n\n**Q3:** \"Results of Baby and Wang 2021, 2022 can also work with sleeping experts style experts.\"\n\n**A3**: Currently, achieving $O(\\log T)$ time complexity for the fixed-share method is challenging due to the need to add a small portion of the prior distribution $N_0$ at each iteration. We will clarify the time-complexity comparison in the revision.\n\n---\n\n**Q4:** two missing references and comparisons\n> - unaware about the following important references...\n> - Table 2: comparison regarding run-times as well as the inclusion of prior works.\n\n**A4:** We will definitely include these two papers and update the table to include the time complexity of the compared methods.\n\n$\\dagger$ Indicates that the time complexity can be improved to $O(\\log T)$ using more refined geometric covering techniques.\n\n| Losses              | Method                                | Regret Bound                                    | Proper Learning | Time Complexity  |\n| - | -| - |- |- |\n| Least-squares loss  | Theorem 5 (Baby and Wang, NeurIPS'22) | $\\widetilde{O}(d + d^{10/3} T^{1/3} P_T^{2/3})$ | Yes            | $O(T)^{\\dagger}$ |\n| Logistic regression | Theorem 3.1 (Baby et al., TMLR'23)    | $\\widetilde{O}(d + d^{10/3} T^{1/3} P_T^{2/3})$ | Yes            | $O(T)^{\\dagger}$ |\n\n---\n\n**Q5:** losses that are mixable but not exp-concave in a compact domain?\n\n**A5:** To our knowledge, common mixable losses, like squared loss, logistic loss are also exp-concave with generally larger coefficients. A key difference is that the mixability coefficient $\\eta_{\\mathtt{mix}}$ typically does not depend on the diameter of the decision domain $\\mathcal{W}$, whereas the exp-concavity coefficient $\\eta_{\\mathtt{exp}}$ often does. For example, the logistic loss is 1-mixable over $\\mathbb{R}^d$ but only $e^{-D}$-exp-concave within a bounded domain $\\mathcal{W}$ of diameter $D$. Consequently, mixability-based results may extend to unconstrained comparators, while exp-concavity-based methods generally require bounded domains.\n\n---\n[Revision: Section 4.4]\n**Limitation and Future Work:**  Although our method achieves improved dynamic regret without relying on KKT-based analysis, there remain several directions for improvement.  First, regarding time complexity: our method matches the $O(t)$ complexity of Baby and Wang et al. (2021, 2022) for the squared loss. However, prior work can further reduces this to $O(\\log T)$ by using the sleeping expert algorithm with a geometric cover, incurring additional multiplicative logarithmic factors in regret. Incorporating this idea into the fixed-share update is a promising direction.  Second, while common curved losses like squared loss and logistic regression are smooth, the analysis by Baby and Wang et al. (2022) does not require smoothness. Removing the smoothness assumption in mixability-based analysis remains an interesting theoretical challenge.  Finally, to construct the mixable prediction $z_{\\mathtt{mix}}$, mixability-based methods require the loss function to have a specific form, unlike the approach by Baby and Wang et al. Although this condition holds in many applications—such as online nonparametric regression, online logistic regression, and LQR control—it is worth exploring whether we can aggregate distributions efficiently using exp-concavity instead of mixability.\n\n---\n\nWe will add these discussions and include a fair comparison to Baby and Wang's line of work. Please consider updating the score if our responses and the additions have adequately addressed your concerns. Thank you!", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Math was not checked in detail.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "Discussed in the related work of the paper.", "essential_references_not_discussed": "The authors seem unaware about the following important references. In Table 2, the problems of optimal dynamic regret for proper learning under linear and logistic regression losses were reported to be unsolved. However, they have been addressed affirmatively in the following two papers.\n\n1) Optimal Dynamic Regret in LQR Control, D Baby and YX Wang, NeurIPS 2022 (solves multi-task linear regression)\n\n2) Non-stationary Contextual Pricing with Safety Constraints, D Baby, J Xu and YX Wang, TMLR 2023 (solves general GLM type losses, including logistic regression)", "other_strengths_and_weaknesses": "See Questions For Authors.", "other_comments_or_suggestions": "See Questions For Authors.", "questions_for_authors": "I believe this paper provides novel insights into a hard problem. My only complaint is that I would like to see a more careful comparison with prior works of Baby and Wang on this topic. This helps to place the current work appropriately in the literature and provides researchers to better understand the pros and cons of each approach. \n\n1) The current work requires to know the form of losses beforehand to compute the output of mixability mapping. Baby and Wang 2021, 2022 do not require to know the form of losses beforehand. Specifically Baby and Wang 2022, requires only access to gradients of the losses.\n\n2) The current work assumes gradient Lipschitnzess for the losses while bounding the comparator gap. I did not see this explicitly stated in any assumptions, but only mentioned in the proof sketch. The work of Baby and Wang 2022 does not require this assumption.\n\n3) Results of Baby and Wang 2021, 2022 can also work with sleeping experts style experts. This reduces the per-round complexity logarithmically. For example, for squared error loss, we obtain a per-round complexity of $O(\\log T)$ while blowing the regret up by a logarithmic factor. Does something similar hold true for your approach? \n\n4) In Table 2, I would like to see a comparison regarding run-times as well as the inclusion of prior works that solves the problem of proper learning under linear and logistic regression losses mentioned in the section Essential References Not Discussed above. This way the comparison will be more complete and fair and will directly convey the readers about the merits and demerits of each approach.\n\n5) Are there examples of losses that are mixable but not exp-concave in a compact domain?\n\nI would be happy to see this manuscript accepted in a venue after including the aforementioned details.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies dynamic regret in the setting of mixable losses. The authors show that using exponential weights with fixed-share updates improves existing regret upper bounds, which previously required the stronger exp-concavity assumption and a more involved analysis.

The reviewer raised concerns about clarity, limited comparison with prior work, and the potentially prohibitive computational complexity for general losses beyond the squared loss. However, they also acknowledged the paper’s technical novelty and its significant contribution to the dynamic regret literature.

The authors are encouraged to carefully address these reviewer comments in the final revision — particularly by improving the clarity were suggested, strengthening the discussion of related work, and clarifying the applicability of the improper-to-proper reduction.
Decision: Accept (poster)