Adapting to Online Label Shift with Provable Guarantees
Authors: Yong Bai
Yu-Jie Zhang
Peng Zhao
Masashi Sugiyama
Zhi-Hua Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: online label shift
dynamic regret

Abstract: The standard supervised learning paradigm works effectively when training data shares the same distribution as the upcoming testing samples. However, this stationary assumption is often violated in real-world applications, especially when testing data appear in an online fashion. In this paper, we formulate and investigate the problem of \emph{online label shift} (OLaS): the learner trains an initial model from the labeled offline data and then deploys it to an unlabeled online environment where the underlying label distribution changes over time but the label-conditional density does not. The non-stationarity nature and the lack of supervision make the problem challenging to be tackled. To address the difficulty, we construct a new unbiased risk estimator that utilizes the unlabeled data, which exhibits many benign properties albeit with potential non-convexity. Building upon that, we propose novel online ensemble algorithms to deal with the non-stationarity of the environments. Our approach enjoys optimal \emph{dynamic regret}, indicating that the performance is competitive with a clairvoyant who knows the online environments in hindsight and then chooses the best decision for each round. The obtained dynamic regret bound scales with the intensity and pattern of label distribution shift, hence exhibiting the adaptivity in the OLaS problem. Extensive experiments are conducted to validate the effectiveness and support our theoretical findings.


Adapting to Online Label Shift with Provable Guarantees
Yong Bail,, Yu-Jie Zhang?: Peng Zhao', Masashi Sugiyama 3.2, Zhi-Hua Zhou"
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China 2 The University of Tokyo, Chiba, Japan
RIKEN AIP, Tokyo, Japan
Abstract
The standard supervised learning paradigm works effectively when training data shares the same distribution as the upcoming testing samples. However, this stationary assumption is often violated in real-world applications, especially when testing data appear in an online fashion. this paper, we formulate and investigate the problem of online label shift (OLaS): the learner trains initial model from the labeled offline data and then deploys it to an unlabeled online environment where the underlying label distribution changes over time but the label-conditional density does not. The non-stationarity nature and the lack of supervision make the problem challenging to be tackled. To address the difficulty, we construct a new unbiased risk estimator that utilizes the unlabeled data, which exhibits many benign properties albeit with potential non-convexity. Building upon that, we propose novel online ensemble algorithms to deal with the non-stationarity of the environments. Our approach enjoys optimal dynamic regret, indicating that the performance is competitive with clairvoyant who knows the online environments hindsight and then chooses the best decision for each round. The obtained dynamic regret bound scales with the intensity and pattern of label distribution shift, hence exhibiting the adaptivity the OLaS problem. Extensive experiments are conducted to validate the effectiveness and support our theoretical findings.
Introduction
One of the fundamental challenges for modern machine learning is the distribution shift [1, 2, 3, 4]. The learned model's testing performance would significantly drop when the distribution different from the initial training distribution. More severely, in many real-world applications, testing data often come in an online fashion after deploying the trained model such that the underlying distribution might continuously change over time. Hence, it is necessary develop learning methods to handle distribution shift online and open environments [5]. Another practical concern is the label scarcity issue in real tasks, particularly those tasks emerging in online scenarios. For example, in the species monitoring task [6, 7]. a learned model is deployed to detect species of wild animals. The data consist of received signals from sensors and hence of upcoming animals will change due to the variety of species across different geographic locations and seasons, and moreover, is hard to gather the labels of streaming data in time.
naturally in the streaming form. The data distribution
Motivated by the above real demand, this paper is concerned with the following problem: how to design algorithm that can adapt non-stationary environments with a few labeled data even unlabeled data observed at every time? In addition to getting empirical performance gain, the overall method is desired to have clear and strong theoretical guarantees. The problem is generally hard due
"Equal contribution. t Correspondence to: Zhi- Hua Zhou <zhouzh @ lamda.nju.cdu.cn>
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

to the non-stationarity of online environments and the lack of supervision. As such, we investigate a simplified case with focus on the specific change on the label distribution. We formalize the online label shift (OLaS) problem, which consists of two stages, including offline initialization and online adaptation. Specifically, the learner collects labeled samples drawn independently from the initial distribution (x. v) where x and denote the feature vector and its associated label, and trains an initial model following standard supervised learning methods. Subsequently, she needs to adapt it to an unknown non-stationary environment where the underlying label distributions change over time. Specifically, at time i, she receives a few unlabeled samples drawn from the current distribution (x(x) and uses them to update the model. In OLaS problems, the essential environment change happens on the label distribution (y) with the conditional [(x y) always remaining the same.
The label shift problem has been widely studied in the offline setting [8. 9. 10, 11, 12, 13, 14), but this is less explored in the more challenging online setup. One natural impulse is to handle OLaS by online learning techniques [15], but it is generally non-trivial due to the lack of supervision in the adaptation stage and also the stationttnn issue. Wu et al. [16] made the first such attempt for OLaS, where they constructed an unbiased risk estimator with the unlabeled data for model assessment and used online gradient descent for model updating. Let T denote the number of rounds. They proved an ((VT) regret bound, which measures the gap between the learner's 's decision and the best fixed decision in hindsight. However, in non-stationary environments, a single decision can hardly perform well all the time, which makes the guarantee less attractive for OLaS problems. Another technical caveat is that their theory relies functions, which was not verified strictly. In fact, this assumption can hardly be satisfied as an operation to take the argument of the maximum is involved in its formulation of the risk estimator.
vital assumption of the convexity of risk
In this paper, we aim to develop an algorithm for adapting to online label shift with provable guarantees. To this end, we first reframe the construction of the unbiased risk estimator via risk rewriting techniques and prove that the estimator still enjoys benign theoretical properties, albeit with a potential non-conver behavior. Second, to handle the non-stationarity of the online stream, instead of using traditional regret as the performance measure, we employ dynamic regret to guide the algorithm design, which ensures the online algorithm is competitive with clairvoyant who knows the online functions in hindsight and hence chooses the best decision of each round. To optimize such strengthened measure, we propose novel online ensemble algorithm building upon the risk estimator, consisting of a meta-algorithm running over a group of base-learners, each associated with a customized configuration. Our algorithm enjoys an OVV2/572/3 dynamic regret, where VT = - 1| 1 || measures the variation of label distributions, with ply, denoting the vector consisting of the class-prior probabilities at time l. Notably, the regret guarantee achieved by our algorithm is minimax optimal in terms of both number of rounds and non-stationarity measure, and importantly, our algorithm does not require the unknown class-prior variation Vr as the input.
Furthermore, for many situations where online label shift contains some patterns such as periodicity or gradual change behavior, we present an improved algorithm to exploit such structures and achieve provably better guarantees. The key idea is to leverage historical information to serve as a hint for online updates. We prove an (V GL/3T1/3) dynamic regret, where Gr measures the reusability of historical information that most (TT) while could be much smaller in benign environments.
As a benefit, the improved algorithm safeguards the OVV achieves great improvement in easier environments. Extensive experiments are conducted to evaluate our approach, which show the usefulness of meta-base structure in tackling non-stationarity and validate the effectiiveness of other adaptive components.
worst-case bound and meanwhile
Technical Contribution. Our method not a direct application of existing non-stationary online learning methods [17, 18, 19]. but rather requires in-depth technical innovations. First, the potentially non-convex risk estimator makes it hard to apply existing techniques of online convex optimization (OCO) [15], but fortunately, we prove the convexity of its expectation such that the OCO framework can still be used (see Remark 2). Second, to optimize the dynamic regret, we employ a meta-base structure to hedge the uncertainty of the unknown minimizer of the expected risk function each round and convert the variation of expected risk minimizers to the intensity of label distribution drifts, natural non-stationarity measure for the OLaS problem (see Remark 3). Third, earlier study showed adaptive dynamic regret bounds for convex and smooth functions [19], while the smoothness
We use OLaS instead of OLS, since OLS often refers to "ordinary least squares".

---

assumption can hardly be satisfied in our case. We remove such constraint by introducing an implicit update, which could be of independent interest for general OCO purposes (see Remark 4).
2 Problem Formulation
We focus on OLaS of multi-class classification with feature space X C R2 and label space y [K] _ {l..... K}. where d is the dimension and K is the number of classes. Below we formulate setups of two stages of OLaS (offline initialization and online adaptation).
Problem Setup. the offline initialization stage, the learner collects number of labeled samples denoted by So = {(x,, yn No, drawn from the distribution Do y) and then obtains a well- performed initial model fo X' + V. In the online adaptation stage, data come in the streaming form without labels. The current model is deployed to predict the labels of online data and also to evolve adaptively. Specifically, at each round t E [T', the learner receives small number of unlabeled data S. {x,, / drawn from the distribution (x))). The non-stationary nature indicates Dd DD in general for different i, t' E [7]. OLaS considers the simplified case that essential changes come from label distributions and there are new classes, formally described in the following condition.
Assumption (Online Label Shift). In the online label shift problem, the label distribution Dz changes over time while the class-con distribution (x y) identical throughout the process fort E {0, T Moreover, it holds that Do(y) > 0 for any y E y
Performance Measure. At round & [7]. the learner uses the information observed so far to make the prediction and also update the model w, E W, where W a convex decision set with diameter r - supw suPw, wwwwllw generalizes well on the underlying distribution D. Thus, the model's quality is evaluated by its risk defined as R((w) = (( [ [f[f(w, x)]. where ff W x X + RK is the predictive function and & R& K x y + R is any convex surrogate loss for classification such that {[ x), v) is convex in w. We introduce two constants, G - x www.wwwwwwwwee...
w'll2- The goal to ensure that the t-round model we
x), v)ll2 and B A xUPPxx.)eexxx [f([(w, x), u)1, as upper bounds of gradient norm and loss function value.
We use regret to examine the performance of online algorithms. In particular, dynamic regret [20, 17] is employed to compete the algorithm's 's performance with the best response at each round, defined as
Regi d
Σ (wo)) Σ min Re(w)=
Σ Re
Σ Ro(w)),
where w² E arg new Rs (w) is the model (or one of the models) with the best generalization ability on the distribution D.. Notably, it is known that sublinear dynamic regret is impossible in the worst case [17], so an upper bound of dynamic regret is desired to scale with a certain non-stationarity measure. A natural measure for OLaS would be the variation intensity of label distributions.
Remark 1 (Static regret vs. dynamic regret). The classic measure for online learning is static regret, defined as Reg² = Σn= (w,.):) - Σ Ra (w"), where w* E arg min wEW Et= (w())) is the best fixed model in hindsight. The measure was adopted in the prior work of OLaS [16]. However, the measure is not suitable for OLaS, because it is too optimistic to expect a single fixed model to behave well over the whole process in changing environments. By contrast, minimizing dynamic regret facilitates the online algorithm with more adaptivity and robustness to non-stationary environments.
3 Proposed Approach
This section presents our approach for the OLaS problem, including the algorithms and theoretical guarantees. In the following, we respectively address the two central challenges of OLaS: the lack of supervision and the non-stationarity of online environments.
3.1 Unbiased Risk Estimator for Online Convex Optimization
OCO is powerful and versatile framework for online learning problems, which enjoys both practical and theoretical appeals [21, 15]. Online Gradient Descent (OGD) [20] is one of the most fundamental
3

---

and powerful algorithms due to its light computational cost and sound regret guarantees. In the OLaS problem, recall that the learner's ss goal is obtain model sequence W enjoying low cumulative risk Σi Rw(w)). Thus, suppose the model's risk Re(w.) is known at each round; then OGD simply updates the model by Wx4-1 IIl [w, [.eR, where [[w[-]] denotes the projection onto W and 17 > 0 is the step size. It is well-known that OGD guarantees the regret bound Ei=1 R4 (we) minwew Ei= (w(w)= S O(VT) when risk function R₂ (e(w) is convex and step size is set as 1 - ( [15] (see Appendix B.1 for more details).
However, the expected risk function Ra R((w) is unknown in the current OLaS setup as it is defined over the underlying joint distribution [x y). More severely, the online environments in the OLaS problem are fully unlabeled, which poses great challenges to apply the OCO framework. Indeed, the lack of supervision makes it hard to empirically assess the expected risk, not to mention ensuring the convexity. In the following, we establish an unbiased estimator R, (w) with unlabeled data St, which exhibits nice properties such that the OCO framework is still applicable for our purpose.
Unbiased Estimator under Label Shift. Inspired by the progress in offline label shift [9, 12, 13], we establish an unbiased risk estimator in OLaS for Re(w) with unlabeled data St and offline data So by the risk rewriting technique. To this end, let yy, E AK denote the label distribution vector with the k-th entry [m é (y = k)., then we have the following decomposition for the true risk:
Re (w) & (x.g)) [[[ (w, x). Elemul R4 Elyll le (
(2)
where R2t (w) & Ex y= [e[ x), k)] is the risk of the model over the k-th label at round t. The second equality holds due to the law of total probability, and the third equality is by the label shift assumption that (x y) = Do y) for any i [Z]]. Since the labeled offline data So is always available, one can approximate R (w) (w) by its empirical version (w) with offline data So, where Ru (w)) A |st1 Exnest ((f(w, x,), 1e) and St is subset of Su containing all samples with label k.
Therefore, the task is now to estimate the label distribution vector My. To this end, we employ the Black Box Shift Estimation (BBSE) method [12] to construct an estimator via only offline data Su and unlabeled data S.. Specifically, we first use the initial offline model fo to predict over the unlabeled data St and get predictive labels De. and next estimate the label distribution via solving the crucial equation y. = 5o H'g. where jag. E AK is the distribution vector of the predictive labels Dr and Cf E IR K is the confusion matrix with [Cjolaj Ex y the classification rate that the initial model fo predicts samples from class as class j. We defer more details to Appendix B.2. As result, through risk rewriting and prior estimation, can construct the following estimator for the true risk Rg (w):
ii] being
K (w) = DIoo Pm.k (w),,
where C₁ and fig are empirical estimators of the confusion matrix and predictive label distribution vector using offline data So and unlabeled data St only. Our constructed risk estimator enjoys the unbiasedness property, which plays crucial role in the later algorithm design and thcoretical analysis.
Lemma 1. The estimator Re(w) in Eq. (3) is unbiased to Ru(w)= = E(x.u)-D,, [[[f(w, x), y)], i.e. Es,-D, (.s,,,,[R((]))) = (e(w)..or for any w W independent of the dataset S,, provided Coo invertible and the offline dataset So has sufficient samples such that C₁ = = and RA (w) =
=R R (w). Vk E y.
The proof of Lemma 1 is in Appendix D.I. Note that the sufficient sample assumption is introduced on offline data So simplify the presentation. Indeed, we can further show [RS.~D, RR (w)) [w,))-R,())
(w)) S O(V1/ ((l)) with high probability (details in Appendix D.2). Such an additional dependence on So also appears in the classical offline label shift [12, 13] and is negligible when a large number of offline data is collected at the initial stage. The requirement is easy to realize and will not trivialize the online adaptation. Another caveat is that storing all the offline data can be burdensome in resource- constrained learning scenarios, then one may use data sketching techniques like corsets [22, 23] or reduced kernel mean embedding [24, 25, 26] to further improve the storage complexity.

---

Remark 2 (Non-convexity issue). Our risk estimator (e(w) can be non-conver as the estimated label distribution (C,, Fa.l le might be negative in order to ensure the unbiasedness. Such non-convex behavior introduces great challenge for applying the OCO framework. Fortunately, owing to its unbiasedness and the fact that the expected risk R₂(w) is indeed convex, we can continue the following algorithm design and theoretical analysis building upon the constructed unbiased estimator.
OGD with Unbiased Estimator. Building upon the risk estimator in Eq. (3), we then deploy OGD and obtain our UOGD algorithm (abbreviated for "OGD with unbiased risk estimator"), namely,
W++1 = ww [w. - V Ry (w:)).
Despite the potential non-convexity of the risk estimator itself, we can still establish solid regret guarantees via the OCO framework due to the benign property that the risk estimator is unbiased and the expected risk indeed convex. For example, UOGD provably enjoys an (vTT) static regret. See the formal statement in Appendix D.3. We remark that our attained static regret already achieves the state-of of-tthe-rtt theoretical understanding of OLaS, in the sense that previously the same bound can be only achieved with an additional unrealistic convexity assumption imposed over the algorithm [16], which UOGD does not require. Concretely, Wu et al. [16] assumed that the risk estimator is convex (in expectation), which is hard to theoretically verify since the estimator approximates the 0/1 and involves an indicator function and an argmax operation due to the employed reweighting mechanism. By contrast, our estimator directly approximates the surrogate loss without reweighting and thus does not suffer from such limitations. Even if modifying their estimator to optimize surrogate loss, the reweighting mechanism makes their method still hardly suitable for the OCO framework. More details are in Appendix C.3. In a nutshell, our constructed risk estimator enjoys nice properties, which are indispensable for the algorithm design and theoretical analysis.
3.2 Adapting to Non-stationarity of Online Label Shift
So far, an O(vT) static regret has been established for OLaS; however, the guarantee is not appealing because static regret is not suitable for non-stationary online problems as discussed in Remark 1. We now introduce our method adapting to the non-stationarity with provable dynamic regret guarantees.
First, benefiting from the unbiasedness and expected convexity of our risk estimator, we prove that UOGD achieves a dynamic regret scaling with the label distribution drift Vr.
Theorem 1. Under the same assumptions as Lemma I, UOGD in Eq. (4) with step size nj satisfies
EE Regi s
(VTT)/m) (5)
where the constant 0 > 0 denotes the minimum singular value of the invertible confusion matrix Cjo- Moreover, VT = -T= M M
|| measures the intensity of the label distribution shift.
The proof of Theorem can be found in Appendix 1. a non-trivial way, and below we expand the technical innovations.
The dynamic regret guarantee is obtained in
Remark 3 (Non-stationarity measure for OLaS). For readers who are familiar with the literature, result is reminiscent of the existing dynamic regret bound in the OCO studies [17, 27] on the surface; however, our result exhibits fundamental differences. The key caveat is that in our case the comparator w at each round is not the minimizer of the online function. Specifically, the expected risk R2 is inaccessible, one has to work on the unbiased risk estimator Rg and requires optimizing the empirical dynamic regret Et Rg (w.) - Σ R,(w)) Importantly, w; E arg min R, (w) but w| & arg minlew (:(w)) in general. Although the empirical dynamic regret can be trivially bounded by Σ Re(w,) -
minwew Re(w), the bound will then be loose and related to temporal variation of risk estimators [17, 27]. making hard to establish relationship to the natural non-stationarity measure of OLaS: Vr.² 4 On the other hand, there exist studies benchmarking dynamic regret with other choices of comparators [20, 18], but the bounds scale with the consecutive variation
Ei= -
*Besbes et al. [17] also considered more general setting with noisy function value feedback. In such cases, the comparator is not the exact minimizer of the online function at each round, and their algorithm will require a periodical restart to deal with the non-stationarity. By contrast, does require the restart in the algorithm.
5

---

Algorithm ATLAS: base-algorithm
Algorithm ATL.SS: meta-algorithm
Input: step size T E H.
Input: step size pool H: learning rate= E
1: let W1,1 be any point in W
I: initialization: vi E [N = 1/N
2: for t t= 2 to 7 do
for t
T do
3: construct the risk estimator R as (3)
I. 3: receive {we.s f== from base-learners
4: update the model of base-learner by
4: update weight Pt AN according to
We,s = II [w,.1 7% V R...RR--.......
Pr,i X exp(-x > R.(w,.)). [N]
5: send Wi,; to the meta-algorithhe
5: predict final output We = -i= Wt,
6: end for
6: end for
of comparators 1t= - whose relation to Vr is also unclear. To address the difficulty, drawing inspiration from [28]. decompose the expected dynamic regret into two parts: (i) the analysis of the first part relies on an in-depth analysis of the empirical dynamic regret of UOGD to track specific sequence of diecewise-stational
comparators avoid undesired variation of comparators; and (ii) the analysis of the second part is directly conducted on the original risk functions attain a non-stationarity measure only related to the underlying label distribution shift.
From the upper bound in Eq. (5), we can observe that proper step size tuning is crucial. Specifically, it can be verified that when the environment is near-stationary (more precisely, Vr I O(T &)), simply choosing 77 (11 (T) ensures (VVT) dynamic regret, which is known to be minimax optimal even for the weaker measure of static regret [29]. Thus, in the following, we focus on the non-degenerated OLaS situation where VT 2 O(T=2) ), and then the dynamic regret upper bound can be further simplified as O11T + 1/n + (Vr7)// As a result, UOGD can attain an (VV T
dynamic regret by setting the step size optimally as O(T V ). According to the lower bound results of Besbes et al. [17], we know that UOGD with an optimal step size tuning ensures a minimax optimal dynamic regret guarantee, see more discussions on the minimax optimality in Appendix E.3.
However, the optimal step size 17" V(T crucially depends on the label distribution drift
V = =E My l1l which measures the non-stationarity and is unfortunately unknown to the learner. It worth emphasizing that the problem cannot be addressed by standard adaptive step size tuning mechanisms in online learning literature, such as the doubling trick [30] or self-confident tuning [31], in that the variation quantity Vr cannot be empirically evaluated as is defined over the underlying label distribution (y) inaccessible to the learner. Even diving into the analysis of Theorem 1, the adaptive tuning requires the knowledge of original risk functions {Re which are also unavailable. Intuitively, the hardness of such optimal step size tuning essentially comes from the uncertainty of the non-stationary label shifts.
To overcome the difficulty, inspired by recent advances in non-stationary online learning [18, 19]. we propose an online ensemble algorithm for the OLaS problem called ATLAS (Adapting To LAbel Shift). Specifically, to cope with the uncertainty in the optimal step size tuning, we first design pool of candidate step sizes denoted by H = (m)..... NTN) such that 7). can be well approximated by at least one of those candidates, which will be configured later and here N is the number of candidate step sizes. Then, ATLAS deploys a two-layer structure by maintaining group of each associated with a candidate step size from the pool 7. and then employs a meta-algorithm to track the best base-learner. The main procedures are presented in Algorithm 1 (base-algorithm) and Algorithm 2 (meta-algorithm), and we describe the details below.
We parallelly run group of instances of UOGD, each one is associated with candidate step size in the step size pool H. Formally, the i-th base-learner yields a sequence of base models (wr.) which is updated by W Tw (W:-1.5 1/ V 1 with E H.
Base-algorithm.
Meta-algorithm. The meta-algorithm aims combine all the learnerss decisions such that the final output is competitive with the decisions returned by the (unknown) base-learner associated with the best step size. To achieve this, employ weighted combination mechanism with the final model as w, = EN Wr,i. where P. E A is the weight vector with Pt.: denoting the weight of the i-th base-learner. We use the classic Hedge algorithm [32] to update the weight vector,
namely, Pt, exp > R. (w..))) where > 0 is the learning rate of the meta-algorithm

---

that can be simply set as ( (In / without dependence on label shift quantity. Intuitively, the meta-algorithm puts larger weights on base-learners with a smaller cumulative estimated risk so that the overall models (we) can be competitive to the base-learner with the best performance.
ATLAS enjoys the following dynamic regret guarantee with the proof in Appendix E.2.
Theorem 2. Set the step size pool us H {mh =
2GVTT 2 i E [N]], where
To
N = 1+ 2 loga(1 (1 + 2T)] is the number of base-leamers. ATLAS ensures that E[Reg?] 1 O ( VTH),, or simplified as O(V for non-degenerated cases of Vr 2 O(T
Theorem 2 shows that ATLAS enjoys the same dynamic regret as UOGD with the (unknown) optimal step size, but unknown -oatstaiionarity VT is no more required in advance. Algorithmically, our online method maintains N = Olog 7') base-learners to achieve optimal dynamic regret, which would be computationally acceptable given a logarithmic dependence on T.
3.3 More Adaptive Algorithm by Exploiting Label Shift Structures
ATLAS is equipped with a minimax optimal dynamic regret, which indicates that it can safeguard the optimal theoretical property in the worst case. Worst-case optimality serves as the istress-testing for the robustness to non-stationarity environments [33]. At the same time, more adaptive results beyond the worst-case analysis are also urgently desired, as improved performance is naturally expected in many easier situations when the shift admits specific patterns such as periodicity or gradual evolution.
To this end, we propose an improved algorithm called ATLAS-ADA with provably more adaptive guarantees. The key idea is to exploit the label shift patterns and reuse historical information to help the current online update [34]. We build on the framework of optimistic online learning [35, 36] by introducing a hint function He : W + IR to encode shift patterns from historical data, which serves estimation of the expected risk R2 (w:). Below, start with given hint function and describe the usage, and finally elaborate on how to design (-)-) guided by the theory.
Similar to ATLAS, the improved ATLAS-ADA also deploys a two-layer meta- base structure. The key difference lies in the usage of the hint function at both the base-level and meta-level.
algorihg. Besides the gradient descent step as did in ATLAS, another update step related to the hint function (-) is performed. Concretely, the i-th base-learner updates the parameters by
We,i = [w [ww]W.-..: - 1/s V R (w:-1.)),, We,1 = arg min 1/: H:)) + 1/2- ||w W.,s 11 (6) where W.,, is an intermediate output and Wa, is the final returned model. When H, = 0 (i.e., without hint function), the above two-step update simply degenerates to the same UOGD update in the base-learner of ATLAS by noting that W., We,s In the general H-(-) case, the second step in (6) is crucial and can be regarded as another descent towards the direction specified by the hint function. As result, this will reduce the regret whenever the hint function is set appropriately to approximate well the next-round risk function, which will be clear in the regret bound presented later.
Meta- Meta-algorithm. H-)-) also necessary to be considered in the update to achieve the adaptivity. To this end, we inject the hint function as the loss evaluation of the meta-al algoriigg,,,,m, and then the weight is updated by Pt. x exp (-e( Σ'= (w..)) + H, (ww.))) for all E [V], where is the learning rate that can be set properly without dependence on Vz. The key distinction to the meta-algorithm of ATLAS is the additional loss H, (w.,)) evaluated over the current local models {wr, I. by the hint function.
The meta- altorithg is used to track the best base-learner, and the hint function
The main procedures are presented in Algorithm 4 (base-algorithm)) and Algorithm 5 (meta-algorithhm) We have the following dynamic regret bound for ATLAS-ADA (proof in Appendix F.2).
Theorem 3. Suppose the hint function Hi, W + R is convex, satisfies maxwew woreew///// || HV ll2 S
maxwewll Ri (w) ||2. and is independent of current data Sy. Set the step size pool as H. = {n- =
La 22-1 i [N]] with N = + [ log, (3T + KT)KT)))) ATLAS-ADA ensures KT
EjRegt < O(V2L/3 G (1V/////////// G//3TT1/3), where Gr = ΣT E(supwew | Re (H((w)]3 [12) measures the reusability of historical information, depending on label shift putterns and hint function designs.
In the worst case, GT is at most O(T) given a bounded gradient norm (VH(()))ss and thus bound ATLAS. More
the bound presented in Theorem 3 safeguards the same
7

---

importantly, when the hint function H-)-) encodes beneficial information and is close to the risk function, the obtained bound can be substantially better than the minimax rate.
Remark 4 (Implicit update). Problem-dependent dynamic regret was first presented in [19] for convex and smooth functions. However, their result critically relied on the smoothness condition, which is not satisfied in our OLaS case. Our key technical innovation is the implicit update in the second step of (6). The previous method required the gradient-descent type update We, = we [ 7) (We-1,)),, which can be deemed as an approximated optimization over the linearized loss (VHr(W;-1,, hence called the "implicit" update [37, 38J. Albeit with slightly larger computational complexity (which will not be a barrier given a proper design of hint functions), our method enjoys the same dynamic regret without smoothness, which could be of independent interest for general OCO purposes.
w) By contrast, we directly updates over the original function Hd (y),).
Design of Hint Functions. The hint functions should minimize the reusability measure GT to sharpen the dynamic regret as suggested by Theorem 3. Recall that (.(w) Σ [ Thus, a natural construction is H,(w) =
RV (w). R2 (w) parametrized by hins priors hy E R which is used to estimate the class prior based on the past observed data {-- Then, Gr satisfies the bias- vtrianariance decomposition (with bias term Elllhy. My.112. and variance term Elll - 11]):
(hy, >
GT S KG2
E
1= E. [1hy. 1i 22KG2 Σ
2'
E [1l My. 1221 + [llpy. - pyy 12
Setting hy. = fhy, will make the upper bound tightest possible, though the underlying class prior My: not accessible in practice. So the design of the hint function is actually a task of approximating it with different parts of previous data guided by prior patterns. In the experiments, we design four hint functions by encoding different knowledge, including Forward Hint (Fwd), Window Hint (Win), Periodic Hint (Peri), and Online K.Maans Hint (OKM). More details are in Appendix F.I.
4 Experiments
In this section, we conduct extensive experiments to validate the effectiveness of the proposed methods (ATLAS and ATLAS-ADA) and justify the theoretical findings. We begin this section with a brief introduction to the experimental setups (more details are deferred to Appendix A) and then present empirical results on the synthetic and real-world data, respectively.
Experiments Setup. We compare seven algorithms in various experimental configurations. The contenders include baseline that predicts with the initial model directly (FIX), three OLaS algorithms proposed by the previous work [16] (ROGI) FTH, and FTFWH), and our proposals (UOGD, ATLAS,, and ATLAS-ADA) with the logistic regression model. Besides, we simulate four types of label shift on synthetic and benchmark data to capture different distribution change patterns. Two of them, including Sine Shift (2Wl) and Square Shift (IIII) change in a periodic pattern. The other two have no periodic structure but are introduced to capture different shift intensities. The underlying distribution changes slowly in the Linear Shift (--) while changes fast in Bernoulli Shift (IIII). We repeat all experiments for five times and evaluate the contenders by the average
error T D 1ST
S. m= [f (w,x,)= F yn] over = 10, 000 rounds.
4.1 Illustrations on Synthetic Data
This subsection first compares all contenders on the synthetic data. Then, we further illustrate the effectiveness of our proposal by closer look at the two key components, including meta-base structure for step size search and a hint function for historical information reuse.
Overall Performance Comparison. Table 1 compares ATLAS with other methods when N, 100 samples are received at every iteration. Basically, FIX is inferior to the online methods, which shows the necessity of designing online algorithms for the OLaS problem. Besides, UOGD outperforms ROGD, the OGD algorithm running with the risk estimator proposed by [16]. The comparison demonstrates the empirical superiority of our estimator besides its benign theoretical properties. Moreover, the ATLAS surpasses almost all other methods in the four shift patterns. In particular, achieves a significant advantage over UOGD (with step size 1j = ( when the environments change relatively fast (Squ, Sin, and Ber). The results justify theoretical finding that the small
8

---

Table 1: Average error (%) for different algorithms under various simulated shifts for the synthetic data. The best algorithms are emphasized bold (paired (-test at a 5% confidence level).
Step Size Ag):
1.6
3.2
12.0
20.3
Squ
Sin
FIX
7.87-0003
7.87+00.22
7.34:00.3
7.79:-0.02
FTH
4.70-0002
6.50:10.01
6.3610.03
6.60100011
(a) Linear shift
(b) Bernoulli shift
FIFWH
5.27=0.02
6.52=0.01
6.3620.02
6.60:0001
ROGD
6.08=0011
7.11+0.01
6.87+0.02
6.40=0.01
Figure 1: Weight assigned of the ATLAS algorithm
LOGD
5.35-0002
6.17400.1
6.37-00.11
5.46+-0.05
for each step size along the learning process. Different colors are used to indicate different step sizes.
ATLAS
5,4400022
4.27=0.02
5.75+0.01
4.04:0.07
Table 2: Average error (%) for ATLAS-ADA with four hint functions under different sample sizes. The best one is emphasized in bold. Besides, indicates a better result than ATLAS without hint (None).
Bhiift Type
Sample Size:
Sample Sire: 10
Sample Size: 100
Nows
Win
Poi
Food
OKM
None
Wie
Pvvl
Fuo
OKM
Nour
Win
Peri
Fwd
OKM
Lin
1. 0.21
6.28
1. 0.26
1. 0.29
1. 0.33
10.31
1: 0.04
5.61
1 0.001
0.03
1 0.05
1. 1.0.5
1. 0.02
5.44
1. 0.003
5.44
1. 1.0.0
5.38
1. 0.02
1. 0.03
5.45
6.03
5.83
5.27
5.88
5.07
4.59
4.69
3.85
3.72
3.91
4.27
4.68
3.39
* 3.33
. 3.46
Equ
+ 0.223
+ 0.244
+ 00220
+ -0.33
+0.35
+ 0.02
+ 0002
-004
+ +002
+ +0003
+ 0.02
+ 0.02
+ 0.03
+ 0.033
+ 0.04
6.90
6.588
6.59
5.25
6.12
5.99
5.83
5.88
5.36
5775
5.78
5.48
5.58
0.22
0.25
# 0.26
0.22
0.07
0.05
=005
-005
+004
0.01
* 0.01
* 0.00
# 0.01
0.00
Bor
1 0.09
5.55
1 0.11
5.42
1. 0.09
5.43
1 0.16
5.63
1 0.17
4.69
1 1.100
4.39
1 0.08
4.45
0.30
4.43
1 0.00
3,66
1 0.06
3.73
1 0.07
4.04
1 0.06
4.29
1 0.00
4.26
1 0.07
3.19
1 10111
3.45
step size O(T-1/3) suggested by the static regret analysis is unsuitable for the dynamic environments.
Our method can better adapt to the changing environments by enjoying the dynamic regret guarantees.
Effectiveness of Meta-Base Structure. One key component of our method is the meta-base structure address the statiiinonartt. To better illustrate its effectiveness, we visualize the weights Pt.: assigned for each base-learne, of ATLAS. As shown in Figure 5, the meta-algorithm can quickly assign larger weights to appropriate base-learners along the learning process. Specifically, Figure ((a) illustrates the case of slowly changing environments, where more weights are assigned to the base- learners with small step sizes. In the fast-changing case, see Figure ((b), larger step sizes are preferred. The results show that our algorithm can adaptively track the suitable step sizes according to the shift intensity of environments. Additional results for other shifts can be found in Figure 5.
Effectiveness of Using Hint Functions. Table 2 reports the performance of ATLAS-ADA with four different hint functions under sample sizes N₂ = 1, 10, and 100. All hint functions improve over vanilla ATLAS in most cases. When N₁ is reasonably large, the Fwd hint, performing transductive learning with current unlabeled data, achieves the best performance. While, the OKM hint, which learns previous patterns by online k-means, is the best choice for a small sample size case (N₂ = 1).
To illustrate how the hint function works, we further vary the buffer size of the Periodic Hint (Peri) on the Squ environment (III),, which shifts in a periodic length L = 40. As shown in Figure 2, when the buffer size matches the multiples of length L, Peri can significantly improve the vanilla ATLAS. Besides the improvement, our method is shown to achieve comparable performance with ATLAS even if the buffer size is misspecified. The result validates our theoretical guarantee of the safety of using hint functions (the readers can refer to the paragraph above Remark 4).
4.2 Comparisons on Real-world Data
We conduct experiments on real-world data, including six benchmark datasets (ArXiv, EuroSAT, MNIST, Fashion, 10, and CINIC10) and the SHI. dataset [39] for the real-life locomotion detection task. Table 3 reports the averaged error of different algorithms, which shows a similar tendency the results in the synthetic experiments. When the distribution changes rapidly (Ber), ATLAS and ATLAS-ADA outperform other contenders. Similar results are also observed in the Sine and Square shift, see Appendix A. for details. Even in a relatively stationary environment (Lin), our algorithms are comparable with the best algorithm (UOGD), which is specifically designed for stationary cases. The above results validate the adaptivity of the proposed algorithms.
Further, we highlight the results on the locomotion detection task. The task aims to distinguish six types of locomotion with sensor data from mobile phones. Figure 3(a) reports the averaged error of all contenders, which shows the superiority of our proposals ATLAS and ATI.AS-ADA (with the OKM hint) over the entire time horizons. In addition, to further validate the adaptivity of our algorithm

---

Table 3: Average error (%) of different algorithms on various real-world datasets (Lin and Ber). We report the mean and standard deviation five runs. The best algorithms are emphasized in bold. "*" indicates the algorithms that are significanty inferior ATLAS-ABE ADA by the paired 1-test at a 5% significance level. Here AT-ADA represents AILAS-ADA (with OKM). The online sample size is set as N: 10.
30.28
28.11
+3.00
21.28
28..0
10.07
1...88
100.1
1.0.20
10.11
10.09
1.009
10.200
100.13
10.19
10.11
10.68
10.70
10.69
EureSAT
14.06
11.16
9.78
12.36
7.04
7.19
7.13
14.12
10:48
10.50
6.99
6.91
20.09
200111
200122
2.3.16
20.11
20.10
10.11
10.13
10.00
10.08
20003
20.04
20.03
10.05
MNNSTT
100002
1.79
1.0.03
1.38
10.02
1.20
10.02
1.25
10.02
1.96
10.02
1,66
10.00
1,06
100.05
1.81
1.0.00
1.29
10.00
1.34
10.00
1:33
9 1.12
10002
10.02
188
10.02
1,43
Fashion
+ 11188
+0.04
+0.07
8.47
+0.06
7.84
+0.07
8.38
+0.08
7.55
+0.07
8.36
+0.08
3,04
11.85
+0.09
+-0.1
9.48
+0.10
8,99
+0.08
8:72
+0.12
8:23
+0.12
7.91
+0.12
7.09
CIFARIO
20.77
10.12
1.0.14
17.36
10.12
15.77
10.47
18.45
10.15
1554
10.11
15.77
10.14
15,62
10.12
20.82
17.06
10.14
10.15
16.96
10.13
17.66
10.29
15.33
14.95
10.30
10.29
14,90
CINICIO
33.9%
40.15
26.38
28.44
28.90
22663
25.85
+0.58
Averge Eree 30
05
t 8
ROC3 ATBASADA
Berscionn
SHR IntersyyllggV
Figure 2: Average error of Peri hint with different buffer sizes. ATLAS- ADA enjoys significant improvement with proper buffer sizes while still safeguarding similar performance ATI.AS even the size is misspecified.
(a) overall performance
(b) weight heatmap
Figure 3: (a) Overall performance comparison on the locomotion detection task. (b) The heatmap of the final round weights for each step size. A larger Vr implics a larger intensity of distribution shift. The darker color in the heatmap indicates the larger weight.
the underlying environment regardless of the fast slow changes, we simulate various shift intensities by sampling the original data with different frequencies. Figure 3(b) shows the weight assignment of ATLAS-ADA ADA for each step size in the final round. Our method automatically selects a larger step size for larger VT while tracking a small step size in a relatively static scenario.
5 Conclusion
This paper proposed algorithms for online label shift with provable guarantees. We constructed an unbiased risk estimator without using any supervision at test time. Then, we designed novel online ensemble algorithms that automatically adapt the non-stationary online label shift and enjoy problem-dependent dynamic regret. Our proposed ATLAS algorithm employed a meta-bas structure
to handle the non-stationarity and obtained an 22233) guarantee, and ATLAS-ADA further introduced hint functions to exploit the shift structure and obtained an improved (Vv3/////// guarantee. Extensive experiments validated the effectiveness of the proposed algorithms.
Our study serves as preliminary attempt to bridge the distribution change problem and online learning techniques by focusing on the label shift case. Considering more general distribution change setting is an important future direction. Besides, our current algorithm is designed for the most challenging unlabeled scenario, and is interesting to consider relaxed real-worll demand where few labels could be available in the learning process. Moreover, our obtained regret guarantees hold in expectation, and we will take high- brobhbrrbbbblityy bounds as the future work.
Acknowledgments
Yong Bai, Peng Zhao, and Zhi-Hua Zhou were supported by NSFC (61921006, 62206125). JiangsuSF (BK20220776), and Collaborative Innovation Center of Novel Software Technology and Industrializa- tion. Yu-Jie Zhang was supported by Todai Fellowship and the Institute for Al and Beyond, UTokyo. Masashi Sugiyama was supported by JST AIP Acceleration Research Grant Number JPMJCR20U3 and the Institute for Al and Beyond, U'Tokyo. Peng Zhao thanks Chen-Yo Yu Wei for discussions on the conversation between function variation and gradient variation. The authors also thank Ruíhan Wu, Yu- Yang Qian, and Dheeraj Baby for their helpful discussions.
10

---

References
[1] Joaquin Quionero- Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D. Lawrence. Dataset Shift in Machine Learning. The MIT Press, 2009.
[2] Masashi Sugiyama and Motoaki Kawanabe. Machine Learning in Non-stationary Environments: Introduction Covariate Shift Adaptation. The MIT Press, 2012.
[3] Thomas G. Dietterich. Steps toward robust artificial intelligence. Al Magazine, 38(3):3-24 2017.
[4] Yoshua Bengio, Yann Leeun, and Geoffrey Hinton. Deep learning for Al. Communication of ACM, 64(7):58-65, 2021.
[5] Zhi-Hua Zhou. Open-environment machine learning. National Science Review, 98): 123,
2022.
[6] Alexander Gómez-Villa Augusto Salazar, and Jesús Francisco Vargas-Bonilla. Towards au- tomatic wild animal monitoring: Identification of animal species in camera-trap images using very deep convolutional neural networks. Ecological Informatics, 41:24-32, 2017.
[7] Mohammad Sadegh Norouzzadeh, Anh Nguyen, Margaret Kosmala, Alexandra Swanson, Meredith Palmer, Craig Packer, and Jeff Clune, Automatically identifying, counting, and describing wild animals in camera-trap images with deep learning. Proceedings of the National 2018.
Academy of Sciences, (5(25))E5716-E55)
[8] Marco Saerens, Patrice Latinne, and Christine Decaestecker. Adjusting the outputs of a classifier to new priori probabilities: A simple procedure. Neural Computation, 14(1):21-4) 2002.
[9] Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In Proceedings of the 30th International Conference on Machine Learning (ICML), pages 819-827, 2013.
[10] Marthinus Christoffel du Plessis and Masashi Sugiyama. Semi-supervised learning of class class-prior balance under class- prior change by distribution matching. Neural Networks,
2014. [11] Tuan Duong Nguyen, Marthinus Christoffel du Plessis, and Masashi Sugiyama. Continuous target shift adaptation in supervised learning. In Proceedings of the 7th Asian Conference on Machine Learning (ACML), pages 285-300, 2015.
[12] 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-3136, 2018.
[13] Kamyar Azizzadenesheli, Anqi Liu, Fanny Yang. and Animashree Anandkumar, Regularized learning for domain adaptation under label shifts. In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
[14] Saurabh Garg, Yifan Wu, Sivaraman Balakrishnan, and Zachary C. Lipton. A unified view of label shift estimation. In Advances in Neural Information Processing Systems 33 (NeurIPS),
pages 3290-3300, 2020.
[15] Elad Hazan. Introduction Online Convex Optimization. Foundations and Trends in Optimiza- tion, 2(3-4):157-325, 2016.
[16] 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 11340-11351 2021.
[17] Omar Besbes, Yonatan Gur, and Assaf J. Zeevi. Non-stationary stochastic optimization. Opera- lions Research, 63(5): 1227-114222 2015.
[18] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 1330-1340, 2018.
[19] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hus Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages
15510-1252,, 2020.
[20] 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.
11

---

[21] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning. and Games. University Press. 2006.
Cambridge
[22] Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning. 1etiv::1703.0660 2017.
[23] Baharan Mirzasoleiman, Jeff A. Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 6950-6960, 2020.
[24] Xi-Zhu Wu, Wenkai Xu, Song Liu, and Zhi-Hua Zhou. Model reuse with reduced kernel mean embedding specification. IEEE Transactions on Knowledge and Data Engineering, 35:699-710, 2021.
[25] Yu-Jie Zhang, Yu-Hu Yan, Peng Zhao, and Zhi-Hua Zhou. Towards enabling learnware to handle unseen jobs. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAT), pages 10964-10972, 2021.
[26] Krikamol Muandet, Kenji Fukumizu, Bharath K. Sriperumbudur, and Bernhard Schölkopf. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends in Machine Learning, 10(1-2):1-141 2017.
[27] 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.
[28] Yu-Jie Zhang, Peng Zhao, and Zui-Hua Zhou. simple online algorithm for competing with dynamic comparators. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), pages 390-399, 2020.
[29] Jacob Abernethy, Peter L Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the 21st Annual Conference Learning Theory (COLT), pages 415-423, 2008.
[30] Nicolò Cesa- Bianchi,,, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How use expert advice. Journal of the ACM, 44(3):427-455, 1997.
[31] Peter Auer, Nicolò Cesa-Bianchi, and Claudio Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48-75, 2002.
[32] Yoav Freund and Robert E. Schapire. A decision-theon generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-13)
1997.
[33] Tim Roughgarden, editor. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020.
[34] Peng Zhao, Le-Wen Cai, and Zhi-Hua Zhou. Handling concept drift via model reuse. Machine Learning, 109(():533-566 2020.
[35] Chao-Kai Chiang, Tianbao Yang. Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Proceedings of the the 25th Conference On Learning Theory (COLT), pages 6.1 6.1200, 2012.
[36] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Conference On Learning Theory (COL.T), pages 993-1019, 2013.
[37] Brian Kulis and Peter L. Bartlett. Implicit online learning. In Proceedings of the 27th Interna- lional Conference on Machine Learning (ICML), pages 575-582, 2010
[38] Nicolò Campolongo and Francesco Orabona. Temporal variability implicit online learning. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 12377-12387,
2020.
[39] Hristijan Gjoreski, Mathias Ciliberto, Lin Wang, Francisco Javier Ordóñez Morales, Sami Mekki, Stefan Valentin, and Daniel Roggen. The university of Sussex-Huawei locomotion and transportation dataset for multimodal analytics with mobile devices. IEEE Access, 6: 42592-42604. 2018.
[40] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. DistiBERTT, a distilled version of BERT: smaller, faster, cheaper and lighter. arXiv.1910001108 2019.
12

---

[41] Patrick Helber, Benjamin Bischke, Andreas Dengel, and Damian Borth. Introducing ETroSAT: novel dataset and deep learning benchmark for land use and land cover classification. In Proceedings of the IEEE International Geoscience and Remote Sensing Symposium (IGARSS), pages 204-207, 2018.
[42] Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pages 770-778, 2016
[43] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-23244 1998.
[44] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNISTT: A novel image dataset for benchmarking machine learning algorithms. arXiv:1708.0711 2017.
[45] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[46] Luke Nicholas Darlow, Elliot J. Crowley, Antreas Antoniou, and Amos J. Storkey. CINIC-10 is not ImageNet or CIFAR-10. 1XXv:1810000500) 2018.
[47] Jia Deng. Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 255, 2009.
[48] Shai Shalev-Shwartz. Online Learning and Online Convex Optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
[49] Jacob D. Abernethy, Peter L. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal stragies and minimax lower bounds for online convex games. In Proceedings of the 21st Conference On Learning Theory (COLT), pages 415-424, 2008.
[50] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-199))) 2007.
[51] Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages
57-68. 2008.
[52] Gilles Blanchard, Gyemin Lee, and Clayton Scott. Semi-supervised novelty detection. Journal of Machine Learning Research, 11:2973-3009 2010.
[53] Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Class-prior estimation for learning from positive and unlabeled data. Machine Learning, 106(4):463-492. 2017.
[54] Harish G. Ramaswamy, Clayton Scott, and Ambuj Tewari. Mixture proportion estimation via kernel embeddings of distributions. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 2052-2060, 2016.
[55] Clayton Scott. A rate of convergence for mixture proportion estimation, with application to learning from noisy labels. In Proceedings of the 18th International Conference on Artificial Intelligence and Statisties (AISTATS), pages 838-846, 2015.
[56] Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. In Advances in Neural Information Processing Systems 27 (NeurIPS), pages 703-711, 2014.
[57] Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation for learning from positive and unlabeled data. In Proceedings of the 32nd International Conference on Machine Learning (ICML). pages 1386-1394, 2015.
[58] Yu-Jie Zhang, Peng Zhao, Lanjihong Ma, and Zhi-Hua Zhou. An unbiased risk estimator for learning with augmented classes. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 10247-10258, 2020.
[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, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Improved dynamic regret for non-degenerate functions. In Advance in Neural Information Processing Systems 30 (NIPS), pages 732-741, 2017.
13

---

[61] 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 8.
[62]
Dheeraj Baby and Yu- Yu-Xin Wang. Online forecasting of total-variation variation-bbundee sequences. In Advances in Neural Information Processing Systems 32 (NeurlPS), pages 11069-11079, 2019,
[63] Xi Chen, Yining Wang, and Yu-Xiang Wang. Non-stationary stochastic optimization under -apa--ariation measures. Operations Reseurch, 6756):1552-776,, 2019.
[64] Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. In Proceedingg of the 3rd Conference on Learning for Dynamics and Control (I,4DC), pages 48-59, 2021.
[65] 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 IEEE Conference on Decision and Control (CDC), pages 7195-7201, 2016.
[66] Lijun Zhang, Shiyin Lu, and Tianbao Yang. Minimizing dynamic regret and adaptive regret simultaneously. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 309-319, 2020.
[67] Ashok Cutkosky. Parameter-free, dynamic, and strongly-adaptive online learning. In Proceed- ings of the 37th International Conference on Machine Learning (ICML), pages 2250-2259) 2020.
[68] Peng Zhao, Yu-Jic Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non-stationarity; Problem-dependent dynamic regret for online convex optimization. 12.1:22.2.11368.. 2021.
[69] Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. Journal of Machine Learning Research, 22(125): 45, 2021.
[70] Dheeraj Baby and Yu- Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Proceedings of the 34th Annual Conference on Learning Theory (COLT), pages 359-409, 2021.
[71] Peng Zhao, Xiang Wang, and Zhi-Hua Zhou Non-stationary online learning with memory and non-stochastic control. In Proceedings of the 25th International Conference Artificial Intelligence and Statistics (AISTATS), pages 2101-2133, 2022.
[72] Lijun Zhang, Wei Jiang. Shiyin Lu, and Tianbao Yang. Revisiting smoothed online learning. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 13599-13612, 2021.
[73] Peng Zhao, Long-Fei Li, and Zhi-Hua Zhou. Dynamic regret of online markov decision processes. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
pages
[74] Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time- varying zero-sum games. In Proceedings of the 39th International Conference on Machine Learning (ICMI)). pages 26772-26808, 2022.
[75] Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. In Proceedings of the 35th Annual Conference on Learning Theory (COLT), pages 4160-4211, 2022.
[76] Joel A. Tropp. Usser-friendly tail bounds for sums of random matrices. Foundations of Compu- tational Mathematics, 12(4):389-4344 2012.
[77] Daniel J. Hsu, Sham M. Kakade, and Tong Zhang. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 1460) 1480, 2012.
[78] Teng Zhang, Peng Zhao, and Hai Jin. Optimal margin distribution learning in dynamic environ- ments. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 6821-6828, 2020.
[79] Shiji Zhou, Han Zhao, Shanghang Zhang, Lianzhe Wang, Heng Chang, Zhi Wang. and Wenwu Zhu. Online continual adaptation with active self-training. In Proceedings of the 25th In- lernational Conference on Artificial Intelligence and Statistics (AISTATS), pages 8852-8883, 2022.
[80] Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. Proceedings of the 3rd Conference on Learning for Dynamics and Control (L4DC), pages 48-59, 2021.
14

---

[81] Wesam Barbakh and Colin Fyfe. Online clustering algorithms. International Journal of Neural Systems, 18(3):185-19, 2008.
[82] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, second edition, 2012.
[83] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems 28 (NIPS), pages 2989-2997, 2015.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yss]. [No], or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description.
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Remark 4 for a discussion on
computational efficiency and Section 5 for discussion on high probability bound. (c) Did you discuss any potential negative societal impacts of your work? [No] We cannot foresee a potential negative societal impact of this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [Yes]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if
applicable? [No] We do not use crowdsourcing.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [No] We do not use crowdsourcing.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [No] We do not use crowdsourcing.
15


Reviews:
[{"review_id": "r9F5z1pUxkI", "reviewer": "Reviewer_P75U", "summary": "This work studies the problem of online adapting to label shift (e.g. where P(Y|X) is fixed, but the priors change) using the framework of online learning. It features a very strong theoretical analysis and excellent experimental evaluation. The presentation is great, and the Appendix even includes a brief intro to OCO! ", "questions": "1) Remark 1; can you make it more formal what you mean by that you should focus on dynamic regret? Could you formally prove the advantage? Or is this already clear from the experiments? \n\n2) Line 162 - Should this really be \\mathbb{E}_{x \\sim D_t} ? I have the feeling that it should not be dependent on t here. \n\n3) \"method still hardly suitable for the OCO framework\" (line 195) - why? Can you be more precise why that is the case? CUrrently a bit vague. \n\n4) I could not understand the remark in line 202 - where is it shown that the risk estimator is convex in expectation? \n\n5) In line 260; the risk is used in the Hedge algorithm. Is there not a overfitting concern here? Should this risk not be estimated using validation data or fresh samples? ", "limitations": "The authors reflect and conclude sufficiently on their own work - indeed high probability regret bounds would be nice to have as a future work, but the current work is already multi-contribution and definitely high quality. ", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) Very strong theoretical and seemingly sound analysis (I did not have time to go through the proofs) and various different variants of the algorithm are proposed and evaluated to show their pro's and cons. \n\n2) A very clear comparison is made to related methods and its discussed in great detail what are the pro's and cons of the proposed method compared to the related work \n\n3) The experiments seem very extensive and show clearly what the authors want to show\n\n4) I was a bit sad to see the conclusions being postponed to the appendix; but the related work was sufficiently covered in the main text according to me. \n\nI would maybe Transpose Table 1 if there is space to make it easier to read (easier to compare numbers vertically than horizontally). \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "S9qeYfL3hzM", "reviewer": "Reviewer_bK7W", "summary": "This paper addresses the problem that the label distribution in testing data is different from training data. The problem is interesting and with practical interest. The authors propose to include the testing data in the training process in the goal to reduce error.\n\nThe proposed method has two stages: first selecting data and corresponding labels from the initial distribution; including unlabeled data from another distribution. If the label shift is not considered, would the model produce wrong prediction results?\n\nThe goal of the work is to make the model adaptive to the new label distribution. Is it a two way door design? That is, when there is no label distribution shift, the model performs as well as the vanilla one trained on the data following the initial distribution.\n\nIn Theorem 1, the constant \\sigma >0 denotes the minimum singular value of confusion matrix. What is the assumption to make the minimum singular value of confusion matrix to be bigger than 0, instead of 0? \n\nV_T measures the intensity of the label distribution shift. Is there any threshold that, if V_T is smaller than the threshold, the label distribution shift does not have effect about the performance of the vanilla model.\n\nCould the method be applied to both classification and regression?", "questions": "If the label shift is not considered, would the model produce wrong prediction results?\n\nDoes the proposed model follow a two way door design? That is, when there is no label distribution shift, the model performs as well as the vanilla one trained on the data following the initial distribution.\n\nIn Theorem 1, the constant \\sigma >0 denotes the minimum singular value of confusion matrix. What is the assumption to make the minimum singular value of confusion matrix to be bigger than 0, instead of 0? \n\nV_T measures the intensity of the label distribution shift. Is there any threshold that, if V_T is smaller than the threshold, the label distribution shift does not have effect about the performance of the vanilla model.\n\nCould the method be applied to classification and regression?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n-The problem is interesting and with practical interest.\n-The paper is well written.\n\nWeakness:\n- The assumptions of the work are not clarified.\n- The data in the experiments is not in large scale.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "46vk_79FmWv", "reviewer": "Reviewer_Z3UA", "summary": "This paper aims to minimize the dynamic regret (instead of the static regret in previous work) for the problem of online label shift (OLS). Specifically, to handle the non-stationarity environment and the lack of supervision, this paper constructs a new unbiased risk estimator that utilizes the unlabeled data and then proposes online ensemble algorithms to deal with the non-stationarity nature.  Besides, theoretical analyses about the dynamic regret bounds are provided. Experiments are conducted to validate the effectiveness of the proposed method.", "questions": "1. As claimed by the authors, [15] mainly utilizes the $0/1$ loss while this paper uses the surrogate loss in the construction of the unbiased risk estimator. However, I find the provided dynamic regret bound is about the surrogate loss while we originally care about the $0/1$ loss (just the same as the evaluation measure in experiments). Thus, a natural question is what is about the dynamic $0/1$ regret bound? Please give more discussions.\n2. In this paper, the hypothesis set (or the model domain) $\\mathcal{W}$ is assumed to be known but nearly impossible in practice. I also checked the experimental part but find no useful information. How to select or set $\\mathcal{W}$? Please give more discussions.", "limitations": "While this paper is built on related work, I am afraid that the novelty may be a bit limited.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not an expert in this area and may neglect related literature. Below are my comments.\n\n### Originality\nThe novelty is limited. This work is mainly built on [15]. While [15] mainly aims to minimize the static regret for the OLS problem, this work aims to minimize the dynamic regret, which needs to consider more suitable online learning algorithms.\n\n### Quality\nOverall, this paper is sound. The proposed methods are natural and built on related work. The claims are supported by formal theoretical results. I have not carefully checked the proofs and the techniques seem standard. Experimental results are also provided to illustrate the effectiveness. Please see my main concerns in the Questions part.\n\n### Clarity\nThis paper is well written and organized.\n\n### Significance\nThis paper should be of interest to the community of label distribution shift, and online learning. Besides, the non-stationary setting may be very practical in some applications although this paper considers the simple OLS setting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept