Adapting to Continuous Covariate Shift via Online Density Ratio Estimation
Authors: Yu-Jie Zhang
Zhen-Yu Zhang
Peng Zhao
Masashi Sugiyama
Venue: NeurIPS 2023 poster (2023)
Keywords: Covariate Shift
Density Ratio Estimation
Online Convex Optimization
Dynamic Regret
Logistic Regression

Abstract: Dealing with distribution shifts is one of the central challenges for modern machine learning. One fundamental situation is the covariate shift, where the input distributions of data change from the training to testing stages while the input-conditional output distribution remains unchanged. In this paper, we initiate the study of a more challenging scenario --- continuous covariate shift --- in which the test data appear sequentially, and their distributions can shift continuously. Our goal is to adaptively train the predictor such that its prediction risk accumulated over time can be minimized. Starting with the importance-weighted learning, we theoretically show the method works effectively if the time-varying density ratios of test and train inputs can be accurately estimated. However, existing density ratio estimation methods would fail due to data scarcity at each time step. To this end, we propose an online density ratio estimation method that can appropriately reuse historical information. Our method is proven to perform well by enjoying a dynamic regret bound, which finally leads to an excess risk guarantee for the predictor. Empirical results also validate the effectiveness.

Adapting to Continuous Covariate Shift via Online Density Ratio Estimation
Yu-Jie Zhang', Zhen- Yu Zhang? Peng Zhao
Masashi Sugiyama 2.1
1 The University of Tokyo, Chiba, Japan RIKEN AIP, Tokyo, Japan
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China
Abstract
Dealing with distribution shifts is one of the central challenges for modern machine learning. One fundamental situation the covariate shift, where the input distribu- tions of data change from the training to testing stages while the input-conditional output distribution remains unchanged. In this paper, we initiate the study of a more challenging scenario contimuous covariate shift in which the test data appear sequentially, and their distributions can shift continuously. Our goal is to adaptively train the predictor such that its prediction risk accumulated over time be minimized. Starting with the importance-weighen show the method works effectively if the time-varying density ratios of test and train inputs can be accurately estimated. However, existing density ratio estimation methods would fail due to data scarcity at each time step. To this end, we propose an online density ratio estimation method that can appropriately reuse historical information. Our method proven to perform well by enjoying a dynamic regret bound, which finally leads to an excess risk guarantee for the predictor. Empirical results also validate the effectiveness.
learning, we theoretically
Introduction
How deal with distribution shifts is one the central challenges for modern machine learning [1, 2]. which is also the key requirement of robust artificial intelligence in open and dynamic environments [3. 4]. Covariate shift a representative problem setup and has attracted much attention [5, 6]. where the input density D(x) varies from training data to test data but their input-conditional output D(y x) remains unchanged. On the one hand, covariate shift serves as foundational setup for theoretically understanding general distribution shifts [7]. and on the other hand, it can encompass many real-world tasks such as brain computer interface [8], speaker identification [9] and audio processing [10].
Existing works of coping with covariate shift mainly focused on the "one-step" adaptation, where the learner aims to train model well-performed on fixed testing distribution. To mitigate the distribution discrepancy, common and classic solution is the importance-wiightin framework [6]. where one assigns an appropriate importance weight each labeled training sample and then conducts weighted empirical risk minimization. The importance weight, also known as the density ratio of test and training inputs, usually needs to estimated via a reasonable amount of unlabeled data sampled from the testing distribution [11, 11, 12]. However, the one-step adaptation can be insufficient in many real-world covariate shift scenarios, especially when data are accumulated an online fashion such that testing environments continuously shift and only few unlabeled samples are observed at each time. For instance, in the speaker identification task, the speech features vary over time due to session
"Correspondence: Yu-Jie Zhang <yujie. zhang @ms.k k.w.....tooooooo www.ttyo.ac..pppp and Peng Zhao cchaop@lamda.ju.edu..com
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

dependent variation, the recording environment change, and physical conditions and emotions of the speakers [9]. Therefore, it is necessary to perform a prompt adaptation to the changes.
Motivated by such demands, we initiate the study of continuous covariate shift, where the learner's goal is to adaptively update the model to minimize the risk accumulated over time (see the formal definition in Section 3). To achieve this goal, we propose the ACCOUS approach (Adapt to Continuous Covariate shift with Unlabeled Stream) equipped with sound theoretical guarantees. Our approach is based on the classic importance-weighttnng framework yet requires innovations to make it applicable to the continuous shift scenario. Indeed, we theoretically identify that the importance- weighttng works effectively if the cumulative estimation error of the üime-varying density ratios of train and test inputs can be reduced. However, at each time step, direct application of one-step density ratio estimation would lead to a high variance due to data scarcity; whereas reusing all previous data can be highly biased when testing distributions change dramatically. Thus, it erucial to design an accurate estimation of time-varying test-train density ratios by appropriately reusing historical information.
To combat the difficulty, we propose generic reduction of the problem to the online convex optimization [13]: one can immediately obtain high-quality time-varying density ratios by suitable online process to optimize its dynamic regret over certain sequence of loss functions. Our reduction is based on the Bregman divergence density ratio matching framework [14] and applicable to various existing density ratio estimation models with specific configurations of the divergence functions. To minimize the dynamic regret, our key algorithmic ingredient of this online optimization the online ensemble structure [15, 16], where a group of base-learners is maintained to perform density ratio estimation with different lengths of historical data, and meta-algorithm employed to combine the predictions. As such, we can properly reuse historical information without knowing the cumulative intensity of the covariate shift. We further instantiate the reduction framework with the logistic regression model [17]. Letting Vr E/=2|lD(
density ratio estimation
(x)1
prove an O(T1/3/2/3) dynamic regret bound for the density ratio estimator, which finally leads to an O(T-1/3/=1/$ averaged excess risk of the predictor trained by importance- -eeeraeee-weigghed weighted learning. The rate can hardly be improved even if one receives labels of the testing stream after prediction (see more elaborations below Theorem and Appendix D.6). Finally, we conduct experiments to evaluate our approach, and the empirical results validate the theoretical findings.
Technical Contributions. We note that online ensemble was also employed by [18] to handle continuous label shift. another typical distribution shift assuming the change happens on the class prior (y). However, their method crucially relies on the unbiasedness of weights in the risk estimator, whereas density ratio estimators for covariate shift adaptation cannot satisfy the condition in general. Instead of pursuing unbiasedness, we delicately design an online optimization process to learn the density ratio estimator, which is versatile to be implemented with various models. Our methodology is very general and might be of broader use, such as relaxing the unbiasedness requirement in the continuous label shift. Besides, the 0(r1/3y2/3) dynamic regret bound for the logistic regression density ratio estimator is obtained non-trivially. Our bound essentially holds for online learning with exp-concave functions under noisy feedback. The only one achieving this [19] holds in expectation and requires complicated analysis on the Marush-Kuun-Tuckee (KKT) condition [20] of comparators. By contrast, our bound holds in high probability, and the analysis is greatly simplified by virtue of exploiting the structure of comparators in our problem that they are essentially the minimizers of expected functions (hence without analyzing the KKT condition).
2 Preliminaries
This section introduces the preliminaries and related work on the continuous covariate shift adaptation. We discuss the related work on non-stationary online learning in Appendix B
One-Step Covariate Shift Adaptation. Let Du(x, y) and (x y) be the training and test dis- tributions. The "one-step" adaptation problem studies how to minimize the testing risk R₁ (w) = (xx.))>D,(x.)) [[(w"] x,)) by the model trained with labeled dataset So (xi, y: Vi sampled from Do(x, y) and unlabeled dataset S, = ) sampled from D, (x). We call this one-step adaptation since the test distribution is fixed and a reasonable number of unlabeled data S₁ is available.
No
Importance- FRM. A classic solution for the one-step covariate shift adaptation the -iportance-weightee empirical risk minimization (IWERM), which mitigates the distribution shift

---

by minimizing the weighted empirical risk R1 (w) = (r x, u)l, where (x)
Di (x)/ /Do(x) is the importance weight. The risk (w) is unbiased to Ri (w) and thus the learned model is consistent over the test distribution [5]. The importance weighted learning was studied from the lens of variance-bias trade off [5, 21], cross validation [22], model misspecification [23], and deep neural network implementation [24]. All those conducted under the one-step adaptation scenario.
Density Ratio Estimation. The importance weighted estimation, also known as the density ratio estimation (DRE) [12], aims to estimate the density ratio r (x) using datasets input of So and S1. Various methods were proposed with different statistical models [14, 17, 25, 26, 27, 28, 29]. All those methods focused on the one-step adaptation, and it is challenging to extend them to the continuous shift due to the limited unlabeled data at each time step. The work [30] studied how to update the density ratio estimator with streaming data, but the ground-truth density ratio is assumed to be fixed. Recently, the time-varying density ratio was investigated [31]. Their problem setup fundamentally differs from ours as they assume sufficient online data at each iteration, while our challenge is dealing with limited data per iteration. The work [32] proposed to learn the time- varying density ratios using all past data at each time. Although learning theory insights are provided in the paper. it is still unclear how the learned density ratios balance sample complexity with environmental shift intensity. In contrast, our density ratio estimator updates in an online fashion with dynamic regret guarantees.
Continuous Distribution Shift. For broader continuous distribution shift problems, the study [33] focused on the label shift case and provided the first feasible solution. Then, the work [18] introduced modern non-stationary online learning techniques to the problem, developing the first method with dynamic regret guarantees. As shown in Remark 2, our solution refines the previous methods [33, 18] by decoupling density ratio estimation from predictor training. paving the way for a theoretically- grounded method for continuous covariate shift. Similarly, the subsequent work [34] developed method for continuous label shift, which allows for training the predictor with various models by separately estimating the label probability through online regression oracle. Another research [35] studied the change detection for continuous covariate shift. However, they only focused on identifying differences between the current and initial offline distributions, and it is still unclear how update the model adaptively with the online data. Moreover, the method [35] can only detect at given time granularity, while ours can perform the model update at each round.
3 Adapting to Continuous Covariate Shift
In this section, we formulate the problem setup of continuous covariate shift and then introduce our approach based on the IWERM framework and online density ratio estimation.
3.1 Problem Setup
There are two stages in continuous covariate shift. The first one is the offline initialization stage, where the learner can collect reasonable number of label data Sg = (x,, 2n Noo from the initial distribution Dy. Then, we come the online adaptation stage, where the unlabeled testing data arrive sequentially, and the underlying distributions can continuously shift. Consider a -round online adaptation. At each round t E [T] & (I....,
".....T), T}. the learner will receive an unlabeled dataset S, = {x,, 1 n=1 sampled from the underlying distribution D,- Without loss of generality, we consider N, 1. We have the following continuous covariate shift condition.
Assumption (Continuous Covariate Shift). For all x E X' in the feature space, y E y in the label space, and any E [T]. we have
D2(y x) Doly x) and (x()) = D,(x)/D((x) S B < 80.
We note that there are emerging discussions on the necessity of covariate shift adaptation [7, 23). When there are infinite number of training samples, well-specified large and ever-parametrize model can be trained to approximate Do(y x) and there is no need to perform covariate shift adaptation. However, in the finite-sample cases, one would prefer to train model with constraint complexity to ensure its generalization ability, which leads to model misspecification and covariate shift adaptation is indeed necessary. In this paper, we study the continuous covariate shift under misspecified hypothesis space W. which generalizes the standard one-step covariate shift problem (see [6] and reference therein) to the continuous shift case. Our goal is to train sequence of model
3

---

1wik-1 that are comparable with the best model wł E arg wew Ra (w) in the hypothesis space each time. Consequently, we take the following average excess risk as the performance measure:
T Σ (w.)
T
(T A T
Σ Ro(w:))
We end this part by listing several common notations used throughout the paper. We denote by R = maxxex|| the maximum norm of the input and by D = wyeW [| w2ll2 the diameter of the hypothesis space W C R. The constant G = x.E weW wew/|Ve(ww VV[( x, y)2 is the maximum gradient norm and L = "EE wew [<(w x, y) is the upper bound of the loss values. We use the (-)-notttioon to hide dependence on logarithmic factors of T'.
3.2 Importance Weighted ERM for Continuous Shift
Our algorithm is based on the importance weighted learning. Consider the scenario where the learner has predefined F; X + [0. B] an estimation for the true density ratio r (x) (x)) (x)
for each time / E [T). Then, the predictor can trained by the importance weighted ERM method:
W. arg minwew
wew Ex-So (x)) (e][(((Tx))) x),]
(2)
The averaged excess risk of the predictor is closely related to the quality of the density ratio estimator.
Proposition 1. For any (0,1), 11, with probability at least 6, IWERM (2) with the estimator (x() ensures (r s 2 Ei=1Exss Ex [[f((x) - rî (x)]) + (log((T /
/No)
In above, the (log T/vNo) term measures the generalization gap of the predictor since it is trained over the empirical data So instead of Do. Such a rate is tight up to a logarithmic factor in T. Indeed, considering a stationary environment (i.e., Dz(x, y) - Di (x, 2)) and an exact density ratio estimation (i.c., (x) = r? (x)), Proposition indicates that the averaged model WT = Σ w enjoys an excess risk bound of R1 (w))) R₁ (w") < Olog /o)),, matching the lower bound for importance weighted learning [36, Proposition 2] up an Ollog T) factor.
Our main focus lies on the Σln [ error of the density ratio estimator F' to the time-varying ground truth r7. To minimize the estimation error, a fundamental challenge comes from the unknown non-stationarity exhibited in the online environments - how select right amount of historical data to reuse for each iteration? Intuitively, the environments change slowly, would be preferable to reuse all historical data to construct the density ratio estimator f,. However, when distribution shifts occur frequently, earlier data could be useless even potentially harmful. In such scenarios, training the density ratio estimator with the most recent data would be more rational strategy. Furthermore, even if we could capture a roughly stationary period, it remains unclear how to update the density ratio estimator in an online manner with guarantees. To knowledge, online density ratio estimation is underexplored in the literature, even for the stationary testing streaming, not to mention the more challenging non-stationary setup.
rf (x))]/T term, which is the averaged estimation
3.3
Online Density Ratio Estimation
Here, we present generic reduction of the online density ratio estimation problem to dynamic regret minimization problem. This novel perspective paves our way for designing an algorithm in tackling the non-stationarity of environments, as mentioned in Section 3.2.
Bregman Divergence Density Ratio Matching. Our reduction is based on the Bregman divergence density ratio matching [14], a general framework that unifies various existing DRE methods. Specifi- cally, in the framework, the discrepancy between the ground-truth density ratio function rī and any density ratio function is measured by the expected Bregman divergence over (x(x) defined by
EB (rī = Ex-))(() [Bg (ri (x)]]((xx))
(3)
where B& (allb) A vaaa - (b) - (b) - b) is the Bregman divergence and 1/: dom x - IR is the associated divergence function. The expected Bregman divergence can be equally rewritten as EB (r?]lr) L (r) LY (r?), where LX" is the loss for the density ratio function defined by
1 (r) = ExxDD. (x))r()))r(x) - <x((x))] - Ex [+)(r(x))]

---

As consequence. one can train the density ratio estimator by minimizing the loss (r). We have r arg min L (r) when H is the set of all measurable functions.
The Bregman divergence- based density ratio matching framework takes various DRE methods as special cases. For instance, choosing the divergence function as c/ = (t - /2 yields LSIF [28] and KMM [26]; choosing (')R(() = / log - (L + 1) log(l + 1] leads to the logistic regression method [17]; and one can also recover the UKL [37] and KLLEP [25] with 4/Kl (1) = log - L.
Online DRE via Dynamic Regret Minimization. For single-round density ratio estimation, the Bregman divergence-based framework suggests to train the density ratio estimator i. by minimizing the gap L (fr) - L (rī). Therefore, to derive an estimator sequence that performs well over time, we utilize the cumulative loss gap Σ T. (Ft) E'= T.ς (r?) as performance measure. Indeed, the cumulative loss gap serves as an upper bound of the estimation error of density ratio estimators. Proposition 2. Let 1/ be a j-sttrongy convex function. For any density ratio estimator sequence I. (r7)) (nT).
(Fe)T= we have + Σi= Bx (F: - rx(( < 2
Proposition 2 indicates that it suffices to optimize the cumulative loss gap to perform online density ratio estimation. Such a measure quantifies the performance difference between the online algorithm (that yields the estimated ratio sequence (fr) and sequence of time-varying comparators (the true ratio sequence {ri (=)) This is exactly the dynamic regrei in online learning literature [38, 39]. As such, we have reduced the online density ratio estimation to a problem of dynamic regret minimization over loss functions (L;
e It against comparators {r; (r=)----
Since the loss function involves the expectation over the underlying distribution Do(x) (see the definition in (4)), we need counterpart result with respect to empirical data So.
Theorem 1. Let vb be a p-strongly convex function satisfying t0))(t)) I 0 and (+)((t) S for all I E dom tb. Let He = {x + h(x,0) 0) 0 θ} be a hypothesis space of density ratio functions parameterized by a finite- dimite-dimensooal bounded set θ a (0 E E2 ||0||2 S S} with certain link function h X ④ + R. Denote by [z]+ & max(2.0} 0). Then, for any density ratio estimator Po E Ho, the empirical estimation error is bounded by
T Σ Ex xx (x)) (x)] S
1
4
Σ
T
() - Σimm +0
Vállo(T/55) N/Noo
PT
provided that h(x, 0) is bounded for any x E X and 0 E Q and Lipschitz continuous. In the above,
L (r) = (x- (0)((()))))()))))))))))))))))))) - ((((x))] - (x) [0(((xx)]
(5)
the empirical approximation of the expected loss T. using the data So-
Remark (assumptions on v)). We imposed certain assumptions the divergence function & in Theorem 1. One can check these conditions hold for commonly used & in density ratio estimation, including all the divergence functions mentioned earlier (vLRR and tOKL are strongly convex when the inputs are upper bounded, which can be satisfied with suitable choices of Ho). Section 4 will present an example with vİLR to show how the conditions are satisfied.
Theorem shows that we can immediately obtain a sequence of high-quality density ratio estimators (r by minimizing the dynamic regret with respect to {EA)) 1i=1
Regi ((L) . = = T
- -
(6)
One caveat is that the second term of L in the definition (5) requires the knowledge of underlying distribution Dr, which is unavailable. Empirically, we can only observe D defined below, building upon the empirical observations S; ~ Dr,
T (r) = Ex (0((r(x))r(x) - (x(())) Ex-s, [r)(r(
(7)
That said, we need to design an online optimization process to minimize the dynamic regret (6)
defined over L based on the observed loss (L. ( yT Since the time- vireingrying comparator r² in (6)
5

---

is nor the minimizer of the observed loss D (but rather the minimizer of the expected loss L defined in (4)), directly minimizing the empirical loss L will lead to a high estimation error. In the next section, we introduce how to optimize the dynamic regret with the online ensemble framework developed in recent studies of non-stationary online convex optimization [15, 16, 19].
Remark 2 (comparison with previous work). For the continuous label shift [18], the online ensemble framework was employed to train the predictor wt. However, the previous method crucially relies on the construction of an unbiased importance ratio estimator satisfying Ep, [fr( = r (x). Such a favorable property hard to be satisfied in the covariate shift case. For example, in the Bregman divergence density ratio matching framework, one can only observe an unbiased loss T. (r), whose minimizer f = arg min, D (r) is not unbiased to the true value rī in general. To this end, we disentangle the model training and importance weight estimation process in this paper. Our reduction holds for the general Bergman divergence matching framework and thus can be initiated with different models (not necessarily unbiased). possible to extend our framework to continuous label shift problem with other importance weight estimators besides the unbiased one [40] used in [18].
4 Instantiation: Logistic Regression Model
When the loss function " is non-convex, is generally intractable to conduct the online optimization, regardless of minimizing the standard regret or the strengthened dynamic regret. Fortunately, the attained loss functions are convex enjoy even stronger curvature with the properly chosen hypothesis space and divergence function. In this section, we instantiate our framework with the logistic regression model. A corresponding online DRE method is presented with dynamic regret guarantees.
Example 1 (Logistic regression model). Consider the function & e'LR - t tlogt (t- 1) log(t 1) and the hypothesis space H&R {x - exp (-0T ((x) ||001|2 S S}. Here, Φ : X + TE represents specific basis function with bounded norm [1x(x)]12 S R. which could be, for instance, the feature representation extractor from deep neural network. Then, the loss function Ż, (8) as per (7) becomes
D (0) (Es. [log(1 + - ]0] Es, [log(1 + e0))
1
Let B = RR) Then, the output of any density ratio function E Ho is bounded by [188, 3..1 It can be validated that LAL is 1/(3+ -strongyy convex and satisfies the condition @RLR (z) < required by Theorem 1. Besides, the logistic loss is a 1/(1(1 + 3)) exxpooncae function and 12/2 /2-
smooth function, presenting favorable function properties for online convex optimization [13].
We note that the other two divergence functions t/1s and d²KL also exhibit desirable function properties as LLR- When choosing the hypothesis space He {x + 0 Φxx) I E +). the methods recover the the uLISF [28] and UKL [37] density ratio estimators equipped with the generalized linear model. Our analysis also applicable in the two cases. More details are provided in Appendix D.7.
4.1 Density Ratio Estimation via Online Ensemble
In this part, we introduce our online ensemble method for online DRE with the logistic regression model. Since the logistic regression loss is exp-concave, [19] shows that one can employ the (FLH) method [41] to minimize the dynamic regret. However, a caveat is that the observed loss L, is only an empirical estimation of L, established on few online data S.. The result of [19] only implies an expected bound for our problem.
We twisted the FLH algorithm to achieve a high probability bound. As shown in Figure 1, our algorithm maintains multiple base-learners, each learning over different intervals of the time-horizon, and then employs a meta-leamee to aggregate their predictions. We modify the meta-learner in FLH from Hedge [42] to Adapt-ML-Prod [43], which ensures that the meta-learner can track each base- learner on the associated time interval with high probability. This strategy allows us to selectively reuse the historical information to handle the non-stationary environments. We introduce ingredients of our algorithms as follows. A more detailed algorithm descriptions and comparison with the dynamic regret minimization literature in OCO can be found in Appendices D. and B respectively.
Base-learner. Our algorithm runs multiple base-learners that are active on different intervals of the time horizon. Let C {4 [st ei] C [T]} be a interval set. Each base-learner E, will only

---

1=1
1=8
update 0r, by (8) active base-learner
update Pt. by meta-learner
02 EiE,, Pe.
An illustration of our online ensemble method, where employ meta-learner aggregate the predictions from base-learners running over different intervals the time horizon.
Figure 1:
update and submit the model o,, to the meta-learner if E 4. We use the online Newton step (ONS) for the model update. For an exp-concave loss function, the method ensures the base-learner'ss model is comparable with the best fixed model over the interval up to a logarithmic factor in I [44]. Specifically, for each lase-learner & running on the interval [s,, e,l. ONS updates the model by
12+1.1 Ars [0., - 7 VL. VE E [st,e:]
8
where the matrix Ar, M + E r VL, (0,,)) VL.
the above, the projection function
arg minggelle 01 IA., and {0 E Bdd ||0||2 S 5} the parameter space. The constant À > O and 17 > O are the regularizer parameter and step size to be specified latter.
defined as A [[0]] -[
Meta-learner. As shown by Figure 1, the meta-learner's role is aggregate the models produced by the base-learners using weighting scheme. At each iteration I, the meta-learner will maintain a weight pr, for each "active" base-learner &,, defined as the one whose associated interval contains t. We update the weights for active base-learners based on the Adapt-ML-Prod method [43]. Specifically, for every active base-learner ε,, our algorithm maintains "potential" Vt,4 E R4 iteration which reflects the historical performance of the base-leaner until time t. Then, denoting by A, the index set of the active base-learners at time their weights and the output model are obtained by
Pt, X Et- Et-1, for all i A, and 0 EEEAA,, P0+1,00+111.
(9)
In the above ε > is a step size that can be automatically tuned along the learning process. A noteworthy ingredient of our algorithm is the construction of the potential Ut using the linearlized loss (V.,( 0g - 0r, / (SR). Then, the generalization gap between T., and T. can be controlled with the negative term introduced by the exp-concave loss function. As result, high probability bound to ensure that 6, is competitive with any bese-learner's model 0r,, on the corresponding interval 7, The detailed configurations of Ut,; and ε,,; are deferred to Appendix D.I.
establish
Schedule of Intervals. As shown in Figure 1, we specify the intervals with the geomer- ric covering scheme [41], where the interval set is defined as C = UKENU(O) Cs with Cs = {li 2 1)- 2 1] N and i- 2* T). One can check that |C] at most and the number of active base-learner is bounded [Ail S t). Thus, only need to maintain at most Ollog t) base-learners at time f. The intervals specified by the geometric covering are informative to capture the non-stationarity of the environments, leading the following dynamic regret guarantees.
4.2 Theoretical Guarantees
This part presents the theoretical guarantees of our method. The estimator fr(x) exp(-6(x TO.) established on 6g returned by the online ensemble method (9) achieves the dynamic regret guarantee. Theorem 2. Assume the true density ratio rī (x) = D,(x)/ Dx(x) is contained in the hypothesis space as rf E HD & {x exp(-Φ(x) T 0) A E θ) for any E [T]. Then, with probability at least 1 8, the dynamic regret of the density ratio estimator Fr (x) exp(-o(x) 0.) is bounded by
Reg (LL, r: S ō (max(( (1+1)+777 T/No).
when the parameters are set as 7 3(1 + 3) and X 1. the above, VT = 1
D,-1 (x)(())]1 measures the variation of input densities.
7

---

Theorem 2 imposes a realizable assumption for the true density ratio function such that r E Hgg Such an assumption required since we train the density ratio estimator on a given hypothesis space while the true density ratio function could be arbitrary. We note that the realizability assumption is frequently used in the analysis for the density ratio estimation problem [29, 45] and other related topics, including active learning [46] and contextual bandit [47], where the density ratio (or density) estimation is required. A possible direction to relax the assumption is to consider a richer function class, e.g., neural network or non-parametric model. We leave this as a future work.
The Ö( V+² rate in our bound exhibits the same rate as the minimax optimal dynamic regret bound for the squared loss function with the noisy feedback [48]. Since the squared loss function enjoys even stronger curvature than the logistic loss, our result is hard to be improved. To achieve this fast-rate result, the key was to show "squared" formulation O max { 1, ( of the dynamic regret for the base-leaner on each interval / (Lemma 3 in Appendix D.2). [19] achieved this by a complicated analysis with the KKT condition capture the structure of the comparators, while greatly simplified the analysis by exploiting the structure that the comparator 0, is essentially the minimizers of expected functions T, (hence avoiding analyzing the KKT condition). Our analysis is applicable to the case where the minimiers lie in the interior of the decision set and only requires the smoothness of the loss function, which can be of independent interest in online convex optimization.
Averaged Excess Risk Bound for Continuous Covariate Shift. After obtaining the density ratio estimator, we can train the predictive model by IWERM (2), leading to the following guarantee.
Theorem 3. Under the same condition as Theorem 2 and letting Vr = Σ'= [D) - Dx-1(x)ll1. running IWERM (2) with the estimated density ratio function fx(x) = exp(-<(x) 0.) yields
Rt ( (o)) S ONo= max A T))
Theorem shows that our learned predictor w. adapts to the environment with a converged average excess risk when compared with the per-round best predictor wi. By the discussion below Proposi- tion 1, the O(N,1/2) generalization error over the offline data So is hard to improve. We focus on the error in the online learning part. When the environment is wearly-stationary, i.e., Vr S O(T
our bound implies an Ö(N, 1LNN-1/2+7-1/// average excess risk, matching the same rate for the one-step adaptation [49], even if the unlabeled data appear sequentially and the comparator wž could change over time. When the environments shift quickly, the 1// rate still exhibits diminishing error for covariate shift adaptation once Vi- = o(T). Indeed, our result has the same rate as that for continuous label shift [18] (with a slightly different definition of Vr though). Appendix D.6, we further provide evidence to show that the (max(2-113v//)) 1T21 rate can hardly be improved, even if one can receive labels of the testing stream after prediction.
Discussion on Assumptions. We end this section by a discussion on possible future directions to relax the linear model assumption for DRE and covariate shift assumption. Since our analysis is based on the online convex optimization framework, we employed the (generalized) linear model for DRE to ensure the convexity. To go beyond the linear model while still having theoretical guarantees, one might extend the online ensemble framework to learn within the Reproducing Kernel Hilbert Space, leveraging advances in online kernel learning [50]. As for the step towards handling the general distribution shift, it is possible to consider the sparse joint shift model [51] where both covariate and label distribution could shift. Besides, studying how to handle the joint distribution shift with few online labeled data also presents an interesting future direction. Our research on the covariate shift might serve basic step towards addressing more complex real-world distribution shifts.
5 Experiments
Setups. We generate continuous covariate shift by combining two fixed distributions with time- varying mixture proportion a, E [0, 1). Specifically, given two fixed distributions D' (x(x) and (x).. we generate samples from D, = (1 a D'(xx ax;) D" ) at each round. The mixture proportion or shifts in four patterns: Sin nin Shift and Squ Shift, a changes periodically, following sine and square waves; in Lin Shift, the environment changes slowly from o1 = to oT 0 linearly over T rounds, while in Ber Shift, the proportion o, flips quickly between 0 and 1 with a certain probability. For parameterization in the Accous implementation, set R by directly calculating the data norm
8

---

220
OLEEE
Average Error (%)
135
Tatiratte Time
Accora
Estiattor Error
35
150
Average Error
Staf Tedictto
125
120
30
75
25
13 12
300
200
300
403 500
500
700
003
500
Lin
Squ
Sin
Ber
Interval length (M =2)
Time
Figure 2: Performance compari-
Figure 3: Weight(S) (6) heatmap of
Figure 4: Average error and esti- mator loss in squared shift.
son on the four kinds of shifts.
base-learners in squared shift.
and set S d/2 for all experiments. We repeat all experiments five times and evaluate the algorithms by the average classification enror over the unlabeled test stream for 10,000 rounds.
Contenders. We compare our method with six algorithms, which can be divided into three groups. The first is a baseline approach that predicts directly using the model trained on initial offline data (FIX). The second group consists of the one-step covariate shift adaptation methods that do not reuse historical information: DANN [52] handles the shifts by learning an invariant feature space, /W- KMM [26]. /W-KEIEP [25]
and /W-uLSIF [28] equip the one-step IWERM method (2) with different density ratio estimators. The third is OLRE, which serves as an ablation study for our Accous algorithm. The OLRE algorithm estimates the density ratio by running an ONS (8) with all historical data and then performs the IWERM at each round. All algorithm parameters are set by their default.
In the following, we focus on the results of empirical studies. Detailed configurations for the datasets, simulated shifts, and setups for the Accous algorithm and contenders can be found in Appendix A.
5.1 Illustrations on Synthetic Data
Average Classification Error Comparison. We summarize the comparison results on synthetic data with different types of covariate shifts with all contenders in Figure 2. The Accous algorithm outperforms almost all other methods in the four shift patterns. We observe that the offline model FIX performs poorly compared to the online methods. The best result of DANN, IW-KMM, IW-KLIED and IW-uLSIF is called One-Step for comparison. By reusing historical data, the Accous algorithm achieves a lower average classification error compared to these One-Step competitors that use only one round of online data. The Accous also outperforms OLRE, especially when the environments change relatively quickly (Squ, ni and Ber). These results justify that performing density ratio estimation with either one round of online data or all historical data inappropriate for non-stationary environments. Moreover, when the number of unlabeled data per round changes from N₁ = 5 to N₂ = the one-step methods suffer severe performance degradation. In contrast, our Accous algorithm still performs relatively well, highlighting the need for selective reuse of historical data.
Effectiveness of Online Density Ratio Estimation. We then take closer look at the core component of our algorithm, the online density ratio estimator, in the Squ shift where the distribution of the online data shifts every M rounds. Figure 3 shows the weight assignment for base-learners with different interval lengths, averaged over their active period. The result shows that our meta-learner successfully assigns the largest weight the base-learner whose interval length matches the switching period M, which ensures that the right amount of historical data is reused. Figure 4 also shows the average error of Accous and OLRE over 1, 000 iterations. The results show that Accous (red line) can quickly adapt to new distributions after the covariate shift occurs. In contrast, OLRE (blue line) struggles because it uses all the historical data generated from different distributions. Furthermore, we denote the loss of the density ratio estimator (0.) by the green line, which is quickly minimized after the covariate shift occurs. The similar tendency between the average error (red line) and the loss of the estimator (green line) confirms our thcoretical finding in Theorem I: we can minimize the excess risk of the predictor by minimizing the dynamic regret of the density ratio estimator.
5.2 Comparison on Real-world Data
Performance Comparison on Benchmarks. In Table and Table 2, we present the results of the average classification error comparison with the contenders four benchmark datasets. Our

---

Table 1: Average classification enror (%) of different algorithms on various real-world datasets with L, n and Ber shifts. We report the accuracy and standard deviation five The best algorithms emphasized in bold. The number data in each round set as N₂
Lin
Boz
FIX
DANN
B.M
KLIKP
u1.S1
1.
OLRE
Accous
FIX
DANN
KMM
K.H.IP
U1.SIV
(I.R)
Accoms
39.14
27.10
16.54
16.25
Breast
3.3000
2:4.7
1: 1:0.31
8.26
8.777
6,50
42:34
2: 11599
7:33
2: 6.25
-0.16
4:00
2:4.66
11.08
15:34
5.5.3
=0060
10.12
1: 11130
+:191
9101
2.2.22
9.34
2.0.4
5.27
4: 10.37
3,89
MNISTSVVNN
21.30
8.19
-0:97
13:91
41.52
6.24
40.53
7.50
29.75
6.38
20.84
6.81
40.38
6.58
1::72
5.91
=0.33
11:33
21.00
16.58
20.53
10.1
20.97
11.50
41.20
12.19
20.50
11.38
=0
13.47
20.51
11L.1
CIPARIS-CINCCO
20.31
79.18
30.45
79.75
$3.34
27.17
28.3
-0.94
$1.29
20.3
+1.57
$1.26
33.09
30.99
Table Average classification emor (%) of different algorithms various real-world datasets with Squ. and Sin shifts. We report the mean accuracy and standard deviation over five runs. The best algorithms emphasized in bold. The number data in each round set as N₂ = 5.
FIX
DANN
KMM
KLIEP
a1.SEF
1.R
OLRE
FIX
DANN
KMM
KIJEP
a1.SIF
LR
OLRR
Accus
Diabries
37.85
45.09
43.57
37.00
35.05
37.83
39:17
36.45
31.30
-6.70
41.95
41.33
15.93
35.40
57.25
36.59
38.5%
35.17
0.52
7.9
7:15
MINSESSVIIN
-1.2
-0.7
-0.51
+1.43
+0.67
11.72
+0.59
13.58
11.00
+1.25
16.73
-1.03
5.91
+1.00
+0.55
+1.37
9.00
+0.55
-6.74
7.74
CIFARIO-CNNCIO
-0.29
34.25
=1.58
16.13
=083
94.08
14.24
34.27
33.73
33.50
31.59
83
39.09
$3.61
=0,60
31,08
2:047
36.
1:109
42.53
20.07
37.00
1:152
36.58
31.02
56.53
2131
96.31
21.86
58.34
21.23
35.42
algorithm Accous outperforms other contenders in the four types of shifts, whether in a slowly evolving enviromment (Lin) or in relatively non-stationn non-stationary environments (Squ,Sin,Ber), The OLRE algorithm uses all historical data, but does not necessarily outperform contenders that use only current data, suggesting that we should selectively reuse the historical data.
Case Study on Real-life Application. We conducted empirical studies on a real-world application using the yearbook dataset [53],
0.35
FIXED
which contains high school front- factnf yearbook photos from 1930
Average Error (%)
044
TW KLIE
EW KDDI
OLRE
Azorue
2013. The photo distributions shift along years due to the changing social norms, fashion styles, and population demographics. Conse- quently, it is essential to adapt to these changes. We used photos before 1945 the offline labeled dataset and generated the online unlabeled data stream using photos after 1945, arranged chrono- logically with 10 photos per round. Figure 5 shows the average error curves. The OLER algorithm performs well when the distri- butions do not change too much, but the method starts to suffer from large prediction errors after 400 iterations. In contrast, our method outperforms all competitors by selectively reusing historical data.
0.3
100
200
300
430
500
60C
700
500
900
T
Figure S: Average error on Year- book dataset with real-life covari- shift.
6 Conclusion
This paper initiated the study of the continuous covariate shift with the goal of minimizing the cumulative excess risk of the predictors. We showed that the aepootaacce-eiihtee. ERM method works effectively given high-quality density ratio estimators (Proposition 1). whose estimation can be cast as dynamic regret minimization problem (Theorem 1). Instantiating with the logistic regression density ratio estimation model, we proposed a novel online that can adaptively reuse the historical data and enjoy tight dynamic regret bound (Theorem 2). The regret bound finally implies an (T- 1/3////3) averaged excess risk guarantee for the predictor. Experiments validate the effectiveness of the proposed method and demonstrate the need for selective reuse of historical data.
Acknowledgments
YJZ and MS were supported by the Institute for Al and Beyond, UTokyo. YJZ was also supported by Todai Fellowship. Peng Zhao was supported by NSFC (62206125) and JiangsuSF (BK20220776). The authors thank Yong Bai and Yu-Yang Qian for their assistance in the experiments.
10

---

References
[1] Joaquin Quinonero-Candela. Masashi Sugiyama. Anton Schwaighofer, and Neil D Lawrence. Dataset Shift in Machine Learning. MIT Press, 2008.
[2] Yoshua Bengio, Yann Lecun, and Geoffrey Hinton. Deep learning for AL. Communications of the ACM, 64(7):58 65, 2021.
[3] Thomas G. Dietterich. Steps toward robust artificial intelligence. Al Magazine, 38(3):3-24, 2017.
[4] Zhi-Hua Zhou. Open-environment machine learning. National Science Review, 9(8), 07 2022.
nwac 123.
[5] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of Statistical Planning and Inference, 90(2):227-244, 2000.
[6] Masashi Sugiyama and Motoaki Kawanabe. Machine Learning in Non-Stationary Environments Introduction to Covariate Shift Adaptation. MIT Press, 2012.
[7] Samory Kpotufe and Guillaume Martinet. Marginal singularity and the benefits of labels in covariate-shift. The Annals of Statistics, 49(6):3299-33 3323, 2021.
[8] Yan Li, Hiroyuki Kambara, Yasuharu Koike, and Masashi Sugiyama. Application of covariate shift adaptation techniques in brain-computer interfaces. IEEE Transactions on Biomedical Engineering, (7(6))1318-133 2010.
[9] Makoto Yamada, Masashi Sugiyama, and Tomoko Matsui. Semi-supervised speaker identifica- tion under covariate shift. Signal Processing, 90(8):2353-233 2361, 2010.
[10] Ali Hassan, Robert Damper, and Mahesan Niranjan. On acoustic emotion recognition: Com- pensating for covariate shift. IEEE Transactions Audio, Speech and Language Processing, 21(7):1458-1468 2013.
[11] Jiayuan Huang. Alexander J. Smola, Arthur Gretton, Karsten M. Borgwardt, and Bernhard Schölkopf. Correcting sample selection bias by unlabeled data. In Advances in Neural Informa- fion Processing Systems 19 (NIPS), pages 601-608, 2006.
[12] Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density Ratio Estimation in Machine Learning. Cambridge University Press, 2012.
[13] Elad Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimiza- tion, 2(3-4):157- -25, 2016.
[14] Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density-ratio matching under the Bregman divergence: a unified framework of density- -ratio estimation. Annals of the Institute of Statistical Mathematics, 64(5):1009-1044 2012.
[15] Lijun Zhang, Shiyin Lu, and Zui-Hua Zhou, Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 1330-1340, 2018.
[16] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages
12510-12520, 2020.
[17] Steffen Bickel, Michael Brückner, and Tobias Scheffer. Discriminative learning under covariate shift. Journal of Machine Learning Research, 10:2137-2155, 2009.
[18] Yong Bai, Yu-Jie Zhang, Peng Zhao, Masashi Sugiyama, and Zhi-Hua Zhou. Adapting to online label shift with provable guarantees. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 39960-29977 2022.
[19] Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning, In Proceedings of the 34th Conference on Learning Theory (COLT), pages 359-409, 2021.
[20] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex Optimization. Cambridge University Press. 2004.
[21] Makoto Yamada, Taiji Suzuki, Takafumi Kanamori, Hirotaka Hachiya, and Masashi Sugiyama. Relative density-ratio estimation for robust distribution comparison. Neural Computation, 132))-1124-370, 2013.

---

[22] Masashi Sugiyama, Matthias Krauledat, and Cobur-Robert Müller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8:985-1005, 2007.
[23] Junfeng Wen, Chun-Nam Yu, and Russell Greiner. Robust learning under uncertain test distributions: Relating covariate shift to model misspecification. In Proceedings the the 31th International Conference on Machine Learning (ICML), pages 631-639, 2014.
[24] Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. Rethinking importance weighting for deep learning under distribution shift. In Advances in Neural Information Processing Systems 33 (NeurIPS), page 11996-12007, 2020.
[25] Masashi Sugiyama, Taiji Suzuki, Shinichi Nakajima, Hisashi Kashima, Paul von Bünau, and Motoaki Kawanabe. Direct importance estimation for covariate shift adaptation. Annals of the Institute of Statistical Mathematics, 60(4):699-746, 2008.
[26] Arthur Gretton, Alex Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Schölkopf. Covariate shift by kernel mean matching. Dataset Shift in Machine Learning, 3(4):5, 2009.
[27] Masashi Sugiyama. huperfast-trainabl multi-class probabilistic classifier by least-squares posterior fitting. IEICE Transactions on Information and Systems, 93-D(11):2690-22)) 2701, 2010.
[28] Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama. A least-qquares approach to direct importance estimation. Journal of Machine Learning Research, 10: (0.1331-1445, 2009.
[29] Masahiro Kato and Takeshi Teshima. Non-negative Bregman divergence minimization for deep direct density ratio estimation. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning (ICML), pages 5320-5333, 2021.
[30] M. C. du Plessis, H. Shiino, and M. Sugiyama. Online direct -ensity estimation applied to inlier-based outlier detection. Neural Computation, 27( 1899-199911119 2015.
[31] Yu Chen, Song Liu, Tom Diethe, and Peter A. Flach. Continual density ratio estimation in an online setting. ArXiv preprint, arXiv:2103.0522
2021.
[32] Rasool Fakoor, Jonas Mueller, Zachary C. Lipton, Pratik Chaudhari, and Alexander J. Smola. Tire-varying propensity score to bridge the gap between the past and present. ArXiv preprint, arXiv: 2210.01422, 2022.
[33] Ruihan Wu, Chuan Guo, Yi Su, and Kilian Q. Weinberger. Online adaptation to label distribution shift. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 1 11340-11355 1131,, 2021.
[34] Dheeraj Baby, Saurabh Garg, Tzu-Ching Yen, Sivaraman Balakrishnan, Zachary Chase Lipton, and Yu-Xiang Wang. Online label shift: Optimal dynamic regret meets practical algorithms. ArXiv preprint, arXiv:2103.05276, 2023.
[35] Sooyong Jang, Sangdon Park. Insup Lee, and Osbert Bastani. Sequential covariate shift detection using classifier two-sample tests. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 9845-9880, 2022.
[36] Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. In Advances in Neural Information Processing Systems 23 (NIPS), pages 442-450, 2010.
[37] XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan. Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization. In Advances in Neural Information Processing Systems 20 (NeurIPS), pages 1089-1096, 2007.
[38] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928-936 2003.
[39] Omar Besbes, Yonatan Gur, and Assaf J. Zeevi. Non-stationary stochastic optimization. Opera- lions Research, 63277:1227-1 2015.
[40] Zachary C. Lipton, Yu-Xiang Wang, and Alexander J. Smola. Detecting and correcting for label shift with black box predictors. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 3128-3138333 2018.
12

---

[41] Elad Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th International Conference on Machine L (ICML), pages 393-400, 2009.
[42] Yoav Freund and Robert E. Schapire. A decision- generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-139 1997.
[43] Pierre Gaillard, Gilles Stoltz, and Tim van Erven. A second-order bound with excess losses. In Proceedings of The 27th Conference on Learning Theory (COLT), pages 176-196, 2014.
[44] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(--3):169-19,, 2007.
[45] Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama. Statistical analysis of kernel-based least-squares density-ratio estimation. Machine Learning, 86(3):335-38) 367, 2012.
[46] Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. In Proceedings of the 34th International Conference Machine Learning (ICML), pages 1915-1924, 2017.
[47] Dylan J. Foster and Alexander Rakhlin. Beyond UCB: optimal and efficient contextual bandits with regression oracles. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 3199-3210, 2020.
[48] Dheeraj Baby and Yu-Xiang Wang. Online forecasting of total-variation-bounee boundee sequences. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 11071-11081, 2019.
[49] Yaoliang Yu and Csaba Szepesvári. Analysis of kernel mean matching under covariate shift. In Proceedings of the 29th International Conference on Machine Learning (ICML), pages
1 1147-1154, 2012.
[50] Daniele Calandriello, Alessandro Lazaric, and Michal Valko. Efficient second-order online kernel learning with adaptive embedding. In Advances Neural Information Processing Systems 30 (NeurIPS), pages 6140-6150, 2017.
[51] Lingjiao Chen, Matei Zaharia, and James Y. Zou. Estimating and explaining model performance when both covariates and labels shift. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 11467-11479, 2022.
[52] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor S. Lempitsky. Domain-adversariaa training of neural networks. Journal of Machine Learning Research, 17:59:1-59:35, 2016.
[53] Huaxiu Yao, Caroline Choi, Bochuan Cao, Yoonho Lee, Pang Wei Koh, and Chelsea Finn. Wild-time: A benchmark of in-the-wild distribution shift over time. In Advances in Neural Information Processing Systems 35 (NeurIPS) Datasets and Benchmarks Track, pages 10309- 10324. 2022.
[54] Shiry Ginosar, Kate Rakelly, Sarah M Sachs, Brian Yin, Crystal Lee, Philipp Krähenbühl, and Alexei A Efros. A century of portraits: visual historical record of american high school yearbooks. IEEE Transactions on Computational Imaging, 3(3):421-431, 2017.
[55] András György and Csaba Szepesvári. Shifting regret, mirror descent, and matrices. In Proceedings of the 33nd International Conference on Machine Learning (ICML), pages 2943- 2951, 2016.
[56] Eric C. Hall and Rebecca Willett. Dynamical models and tracking regret in online convex programming. In Proceedings of the 30th International Conference on Machine Learning (ICML), pages 579-587, 2013.
[57] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization Competing with dynamic comparators. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 398-406, 2015.
[58] Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online opti- mization in dynamic environments: Improved regret rates for strongly convex problems. In Proceedings of the 55th IEFE Conference on Decision and Control (CDC), pages 7195-7201, 2016.
13

---

[59] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 449-457, 2016.
[60] Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 5877-5886, 2018.
[61] Yu-Jie Zhang, Peng Zhao, and Zhi-Hur Zhou. A simple online algorithm for competing with dynamic comparators. In Proceedings of the 36th Conference Uncertainty in Artificial Intelligence (UAI), pages 390-399, 2020.
[62] Dheeraj Baby and Yu- Yu-Xiang Wang- Adaptive online estimation of piecewise polynomial trends. In Advances in Neural Information Processing Systems 33 (NeurlPS), pages 20462-20472,
2020.
[63] Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. In Proceedings of the 3rd Conference on Learning for Dynamics and Control (LADC), pages 48-59, 2021.
[64] Zhi-Hua Zhou. Ensemble Methods: Foundations and Algorithmss Chapman & Hall/CRC Press, 2012.
[65] Shai Shalev-Shwarte and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[66] Gilles Pisier. The Volume of Convex Bodies and Banach Space Geometry, volume 94, Cambridge University Press, 1999.
[67] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zui-Hua Zhou. Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. ArXiv preprint, arXiv: 2002.07729, 2021.
[68] Mehrdad Mahdavi, Lijun Zhang, and Rong Jin. Lower and upper bounds on the generalization of stochastic exponentially concave optimization. Proceedings of The 28th Conference on Learning Theory (COLT), pages 1305-1320, 2015.
[69] Joel A. Tropp An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1 1-00, 2015.
[70] Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 943-951, 2017.
[71] Yoav Freund, Robert E. Schapire, Yoram Singer, and Manfred K. Warmuth. Using and com- bining predictors that specialize. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC), pages $34-343, 1997.
[72] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. University Press, 2006.
Cambridge
[73] Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: AdaNormalHedge. In Proceedings of the 28th Anmual Conference Computational Learning Theory (COLT), pages 1286-1304, 2015.
[74] Dmitry Adamskiy, Wouter M. Koolen, Alexey V. Chernov, and Vladimir Vovk. A closer look at adaptive regret. Journal of Machine Learning Research, 17:23:1-23:21, 2016.
[75] Lijun Zhang, Shiyin Lu, and Tianbao Yang. Minimizing dynamic regret and adaptive regret simultaneously. In Proceedings of the 23rd Internutional Conference Artificial Intelligence and Statistics (AISTATS), pages 1099319,000 2020.
14

---

A Omitted Details for Experiments
In this section, we first provide additional details that were omitted in section 5. We then provide the descriptions of our experimental setups, which include details of the datasets used, simulations of continuous covariate shifts, descriptions of the competing algorithms, and the parameter configuration of our proposed Accous algorithm. After that, supplement the detailed numerical results obtained from the synthetic experiments.
A.1 Experiment Setup
Continuous Covariate Shift Simulation. To simulate the continuous covariate shift, generate offline and online samples from different marginal distributions and annotate them with the same labeling function. Given two different marginal distributions D' (x) and D (x), the offline dataset So is sampled from the distribution Dx = (1 on) ('())) + org (x)), where ag E [0. 1] is a mixture proportion coefficient. The online dataset S, received at each iteration t is sampled from the distribution Dx(x)= = (1 (z)) + azD" (x), where a2 E [0, 1] is the time aneevaryyigg coefficient. simulate different types of continuous covariate
By changing the coefficient a, for t 2 shifts with different shift patterns.
Linear Shift (Lin): We set a; = t/T to simulate a gradually changing environment.
Square Shift (Squ): In this case, the parameter o₃ switches between 1 and 0 every M rounds, where 2M is the periodic length. We set M = ((VT) to simulate fast- changing environment with periodic patterns.
Sine Shift (Sin): : We set a₂ = sin i7. where = t mod M and M is the periodic length. We set M @(vT) simulate fast-changing environment with periodic patterns.
Bernoulli Shift (Ber): In this case, we keep the a = Q4-1 with probability p E [0, and otherwise set a = 1 at-1- We set = @(I/vT) to simulate a fast- changing environment but without periodic patterns.
Datasets. For the synthetic dataset, we generate ('(x) and (*)x) using the multinomial Gaussian distribution, wherein each class is generated from a Gaussian distribution. For D')x), the positive class data is generated from (xx; uf; E), and the negative class data is generated from N(x; 4 E). Here, μu is set to -0--111 1.2 in R and μr is set to -0.8 in R As for D"(x), its positive class data is generated from N(x: u.a E). and the negative class data is generated from ((x; μ Σ). Here, μ is specified as 1.2 in IR 12_ and μz as 0.8 in 122 The covariance matrix is set as = Ia in 12x12 and the prior probability for the positive class data is fixed at 0.5. Besides, we generated offline data with ap- = 0.9 and introduced a time-varying coefficient, (r,, to simulate continuous covariate shifts.
The benchmark datasets are generated from real-world datasets.
Diabetes (Dia) is tabular UCI dataset. Each sample is an 8-dimensional vector with a binary label. We split the dataset into two subsets and choose the split such that the classifier trained on one dataset generalizes poorly to the other. We choose one of them as the offline dataset and combine them with varying coefficient to generate the online data.
Breast (Bre) is a tabular UCI dataset. Each sample is a 9-dimensional vector with a binary label. This dataset generated similarly to the Diabetes dataset.
MNIST-SVHN (M-S) contains the digital images collected from handwriting or natural scene images. A feature extractor pre-trained on this dataset produces 51 312-dimensi vector with a 10-class label for each sample. We choose 10% MNIST data and 90% SVHN data as the offline dataset and generate the online data by mixing the MNIST and SVHN datasets with a time-varying proportion coefficient at,-
CEFARIO-CINICL (C-C) contains real-life subjective images collected from different sources. This dataset is generated similarly to the MNIST-SVHN dataset.
We also conduct experiments on a real-world dataset where the underlying data distributions exhibit continuous shift.
15

---

Yearbook [53]: This dataset contains the 37,921 Poonal-facing American high school yearbook photos from 1930 to 2013 [54]. Each photo is a x 32 grayscale image associated with binary label representing the student's gender. This dataset captures the real-life changing of social norms, fashion styles, and population demographies. The offline data is generated with photos before 1945, the online data is generated from 1946, and the data size is 10 per round.
Contenders. We compare our proposed approach with six contenders, including:
FIX is the baseline method that predicts with the classifier that are pre-trained on offline data without any updates in the online adaptation stage.
is general domain adaptation algorithm that mitigates the discrepancy between the training and test distributions by learning an invariant feature representation. We adapt this method to the online setting by running DANN at each round t E [T') based on the offline data So and the online data S, available that round.
IW-KMM is an importance weighting learning method that first estimates the density ratios by the Kernel Mean Matching (KMM) method [26] and then performs the IWERM train the model. At each iteration & E [T]. the density ratios are estimated with the offline dataset So and the online dataset S₁ by the KMM. Then the model is trained by running the IWERM method on the offline data Sg-
/W-KLIEP is also an importance weighting learning method, where the density ratios are estimated by the KLIEP method [25]. At each iteration E [T], after the density ratios have been estimated by KLIEP, the learner performs the IWERM over the offline data So-
/W-ul.SIF is importance weighting learning method where the density ratio estimated by the uIFIF method is used [28]. At each iteration & E [7]. the learner first estimates the density ratios by the uI.IIF and then performs the IWERM the offline data So-
LR serves as an ablation study for the proposed Accous algorithm. each iteration E [T]. the learner first estimates the density ratios by an ONS with logistic regression model and then performs the IWERM on the offline data So.
OLRE also serves as an ablation study for the proposed Accous algorithm. It estimates the density ratios in an on-line manner by running ONS with a logistic regression model with all the historical data and then performing the IWERM each round.
Accous Setup. We implement the Accous algorithm using a logistic regression model. Before rumning the Accous algorithm, two parameters must be defined. They are the maximum norm of the feature R and the maximum norm of the density functions S. We set R by directly calculating the data norm. The covariate shift level determines the parameter S, which is difficult to predict in advance. We found that setting S = d/2 is a good choice in the experiments. For stable performance, set threshold of 100 and truncate the large weights after the density ratio estimation in each round. We also ignore the base models with interval lengths 1, 2 in the density ratio estimation.
For the synthetic, diabetes, and breast tabular datasets, the linear model is used. For the MNIST- SVHN, CIFAR 10-NNIO-,, and Yearbook datasets, the deep model used for density ratio estima- tion and predictive model training. The deep models consist of a backbone and a linear layer. In all experiments, only the linear layer of the neural network is updated, while the backbone parameters trained with offline data remain fixed. Backbone settings for different datasets are presented below.
MNIST-SVHN and IPARRIOCCNICIA The backbone is a pre-trained ResNet34 backbone from torchvision with its weights initialized by training on ImageNet. Both the weight estimator and the classifier share the same backbone and its corresponding parameters.
Yearbook: Our network adopts a similar structure and updating process as in the MNIST: SVHN and CIFARIO-CINICIO experiments, following the configuration described in [53]. The backbone of network consists of a CNN model with the default settings.
Computational Resources. We run experiments with two Xeon Gold 6248R processors (24 cores, 3.0GHz base, 4.0GHz boost), eight Tesla V100S GPUs (32GB video memory each), 768GB RAM, all managed by the Ubuntu 20.04 operating system.
16

---

Table 3: Average enorr (%) over the entire time horizons for different algorithms under various simulated shifts. The best algorithms are emphasized in bold.
Ar 5
FIX
DANN
KMM
KLJEP
uLSNF
L.
OLRE
Accous
FIX
DANN
KMM
KL.EP
nESSFF
1.R
OLRE
Accous
Lin
10.43
32.85
-2.40
46.93
10.36
31.97
10.82
36.26
10.40
16.34
11.12
36.51
10.14
27.13
10044
27.68
1.0.53
32.59
12.99
40.33
-0.86
32.68
10.30
24,13
10.46
31.70
1.0.72
32.21
10.81
27:34
10.69
27.11
33.19
40.59
35.50
35.13
36,44
36.21
34,82
29.30
33.37
41.24
31.52
30.94
32.07
31,63
34.46
28.46
+0.56
-1.28
+-0.3
+061
+0.70
-0.46
+0.30
-8.82
+-0.57
+4.01
-0.46
+0.55
+0.36
+1.08
+0.56
+0.54
sin
32.80
42.65
36.25
+0165
35.83
37.01
35.42
33.15
31.08
32,66
39,94
34,15
34.47
33.93
34.62
31.85
30.57
34.11
20:45
10.42
19.67
10.36
20.85
20.36
10.78
10.72
A.2
Supplementary Numerical Results for Section 5.1
In Section 5.1 we summarize the results of the synthetic experiments, and here in Table 3, we supplement their detailed numerical results. Overall, Accous outperforms almost all other methods in the four shift patterns. Compared to the competitors that use only one round of online data, our proposed method achieves a lower average error. The general domain adaptation method DANN is also inferior in the online setting due to the limited amount of data per round, which makes it difficult learn good representation. The proposed Accous algorithm also outperforms the OLRE algorithm, which reuses all historical data. The above evidence demonstrates the need for selective reuse of historical data and validates the effectiveness of our algorithm.
B More Related Work
B.1 Related Work on Non-stationary Online Learning
Online convex optimization (OCO) [13] is a powerful paradigm to handle sequential prediction problems. To adapt the continuously shifting environments, exploit the online ensemble technique [15, 16] developed in non-stationary online learning literature to hedge the uncertainty. In this part, will introduce the related works and discuss the difference between our algorithm and the previous work.
Specifically, OCO paradigm considers 7-round game between learner and the environment. At every round the learner makes prediction 0, E O, and, the same time, the environments reveal the convex loss function L, ④ R. Then, the learner suffers from the loss L,(0,) and observes certain information about Le to update the model for the next iteration. classical performance measure for OCO framework in non-stationary environments is the dynamic regret,
Reg ((. Σ (..).)
Σ L.()))
(10)
which compares the learner's prediction with the function minimizer 02 at every iteration. Over the decades, a variety of online learning algorithms have been proposed to optimize this dynamic regret measure [38, 39, 55, 56, 57, 58, 59, 60, 61, 62, 63] in the online convex optimization problem.
Worst-case Dynamic Regret. Many works focus on the full information setting [57, 58, 59, 60, 63). where the learner can observe the loss functions entirely. We call the dynamic regret in such as "worse-case" dynamic regret in the sense that the comparator 6 is exactly the minimizer of the observed function L, According different complexity measures for quantifying the environmental non-stationarity, there are two lines of results. The first is the path length of comparators V Σi=110; 0,-11/2 measuring the variation of the function minimizers; and the second one is the variation of the function values V = DT max (0) L, ( For the full information setting, the prior art [63] showed that simple greedy strategy can already be already well-behaved and achieves an Ommin( V dynamic regret bound that minimizes the two kinds -on-stationarity measure simultaneously.
Universal Dynamic Regret. Competing to the sequences of observed functions' minimizers can be sometimes too pessimistic for the online optimizing, which may lead to severe overfitting. A more appropriate performance measure the universal dynamic regret [38], which has drawn more and more attention in recent years. Universal dynamic regret compares the learner's 's prediction with an
17

---

arbitrary comparator sequence {uilT=>>
T
Reg/ (fL,, vt L.)) Σ (())).
(11)
Let Vi = - 42-1l2 1l2 be the path length of the comparator sequence (v=)==1-
[38]
showed that the online gradient descent algorithm achieves an ((1 + VT) universal dynamic
regret bound for convex function, whereas there is still gap to the 92( ((VT(11 VP) lower bound
established by [15], who further proposed an algorithm attaining (VT((1 + VF)) dynamic regret bound and thus closed the gap. Their key algorithmic ingredient is the online ensemble structure [64], which hedges the non-stationarity of the environments by employing a meta-learner to ensemble the predictions from a group of base-learners. When, the loss function is convex and smooth, the O ((VT(1+ + VT)) can be improved to O( min PT, GT) + VFX(1 + VF)) [16], where Fr Ex. (1(rr) and GT = Lt= maxage ( 1 are two problem-dependent quantities capturing different kinds of easiness of the environments. For the exp-concave and smooth functions, [19] showed an O ((T)/((V)) (VF))/3 universal dynamic regret by an improper algorithm (i.e., the output decisions can be slightly out of the feasible domain, while comparators have to locate in the domain), which is proven to be minimax optimal for exp-concave functions. Note that the worst-case dynamic regret (10) is clearly special case of the universal dynamic regret defined in (11), universal dynamic regret upper bound directly implies an upper bound for the worst-case dynamic regret, by substituting comparators {ur)?= as functions' minimizer {0:] J1=1. This method yields a path-length type bound. Furthermore, we mention that it is also possible to obtain a function-variattn type worst-case dynamic regret bound from the universal dynamic regret guarantee, which is revealed in [61, Appendix A.2].
An Intermediate Dynamic Regret. There is also an intermediate case between the worst-case and universal dynamic regret. We refer to it the "intermediate" dynamic regret in this paper. In this intermediate case, the online learner still aims optimize the worst-case dynamic regret of the loss function (,),), but she can only observe a noisy feedback (0) at each iteration. Since the comparator 87 = arg mingee (0) is not the minimizer of the observed loss L, (0). such a kind of problem is more challenging than the worst-case dynamic regret minimization problem given the uncertainty of the comparator sequence. [39] showed a restarted online gradient descent algorithm can
achieve an ( dynamic regret bound for convex function and an O( (TV+) bound for strongly convex function under the noisy feedback. However, their algorithm requires the knowledge of the non-stationarity measure Vi2 EiT maxage (0) - (0)] defined over Lt, which generally unknown. [48] showed that an ((T2/3(1 bound is achievable with the noisy feedback when T,, is one-dimensional squared loss. The proposed method is based on the de-noising technique and are free from the knowledge of Vg. Evidently, this intermediate dynamic regret is still feasible realization of the universal dynamic regret, regret bound by the universal dynamic regret. However, this reduction will only provide an expected guarantee. More detailed discussions are provided below.
can achieve the intermediate dynamic
Comparison of Our Results and Earlier Works. Our ((T, (;)))) S (1
high-probability dynamic regret bound for logistic regression (Theorem 2) falls into the intermediate case, where we aim to minimize the worst-case dynamic regret bound in terms of L, with noisy feedback. The closest related work is by [19], who also exploited an online ensemble structure and achieved a universal dynamic regret in the form of Reg/ ((T,, " ) S O(TI/3 (V/)2/3) universal dynamic regret by taking Le as the input. Further choosing 14 = 0r and taking the expectation over S, for each round, their result implies expectation bound E[Regi di < (TT1/3 2/3). ) One main advantage of our result is that the bound holds with high probability. To achieve the high-probabilityy bound, twist the meta-learner from Hedge [42] to Adapt-MI--Prod [43] which helps control the generalization error between L, and L, with the negative term introduced by the exp-concavity of the loss function. Besides, similar to [19], our analysis crucially relies on providing squared formulation of the dynamic regret O (max (1, (VV)))) on each interval I. However, to obtain such a result, [19] crucially rely on a complicated analysis on the KKT condition to depict the structure of comparators. We greatly simplify the analysis by exploiting the fact that our case the comparator 0r is actually the minimizer of expected functions L,, hence avoiding analyzing KKT condition. Our
18

---

analysis is applicable to the case when the minimizers lie in the interior of the feasible domain and require the smoothness of the online functions only (which does not rely on the particular properties of logistic loss). This result might he of independent interest in other online learning studies.
C Omitted Details for Section 3
This section provides the proofs for Section 3 in the main paper.
C.1 Proof of Proposition
Proof of Proposition 1. We first provide an excess risk bound for the model w. at each time t and then combine them for T rounds. For each time E [T], let R, (w) (x. (x)(((( x, v) be the risk built upon the true density ratio function rī and (w)) = -( [x))((W x, v) be that built upon the empirical density ratio function Ft. We decompose the excess risk of the trained model W, as
R,(w,) R,(w;) = R2 W.
Rs W.
R (w,)
RR (w)) R. (ww))
(a)
(b)
(c)
For term (a), by a standard generalization error analysis as shown in Lemma 2, with probability at least 1 - 6/T"),, the gap between R,, and Re(we) is bounded by
2BGDR VNo +4BL,
2In((8T)/O)
term (a) Rs
Re (w)) E
No
Then, we proceed to bound term (b).
term (b) Rs (w.) R:(wi)
(w:) R.(W.) + Re(Wi) (w:) R((w;) + Re(w)) Rc())
< (w. R.(W.) + Rw(w;) - RR(
(x [x7(() - (x()))((W. x. y)] (xx))~ [(f((x) r (xx)))(((;;)T
Xx, v)]
< 2LEx-ss [x) - -x)())].
where the first incquality is due to the optimality of w, and the second inequality is by the condition maxxeW.9E\.wen) [((w v) L.
Finally, as for term (c), since wł is independent of Su, a direct application of the Hoeffding's inequality [65, Lemma B.6] implies,
2In((87)/5)
term (c) = Ro(w)) Re(w?) & BLY
No
with probability least 1 5/(2)). Combining the upper bounds for term (a), term (b) and term (c) and taking the summation over T rounds, we get
My ((w)( 2BGDRT
(8T((8))/8)
+ 5BLT
+ 2L
>
Ex so (x) (x (x))
NNo
No
1=1
with probability at least - 8, which completes the proof.
C.2 Proof of Proposition 2
Proof of Proposition 2. We begin with converting the estimation error the squared formulation,
T
(x- (x))
19

---

T Σ
T
(x)
fx(x) [11
(12)
where the first inequality is by Jensen's 's inequality and the last inequality is due to the Cauchy-Schwarz inequality. Then, we can bound the squared density ratio estimation error as
M
Do(x) [1T(()) ri (x) v EE (o(x) ( (r2 (x)) + (fx(x)) au (F(()) - 2
=B (b) L, (ft) (r7),
(13)
where the first incquality is due to the strong convexity of the function v. The last equality by the definition of the loss function L," Combining (12) and (13), we have
T
Σ
Ex (xx 1=1
- ((xx))
2T
Σ 1=1
L
(Tt)
Σ
/
C,3 Proof of Theorem
Proof of Theorem I. Following the same arguments in obtaining (12), the empirical cumulative estimation error of the density ratio estimators can be bounded as
Σ [xx (x)1l s T
E Sox) [1((())){(((]]]]]]
(14)
Then, we proceed to bound the squared cumulative estimation error by the regret of the loss function L (r) defined in (5), For notation simplicity, we define
fi(2) 0xb())z (=) and fe(2) = 0xb(2).
In such a case, the loss function Σ (r) = Ex So [f((r(x)) - Ex-D [f2(r(x))] and the regret over T.Y" can be written
(..) - (x7) = Ex (f)(() - fa(ri - Bx-.D, - (x(r) (15)
For the first term of R.H.S. of (15), by the Taylor's Theorem, for each x E X, we have
Ex
(x(( - (x)(()))
8 f2(E()
= Ex
0f(()(()))(()))-)))))))))))))))) - (x)) +
(Fr(x) r;)))
2
- rx))] + 1 Exwss [(F(()) - r (x))))-
2 Ex
(16)
2
In above Ex E dom vi is certain point on the line collecting fx( and (x). The second inequality due to the definition of fi such that,
S(x) = (bx - 0' 14,
where the inequality holds due to the μ-strong convexity of (2)2 and the condition (x.))(Ex)) S for all & E domeb.
Then, we proceed to bound the second term of R.H.S. of (15),
Ex-D, (f2(F((x)) - fe(r]
2 f2(x))
= Ex (ri (fx(x) - (x))] + ExnD,
(fr(x) -1(x))
2
< ExnD, (x)x(r;(())) (Fr(x) - (x))) = Ex
(17)
20

---

In above &x E dom &b is certain point on the line connecting (x) and (x)x). The first inequality is due to the definition of fz and the condition on vi such that d² f2(xx) (xx()x) s O. Plugging (16) and (17) into (15), and rearranging the terms, we arrive
1 Ex So [(F((x) - -7 (x))² (f:) (r²) Un.
(18)
where the term U2 is defined as U, Ex (r((((())) ((x) -xx
([(x))
It remains to analyze the generalization gap U2 for every iteration. The main challenge is that the learned model Ft depends on the initial dataset S, and the generalization error is related to the complexity of the hypothesis of the density ratio estimator. In the following lemma. we use the covering number [65. Chapter 27] measure the complexity of the hypothesis space. It possible to provide an upper bound of Ug with other advanced complexity measure.
Lemma 1. Let H, A fr: X + R |m - B be a hypothesis space of the density ratio function whose covering number is N(H,, s, 1-160)) Then, for all model r Hr and 6 (0, 1), we have the following upper bound
U. = -Ex=Do [6P (r (r(x)
-ri - Exxso (xx))()) -r(x)))
I (x( log (2N 11-1o))///
Es [(x(x) (x)))) 2A, +24 ME²
No
4
with probability at least 8 for any > O, where Cr(y) = B,, +
+ 16A4/ /1 + 3uB² =
Omax 1/11) with constants A, maxxxx
and B, = max [ B.).
Combining (18) and Lemma with the hypothesis space H, = Ho - {x 1(xx 0) 0 E { and rearranging the terms yields.
L Ex (x) - r, (x)) -[) + C(( (2N E, 11-) + -A,EE + ME
4
No
Further choosing e = T/T and taking the summation of the T iterations, we have
T
1
E
Exwso
(() - (x))))
4 1=1
T
T (x) + Ca(1) log (27 1/T, (1,ll)))) + D, t=1
Σ
LY (F))
(19)
No
1=1
where D, = 2A, + n/(4T) 0(1) is constant. Then, we proceed to bound the covering number of the hypothesis space Ho. Let 0, 0' E θ be the corresponding parameters for the two density ratio function r, E Hg. Then, we can show that for any ||0 8'1l2 S E, we have
max [h(x, 8) h(x, 0')l I G - 112 xeX
where G₁, = maXxex, eee [ 0)1l2 is the Lipschitz continuity constant. Then, we can check that the covering number of He in terms of loo can be bounded by that of θ in terms of ||-1|2
(20) In the above, the last inequality holds because the parameter space θ is essentially L2-ball with radius S, whose covering number is bounded by (35/e)² d [66]. Then, plugging (20) into (19), we arrive
[HH, 1/T, 11-1 S ((G,T), 11-112) < (3SG,T)d
T
4
T
(.)))) + (dTC,(( log (6SG,T/8) (+))))
4D,
Ex [(i(()) (x)
<
MNo
#
Then, we complete the proof by plugging this inequality into (14),
T
Bxm5 rī (x)l]
21

---

4T
T
Σ (8))))
T
4dT²Cr(()) log (6SG,T/6)
4TD,
(fi)
+
11
mNoo
1=1
4T
max
T
Lg (ft)
Σ
T
5400))00+
(71)) +0
max
1, 1
Todlog(T/0)
P
11
VNo
t=1
C.4 Useful Lemmas
(xx)))((x,))]]] Lemma Let Re(w) = B(x,))s, [x](x) x, drawn of So, all predictions E W satisfy
With probability at least over the
2BGDR
2ln(4/))
(w) Re(w)]
+ 4BL
VNo
No
Proof of Lemma 2. Since the risk funetion (w) bounded by BL for all w E W, the standard
analysis on generalization bound with Rademacher complexity (e.g. [65, Theorem 26.5]) shows that
ln(/0)
[w) (w)) S 28s, (C.) + 4BL
No
for any W. In above, the function space La is defined L. {(x, y) ri (x)(((TTx xx,
E W] and Rs. (Cx) (= supwew Ene (x,r(xx)((()) T xn. yn) is the empirical Rademacher complexity of Lt.
Note that the function on R - R defined as @n(2) = (x,, (2 Vn) is BG-Lipschitz such that 1 (w] x,) - 6n @n(, x,)] | < BGI (w -w2) Xn. for any Wi, W2 E W. Then, according to the Talagrand's lemma [65, Lemma 26.9], have
Rs. (Cx) < BGRs. (W),
where W (x+ w w E W) is hypothesis space for the linear functions. By [65, Lemma 26.10], the Rademacher complexity of the linear function class is bounded by
D maxx, E 1
1/x/l2 DR
Rs (W) S
VNo
VNo
We complete the proof by combining the above displayed inequalitics.
Proof of Lemma 1. We begin with the analysis for the generalization gap for fixed model E Hr- For notation simplicity, we denote by
(x) O2 (ri (r(x) - r² (x))
and the random variable Z; = Ex [x)] - (x:) for any x; So. Since x; i.i.d. sampled from Do and fo is independent of So. we have Z and Z < 2A, with the constants A, xiaxxexx@@@pbe (x))rī (x)l and B, = max B, maxxxxx [x()]]] Besides, the variance
of 7, is bounded by
E = Ex ((f()))) - (Ex-D, (E < Ex [(f())))]]
Then, by the Bernstein's 's inequality [65, Lemma B.9], with probability at least 8, we have
4A,, B, log(1/0)
2 2 (1((1)))) ED, [(F (xx())))
E Ex-D, [fr(x)) - Ex [fx(x)) <
3.o
No
B,
16A2
log(1/8)
# 8
ED. ((f(()))
No
22

---

B,
16 log(1/6) 3
M EDg [(r(x) - r/ (x))²]
No
(21)
where the first inequality is due to the AM-GM inequality. The second inequality is due to the fact that [x)l S (89tb(7 (x))r |r(x) - r (x) S (x - rf( for any x E X.
Then, since is a fixed model in Hr. we can further bound Ep, [(r(x) - (x))² by Es. (r(x) ((xx--17 (x)) by applying the Bernstein's inequality to the random variable Y; Specifically, after checking B ED, [(r(x) - (xx)))))/((B33 and
(r(x;) - rī (x:))²
Y [0, 1], a direct application of [65, Lemma B.10] implies
ED. [(((x) - (r) (x:))]
S Es, [r((x) [x] + 16B log(1/6)
8 8B2Es, [(((x) -
No
No
< 24B log (1/8) + Es. [r((x) rī (x))"
(22)
No
where the last inequality is due to the AM-GM inequality. Plugging (22) into (21), for a fixed r E He. we have
Ex Do [x]] - Ex [x)(
AA
log(2/0) 16A7 + 3
+ Es [(((x) - (e(x)))((xx)) (x)))
No 8
with probability at least 1 8.
Then, based on the notion of covering number, show union bound of U. over all r E Hy. Let N(H,, (l-lloc) be the E-net of H. such that for any r E H, one can find a E @NH,,, lll)) satisfying ||r-r'll> S The covering number N N(Hr, e, [I-]loe) is defined as the minimal cardinality of an e-net of Hy, By taking the union bound over all r' E N (H,,, e, lll), with probability at least 1 - 5, the following holds for any r' E &N,,, 8, I1-1),)),
If (x) - Ex~So [fr (x)] Cr(1))ogg
2N(H.,,.
(23)
+ Es [(r( ((xx))r;(x)))) (x))
M
No
8
where (r(n) = B, + 164//u / + 3uB, = O(max (r, 1/13). Then, for any model r E He. we can show
Ex (fr (x)] - Ex [x)]
Ex Ifr (x)] Ex~ S, [fr (x)] + (f - fr( - Ex - (x)]
< Ex [s (x) Ex Sn [sr (x)]
+ A,A,
(H) log (2N (H,,,, E, 11 10)
H Es,, [(r'(x) -x(x)))] -APE
No Cr(m)) log (2NN (H,,H, E, 100)))))
8
+ ! EEs. [(r(x) - (x))) + 2A,5 + RE
No
4
4
where the first inequality is due to the property of the e-net such that
Ex-Do./ - (x)) s Ex (0
- -2 (x)]] < Arllr - r'10o S Are.
The last inequality is by
M E.s, [r'(xx) - (x))) < LR,, [r((x) - [x))) + # E.s, [(r(x) - ?1
4
" r r r1133 < Es,, [(r(x) r3 (x))) + us²
< " Es [r((x) - (x)))
4
Thus, complete the proof.
23

---

Algorithm Base-learner &
Input: Active interval 1, = [s ei], regularization parameter X and step size 7) feasible domain e
1: Initialize the model f., any point in the domain è and the matrix As;-1 Ald-
2: for E 1, = [ ei] do
3: Submit the model 0,, to the meta-learner.
4: Update the matrix by Ar, = At-1, 1, + VL.(O...)V,(((..))
5: Update the model for next iteration by
0 - 1 7 VL.
where [u] arg min 0 u/lAn, the projection operator.
6: end for
D Omitted Details for Section 4
This section presents the omitted details for Section 4. We will first introduce the algorithm details for our online ensemble algorithm, characterized by its meta-base structure, in Appendix D. Then, we present the theoretical guarantees alongside their proofs for the base-learner (Lemma 3) and meta- learner (Lemma 10) in Appendix D.2 and Appendix D respectively. These elements collectively contribute the dynamic regret guarantee of the overall algorithm. The dynamic regret of the online ensemble algorithm (Theorem 2) is presented in Appendix D.4. We provide the proof for the average excess risk (Theorem 3) in Appendix D.5. Further discussions regarding the tightness of the bound and alternative choices for the Bregman divergence function are located in Appendices D.6 and D.7.
D.1 Omitted Algorithm Details
Here, we introduce the algorithmic details for the online ensemble method omitted in Section 4.1. Interval Schedules. We run multiple based learners on the geometric covering:
C C Uunenuoo Cs and C. {[i 2 (i (i+ 1)- 2* 1] E N and i. 2tt S T}
(24)
and then employ meta-learner combine them by weights. For any interval 1; [s), es] E C, which starts at time f = 8; and end at / Ci we denote by & the base-learner running over I..
Base-learner. The base-learner & updates his/her model with the ONS algorithm [44] in the associated active period I, The algorithmic details of the base-learner are summarized in Algorithm 1. At every iteration & E 7, the base-learner & will first submit his/her model 0z,; to the meta-learner and then update the model for the next iteration by Line 4 and Line shown in Algorithm
Meta-learner. The meta-learner aggregates the predictions each active base-learner by a weighted combination scheme. To obtain the weight pt. for each active base-learner &,, maintain three terms my Ut,i and ε,, for each base-learner E, when he/she is active, i.c., E 4. Let (:) = (VL,, (0.), 0 02) be a linearized loss for the original function (0). The first term is defined by
(o. (o....) LVL, (0.), oe..)
m4,1
SR
SR
which measures the performance gap between the meta-learner's prediction 0 and the i-th base- learner's 's prediction t.,, over the linearized loss (e). The second term Ut is the "potential" of the base-learner ε,, which measures the historical performance of &, over the interval. When invoking the base-learner E, at & = ss, we initialize U,, = 1/K and the term is updated by
V1,6 = (uo-1, (1+Ee.).m..))
Vt E I..
(25)
The last term εi is the learning rate, which is set as
In K
E, min
(26)
2'
14 E+=,, m²
24

---

Algorithm 2 Meta-learner
Input: Interval set for base-learners C.
1: litialize the set for active base-learner Ao @ and let K -C/--
2: for / 1,..., do
3: for I, [s, E do
4: if' s; is equal to & then
5: Create base-lcaner by Algorithm and initialize the potential Us, 1/K and
step size E,, = min(1/2 vIn K}. Add the index to the active set A, A U {i}.
6:
7: else if e; + is equal to then
8:
Remove the index from the active set Ar = A
9: end if
10:
end for
11: Receive the 0.. from active base-learners & E A, and update their weights pt, by (27).
12:
Submit the model by 0g EvEA, Pr,
13:
for i E A do
14:
Update the step size 1,+1,1 for all current active base-learner by (26).
15:
Update the potential 1441, for all current active base-learner by (25).
end for
17:
end for
After obtaining the ve,i and Et, for each active base-learner, the weight for the next iteration + is updated by
Et,eUt,i for E A441-
PL111 = EieAcy E
(27)
The algorithm is summarized in Algorithm 2. At the beginning of each iteration I, the algorithm will update the index set for the active base-learner (Line 3-L 10). Then, the meta-learne''s prediction generated by the weighted combination rule (Line 11). After that, the meta-learner will update the potential 1, and the step Et+1,i for the next iteration.
D.2 Regret Guarantee for Base-Algorithn (Lemma 3)
By suitable configurations of the parameters 7, > we show that the ONS algorithm enjoys the following dynamic regret guarantees,
Lemma 3. Let 07 arg minøers (.(0) and all the minimizer 07 's lie in the interior of Q Set Then, with probability least the ONS running on the interval 7, = [si, es C [T] ensures
? 6(1 3) and
Ei.O. I.(00)) < so = (171/8) [ZI((?)2
[1 [og(T/() No
1eL.
where VT. E
07-1112 is the path length measuring the fluctuation of the minimizers. |10
D.2.1 Main Proof
This section provides the proof of the ONS algorithm. Since the analysis of the single base-learner is independent from the online ensemble structure, for notation simplicity, we omit the subscribe of the base-learner in the analysis. Specifically, we abbreviate the prediction 0r matrix A and the interval I Or, matrix A, and the interval / respectively.
Proof of Lemma 3. We begin the proof the dynamic regret with a lemma on statie regret of the ONS algorithm, whose proof is proved in Appendix D.2.2. For notation simplicity, we omit the subscribes of the base-learner, where the prediction 0,,s, matrix Ag and interval I, is abbreviated as 0,, A, and I, respectively.
25

---

Lemma 4. y 6(1 + B) and À = 1. With probability at least 1 26, for any d E (0, 11. the
ONS algorithm (8) running on the interval I = [s.c] - [T] ensures
E.. - Σ (0) - (6) = o (d3 (og(1(()1))
TET
EE1
for any 0 E O where C (6) = 12d3' log (1 + [ +
S 3
+ (48 + 6
V211+1 log
1
8
(4SR + s²n², n? log o²
+1 and 3' = B +
Then, we can decompose the dynamic regret as follows,
(i,(O))
[l(( = Σ (.)) Ii((7)) + Σ (,(07) +II(07))
Σ
1El
IE1
1E1
IE1
IEI
(ET
< of (0) + - - -EI
(28)
LE1
LE1
EiEr 0 is an averaged prediction of the function minimizers over T rounds. Under the condition all function minimizers lie in the interior of θ, we have 0j E O. As consequence, the last inequality holds due to Lemma 4.
where 87 1
Then, we proceed to bound the last two terms of the R.H.S. of the above inequality. Since the first-order derivative of the sigmoid function o d'(z) exp(-2)/(L + exp(-2))² S 1/4 for any 2 E R. Let Ia E Raxd be the identity matrix. we can check L, is a R2 /2//4-soon 4mooth function such that (0), Bx [o'(x (x((x (x)) + 1o (x (x)
R² 4 Ia for any 0 E O.
Then, with probability at least 26, we have
R²
L.(07) - (0)) < (VL,(0;), 0,)
00 0,
8
8 V. +
R2
100 0,13
R
4
16 16 + 1)/8)
R²
log(d/6)
00 07112 +
No
4
No
16 16In((d + 1)/8)
R²
(V1)2 + (log(d/))
(29)
No
4
No
where V/2 = Distt |0_ 1/ with s being the start time of the interval and e being the ending time. In above, the first inequality due to the smoothness of the loss function and the second inequality comes from the AM-GM inequality. The third inequality is due to Lemma 5. The last inequality can be obtained by the definition of 07 such that
(
2
2
100 1/
0
0:
<
Σ
10
0,112
$ (V/)2.
Plugging (29) into (28) and taking the summation over I rounds, we obtain
Σ (
[()
IET
GET
16/4 In((d 1)141/88
R² 111((1)) +o
[ (og(d)11100)
< cf +
No
No
=o d3 (oggll1/////
[X] [nd1/1)))
+ +
No
with probability at least --30 36. We have completed the proof.
26

---

D.2.2 Useful Lemmas
Lemma 4. Set 6(1 + () and À = 1. With probability at least 1 26, for any ó E (0, 1). the
ONS algorithm (8) running on the interval I I [T] ensures,
ΣL.O0 - Σi,(0) (0) - c (8) - (d3
TET
DE1
for any 0 E ④ where C = 12d3' log (1 + [| + S
3/30 + (488' +
65 R² V21+1
log
8'
(4SR + s²R') 8
log 21 and 3' 1+1
Proof of Lemma 4. The main difference between the proof of Lemma and the standard analysis for the ONS algorithm (c.g., proof of [13, Theorem 4.3]) is that the later one is for the full information online learning setting, in which the learner can exactly observe the loss function L. However, in the continuous covariate shift problem, challenge bound generalization gap between the expected loss L, and the empirical observation T., (e.g. term (b) in (35)). We manage show such a gap can bounded by O T) with the self-normalized concentration inequality for the martingale different sequence.
only observe the empirical loss L,, which poses the
We start with the analysis of the instantaneous regret. By the Taylor's theorem, have
(ū.)) (,) = (VL, - -- 0) " -0)-
(30)
where & _R is certain point on the line connecting 0 and 0.. In above, the second order derivative L can be further lower bounded by
1 F Fx (o (x)(())(())
]]+ Rx lo' (x)
2
(Ex~s, 1x
4(1 + S))
>
1
(Z,
(31)
2(1 + B)
where d(x)) exp(-2)/1 + exp(-z))² is first-order derivative of the sigmoid function (=2) = 1/(1 2x) and A > B indicates A - B is positive semi-definite matrix for any matrix A, B E paxd The first equality is due to the definition of L, and the second inequality is due to Lemma 6.
Plugging (31) into (30), have
(0.)) - [,(00) S (V),
4(1+ (O.
1
(32)
Let E.Fl Es. -D, Su, S1, ... 1 be the expectation taken over the draw of S, conditioned on the randomness until round 1. Since 0, is independent of St, we have E. (0.)) (0.) and E, (.., = (O.) Taking the expectation over both sides of (32) yields
(,:)) - L.(
< (O.) 0, - -0) - 4(1 + 3)
1
E, (VL. (000-0)) (0,-))))
(V., -0) 0) + (VL.(0.) VL. - 4(1 + B)
1
E. (VL,(0)) -0))²]
(33)
where the first term of the R.H.S. can be further bounded by
(V. - 0) (O.), 0) (VL. - 0(41)
27

---

$ 24 (0) 012, 100+1 - 012, 10: - -0+11121, + (V), 0. - -0++1)
(00 012,
10 - 012.. 10. - 11a)) + 2,/11
22 110 2 112111
1
2y
= 27 [L. (0))1 A + 1
27 (10. - 0112, 10 - 0112.)
- 27 VL, (0.) + 27 [10, - 0112,_, - -100+1 - -112.) + -/2 (V., -))
1 2;
(34)
In above, the first incquality is due to the update rule of the ONS algorithm and the Bregman proximal inequality [67, Lemma 5J. The second inequality is due to the AM-GM inequality. The last equality
due the definition of A, such that 1|0c 0 - -10 01
(VL, (0.) (0. 0))²
Plugging (34) into (33) and taking the summation over the interval I [s, e]. have
Σ
(..)
Σ (0)
IE/
27
1
00
-112,
+
1 Σ
(V) 0))
27
2
LE1
E1
(35)
term (a)
(T), - Vi. 0)
E. (V) 0])
4(1 +
IEI
1E1
term (b)
Now, we proceed bound term (a) and term (b), respectively. Firstly, according to Lemma we can show term (a) is bounded by
R X
term (a) s 2dl log 1
Then, we handle term (b) with the Bernsteinttype self-normalized concentration inequality [68, Theorem 4] Specifically, let E.[-] = Es.-D, S, Si...., St-1] be the expectation taken over
the draw of St conditioned on the randomness until round f 1. Denoting by Z, = (VL, (0.) VL, (..) (,), 0, 0), it is easy to check (Ze) is martingale difference sequence such that E, [Zr] 0 and |z < R.R. Lemma 8 with the choice v = 1/(48(1 + ()) indicates,
term (b) S 24(1 + B)
Σ SE!
(V...()))(().)) -0)) + E. (VIL()) (0)))))))
2
2/ +
+ 48(1 + B) log
4SR log
(36)
52
Combining the upper bounds for term (a) and term (b) with (35), we have
I((O0) - Σ (0)
YES
IE1
R
2252
2
+1
2 +1
< 2dy log
1+
+
+ +81 + log
+
4SR V log
X
7
8
82
1
1
L(VI. (0.) T 0))
5
(V.) (0.-
- 0))
+
2ry
24(1
B)
24(1 B)
1E!
YE!
term (c)
(37)
Then, setting y 6(1 B), with probability at least -- 8, we can bound term (c) by
term (c) < 6(1 + B)
3
VL. 0))²
5
E, (VIZ. -00000000)) 0))²)
4 111
28

---

65 R2 1+ /
/2 +1
S
2 +
log
log
6
1+
8²
where the last inequality is due to Lemma 9, Combining the upper bound for term (c) and (37) and setting À 1, we have
Σ (0.) TE1
Σ I.(
LEI
S
S 12d(1 + +,3) log (1 + | +
333 + 3
R.
/2 +
S²R²
21 + log
+ 48(B + 1
log
4SR+ +
3+1
82
(0 log(
with probability at least
26, which completes the proof.
Lemma 5. When all the minimizers 0 = arg min Le( lie in the interior of O then we have
(0))11 2n2 In((d + 1)/0) +
[log(//))
No
No
Proof of Lemma 5. Since all the minimizers 02 arg mingeRa Ix(0) lie in the interior of θ, then we have (O,) and the term (0) can be rewritten
Vi. (e,) VL,
I Fx
(( 0;) 1)o(x)) ( 1)((x)]11
No.
=
No
Un
(38)
2
where 1 with Zn (T 1))(),) Ex ((((ox) T 07) 1)x(x) are No
independent random vectors. We can check that ~x, [nn] = 0 and || Zm l2 S 2R for any E X. Then by the Hoeffding's inequality for the random vector [69, Theorem 6. 1.1.1 I.1], with probability least 1 - 8, we have
1 No
2RIn((d + 1)8)
8R² In((d + 1)/6)
7m
(39)
3No
No
2
Plugging (39) into (38) obtains
VL,(07)
2R In((d+1)/8)
log(d/8)
No
No
Lemma 6. Let (.. (0 (O:) - 1)o(x))
s, 0x)(())) We have
2vi & Ex [xx 1 Ex-s, { ((xx)
Proof of Lemma 6. For notation simplicity, denote a, Ex (a (xTT) 1)x] and b, (xx)))x)]
Ex (a(x xx)x.. Then, according to the definition of V T., (O.), we have
V 4 (a. + b,) + b.)
1 2 (ara + b,b,))
where the last inequality is due to Lemma 16. We can further bound the R.H.S. of the above inequality by
a,a, (((osx((((((()) 1)x(())) ((x-sx)(o(( 1)6(x)))
(oox 0,) -
(0))-))2(xxxpl 1))x(x)((x)) Exxs,,0(xxx05
29

---

In above the first inequality is due to the fact that B/a 1 [a] < E/aa"] for any random vector
Rd. The second inequality comes from (a(x 8,) 1)2 I 1 since the output value of the
sigmoid function a is bounded in (0, 1). A similar arguments shows b,b, S 18x~s, (x())(())
Combining it with above displayed inequalities completes the proof.
Lemma 7. The predictions returned by the ONS algorithm satisfies,
S dlog (1 | A
Σ XET
EIVL,O)
Proof of Lemma 7. The proof follows the standard arguments the analysis of the online Newton step algorithm [13, Theorem 4.3]. We present the proof here for self-containedness.
Σ tET
vl,(0)) = Σv A LL.
tET
Σ
Irace
(1.
EE/
Σ trace (A,
Ac-1))
TET
|A,1
|Ael
Σ TET
log
=log
|Ac-1
|Aal*
where the last inequality due to the fact that trace( A- B)) S log(1 Al/|B) for any positive
definite matrix satisfying A > B > 0 [13, Lemma 4.5).
By definition, we have A, AIa Iddd and we have A, = AIa + Exer (.,
Furthermore, since || [. N R. we have |Ael S (11)12 + A)d. In such a case, we can bound the above inequality by
[Ael
(IIR2 + A)
1 X
Σ DI S log FET
< log
S d
1+
[Aa
A'
and finish the proof.
Lemma 8. Let 21 (V.) VL.(0,,,, -0). Then, with probability at least 1 8, we have
E < 2v
Σ
VL.(0.) T -0)
+ 2v Σ E,
(..)
(0. - -0]) 27
IET
IE1
tET
1
2 +1
2 +
log
+
4S
R
log
V
6
82
for any 5 E 10 and O.
Proof of Lemma 8. We can check that (2.)_. is a martingale difference sequencee such that IE, [2c] O since oe is independent of St. Further noting that Zz < ( - (L. 12:11, 0|12 4SR. a direct application of Lemma 17 shows that
2 + + 4SR log
2 +1
Σz NET
2
E,
log
(40)
8
82
TET
with probability least 1 8 for any O. Then, for any t E [T], can further bound the term 2 and E. [2?] by
= (VL, - VL.(O.),
0/2 < 2(VL. 2 2.). 0)2
(41)
and
E, = (V 0, - 033 (VL. -0
30

---

where the first inequality is due to the fact (a b)2 - 2a² + 26 for any a. b E R. Then, combining the above two displayed inequalities and taking the summation over T iterations, we have
Σ tE!
+4++
E,
+ 2
B.|zi1 < 22(V 2 -
tE!
EE
tES
(42)
We complete the proof by plugging (42) into (40).
Lemma 9,
With probability at least ô, we have
3
(V). (0. 0))²
R2 (O)) -0)8]]] S AT(())
4
EE
DEl
for any ô E (0, 1), where A,) 32S R22 log V / + 4.
v log 24
Proof of Lemma 9, We can check {Ye]i=. is a martingale difference sequence such that |Y/] s 4S2 R². As consequence, direct application of Lemma 17 implies,
Σv: [(V (Ō. 0))² - Σ E2 [V 01)²] 1E1
IE1
EE!
S 2v
Σ (O.) -0)+
TØ. 0)>1))
2 +1
log 211 +1
V log
+ 452 R2
Σ (.)) (0,- + E. Lx (0.) - -)))))
32S R² log 2 +1 + 45 R² log 82
2
where the first inequality follows the proof of Lemma and the second inequaliuty due to the parameter setting / = 1/(32S R²) and the condition that (VL, (0. - 0))² s R² Rearranging the above inequlaity, have
3 4
(L. - 0))
E, (V.)
( 0))2
IE1
EE1
/
2 +1
R² log
+ 4S² R²
RS2R²
V
log
6
8²
which completes the proof.
D.3 Regret Guarantee for Meta-Algorithm (Lemma 10)
We have the following guarantee on the meta-algorithm, which ensures that for any interval I, E C, the final prediction is comparable with the prediction of the base-learner &, with an Olog T) cost.
Lemma 10. For any interval I; C and 8 (0, 1), with probability least - 8, the final prediction returned by our meta-learner satisfies
EL.00 ELOO..) & (T)) YET;
LET,
where K == =1C] is the number of the intervals contained in the set C.
31

---

D.3.1
Main Proof
This part presents the proof of Lemma 10. Our analysis for the meta-learner is based on that of the strongly adaptive algorithm [70], where the problem of tracking base-learners on the corresponding intervals is converted to a sleeping expert problem [71]. The main challenge of our problem is that the feedback function noisy. Thus, we require to provide tight analysis on the generalization gap between I, and L, without ruining the (log 7) regret guarantee. By twisting the meta-algorithm from Hedge [42] used in the previous work to Adapt-ML-Prood [43], we show that the generalization gap can be cancelled by the negative term introduced by the exp-concavity of the loss functions (see how to bound term (b) in (48)).
Proof of Lemma 10. To prove Lemma 10, show that the final prediction 0, generated by rule 0, EE,EA Pt. with the weight update procedure (25), (26) and (27) is identical an algorithm learning in the standard prediction with expert advice (PEA) setting [72], where all base-learners submit their predictions at each time E (T).
Lemma 1I.
For any base-learner Eú, let & be surrogate & whose prediction 0e, = Ōo.5 , is the same that of for any E I; and 0t, 0e for other iterations. Then, for any time t [T], the surrogate meta- -eaa-eerrerr predicts as
0, = Epadre and Pr.i = ΣiE[K] 1,
E1-1,10-11
(43)
iE(R]
where the potential Ve,i and the learning rate EL,s is defined as
$1. Tt-1
Ut (ū--1. (1 1,
for all 1 [7],
(44)
and
K
Eti = min
for all t E [T]
(45)
2' 1 Ei= m
with ma,; = (Z.(())) 0g - B,,)) To.s
1 K and Eo.; = min(1/2 K} for all i e [K]. Then, we
have 9. = 0r for any e [T].
We have the following guarantee for the final prediction generated by the surrogate algorithm defined by (43).
Lemma 12. With probability at least 28, for any 8 E (0, 1), the prediction returned by the surrogate meta-algorithe defined as (43) ensures,
T
(.(0.)
Ii(O S (8) 0 (0 3Bmmk)
for any base-algorithm E/ i E [K]. where c = 16(1+8) (C + 6(1+8)
Ink
2C" + 24(1 + 3) + p1 In (1 K (1 + (n( + 1))) = O(In K + 1n.
I+9 log 22T+I + [SR + S²R² X(+3)
V log
2T 8
and Cy = 3ln +
Then, according to the relationship between & and E,, we can bound the regret of the final prediction 0, with respect to that of any base-learner E, over the interval 1, by
T
(..).
Σi. TEI.
Σ (O.) EL.(ss)) s (P) (0) 0(3l0g(T/// + 3,8m K). 1=1
1EL.
In above, the first equality is due to Lemma 11 and the definition of the surrogate base-learner E such that 0.,- = Ōe, for any E I; and 0,,- = 0. for any L E [T]/I. The first inequality is due to Lemma 12. In the last equality, we treat double logarithmic factors T as a constant, following previous studies [73, 74]. We have completed the proof.
32

---

D.3.2 Useful Lemma
Proof of Lemma 1I. We show that the predictions 0g and 6g by the two algorithm are exactly the same for any & [T] by induction. At iteration E [T), we have the following two induction hypotheses:
IHI: the final predictions satisfy 0- = 0- for all T S...
/f12: any base-algorithms & A, satisfy Pr,i -rri/ Pr,s) for all T S L.
Base case: For the base case of = 1, there only one active base-algorithm. Denote by i the index of the active alse-algori,hm, we have 0, = -11.i. Pı, = and A, = -f Moreover, for the surrogate algorithm, we have Pı,: 1/K for any [K] and 01 (EgKk]/a 0 i
01. We check that 01 0, and Pı, /1,s/ EiEr, Pr, a for any i A1. Induction step: For the induction step, we first show
P1+1,
Pt+1,i ExEree Pe+1,i
(46)
for E A.t1. By the definition of Pe+1,s it sufficient to prove
Er, for any i E A
P1+11 ΣiEAm Cr,
(47)
For the base-algorithm E, active at iteration + and his/her corresponding surrogate base-algorithm E,, we can decompose the time horizon until t + into two intervals: asleep interval I = [1, s; 1]
and active part Ieet = [s,, + 1). For any time stamp belonging to the asleep interval T E I we can check that the loss for the base-algorithm E satisfies
mr (O.). θ.,.) (O.),, - 0,) = =0,
where the first equality is by the definition of m.,,s. The second equality is due to IHI such that
0, 0, for any S and the definition of the surrogate base-learner & such that the prediction
,,,; = o, on the aslcep interval. For any time stamp belonging to the active interval 5 E I,st, similar argument shows that
my,; = (,,(0)),,,-
- = -,,i
Thus, by definition, we can draw the conclusion that ūy u4,; and Ee, ets for any active base-algorithm with index i E A+t1, which would finally lead to (47).
Then, we show Ō.t1 Dz+1 based on IHI and IH2. We have
0.11
Σ
Pe41,
Σ
0
iEAc41
iE(K]/AL-1
+(1-
Σ HEAl+1
Petra
Σ
Peti Phtt,
+ 1
Σ Detis
Oet1
(Ede+z
iEAet1
Σ iEAA+
P411A
0s
1-
Σ Petia
Ō0t1
Oz.
iEAAh
where the first equality is due to (46) and the second inequality is due to the definition of Ūeg1. We have finished the induction steps and completed the proof.
Proof of Lemma 12. Since 0r and o., are both independent of S,, using the same arguments for obtaining (33), can obtain that
Σ (0.) Σ L. (..).)) s Σ (V). 0..))
Σ
(.) V -
tern (a)
tern (b)
33

---

T
E (V.) (0.))
(48)
2(3 + 1)
1=1
For term (a), have
2SRCT
1 (L,(0))T 1.:--81) -mi)) + +22
term (a) -
vIn K
24(3 + 1)S2 R2 (C))2
1
(L.( 10, -B..) + +C2,, 6(3 +
1
+
InK
1)
(49)
for any i E [K], where Ci5, 31n K In (1+ (1+ 1))) O(n K In In above, the first inequality is direct application of [43, Corollary 4] with the linearized loss M,(0)
(0.) 0)/ (2SR) + 1/2 and the second inequality is due to the AM-GM inequality.
For term (b), by Lemma 8 with v = 6(1 + 3) and a similar argument in (36), we have
1
T
(Vi. (0. - B(.)))² + E. (VI,()) - -B..)) )
)
term (b) v
12(1 3)
1=1
2T
2T +
+ 24(1 + log
+ 4SR log 8²
(50)
8
Combining the upper bound for term (a) and term (b) with (48) yields,
(.) - Σ (.,)))
T
(L.(O,) 100, - -bii)² 12(1 + 8) E. [(VI.()) T(, (00--0..) (00-0(,))) 02.))
21
<
4(1 + 3)
t=1
tezn (c)
24(1 + (C
V2T +1 1
2T +
+
6(1 + 3) + +02 + 24(1 + B) log
+ 4SR
log 82
Kn
8
Then, according Lemma 9, we can further bound term (c) by
term (c)
1
(.. (0. -o.s)
5
Er
(VL,(0))T
(0. 0
4(1 + 3)
12(1 + 3)
11
2 +1
4S R²
2T +
log
3(1 + B) /
log
1 B
5
82
which implies
T
T
Σ (..).)
tm1
< 24(1 (2)
1
V2T+1 +1
2T +
+
+ 2C C log
+ C/ log
In K 0(8log (T/8) 11 K).
6(1 + B)
82
In above, C7- 21(1 3) + 11S2 /1 + 3) and C²2- = 4SR + 45 15 3)). In the last equality, we treat double logarithmic factors in T as a constant, following previous studies [73, 74]. We have completed the proof.
D.4 Proof of Theorem 2
This part presents the proof for Theorem 2, which based on the dynamic regret for the base-learner (Lemma 3) and that for the meta-learner (Lemma 10) presented in Appendix D.
34

---

D.4.1 Main Proof
Proof of Theorem 2. When choosing the Bregman divergence function as (b()) 1/LR(t) t llog (1+1) 1)) and the hypothesis space Hhp
(x exp(-0' x(x)) |01|2 S 5}. The expected
loss function (0) defined by (4) equal
(. = _/2 ED, [log(1 te + O)] + (log(1 + _00x))
Let 02 - arg mingeg (0). Since the ground-truth density ratio r (x) / /D((x) function contained in the hypothesis space as D,(x)/ E Hd.. One can show that D,(x)/Do(x) = exp(-(0;) ((x)) and 07 E θ {e E R |10112 8).
Then, for the base-learner E; running on any interval 7,, Lemma 3 in Appendix D.2 shows that its prediction or,; is comparable with the best model at every iteration 07 with an O(IT)(()))) cost:
ELoOres- Σ Le((0)) so ((BBlog (141/6) + (4)()))
logg
(51)
No
FET,
tEL,
where VT. E 11=0++1105 100 01-1112 112 is the path length measuring the fluctuation of the minimizers.
Besides, Lemma 10 in Appendix D.3 ensures that the prediction 6, of the meta-learner is comparable with the prediction o, of each base-learner & on the associated interval 1, with an (log T))
ΣE,O Et. s tET:
3m
(52)
NET;
A direct combination of (51) and (52) shows that the meta-learner is able to track the best prediction or on any interval I, E C. Actually, by exploiting the structure of the geometric covering (24), it can be shown that such property can be extended arbitrary interval I E [T] as the following lemma, whose proof is deferred to Appendix D.4.2.
Lemma 13. With probability least 1 56 for any å E (0, for any interval [s,e] [T]. the meta-learner's prediction 6g returned by (9) ensures,
Σ (..)
IET
YET
S [1((1)) + 21og/ (cL) + C4(61) 16/ [6]7]]/ In((d+11)og))1)/))
R²
[ log log(dd
+o
No
No
where V/ Ei=4t1 |0 0111 and 8' 6/2log 11. The coefficient
(d3
and c2 (6) = O log(T/))) defined in Lemma 4 and Lemma 12, respectively.
Then, we can use the bin partition [19, Lemma 30] to convert the dynamic regret each interval to dynamic regret over T iterations. For colffcontainedness, we restate the lemma here.
Lemma 14 (Lemma 30 of [19]). There exists partition P. of the time horizon [T') into M
O(max(dT" /3 (U4)2/3,1) ,1}) intervals jie., {4 [st, e, such that for any interval I E P.
U%. S Dmax/ / Lil. where U9, - -i 10; 07-1111 and Dmax max S max S.
Then, we can decompose the overall dynamic regret of our method into those over the key partition P. Specifically, with probability at least 56, we have
(.)))) - Σ (07)
1=1
E=1
Σ
Σ
(.(0)
I
35

---

16/1 In (2
Rt
$
Σ
+
Σ
4
No
7EP
I.P
logl Til (4+) (6/2M loalr)) + O7 (5/aMMoulz)))
+ 2
LEP
16T 12d++1)7 TM/8
MS² R2
2M log'T (cf) (1/2 + cf (6/2M
log (4/2Mbo0))
+
4
No
terTE (8)
torn (b)
tern (c)
where the second last incquality is due to Lemma 13 and union bound taken over all intervals in the key partition. The last inequality due to Lemma 14 such that V%, I Uf. S/VT; for any interval I E P. Lemma 14 shows that we can bound the partition number by M O (UTT 11) = (maxx (1 1)). Then, we can further show that
term (a) O (1/3 max (Tax (V .1))
term (b) S O 41/3 log T' (T/(0 max (T (1 13)
T Tin(dT/))
term (c) (c) 5 0
No
which implies that the overall dynamic regret bounded by
EL.O0 Ei.O) s E
T
T
o d d (dgBlog log? T log (T/6) (T3 1)
T (lnd
No
Hence, we complete the proof by showing (07) = (r() under the realizable assumption and converting the variation of the model parameter VL Ei=1100 2 0i-11l2 to the variation of the feature distribution VT= = (Dx() D2-1(x)]11 by Lemma 15.
D.4.2 Useful Lemmas
Lemma 13. With probability at least 1 - 56 for any ō E (0, 1), for any interval [s, E [7]. the meta-learner's prediction Og returned by (9) ensures.
Σ (..) TT((
IE1
TET
R²
[[((P)) + 2og (C + C2(61) + 16 7| In(((111 T/8) to
(o
< 4
No
No
where Vi Ei=041 10: 17112 and 8' = 6/21o5 The coefficient cf O loglog(() (T/8))
(8) and ( O (o))(T is defined in Lemma 4 and Lemma 12, respectively.
Proof of Lemma 13. A direct combination of Lemma 3 and 10 shows that, with probability at least 1 58, we have the following dynamic regret guarantee on any interval = [ss, e,] E C.
O.)
Σ (0))
IE1
AET
cff (0) + C/22 (8) + R²
4 2 + 16/4, In((d + 1)/41/8) +
14 log(d[44/00) (53)
(
No
No
where VL.- Ed Eis5--100i-11 07112. The coefficient c = 0 (d3 log( (+//))) is defined in Lemma and cf2 (8) = 0 (oloo(T/0 (8) is defined Lemma
36

---

For any interval I = ss e| S [T). [75, Lemma 3] showed that it can be partitioned into two sequences
of disjoint and consecutive intervals, denoted by I_p...., E C and I..... Ig E C. such that
|=il/\7=+111 - 1/2, 2 and
| - 1/2, Vi 2 2.
(54)
Then, with probability at least 1 56, we can decompose the regret over I = [s, c] S [T]
?
Σ 1E1
O.) Σ IET
Σ
(.)) - [[,
1=-p MET
IET,
R² Σ 1L(()))
S (p + () (6/p+9) + +C (5/p+0) +
t=-p
16 In In(((++(o+t)))/
Log + 9)/6)
No
No
where the last inequality is due to (53) and a union bound taken over all intervals. Then, due to the partition of the intervals (54), we can check that p p+ q S 2log] T]. Then, we can further bound the above displayed inequality by
R2 L,) < log|d (f/2 (D)) + (5/21000))))) + + [V(2))) TET
Σ (O.) RET
16 b6
([Tog((TTog111/))
+
No
No
R² ( + +0 d3 logg ||gg//|oog//////// +
[1] lo dTT log 11/8)
No
where the first inequality is due to the fact that Ei=p V S V7. This completes the proof.
Lemma 15. Under the condition that Dx(x)/Do(x) E HBR - (exp(-0T ||0|2 S S} for
any 1 E [T] and (lx(() al] 2 a a/|a|p for any a E Rd with certain a >> 0. Then, we have
|10: - 01 s BI Di (x)]l////
Proof of Lemma 15. Under the realizable assumption such that Dx(x)/Po(x) E H6 One can verify that exp(-o(x) 01) (x (x)))(((x.. Then, we can convert the variation of the model |102-1 - 0, to the variation of the distribution [D:-1 (x) - (x(x)l11.
1 Ben-Doli(x 100-1-001101111
110_1 0,112 a
07 e 0f S 3 S B ExwDo [le (
Dx(x) Dx-1(x)
|| = - |ID((x) (D-x))ll a
Ex
a
a
Do(x)
Do(x)
where the first inequality is by the condition Ex Do [xx(x) Tall 2 a allall2 and the second is by the
mean value theorem and the boundedness of (ø(x) (0:-1 - -0;] < 2SR for any x E X. The last inequality is due to the realizable assumption.
D.5
Proof of Theorem 3
Proof of Theorem 3. Then, we can bound the overall excess risk over the model trained by IW- ERM (1) by combination of Proposition I and Theorem as
1
T
(w:)
Σ R((w))
T
<
B C-Cr())
+
21 Exaso - (x)
T
VNo
1=1
B. Cr(
4LB
T
T
Log(T/0)
T
Σ
L.(O.)
L,(
+0
(55)
VNo
T
VNo
t=1
t=1
37

---

where the first inequality is due to Proposition and Cr = 2GDR + / O(log(T/6)) The second inequality is due to Theorem with the choice of the logistic regression model (t) = t toggt 100t--11+3) (1+t) log(1+t) and Fr (x) =
(8T/5)
0,) and the realizability assumption
rf (x) = ((x) 87). Then, by Theorem 2, we have
T
Te(rt) = log log (T/6) max mmax(TiV (T
T Tin(dT/0)
Σ
No
which implies
$o(ai log (T/6) max vT) + T
In(dT/O (8)
T
Σ (0))
L((:))
No
(56)
We complete the proof by substituting (56) it into (55).
L
D.6 Discussion on Tightness of the Bound
This part illustrates the tightness of our bound with the case where the labels of testing samples available after the prediction.
Continuous Shift with Labeled Feedback. We consider T T'round online learning process. At iteration t, the learner submits her prediction w, E W. At the same time, the environments pick the data pair (X,, M1) De. Then, the learner updates her model with the loss function R, (w) = E(w xx, 9r) and obtains the prediction W++1 e W for the next iteration. The goal of the learner is to minimize the cumulative excess risk against the sequence of optimal models w? arg wew (w)),, that is,
Ri RrWWW
Rd (w
Σ (w:).
(57)
The goal is the same as that of standard continuous covariate shift, see the problem setup in (1). The key difference is that now the label of testing data is available. Therefore, the noisy feedback R2 (w) observed by the leamer is unbiased estimator with respect to the true risk R.(w).
Tightness of Our Bound. The continuous shift with labeled feedback is essentially non-stationary stochastic optimization problem [39]. For general convex functions, [39] showed that any gradient- based al algorithm will suffer
E (( ( = Ω (/-3
(58)
in the worst case. In above, V Σt= maxwew (w) R-- 1 (w) measures the fluctuation of the risk function. For the same performance measure, our algorithm achieves
max (T1/5v 1/3 --)))
Rr (r((
(59)
NN
In the non-stationary case, i.e., Vr 2 (T our bound becomes (1/VNo + T-1/3/ As discussed below Proposition the first term (1) is hard to be improved. We thus focus the tightness of the second term O(T-1/3y,1
Although the definition of Vr in our upper bound is different from the that of V in the lower bound (58), the two bounds share the same dependence on the time horizon T, which provides evidence that our bound is hard to improve. Indeed, consider the 1-dimensional case where the underlying distribution only shifts once from Dz y) to D2(r,, v) at certain time i. E [7). In such case, VT= O(1) and our bound implies an (1/31/3) rate for the second term of (59). On the other hand, the rate in the lower bound (58) becomes 11/33. The same dependence on the time horizon T indicates our bound is hard improve. We leave precise lower bound argument as the future work.
38

---

D.7 On Other Choices of Bregman Divergence Function
In this section, we discuss how apply the other two choice of the divergence function eiLs (t - /) 2 and dKKL tlggt- - t in our framework. Our analysis crucially relies on two conditions:
the Bregman divergence function v satisfies the conditions in Theorem
2. the induced loss function (0) is exp-concave and smooth function with respect to 0.
Choice of (1) = (L - 12 Considering the Bregman divergence function (+(() = (t - 1) and the hypothesis space Hg = {x + <(x) T ||0 la S S), where ; + R2 represents
specific basis function with bounded norm | x 2 S R. Then, the loss 2 (0) as per (7) becomes
(0)
1 Es (((()) T 0) Es, (ox)))))
2
The above configuration recovers the unconstrained least-squares importance fitting (uLSIF) method [28]. We can show such a choice of divergence function satisfy the condition required by Theorem and enjoys favorable function properties.
Conditions in Theorem I: when Bregman divergence function is chosen Lhs we have (t) = 1 and @'))s((t) = 0. Thus, tLs is a 1-strongly convex function and v0s 0 for t R.
Expconcavity and smoothness: We have (² (xx))(x)(())) TJ. Then, when the input is upper bounded by [[x(x)] I R for all é(x) X, have (2), R which implies the smoothness. Furthermore, if the initial data ensure (x)x())
ald. the (0) strongly convex and thus is exp-concave as shown by [60, Lemma 2]. We note that the regularity condition the offline data Es, (o(x)((x)) ] aTa is used in the analysis of LSIF algorithm [28, Lemma l].
Choice of t²Kl- = t log t - t. Considering the Bregman divergence function (t) = t log t - t and the hypothesis Hg = fx + <(x)T 8 ||0||2 I S}. where Φ X + R4 represents a specific basis function with bounded norm [|ø(x) - R. Then, the loss Σ (0) per (7) becomes
(0) = Es, [xx) T 0)] Es, (ox))) To)].
To ensure (0) is well-defined, we further require the density function f(x) <xx) 1/B for any x E X' and θ {0 |10||2 < S} with certain positive constant 3 > 0. The above configuration recovers the UKL method [37] with the generalized linear model. We can show such a choice of divergence function satisfy the condition required by Theorem and enjoys favorable function properties.
Conditions in Theorem 1: When Bregman divergence function is chosen d'KL, we have ( = 1/t and 0 xxxxx( (t) = -1/t². When the input of the loss function satisfies 1 12 B, thKl (t) is 1/9-strongly convex function, and we can also check that 102 (1) < 0 for all / E R
Expconcavity and smoothness: We have v²Z,(0) EEs (x())((x)) (Ø(x)) (000x))T0))) 0)2]. Then, since the output of the density ratio function f(x) o(x) @ 2 1/8 for any E X and θ and the boundedness of the input feature [xx(x]] S R, we have (2T,, x 3²2 Ia for any 0 E O. Then, the loss function is a smooth function. Besides, under the regularity condition Es, [xx") > aTa of the initial data and again the boundedness of t
and [(((x)) < R, the loss function is also a strongly convex function by T x a))S) Ta, which indicates the expconcavity of the loss function.
E
Technical Lemmas
This section presents several useful technical lemmas used in the proof.
39

---

Lemma 16. For any a, b E R we have (a b) x 2(aa + bbb"), where any matrix
A, B E Raxd A x B indicates A is positive semi-definite matrix.
Proof. For any x E Rd, (2(aa +bb ) [
(a+bb
x (aa ( +bb -ab -abT-ba T) "x
=x ((a (a - b) x 2 0, which completes the proof.
Lemma 17 (Theorem 4 of [68]). Let {Z, 2::12 1} be a martingale difference with the filtration
= (FF 2 1} and suppose Z,I I R for all i 2 1. Then, for any 5 (0, 1). 0, with probability at least 8.
Σ 2
S r
Σ i=1
1
2
Σ
Fi-1l
+ log r
V2l + R
+ log
8²
40


Reviews:
[{"review_id": "4AGVcoPcC8", "reviewer": "Reviewer_ZW3t", "summary": "This paper focuses on deriving theoretical bounds for online density ratio when there exists continuous covariate shift. The formulation is based on the importance-weighted empirical risk minimization, which is a conventional one for covariate shift adaptation. The paper chooses the Bregman Divergence Density Ratio Matching as the method and tries to bound the regret of the to a dynamically changing optimal density ratio. The results are first established for a general convex function class and then instantiated to a logistic regression model. The online ensemble method proposed mimics the previous continuous label shift work. Experiments are conducted on four different synthetic shift patterns and mint/cifar datasets.\n\n\n\n\n\n\n", "questions": "Questions:\n\nIt would be nice to see different shift change patterns and how they affect the learning results. But it seems the errors are averaged before showing? Figure 2 only shows different methods but covers 4 kinds of shifts? \n\n", "limitations": "There can be more discussions about limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Pro:\n\nThe paper studies an important problem, is very clearly written, and has solid results.\n", "weaknesses": "Con:\nI am not sure how much the first part of the analysis adds to our knowledge about the continuous covariate shift. This is maybe my bias. To my understanding, if we are in this kind of online learning scenario (shift is changing continuously), the minimization of the cumulative dynamic regret is a very straightforward choice. The question is how to minimize it and whether the theory guides the algorithm design. So, bounding the empirical estimation error using the approximated cumulated regret (theorem 1) is not very informative to me. \n\nAlso, the paper shows that many density estimator function satisfies the assumption and can achieve the bounds. So the main novel part of the proposed methodology seems to be the twist to the FLH algorithm?\n\nTheoretically, even though it is nice to see a general and relatively standard algorithm can achieve the minimax optimal guarantee for the online density ratio estimation under continuous covariate shift, the theoretical contribution seems to be a bit limited: the high probability result (instead of the expected), and the greatly simplified analysis. \n\nThe experimental results can be presented in a better way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed comments. In the following, we will first highlight the contribution of our work (Q1 and Q2) and then address your concern about the experiments (Q3). We will improve our paper according to your comments.\n\n---\n\n**Q1：**“I am not sure how much the first part of the analysis adds to our knowledge about the continuous covariate shift…”\n\n**A1:**  While the conversion from density ratio estimation to regret minimization might appear intuitive (for those who are very familiar with both IW-ERM and density ratio estimation), we believe our first part of the analysis is *still novel and interesting to the community*, given that the study presents the **first theoretically grounded framework** for the continuous covariate shift problem.\n\nWe emphasize the contribution of our framework through the following two points:\n\n- **Novel framework:** It is noteworthy to mention that existing approaches (e.g., [18], the closest work to ours proposed for continuous label shift) *cannot be applied to the continuous covariate shift problem*.  As discussed in line 63-67, the previous work typically follows the framework of first constructing an unbiased risk estimator $\\hat{R}_t(\\mathbf{w})$  and then conducting online optimization over $\\hat{R}_t(\\mathbf{\\mathbf{w}})$ to learn the predictor. However, the construction of $\\hat{R}_t(\\mathbf{w})$ relies on the unbiasedness of the importance weight function such that that $\\mathbb{E}[\\hat{r}_t] = r_t$, which is hard to satisfy in the continuous covariate shift problem (e.g.,  $\\mathbb{E}[\\hat{r}_t] \\neq r_t$ in Example 1). The first part of our analysis provides us a novel framework to handle continuous covariate shift.\n\n- **Flexibility:** Our framework is very flexible and holds the potential to serve as a principled way to manage more general continuous distribution shift scenarios. For instance, applying our framework to the continuous label shift problem immediately yields a new approach that *does not require the construction of an unbiased estimator*. Besides, with the disentanglement of predictor training and the IW estimation process, our framework supports the use of more complex hypotheses to train the predictor $\\mathbf{w}$, while the model used in [18] is limited to a linear model.\n\nWe thank the reviewer for the comments. In the next version, we will further emphasize the novelty and flexibility of our framework for the continuous covariate shift problem.\n\n---\n\n**Q2:** the theoretical contribution seems to be a bit limited: the high probability result (instead of the expected), and the greatly simplified analysis.\n\n**A2:** We respectfully disagree with the comments and would like to take this opportunity to emphasize our contributions in the regret analysis part.\n\n- First of all, we would like to highlight that the performance measure we investigate serves as an intermediate case between worst-case dynamic regret and universal dynamic regret as detailed in lines 750-765, Appendix B.1. The intermediated regret receives **less attention in standard OCO literature**, but is very **importance for the continuous distribution shift problem.** Using the previous result on universal dynamic regret [19] in a black-box way can only imply an expected bound. In contrast, We contribute to provide a high-probability bound with greatly simplified analysis (without involving KKT conditions) for this less-explored yet practically significant intermediate setting.\n- Furthermore, our high-probability bound is obtained **non-trivially**. As outlined in lines 766-783, Appendix B.1, we strategically modify the Hedge algorithm into Adapt-ML-Prod. This alteration enables us to effectively control the generalization gap between $\\hat{L}_t$ and $\\tilde{L}_t$ by leveraging the negative term introduced by the exp-concavity of the loss function. Additionally, while the primary focus of this paper is on the continuous covariate shift problem, our simplified analysis is also applicable for general OCO purposes when the minimizers lie in the interior of the decision set. This approach can be of independent interest for other online learning problems.\n\nDue to page limits, we have to place much of the content in the appendix (especially the dynamic regret discussion in Appendix B.1). However, we greatly value your comments and will carefully revise the paper, making sure to emphasize those points more clearly in the main text.\n\n---\n\n**Q3**: It would be nice to see different shift change patterns and how they affect the learning results. But it seems the errors are averaged before showing? Figure 2 only shows different methods but covers 4 kinds of shifts?\n\n**A3**: We have detailed the performance of all contenders across four different types of distribution shifts in Tables 1, 2, and 3. The results show that our algorithm can adapt to different kinds of shifts. Regrettably, due to space limitations, we have to place these results in Appendix A.1 for this version. In the next version, we will include some of these empirical findings within the main text. We believe this will be quite feasible, especially considering that an additional page is permitted in the camera-ready version. Thank you!"}, {"review_id": "XBMtBAajaK", "reviewer": "Reviewer_UHuD", "summary": "This work studies the continuous covariate shift problem, where there exists an initial labelled dataset and in every subsequent round, a new unlabelled dataset is revealed. One needs to adapt the model for every round to achieve good performance. The paper uses importance-weighted ERM where the weights are estimated based on Bregman divergence minimization (Sec.3.3) and online ensemble (Sec.4.1). Theoretical analysis shows that the estimation has a linear dynamic regret (Theorem 2) and corresponding IWERM has an average excess risk that depends on problem instances (Theorem 3). Empirical studies on synthetic and real-world data show that the proposed method can outperform several alternatives.", "questions": "Q1: Are there any possible ways to extend the current work beyond linear models?\n\nQ2: How are the images being sampled for the Yearbook dataset?", "limitations": "The assumption of using linear models should be explicitly mentioned.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Clear writing and easy-to-follow presentation\n- Strong theoretical guarantees on both the ratio function (Theorem 2) and the learned model (Theorem 3)\n- Convincing empirical demonstrations on both synthetic and real-world datasets", "weaknesses": "- The algorithm and analysis rely on the assumption of using linear prediction models (see, e.g., Eq.(2) where the prediction is linear in w). Linear models are hardly sufficient in many cases, and more powerful models are needed.\n- The work of Baby et al (2023), albeit very recent, should be discussed as it achieves a similar bound to the current work in a different setting.\n- Baby, D., Garg, S., Yen, T.C., Balakrishnan, S., Lipton, Z.C. and Wang, Y.X., 2023. Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms. *arXiv preprint arXiv:2305.19570*.\n- A somewhat minor point to mention is that in the experiment, the description of the Yearbook dataset is not very clear. The appendix only mentions 10 images per round, but it remains unclear how the images are sequentially sampled.\n\nSome minor comments\n- R_t should be defined explicitly after Eq.(1) to avoid confusion (since it is the population version, different from (2), the empirical version)\n- L173: Ref [37] doesn’t mention UKL and ref [25] is KLIEP instead of KLLEP\n- L262: latter -> later\n- L305: minimiers -> minimizers\n- L336: KEIEP -> KLIEP", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your great appreciation and bringing the concurrent work to us! In the following, we will address your questions. We will further improve the paper according to your suggestions.\n\n---\n\n**Q1:** Are there any possible ways to extend the current work beyond linear models.\n\n**A1**: We believe it is quite feasible to extend the current work beyond linear models. Our algorithm consists of two integral components: IWERM for predictor training and an online ensemble for density ratio estimation.\n\n- **For the predictor training part,** since this is an ERM-based method, we can extend our approach to learn within a more complex hypothesis space beyond the linear class, as long as Equation (2) can be minimized.\n- **For the density ratio estimation part,** if theoretical guarantees are not a primary concern, our ensemble algorithm can assuredly be extended to learn with more intricate models, such as deep neural networks.  When considering theoretical guarantees, the extension is not as straightforward, given that our method is based on the online convex optimization framework.  However, we believe there are many viable opportunities. For instance, Example 1 demonstrates that our model can already be implemented using a generalized linear model. Besides, it is feasible to extend our online ensemble framework to learn within the Reproducing Kernel Hilbert Space (RKHS), by leveraging the recent advances in online kernel learning [Calandriello et al., 2017; Zhang et al., 2019]. Furthermore, for more complex models like DNNs, although analyzing the nonlinear neural networks is always challenging, it could be an intriguing direction to consider combining the neural tangent kernel theory into the online learning process.\n\nThank you for raising this point. We will add more discussion in the next version!\n\nReference:\n\n[1] Daniele Calandriello, Alessandro Lazaric, and Michal Valko. Efficient second-order online kernel learning with adaptive embedding. In NeurIPS 2017.\n\n[2] Xiao Zhang and Shizhong Liao. Incremental randomized sketching for online kernel learning. In ICML 2019.\n\n---\n\n**Q2**: about the online label shift paper from Baby et al., 2023\n\n**A2:** Thank you for bringing the concurrent paper on the online label shift to us. We will add a discussion to the paper in the next version.\n\n---\n\n**Q3:** How are the images being sampled for the Yearbook dataset?\n\n**A3:** We generate the unlabeled data stream from the Yearbook dataset based on the inherent timestamps. Within the Yearbook dataset, each image is associated with a specific year. We meticulously reorganized the data to align with the chronological sequence of image years, introducing controlled randomness among images from the same year. Based on this process, we can generate coherent, sequential data that faithfully represents the passage of time with natural distribution shifts.\n\nWe will provide a more detailed description of the yearbook dataset in the revision. Many thanks!\n"}, {"review_id": "q7nCr4KXeV", "reviewer": "Reviewer_Ls7D", "summary": "This paper proposes an online density ratio estimation method to adaptively train a predictor in the scenario of continuous covariate shift. The proposed method estimates the density ratio between the training and testing distributions using a small number of unlabelled samples and updates the predictor using a weighted empirical risk minimisation algorithm. The paper provides a clear and comprehensive explanation of the problem of continuous covariate shift and the challenges it poses. The paper also provides a thorough review of related work and explains how the proposed method builds on and improves existing methods. The authors also give a dynamic regret bound, which finally leads to an excess risk guarantee for the predictor. The regret bound is minimised by designing an online optimisation process to minimise the dynamic regret defined over the observed loss. The paper explains how to optimise the dynamic regret with the online ensemble framework developed in recent studies of non-stationary online convex optimisation. The proposed method is validated through empirical results on synthetic and real-world datasets, demonstrating its effectiveness compared to other algorithms.\n\nOverall the paper appears technically sound, is easy to follow, and gives theoretical guarantees. The paper is less strong from the empirical perspective. Further, the setting is a little esoteric (offline training followed by online adaptation for models where density ratios can be used), and may be of limited appeal to a wider audience.\n\n----\n\nPost rebuttal increasing my score from 6 to 7", "questions": "How sensitive is the method to the intervals in the ensemble members?\n\nHow crucial is the ensemble to the method overall?\n\nAm I right in thinking that the bound does not take account for the presence of the ensemble. Does this mean that the bound actually holds for the algorithm as employed in experiments?\n\nCould you plot the bound for one of the synthetic examples to show how tight it is?", "limitations": "The authors did not address limitations or potential negative social impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Formulating the problem using the Bregman divergence was a useful tool to be able to generalise some existing methods, and also unlocked the analysis that follows. \n\nDisentangling the model training and importance weight estimation also allowed for adaptation to the continuous shift setting and abiility to change importance weight estimators.", "weaknesses": "In terms of empirical study, this is limited to a study using synthetic data, and a small study on the yearbook dataset. For the synthetic scenario, the nature of the shift - sinusoidal and square waves altering a convex combination of distributions for the first two, then linear and “Ber” (which is not fully described in the main text, but is samples from a Bernoulli distribution) seem rather simplistic and artificial. For the single real world experiment, it’s not clear how the hyperparameter settings for the various methods were chosen, so it’s hard to know if this result is cherry-picked or robust. \n\nAnother thing that’s not clear is whether the intervals chosen for the ensemble members match up with the period of change in the synthetic experiments. If they do, it’s not a surprise that they do well, but would require knowledge ahead of time. \n\nFigures 2-5 are extremely small and hard to read when printed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments. We will address your questions below and improve the paper according to your suggestions. To better present additional experimental results, we include them in a PDF attached with the global response.\n\n---\n\n**Q1:** empirical study is limited to a study using synthetic data, and a small study on the yearbook\n\n**A1:** We understand the reviewer's concern regarding the distribution shift generating process and scale-up issue to large data in experiments. However, we would note that the main contribution of this work is to propose the **first theoretically grounded solution** for continuous distribution shift problem. Our experiments are designed to verify the effectiveness of the method, particularly its ability to reuse historical information properly.\n\nOur experimental design follows the **same** settings used in existing works on continuous label shift [1,2], where $\\mathcal{D}_t$ is taken as a mixture of two distributions with different shift patterns. We also follow the convention to conduct experiments in three parts: **(1) synthetic data**, to provide controlled illustrations; **(2) four benchmark datasets**, to enable comparative evaluation (Regrettably, the results are reported in Tables 1 and 2 in Appendix A due to limited space); and **(3) real-world scenarios**, to demonstrate real-life applicability. While we acknowledge that more extensive real-world validation would be ideal, we believe that the experiments conducted have already shown the effectiveness of our method and supported the theoretical findings. In the future, we will find more real-world scenarios satisfying covariate shift assumptions and explore further results.\n\n[1]  Online adaptation to label distribution shift. NeurIPS'21\n\n[2]  Adapting to online label shift with provable guarantees. NeurIPS'22\n\n---\n\n**Q2:** hyperparameter settings for the various methods\n\n**A2:** For each individual algorithm, we use **the same rule in all experiments** to select the parameters.\n\n- For the contenders (DANN, KMM, KLIEP, and uLSIF), the parameters are set to the default settings as detailed in the corresponding ADAPT python package.\n\n- As for our algorithm (Accous), we provide detailed parameter configurations in lines 670-688, Appendix A.2. Specifically, we need to specify the parameters $R$ and $S$ for the logistic regression. Here, $R$ is set as the maximum feature norm in the offline data. Meanwhile, $S$ is the maximum norm of density functions; we set it as $S = d/2$, where $d$ is the dimension of the feature. OLRE uses the same parameter configuration as Accous.\n\nIn the revision, we will include the parameter setup in the main text for clearer accessibility. Thanks!\n\n---\n\n**Q3:** Figures 2-5 are extremely small\n\n**A3:**  Thanks for the comment. We will enlarge the figures to enhance readability in the revision.\n\n---\n\n**Q4:** whether the intervals chosen for the ensemble members match up with the period of change\n\n**A4:** In all performance comparison experiments, both on synthetic (Figure 2&4) and benchmark data (Table 1&2), the distribution change period **does not align with** the intervals of the ensemble members. These intervals are determined by the theoretical guidance, i.e., $|I_k| = 2^k$. By contrast, the period of distribution change is set as $M = \\sqrt{T} = 100$ for $T =10000$, as mentioned in lines 612-614, Appendix A.\n\n**Figure A** in the PDF reports the additional results for the weight assign experiment (Figure 3 in the paper) in the case where the ensemble member interval does not match the shift period $M$. The results show our method can still assign larger weights to the \"right'' ensemble members whose interval lengths are close to $M$.\n\n---\n\n**Q5:** How sensitive is the method to the intervals in the ensemble members?\n\n**A5:** We conducted additional experiments to investigate the sensitivity of ensemble members' intervals length, increasing them by factors of 3 and 5, i.e., $\\vert I_k\\vert = 3^k$ and $\\vert I_k\\vert = 5^k$. The results, presented in **Table A** of the PDF, show that our algorithm is generally robust to variations in the interval length.\n\n---\n\n**Q6:** How crucial is the ensemble to the method overall?\n\n**A6:** The ensemble structure is the core component to ensure our method's adaptivity. Intuitively, one of the main challenges of the continuous covariate shift is the unknown shift intensity $V_T$. To address the problem, we maintain multiple ensemble members to account for possible shift intensities of the environments and employ a meta-algorithm to combine them. The intuition is **supported by our theoretical analysis**, as shown by Lemma 10 in Appendix D.3, the ensemble structure ensures us to track the best ensemble members on each interval, which finally leads to the dynamic regret bound. **From an empirical standpoint,** Figure 3 further shows the importance of our ensemble structure, illustrating how it helps to selectively reuse the right amount of historical information according to the (unknown) shift intensity.\n\n---\n\n**Q7:** ...the bound does not take account for the presence of the ensemble? \n\n**A7:** Our bound explicitly accounts for the presence of ensemble structure, encompassing both the meta-algorithm and the ensemble members with interval schedule  $|I_k| = 2^k$. As discussed in Q6, the ensemble structure is the core component to achieve our theoretical guarantees (Theorem 2&3). \n\n---\n\n**Q8:** plot bound for one of the synthetic examples to show how tight it is\n\n**A8:** Thank you for the comment. We have provided a detailed discussion about the tightness of our results in lines 311-321, with further details in Appendix D.6. From a theoretical view, we show that the rate can hardly be improved, even if one can receive labels of the test stream after prediction. We further conducted experiments to show the consistency between our theory and empirical results. Please refer to **Figure** **B** in the PDF for more details. Thanks!"}, {"review_id": "iK25fnTGT2", "reviewer": "Reviewer_KTsd", "summary": "This work introduced an online density ratio estimation method that can adaptively update the model to minimize the risk accumulated over time in the continuous covariate shift scenario. This method is able to estimate density ratios between test and training samples when the test set is varying over time. Only a few unlabeled samples are required at each time. A theoretical analysis of the regret bound of the density ratio estimator is provided.", "questions": "I understand covariate shift is a well-established research area but the assumption of covariate shift (p(y|x) not change) is quite strong, so how can we verify or guarantee this assumption is valid in a real-world problem? ", "limitations": "Since this method is for continuous covariate shift, the inherent limitation would be the assumption of covariate shift.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written with clear justification and useful theoretical analysis. The proposed method relaxes the requirement of unbiasedness of prior work and does not need a large amount of unlabeled data at each time step. The authors also proved the dynamic regret bound of the density ratio estimator. The experiments demonstrate the effectiveness of the proposed method. ", "weaknesses": "I don't have many complaints about this paper. One weakness is that some important experimental results are in the appendix which is not reasonable as the appendix is optional to read by reviewers. I understand the page limitation but I would suggest moving some preliminary content to the appendix instead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your great appreciation for our work and the helpful comments! In the following, we will address your questions. We will further improve the paper according to your suggestions.\n\n---\n**Q1:** important experimental results are in the appendix which is not reasonable as the appendix is optional to read by reviewers\n\n**A1:** Many thanks for your careful review and constructive comments. In the next version, we will try to move the empirical results into the main text. We believe this is very feasible, given that an additional page is allowed in the camera-ready version. Thanks!\n\n---\n\n**Q2:** but the assumption of covariate shift (p(y|x) not change) is quite strong, how can we verify or guarantee this assumption is valid in a real-world problem?\n\n**A2:**  We appreciate your insightful comment on the covariate shift condition and acknowledge that it is somewhat a strong assumption. However, it is important to note that the unsupervised distribution shift adaptation problem is inherently challenging, and it is generally hard to perform the adaptation without any assumptions. The covariate shift condition is one of the most fundamental assumptions in the study of learning with distribution shift, which has also been successfully employed in many real-world applications (e.g. [8,9,10]).\n\nThere are several possible directions to relax the requirement on the covariate shift assumption. When no label information about the test distribution is available, we could explore more complex modeling of the distribution shift, such as considering the case where both covariates and labels shift (Chen et al., 2022). Another interesting direction is to study how to efficiently test the covariate shift assumption with limited labeled data from the test distribution, particularly in the continuous shift setting. Our study for the basic covariate shift setting may serve as a foundational step toward addressing more complex real-world distribution shift cases.\n\nThank you for the comments; we will include a more detailed discussion about potential ways to generalize the covariate shift assumption in the next version.\n\n**Ref**: Chen et al. Estimating and Explaining Model Performance When Both Covariates and Labels Shift. In NeurIPS 2022.\n"}]

Author rebuttal:

We sincerely appreciate insightful comments and the positive feedback from all reviewers for this paper. In the rebuttal period, we conducted additional experiments to further support our claim (particularly to address the concerns from Review Ls7D), as presented in the attached PDF file.  The experimental setup and results are listed as follows. To provide a better readability of the results, we have also included the text in the PDF files. Thanks!

---

**Experiment Setup for Figure A.** In response to Q4 (Reviewer Ls7D), we conduct weight assignment experiments in the case where the interval lengths of ensemble members **do not match** the period of distribution shift. The experimental setup and performance measure is the same as that in Figure 3 except that the distribution shift period is changed to $M = 10, 50, 100, 200, 400, 800$. 

**Experiment Result for Figure A.** Figure A shows that our meta-algorithm can still assign larger weight to the "right'' ensemble members whose interval length is close to the distribution shift period ($M$) even they are not exactly matched.

---

**Experiment Setup for Table A.** In response to Q5 (Reviewer Ls7D), we provide the performance comparison on the synthetic dataset. The experimental setup and measure is the same as that in Figure 1 except we additionally report the performance of Accous when the interval length of the ensemble members are increased by the factor of 3 and 5, i.e., $\vert I_k\vert = 3^k$ and $\vert I_k\vert = 5^k$, respectively.

**Experiment Result for Table A.** Table A shows the averaged error over $T=10000$ iterations. The results show that our method is generally robust to the interval lengths of ensemble members.

---

**Experiment Setup for Figure B.** In response to Q8 (Reviewer Ls7D), we empirically plot the order of the averaged excess risk suffered by our algorithm and compare it with the result established in Theorem 3. We conduct experiments on the synthetic dataset with the $\texttt{Lin}$ shift ($V_t = \Theta(1)$). To empirically measure the order of the averaged excess risk, we introduce the **"risk ratio''** $\rho_t(p)$, defined as $\rho_t(p) = \mathfrak{R}_t\times t^{p}$ for each time $t$, where $p\in(0,1)$ is a constant, and $\mathfrak{R}_t$ is the averaged excess risk at $t$. If the risk ratio of an algorithm decreases over the horizon, it means the convergence rate of risk is at least $O(T^{-p})$. Otherwise, the risk order is slower than $\Theta(T^{-p})$.

**Experiment Result for Figure B.** Figure B shows the risk ratio of our algorithm. As suggested by Theorem 3, the excess risk of our algorithm should converge at least at the rate of $O(T^{-1/3})$ for the $\texttt{Lin}$ shift. The green line shows that the risk ratio $\rho_t(1/3) = \mathfrak{R}_t \times T^{1/3}$ decreases in the $\texttt{Lin}$ shift scenario, indicating that the algorithm empirically attains a convergence rate faster than $O(T^{-1/3})$, which is consistent with our theory.

We further note that the risk ratio $\rho_t({7}/{12})$ (red line) also slightly decreases along the horizon, indicating that the algorithm converges slightly faster than $O(T^{-7/12})$ empirically, thus quicker than $O(T^{-1/3})$. However, this result does not imply that our bound is loose. Theorem 3 essentially provides the **worst-case guarantee**: our algorithm is guaranteed to attain the $O(T^{-1/3})$ rate in any pattern of distribution shift when $V_T = \Theta(1)$. But, it is also possible to achieve a better convergence rate in benign environments. In the online learning literature, a bound that can adapt to benign environments is known as a problem-dependent bound, which requires more advanced techniques to attain. In this paper, we primarily consider the worst-case guarantee and will address how to achieve the problem-dependent bound in future work.

Meta-review: This paper studies the problem of online learning in the presence of continuous covariance shifts. This paper was globally well received. Reviewer ZW3t had some concerns about how impactful the theoretical analysis was. The other reviewers mostly had questions about the experiments, concerns that were answered in the rebuttal. While I agree with reviewer ZW3t that some of the theoretical derivations are not the most impactful ones, I think that this work passes the bar for publication at Neurips. It is the first work providing a method for handling continuous covariance shifts with sound theoretical guarantees. The paper is well written, the work is novel and correct.
Decision: Accept (poster)