Online Feature Updates Improve Online (Generalized) Label Shift Adaptation
Authors: Ruihan Wu
Siddhartha Datta
Yi Su
Dheeraj Baby
Yu-Xiang Wang
Kilian Q Weinberger
Venue: NeurIPS 2024 poster (2024)
Keywords: label shift
online learning
Primary area: other

Abstract: This paper addresses the prevalent issue of label shift in an online setting with missing labels, where data distributions change over time and obtaining timely labels is challenging. While existing methods primarily focus on adjusting or updating the final layer of a pre-trained classifier, we explore the untapped potential of enhancing feature representations using unlabeled data at test-time. Our novel method, Online Label Shift adaptation with Online Feature Updates (OLS-OFU), leverages self-supervised learning to refine the feature extraction process, thereby improving the prediction model. By carefully designing the algorithm, theoretically OLS-OFU maintains the similar online regret convergence to the results in the literature while taking the improved features into account. Empirically, it achieves substantial improvements over existing methods, which is as significant as the gains existing methods have over the baseline (i.e., without distribution shift adaptations).

Online Feature Updates Improve Online (Generalized) Label Shift Adaptation
Ruihan Wu"
Siddhartha Datta" f University of Oxford siddhartha datta@cs ox. ac. uk
Yi Su Google DeepMind vissuntt@googge.com com
UC San Diego ruw0760ucsd. edu
Dheeraj Baby
Yu-Xiang Wang
Kilian Q. Weinberger Cornell University
UC Santa Barbara dheeraj@ucab. edu
UC San Diego yuxiangw@ucsd. edu
kilian@cornell edu
Abstract
This paper addresses the prevalent issue of label shift an online setting with missing labels, where data distributions change over time and obtaining timely labels is challenging. While existing methods primarily focus on adjusting or updating the final layer of pre-trained classifier, explore the untapped potential enhancing feature representations using unlabeled data at test-time. Our novel method, Online Label Shift adaptation with Online Feature Updates (OLS-OFU), leverages self-supervised learning to refine the feature extraction process, thereby improving the prediction model. By carefully designing the algorithm, theoretically OLS-OFU maintains the similar online regret convergence to the results in the literature while taking the improved features into account. Empirically, it achieves substantial improvements over existing methods, which is as significant as the gains existing methods have over the baseline (i.e., without distribution shift adaptations).
Introduction
The effectiveness most supervised learning models relies on a key assumption that the training data and test data share the same distribution. However, this assumption rarely holds in real- world scenarios, leading to the phenomenon of distribution shift [41, 2]. Previous research has primarily focused understanding distribution shifts in offline batch settings, where single shift occurs between the training and test distributions [33, 45, 51, 52, 35). In contrast, real-world applications often involve test data arriving in online fashion, and the distribution shift can continuously evolve over time. Additionally, there is another challenging issue of missing and delayed feedback labels, stemming from the online setup, where gathering labels for the streaming data in timely manner becomes a challenging task.
To tackle the distribution shift problem, prior work often relies additional assumptions regarding the nature of the shift, such as label shift or covariate shift [43]. this paper, we focus on the common (gemeralized) label shift problem in online setting with missing labels [49] Specifically, the learner given a fixed set of labeled training data Dy ~ pirain in advance and trains a model fo- During test- time, only small batch of unlabelled test data S, Ptest arrives in online fashion (t 1.). For the online label shift, we assume the label distribution prest (y) may change over time while the conditional distribution remains the same, i.e. Plest (xrly) pirain (xly). For example, employing MRI image classifiers for concussion detection becomes challenging as label shifts emerge from
Equaa contribution
Work done while Comell University
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Offline train stage
time step 1, ...,
Online test stage
P-
Labeled train data
(i) (1))
f
Unlabeled test samples Si = (x)) .af)
Make prodictions on by
Update to f.,
Vs. (61 s0) ~ plas
Vi. ~ plrst
Figure 1: Overview of online distribution shift adaptation. We further assume Pi (xly) pirain (xly) for online label shift and assume the existence of an unknown feature mapping such that Plest (1((z) w) = (ptrai(((())) for online generalized label shift.
seasonal variations in the image distribution. A classifier trained during skiing season may perform poorly when tested later, given the continuous change in image distribution between skiing and non-skiing seasons. In contrast to label shift, the generalized label shift relaxes the assumption of an unchanged conditional distribution on x given y. Instead, it assumes that there exists a transformation h of the covariate, such that the conditional distribution (h(=)(((x))) same. Reiterating our example, consider an MRI image classifier that undergoes training and testing at different clinics, each equipped with MRI machines of varying hardware and software versions. As a result, the images may display disparities in brightness, resolution, and other characteristics. However, feature extractor h exists, capable of mapping these variations to the same point in the transformed feature space, such that the conditional distribution P(h(x))ly) remains the same. In both settings, the goal of the learner to adapt to the (generalized) label shift within the -on-statoonary environment, continually adjusting the model's predictions in real-time.
ptrain (h(x)) y) stays the
Existing algorithms for online label shift adaptation (OLS) primarily adopt one of two approaches: either directly reweighting of the pretrained classifier fo. or re-training only the final linear layer of fo while keeping the feature extractor frozen. Recent work [46, 48, 36, 39] have demonstrated the potential for improving feature extractors, even during test-time and in the absence of labeled data. We hypothesize that similar effect can be harnessed in the context of (generalized) label shift, leading to the idea of improving feature representation learning during testing. In online label shift, updating the feature extractor offers two potential advantages. First, it utilizes the additional unlabeled samples, hence enhancing the sample efficiency of the feature extractor. Second, it enables the feature extractor adapt to label shift, which crucial to the learning process as the optimal feature extractor may depend on the underlying label distribution. Particularly in generalized label shift scenarios, where the feature transformation h is often unknown, the integration of extra unlabeled test samples facilitates the learning of h.
Building upon this insight, this paper introduces the Online Label Shift adaptation with Online Feature Updates (OLS-OFU) framework, aimed at enhancing feature representation learning in the context of online label shift adaptation. Specifically, each instantiation of OLS-OFU incorporates self- supervised learning method associated with a loss function denoted as last for feature representation learning, and an online label shift adaptation (OLS) algorithm to effectively address distribution shift. By carefully checking the existing OLS methods and SSL methods, we identify three principles for algorithm design: maintain the theoretical guarantee, obey the underlying assumption of the existing OLS methods and fit the required condition of SSL techniques while avoiding heavy additional computational costs. Within the principles, OLS-OFU is designed as three main steps: at each time step,
first executes a revised OLS algorithm and then every steps, OLS-OFU updates the feature extractor through self supervised learning and subsequently refines the final linear layer.
In addition to its ease of implementation and seamless integration with existing OLS algorithms, OLS-OFU also shows strong theoretical guarantee and empirical performance. Theoretically, we demonstrate that OLS-OFU effectively reduces the loss of the overall algorithm by leveraging self- supervised learning (SSL) techniques to enhance the feature extractor, thereby improving predictions for test samples at each time step t. Empirical evaluations on various datasets, considering both online label shift and online generalized label shift scenarios, validate the effectiveness of OLS-OFU. Our OLS- OFU method achieves substantial improvements over existing OLS methods, which is as significant as the gains existing OLS methods have over the baseline (i.e., without distribution shift adaptations). This demonstrates that integrating online feature updates is as effective in solving online distribution shift as the fundamental online label shift method itself. Moreover, the improvement is consistent on various datasets, all existing OLS methods and the various choices of SSL techniques. This consistency underscoring robustness across different scenarios and its generality to incorporate future OLS methods with more advanced online learning techniques and better SSL techniques.

---

2 Problem Setting & Related Work
We start with some basic notations. Let A be the probability simplex. Let X + A denote a classifier. Given an input z from domain X, f(r) outputs probabilistic prediction over K classes. For example, f can be the output from the softmax operation after any neural network. If we reweight a model output from f by vector E RK we refer to this model as f(; with g denotes the method of reweighting. For any two vectors p and q, p/q denotes the element-wise division.
Online distribution shift adaptation. The effectiveness of any machine learning model ʃ relies common assumption that the train data Do and test data Diest are sampled from the same distribution, i.c., ptrain plest However, this assumption is often violated in practice, which leads to distribution shift. This can be caused by various factors, such as data collection bias and changes in the data generation process. Moreover, once a well-trained model fo is deployed in the real world, moves into the testing phase, which is composed of a sequence of periods or time steps. The test distribution at time step t, Prest, from which test data x; is sampled, may vary over time. One example is that an MRI image classifier might be trained on MRI images collected during skiing season (which may have a high frequency of head concussions) but tested afterward (when the frequency of concussion is lower). The test stage can last several months until the next classifier is trained. During this test period, the distribution of MRI images may undergo continuous changes, transitioning between non-skiing and skiing seasons.
As the test-time distribution changes over time, the challenge lies in how to adjust the model continuously from fi-1 to ft in an online fashion to adapt to the current distribution Plest We call this problem online distribution shift adaptation and illustrate it in Figure 1. Given total of T steps in the online test stage, we define the average loss for any online algorithm A through the loss of the sequence of models fi, E [T] that are produced from A, i.e.
T L(A; , Praat T Σ ((eP)t
where E(;P)) = -aapg) y) and loup is the loss function, for example, 0-1 loss or cross-entropy loss for classification tasks.
In this paper, we consider the challenging scenario where at each time step t, only a small batch of unlabeled samples St {z) x²() is received. We formalize the algorithm A as: Vt E [T].
f = A (1S), ... S1-1h
.t- Do. D().
In contrast to the classical online learning setup, this scenario presents a significant challenge as classical online learning literature usually relies on having access to either full or partial knowledge of the loss at each time step, i.e., (su (xx) yt). In this setting, however, only a batch of unlaheled samples is provided at each time step and this lack of access label information and loss values presents a significant challenge in accurately estimating the true loss defined in Equation 1.
Online label shift (OLS) adaptation. Online label shift assumes the marginal distribution of the label plest (y) changes over time, while the conditional distribution keeps invariant:
Vt E Piest (x)p) = pirain (xly)-
This assumption most typical when the label y is the causal variable and the feature x is the observation [43]. The aforementioned example of concussion detection from MRI images fits this scenario, where the presence or absence of a concussion (label) causes the observed MRI image features. Most previous methods tackle this problem through non-trivial reduction to the classical online learning problem. Consequently, most of the online label shift algorithms [49, 7, 6] study the theoretical guarantee of the algorithm via the convergence of the regret function, which could be either static regret or dynamic regret. In previous studies, the hypothesis class F of the prediction function f is typically chosen in one of two ways:
1. F is defined as a family of post-hoe reweightings of fo. with the parameter space comprising reweight vectors. Examples within this category include ROGD [49], FTH [49], and FLHFTL [6]. F is defined as a family of functions that share the same parameters fo except the last linear
layer, such UOGD [7] and ATLAS [7].
3

---

Notice that the existing OLS methods don't update the feature extractor at the online test stage, but focus on how to leverage advanced online learning techniques to update the remaining part of the model under certain theoretical guarantees. Our method will be orthogonal to them: it will focus on how to leverage the self-supervised learning techniques to update the feature extractor and, therefore, can improve each of them. Our empirical results in fact show that the improvement from the feature extractor update is as significant as the improvement from online learning techniques.
Online generalized label shift adaptation. In the context of MRI image classification, where head MRI images serve as the feature z, variations in software or hardware across different clinies' MRI machines can introduce discrepancies in image characteristics like brightness, contrast, and resolution. In such scenarios, the conditional probability distribution P(zly) no longer invariant. However, when a feature extractor h is robust enough, it can map images into feature space where the images from different machines have the same distributions (()())))) in the transformed feature space. The concept of generalized label shift, as introduced in Tachet des Combes et al. [47], formalizes this by postulating the existence of an unknown function ht such that (h)(2)) (3) remains invariant. The primary challenge in this context is to find the underlying transformation h. Building upon this, online generalized label shift assumes that there exists an unknown function /t such that
Vt E [2], Plest (h(x)) = ptrain (h())ly).
Thus, to apply the OLS methods for this more general problem, it is important to learn a proper feature extractor as this underlying function h.
Motivations of deploying self-supervised feature updates. As we reviewed above, OLS methods in the literature don't 't update the pretrained feature extractor in the online stage. However, the pretrained feature extractor in fo can be suboptimal for the online test stage in online (generalized) label shift adaptation, because of the three potential reasons:
The amount of pretrained data doesn't achieve the learning capacity of the feature extractor structure, i.e. learning with more data can improve the feature extractor.
2. The optimal feature extractors can be different for two different distributions. In our problem, the distribution shifts overtime and the optimal feature extractor can be dynamic too.
3. Particularly in online generalized label shift adaptation, the domain of the data can be dramatically changed between train and test, and the pretrained feature extractor could have unpredictable performance for the test data.
Fortunately, in online (generalized) label shift adaptation problem, the learner receives many unlabeled test samples S₁ -... U S before the prediction for time step t. On the other hand, self-supervised learning is very powerful for representation learning [18, 32, 30, 16, 37, 9, 23, 20, 24] and domain adaptation [46, 48, 36, 39J. In this paper, we will introduce how to deploy these self-supervised learning techniques to the existing OLS methods such that we can still enjoy the theoretical guarantees from online learning techniques and, more importantly, take the advantage of self-supervised learning to achieve better empirical performance.
3 Method
In this paper, we introduce novel online label shift adaptation algorithm OLS-OFU, that leverages self-supervised learning (SSL) to improve representation learning and can be seamlessly integrated with any existing online label shift (OLS) method. By carefully designing how to place the SSL techniques, our algorithm maintains a similar theoretical guarantee from the existing OLSS methods, obeys the underlying assumption in existing OLS methods that is important for the effectiveness, and fits the required condition of the SSL techniques while avoiding heavy additional time cost. Through the derived theoretical results, we further understand how the online learning techniques and SSL techniques contribute together to reduce the test loss in the online label shift adaptation problem. Lastly, we demonstrate how the SSL techniques help with the more challenging problem online generalized label shift adaptation.
3.1 Three Principles of Algorithm Design.
To combine the step of feature extractor update with any OLS method, the most straightforward thought is to directly insert this step right before or after the step of original OLS in each time step;

---

see the summarization of the online process in Figure 1. Starting from this thought, there are three remaining questions before finalizing the algorithm: Q1: Inserting this step before or after the original OLS step, which option is better? Q2: Besides this feature extractor update step, are any other steps also necessary? Q3: How frequently (in terms of time step 1) should we update the feature extractor? We are going to introduce three principles when designing our algorithm, which helps answer the three questions and together lead to our final design.
Principle I: maintain the theoretical guarantee. One main advantage of existing OLS methods is that they have theoretical guarantees for the performance of any unknown label shifts in the online test stage. We would like to keep this advantage after deploying the feature extractor update step. By carefully checking the theoretical analysis of the existing OLS methods, we find that when we deploy the feature extractor update into ROGD, UOGD, or ATLAS, if we would like to update the feature extractor by the unlabeled test samples including S,, is necessary to execute this update after the step of these OLS methods at time i to maintain the similar theoretical guarantee. This is because the main idea of ROGD, UOGD, and ATLAS is to construct an unbiased estimator for the gradient V Vf((ft P) using batch of samples Se ~ Plest, The estimator has the form of
Σ VEY
St stiyl V E (zta) sup (f((z),))
(3)
where s, is an unbiased estimator for the label marginal distribution qe and it depends on samples S as constructed. If the feature extractor update according to St happened before the step of ROGD, UOGD or ATLAS, ft would not be independent of in Equation 3 and this can break their main idea, as illustrated in the following proposition.
Proposition 1. If ft is not independent of the samples St, the gradient estimator in Equation 3 is not guaranteed to be an unbiased estimator of the gradient yf((r;
Thus, to maintain a similar theoretical guarantee after updating the feature extractor by the online test samples, we should insert the feature update involving St after the step of original ROGD, UOGD or ATLAS, and this answers Q1. In the experiment, we will validate the necessity of this design.
Principle 2: obey the underlying assumption of the existing OLS methods. We find that the existing OLS methods ROGD, FTH, and FLHFTL opt for the hypothesis I to be a post-hoc reweight of the pre-trained model Jo- The underlying assumption behind this design is that So is a good approximation of ptrain [z) Within this assumption, because ptest (yy 2:) is post-hoc reweight of ptrain (y/22 2)) in the case of label shift [34, 49], reweighting such fo can approach plest (y|z). Therefore, after updating the feature extractor, we expect that the base model, which is to be reweighted, still approximates the training distribution ptrain (y)z). This can be done by re-training the linear layer under the training data after the feature extractor update, and this answers Q2.
Principle 3: fit the required condition of the SSL techniques while avoiding heavy additional computational costs. Given set of unlabeled samples S, we denote the loss of an SSL technique for a model / as E (S; J)) and the update to this model would be in the form of gradient descent: great + gfiat - V eaa ; f), where 77 is the learning rate. We notice that the batch size [S] cannot be very small. Otherwise. the update can be too noisy due to the data variance or some types of SSL whose benefit replies on large batch sizes, such as contrastive learning [9, 23], would lose this benefit. However, online (generalized) label shift problem assumes we only have a small batch of unlabeled samples St at time t; the batch size is set as or 10 in the experiment of literature. Therefore, for the effectiveness of SSL techniques, instead of updating the feature extractor each time step by S,, we opt to accumulate the sample batch Sre U... U Sr(e+1) and update the feature extractor once every T time steps, and we call it batch accumulation.
Besides the help of effectiveness, batch accumulation also helps with time efficiency. The existing OLS methods only involve the updates for the small reweighting vector or the linear layer and the time cost is low. However, updating the feature extractor and re- re-training the linear layer on the full training set, which are introduced in Principle 2, are much computationally heavier. For example, when we evaluated the methods in the experiment with ResNet18 on CIFAR 10 dataset, one step of FLHFTL only took 0.069 second, while one step of FLHFTL together with feature extractor update and linear layer re- re-irnnn took 17.1 seconds, which is 247 times. After applying batch accumulation and we select
100, the additional time costs will be reduced by (T - 1)/T 99%.
Batch accumulation answers Q3 we should update the feature extractor every T steps for effective- ness and time efficiency. We will study how batch accumulation helps in the experiments.
5

---

Algorithm 1 Online label shift adaptation with online feature updates (OLS-OFU).
Require: An online label shift adaptation algorithm OLS, self-supervised learning loss Eaal A pre-trained model fo and initialize f1 = =I" == fo- fort= 1,............. T do
Input at time I: Samples S₁ U U...UU S,, models [_,,,... ; train set Do. validation set Dÿ- 1. Run the revised version of OLS, that is, OLS-R, and get fi+1-
If 1%T * 0, ft+1 == J'+1. fi+ := Jx' Else, go to the next step 2-3.
2. Update the feature extractor ofone in f:+1 by Equation 4. Replace Ofeat in f241 by 6feat-
3. Re-train the last linear layer by Equation 5, calibrate the model and get f241-
Output at time t: For the reweighting OLS methods, denote the latest reweighting vector from
Step is 1++1 and we define Jr+1 == 1. else, we define S2+1 == s'+11.
end for
3.2 Online Label Shift Adaptation with Online Feature Updates
We have discussed three principles and now we can finalize our algorithm Online Label Shift adaptation with Online Feature Updates (OLS-OFU; Algorithm I), which requires self-supervised learning loss (x) and one of existing OLS methods the literature, which either reweights the offline pre-trained model fo or updates the last linear layer. In the training stage, we train fo by minimizing the supervised and self-supervised loss together defined on train data. In the test stage, OLS- OFU comprises three steps at each time step L: (1) running the refined version of OLS, which we refer to as OLS-R, (2) updating the feature extractor, and (3) re-training the last linear layer. As suggested by Principle 3 in Section 3. steps (2-3) only run every steps. We illustrate the details of these three steps are elaborated below.
(1) Running the Revised OLS. At the beginning of the time t, we use f. to denote the model within the latest feature extractor and the re-trained linear model (using data {Sp. S,-1)). The high level idea of our framework centers on substituting the pre-trained model fo used in existing OLS methods with our updated model f.". which we call OLS-R. To provide an overview, we examine common OLS methods (FLHFTL, FTH, ROGD, UOGD, and ATLAS) and identify two primary use cases of fo. Firstly, all OLS methods rely on an unbiased estimator 8; of the label distribution gr and So is part of the estimator. Secondly, the hypothesis f is some weights of reweighting the fo output or only the last linear layer in so is updated. We illustrate all revised OLS methods formally in Appendix C. We use f to denote the model after running the OLS-R.
(2) Updating the Feature Extractor. As guided by Principle in Section 3.1, the step of updating the feature extractor should be after the Revised-OLS module (step (1)) for theoretical guarantees. We now introduce how to utilize the SSL loss Eaal to update the feature extractor based on the accumulated batch of unlabeled test data STe U... US...U) at timestep t T(c+ 1). Specifically, let @foat denote the parameters of the feature extractor in f1+1- The update of ofout is given by:
great == gfeat 17. V ginne (St U... U S Sr fet1)
(4)
Then we update the feature extractor in fi+1 with Ofont.
(3) Re-training Last Linear Layer. Principle 2 in Section 3.1 suggests this step of re re-training the last linear layer on the training distribution. The re- re-training starts from random initialization while the feature extractor remains frozen. The training objective of 8lincar is to minimize the average cross-entropy loss over train data Do. We denote the model with the frozen feature extractor 0+1 as f-10ffrtt 11 glinear) The objective for re-training the last linear layer can be written as follows:
Loo (ftoldeet Jlueear) ),
0 glinear arg min
Σ (z,2))Do
Oriment
We calibrate the model f-1@ffet, @linear) by temperature calibration [21] using the validation set D/ and denote the model after calibration as f#
Output at time l. Finally, we define fe+1 for the next time step prediction. For the reweighting OLS methods (ROGD, FTH, FLHFFTI), denote the latest reweighting vector from Step 1 as Pt+1 and define fi+1 g6: f Pt+1). For those which optimize the last linear layer (UOGD, ATLAS),

---

define fi+1 := fi+1 as stated in Principle 2 in Section 3.2, the f including retrained last linear layer serves specially for the reweighting OLS method.
The requirement of the training data. Notice that in step (3), we need the training data to retrain the linear classifier, which potentially brings the additional cost of memory and computation in the test time. As discussed in Principle 2 and lines 248-252, retraining the last linear layer is designed only for three previous OLS methods (ROGD, FTH, FLHFTL); our algorithm for two other OLS methods (UOGD and ATLAS) in the literature are independent of this step. As for ROGD, FTH, or FLHFTL, we interestingly find that OLS- OFU without this re-training step, which means that we update the feature extractor but reuse the pretrained linear classifier, still has certain ad advantage over the original OLS methods- although more stored training data results the more significant benefit of OLS-OFU, This suggests that in practice, if we reduce the amount of stored training data due to the memory or computational constraint, OLS-OFU is still effective.
3.3 Performance Guarantee for Online Label Shift Adaptation
One main advantage of the original OLS methods is that they exhibit theoretical guarantees in terms of regret convergence for online label shift settings. Next, we will show how OLS-OFU demonstrates analogous theoretical guarantees with the incorporation of additional online feature updates. Due to limited space, we illustrate the theoretical results pertaining to FLHFTL-OFU here, and present the results for ROGD-OFU, FTH-OFU, JOGD-OFUL and ATLAS-OFU in Appendix D.
Theorem 1. (Regret convergence for FLHFTL-OFU] Suppose we choose the OLS-R to be FLHFTL. R (Algorithm 6) from Baby et al. [6]. Let ft ffinftl be the output at time step t - 1 from Algorithm 1, that is g(: Jt', ).). Under Assumptions I and 2 in Baby et al. [6], FLHFTL-FFU has the guarantee:
E
( ffihhtl-ot ofu, plest)
S
E
T
Elgltsh' 2:
)): Ptestt
+0
K K2/0 1//0v//3
1/3
+
K
T
T1/3
VT
(6)
where VT =- -Et= - K is the number of classes, and the expectation is taken w.r.l. randomness in the revealed co-variates. This result is attained without prior knowledge of Vr.
How do online feature updates contribute the bound? We observe that the upper bound of the test loss has two terms. The first term is the loss of the model within the up-to-date feature extractor when the knowledge of label distribution qi is known. Any improvement from SSL could be reflected in this first term. The second term is to quantify the loss gap between the knowledge of label distribution dr and the estimation of the label distribution by the online learning technique.
When do online feature updates improve the guarantee from FLHFTL to FLHFTI-OFF? If we do not make any update to the feature extractor (i.e. ft for Vt), the upper bound in Equation would be naturally reduced to the theoretical guarantee of FLHFTL [6]. Moreover, in the following event of f (t E [T]):
E
T Σ
elols Ji, 3); Phestt qo
llols fo, go
2 P!:ttt)))
T
our theorem will guarantee that the loss of FLHFTL-OFU converges to a smaller value than the one of the original FLHFTL, resulting in a better upper bound. We substantiate this improvement through empirical evaluation in Section 4.
3.4 Online Feature Updates Improve Online Generalized Label Shift Adaptation
The generalized label shift is harder because the feature map h is unknown and naively applying OLS methods might raise the challenge due the violation of the label shift assumption. Fortunately, existing research in test-time training (TTT) [46, 48, 36, 39] demonstrates that feature updates driven by SSL align the source and target domains in feature space. When the source and target domains achieve perfect alignment, such feature extractor effectively serves as the feature map h as assumed in generalized label shift. Therefore, the sequence of feature extractors in fi, , .r generated by Algorithm 1 progressively approximates the underlying h. This suggests that, compared to the original OL., OL---OF experiences a milder violation of the label shift assumption within the feature space and is expected to have better performance in online generalized label shift settings.
7

---

Basc
OLS
OLS OFU
Rotation Prediction
Minimization
(N4
Error (N)
Error 0h)
PTPON PTM RONG A11.0 UOOD FLMPTL
PTPAN
RONG A1L.8
U000 FLMPTT
PTM
ROOD AILON
BOGD FLMPIL
Mathods
(a) Results CIFAR-I0 for three SSL. methods in OLS-OFU (Sinusoidal shift)
STL10
EuroSAT
Error (%)
Error (%)
OLS Methods
OLS Methods
OLS Methods
(b) Results on three more datasets (rotation degree prediction, Sinusoidal shift)
Gaussian Noise
Fog
Pixelate
Errer (%6
Envor (%6
FTAMM
FTH
ROGD ATLAS
DOGD FUNNFLL
FTPMM
FTH
ROGD ATLAS UOGO FUR-FL
FTH
ROGD ATLAS
DOGD FIN-FTL
(c) Results three types of corruptions in CIFAR-IOC (rotation degree prediction, Sinusoidal shift)
Figure 2: Evaluation of OLS and OLS-OFU.
FTFWH
FTH
ROGD
ATLAS
UOGD
FI.H-FTI.
OLS
11.9% 00.41
12.04% / 0.705
13.65%
00.937
12.18%
43.2
11.54% 297
12.02% 11.15
S-ORU (r = 1)
11.3% 283
11.2% / 286
13.9% 385
11.6%
11.4% /19
11.2% 285
OLS-OFU 10)
9,93%
28.8
10.2% / 29.6
13.1% /4.9
/45.1
/00
9.93% / 29.9
OLS- 50)
8.15% / 6.47
8.89% / 6.91
12% / 99.49
11.3% /4.88
9.27% /:3
8.27% / 7.08
OLS-OFU (7 = 1000)
7.33% 3.57
8% 3.85
10.8% 5.29
10.1% /44.2
8.35% 303
7.45% / /4.15
OLS-OFU (r = 500)
11.6% / 1.27
11.7% / 1.53
13.5% 2.09
12.1% /43.6
11.3% 298
11.7% / 1.94
Table 1: Average error/time (minutes) of 6 original OLS methods versus OLS-OFU with various
frequency T in batch accumulation. The SSL in OLS-OFU is the rotation degree prediction.
Experiment
In this section, initiate OLS-OFU with three popular SSL techniques and empirically evaluate how OLS-OFU improves the original OLS methods on both online label shift and online generalized label shift on various datasets and shift patterns".
4.1 Experiment Set-up
Dataset and Label Shift Settings. For online label shift, we evaluate the efficacy of algorithm on CIFAR-10 10 [29]. STL [12], CINIC [13], and EuroSAT [25]. For each dataset, we split the original train set into the offline train (i.e., Do) and validation online test stage, unlabeled batches are sampled from the test set. For online generalized label shift, the offline train and validation sets are the CIFAR- 10 images. The test unlabeled batches are drawn from CIFAR-IOC [26]. a benchmark with the same objects as CIFAR-10 but with various types of corruption. We experiment with three types of corruptions with CIFAR-10C: Gaussian noise, Fog,
(i.e., D)) following ratio of 1. At the
CCode released https: : hhmps:///gttan /ttgtttttb..///////////gtt www./atttasi.dcaaaaaaaaacco htt.://mn-----eeteau--ee-----ee olsofu

---

FTFWH
FTH
ROGD
ATLAS
UOGD
FLHFTL
OLS-OFU(T = 1)
11.3%
11.2%
13.9%
11.6%
11.4%
11.2%
OLS-OFU-diifooderrt = 1)
12.33%
12.12%
14.35%
12.10%
11.91%
12.08%
OLS-OFU(T = 100)
7.23%
7.91%
10.81%
10.12%
8.33%
7.53%
OLS- OLS-OFU-difforder( 100)
8.02%
8.63%
11.19%
10.55%
8.80%
8.29%
Table 2: Ablation study on the order between OLS and the feature update step in OLS-OFU.
and Pixelate. We follow Bai et al. [7] and Baby al. [6] to simulate the online label distribution shift with two shift patterns: Sinusoidal shift and Bernoulli shift. We experiment with 7 = 1000 and batch size B 10 at each time step. following Baby et al. [6]. See more details of dataset set-up and online shift patterns in Appendix E.
Evaluation Metric. We report the average error during test, i.c., TB Σx Ex,es, 1 (fe(tr) + ye). where (Ize (t) ~ Piest, to approximate + Σx E(fri Plont) for the evaluation efficiency.
Self-supervised learning methods in OLS-OFU. In the experiment, we narrow our focus on three particular SSL techniques in the evaluation for classification tasks: rotation degree prediction [16, 46], entropy minimization [18, 48] and MoCo [23, 10, 11]. It is important to note that this concept extends beyond these three SSL techniques, and the incorporation of more advanced SSL techniques to further elevate the performance. Appendix E. gives more details of these SSL techniques.
Set-ups of OLS methods, OLS-OFU and baselines. We perform extensive evaluation of 6 OLSS methods in the literature: FTFWH, FTH, ROGD, UOGD, ATLAS, and FL.HFTI by following the implementation in Baby et al. [6]. We report the performance of our method OLS-OFU (Algorithm applied on top of each OLS and SSL methods introduced above. The frequency parameter r is fixed as 100 for most experiments unless we particularly mention it. Additionally, by following the setup in [49, 6], we report one baseline score Base, which uses the fixed pre-trained model fo to predict the labels all time steps.
4.2 Results
comparison between OLS-OFU and OLS under online (generalized) label shift. Figure 2(a) shows the performance comparison between OLS-OFU, implemented with three SSL methods, and their corresponding OLS counterparts on CIFAR-10 under the scenario of classical online label shift. Figure 2(b) shows the results on three more datasets with SSL technique in OLS-OFU being rotation degree prediction. Figure 2(c) shows the results on CIFAR-1OC datasets for evaluating methods on online generalized label shift. The online shift pattern in Figure 2 is the sinusoidal shift and similar results on the Bernoulli shift are Appendix F.2. We have two main observations from the results. First, find our OLS-OFU method achieves substantial improvements over existing OLS methods, which is as significant as to the gains existing OLS methods have over the baseline (i.e., without distribution shift adaptations). This demonstrates that integrating online feature updates is as effective in solving online distribution shifts as the fundamental online label shift method itself. Second, the improvement is consistent across all six original OLS methods and three SSL techniques on all datasets, which further demonstrates our OLS-OFI is general enough to incorporate future OLS methods and more advanced SSL techniques as well.
Main Results:
Validating Principle 1: ablation study on the order between OLS and the feature update step in OLS-OFU. We compare OL--OFU with its other variant named OLS-OFU-ddifforde where we update SSL first and run OLS later (which violates Principle 1). We compare these two algorithms 1 and 100. The
across all previous 6 OLS methods and two choices of batch accumulation dataset CIFAR- 10, the SSL is rotation degree prediction and the shift pattern is the sinusoidal shift. We report the average error every time step when the feature extractor is updated, so the order matters. From Table 2, we can observe that benefiting from Principle 1, the error OLS-OPF is consistently lower than OLS-OFU-diffodder This means that Principle 1 indeed is not only necessary for the correctness of theoretical guarantee but also plays an important role in practice.
Validating Principle 3: ablation study on frequency in batch accumulation in OLS-OFU. In section 3. 1, we introduce the batch accumulation to flavor the effectiveness of the SSL and reduce the additional time cost of OLS-OFU compared with the original OLS methods. In Table 1,

---

% Stored Training Data
100%
80%
60%
40%
20%
10%
5%
0%
OLS only
FTH-OFU
8%
8.18%
8.68%
9,49%
9.54%
9.67%
9.81%
10.24%
12.04%
ROGD-OFU
10.8%
10.93%
11.84%
12.30%
12.63%
12.82%
12.94%
13.50%
13.65%
FLHFTL-OFU
7.45%
7.62%
8.04%
8.91%
9.51%
10.11%
10.34%
10.43%
12.02%
FTYWH-OFF
7.33%
7.48%
7.92%
8.40%
8.91%
9.86%
10.03%
10.41%
11.9%
Table 3: The effectiveness OLS-OFU versus the percentage of stored training data in step (3).
evaluate OLS-OFU on CIFAR-10 with various T while initiating OLS-OFU with rotation degree prediction and compare the average eπror and time with OLS. We have these observations across all OLS (columns): 1. OLS-OFU with all 7 outperforms OLS; The average error of OLS-OFU decreases from r = 1 (w/o batch accumulation) to 100 and starts to increase after and this is because the effectiveness of SSL benefits from T > 1 while larger 7 means less updates and hence hurts the long term performance; 3. the additional time cost of OLS-OFU with larger 7 is smaller and t 100 gives a great balance of performance and time cost for all OLS (and SSL; the similar tables for other two SSL are presented in the Appendix E.3). From the results, we recommend good starting point for choosing this parameter.
100 as
Ablation study on the amount of stored training data in step (3). We further study how the amount of training data stored influences the effectiveness of our OLS-OFU when the OLS is ROGD, FTH, or FLHFTL. which is dependent on step (3). We experiment with the CIFAR-10 dataset and the shift pattern of sinusoidal shift; the SSL. chosen as rotation degree prediction. The percentage of stored training data (out of the whole training set of size 10,000) is varied in (100%, 80%, 60%, 40%, 20%, 10%, 5%, 0%); 0% means that we still update the feature extractor but reuse the pretrained linear classifier. The results are reported in Table 3. We can observe that with less stored training data for retraining the last linear layer, the error OLS-OFU would increase gradually. However, an important finding is that even with 0% stored training data, the error of OLS-OFU is still lower than the OLS without feature extractor updates. This can actually explained by the original test-time training papers [46, 48, 36, 39], where they only update the feature extractor without refining the last linear layer and still have substantial benefit. The results suggest that a large amount of stored training data is not necessary for the effectiveness of data can bring more benefits.
while more stored
Empirical validation of Equation 7. In Section 3.3, we argued that when the in- equality in Equation 7 holds, the loss of FLHFTL-OFU exhibits a tighter upper bound compared to FLHFTL. Figure 3 presents the RHS (corresponds to OLS) and LHS (corresponds to OLS-OFU with SSL loss as rotation degree prediction) of Equation 7. We perform the study over eight different settings and vary the domain shift and online shift patterns. It is evident that OLS-OFU yields improvements on the baseline of the regret shown in Equa- tion 7. Appendix E.4 validates this inequality for other SSL.
Rotation Degres Prediction
OL5-FFI
Entor PM
Oben 1963
Ose deci
Gemta din) cauth 1800) Fog 15P-)
Fng lher)
PS. Smn
PRc (861)
Type)
Figure 3: Empirical validation of Equation 7. Clean denotes the experiment on CIFAR-IO, and others denote the corruption type. They are paired with two online shift patterns: Sinusoidal and Bernoulli.
Conclusion and Future Work
We focus on online (generalized) label shift adaptation and present novel framework OLS-OFU, which harnesses the power of self-supervised learning enhance feature representations dynamically during testing, leading to improved predictive models and better test time performance.
Discussion and future work. One promising direction is to extend the idea of this paper to online covariate shift, for example, the algorithm in Zhang et al. [53] freezes the feature extractor and only updates the linear layer. Another possible direction is to consider more realistic domain shift scenario within the generalized label shift setting - domain shift types may vary over time or be more challenging, such as shifting from cartoon images to realistic images.
10

---

Acknowledgments and Disclosure of Funding
RW and KQW are supported by grants from LinkedIn, DARPA Geometries of Learning, and the National Science Foundation NSF (1934714), RW is also supported by grants from the National Science Foundation NSF (CIF-2402817, CNS-1804829), SaTC-2241 CCF-2217058, ARO- MURI (W911NF2110317), and ONR under N00014-24-1-2304 YW and DB are partially supported by NSF Award #2134214.
References
[1] A. Alexandari, A. Kundaje, and A. 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.
[2] D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané. Concrete problems ai safety. arXiv preprint arXiv:1606.0000
2016.
[3] E. Arazo, D. Ortego, P. Albert, N. E. O'Connor, and K. McGuinness. Pseudo-labeling and confirmation bias in deep semi-supervised learning. In 2020 International Joint Conference on Neural Networks (ICCNN). IEEE, 2020.
[4] K. Azizzadenesheli, A. Liu, F. Yang, and A. Anandkumar. Regularized learning for domain adaptation under label shifts. In International Conference on Learning Representations, 2019.
[5] D. Baby and Y--.. Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In International Conference on Artificial Intelligence and Statistics, pages 1805-1845. PMLR, 2022.
[6] D. Baby, S. Garg, T.-C. Yen, S. Balakrishnan, Z. C. Lipton, and Y.-.. Wang. Online label shift: Optimal dynamic regret meets practical algorithms. To appear at Advances in Neural Information Processing Systems, 2023.
[7] Y. Bai, Y.-J. Zhang, P. Zhao, M. Sugiyama, and Z.-H. Zhou. Adapting online label shift with provable guarantees. Advances in Neural Information Processing Systems, 35:29960-299747 2022.
[8] O. Besbes, Y. Gur, and A. Zeevi. Non-stationary stochastic optimization. Operations research, 6365):1227-1244, 2015.
[9] T. Chen, S. Korbblith, M. Norouzi, and G. Hinton. A simple framework for contrastive learning of visual representations. In International conference on muchine learning, pages 1597-1607, PMLR, 2020.
[10] X. Chen, H. Fan, R. Girshick, and K. He. Improved baselines with momentum contrastive learning. arXiv preprint Sitiv::0003042297, 2020.
[11] X. Chen, S. Xie, and K. He. An empirical study of training self-supervised vision transformers. In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pages 9620-9629, Los Alamitos, CA, USA, oct 2021. IEEE Computer Society. doi: 10.1109/CCV44992222220.0000 1199/ICVV49922. 2021 00950.
URL https: ieeecoopttersocietyy. org/10.
[12] A. Coates, A. Ng, and H. Lee. An Analysis of Single Layer Networks in Unsupervised Feature Learning. In AISTATS, 2011. https://cs stanford. edu/ aataa//ccaatt//paprraaa coatesleeng. Btt_lleenn_isttt______ aistats_2011 caattts_211..ddi
[13] L. N. Darlow, J. Crowley, A. Antoniou, and A. Storkey. Cinic- 10 is not imagenet or 10, 2018.
[14] S. Garg, Y. Wu, S. Balakrishnan, and Z. C. Lipton. A unified view of label shift estimation. arXiv preprint arXiv:2003.075544 2020.
[15] S. Garg, N. Erickson, J. Sharpnack, A. Smola, S. Balakrishnan, and Z. Lipton. Risbench: Domain adaptation under relaxed label shift. In International Conference on Machine Learning (ICMI), 2023.
[16] S. Gidaris, P. Singh, and N. Komodakis. Unsupervised representation learning by predicting image rotations. In International Conference on Learning Representations, 2018. URL https: //openeeview net stte/foormiidddS11li.

---

[17] Y. Grandvalet and Y. Bengio. Semi- Semi-super learning by entropy minimization. In L. Saul, Y. Weiss, and L. Bottou, aditors, in Neural Information Processing Systems, volume 17. MIT Press, 2004. URL http:tt:ppp/occceeeiiiaaoo neurips. cc/paper f files /slees/ppper/0044 file/ http////6650000111aaa00020000000
Paper .df.
[18] Y. Grandvalet and Y. Bengio. Semi-supervised learning by entropy minimization. Advances in neural information processing systems. 17, 2004.
[19] A. Gretton, A. Smola, J. Huang, M. Schmittfull, K. Borgwardt, and B. Schölkopf. Covariate shift by kernel mean matching. Dataset shift in machine learning, 3(4):5, 2009.
[20] J.-B. Grill, F. Strub, F. Altché, C. Tallec, P. Richemond, E. Buchatskaya, C. Doersch, B. Avila Pires, Z. Guo, M. Gheshlaghi Azar, et al. Bootstrap your own latent-a new ap- proach to self-supervised learning. Advances in neural information processing systems, 33: 21271-21288 2020.
[21] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks. In International conference machine learning, pages 1321-1330. PMLR, 2017.
[22] E. Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. In Electronic colloquium on computational complexity (ECCC), volume 14, 2007.
[23] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9729-9738, 2020.
[24] K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. Girshick. Masked autoencoders are scalable vision learners. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 16000-16009, 2022.
[25] P. Helber, B. Bischke, A. Dengel, and D. Borth. Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 12(7):221722266 2019. doi: 10. 109/STTARSS 2019. 2918242.
[26] D. Hendrycks and T. Dietterich. Benchmarking neural network robustness to common corrup- tions and perturbations. arXiv preprint arXiv: 000003//220: /226/, 2019.
[27] Hoffman, T. Darrell, and K. 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.
[28] Huang, A. Gretton, K. Borgwardt, B. Schölkopf, and A. Smola, Correcting sample selection bias by unlabeled data. In Advances in neural information processing systems, volume 19, pages 601-608. Citeseer, 2006.
[29] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[30] S. Laine and T. Aila. Temporal ensembling for semi-supervised learning. arXiv preprint arXiv:161000224.. 2016.
[31] D.-H. Lee. Pseudo-label: The simple and efficient supervsee learning method for deep neural networks. ICML 2013 Workshop: Challenges in Representation Learning, 2013.
[32] D.-H. Lee et al. Pseudo-label: The simple and efficient semi- uumissupervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML., volume 3, page 896. Atlanta, 2013.
[33] Y. Lin, Y. Lee, and G. Wahba. Support vector machines for classification in nonstandard situations. Machine learning, 46(1):191-202 2002.
[34] Z. Lipton, Y.-X. Wang, and A. Smola. Detecting and correcting for label shift with black box predictors. In International Conference on Machine Learning, 2018.
[35] Z. Lipton, Y.-X. Wang, and A. Smola. Detecting and correcting for label shift with black box predictors. In International conference on machine learning, pages 3122-3130. PMLR, 2018.
[36] Y. Liu, P. Kothari, B. Van Delft, B. Bellot-Gurlet, T. Mordan, and A. Alahi. Tit++: When does self-supervised test-time training fail or thrive? Advances Neural Information Processing Systems, 34:21 808021820000000 2021.
12

---

[37] T. Miyato, S.-i. Maeda, M. Koyama, and S. Ishii Virtual adversarial training: a regularization method for supervised and semi- -upeevieee learning. IEEE transactions on pattern analysis and machine intelligence, 41(8):1979-199) 2018.
[38] R. T. Mullapudi, S. Chen, K. Zhang. D. Ramanan, and K. Fatahalian. Online model distillation for efficient video inference. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3573-3582, 2019.
[39] S. Niu, J. Wu, Y. Zhang. Y. Chen, S. Zheng, P. Zhao, and M. Tan. Efficient test-time model adaptation without forgetting. In International conference machine learning, pages 16888- 16905. PMLR, 2022.
[40] Y.-Y. Qian, Y. Bai, Z.-Y. Zhang, P. Zhao, and 7. Zhou, Handling new class in online label shift. In 2023 IEEE International Conference on Data Mining (ICDM), pages 1283-1288. IEEE, 2023.
[41] Quinonero-Candela, M. Sugiyama, N. D. Lawrence, and A. Schwaighofer. Dataset shift in machine learning. Mit Press, 2009.
[42] M. Saerens, P. Latinne, and C. Decaestecker. Adjusting the outputs of a classifier to new a priori probabilities: simple procedure. Neural Computation, 14(1):21-44 2002.
[43] B. Schölkopf, D. Janzing, J. Peters, E. Sgouritsa, K. Zhang, and J. Mooij. On causal and anticausal learning. arXiv preprint arXiv: 2012.
[44] S. Shalev-Shwartz. 2012.
[45] H. Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244 2000.
[46] Y. Sun, X. Wang, 7. Liu, J. Miller, A. Efros, and M. Hardt. Test-time training with self- supervision for generalization under distribution shifts. In International conference on machine learning, pages 9229-9248. PMLR, 2020.
[47] R. Tachet des Combes. H. Zhao, Y.-X. Wang, and G. J. Gordon. Domain adaptation with conditional distribution matching and generalized label shift. Advances in Neural Information Processing Systems, 33:19276-1997 19289, 2020.
[48] D. Wang, F. Shelhamer, S. Liu, B. Olshausen, and T. Darrell. Tent: Fully test-time adaptation by entropy minimization. arXiv preprint arXiv:2006. 10726, 2020.
[49] R. Wu, C. Guo, Y. Su, and K. Q Weinberger. Online adaptation to label distribution shift. Advances in Neural Information Processing Systems, 34:1 1340-11351, 2021.
[50] Q. Xie, M.-T. Luong, E. Hovy, and Q. V. Le. Self-training with noisy student improves imagenet classification. In 2020 JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10684-15 10695, 2020. doi: 10.1 109/C//R422000 200.0.002200000000000
[51] B. Zadrozny. Learning and evaluating classifiers under sample selection bias. In Proceedings of the Twenty-First International Conference on Machine Learning, page 1 11,, 2004.
[52] K. Zhang, B. Schölkopf, K. Muandet, and Z. Wang. Domain adaptation under target and conditional shift. In International Conference on Machine Learning, pages 819-827. PMLR, 2013.
[53] Y.-J Zhang, Z.-Y. Zhang, P. Zhao, and M. Sugiyama. Adapting to continuous covariate shift via online density ratio estimation. arXiv preprint arXiv:2302.00555. 2023.
[54] Zhao, Y.-J. Zhang. Zhang, and Z.-H. Zhou. Adaptivity and non-stationarity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 -2, 2024.
13

---

A Further Related Work
Offline distribution shift and domain shift. Offline label shift and covariate shift have been studied for many years. Some early work [42, 33] assumes the knowledge of how the distribution is shifted. Later work [45, 51, 28, 19, 35, 1, 4, 14] relaxes this assumption and estimates this knowledge from unlabeled test data. recent work by [15] considers relaxed version of offline label shift problem where the class-conditionals can change between train and test domains in a restrictive way. Extending their results to the case of relaxed online version of generalized label shift is an interesting future direction.
Online distribution shift with provable guarantees. There has been several work modeling online distribution shift as the classic online learning problem [49, 7, 6, 53), which leverage the classical online learning algorithms [44, 8, 5] bound the static dynamic regret. Qian al. [40] focuses on a special setting in online label shift, where there can be new classes occurring in the test stage. They handle the new class by unsupervised estimating the portion of unseen data. However, none of them updates the feature extractor in a deep learning model but only the last linear layer or the post-hoc linear reweighting vectors. Our proposed method OLS-OFU utilizes the deep learning SSL to improve the feature extractor, which brings better performance.
Domain shift adaptation within online streaming data. When consider the most authentic online learning setup where the learner only receives the unlabeled samples, the most representative idea is test-time training [46, 48, 36, 39), which utilizes (deep learning) self-supervised loss to online update the model. However, focuses on how to adapt to a fixed domain shifted distribution from online streaming data and is not designed for how to adapt continuous distribution changes during the test stage, while our algorithm concentrates the later problem. Besides test-time training, Hoffman et al. [27] and [38] study the online domain shift for specific visual applications.
B Proof of Proposition 1
The proof of Proposition 1. We first write the derivation that Evey s:byl
V V Pneapiai ( (sup((((()))) is an unbiased estimator of Vl((seP) when Ss is indepen-
Algorithm 2 Revised ROGD for online feature updates ROGD-R. See the original version in Equation and Equation in [49].
Require: Learning rate 7). for tor==1 1,..., ,T do
Input at time t: Samples S1 .... U St, models {.f..... }. and intermediate model
{f" .... [.' from step 3 in Algorithm 1, the validation set D). the training label marginal Go (train (y).
1. Compute the unbiased estimator for label marginal distribution: D the original ROGD, it is fo rather than ft
8t T&. Exies, CTd7 Ji.DD D0, (xx).
2. Grab the weight Pt from ft.
3. Update Pt+1 = Projax Pt 17 Jp(p)) Tspl
where Jp. (pt) = 0p
diag( C _ )pppp and let f.41 be a reweighting version of
ff by the weight |++1|k k 1,... K)
In the original ROGD, it is rather than f
go/k]
Output at time t: f4+1.
end for
14

---

dent of St.
Es,
s pyb sff((())) (f)( NEY
Σ Es. [ V v (1a (ft(2))))))))
wEY
Σ
Rs [
Parmani (-1)) (wy
vEy
Σ grlu] V plannn
vEy
Σ VEY
qclul V p
V)((f.))
The third equality is as how is constructed. The fourth equality holds by the label shift assumption. can check the second equality: if fi is dependent of S,, the correctness the second equality is not guaranteed and so is the overall unbiased property derivation.
C The Revision for Previous Online Label Shift Adaptation Algorithms
The revised algorithms to be used in the main algorithm OLS-OFU (Algorithm 1) are FTH-R (Algorithm 3), UOGD-R (Algorithm 4), ROGD-R (Algorithm 2), ATLAS-R (Algorithm 5), FLHFTL. R (Algorithm 6).
D Theorems for OLS and Proofs
In this section, we present the theoretical results FLHFTL-OFU, ROGD-OFU FTH-OFU, UOGD- OFU. ATLAS-OFU and their proofs. The proofs are mostly the same as the proofs for the original algorithms with small adjustments. As our results are not straight corollaries for the original theorems, we write the full proofs here for the completeness.
D.1 Theorem for FLHFTL-OFU
Before proving Theorem 2 (in Section 3.3 recall the assumption from Baby et al. [6] for convenience. We refer the reader to Baby et al. [6] for justifications and further details of the assumptions.
Assumption 1. Assume access to the true label marginals qo E ΔK of the offline train data and the true confusion matrix C IR kK Further the minimum singular value o mmin (C) 22(1) is bounded away from zero.
Algorithm 3 Revised FTH for online feature updates (FTH-R). See the original version in Equation in [49].
for t 1, 1.... T do Input at time t: Samples S1 .... U S. models -. fe }. and intermediate model [f" .... [(" from step 3 Algorithm 1, the validation set D' the train label marginal 4o ptrain (z).
1. Compute the unbiased estimator for label marginal distribution: E the original FTI., it fo rather than fi'
8t
[S.T Emes,, CT..Dy
Ji (x))).
2. Compute Pc+1 = = Sy
3. Let f(+1 be reweighting version of f. by
the weight
[[++[k]] k 1.... K)
In the original FTL., it is rather than fr
s0|A]
Output at time t: fl+1. end for
15

---

Algorithm 4 Revised UOGD for online feature updates (UOGD-R). See the original version in Equation [7].
Require: The learning rate 1/.
for f 1,... T do
Input at time t: Samples S U... U S,, models (fi..... ft). and intermediate model
[/' ,
from step 3 in Algorithm 1, the validation Do- the train label marginal == (traii()) (y).
1. Compute the unbiased estimator for label marginal distribution: b In the original UOGD, it is rather than fl"
8t [ST Ea,es, of D/ St (x)).
2. Grab the weight wy from the last linear layer of Jt-
3. Update W++1 = Wh - Fw (w(()) St. where Ju (wr) = Dw (ft) (w). ... Ri (w)) 1
RG (w))
[DH EiWiED for (Er)0foa glinear w), .), D denotes the set of data with
label k in Do-
Di In the original UOGD, it is 0fml rather than of
4. Let f(+ be f-10ffonr w(41)). Output at time t: f/411
end for
Algorithm Revised ATLAS for online feature updates (ATLAS-R). See the original version in Equation 9 in [7].
Require: The learning rate pool H with size N; Meta learning rate e; Vi E (M) = 1/N and 11,1 fo for = 1,... do
glinear
Input time t: Samples S1 .... U S,, models {f1.... fi). and intermediate model
{f ..... Jh' from step 3 Algorithm 1, the validation set D the train label marginal
qu ptrain (y).
1. Compute the unbiased estimator for label marginal distribution: In the original ATLAS, it is fo rather than ft"
194T Enes, CT..gg ft (xxe).
8t
for i E [N]do do
2. Update W1+1,i Wti
ow Jan (Wl,i) St, where
Ju (wi,a) = 8w RR (w),.... ... R2 (w)) 1
R/ (w)
DDT E (x,))ED loolf (xffffffo w), w), DØ denotes the set of data
with label & in Do-
1> In the original ATLAS, it ofoat rather than ofeat.
end for
3. Update weight P++1 according to Pp.. exp(-s Et=1 R, (wr,))
3. Compute Wx+1 - 1 Let f1+1 1(-10feet Wz41). Output at time L: f/41
end for
Algorithm 6 Revised FLHFTL for online feature updates (FLHFTL-R); See the original version in [6].
Require: Online regression oracle ALG.
for = 1,... T do
Input time t: Samples -,U.-UU,, models (.f,...,, fe). intermediate models (ffl.-. J!
the validation set D/,, the train label marginal := pirrain (y).
1.
Compute the unbiased estimator for label marginal distribution:
[S.] Ex,s,, T.r. fl (zx > In the original FLHFTL, it rather than f²
2. Compute qu+1 := ALG(s1,.... .s)
3. Let fit be reweighting version of f by the weight ( ( = 1, ... K D. In the
original FLHFTL, is fu rather than ft'
Output at time t: f441.
end for
16

---

Assumption 2 (Lipschitzness of loss functions), Let D be compact and convex domain. Let re be any probabilistic classifier: Assume that (p(p) == E [e(g(:)Te p/ p/qo))az; is G Lipschitz with p E DD S Kr ie, [x(p1) - (x(22) S G'Ip1 p2l12 for any P1,22 E 'D The constant G need not be known ahead of time.
Theorem [Regret convergence for FLHFTL-OFU] Suppose we choose the OLS-R to be FLHFTL- (Algorithm 6) from Baby et al. [6]. Let ft of be the outpu at time step 1 from Algoritim 1, that is g(: ft', de) ). Let be the smallest among the the minimum singular values of invertible confusion matrices [C [C "i:""" C. Then under Assumptions and 2 in Baby et al. 16),
FLHFTI-OFU has the guarantee below:
k1/6 02/3T1/3 + oVT (8)
E
e(St off, Plest)
E T
E(g(: S:" 9t ):: P!est) 9o
+0
K
T
where VT == =Ei= - 99-1ll,, K is the number of classes, and the expectation is taken w.r.f. randomness in the revealed co-variates. This result is attained without prior knowledge of VT.
Proof: The proof follows the similar idea in the original online regression algorithm FLHFTL [22]
and its variants for solving online label shift problem in Baby al. [6].
The algorithm in Baby et al. [6] requires that the estimate s; in Line of Algorithm 6 is unbiased estimate of the label marginal q.- Since f! in Algorithm 6 is independent of the sample S,, and since we are working under the standard label shift assumption, due to Lipton et al. [35] we have that C JF [S.] Em.es. (xx) forms an unbiased estimate of Ex~ [f'' (a=)] Further, from Lipton et al. [35], the reciprocal of standard deviation of this estimate is bounded below by minimum of the singular values of confusion matrices {C Pb', Cyy,b)):
Let & be the estimate of the label marginal maintained by FLHFTL. By Lipschitzness, we have that
El ofe plestt) Elg(; (q:) E\Le(1))
(9)
S G Elllg: - 9cl12).
(10)
where the last line is via Assumption 2.
Flles (illlllltoo ploot) f(
Σ G Ellg- gell2]
(11)
T
G E lge
gell
(12)
S
T
Ellla
(13)
Ô K1/672/3 1/ /// (1/0
2/3 (C)) + VKT o min (C)
(14)
where the second line is due to Jensen's 's inequality, third line by Proposition 16 in Baby et al. [6]. This finishes the proof.
and last line by
D.2 Theorem for ROGD-OFU
We state the assumptions first for the later theorems. These assumptions are similar to Assumption 1-3 in [49].
Assumption 3. VP E (ptrain plest,... ,leest diag(Cr.p) is differentiable with respect to f.
17

---

Assumption 4. AY E (T). l(g(= p.. p/qu); Plost) is convex in where ft. is defined in Algorithm 1.
Assumption 5. [M |V Vp ft" p/ P is finite and bounded by L.
pl for ROGD-OFU), If run Algorithm with ROGD-R (Algorithm 2)
Theorem 3
and 1j
under Assumption 3, 5, ROGD-OFU satisfies the guarantee
T L
E
(f
ofu, )lest)
min E BEDK
1
Aglls p/ P!ont)
2 S SV
(15)
T
E
1 T
20)
min E PEAX T
1 Σ
(lo(s pp Jos q0): 21)
S
VV
2
L.
(16)
Proof: The proof follows the similar idea in the original online leanring algorithm online gradient descent (OGD) [44] and the ROGD in Wu et al. [49]. For any fixed p.
E(Sennd
(oprogd-oo ofu, ;Plest) E(g(; S" p/go): Preat)
Elg(: S" pc/10); Pleat) (lg(s .// Piest)
S (Pr p) Vplig(: S :t
(P: p) Jp (Pt) Es,, St 1......... S
Es, - p) St (pt) se S1, ... ,
where the last inequality holds by the fact that (pr - p) sp (p:) is independent To bound (pt p) -...5 (pt) sts
|pt+1 p112 = ||rrol A (pt 11 pp (pt) T 8t) -r11
s |lp: 77 Jp.. (pt) T 8t pl2
= Ilpe -1 + 1²² 1 p. (Pt) T sel1 20(er - p) (p))
This implies
(pi-p)
p) p) (p (p)) ss)) S (llp: pll - --lppt11 - -pli)) + " Jp. (pt) T
1
27
2
Thus
T
T
Eg Es Sr
1
rogd poodd-ofu ofu stost)
Σ
E(g(: f:", ./" p/90): Pi
T
T
1=1
t=1
1
< Esi,.-,st Sr
(IIp: p11 - ||pp+11 p1l2) + 1 (p Ts
T
21
1=1
1
|lp1 - -pl2
17
T
Es... s. 11::5 sc
21/l
2T
1
?L
2
T
T
This bound holds for any Thus,
1
T
T
E(g(: ft' (tllfffpp///))))/ Preot) S 2
Es.... .8
e progd oofu, pleet)
min Es.... ST PEAK-1
T
T
D.3 Theorem for FTH-OFU
We begin with two assumptions.
Assumption For any plest s.t. plast (xly) = Ptraiu (ernia((x))) (xly), denote q: = (Ptest (y = k)) : h E [K]) and then
ll - arg min -1
(gg(;; /0): plest) S 6.
18

---

Assumption 7. Vptest s.t. plest (zly) = Ptrain (aly), sup, V p(g(( ft. . qu); Plest) I S L
Theorem (Regret convergence for FTH-OFU). If we run Algorithm 1 with FTH-R (Algorithm 3) and assume is no larger than the minimum singular value of invertible confusion matrices (Crr .h.... C.. under Assumption 6 and 7 with ò 0, FTUI-OFU satisfies the guarantee that with probability at least 2KT over samples S1 U.....U. ST.
T
log T
1
K log T
E(St ff ((ffth-ofe ofu, :
min PEAK T
Elg(t ft' p/90):: 00
+
T
T
0
T
(17)
where K is the number of classes.
The proof follows the similar idea in the original online leanring algorithm FTL [44] and the FTH in Wu et al. [49]. Denote qi = (Plest (y k) k E [K]). By the Hoeffding and union bound, we have
Proof:
P
St lpe+1
v1
E VKee) (Kee) 21 21-
2M exp (-2eît/o²)
This implies that with probability at least 1 - -T-= 2M 2Mxxp (-2o2t/o2), Ap.
(pe: Plest)
{(((: p()o.))):)//
T
Σ
9r /0/: Plest)
Σ
Pleat) + LVM Σe E7
T
T
Egg(=s"
gr /e// Pleat)
Σ
{(g(=
ft"
1
4r 90/90); Plest)
+ LVM
1=1
t=1
r=1
Σ1
Σ
4+
47
+ LVM
M
Σ
E1
1=1
Σ L
1-1
Σ
9t
q1
+ LLM
Et
2L
r
+
LVM
Es.
If we take e, 20 V
m the above is equivalent with probability at least 1 - 2KT
1
P(pp: min 1 P T
Σ flg(: So Pla 2L In
K Kn
T ALoV
+
T
D.4 Theorems for UOGD-OFU and ATLAS-OFU
Theorem 5. [Regret convergence for UOGD-OFUJ Let f(; ((:3tfr w) denote a network with the same feature extractor as that of f" and a last linear layer with weight w. Let fuogd-ofu f(; ffas wx). where we is the weight maintained at round t by Algorithmm 4. If we run Algorithum 1 with UOGD in [7] and let step size be n, then under the same assumptions Lemma I in [7], UOGD-OFU satisfies that
T
T Σ
Kn σ2
1
Vr
E
((googd ofu, Prestt)
min (fo(: w); Prest) wEW
<0
+
T
T
r/
Tm
(18)
where Vr = Et supwew (e Gleat w); Plest) E(s(;
Gleat R- RL,, ,w); (t): a denotes the min-
imum singular value of the invertible confusion matrices (C .........C... and K is the number of classes and the expectation is taken with respect to randomness in the revealed co-variates.
19

---

Proof Sketch: Recall that {(f (fat
f w); Ptost) == E(a.a)) (f(z)0) S1" w). vv)
This guarantee follows from the arguments in Bai et al. [7] from two basic facts below:
1. The risk {(((; Opp' w); Plest) is convex in w over a convex and compact domain W.
2. It is possible to form unbiased estimates Gi(w) e IR such that ([G(( =
F((ea)))pee Vulco (f w),y)
Hence we proceed to verify these two facts in our setup. Fact is true because the cross-entropy loss is convex in any subset of the simplex and the last linear layer weights only defines affine transformation which preserves convexity.
For fact 2, note that the f" only uses the data until round / --1 1. So by the same arguments in Bai et al. [7], using the BBSE estimator defined from the classifier f" the unbiased estimate of risk gradient can be defined.
Let we be the weight of the last layer maintained by UOGD at round Let u1r be any sequence in W. Consequently we have for any round,
e( ((pugdd-of, )lea)) - [[[(: gleat 13" uz) E(s(: (:00; Gleat we) e(f(: 0f000 u4))
(19)
S (V (( 6 we), we un)
(20)
(F:(G((::))S1:
uz)-
(21)
Rest of the proof is identical to Bai et al. [7].
Theorem for UOGD-OLS OLS shows bound that depends on the learning rate and one can set up the learning carefully to get the optimal rate. However, this learning rate requires the prior information of Vr, which is typically unknown during the learning process. ATLAS-OLS overcomes this issue by applying the same online ensembling framework [54] as the original ATLAS. Without knowing this prior information, ATLAS-OLS able to achieve the same rate of upper bound too, which is stated in the following theorem.
Theorem 6 (Regret convergence for ATLAS-OFU), Let f(:: f3 w) denote a network with the same
feature extractor as that of f( and a last linear layer with weight w. Let fatlus- ofu f(; Ofeat we). where W, the weight maintained at round by Algorithm If run Algorithm 1 with ATLAS in
[7] and up the step size pool 7. = {n1 =0
2 1/ [N]] (N 1+ [ (1-2(1+27)
VKT then under the same assumptions as Lemma in [7], ATLAS-OFU satisfies that
5o 50(K1% (K13
V
K
E( patles--hhy ofu, plest)
Σ min wEW
E((:
Ofeat w); Pt
+1
T1/3
2T
(22)
gfoat K"_, w0); (lext) imum singular value of the invertible confusion matrices .pb. Cy.,ng D2 and K is the number of classes and the expectation is taken with respect to randomness the revealed co-variates.
where Vr Et sup (=( ( w); P!oat) E(f(:
denotes the min-
The proof is similar to that of Theorem 5, which mainly follows the similar idea in the original online ensembling framework [54] and ATLAS [7], and hence omitted.
Discussion about the assumption. In the theorems for UOGD and ATLAS, the definition of Vr, is shift severity from prest However, in the theorems for UOGD-OFU and ATLAS-OFU above, Vr, is shift severity from both Prest and gfoat, which can be much larger. This might lead to harder convergence of the regret.
20

---

Base
CLS
OLS GFU
Rotation Prediction
Minimization
MoCo
Error (56)
OLS Methods
OLS Methods
OLS Methods
(a) Results on CIFAR-10 three SSL methods in OLS-OFU (Bernoulli shift)
Beror (%)
(%)
ATLAS FTTWH
FUN-FTL
FTWW
Methods
Mathods
(b) Results on three more datasets (rotation degree prediction, Bernuulli shift)
Gaussian Noise
Fog
Pixelate
Emar
PTPWN
ROOD ATLAS
UDOD PUN-FTL
PTPWH
PTH
ROOD ATLAS
U000 FUM-PTL
PTPW
500D ATLAS
UOOD PUN-FTL
OLS Methods
OLS Methods
OLS Methods
(c) Results three types of corruptions in CIFAR-IOC (rotation degree prediction, Bernoulli shift)
Figure 4: Evaluation of OLS and OLS-OFU.
E
Additional experiments
E.1
Additional Details of Datasets, Online Shift Patterns, and SSL
Severity of CIFAR-10C in the experiment. For each type of corruption in CIFAR-10C, select a mild level of severity in the experiment section. Here we introduce the exact parameters of mild and high levels of severity for those corruptions. For Gaussian Noise, the severity level is 0.03. For Fog, the severity level is (0.75,2.5). For Pixelate, the severity level 0.75.
Details of online shift patterns. Specifically, given two label distribution vectors q and g', simulate the label marginal distributions time as a weighted combination of them: q := izt agg + (1-10)0) ax) )' Sinusoidal shift, ag sin Z (periodic length = VT, = mod L) while in Bernoulli shift, ag is random bit (either or 1), where the bit switches aı 1 0x-1 with probability = VT In our experiments, we set the initial distribution vector and d' with
(1. 1) and (1, 0). To sample the batch test data time t, we first sample a batch of labels (not revealed to the learner) according to g.- Then given each label we can sample an image from the test set, and collect this batch of images without labels S..
Details of self supervised learning techniques. rotation degree prediction involves initially rotating a given image by a specific degree from the set (0, 90, 180, 270) and the classifier is required to determine the degree by which the image has been rotated. Entropy minimization utilizes minimum entropy regularizer, with the motivation that unlabeled examples are mostly beneficial when classes have a small overlap. MoCo is more advanced representation learning technique, using query and momentum encoder to learn representations from unlabeled data by maximizing the similarity of positive pairs and minimizing the similarity of negative pairs.
21

---

FTFWH
FTH
ROGD
ATLAS
UOGD
FLH-FTL
OLS
11.52% /0.397
11.56% 00339
14.21% 1.15
12.02% /4..5
11.65% 312
11.63% / 1.09
OLS-OFU-BI
10.5%
10.5%
14.%
12.1% 44.22
287
OLS-OFU-BA 10)
9.19% 28.
9.64% / 28.7
13.2% 40.9
12% /3.9
10.6% /319
9.39% 28.4
OLS-OFU-BA (T= 50)
7.54% /6.16
8.41% 6.3
12.1%
11.7% /43.8
9.4% /
7.82% 6.88
OLS-OFU-BA
6.79% 3.4
7.57% 3.338
10.9%
10.5% /43.6
8.46% /314
7.04% /4009
OLS-OFU-BA (T 500)
11.2% / 1,19
11.3% 1,18
14.1%
11.9% /42.7
/314
11.3% 1.88
Table 4: Average error time (minutes) of original OLS methods versus OLS-OFU with various
frequency in butch accumulation. The SSL in OLS-OFU is Entropy Minimization.
Their loss functions as follow. When the SSL loss is rotation degree prediction, it requires another network frice to predict the rotation degree, sharing the same feature extractor g as fo but with different set of downstream layers. Its SSL. loss ( (S; f') is defined as Eres fee (J (R(x; i)), i), where is an integer uniformly sampled from [4], and R(x, i) is rotate with degree DL from list degrees DL = [0, 90, 180, 270]. Alternatively, the SSL loss is entropy minimization, (S; f)
would be the entropy Exes Σk=1 f(z)& log f(r).. Moreover, the SSL loss of MoCo would be contrastive loss (InfoNCE) where the positive example x' is an augmented version of x and other samples in the same time step can be the negative examples.
E.2 Additional Results of OLS-OFU and Baselines
Figure 2 has three subfigures, showing the results of OLS-OFU with three SSL CIFAR-10, the results on three more datasets for evaluating online label shift, and the results on CIFAR-10C for evaluating online generalized label shift; the online shift patterns figures in Figure 2. We show similar figures Figure but now the online shift patterns are Bernoulli shift. We can have the exact same observations from Figure 4: the improvements from original OLS methods to OLS-OFU are significant and consistent across 6 OLS methods, SSL techniques, datasets with online label shift and datasets with online generalized label shift.
Sinusoidal shift for all these
We also evaluate three SSL methods in OLS-OFU on CIFAR- 10C with mild severity for two online shift patterns. In Figure 7, the improvement from OLS to OLS-OFU is very significant but OLS-OFU cannot outperform OFU.
E.3
Ablation Study Frequency in OLS-OFU for Entropy Minimization and MoCo
Table the main paper shows ablation study
when SSL is ro- tation degree prediction. Here we in- clude Table 4 and Table for the same ablation study on т but the SSL in OLF-OFU is Entropy Minimization and MoCoin two tables respectively. We have same observations we observed from Table I: 1. OLS- OFU with all outperforms OL.;; 2. The average error of OLS-OFU de- creases from
Entropy
Enor (M)
what
Data Setup (Online Shift Type)
(w/o batch ac-
Breer (8))
cumulation) to - = 100 and starts increase after and this is because the effectiveness of SSL benefits from 1 while larger means less up- dates and hence hurts the long term performance; the additional time cost of OLS-OFU with larger is smaller and r = 100 gives a great balance of performance and time cost.
Data Setup (Online Shift Type)
Figure 5: Empirical examination for the holdness of Equa- tion 7. Clean denotes the experiment on CIFAR-10 10 and others denotes the corruption type. They paired with two online shift patterns: Sinusoidal and Bernoulli.
22

---

FTFWH
FTH
ROGD
ATLAS
UOGD
FLH-FTL
OLS
6.21% / 0.392
7.03% / 1.05
8.23% / 00.88
7.82%/42.2
6.97% / 302
6.45% 00.4
OLS-OFU-BA (r 1)
6.76% /277
8.13% 280
8.86% 374
7.57% /5633
7.84% / 319
8.55% /
OLS-OFU-BA (T = 10)
5.64% 28.6
7.08%
8.01% 39.7
7.2%
6.87% / 313
7.2% / 28.5
OLS-OFU-BA (r 50)
4.52% 6.118
6.03% 6.96
7.16% 8.7.7
6.84% /337
5.9% /312
5.86% 6.09
OLS-OFU-BA (F 100)
3.97% 3.42
4.2
6.3% 44.91
/3.44
5.19% 308
5.15% 3,36
OLS-OPU-BA 500)
5.06% 2.13
6.32% 2.86
7.52%
7.12% /43.1
6.23% 309
6.05% 2.12
Table 5: Average error / time (minutes) of 6 original OLS methods versus OLS-OFU with various
frequency т in batch accumulation. The SSL in OLS-OFU is MoCo.
E.4
Empirical Validation of Equation
Similar to Figure 3, as shown in Figure 5, is evident that OLS-OFU with SSL chosen as Entropy Minimization and MoCo is able to yield improvements on the baseline of the regret as shown in Equation 7.
E.5
Self-training
CLS-aru llu holll-/oaa-uteeee
CLS-arU Su fuyl Vaen-a 12
Sinusoidal Shift, Rotation Degree Prediction
Sinusoldal Shift, Rotation Degree Prediction
Error (%)
Error (%)
FTPWH FTH
ROGD ATLAS UOGD FLH-FTL
FTEWH ROGD ATLAS UOGD FLI-FTL OLS Methods
OLS Methods
Bernoulli Shift, Rotation Degree Prediction
Degree Prediction
(%)
Error (%)
FTPWH FTH
ROGD ATLAS UOGD FLH-FTL
ATLAS OLS Methods
OLS Methods
(a) number of online samples: 10
(b) number of online samples: 50
Figure 6: Results on pseudo-labelling
Pseudo labelling [31]. J. a common self-training technique, generates pseudo labels for unlabelled data and uses them to update the model. Though are not able use ground-truth labels to compute feature extractor updates, we can use the model at time to make predictions with respect to the online samples at time f, and train on the inputs with their assigned (pseudo) labels. An issue that arises in self- eeff-training is confirmation bias, where the model repeatedly overfits to incorrect pseudo-labels. As such, different methods can used to select which samples will be pseudo-labelles and used in updating the model, e.g. using data augmentation [3], using regularization to induce confident low- entropy ppeudo-labelling [17], using softmax thresholds to filter out noisy low-confidence predictions [50]. We make of ensembles to identify noisy now-confiieenceeentopy pseudo-label predictions,
23

---

though other various alternatives can also be used. In addition to OLS and OLS-OFU, we highlight the methods under comparison:
OLS-OFU (Laup(: Igroend-tmuhh): Instead of computing pseudo-labels, we make use of the correct ground-truth labels Vground-truth- Recall suu is the supervised learning loss. We update the feature extractor with the supervised loss w.r.t. ground labels <uu Mground-cruth.
OLS- (Last + kaup( (+, Mground-truth)) ): Instead of computing pseudo-labels, we make use of the correct ground-trute truth labels Vground truth Recall East and <up are the self-supervised and supervised learning losses respectively. We update the feature extractor with both the self-supervised loss fast as well as the supervised loss w.r.t. ground-truth labels
ksupl (1, Uground-truth)
OLS-OFU (faal + (- 3pscuudo-abellccamplss-- #FUsamples=))):: Recall lasl and faup are the self-supervised and supervised learning losses respectively. We compute pseudo-labels Ypseudo-label). and update the feature extractor with both the self-supervised loss Easl as well as the supervised loss w.r.t. pseudo-labels Luup( (-, Mpseudo-labet)-
How to compute pseudo-labels? We now describe the procedure to compute pseudo-labels for Caup( (-, Jppono--abccissmmlsss #FU-samples)). The seed used to train our model 4242, and we train an additional 4 models on seeds 4343, 4545, 4646, 4747. With this ensemble of 5 models, we keep sampling inputs at each online time step until we have #FU-samples samples, or we reach limit of #samples samples. We accept an input when the agreement between the ensembles exceeds a threshold e 1.0 (i.e. we only accept samples where all ensembles agree on the label of the online sample). In the default online learning setting, there are only #samples-10, and therefore there may not be enough accepted samples to perform feature update with, thus we evaluate with a continuous sampling setup, where we sample #samples=50 (and evaluate on all these samples), but only use the first 10 samples (#FU-samples=10) to perform the feature extractor update.
Results on pseudo-labelling. We report the results of OLS-OFU with r = 1 in this section. First, we find that OLS-OFU (Eeat + kuup (: (ygoond-rmah))) ) attains the lowest error and is the lower bound we are attaining towards. Evaluating OLS-OFU (Eaa Esup(' A/peendo-abellttsmmlee we find that the performance does not outperform OLS-OFU, and is not near OLS-OFU (faal + laup(' (:s Vgroond-truuh/ ). If we set the threshold too high, there may not be enough online samples to update the feature extractor. If we set the threshold e too low, there may be too many incorrect labels and we incorrectly update our feature extractor. As such, each online time step such that we can balance this tradeoff. We sample #samples=50 at each online time step, and update with #FU-samples S 10. For fair comparison, we also show the comparable methods in both #samples=10, #FU-samples=10 and #samples=50, #FU-samples=55 settings.
HFU-sampless 10))) ),
would like to sample more inputs at
With this sampling setup, we find that OLS-OFU (East + Laup(', (ppenaa-lahe((taammcessss #FU--samples (0) can outperform both OLS-OFU (#samples-10 and OLS-OFU ass 50)= Though does not exceed neither OLS-OFU (Esel faup(' (ground-truth) ) for #samples=10 nor #samples=50, it lowers the gap considerably.
24

---

Base
OLS
OLS-OFU
Gaussian Noise
Fog
Pixelate
Error (%)
STEWH FTH
BOGD ATLAS UOGO FUN-FTL
FIPMM
FTH
ROGO AILAS UOGO FLN-FIL
FTPWA FTN
ROGO ATLAS UOGO FLI-FIL
Methods
OLS Methods
OLS Methods
Simusoicti Rotation Degree Prediction
Fog
(%)
Error (%6
FTFWH FTH
10OD ATLAS UOGD PUN-FTL
PTPWM PTH
ROOD ATLAS UDGD FLH-FTL
FTPMM FTH 50CD ATLAS UOCO FLI-FIL
(b) Beroulli Shill, Rotation Degree Prediction
Fog
Error (%6
Error (%)
FITWR
UOGO
FTTW/
Methods
Methods
OLS Methods
(c) Sinusoidal Shift, Entropy Minimization
Gaussian Noise
Pixelate
Error (%)
Enror 1%6
Methods
OLS Methods
OLS Methods
(d) Hernaulli Shaft, Entropy Minimization
Gaussian Noise
Fog
Pixelate
(50
Error (%6)
OLS Methods
OLS Methods
OLS Methods
(c) Simssiidl Shiß, McCo Fog
Gaussian Noise
Pixelate
Error
FIFWN
ROCD ATLAS UOCD FUI-FLL
UOCO FUI-FTL
FTTW
OLS Methods
OLS Methods
OLS Methods
(1) Shift,
Figure 7: Results of online shift patterns CIFAR-10C and three SSL methods in OLS-OFU. 25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
26

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
27

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/nips. wwtppcccccc/cceeccccccccccccclct httaa//ggiieeeeeeeuuiiieeeee /Coo//eoomissssseeeee mmmiisssioooiyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
We reported large range of experimental results, though error bars included.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
28

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We use A6000 GPU and report time cost evaluation.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpps:///eurips cwtppblic/tthiiccccccecc.c..c csGuidel ines?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We use practical examples like MRI machine.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
29

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No such models/data are used in this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No new assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
30

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human participants.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "T9WCgL8lTE", "reviewer": "Reviewer_fST3", "summary": "This paper addresses the problem of online (generalized) label shift, where label information is unavailable during testing, and the label distributions change over time. The main contribution of this work is the proposal of a unified framework that integrates feature learning into the online learning process, enabling the method to leverage the strengths of deep models. Theoretical analysis and experiments demonstrate the effectiveness of the proposed approach", "questions": "Could you provide more theoretical insight on the feature extractor? For instance, is there any guidance on selecting the SSL method or determining the step size for performing the gradient step?\n\n- Is there any method to reduce the requirement of storing the train set $D_0$?\n\n- Could you provide more justification for Principle 1? (Please refer to the three points of concern outlined above for more details.)", "limitations": "I did not identify the negative societal impact of this work.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Overall, this paper is well-motivated and makes a valuable contribution to the online label shift problem. It is an important question for me on how to effectively incorporate feature learning into the online learning process, and this paper provides a unified framework that demonstrates strong empirical performance. The strengths of this paper are as follows:\n\n+ The paper presents a general method applicable to various online label shift approaches proposed in the literature.\n+ The experimental results show a significant improvement in classification accuracy by incorporating the feature learning process.\n+ The proposed method is robust to the generalized label shift problem.", "weaknesses": "- One of my main concerns is the theoretical analysis of the feature learning component. While Theorem 1 is commendable for demonstrating that the proposed method is comparable to the best model adapted from $f_t^{''}$, it remains unclear how effective the feature extractor obtained via self-supervised learning is (from a theoretical view). The self-supervised learning technique appears to be used as a black box, with no theoretical insight provided into its performance.\n\n- Regarding storage costs: It seems that the proposed method requires storing the training set $D_0$. Such a requirement is somewhat unfavorable in practice, as the training set $D_0$ typically consists of a large volume of data.\n\n- Concerning Principle 1: I understand that Principle 1 is essential for achieving theoretical guarantees in the online label shift problem. However, I am uncertain whether such a requirement is necessary in practice. Should the update procedure depend on the amount of data available at each round? If we have a reasonable amount of data at each time, wouldn't it be more reasonable to update the feature extractor before the online learning process to gather more information? Conversely, if the data at each iteration is limited, I'm unsure if the difference between update procedures is significant. It would be beneficial if the authors could provide a more detailed discussion on this matter.\n\nI am happy to discuss these concerns with the authors and update my score if the questions are adequately addressed.\n\n===post-rebuttal===\n\nI appreciate the authors' efforts in addressing my questions and am satisfied with their feedback. I encourage the authors to incorporate the discussion from the rebuttal period into the main paper. I have raised my score to 7.", "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": "", "extra_scores": {}}, {"review_id": "yfn6E4WJAy", "reviewer": "Reviewer_ZntR", "summary": "This paper introduces a novel method for addressing label shifts in an online setting, where data distributions change over time, and obtaining timely labels is challenging. Unlike traditional approaches, this paper explores enhancing feature representations using unlabeled data during test time. The proposed method, Online Label Shift adaptation with Online Feature Updates (OLS-OFU), leverages self-supervised learning to refine the feature extraction process, thereby improving the prediction model. This approach is designed to maintain similar online regret convergence to existing results while incorporating improved features. Empirical evaluations show that OLS-OFU achieves substantial improvements over current methods, demonstrating that integrating online feature updates is as effective as the fundamental online label shift methods themselves. The results are consistent across various datasets and scenarios, highlighting the robustness and generality of OLS-OFU. The paper suggests that this method could be extended to more complex scenarios, such as online covariate shift and varying domain shifts over time.", "questions": "- What is the difference between concept drift and online generalized label shift situations?", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "-\tIn the Problem Setting & Related Work section, the paper effectively describes the mathematical definition of online label shift (OLS) adaptation and related research. By leveraging a similar mathematical framework, the paper clearly explains the approach to solving the online generalized label shift adaptation problem, demonstrating that the proposed method is well-motivated and thoroughly explained.\n-\tThe author thoroughly explores potential questions and concerns associated with the introduction of new methods for addressing the problem. The paper presents well-defined principles and explanations that connect these concerns to the proposed approach, demonstrating a deep and thoughtful analysis of the new methodology\n-\tThe experimental results presented in the paper effectively showcase the strong performance of the proposed OLS-OFU method compared to both baseline approaches and the existing OLS method. The comparisons clearly illustrate that OLS-OFU achieves better results, validating the efficacy of the proposed technique.", "weaknesses": "- From a critical perspective, the online generalized label shift problem presented in the paper could be viewed as a sub-field of concept drift, where the relationship between x and y changes over time. Therefore, a detailed explanation of the differences between the proposed online generalized label shift scenario and the traditional concept drift is required. Additionally, it would be beneficial to conduct experimental comparisons to determine whether methods developed for concept drift could be effective in the experimental settings used in this study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing insightful comments! Here are our responses.\n\n**Discussion with concept drift.** Yes, you are right that the (online) generalized label shift problem is a sub-field of concept drift and has its particular assumption. According to the definition of generalized label shift, it can be reduced to label shift once the learner knows the underlying feature mapping $h$. We would like to explain how each component of our method can solve each part specifically according to the literature and hence our method .\n1. Online feature update learns the underlying feature mapping $h$ that makes $P(h(x_t)|y_t)$ invariant. In the literature of test-time training [1, 2, 3], they found the self-supervised learning of feature updates can explicitly align the feature space of new distribution to the feature space of training distribution; they even only trained with the feature extractor **without retrain the last linear layer**, this strongly supports the straightforward feature space alignment between original distribution and shifted distribution.\n2. Built upon the updated feature extractor from 1, the problem can be reduced to online label shifts and we adopt the particular online label shift method, which follows the well-studied offline label shift method.\nThank you for raising this point about generalized label shifts. We will add these explanations to Section 3.4 and we believe this can help improve the understanding of how our method can tackle the online generalized label shift.\n\n[1] Y. Sun, X. Wang, Z. Liu, J. Miller, A. Efros, and M. Hardt. Test-time training with self-supervision for generalization under distribution shifts. In International conference on machine learning, pages 9229–9248. PMLR, 2020.\n\n[2] Wang, Dequan, et al. \"Tent: Fully test-time adaptation by entropy minimization.\" arXiv preprint arXiv:2006.10726 (2020).\n\n[3] Liu, Yuejiang, et al. \"Ttt++: When does self-supervised test-time training fail or thrive?.\" Advances in Neural Information Processing Systems 34 (2021): 21808-21820.", "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": "", "extra_scores": {}}, {"review_id": "IhGNIL8M82", "reviewer": "Reviewer_XJxy", "summary": "This paper addresses the online label shift (OLS) adaptation problem, which involves continually adapting a pretrained offline model to test data with various and evolving label distribution shifts. The proposed method integrates existing self-supervised learning (SSL) techniques into current OLS methods, based on three proposed method-combination principles. Experimental results demonstrate that incorporating SSL methods leads to performance improvements.", "questions": "See Weaknesses.", "limitations": "Already addressed by Authors.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The proposed method encompasses various OLS baseline methods and self-supervised learning approaches, demonstrating a comprehensive range of experimental cases.\n\n2. The proposed method consistently achieves performance improvements over the comparison methods.", "weaknesses": "1. **Limited Novelty and Significance**: The proposed method appears to be a straightforward combination of existing approaches, specifically SSL and OLS methods. The three proposed principles for combining these approaches are relatively trivial:\n\n    - Since SSL affects extracted features, OLS is performed first.\n\n    - As SSL changes the feature extractor, the classifier is retrained.\n\n    - Given that SSL requires additional training resources, it is applied after accumulating enough data.\n\n    These principles seem too basic to be considered significant technical contributions.\n\n2. **Problems in Paper Structure**: The paper has serious structural issues.\n    The proposed method relies heavily on existing OLS methods, yet there is a lack of brief or detailed introduction of related OLS methods. Only three sentences describe OLS and SSL methods.\n\n    Conversely, the problem setting of online label shift, which can be summarized in one sentence as \"the test data have a different label distribution from training data\", is explained with excessive and redundant content, including irrelevant details about online distribution shift.\n\n    As a result, the experimental section is compressed into two pages, limiting the space to present results adequately. The conclusion is also excessively brief, reduced to just one sentence.\n\n3. **Unreasonable Problem Setting**: The addressed problem seems unreasonable for several reasons.\n\n    - **Data Privacy Concern**: Adapting the model at each time step requires storing all historical training data, testing data, and models, raising significant data privacy concerns. For instance, in the MRI example mentioned in the paper, it is questionable whether you are allowed to carry MRI data from 999 clinics just to adapt the model to the 1000th clinic.\n\n    - **Adequate Offline Training Data**: The offline training data appears overly sufficient, making the problem less challenging. In the CIFAR-10 experiment, all training data are used for offline training, with the only challenge being the variation in label distribution in the test data. Without any adaptation, the model performs well on the testing data.\n\n4. **Low Baseline Performance**: The reported baseline result without any adaptation appears too low. A ResNet-18 model on CIFAR-10 typically achieves around 93\\% accuracy on test data without any special data augmentation (see https://github.com/kuangliu/pytorch-cifar), which is significantly higher than the reported 84\\% and most adaptation results.\n\n5. **Minor Typos**:\n    - Line 83: How do you reweight a model f? Do you mean reweight the model output?\n    - Line 179: OGD or ROGD?\n    - Lines 232-233: \"Either...or\" should be used correctly.\n    - Line 249: Should it be \"is\" or \"as\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for providing some useful comments about data privacy concerns and some typos. However, we respectfully disagree with the criticism on novelty, paper structure and the experiment set-up (data split and baseline performance). We reply to the weaknesses and questions point by point as below.\n\n**Novelty of three principles**. While we agree that it turns out the steps are simple, the choice of them rather than other options is out of careful considerations. We list the possible other options and re-iterate why our final design stands out from other options.\n1. *Update the feature extractor first or run original OLS first*. Through our analysis, we found only running original OLS first can still guarantee the theoretical results, while the other option cannot.\n2. *Re-training the linear layer under training distribution or other distribution*. A more natural option is actually to retrain the linear layer with the most recent estimated label distribution. However, by checking with the original OLS methods, they require the model to be in the training distribution, or at least a distribution having all classes, but test distribution is not guaranteed to have this property since it can be just one class.\n3. *Batch accumulation or not*. In fact, as shown in Table 1, even with batch size $\\tau=1$ OLS-OFU has consistent improvement over OLS, and the necessity of batch accumulation can be missed. Through the experiment, as shown in Table 1, the benefit of batch accumulation brings both the performance gain and more time efficiency. \nMoreover, through theoretical and empirical analysis, we show that our algorithm provides a way to leverage self-supervised learning, which largely improves the performance as validated through the experiments and still keeps the similar theoretical guarantees.\n\n**Paper structure**. \n> “Only three sentences describe OLS and SSL methods.”\n\nWe actually spent more energy to describe OLS and SSL methods. Given that our focus is on how our algorithm makes the bridge between the two, we included the sufficient details in the main paper and enumerated more details in the appendix. \n- For OLS, we kindly refer the reviewer to these positions:\n    1. At line 115 - 125 in Section 2, original OLS methods do not update feature extractor and this motivates the methodology of our paper. \n    2. Line 175-181 describes the details of the condition where the theoretical guarantees would hold for original OLS methods, and this motivated our first design of our algorithm.\n    3. Line 187-191 describes the choice of hypothesis space of original OLS methods, and the underlying reason for this choice in the literature motivates our second design of our algorithm.\n    4. Moreover, for completeness, we included detailed algorithms of all 5 OLS methods as Algorithm 2-5 in the appendix.\n- For SSL, the details of SSL are not our focus,  as long as it has the form of $\\ell_{\\rm ssl}(S)$ for any batch of data $S$. Our algorithm OLS-OFU should work for general SSL methods, which is one of the information we would like to convey from our experiments. Therefore, we experiment with different SSLs as introduced at line 304-308 and their numerous details in the Appendix E.1.\n\n> “The problem setting of online label shift, which can be summarized in one sentence as \"the test data have a different label distribution from training data\", is explained with excessive and redundant content, including irrelevant details about online distribution shift.”\n\nWe kindly disagree with the description of online distribution shift and online label shift is redundant. Rather than just describe the mathematical problem, other components are necessary in introducing a problem too to make the paper have a broader audience, which include the motivating example (line 85-96), the description of objective function in the online setting (Line 97-103), the learning setting of unsupervised adaptation and limited unlabeled batch (Line 104-110), the assumption of label shift (Line 110-113), the summarization of existing online label shift methods and their limitations (Line 114-128) and introducing online generalized label shift adaptation as a first work (line 128 until line 129.)\n\n> “The experimental section is compressed into two pages, limiting the space to present results adequately”\n\nWe believe our experiment results are strong enough to demonstrate the effectiveness of our algorithms, which can be reflected by other reviews. We disagree that a two-pages experiment is a limitation, while we would appreciate any *concrete advice* to improve our result presentation.\n\n**Data privacy concern**. This is actually an insightful point. We acknowledge this can bring additional privacy concerns, depending on the practical scenarios, and we would like to discuss this in the revision. At the same time, as shown in Table 1, we can find that even without batch accumulation (batch size $\\tau$=1), OLS-OFU still outperforms OLS. Parameter $\\tau$ can be treated as the performance and privacy trade-off. \n\n**Data split and baseline performance**. There seems to be some misunderstanding about our data split and baselines, where we basically followed the literature. For the data split, as described at Line 293, our model was trained by 80% training set offline, with a 20% split as a validation set. We followed the code released from [1] for training the $f_0$ and our performance of “base” matches their numbers in Table 1, which are around 16% error for the CIFAR10.\n\n**Typos**. Thanks for catching them! We will fix the typos. The definition of reweight is to reweight the soft-max probability by element-wise multiplying another vector.\n\n[1] Baby, Dheeraj, et al. \"Online label shift: Optimal dynamic regret meets practical algorithms.\" Advances in Neural Information Processing Systems 36 (2024).", "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": "", "extra_scores": {}}, {"review_id": "YnVISk2Dnr", "reviewer": "Reviewer_aV82", "summary": "This paper addresses the problem of online label shift and proposes a novel algorithm that exploits feature representation learning to enhance performance. Inspired by test-time training literature, the proposed method uses self-supervised learning to refine the feature extraction process. The algorithm comes with strong theoretical guarantees, and experiments demonstrate its effectiveness.", "questions": "See weakness above.\n\nIn addtion, for the storage of historical data, is it feasible to apply data augmentation techniques to the limited number of data per time stamp and use the augmented data for self-supervised learning? How does the number of historical data stored affect the proposed algorithm?", "limitations": "the authors adequately addressed the limitations", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Online label shift problem is a common but crucial issue in many real-world applications. This paper considers the important task of exploiting feature representation, proposing a novel algorithm that leverages self-supervised learning to refine the feature extraction process in the online label shift problem.\n\nThe proposed method satisfies the practical requirements while having solid theoretical guarantees that ensure its general applicability and reliability in various non-stationary learning scenarios.\n\nExperiments show the superiority of the proposed algorithm on several benchmark datasets and two distinct online shift patterns, highlighting its effectiveness and practical impact.", "weaknesses": "1. The proposed method requires the storage of previous historical data for self-supervised learning (batch accumulation in the paper). This may not be feasible in certain problems with privacy concerns.\n\n2. The experiments are primarily conducted on simulated benchmark datasets, such as CIFAR-10 and CINIC, rather than real-world applications or datasets. This limits the understanding of the method's performance in practical settings.\n\n3. It is recommended to include some recent work on online label shift in the paper, such as [1], which addresses the appearance of new class data in the scenario of online label shift.\n\n\n[1] Qian Y Y, Bai Y, Zhang Z Y, et al. Handling New Class in Online Label Shift[C]//2023 IEEE International Conference on Data Mining (ICDM). IEEE, 2023: 1283-1288.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing insightful comments! Here are our responses.\n\n**The storage of previous historical data**. This is actually an insightful point! We acknowledge this can bring additional privacy concerns, depending on the practical scenarios, and we would like to discuss this in the revision. At the same time, as shown in Table 1, we can find that even without batch accumulation (batch size $\\tau$=1), OLS-OFU still outperforms OLS. Parameter $\\tau$ can be treated as the performance and privacy trade-off. \n\n**Dataset set-up**. Our selection of datasets and the way to simulate the shift pattern mainly follow the previous online label shift literature [1, 2] and additionally, we experiment with additional domain adaptation dataset CIFAR-10C. Although we agree experimenting with real-world shifts can be meaningful, we believe our current experiments are sufficient enough to prove the improvement from the literature.\n\n**Related work**. Thank you for the pointer! This work particularly solves the unseen categories in the online label shift setting and is very relevant. It tackles the new unseen class by unsupervised estimating the portion of unseen data. We will add this literature in our related work section.\n\n[1] Baby, Dheeraj, et al. \"Online label shift: Optimal dynamic regret meets practical algorithms.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[2] Bai, Yong, et al. \"Adapting to online label shift with provable guarantees.\" Advances in Neural Information Processing Systems 35 (2022): 29960-29974.", "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": "", "extra_scores": {}}, {"review_id": "t019hyN1mN", "reviewer": "Reviewer_Dj3x", "summary": "The authors of this paper focus on the task of label distribution shift in the online setting without true labels. Following the importance of improving feature extractors even during test-time found in the current literature, they propose to update the feature extractor online with unlabeled instances during testing for online label shift and then refine the last classification layer with labeled instances. The proposed method is simple and intuitive, and extensive experiments over several label shift cases and benchmark datasets have shown its effectiveness.", "questions": "1.\tWhat is the difference between (online) label distribution shift and domain adaption? Can the proposed method adapt to the domain adaption task?\n2.\tWhat will happen if there are some instances related to new unseen categories during testing? And how to handle this case? Can improving the feature extractor be helpful?", "limitations": "See the above “*Weaknesses*” and “*Questions*” parts.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThe online label shift task is an interesting problem and worth paying more attention to, and the proposed method in this paper is simple and intuitive.\n2.\tIn addition, this paper has proved the regret convergence of the proposed method partially, so that provides the necessary justification.\n3.\tThe experimental section and the supplementary material present experimental results that demonstrate the effectiveness of the method proposed in the article.", "weaknesses": "1.\tThe motivation of this paper is not clear. The authors are just motivated by “the potential for improving feature extractors”, and hypothesize “that a similar effect can be harnessed in the context of (generalized) label shift”. This may be too intuitive. Why is improving feature extractors helpful for only label shift? What can improve feature extractors gain? Are there some theoretical or empirical results to prove that? The theory of regret convergence may be not enough.\n2.\tThe novelty of the proposed method may be limited. Improving feature extractors has been proved its importance during testing time for distribution shifts in the current literature, such as [1]. What is the difference between the proposed method and them? What are your main contributions in this paper?\n3.\tWhat are the limitations and broader impacts?\n\n[1] Y. Sun, X. Wang, Z. Liu, J. Miller, A. Efros, and M. Hardt. Test-time training with self-supervision for generalization under distribution shifts. In International conference on machine learning, pages 9229–9248. PMLR, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing insightful comments! Here are our responses.\n\n**Motivation and its justification**. We would like to answer your questions in this point separately.\n- “Why is improving feature extractors helpful for only label shift?” In fact, updating feature extractor can help with other types of shift too. As discussed at line 359-361, the existing algorithm to solve online *covariate* shift, which has strong theoretical guarantee, also doesn’t take feature extractor update into account. We believe by adopting online feature update, the performance of the algorithm can get certain improvement as well, and our work shows this possibility as a first work to introduce feature extractor update into those theoretical algorithms.\n- “What can prove feature extractors gain? Are there some theoretical or empirical results to prove that?”  Equation (7) describes **the gain from the feature extractor improvement rather than the label shift adaptation**, because it is “almost” the best loss at time $t$ given the updated feature extractor $f_t’’$ or the old feature extractor $f_0$ together with ** the knowledge of label distribution $q_t$**. On the one hand, the theoretical guarantee can be improved from the feature extractor when Equation (7) holds; on the other hand, in the experiment, we empirically validate the holdness of equation 7. We believe these two theoretical and empirical evidence explain how the feature extractor updates improve our target problem.\n\nWe will write those arguments more explicitly in our revision!\n\n**Relation to the related work [1]**. Thanks for connecting our work to [1]. First, as cited in section 2, we introduce it as a self-supervised feature update algorithm, which can serve for our motivations discussed at line 135-141. Moreover, we discussed in Section 3.4 on how it is particularly powerful to address online *generalized* label shift. We would like to clarify this point here:\n\nAccording to the definition of generalized label shift, it can be reduced to label shift once the learner knows the underlying feature mapping $h$, and online feature update actually helps learn the underlying feature mapping $h$ that makes $P(h(x_t)|y_t)$ invariant. In the literature of test-time training [1] and more [2, 3], they found the self-supervised learning of feature updates can explicitly align the feature space of new distribution to the feature space of training distribution; they even only trained with the feature extractor **without retrain the last linear layer**, this strongly supports the straightforward feature space alignment between original distribution and shifted distribution.\n\nWe would like to add this explanation in Section 3.4, which we believe can better explain the role of [1] when tackling the online *generalized* label shift.\n\n**Our main contribution**. Our main contribution is as a first work to bring self-supervised learning into the online label shift problem, which was mainly studied from the theoretical aspects. Our algorithm provides a way to leverage self-supervised learning, which largely improves the performance as validated through the experiments and still keeps the similar theoretical guarantees.\n\n**Limitations and broader impacts**. The goal of this work is to advance the robustness of models for real-world deployment. Our work contributes to the mitigation of different adverse effects of online label shift, such as out-of-date or miscalibrated models (e.g. healthcare or finance settings, autonomous systems such as self-driving). Adaptation to changing shifts has positive ethical implications, such as in fairness (e.g. improving the models with updated, fair data over time) or privacy (e.g. unlearning data owned by specific groups).\n\n**Difference between label distribution shift and domain adaptation**. Domain adaptation is a broader concept, including the case where the support of x can be totally different. Label distribution shift has an explicit assumption where $P(x|y)$ doesn’t change. Our algorithm and previous label shift adaptation algorithms are studied given this explicit assumption and the theoretical results are based on this assumption. While those algorithms work well for label shift, there is no guarantee that they can work well without the label shift assumption.\n\n**How to handle unseen categories**. This is actually an interesting question! As pointed out by Reviewer aV82, [4] focuses on this special setting by unsupervised estimating the portion of unseen data. We will add the discussion of this setting and the related work [4] into the related work section.\n\n[1] Y. Sun, X. Wang, Z. Liu, J. Miller, A. Efros, and M. Hardt. Test-time training with self-supervision for generalization under distribution shifts. In International conference on machine learning, pages 9229–9248. PMLR, 2020.\n\n[2] Wang, Dequan, et al. \"Tent: Fully test-time adaptation by entropy minimization.\" arXiv preprint arXiv:2006.10726 (2020).\n\n[3] Liu, Yuejiang, et al. \"Ttt++: When does self-supervised test-time training fail or thrive?.\" Advances in Neural Information Processing Systems 34 (2021): 21808-21820.\n\n[4] Qian Y Y, Bai Y, Zhang Z Y, et al. Handling New Class in Online Label Shift[C]//2023 IEEE International Conference on Data Mining (ICDM). IEEE, 2023: 1283-1288.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of online generalized label shift adaptation, proposing a feature learning stage integrated with existing methods for online label shift. The authors theoretically demonstrate the soundness of their methods and conduct a variety of experiments to show their practical effectiveness.

The paper initially received mixed evaluations, so I invited another expert reviewer. After checking all the reviews and also paper myself, I find the paper's contributions interesting and valuable to the community. Specifically, integrating the feature learning (i.e., the representation ability of deep neural networks) into online label shift adaptation is highly useful for practical applications. Therefore, I recommend the acceptance. However, several reviewers have raised constructive feedback, including suggestions to enhance the experiments to make their claims more convincing. Moreover, it is also important to discuss the storage complexity in the initial stage. Other interesting issues include how to manage new classes during the online adaptation phase, etc. The authors are encouraged to take those comments into account when revising the paper. Some issues may be acknowledged as limitations or noted for future work. It is common in scientific research to focus on certain points and leave some limitations in future studies, but it is important to discuss and acknowledge them clearly.
Decision: Accept (poster)