Online Adaptation to Label Distribution Shift
Authors: Ruihan Wu
Chuan Guo
Yi Su
Kilian Q Weinberger
Venue: NeurIPS 2021 Poster (2021)
Keywords: Damain Adaptation
Label Shift
Online Learning

Abstract: Machine learning models often encounter distribution shifts when deployed in the real world.  In this paper, we focus on adaptation to label distribution shift in the online setting, where the test-time label distribution is continually changing and the model must dynamically adapt to it without observing the true label. This setting is common in many real world scenarios such as medical diagnosis, where disease prevalences can vary substantially at different times of the year. Leveraging a novel analysis, we show that the lack of true label does not hinder estimation of the expected test loss, which enables the reduction of online label shift adaptation to conventional online learning. Informed by this observation, we propose adaptation algorithms inspired by classical online learning techniques such as Follow The Leader (FTL) and Online Gradient Descent (OGD) and derive their regret bounds. We empirically verify our findings under both simulated and real world label distribution shifts and show that OGD is particularly effective and robust to a variety of challenging label shift scenarios.

Online Adaptation to Label Distribution Shift
Ruihan Wa Cornell University rw565@cornell.em edu
Chuan Guo
Yi Su
Kilian Q. Weinberger
Facebook Al Research chuanguo@fb.. com
Cornell University
(ys756, kqu4@cornell.edu)
Abstract
Machine learning models often encounter distribution shifts when deployed in the real world. In this paper, we focus on adaptation to label distribution shift the online setting, where the test-time label distribution is continually changing and the model must dynamically adapt to it without observing the true label. Leverag- ing novel analysis, show that the lack of true label does not hinder estimation the expected test loss, which enables the reduction of online label shift adap- tation conventional online learning. Informed by this observation, we propose adaptation algorithms inspired by classical online learning techniques such as Fol- low The Leader (FTL) and Online Gradient Descent (OGD) and derive their regret bounds. We empirically verify our findings under both simulated and real world label distribution shifts and show that OGD is particularly effective and robust a variety of challenging label shift scenarios.
Introduction
common assumption in machine learning that the training set and test drawn from the same distribution (25). However, this assumption often does not hold in practice when models are deployed in the real world [3] 28). One common type of distribution shift is label shift, where the conditional distribution p(xly) is fixed but the label distribution p(y) changes over time. This phenomenon is most typical when the label y the causal variable and the feature x is the observa- tion [1. For instance, model trained to diagnose malaria can encounter much higher prevalence of the disease in tropical regions.
Prior work have primarily studied the problem of label shift in the offline setting 2 4 22
42),
where the phenomenon occurs only once after the model is trained. However, many common scenarios, the label distribution can change continually over time. For example, the prevalence of disease such as influenza changes depending on the season and whether an outbreak occurs. The distribution of news article categories is influenced by real world events such as political tension and the economy. In these scenarios, modeling the test-time label distribution being stationary can be inaccurate and over-simplistic, especially if the model is deployed over long period of time.
To address this shortcoming, define and study the problem of online label shift, where the distri- bution shift is modeled as an online process. An adaptation algorithm in this setting tasked with making sequential predictions on random samples from a drifting test distribution and dynamically adjusting the model's prediction in real-time. Different from online learning, the test label is not observed after making prediction, hence making the problem much more challenging.
Nevertheless, we show that it is possible to adapt to the drifting test distribution in an online fash- ion, despite never observing single label. In detail, describe method of obtaining unbiased estimates of the expected 0-1 loss and its gradient using only unlabeled samples. This allows the reduction of online label shift adaptation define two algorithms inspired by classical Rechniques-Onee low The History (FTH) the latter being a close relative of the Follow The Leader algorithm. Under
conventional online learning, which then utilize to
Gradient Descent (OGD) and Fol-
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Framework The general framework for online label shift adaptation.
Input: AA
1: fi = fo:
2: for = 1... . do
3: Nature provides X,, where (xt, yt) ~ Qt and (x(x)))) = Qo (x(3))
4: Learner predicts fi(x;)
5: Learner updates the classifier: fi+1 = A(fo, (xI,-.. 1x,,".,> .x.))
6: end for
mild and empirically verifiable assumptions, we prove that OGD and FTH are as optimal as fixed classifier that had knowledge of the shifting test distribution advance.
To validate our theoretical findings, we evaluate our adaptation algorithms on CIFAR-10 (0) un- der simulated online label shifts, well as on the ArXiv datase @ for paper categorization, which exhibits real world label shift across years of submission history. We find that OGD and FTH are able to consistently match or outperform the optimal fixed classifier, corroborating our theoretical results. Furthermore, OGD empirically achieves the best classification accuracy on average against a diverse set of challenging label shift scenarios, and can be easily adopted in practical settings.
2 Problem Setting
We first introduce the necessary notations and the general problem of label shift adaptation. Consider
a classification problem with feature domain and label space y = (l..... M). We assume that classifier f X' + y operates by predicting a probability vector Py(x) A A where A A denotes the -M--1)ddimensonad probability simplex. The corresponding classification function is fx) arg ya Px(x)x)))))))))))) [x] While the focus of our paper is on neural networks, other models
such as SVMs 7 and decision trees 27 that do not explicitly output probabilities can be calibrated
to do well 26 41).
Label distribution shift. Let Q be a data distribution defined on X' x y and denote by Qx the class-conditional distribution, and by Q1y) the marginal distribution, so that Q(x, Q(xly)Q(v). Standard supervised learning assumes that the training distribution Qirain and the test distribution Qeest are identical. In reality, a deployed model often encounters distributional shifts, where the test distribution Que may be substantially different from Quain. We are interested in the scenario where the cansscooniiiinal distribution remains constant (i.e., (xsx()ll) Q (x (xly) for all x E X,y E }) while the marginal label distribution changes (i.e., Quea * Quain (3) for some y E }), a setting we refer to label shift. The problem of label shift adaptation is to design algorithms that can adjust the prediction of a classifier f trained on Qurai to perform well on Quest
Offline label shift. The general setting in this paper and in prior work on label shift adaptation that the label marginal distribution Quea(y) is unknown. Indeed, the model may be deployed in foreign environment where prior knowledge about the label marginal distribution is limited or inaccurate. Prior work tackle this challenge by estimating Qua(y)) using unlabeled samples drawn from Qust [2] 4 10 22 30). Such adaptation methods operate under the offtine setting since the distribution shift occurs only once, and the adaptation algorithm is provided with an unlabeled set of samples from the test distribution Ques upfront.
Online label shift. In certain scenarios, offline label shift adaptation may not be applicable. For example, consider a medical diagnosis model classifying whether patient suffers from flu or hay fever. Although the two diseases share similar symptoms throughout the year, one is far more prevalent than the other, depending on the season and whether an outbreak occurs. Importantly, this label distribution shift is gradual and continual, and the model must make predictions on incoming patients in real-time without observing an unlabeled batch of examples first. Motivated by these challenging use cases, we deviate from prior work and study the problem where Qiest is not stationary during test time and must be adapted towards in online fashion.
Formally, we consider a discrete time scale with a shifting label distribution Q+(y) for t = 0,1,2.... where Qo Qinin denotes the training distribution. For each t, denote by qe E A M-1
https://wwwz kaggle. wttpe//eooooooeeeeeeaeeeeeet///e

---

the label marginal probabilities so that qı Fq, (yt = i) for all i == 1..... M. Let H. be fixed hypothesis space, let fo E H. be a classifier trained on samples from Qo. and let fi = fo-
At time step i, nature provides (X+. ~ Qt and the learner predicts the label of x; using ft- Similar to prior work on offline label shift, we impose crucial but realistic restriction that the true label Yt and any incurred loss are both unobserved. This restriction mimics real world situations such medical diagnosis where the model may not receive any feedback while deployed. Despite this limitation, the learner may still seek to adapt the classifier to the test-time distribution after predicting on X₁. Namely, the adaptation algorithm AA takes as imput fu and the unlabeled set of historical data {x1. Xx} J and outputs a new classifier fi+1 E H. for time step + 1. This process
repeated until some end time and summarized in pseudo-code in Framework !
To quantify the effectiveness of the adaptation algorithm A, we measure the expected regret across time steps 1 .....,? T. Formally, we consider the expected 0-1 loss
{(;; Q) ((x.))-Q(f( (f()) # v),
which we average across I and measure against the best-in-class predictor from H:
Regret- = + E (ff:..))
1
- inf JEH
1
Σ ((:Q))
(2)
The goal of online label shift adaptation is to design algorithm A that minimizes expected regret.
3 Reduction to Online Learning
One of the main differences between online label shift adaptation and conventional online learning that in the former, the learner does not receive any feedback after making a prediction. This restriction prohibits the application of classical online learning techniques that operate on loss function observed after making prediction each time step. In this section, we show that in fact the expected 0-1 loss can be estimated using only the unlabeled sample xt, which in turn reduces the problem of online label shift adaptation to online learning. This reduction enables a variety of solutions derived from classical techniques, which we then analyze in in|section 4|
Estimating the expected 0-1 loss. For any classifier f and distribution Q++ let Cj.q.
RM denote the confusion matrix for classifying samples from Q,. Formally, Cr..l. =
Px,-Qe(-v y, m²) (x,, = j). Then the expected 0-1 loss of f under distribution Qe (cf. [Equation 1 can be written in terms of the confusion matrix C₁.q. and the label marginal probabilities q. by:
M
((f:Q()=
= P (f(x.) # vc)
Σ
Px (x==(((w==)((())) +1) Pq. (ye i)
M
= Σ (1- (1-PPxn i)) q. = diag (C,.q.) .4))
where 1 denotes the all-1 vector, and diag(Cr.Q.) is the diagonal of the confusion matrix. The difficulty in computing {(f: Qt) is that both Cf.q, and qu depend on the unknown distribution Qi- However, by the label shift assumption that the conditional distribution (x(yly) does not change over time, it immediately follows that CjQ. C, VI, and therefore {(f; Q+) is linear in q
e(f: Q.) = (1 diag (Cr.q.) qt).
(3)
In the theorem below, we utilize this property to derive unbiased estimates of E(): and its gradi- ent V ve(s; Qx) with the assumption that diag (Cr.0a) is differentiable with respect to sü we discuss this assumption in more detail in Section 4.1 The proof is included in the appendix and is inspired by prior work on offline label shift adaptation (22].
Assumption 1. diag (Cr.qw) is differentiable with respect to f.
Theorem 1. Let f be any classifier and let fo be the classifier trained on data from Qo Suppose that fo predicts fo(x:) i input xt ~ Qt and let e, denote the one-hot vector whose non-zero
entry is i. If the confusion matrix So is invertible then q = (CTo.o) e is an unbiased
3

---

Framework 2 The re-weighting framework for online label shifting adaptation.
Input: A, fo. qo. Do
fi = fo:
2: for fort=1.-
T do
3: Nature provides Xx, where (x,, (x),)r)= ~ Qe and (x(x)))) (x(gbe):
4: Learner predicts fxx))
5: Learner updates the re-weighting vector: Pt+1 = A(fo, qo: Do: (
6: Learner updates the classifier: fi+1 = g(x; for qu. P(+1).
7: end for
estimator of the label marginal probability vector q. Further, we obtain unbiased estimators of the loss and gradient of f for Q: with Assumption 7
Q(): Eq, [1 diag (CI.qu).
vel(f:Qi Qi) Eq. [J)
where J,- 87 [1 diai (C)) denotes the Jacobian of - diag (Cz.Qu) with respect to f.
Note that in the theorem, the true confusion matrices C,Qq, and Co require knowledge of the training distribution Qo and are generally unobservable. We assume we have the full access of distribution Qn for the theoretical analysis in the remainder of the paper, including both values and gradients of C.QQ given any f. In practice, we can estimate the value of Cg.Qo Qo by using large labeled hold-out set Do drawn from Qo and the estimation error that can be reduced arbitrarily by increasing the size of Do (22). For the detail of the practical gradient estimation, we discuss it in Section
Re-weighting algorithms for online label shift adaptation. The result from Theorem I allows us to approximate the expected 0-1 loss and its gradient for any function f over Qee. which naturally inspires the following adaptation strategy: Choose hypothesis space G, and at each time step t, estimate the expected 0-1 loss and/or its gradient and apply any online learning algorithm to select the classifier f++1 G for time step t + 1.
A natural choice for is the hypothesis space of the original classifier fo, i.e., = H. Indeed, the unbiased estimator for the gradient V vyE(f; Qc) in Theorem can be used to directly update fo with stochastic online gradient descent. However, we assume that only the marginal distribution Qx(y) drifts and Qx y) = Qa (xly), the conditional distribution Q+ x) must be a re-weighted version of Qo(y)x)) Specifically,
Qx(v) Qv(1)x) (x(x) (x Q:(v) ()(x (x) Qu(y) Qx(x)
(v) Qo(x) Qo(yix)
Qi(v)
Oo(vix). (4) Qo(y)
Since the goal of fo is to approximate this conditional distribution, in principle, only rewihttttigg of the predicted probabilities needed correct for any label distribution shift. similar insight has
been previously exploited to correct for training- time label imbalance 6 g 16. 39 and for offline
label shift adaptation 22
We therefore focus our attention to the hypothesis space of weiwhihhted
classifiers: ((fo. qo)
{g(x; fo, qo p) p E AM-1), where the classifier g(x; fo. qo. p) is defined by the learned parameter vector p and takes the following form:
plyl Pj (x)[,),
g(x; for qo: p) arg max yEY
(5)
Z(x goly)
Pro (x) [u] being the normalization factor. We specialize the online label shift adaptation framework to the hypothesis space [( qo) in Framework 2 where the adapta- tion algorithm AA focuses on generating re-weighting vector p. each time step construct the classifier gx; for qo. Pt). The online learning objective can then be re-framed as choosing the re- weighting vector Pt that minimizes:
(ul with (xx) = Eyey golyl
T E ((p)iq))
Regret = T
inf DEAM- M-1
1 T
Σ (p: q:),
(6)
t=1
where (pp q:) == [(g(x; ; for oo. Pt): Q.). For the remainder of this paper, we will analyze several classical online learning techniques under this framework.

---

Online Adaptation Algorithms
We now describe our main algorithms for online label shift adaptation. In particular, we present and analyze two online learning techniques-Onine Onnine Gradient Descent (OGD) and Follow The History (FTH), the latter of which closely resembles Follow The Leader [32]. We show that under mild and empirically verifiable assumptions, OGD and FTH both achieve 0(1/V7) regret compared to the optimal fixed classifier in G(Jo.qo))
4.1 Algorithm 1: Online Gradient Descent
is a classical online learning algorithm based on iteratively updating the hypothesis by following the gradient of the loss. Applied our setting, the algorithm Aogd computes the stochastic gradient <p q:) p=p. = (p(P:) d: using Theorem where
Online gradient descent (OGD) 32
Jp
(1 diag (Co(:fo.9o.))....)
Öp
p=p:
denotes the M x M Jacobian with respect to p. OGD then applies the following update:
P++1 = ProjaM-1 (P: 17 Vp((p:
(8)
where 77 > 0 is the learning rate, and ProjaM-: projects the updated vector onto A AM-1_
The convergence rate of Aoga depends on properties of the loss function E(p; q). We empirically observe that {(p: q) is approximately convex in the re-weighting parameter vector p. which we justify in detail the appendix. To derive meaningful regret bounds for OGD, we further assume that the loss function {p: q) is Lipschitz with respect to p. Formally:
Assumption (Convexity). Vq E AM-1, ((p: q) is convex in p.
Assumption (Lipschitz-ness). SuPpeAM-1,=m1
.M p ppe(p:(GG (p:(CT..o)
e:
ee)l is finite.
Below, we provide our regret bound for OGD, which guarantees a O(1/VV convergence rate. The proof follows the classical proof for online gradient descent and is given in the appendix. and let L
Theorem
2 (Regret bound for OGD.). Under Assumption
sup p M. MM
P
(CT
10.90)
C;
If = v 7 then Aogd satisfies:
T E(pr: qu)
1
Σ ((: q:) S v 1
inf DEAM-
T
Gradient estimation. Computing the unbi- ased gradient estimator Vp 9:)lp=p. in- volves the Jacobian term (p(p)) ) in |Equation 7 which is discontinous when estimated using the hold-out set Do. More precisely, each entry of is the expected 0-1
Algorithm 3 Gradient estimator for V Vpe(p:g)
Input: p,q, 6,
1: for 1,..., M do
2:
A, {p j8 Ci 9) - C(p jō. e, q)
1 diag (Cs(::fo.qo-p) loss for partieular class, whose estimate using Do is step function. This means that taking the derivative naively will result a gradient value of O. To circumvent this issue, we apply finite difference approximation [I] for comput- ing (p: 4:)lp=p. which is detailed in Algorithm We also apply smoothing to compute the average estimated gradient around the target point p. to improve gradient stability.
3:
Vplil = Σ}= a (265)) where o,
2 2-11) ((t))
4: end for
5: Return: V
Alternatively, we can minimize a smooth surrogate of the 0-1 loss that enables direct gradient com- [0, so that frrob l when Py outputs one-hot probability vectors. Furthermore, we show that gorob enjoys the same unbiased estimation properties that of f in Theorem I admits smooth gradient estimates using finite
putation. In detail, we define (prob (f: Q) == [xx,))=[[1 (x)
5

---

hold-out set Do. and is classification in the sense of Tewari and Bartlett [38]. The formal statement and proof of the above properties are given in the appendix. In [section we empirically evaluate OGD using both the finite difference approach and the surrogate loss approach for gradient estimation.
4.2 Algorithm 2: Follow The History
Next, we describe Follow The History (FTH) minor variant of the prominent online learning strategy known Follow The Leader (FTL) 32 In FTL, the basic intuition is that the predictor fi for time step t is the one that minimizes the average loss from the previous time steps. Formally:
P++1 arg min 7 Σ e (p: arg min l pi 2 cr
(9)
DEAM
==1
DEAM
where the second inequality holds by linearity of t. However, faithfully executing FTL requires optimizing the loss in [Equation 9 at each time step, which could be very inefficient since multiple gradients of need to be computed as opposed to single gradient computation for OGD.
To address this efficiency concern, observe that if the original classifier fo is Bayes optimal, then for any q. E A M-1, the minimizer over the re- re-weighting vector of &(p: qe) is the test-time label marginal probability vector q, itself (cf. [Equation 4). In fact, show in the appendix that this assumption often holds approximately in practice, especially when fo achieves a low error on Qo and is well-calibrated [12 26 41). Assuming this approximation error is bounded by some 0, we can derive a more efficient update rule and a corresponding regret bound. Formally:
Assumption (Symmetric optimality). For any q A |/q arg wim.eEaM-...... ((p: g) S 8.
We define the more efficient Follow The History update rule Atth as: P++1 = + 4r. which is a simple average of the estimates å, from all previous iterations of the algorithm. FTH coincides with FTL when Assumption holds with ō O. In the following theorem, we derive the regret bound for FTH when = 0 but prove the general case of 6 2 0 in the appendix. The theorem relies on an assumption of Lipschitz-ness that is slightly different from Assumption We formally state them as below:
Assumption (Lipschitz-ness for FTH), sup -. V (p: g)lp2 is finite.
Theorem 3. Under Assumption 4 and 5 with = O, with probability at least 2M over samples (xi, yi) Qt 1...., we have that Afth satisfies:
In
MInT
((p inf Σ ((: < 2L P
+
+4LOV
T
T
T
(CT
where c max;=1......
To.
C;
and L = sup supp a vpl(p:))l
5
Experiment
In this section, we empirically evaluate the proposed algorithms on datasets with both simulated and real world online label shifts. Our simulated label shift experiment is performed on CIFAR-10 (20,, where we vary the shift process and explore the robustness of different algorithms. For real world label shift, we evaluate on the ArXiv datase for paper categorization, where label shift occurs naturally over years of paper submission due to changing interest in different academic disciplines.
5.1 Experiment set-up
Online algorithms set-up. We evaluate both the OGD and FTH algorithms from Section 4 For OGD, we use the learning rate 1 = \ T suggested by Theorem where L is estimated by laking the maximum over (e, y E y} for 100 vectors p' uniformly sampled from A-1, The
ftttps://www.ii http:p//wwww..aaaeeeo////////ee/ /atee//eerrr//ooolllaaaaaatraarr

---

gradient estimate can be derived using either the finite difference method in Algorithm 3 or by directly differentiating the surrogate loss garab We evaluate both methods in our experiments.
For FTH, we evaluate both the algorithm Afth defined in |uusectionn 4.2 and a heuristic algorithm Aftffw which we call Follow The Fixed Window History (FTFWH). Different from FTH where P++1 is the simple average of q across all previous time steps = 1, I...,... t, FTFWH averages across pre- vious estimates Âr in a fixed window of size w. i.e., P++1 = -r m (1,t-=+1) qr/ min(w, l). Intuitively, FTFWH assumes that the distribution Q2 as fixed for w time steps and solves the offline label adaptation problem for the next time step. We use three different window lengths = 100, 1000, 10000 in our experiments. We will show that FTFWH can be optimal at times but inconsistent in performance, especially when the window size w coincides with the periodicity in the label distribution shift.
Baselines. In addition, we consider the following baseline classifiers as benchmarks against online adaptation algorithms.
Base Classifier (BC) refers to the classifier fo without any online adaptation, which serves reference point for evaluating the performance of online adaptation algorithms.
Optimal Fixed Classifier (OFC) refers to the best-in-class classifier in ((o. qo). which is the optimum in Equation 6 We denote the re-weighting vector that achieves this optimum as popt In simulated label shift, we can define the ground truth label marginal probability vector qu and optimize for p directly. For the experiment on ArXiv, we derive the optimum using the empiri- cal loss: p arg minp (p: El= Cy. where ye is the ground truth label at time Note that OFC is not practical algorithm since Y/ is not observed, but it can be used to benchmark different adaptation algorithms and estimate their empirical regret.
Evaluation metric. Computing the actual regret requires access to for all f, which we do not observe in the real world dataset. To make all evaluations consistent, we report the average error 1 T E 1
(x;: fo: qo: Pr) * yr) to approximate T Σ E(pr; qr). This approximation is valid for large T due to its exponential concentration rate by the Azuma-Hocffide Hoeffding inequality.
5.2 Evaluation on CIFAR-10 under simulated shift
Dataset and model. We conduct our simulated label shift experiments on CIFAR-10 [20] with a ResNet-18 18 [3] classifier. We divide the original training set into train and validation by ratio of 3 3: 2. The training set is used to train the base model fo. and the validation set Do is used for both temperature scaling calibration [22 and to estimate the confusion matrix. The original test set is for the online data sampling. Additional training details are provided in the appendix.
Simulated shift processes. Let (t), ( M-1 be two fixed probability vectors. We define the following simulated shift processes for the test-time label marginal probability vector qr-
Constant shift: qu (") for all t, which coincides with the setting of offline label shift. i.e,
Monotone shift: q, interpolates from (2) to ((2), i.e., q. = (1 +) (1)) (1) (2).
Periodic shift: q, alternates between (2) and (22) at a fixed period of Tp- We test under three
different periods T, 100, 1000, 10000.
Exponential periodic shift: qe alternates between (1) and q (2) with exponentially growing period. Formally, Vi E (222111 q := ()) Vt E | k2 q (2)), We use k 2,5 for our experiments.
In our experiments, (2) and q (2) are defined to concentrate on the dog and cal classes, respectively. That is, q (1) [dog] = 0.55 and q (3) 0.05 for all other classes y, and similarly for (2)) The end time T is set to 100, 000 for all simulation experiments. All results are repeated using three different random seeds that randomize the samples drawn at each time step t.
Results. Table I shows the average error of various adaptation algorithms when applied to the simulated label shift processes. All adaptation algorithms can outperform the base classifier fo (except for FTFWH for periodic shift with T, = 100), which serves as a sanity check that the algorithm is indeed adapting to the test distribution.
7

---

Simulated Label Shift
Method
Periodic
Exp. Periodic
Constant
Monotone
Tp 100
T, 1000
T, 10000
k
k 5
Base Classifier (a)
12.43+ 004
11.63+
11.63+ 0.09
11.62- 0.08
11.63+ 0.10
11.67+ 0.77
11.81+
Opt. Fixed Classifer
7.78#
10.24:
10.25: 0.08
10:24: 0.08
10.24: 0.08
10:27: 0.07
10.25:
FTH
7.68& 0.11
10.364
10.274 0.08
10.25 0.06
10.331 0.10
10.234 0.06
10.254
10a
8.71+
10.19
12.15+ 0.01
8.85+ 0.04
8.46= 0.11
8.52+
8.54= 0.05
FTFWH
10
7.741 0.07
9.52- 0.10
10.25,1 0.07
11.16: 0.12
7.841 0:09
7.771
7.67 0.08
10
7.67+ 0.08
9.53 0.10
10.26+ 0.07
10.26- 0.06
10.83+ 0.07
8.93+
8.46- 0.07
OGD (finite diff.)
8.08.1 0.08
9.79: 0.09
10.71: 0.10
10.62-0.00
10.11: 0.06
8.901 0.05
8.56.
OGD (surrogate loss)
7.78+ 0.11
9.75+ 0.07
10.24+ 0.06
10.21+am o007
10.05+ 0.09
8.92+ 0.04
8.50 0.11
Table 1:
Average error (%) for different adaptation algorithms under simulated label shift on
CIFAR-10. Standard deviation is computed across three runs, Results that are better than the OFC benchmark by 0.5 or more are highlighted in blue, and results that are worse than the OFC benchmark by 0.5 or more are highlighted in red.
Method
Base (fo)
Opt. Fixed
FTH
FTFWH
OGD
10a
10a
10a
finite diff.
surr. loss
Avg. Error (%)
27.21
25.56
25.62
30.14
26.09
25.87
25.52
25.70
Table 2: Average test error (%) on the ArXiv dataset.
Comparison with the optimal fixed classifier (OFC) reveals more insightful characteristics of the different algorithms and we discuss each algorithm separately as follows.
The performance of Follow The History (FTH) is guaranteed to be competitive with OFC by Theorem 3 when the base model fo is well-calibrated. Indeed, as shown in the table, the average error for FTH is close to that of OFC for all shift processes. However, it is also very conservative and can never achieve better performance than OFC by a margin larger than 0.5.
Follow The Fixed Window History (FTFWH) with a suitably chosen window size performs very well empirically, especially for constant shift, monotone shift, and exponential periodic shift. However, when encountering periodic shift with the periodicity Tр equal to the window size w (highlighted in red), FTFWH consistently subpar compared OFC, and sometimes even worse than the base classifier fo- Since real world distribution shifts are often periodic in nature (e.g., seasonal trends for flu and hay fever), this result suggests that deploying FTFWH may require knowledge of the periodicity in advance, which may not be feasible. In fact, we show in our experiment on real world label shift on ArXiv that FTFWH is never better than FTH and OGD.
Online gradient descent (OGD) with learning rate 7) / 7 ? is also guaranteed to be as good as OFC by Theorem D which is empirically observed as well. Moreover, unlike FTH which only achieves an average error no worse than that of OFC, OGD able to outperform OFC on certain scenarios such as monotone shift, periodic shift with T, 10000 and exponential periodic shift with = 2,5. We also observe that OGD using the surrogate loss for gradient estimation is consistently better than OGD with finite difference gradient estimation.
Overall, we observe that OGD is the most reliable adaptation algorithm from the above simulation results, as it is uniformly as good as OFC and sometimes can achieve even better results than OFC.
5.3 Evaluation on ArXiv under real world distribution shift
Dataset and model. We experiment on the ArXiv dataset for categorization of papers from the Computer Science domain into 23 refined categories]] There are total of 233, 748 papers spanning from the year 1991 to 2020, from which we sort by submission time and divide by a ratio of 2 1: into the training, validation, and test sets. For each paper, we compute the tf-idf vector of its abstract as the feature x, and we use the first category in its primary category set as the true label y. The base model fo is an Izzrregularized multinomial regressor. Same as in the simulated shift experiments, the validation set Do is used to calibrate the base model fo and estimate the confusion matrix. Additional details on data processing and training are given in the appendix.
3 'There are actually 40 categories in the Computer Science domain, from which we select the 23 most populated categories.
8

---

shows the average error for each adaptation algorithm over the test set, which consists of papers sorted by submission time with end time T 58, 437. In contrast the simulated shift experiments in (ubsecttinn 5.2 FTFWH is consistently worse than the optimal fixed classifier (OFC), especially for window size w 100 where it even worse than the base classifier fo- This result shows that despite the good performance of FTFWH for simulated label shifts on CIFAR-10, it encounters significant challenges when deployed to the real world.
Results. [abll 2]
On the other hand, FTH and OGD both achieve an average error close to that of OFC, which again validates the theoretical regret bounds in Theorem and Theorem 3] Given the empirical observa- tion of OGD's performance on both simulated and real world label shift, as well as its conceptual simplicity and ease of implementation, we therefore recommend it as a practical go-to solution for online label shift udaptation in real world settings.
6 Related Work
Label shift adaptation has received much attention lately. The seminal work by Saerens et al. [30] made the critical observation that the label shift condition of p(xly) being stationary implies the optimality of e--eeigtted classifiers. They defined an Aopectation-Maximiaatti to utilize this insight and learn the re-weighting vector that maximizes likelihood on the test distri- bution. Alexandari et al. 2 studied this approach further and discovered that calibrating the model can lead to significant improvement in performance. Another prominent strategy for learning the re-weighting vector is by inverting the confusion matrix [22), which inspired our approach for the online setting. Extensions to this method include regularizing the re-weighting vector 4. generaliz- ing the label shift condition to feature space rather than input space (37. and unifying the confusion matrix approach and the EM approach [10].
(EM) procedure
Another type of test-time distribution shift that has been widely studied is covariate shift. Differing from the label shift assumption that p(xly) is constant, covariate shift assumes instead that p(y[x) is a constant and p(x) changes between training and test distributions. Earlier work by Lin et [2] relied on the assumption that the density function p(x) is known, while subsequent work relaxed this assumption by estimating the density from data [1 covariate shift problem have also been considered. Solutions to this problem either rely on the knowledge of test labels [18), or use unsupervised test-time adaptation methods that are tailored to visual applications 44 24 36).
40). Online extensions to the
More broadly, both label shift adaptation and covariate shift adaptation can be categorized under the general problem of domain adaptation. This problem is much more challenging because a test sample may not necessarily belong to the support of the training distribution. In this setting, there is a large line of theoretical work that prove performance guarantees under bounded training and test distribution divergence
[5]
23 33), as well empirical methods for domain adaptation in the
realm of deep learning 9
9
29
35
7 Conclusion
We presented rigorous framework for studying online label shift adaptation, which addresses lim- itations in prior work on offline label shift. Under our framework, we showed that it is possible to obtain unbiased estimates of the expected 0-1 loss and its gradient without observing a single label at test time. This reduction enables the application of classical techniques from online learning to define practical adaptation algorithms. We showed that these algorithms admit rigorous theoretical guarantees performance, while at the same time perform very well empirically and can adapt to a variety of challenging label shift scenarios.
One potential future work is to relax Assumption to weak convexity assumption. With this re- laxation, one needs take closer look online learning techniques and applies it into the online label shift problem with the reduction introduced in this paper and potential additional reduction. Another extension is that we focused on re-weighting algorithms for online label shift adaptation in this paper, the reduction presented in sessectton 3 technically enables larger set of solutions. Indeed, one possible future direction is to directly apply OGD to update the base classifier fo. which may further improve the adaptation algorithm's 's performance.

---

Acknowledgments and Disclosure of Funding
RW and KQW are supported by grants from the National Science Foundation NSF (III-161814, III- 1526012, 119882, and IIS-1724282), the Bill and Melinda Gates Foundation, and the Cornell Center for Materials Research with funding from the NSF MRSEC program (DMR-1719875), and SAP America.
References
[1] Karsten Ahnert and Markus Abel. Numerical differentiation of experimental data: local versus global methods. Computer Physics Communications, 177(10):764-774, 2007.
[2] Amr Alexandari, Anshul Kundaje, and Avanti Shrikumar. Maximum likelihood with bias- corrected calibration is hard-to-beat at label shift adaptation. In International Conference on Machine Learning, pages 222-232. PMLR, 2020.
[3] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Conerete problems in ai safety. arXiv preprint arXiv:16000 06566,06655504 2016.
[4] Kamyar Azizzadenesheli, Anqi Liu, Fanny Yang, and Animashree Anandkumar. Regularized learning for domain adaptation under label shifts. In International Conference on Learning Representations, 2019.
[5] Shai Ben-David, John Blitzer, Koby Crammer, Fernando Pereira, et al. Analysis of representa- tions for domain adaptation. In Advances in neural information processing systems, volume 19, page 137. MIT; 1998, 2007.
[6] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbal- anced datasets with label-distrbbution-aaar margin loss. In Advances in Neurul Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[7] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3): 273-297, 1995.
[8] Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number of samples. In Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition, pages
2019.
[9] Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty. Deepjdot: Deep joint distribution optimal transport for unsupervised domain adapta- tion. In Proceedings of the European Conference on Computer Vision (ECCV), pages 447 447-463, 2018.
[10] Saurabh Garg, Yifan Wu, Sivaraman Balakrishnan, and Zachary Lipton. A unified view of label shift estimation. arXiv preprint arXiv:2003.07554, 2020.
[11] 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.
[12] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pages 1321-1330. PMLR, 2017.
[13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recogni- lion, pages 770-778, 2016.
[14] Judy Hoffman, Trevor Darrell, and Kate Saenko. Continuous manifold based adaptation for evolving visual domains. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 867-874, 2014.
[15] Judy Hoffman, Mehryar Mohri, and Ningshan Zhang. Algorithms and theory for multiple- source adaptation. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 2256-866,, 2018.
10

---

[16] Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang. Learning deep representation for imbalanced classification. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 5375-5384, 2016.
[17] Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola. Correcting sample selection bias by unlabeled data. In Advances in neural information pro- cessing systems, volume 19, pages 601-608. Citeseer, 2006.
[18] Vidit Jain and Erik Learned-Miller. Online domain adaptation of a pre-trained cascade of classifiers. In CVPR 2011, pages 577-584. IEEE, 2011.
[19] Guoliang Kang, Lu Jiang, Yi Yang, and Alexander G Hauptmann. Contrastive adaptation network for unsupervised domain adaptation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 4893-4902, 2019.
[20] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[21] Yi Lin, Yoonkyung Lee, and Grace Wahba. Support vector machines for classification in nonstandard situations. Machine learning. 46(1):191-202, 2002.
[22] Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. International conference on machine learning, pages 3122- 3130. PMLR, 2018.
[23] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In 22nd Conference on Learning Theory, COLT 2009, 2009.
[24] Ravi Teja Mullapudi, Steven Chen, Keyi Zhang, Deva Ramanan, and Kayvon Fatahalian. On- line model distillation for efficient video inference. In Proceedings of the IEEE/CVF Interna- tional Conference Computer Vision, pages
2019.
[25] Kevin P Murphy. Machine learning: a probabilisticc perspective. MIT press, 2012.
[26] Alexandru Niculescu-Mizil and Rich Caruana. Predicting good probabilities with supervised learning. In Proceedings of the 22nd international conference on Machine learning, pages 625-66 632, 2005.
[27] Ross Quinlan. Induction
of decision trees. Machine learning, 1(1):81-106, 1986.
[28] Joaquin Quiñioner--Camt Candell,, Masashi Sugiyama, Neil D Lawrence, and Anton Schwaighofer. Dataset shift in machine learming. Mit Press, 2009.
[29] Artem Rozantsev, Mathieu Salzmann, and Paseal Fua. Beyond sharing weights for deep do- main adaptation. IEEE Transactions Pattern Analysis and Machine Intelligence, 41(4): 801-814, 2019.
[30] Marco Saerens, Patrice Latinne, and Christine Decaestecker. Adjusting the outputs of clas- siferr to new a priori probabilities: simple procedure. Neural Computation, 14(1):21-4) 2002.
[31] Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris M Mooij. On causal and anticausal learning. In ICML, 2012.
[32] Shai Shalev-Shwartz al. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2):107-194, 2011.
[33] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
[34] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihodd function. Journal of statistical planning and inference, 90(2):227-24 2000.
11

---

[35] Baochen Sun, Jiashi Feng, and Kate Saenko. Return of frustratingly easy domain adaptation. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 2058-2065, 2016.
[36] Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt. Test- time training with self-supervision for generalization under distribution shifts. In International Conference Machine Learning, pages 9229-9248. PMLR, 2020.
[37] Remi Tachet des Combes, Han Zhao, Yu-X Yu-Xiang Wang, and Geoffrey J Gordon. Domain adap- tation with conditional distribution matching and generalized label shift. In Advances in Neural Information Processing Systems, volume 33, 2020.
[38] Ambuj Tewari and Peter L Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(5), 2007.
[39] Yu-Xiong Wang, Deva Ramanan, and Martial Hebert. Learning to model the tail. In Proceed- ings of the 31st International Conference on Neural Information Processing Systems, pages 7032-7042, 2017.
[40] Bianca Zadrozny. Learning and evaluating classifiers under sample selection bias. In Proceed- ings of the Twenty-Firs. International Conference on Machine Learning, page 114, 2004.
[41] Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from deci- sion trees and naive bayesian classifiers. In International Conference on Machine Learning. volume 1, pages 609-616, 2001.
[42] Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In International Conference on Machine Learning, pages 819-827. PMLR, 2013.
12


Reviews:
[{"review_id": "ig5ZKT9k-Z", "reviewer": "Reviewer_qmA9", "summary": "This paper studies how to learn with target shift in an online fashion, especially when the label distribution could shift over time. For the target shift problem, the key challenge is how to estimate the probability of each label in testing time (or at every iteration in the online fashion), and then one can adapt the original classifier ($f_0$) to make good predictions. To address this issue, based on the previous study [40], authors first approximate the true label probability $q_t$ by its unbiased estimator, and then use the unbiased estimators to update the next guess $p_{t+1}$ for the true label probability $q_{t+1}$ with several classical online algorithms. Theoretical analysis shows that the proposed algorithms enjoy sublinear regret bounds in expectation. Experiments also validate the effectiveness of the methods.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Novelty: The problem studied in the paper is novel and realistic. To my knowledge, there seem little works considering how to handle the changing label probability in an online fashion. Although the proposed methods are largely established on the previous studies (i.e. the unbiased estimator developed in [40] and the use of the classical online algorithms), I found it an interesting solution to the problem.\n\nQuality: My main concern about the paper is the mismatch between the initial goal and the performance measure in Theorem 2. Theorem 2 shows that the proposed online algorithm can predict as well as the single best classifier in the hypothesis space. However, since the underlying label probability is changing over time, it is unconvincing that a fixed model could perform well over all iterations. Maybe a time-varying comparator could be a better choice.\n\nBesides, the proposed algorithms seem that heavily rely on the quality of the initial models. Although the estimator is unbiased for $q_t$, its asymptotic behavior could be influenced by $f_0$. I think it would be better if there are some analyses or experiments to illustrate the influence on the quality of the initial model.\n\nClarity: The paper is clearly written and well organized. \n\nOverall, I think the paper falls in the borderline case but has the merits that outweigh the flaws.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned above, the performance measure (the regret) used in the theoretical analysis might be too weak for the case where the label probability could change over time. The time-varying comparator could be a better choice.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6 hours"}, "extra_text": {}}, {"review_id": "IimuZoGURA", "reviewer": "Reviewer_EUMs", "summary": "The paper proposes methods for adapting models in an online manner when the label distribution P(y) is continually changing but the class conditional distribution p(x|y) is fixed, and the labels are not available. It shows a surprisingly elegant argument that the expected 0-1 loss and its gradient can be computed without the labels, and hence the models can be adapted in an online manner. \nThrough experiments on different simulated label shifts on CIFAR data, and on a real dataset from arXiv, it shows that one of the proposed methods OGD is simple and performant in adapting to online label distribution shifts. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Originality: The paper is one of the few focusing on model adaptation for label distribution shifts in an online setting.  Through a simple and elegant argument (equation 3 and Theorem 1) it shows how the model can be adapted in this online setting. Although simple, this appears to be the first paper to identify this connection, and exploit it to update models in this online manner. \n\nQuality: The paper is of good quality - the arguments seem sound, theorems and assumptions are explained and proved, and bounds are shown clearly. The experiments on both simulated label shifts on CIFAR data and a real dataset from arXiv are sound. The results look plausible and convincing.  The paper presents good details on implementation - for example using both finite difference and surrogate losses to estimate the loss gradient, and carries forward these details through the experiments. The intuitive arguments, mathematical arguments, theorems and proofs and experiments appear rigorous. \n\nClarity: The paper is written well, with clearly stated assumptions, theorems, frameworks, algorithms, experiment methodologies and results.  I have not checked the proofs in the appendix.\n\nSignificance: Label distribution shifts is a common problem in real world applications. It is not clear how well the assumption that P(x|y) holds in practice, but under this assumption the proposed methods - and especially the simple OGD method that is performant is interesting, useful and significant. I can see this method becoming popular in applied machine learning in practice,  due to its simplicity and performance. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "My main concern is how valid of the assumption that the class-conditional distribution p(x|y) does not change, in real world situations. It is likely true in the one real dataset they tested viz. arxiv; however, how general is this assumption valid in practice? I am less clear that the same assumption holds for example in the healthcare (flu vs. hay fever) mentioned in the paper. For example, even between different episodes of flu, the variants are slightly different (although generally under the class \"flu\") and these differences in class can translate into differences in the covariates. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3.5 hours"}, "extra_text": {"ethical_concerns": "\nThe authors can address the societal impact of this work. For example, if these methods are used in social systems (say, to model credit default probabilities, risk propensity, dangerous behavior etc.), it is critical to use covariates where the class conditional probabilities do not change. For example, typical covariates in these models like demographics, behavior all change with time, and even the class conditional probabilities can change over time. So, the authors can mention in the paper for the reader/user of this method to be cautious when applying this method in practice.  "}}, {"review_id": "GTmIE-DAIkJ", "reviewer": "Reviewer_r9Tm", "summary": "This paper proposes FTH and OGD methods against the online label shift problem, and the experimental results demonstrate that the proposed methods are effective and robust to various online label shift scenarios.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "As far as I know, this is the first paper considering the online label shift problem which is practical and important for many real-world machine learning problems. The authors give a detailed analysis targeting the online label shift problem and propose solutions for this problem. The well-designed experiments also demonstrate the effectiveness of the proposed methods. Although the result shown in this paper is satisfactory and the analysis is thorough, I have some questions in some detail.\n\n1. Is the proposed method effective for datasets with large label space? The current label shift method often fails to deal with the large label space dataset, such as Cifar100, Imagenet. According to Table 2 in the main paper, the proposed methods seems to improve marginally in the dataset with  23 categories but such a dataset with an even larger label space is common in real-world problems.\n\n2. Is the methods still effective/better if we only fine-tune the final layer of the classifier (the layer before softmax)?  According to the experimental results of the related paper [1], label shift is arisen by the last layer of the classifier if the classifier is trained on the balanced training dataset.\n\n3. I fail to find the difference between \"Label distribution shift\" and the existing \"Label Shift\", and so it is unnecessary to introduce a new concept into the current research area. It is better to use a new title related to \"Label Shift\".\n\n[1] Guo, J., Gong, M., Liu, T., Zhang, K., & Tao, D. (2020, November). LTF: A Label Transformation Framework for Correcting Label Shift. In International Conference on Machine Learning (pp. 3843-3853). PMLR", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the section \"Main Review\"", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "6k71RuXl_ee", "reviewer": "Reviewer_BpAt", "summary": "This paper proposes a framework for studying problems in which the test time distribution of labels can change continuously, and the model can adapt in an online fashion but is not provided any ground truth test labels. Theoretical results demonstrate that, when there is label shift but no concept shift, an unbiased estimate of the expected 0-1 loss and its gradient can be computed even without test labels. Using this insight, two online learning methods are proposed for this setting that outperform non adaptive base and oracle models in CIFAR-10 and arXiv classification problems.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Originality\n---\nTo the best of my knowledge, this paper proposes a novel problem setting, produces novel theoretical results, and provides novel empirical methods. However, I am not an expert in the topics of online learning and label distribution shift.\n\n\nQuality\n---\nThis paper is of relatively high quality. I did not carefully check the proofs for correctness, but the theory appears generally sound and provides a clear direction for devising the practical methods. It is nice that the paper provides some empirical evidence as to the reasonableness of the assumptions. One additional assumption that would be good to test empirically is the core assumption of no concept shift, i.e., p ( x | y ) remaining constant. This is, of course, hard to verify or measure, but the authors could study a controlled setting in which there is control over how much p ( x | y ) changes, e.g., ImageNet superclass classification where the subclasses change over time, in order to better understand how crucial this assumption is in practice. This would also provide another set of experiments, which would help to strengthen the paper but, in my opinion, is not by itself critical.\n\nAdditionally, another natural point of comparison would be an even stronger oracle that is allowed to adapt with knowledge of the test labels, i.e., a \"standard\" online learner. This would help the reader quantify how much is lost from not having access to any labels at test time.\n\n\nClarity\n---\nThe paper is generally well written and structured. There seem to be enough details that one could reasonably expect to be able to reproduce the methods and results. In the experiments, a few additional details would be helpful for intuition:\n\n- Plots of sliding window average model accuracies (or some related quality) over the course of testing, in order to better understand how the models actually adapt and how rapidly this process occurs.\n- A visualization or description of the label distributions in the arXiv dataset, perhaps split up by year, in order to better understand the problem.\n- Some additional clarifying details about the arXiv problem setup. For example, are the data splits done by year, such that the validation set is also a different set of years (and thus also have label shift) from the training set? This seems like it could pose issues regarding model calibration and confusion matrix computation. This also appears to violate the detail in L80 about Q_0 = Q_train, so some commentary about the necessity of that assumption would also be helpful.\n\n\nSignificance\n---\nIn general, this work should be of interest to researchers studying online learning, label distribution shift, and adaptation. Furthermore, practitioners working on problems which naturally exhibit this type of test setting should also find these methods interesting. However, I cannot claim this with absolute certainty -- the paper mentions the example of medical diagnosis a few times, but there are no experiments to verify this intuition in this setting, so additional work would be needed to verify the methods' applicability to other real world problems.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors are encouraged to include additional discussion of the limitations and potential societal impacts of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of label distribution shifts in the online setting, and proposes two algorithms which guarantee low regret without the need to ever observing the true labels or losses on the test data sequence.

The paper received uniformly positive reviews. The reviewers appreciated:
- novel setting (first study of label distribution shift in the online setting), potentially important for real-world machine learning problems
- original and novel theoretical results
- comprehensive experimental study
- clarity of presentation.

Given the above, I also recommend the paper to be accepted.
Decision: Accept (Poster)