Test-time Adaptation in Non-stationary Environments via Adaptive Representation Alignment
Authors: Zhen-Yu Zhang
Zhiyu Xie
Huaxiu Yao
Masashi Sugiyama
Venue: NeurIPS 2024 poster (2024)
Keywords: non-stationary environments
continuous distribution shift
test-time adaptation
unlabeled data
Primary area: online_learning

Abstract: Adapting to distribution shifts is a critical challenge in modern machine learning, especially as data in many real-world applications accumulate continuously in the form of streams. We investigate the problem of sequentially adapting a model to non-stationary environments, where the data distribution is continuously shifting and only a small amount of unlabeled data are available each time. Continual test-time adaptation methods have shown promising results by using reliable pseudo-labels, but they still fall short in exploring representation alignment with the source domain in non-stationary environments. In this paper, we propose to leverage non-stationary representation learning to adaptively align the unlabeled data stream, with its changing distributions, to the source data representation using a sketch of the source data. To alleviate the data scarcity in non-stationary representation learning, we propose a novel adaptive representation alignment algorithm called Ada-ReAlign. This approach employs a group of base learners to explore different lengths of the unlabeled data stream, which are adaptively combined by a meta learner to handle unknown and continuously evolving data distributions. The proposed method comes with nice theoretical guarantees under convexity assumptions. Experiments on both benchmark datasets and a real-world application validate the effectiveness and adaptability of our proposed algorithm.

Test-time Adaptation in Non-stationary Environments via Adaptive Representation Alignment
Zhen-Yo Yu Zhang
Zhiyu Xie
Center for Advanced Intelligence Project, RIKEN zhen-yu. wwangorikeenn..ia..
Stanford University zhiyuxie@stanf
Huaxiu Yao
Masashi Sugiyama
UNC-Chapel Hill
Center for Advanced Intelligence Project, RIKEN Graduate School of Frontier Sciences, The University of Tokyo
huaxiuBcs. unc. edu
sugi@k u-tokyo.ac.
Abstract
Adapting to distribution shifts is critical challenge in modern machine learning, especially as data many real-world applications accumulate continuously in the form of streams. We investigate the problem of sequentially adapting model to non-stationary environments, where the data distribution continuously shifting and only small amount of unlabeled data are available each time. Continual test- time adaptation methods have shown promising results by using reliable pseudo- labels, but they still fall short in exploring representation alignment with the source domain in non-stationary environments. leverage non-stationary representation learning to adaptively align the unlabeled data stream, with its changing distributions, to the source data representation using sketch of the source data. To alleviate the data scarcity in non-stationary representation learning, we propose a novel adaptive representation alignment algorithm called Ada-ReAlign. This approach employs group of base learners to explore different lengths of the unlabeled data stream, which are adaptively combined by meta learner to handle unknown and continuously evolving data distributions. The proposed method comes with nice theoretical guarantees under convexity assumptions. Experiments on both benchmark datasets and a real-world application validate the effectiveness and adaptability of our proposed algorithm.
this paper, we propose
Introduction
Machine learning algorithms, particularly deep learning models, have achieved remarkable success when the test data share the same distribution of the training data. However, in many real-world applications, the learning environment is changing over time, resulting in the test data inevitably encountering natural variations. For example, once autonomous driving model is deployed, external factors such as weather changes (e.g., snow, frost, or fog) and internal factors like sensor degradation (e.g., causing Gaussian noise, defocus, blur) can negatively impact its performance. Unfortunately, many well-trained models are highly sensitive to such distribution shifts and may suffer significant performance degradation, even when the shifts are minor [12]. Moreover, once deployed, models often lack access to the original training data, making it essential to equip the learning system with the ability to adapt to -ta-ssationary environments in test time [29, 45].
promising line of research is known as test-time adaptation (TTA), which focuses on adapting mod- els to environments using only unlabeled data. Pioneering approaches consider adaptation to fixed distribution, including introducing auxiliary self-supervised learning tasks [30, 28) or employing
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

entropy minimization to update the model [26, 32]. In addition, aligning the representation of unla- beled data back to the source representation has also been proposed to improve performance [28, 10]. More recently, several seminal works have explored continual test-time adaptation with unlabeled data streams, where data arrive continuously, and the distribution may change over time. These algorithms often rely on generating and selecting high-confidence pseudo-labels to update the model, with techniques such as reliable entropy minimization [34, 25J. Non- con-paamettric approaches have also be proposed, leveraging both source labels and pseudo-labeled data for adaptation [40]. Despite these advances, the exploration of effective representation alignment with the source data representation in non-stationary environments remains underexplored.
In this paper, we propose a non-stationary representation learning approach to adaptively align the unlabeled data stream with changing distributions to the source data representation, leveraging the marginal information from the source distribution. Our framework follows a common confi confiuuration used in prior work, which assumes the model comprises representation learning module and a linear classifier [30, 32]. The core idea to continually update the representation learning module so that projects non-stationary unlabeled data at each time step to a distribution aligned with the source data representation, relying solely on the source marginal distribution. Different from prior representation alignment methods for fixed distributions [23, 28), the key challenge in non-stationary representation learning lies in the limited amount of data available at each time. Updating the model with only a single batch of data can introduce high variance due to the small sample size, while relying on the entire data stream risks high bias as the distribution evolves over time.
To handle the challenges posed by the unknown and ever changing distributions and limited data in each round, we propose novel algorithm named adaptive representation alignment AddgReAlign). Drawing inspiration from recent advances in non-stationary online learning [38, 43, 41], the represen- tation learning module employs group of base models learning with varying window sizes to explore different part of the data stream, along with meta learner that adaptively combines their output to learn a well-aligned representation. We then further refine the linear classifier by applying entropy minimization, with regularization to the initial one, based on the aligned the data representation. Our algorithm enjoys nice theoretical guarantees with convex models and loss functions, providing a solid foundation for its empirical success. Through benchmark experiments and a real-world application, we demonstrate the effectiveness and efficiency of our method in improving performance under non-stationary environments. We summarize our contributions as follow:
(1) We propose non-stationary representation learning for continual test-time adaptation, which adaptively aligns non-stationary data with the source representation using sketch of source data.
(2) We propose a novel online learning algorithm that adaptively aligns representations to the source by exploring variations across different periods of the data. Theoretical analysis demonstrates that the proposed method approximates the optimal model sequence for convex losses and models.
(3) We demonstrate the effectiveness and efficiency of our method for test-time adaptation in non- stationary environments through benchmark experiments and a real-world application.
Organization. We first introduce related work in Section 2. In Section 3, we present our main results, including the proposed algorithm with corresponding theoretical analysis. Section 4 reports the experiment results, followed by the conclusion in Section 5, All proofs and omitted details are provided in the Appendix.
2 Related Work
In this section, we present the most relevant literature related to our learning setting and the techniques used in our approach. A more detailed description is provided in Appendix B.
Continual Test-time Adaptation in Non-stationary Environments. Recently, continual test-time adaptation in non- stationary enviromments has gained significant attention. Due to the evolving nature of streaming data, the data distribution naturally changes over time. A simple idea involved recovering the model weights from the initial model after each adaptation step of mini-batch, such as MEMO [39], episodic Tent [32], or DDA [10]. However, these sequential one-step adaptation methods could be insufficient because they only explore the limited number of data each round, and thus cannot explore the knowledge of the accumulated historical data.

---

To tackle this challenge, CoTTA [34] was introduced, generating robust pseudo-labels through a weighted average of historical models while preserving the initial model's parameters. It also stochastically replaces the model's parameters with the initial model's 's parameters at each round to resist distribution change. Building on this, ECoTTA [27] and BcoTTA [20] improved param- eter and memory efficiency during continual adaptation. Similarly, SAR [25] updated the model based on reliable entropy and reset it to its initial state whenever the entropy exceeds a predefined threshold. AdaNPC [40] resisted non-stationarity by constructing a memory buffer to store historical distributions. Although these methods have demonstrated empirical success in various real-world ap- plications, they rely on prior knowledge to estimate pseudo-labels or require access to source-labeled data during adaptation.
Adapting to Non-stationary Environments with Offline Labeled Data. This line of research focuses on specific types of distribution shifts, employing adaptive learning with weighted source- labeled data to handle continuous distribution changes. Previous studies have tackled the challenge of statstaaionartty in the context of online label shift, where only the class priors change. In such scenarios, an unbiased loss estimator is used to estimate the loss at each round, enabling dynamic regret minimization in non-stationary environments [2]. Another work investigated the problem of continuous covariate shift, where only the input distribution changes [41]. They reframed this problem as an online density ratio estimation task and proposed a generic reduction of the density ratio estimation problem to dynamic regret optimization. However, these approaches assume access to the offline training data for adaptation, which may not always be feasible in practice.
3 Algorithm and Theory
We start by introducing the notations and problem formulation, followed by a detailed explanation of the proposed Ada Ada-ReAlign algorithm and its theoretical analysis.
3.1 Problem Formulation
In this part, we first formulate the learning problem. We assume access well-trained model on source data, along with a sketch of them. During adaptation, unlabeled data arrive sequentially from non-stationary environments, where the underlying data distribution could change over time. Following previous work [30, 32), we assume the model consists of a representation learning module and a linear function as classification module. Let d.(+): : X' + Rd be the representation learning module, and let the linear function be represented by matrix w, E R where i | Thus, the prediction model is defined as f.()) = (We, dc(-)). We denote the representation module of the well-trainer initial model the source data by do(.) and its corresponding linear function by wo-
As streaming data are collected non-stationary environments, the underlying data distribution remains both unknown and ever-changing The learning task is framed as sequential prediction problem over T rounds, with T > O. At each round t E [T] := {I...., T}, the learner receives a batch of unlabeled data 5, = fxx,5 N, i==, sampled independently and identically from the distribution Dr, where N, and D, could change over time. Our objective is to learn a sequence of models (f.TT, that perform well across the evolving distributions (D.),_
We define pa e Ed and Eg E Rddd as the mean and covariance of the representation distribution of the source data with the initial model, where μo = Ex=ss (x)).. Eo = Ex~s, [(o - Mo)], and d denotes the dimensionality of the feature embedding. This approach of sketching the source data does not rely on label information from the source data, which is particularly advantageous in tasks involving privacy concerns. Moreover, marginal information can be generated using coreset techniques [31, 16], eliminating the need for direct access to the original source data.
Following the online learning literature [1]], we use dynamic regret as the performance measure. The is evaluated through the average excess risk, defined as:
performance of the model sequence {
T
D-Regret ((.)t)))))))))))))
Σ R&(F)) Σ R&())) E=1
where Rf(f) E(x,y)=,, [((f()),)) x)] is the expected loss at time t with loss function e, ft arg minser (f) represents the corresponding optimal model in the hypothesis space at each round.
3

---

When the distribution of unlabeled data stream is fixed, e.g. Dj D1. vt E [T], this formulation recover back to the previous setting of TTA a stationary environment [30. 32]
Remark (Dynamic Regret and Catastrophic Forgetting). The dynamic regret defined in Eqn. (I) quantifies the difference between the performance of the learned model and the optimal model at each time step. In our formulation, the data distribution at any given time step can correspond to any previously encountered distribution, and the model has no prior knowledge of this distribution during prediction. Therefore, if the performance of the model remains comparable that of the optimal model that minimizes the expected loss at that time step, this indicates that the learned model successfully retains previously acquired knowledge and mitigates the catastrophic forgetting issue.
3.2 Representation Alignment with Source Sketch
To adapt the model to a new target domain, natural intuition that if the data in the target domain can be accurately projected back to their representation in the source domain, the well-trained source model can be reused for predictions. Based on this idca, we keep the classification module
fixed by setting W, wo and adapt the representation learning module { to ensure that the
representation of the non-stationary unlabeled data stream aligns closely with that of the source data.
We employ dynamic regret as the performance measure for representation learning in non-stationary environments and define the objective as:
T
min
Lo(or, 0o)
Lo(oi,
(2)
where (x):)) represents the representation discrepancy between di and Φo in each round, where de is the model learned at round t. Here of denotes the optimal representation learning function, defined as 6 = arg ming Le (1), Φo).
We now define the loss function :. Given the challenges in accurately estimating representation discrepancy, we propose to use a surrogate loss function to approximate it. Inspired by prior work on representation learning with deep neural networks [37, 28], we model the representation distribution using Gaussian approximation. Specifically, we measure the discrepancy as the gap in mean and covariance between the projected unlabeled data and the source data representation, defined as follows:
Lo(Ø, Φo) = |1 - uall3 + x|E, Eolli
Σ, = Ex~D, [x-xx[( (d) -14)] || ||2 denotes the Euclidean norm, and || ||| denotes the Frobenius norm. To improve numerical stability, we also add the identity matrix multiplied with a small constant to each covariance matrices E, to reduce their condition number.
where À is the hyperparameter, ر4 [x,
Since we only have empirical data at each round, we use the empirical loss to approximate the discrepancy. We define Rú Ene (x(xx)/n, and Σ, 2 ((ox((((x)) - "T) - pP)l/mm thus we have the empirical estimation of the divergence.
(Ó Φb) = |ife Po 112 + - -
(3)
At first glance, it may seem straightforward to minimize the loss defined in Eqn. (3) to update the representation learning module. However, the limited amount of data available in each round poses a challenge to obtain well- well-generalized model. Therefore, we leverage online learning techniques to reuse a suitable number of historical data, ensuring effective learning of the representation model.
Remark 2 (Comparison with Distribution Alignment Approaches). Aligning the representations of unlabeled data with those of source data has been explored in works such as [23, 28]. These studies primarily focus adapting the model to fixed domain with large amount of unlabeled data. Our problem involves adaptation to non-stationary environments, where the data distribution can change continuously with a limited number of data available in each round. This non-stationary setting requires the development of novel methods to adaptively leverage historical data for adaptation.
The proposed discrepancy measure aligns the global representation distribution between the source data and the new unlabeled data. Additionally, exploring class-specific prototypes can further enhance performance [17, 28), which we leave for future investigation.

---

Basc
14
15
1g
Lg
110
T Time
Learners
do Mo, Le
Oo, Ma-
En
KL
3
restart
Pt
KT
Ba
L
restart
KL
L
Meta Learner
restart
K
Change
Change
Change
Figure 1: An illustration of our problem and the Ada-ReAlign algorithm. The test data accumulate over time with changing distributions, and only a limited number unlabeled data are available at each step. Initially, an offline model and the statistics the offline data are provided, followed by continuous adaptation to the new distributions. Ada-ReAlign is composed of a group of base learners and a meta learner. Each base learner operates with different window size by restarting, learning representations for its respective period by minimizing the discrepancy from the source representation. The outputs from the base learners are then combined by the meta Iearner to produce the final representation.
3.3 Adaptive Representation Alignment
In this part, we present the proposed algorithm. Inspired from the online ensemble framework [43] developed in recent research non-stationary online learning, propose two-layer adaptive learning algorithm. This approach is designed to handle the unknown change in data distribution and the limited data available in each round.
Base Learner. We construct set of base learners { each with a different learning window size. These base learners initialize their parameters as Φn- As shown in Figure 1, at each round, they perform online gradient descent using the loss defined in Eqn. (3), i.e
O oi V L. 6n).
(4)
In addition to performing gradient descent, each base learner is assigned a learning window of varying size, determined by its index. As an example, the i-th base learner trains data segments of length 2'. At each round t = 2', its representation function of is re-initialized to the initial state Φ and new learning process is initiated using online gradient descent procedure we refer to as a "restart".
Intuitively, when the data distribution shifts gradually or stabilizes in a new environment, the base learner that leverages the entire historical dataset tends to perform well. In contrast, when the distribution undergoes abrupt changes, a base learner that frequently restarts and relies only on recent data can achieve competitive performance [18]. The flexibility of exploring set of base learners allows us to design a meta learner that strategically combines these base learners, optimizing the overall performance of the ensemble algorithm.
Meta Learnrr. As shown in Figure 1, we employ a meta learner to combine the base learners that learn different time length. To implement the meta learner, employ the HdaNormalHedge algorithm with the geometric covering scheme [24]. At each round, the meta learner receives a set of loss (in Eqn. (3)) from the base learners and combine them generate the output for round Let p be the weight assigned to the i-th base learner at round t. The meta leaner outputs
(xx))
Σ pl (xx)).
(5)
The weight p for each base-learner f1 at round / is updated by first calculating
p x t ( + C/ + +1) $ D( - 1, C 11;
(6)
where ((R,C) exp R /3C), L, = E. L3 and
R = Ri-1 + (L, L)), = = I1 Lz]-
We set R₁ and Cj to 0 when t = 2 for each restarted base learner.
5

---

Algorithm Adaptive Representation Alignment
1: Initialization: Vi [K], d; 60
2: for = too T do
3: for = to K do
4: 2' mod t = 0 then
5:
of Φo. R. = 0, C; =0
6: end if
7:
end for
8: update base learners by Eqn. (4) and update weight pa E Ax according to Eqn. (6)
9:
combine base learners according Eqn. (5)
10: update classifier module according to Eqn. (7)
end for
After updating the representation learning model, we follow previous studies on TTA [32, 39, 25] by employing entropy minimization with a regularization term. This regularization ensures that the updated linear classification model remains close to the initial one, enhancing performance, which is defined as
L (w x)
Σ l(w, (x))),, ( (x()))l)))) yEV
where Hl is taking the y-th entry the vector [-]. This regularization term encourages the model to generate confident predictions on unlabeled data by assigning higher probabilities to the most likely classes and lower probabilities less likely ones. As a result, it helps prevent the model from becoming overly uncertain and making unreliable predictions. We then minimize the entropy of the predictions using the updated representation learning model with regularization, that is,
W; arg miiI
C Comuro (.)x) + ||w woll2.
We summarize the main procedures of the proposed algorithm in Algorithm 1.
Remark 3 (Computational Efficiency). Since the i-th base learner is restarted every 2'-th round, within time interval of size T, only need to maintain most log(T) base learners. For example, with 7 100, 000, only 11 base learners are required. In the next section, we will demonstrate that this is sufficient achieve the optimal dynamic regret for convex losses and models.
Note that the ensemble structure requires maintaining multiple base learners, to further enhance the computational efficiency, follow the spirit of [42] to reduce the base learners' update complexity, which involves updating only the affine parameters of the normalization layers similar to those used in previous studies [21, 32, 28, 25]. The affine parameters typically comprise less than 1% of the total model parameters [32], making them particularly efficient to update.
3.4 Theoretical Analysis
In this part, we provide the theoretical analysis of our proposed Ada Ada-ReAlign algorithm for convex losses and models. For convex representation learning models, such as input convex neural net- works [1], and convex loss functions, we show that the proposed algorithm achieves a dynamic regret guarantee, using the optimal representation sequence {øz YT= as the comparator.
Theorem 1. Assuming th is convex, La La(#) is convex with respect to d, and the input x the value of the loss function, and its gradient are all bounded. The Ada-Re Ree-Rel algorithm satisfies
EE Σ L.(0) - En1oss) -
30(12/3/1/9)
1=1
where function variation VT Ei= sups (L(()) La ( Detailed proofs are Appendix C.I.
Theorem demonstrates that the average regret decreases at a rate O(T-1/3). In this theorem, the function variation Vr captures the cumulative change in the optimal representation function sequence,

---

serving as measure of the underlying distribution shift in non-stationary environments and reflecting the inherent difficulty of the learning task. When the unlabeled test data stream generated from relatively stable environment, indicated by small Vr, the accumulative loss decreases nearly at a rate of ((22/5). We notice that directly optimizing Eqn. (3) in each round would result in (IT) regret, as a generalization error would accumulate in every round. Thus, Theorem provides the theoretical foundation for the empirical success of the Ada-ReAlign algorithm in effectively adapting to unknown and continuous distribution shifts.
4 Experiments
We evaluate the proposed Ada-ReAlign algorithm on two large-scale benchmark datasets: CIFARIO6 and ImageNerC. Our empirical studies aim to answer the following three questions: Q1: Does the Ada-Rea ReAlign algorithm outperform competing methods? Q2: Are the mechanisms in the proposed algorithm effective in handling non-stationary data? Q3: Can the proposed method handle real-world data streams with unknown distribution shifts?
4.1 Experimental Setups
Data Stream Generation. The CIFARIOC and ImageNetC datasets provide both original clean data and corrupted data with varying types and levels of severity. We train the offline model on the clean data and the corrupted data to generate unlabeled data streams, allowing to simulate diverse distribution shifts within the data stream.
We assume small batch of data is obtained at each round 1, where i E [T] (1....,7) 7). In each round, this batch is generated from a fixed data distribution with a specific corruption type and severity level. By continuously varying the corruption types severity levels, we simulate unlabeled data streams across different non-stationary environments, Let N, denote the number of data points in round and M represent the duration for which the data distribution remains unchanged, spanning M rounds between distribution shifts.
In our empirical studies, we simulate two common types of distribution shifts:
(1) Gradual Shift:
To simulate unlabeled data stream with a gradual shift, we keep the type of data corruption constant throughout the stream while varying the severity level every M rounds. For example, in an unlabeled stream representing the "Snow" condition, the severity levels change sequentially as follows: [1] MM + [2] M + [3] M ..... Here, [1] * M denotes M consecutive rounds of data under the "Snow" condition with severity level of 1.
(2) Sequential Shift: To simulate an unlabeled data stream with a sequential shift, we keep the corruption severity level constant throughout the stream while changing the type of data corrup- tion every M rounds. For instance, with a fixed severity level of 5, the corruption types evolve sequentially follows: [gaussian] * MM [shot] M + [impulse] * M - ... Here, [shot] M represents M consecutive rounds of data with "shot" at severity level 5. In this paper, we set the severity level of the sequentially shifting data stream to 5.
Contenders. We compare the proposed algorithm with six competing methods. First, we use the performance of the initial Non-adapt model as a baseline. Next, we include methods that restart the model at each round and adapt based on the current round's 's data: TENT-RE [32], which minimizes entropy at each round, and MEMO [39], which enhances robustness through data augmentation. We also evaluate methods that leverage all the data, such TENT-CT, which updates the model using the results from the previous round via the TENT [32] and TTAC [28], which focuses on aligning the representation with the initial model using the entire data stream. Additionally, we include two state-of-the -frt--rrr TTA methods designed for non-stationary environments: CoTTA [34] and SAR [25], both of which incorporate reset mechanism to mitigate long-term forgetting during adaptation.
Implementation Details. We conduct experiments using a deep neural network with a ResNet50 architecture from the torchvision library. The initial model is trained on the original CIFAR- 10 and ImageNet datasets. For our proposed algorithm, we use SGD as the update rule, with a momentum of 0.9 and learning rate of 0.0005. Following prior studies [21, 32, 28, 25J, adapt the affine parameters of the normalization layers in ResNet50 during the adaptation process. Further details are provided in Appendix A.1.
7

---

Table 1: The average classification error (in %) for the CO-AAIO----CFARRRO dataset under Gradual Shift. All
results were averaged over 5 runs with different initializations. The number of data points per round was set with a duration of
N.
10.
The best results are highlighted in bold.
Method
Gauss.
shot
impul.
defoc
glass
motio.
zoom
snow
Irost
log
brigh.
contr.
clast.
pisel.
Jpeg
Mean
Non adapi
30.8
13.8
18.3
17.2
20.3
22.7
15.1
16.3
17.1
23.5
22.7
21.5
10.6
20.4
20.1
+1.7
+1.1
=0.8
20.4
20.3
10.2
40.4
=0.4
10.1
=0.2
=0.1
20.4
=0.8
MEMO
31.8
26.0
24.7
13.5
38.1
17.9
17.0
16.9
19.1
12.3
14.5
14.6
20.7
17.3
19.6
+0.4
+0.3
+0.2
+1.2
+1.0
+-0.7
+0.6
+0.5
+0.3
+0.3
-0.5
40.2
+0.3
-0.2
+0.6
+0.7
TENT-RE
32.4
25.1
24.1
14.2
37.6
18.1
17.2
15.4
19.7
9.20
13.7
14.2
20.4
18.1
18.5
+0.3
+0.3
+0.4
+1.5
+0.99
+1.1
+0.77
+0.6
+04
+0.2
-0.6
+0.3
+0.5
-0.3
+0.6
+0.9
TENT CT
26.3
21.7
22.4
11.9
26.4
14.5
13.4
13.9
15.5
11.0
6.82
11.6
14.8
15.3
16.0
15.4
1:0.3
102
10.3
11.0
10.8
20,9
10.5
10.4
20.3
10.3
:0.5
10.3
204
=0.2
10.5
20.5
TTAC
24.6
22.0
22.2
10.8
25.7
12.7
10.1
12.9
14,4
10.7
5.52
10.3
14.2
13.8
15.1
14.3
1:0.2
10.4
10.5
10.9
10.7
20,9
10.6
20.5
20.3
10.4
20.3
10.1
20.5
20.3
10.4
20.5
COTTA
22.1
20.6
23.0
9.80
25,3
10.7
8.08
12.2
12.6
10.2
5.90
8.20
14.3
12.5
15.3
14.1
+.0.4
+0.3
+0.5
#1,1
+0.8
+0,8
+0.7
404
-0.5
40,3
-02
40.3
-04
=022
+0,3
-0.6
SAR
20.6
19.3
21.9
8.00
24.1
9.13
5.96
10.4
10.7
9.21
4.12
6.92
13.2
11.3
134
12.6
+0.5
+0.3
+0.4
+1.0
+0.7
+0.6
+0.6
+0.5
-0.4
40,3
-0.3
+0.4
+02
-0.3
+0,3
-05
Ada-RcAlign
20.6
19.8
21,1
8.19
23,4
8.72
5,30
10.4
11.1
9.04
431
6.29
12.6
1288
12.7
11.8
1006
+0.5
40.5
41.2
40.6
+0.8
+0.5
20.4
+0.3
40.1
-03
40.5
-0.1
-02
+0.4
-0.7
Table 2: The average classification error (in %) for the CI-FRIIOC dataset under Sequential Shift. All results were averaged over 5 runs with different initializations. The number of data points per round was set to N₂- = 10 with a duration of M =
10. The best results are highlighted in hold.
Methed
Gauss.
shot
impul.
defoc.
plass
mohio
frest
fog.
brigh.
clast.
jpeg
Mcan
Non-sdapt
48.4
44.8
50.3
24.1
47.7
24.5
24.1
24.1
35.1
28.0
14.1
29.7
25.6
43.7
28.3
32.7
+0.8
+1.1
+002
+2.3
+1.8
+1.2
+0.4
+0.4
+0.6
+0.3
-0.5
+0.1
+0.3
-0.1
+00.7
+1.0
MEMO
43.5
39.8
43.3
26.4
44.4
25.1
25.0
20.9
28.3
22.8
11.9
28.3
21.1
42.8
21.7
30.4
+0.6
+1.0
+0.
+0.9
+1.1
+1.1
+0066
+0.3
+0.6
+0.5
-0.7
+0.1
+0.55
-0.2
+0.2
+1.1
TENTRE
43.6
37.8
42.3
25.1
43.6
26.1
24.8
22.1
27.3
21.1
10.1
29.0
20.9
42.6
22.2
28.2
+2.0
11.1
10.3
11.4
11.
11.5
10.0
20.1
=1.
10.7
20.4
10.3
102
20.4
10.5
#1.8
TENT-CT
38.6
34.4
42.4
28.2
44.9
30.3
27.9
32.9
32.4
324
26.0
34.1
39.5
34.6
38.7
34.2
+1.5
+0.9
+0.5
#1.1
+1.0
+1.2
+0.1
+0.2
=0.7
+0.5
=0.5
+0.6
=0.1
=0.4
+0.2
+1.4
TTAC
33.6
29.6
36.3
22.7
37.7
23.1
22.2
28.0
25,8
26,8
20.1
26.1
33.2
26.7
33.9
28.0
+1.0
+0.8
+0.3
+1.5
+1.
#1.1
+0.4
+0.3
-0.9
+0.6
=0.4
+0.8
=0.4
=0.7
+0.6
+1.
COTTA
25.7
27.3
30,1
38.5
34.4
35.7
32.5
10.8
11.1
10.8
11.9
112
10.9
10.6
10.5
11.0
10.5
-0.6
10.7
10.3
10.6
10.4
11.
SAR
27.5
19.7
23,4
22.2
23.0
30,9
24,9
11.1
108
10.7
11.7
11.0
10.9
10.5
10.6
10.9
10.6
2044
10.5
10.4
108
10.3
11.
Ada-KeAlign
23.8
13.9
15.2
20,3
12.2
19.2
19.6
27.1
21.1
11.
10.9
10.6
11.5
113
10.8
10.3
10.7
10.8
10.6
0.2
10.6
10.3
0.9
10.2
199
4.2 Performance Comparison
We present the comparison results for the CUPARR10to-CIFARIOO datasets in Table and Table 2. Results for the ImageNNttto-ImageNNe datasets are provided in Appendix A.2, where we observe similar trends. Our proposed Ada-ReAlign algorithm consistently achieves top performance un- der both gradual and sequential shifts, particularly in sequential shift scenarios, highlighting its adaptability in diverse non non-stationary environments.
In Table 1, we report the average classification error rate, along with the standard deviation, for gradual severity shifts across 15 types of distribution shifts. These results are based on batches of N₂ 10 data points per round, with a distribution duration of M 10 rounds, averaged over five runs with different initial models. Overall, our algorithm demonstrates competitive performance compared to other methods. We also observe performance improvements from TENT-CT and TTAC, which reuse all historical data, underscoring the importance of effectively leveraging past data. Meanwhile, Ada-ReAlign outperforms CoTTA and SAR, both of which incorporate reset mechanisms to enhance adaptability to severity shifts.
In Table 2, we evaluate the algorithm across the entire data stream and report its average accuracy for each type of data corruption. By effectively reusing historical data, our proposed Ada- ReAlgn algorithm achieves lower average classification error across all types of distribution shifts compared to the competitors. Notably, MEMO and TENT-RE, which reuse only the current batch of data, outperform TENT-CT, which utilizes all historical data. These findings align with theoretical analysis, confirming that a fixed adaptation model is not well-suited for non-stationary environments.
Additionally, COTTA, which stochastically resets parts of the model parameters to their initial values, also underperforms in non-stationary settings. This further highlights the superiority of our adaptive representation alignment algorithm. These results answer the question Q1.
8

---

Average Error (1S)
budo
Avemun
interaa longth INI
Intervalenntt OK 21
Time
Processing Time per Round (sec)
(a) Sequential shift
(b) Berouulii shift
(a) Sequential Shift
(b) Algorithm efficiency
Figure 2: Weight (%) heatmap of base learners in (a) Sequential shift with different intervals. (b) Berouuli sequential shift with different intervals, where the length of interval is an expected value.
Figure 3: (a) Average error (%) and estimator loss curve with continuous sequential shift. (b) Average error (%) and processing time per round (sec) of three contenders with two kinds of distribution shifts.
4.3 Ablation Study
Next, we evaluate the adaptability of the Ada-ReAlign algorithm changing distributions, along with its computational efficiency and the effectiveness of each component. Additional ablation studies on the impact of the number of data each round N, and duration M are provided in Appendix A.3.
Detailed Analysis of the Meta-Base Structure in Ada-ReAlign. We now take closer look at our adaptive representation alignment algorithm, which integrates meta-base structure. Specifically, we conduct experiments to evaluate the algorithm's s ability to handle scquential shifts, where the distribution of online data alternates between two distributions every M rounds. To explore this, vary the duration M and report the weight assignment (expressed as percentages) for base learners with different interval lengths in Figure 2. For instance, when M 8, the data distribution shifts every 8 rounds. The weights assigned to each base learner are averaged over its active period.
Our results show that the meta learner effectively assigns the highest weight to the base learner whose interval length aligns with the switch period M. This result shows that the right amount of historical data is reused, leading to strong performance in non-stationary environments.
In addition, in Figure 3 (a) compares the average error of the Ada-ReAlign algorithm with that of the TTAC algorithm over 200 iterations. During the experiment, the data distribution shifts three times, transitioning from Noise "Gaussian" to Blur "defocus", then to Weather "Snow", and finally to Digital "contrast". Each distribution is maintained for 50 iterations. TTAC is chosen for comparison since it also aims align the model's representation with the initial one.
The results show that the Ada- ada-ReAlign algorithm adapts quickly to new distributions as soon as a shift occurs. In contrast, the TTAC algorithm struggles, as it relies on all historical data, including samples from different distributions, which limits its adaptability.
Efficiency and Performance Evaluation. We conduct additional experiments to evaluate the algorithm's 's efficiency and performance gain. Specifically, we measure the processing time per round and the average accuracy, comparing the proposed algorithm with SAR (single model with forward and backward procedures) and AdaNPC (single forward procedure only) [40]. Since AdaNPC requires access the labeled source data during adaptation, we exclude it from the main comparison.
As shown in Figure 3 (b), the Ada- Ada-Re algorithm demonstrates superior performance in both gradual and sequential shifts on the CIFAR 10-tt-0IIFAARRA dataset. In terms of computational time, Ada-ReAlign (with base learners) is approximately five times slower than SAR. However, SAR involves solving a bi-level optimization problem during adaptation, which incurs additional computational overhead. AdaNPC is more efficient than both gradient- baaden algorithms, as it employs KNN-based porreeraettiic classifier. These findings answer the question Q2.
Component Analysis of the Proposed Algorithm. We evaluate the impact of each component within the proposed algorithm in the sequential shift environment. The proposed algorithm consists of two elements: alignment of the representation divergence with the initial model and minimization of prediction entropy at each round. To investigate their individual contributions, we run the algorithm across the entire data stream using different loss configurations. Specifically, "Ada-ReAlign w/o DA" refers to the version where only prediction entropy is minimized at each step (without Distribution Alignment), while "eda-ReAlign w/o EM" denotes the version where only the representation aligned at each round (without Entropy Minimization).

---

Figure Average Classification Error (%) Compari-
Figure Average Classification Error (%) Compari- son with Different Restart Mechanisms.
son with Various Components.
We report the average accuracy for each type of data corruption. As shown in Figure 4, both representation alignment and entropy minimization play crucial roles in the performance of the Ada-ReAlign algorithm. Moreover, the results highlight that, in most cases of distribution shifts, representation alignment offers greater performance gains, underscoring the importance of adaptive representation alignment non-stationary environments.
Comparison with Restart Mechanisms. We compare the proposed algorithm in a sequential shift environment with three different restart mechanisms: Ada-RE, Ada-CT, and Ada-TS. In Ada-RE, the model is reset to the initial offline model at the beginning of each round and undergoes "one-step" TTA using the surrogate loss defined in Eqn (3). This approach is similar the MEMÓ and TENT-RE algorithms, which restart the model at each round.
The second method, Ada-CT, updates single model continuously, where the adapted model from the previous round serves as the initial model for the next. The third approach, Ada-7S, also employs a single model but incorporates restart mechanism based threshold for model entropy. Following the previous study [25], we restart the model whenever the entropy falls below a threshold of 0.4.
The average accuracy of our proposed method and the three competing approaches is presented in Figure 5. The datasets. These results highlight the critical role of the meta learner in the online ensemble structure, which enables the adaptive combination of base learners to resist the non-stationarity.
algorithm consistently outperforms the competitors across nearly all
4.4 Real- World Evaluation on Wildlife Species Classification
We further evaluate the proposed algorithm on real-world wildlife species classification task using the iWildCam dataset [3], where the distribution of images naturally varies with the time and location of capture. The earliest 10% of the data is used labeled offline data to train the initial model, while the remaining data serves as the unlabeled data stream. We compare the performance of our method against competing approaches, and the results demonstrate that our algorithm achieves the best performance. These results answer question Q3.
Table 3:
The Average Classification Error (%) for iWildCam dataset. All results averaged over 5 runs with different initial models. We set number of data N, 10 cach round.
Method
Non-udapt
TTAC
CoTTA
SAR
Ada-ReAlign
Classification Error (%)
47.2 = 2.3 27.3 1.9
29.3 + 2.0
31.5 + 2.4
23.6 1.8
5 Conclusion
In this paper, we explored non-stationary representation learning for continual test-time adaptation. Beyond entropy minimization with regularization, we proposed adaptively aligning the unlabeled data stream, with its evolving distributions, to the source data representation by leveraging sketch of the source data. To exploit this marginal information, we introduced a novel two-layer algorithm, Ada-ReAlign, designed to track and to approximate the optimal representation learning model at each round. Our theoretical analysis showed that the learned model comparable to the optimal model sequence under convexity assumptions. Experiments on various benchmark datasets and a real-world application demonstrated the superiority of our approach over competing methods, confirming the effectiveness of the adaptive representation alignment mechanism.
10

---

Acknowledgments
MS was supported by the Institute for Al and Beyond, UTokyo.
References
[1] Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 146-155, 2017.
[2] Yong Bai, Yu-Jie Zhang, Peng Zhao, Masashi Sugiyama, and Zhi-Hua Zhou. Adapting to online label shift with provable guarantees, Advances Neural Information Processing Systems (NeurIPS), 35:29960-29974, 2022.
[3] Sara Beery, Arushi Agarwal, Elijah Cole, and Vighnesh Birodkar. The iwildcam 2021 competi- tion dataset. arXiv preprint arXiv:2 00444449, 2021.
[4] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- lions Research, 63(5):1227-1244) 2015.
[5] Dian Chen, Dequan Wang. Trevor Darrlll, and Sayna Ebrahimi. Contrastive test-time adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 295 195-305,22 2022.
[6] Yining Chen, Haipeng Luo, Tengyu Ma, and Chicheng Zhang. Active online learning with hidden shifting domains. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2053-2061, 2021.
[7] Chao-Kat Chiang, Tianbao Yang. Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Proceedings of the 25th Conference on Learning Theory (COLT), pages 1-20, 2012.
[8] Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: standardized ad- versarial robustness benchmark. Advances in Neural Information Processing Systems (NeurIPS) Datasets and Benchmarks Track, 34, 2021.
[9] Yulu Gan, Yan Bai, Yihang Lou, Xianzheng Ma, Renrui Zhang, Nian Shi, and Lin Luo. Decorate the newcomers: Visual domain prompt for continual test time adaptation. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 37, pages 7595-7603, 2023.
[10] Jin Gao, Jialing Zhang, Xihui Liu, Trevor Darrell, Evan Shelhamer, and Dequan Wang. Back the source: Diffusion- driven adaptation to test-time corruption. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 11786 1766-11777 11796, 2023.
[11] Elad Hazan. Introduction Online Convex Optimization. Foundations and Trends in Optimiza- tion, 2(3-4):157-325, 2016.
[12] Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
[13] Dan Hendryeks, Norman MU, Ekin Dogus Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshminarayanan. Augmix: A simple data processing method to improve robustness and uncertainty. In Proceedings of the 8th International Conference Learning Representations (ICLR), 2020.
[14] Judy Hoffmman, Trevor Darrell, and Kate Saenko. Continuous manifold based adaptation for evolving visual domains. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 867 2014.
[15] Xuefeng Hu, Gokhan Uzunbas, Sirius Chen, Rui Wang, Ashish Shah, Ram Nevatia, and Ser- Nam Lim. Mixnorm: Test-time adaptation through online normalization estimation. arXiv preprint arXiv:2110.11478, 2021.
11

---

[16] Jonathan Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable bayesian logistic regression. Advances Neural Information Processing Systems (NIPS), 29:4080-4088, 2016.
[17] Yusuke Iwasawa and Yutaka Matsuo. Test-time classifier adjustment module for model-agnostic domain generalization. Advances in Neural Information Processing Systems (NeurIPS), 34:2427- 2440, 2021.
[18] Bartosz Krawezyk, Leandro L Minku, Joao Gama, Jerzy Stefanowski, and Michal Wozniak. Ensemble learning for data stream analysis: A survey. Information Fusion, 37:132-156, 2017.
[19] Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self-training for gradual domain adaptation. In Proceedings of the 37th International Conference Machine Learning (ICML), 2020.
pages
[20] Dacun Lee, Jachong Yoon, and Sung Ju Hwang. Becotta: Input-dependent online blending of experts for continual test-time adaptation. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 27072-27093, 2024.
[21] Jian Liang, Dapeng Hu, and Jiashi Feng. Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation. In Proceedings of the 37th International Conference on Machine Learning (ICMI.), pages 6028-6039, 2020.
[22] Hyesu Lim, Byeonggeun Kim, Jaegul Choo, and Sungha Choi. TTN: A domain-shift aware batch normalization test-time adaptation. In Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023.
[23] Yuejiang Liu, Parth Kothari, Bastien Van Delft, Baptiste Bellot-Gurlet, Taylor Mordan, and Alexandre Alahi. TTT+:: When does sulf--uue test-time training fail or thrive? Advances in Neural Information Processing Systems (NeurIPS), 34:21808 21820, 2021.
[24] Haipeng Luo and Robert E Schapire. Achieving all with no parameters: Adanormalhedge. In Proceedings of the 28th Conference on Learning Theory (COLT), pages 1286-1304, 1304, 2015.
[25] Shuaicheng Niu, Jiaxiang Wu, Yifan Zhang, Zhiquan Wen, Yaofo Chen, Peilin Zhao, and Mingkui Tan. Towards stable test-time adaptation in dynamic wild world. In Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023.
[26] Steffen Schneider, Evgenia Rusak, Luisa Eck, Oliver Bringmann, Wieland Brendel, and Matthias Bethge. Improving robustness against common corruptions by covariate shift adaptation. Advances in Neural Information Processing Systems (NeurIPS), 33:11539-11551, 2020.
[27] Junha Song, Jungsoo Lee, In So Kweon, and Sungha Choi. Ecotta: Memory-efficient continual test-time adaptation via self-distilled regularization. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 11920-11929, 2023.
[28] Yongyi Su, Xun Xu, and Kui Jia. Revisiting realistic test-time training: Sequential inference and adaptation by anchored clustering. Advances in Neural Information Processing Systems (NeurIPS), pages 17543-17555 2022.
[29] Masashi Sugiyama and Motoaki Kawanabe. Machine Learning in Non-Stationary Environments Introduction to Covariate Shift Adaptation. MIT Press, 2012.
[30] Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt. Test-time training with self-supervision for generalization under distribution shifts. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 9229-9248, 2020.
[31] Ivor W Tsang, James T Kwok, Pak-Ming Cheung, and Nello Cristianini. Core vector machines: Fast svm training on very large data sets. Journal of Machine Learning Research, 6(4):363-3) 2005.
[32] Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization. In Proceedings of the 9th International Conference Learning Representations (ICLR), 2021.
12

---

[33] Haoxiang Wang, Bo Li, and Han Zhao. Understanding gradual domain adaptation: Improved analysis, optimal path and beyond. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 22784-22882 22801, 2022.
[34] Qin Wang. Olga Fink, Luc Van Gool, and Dengxin Dai. Continual test-time domain adaptation. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 7201-7211, 2022.
[35] Chen- Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Proceedings of the 34th Conference on Learning Theory (COLT), pages 4300-4354, 2021.
[36] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. In Proceedings of the 9th International Conference on Learning Representations (ICLR). 2021.
[37] Werner Zellinger, Thomas Grubinger, Edwin Lughofer, Thomas Natschläger, and Susanne Saminger-Platz, Central moment discrepancy (cmd) for domain-invarian representation learn- ing. In Proceedings of the 5th International Conference on Learning Representations (ICLR),
2017.
[38] Lijun Zhang, Shiyin Lu, and Tianbao Yang. Minimizing dynamic regret and adaptive regret simultaneously. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 909-319, 2020.
[39] Marvin Zhang. Sergey Levine, and Chelsea Finn. Memo: Test time robustness via adaptation and augmentation. Advances in Neural Information Processing Systems (NeurIPS), 35:38629- 38642, 2022.
[40] Yifan Zhang, Xue Wang, Kexin Jin, Kun Yuan, Zhang Zhang, Liang Wang, Rong Jin, and Tieniu Tan. Adanpe: Exploring non paraamametriic classifier for test-time adaptation. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 41647-41677 2023.
[41] Yu-Jic Zhang, Zhen- Yu Zhang, Peng Zhao, and Masashi Sugiyama. Adapting to continuous covariate shift via online density ratio estimation. Advances in Neural Information Processing Systems (NeurIPS), 36:29074-299
2023.
[42] Peng Zhao, Yan-Feng Xie, Lijun Zhang, and Zhi-Hua Zhou. Efficient methods for non-stationary online learning. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 11573-11585, 2022.
[43] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou, Adaptivity and con-stationariity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learn- ing Research, 25(98):1 52, 2024.
[44] Shiji Zhou, Han Zhao, Shanghang Zhang, Lianzhe Wang, Heng Chang, Zhi Wang, and Wenwu Zhu. Online continual adaptation with active self-training. In Proceedings of the 25th In- ternational Conference on Artificial Intelligence and Statistics (AISTATS), pages 8852 8883, 2022.
[45] Zhi-Hua Zhou. Open-environment machine learning. National Science Review, 9(8), 07 2022.
nwac 123.
[46] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928-936. 2003.
13

---

Appendix
A Experiments
In this section, we supplement the omitted details in Section We begin by presenting a comprehen- sive overview of the experimental setups, followed by showcasing the previously omitted empirical results on ImageNet dataset. Furthermore, we conduct additional ablation studies to further investigate the proposed Ada-Ree dda-ReAlign algorithm.
A.1 Experimental Setups
Contenders. We compare our proposed approach with six contenders, including baseline method,
Non-adapt: This method directly uses the offline model make predictions the unlabeled data stream without any adaptation.
One modified "one-round" TTA method is employed, where the model parameters are reset to the offline model at the start of each round and then undergo one-step adaptation:
MEMO [39]:
This method applies various data augmentations to each input and adapts all model parameters by minimizing the entropy of the average output distribution across these augmentations. At the beginning of each round, the model parameters are reset to those of the offline model.
Two continuous TTA methods are also evaluated, where the model is updated throughout the entire data stream without resets:
TENT [32]: This method optimizes the channel-wise affine transformations within the normalization layers by minimizing the entropy of the model's predictions.
TTAC [28]: This approach introduces a test-time anchored clustering method improve the aligmment of test-time features with the offline model's learned representation. It also employs pseudo-label filtering to enhance the effectiveness of the clustering process.
Additionally, include two otate-of-the-art continuous TTA methods specifically designed to address distribution shifts in non-stationary environments:
CoTTA [34]: This algorithm continuously adapts by learning pseudo-labels from its own predictions. It leverages weight-averaged and augmentation-aaverage predictions to produce more reliable pseudo-labels for the unlabeled data stream.
SAR [25]: SAR is sharpness-aware algorithm that minimizes entropy while ensuring robustness by filtering out noisy samples with large gradients. encourages the model weights to converge to flat minimum, improving resilience noisy labeled data.
In summary, these contenders cover a wide range of continuous TTA approaches, from methods that rely on individual batches of data to those that incorporate the entire data stream. Our comparison also includes offte-of-thh-an algorithms specifically designed to handle distribution shifts in non-stationary environments.
Algorithm Implementation Details of Contenders. For the remaining contenders, we provide their detailed hyperparameter settings used in the experiments follows.
MEMO [39]: We adopted the default
settings used in MEMO. Specifically, we employed AugMix [13] for data augmentations, with an augmentation size of 32, The optimizer is SGD with momentum of 0.9, batch size of 32, and learning rate of 0.0005.
TENT-RE [32]: We adopted the default pyper-parameter settings used in TENT. The opti- mizer is SGD with momentum of 0.9, a batch size of 32, and learning rate of 0.0005. The trainable parameters are the affine parameters within the batch normalization layers. At the start of each round, the model parameters are reset to match those of the offline model.
14

---

Table 4: The average classification error (in %) for the ImageNet-to-Imageee ImageeeeCC cataset under Gradual Shift. All results were averaged over with different initializations. The numher of data points per round was set No- with a duration of
10. The best results are highlighted in bold.
Method
Gauss.
shot
impul.
defoc.
glass
motin.
zoom
snow
first
Fog
brigh.
contr:
elast.
pixel.
ipeg
Mcan
Non-adapt
32.3
82.6
72.4
79.1
62.9
61.7
86,3
83.1
85.3
66.4
72.1
68.7
86.8
74.9
65.7
72.1
+0.3
+0.4
-0.2
+0.6
+0.7
+0.5
+0..3
+0.2
+0.2
+0.3
+0.5
+0.6
+04
+0.3
+0.3
+0.55
MEMO
32.7
76.3
69.8
55.1
54.3
58.7
82.7
78.2
81.2
55.7
54.5
51.2
80.8
65.5
48.8
62.9
20.5
208
=0.7
10.9
=1.3
10.5
20.5
20.6
20.4
#0.2
=0.3
+0.3
20.4
20.5
20.4
20.6
TENT-RE
33.3
69.9
73,5
60.3
50.8
59.4
80,3
81.7
79.0
60.9
62.0
57.6
80.6
63.0
49.9
64.1
#0.7
+1.0
=1.3
#1,2
=1.7
#1.4
20.5
20.5
20.7
20.4
#0.2
20.6
20.3
20.5
20.4
#0.6
TENT-CT
34,6
42.5
73.4
38.9
39,3
60.6
81,9
83.4
75.6
50.7
44.0
37.7
80.9
52.4
42.0
55.8
+0.2
+0.6
-0.5
+0.8
+1.2
+0066
+0.5
+0.5
+0.4
-0.6
+0.7
+0.5
+0.6
+0,4
+0.8
TTAC
35.5
43.0
63,2
44.5
40.5
48.7
60.6
67.2
71.0
49.0
45.1
39.1
$6.9
48.2
41.9
50.3
10.5
=0.6
11.7
=19
11.
20,8
10.4
=0.5
10.3
10.7
=0.4
20.8
CoTTA
32.6
40.4
64.1
37.3
36.4
46.5
63.4
69.3
64.2
46.5
40.8
38.5
61.7
44.1
39.1
48.3
10.7
10.6
=04
12.0
=1.5
10,9
10.7
20.3
20.7
10.3
=0.2
20.3
=0.3
10.6
SAR
32.8
41.7
65.3
39.5
33.5
42.7
60.4
61.2
63.2
49.3
55.6
35.3
55.0
44.9
41.5
48.5
+0.7
+0.5
=0.7
+1.6
-1.3
+1.2
+12
+088
+0.6
+0.5
+0.5
+0.7
+0.3
+0.6
+0.7
+0.8
Ada-RcAlign
35.7
42.0
61.6
38.0
37.8
42.5
55.3
67.0
57.1
47.3
44,8
33.1
53.5
45.7
39.2
46.6
+0.5
+0.6
-0.6
+1.5
=1.6
+1.8
+0,4
+0.6
-0.
+0.3
+05
40.7
+0,4
+03
+0.6
+0.9
TENT-CT [32]: We adopted the default hyper-parameter settings used in TENT. The opti- mizer SGD with a momentum of 0.9, a batch size of 32, and a learning rate of 0.0005. The trainable parameters are the affine parameters within the batch normalization layers.
TTAC [28]: We adopted the default hyper-parameter settings used TTAC. The optimizer is SGD with momentum of 0.9, a batch size of 32, and a learning rate of 0.0005. The trainable parameters are the affine parameters within the batch normalization layers.
settings used in CoTTA. The optimizer is Adam with a learning rate of 0.001. We use the default data augmentation techniques in the CoTTA algorithm. We updated all trainable parameters while incorporating restoration probability of 0.01 to mitigate the risk of catastrophic forgetting.
CoTTA [34]: We adopted the default
SAR [25]: We adopted the default hyper-parameter settings used in SAR. The optimizer is SGD with a momentum of 0.9. batch size of 32, and learning rate of O. 0.0005. To clip the large gradients, we applied a threshold set to 0.4 x In 1000, Additionally, we set to 0.05 to encourage the optimization process converge towards flat minima, following the default settings. For model recovery, we tracked the entropy loss values using a moving average factor of 0.9. The trainable parameters are the affine parameters within the batch normalization layers.
Algorithm Implementation Details. We adopt the standard ResNet-50 model from RobustBench [8] as the model structure. We freeze the top two linear layers and only update the affine parameters of the normalization layers within the remaining shallow layers of ResNet-50. The optimizer employed SGD, with a momentum of 0.9 and a batch size of 32 for rounds where the number of data data exceeds 32. In cases where the number of data in a round is smaller than 32, we employ data augmentation techniques [39] to augment the data and ensure its number reaches minimum of 32. The learning rate is set to 0.0005. We use the following compute resource configuration: 2 Xeon Gold 6242R with a base frequency of 3.1 GHz, GeForce 3090 with 24GB VRAM, and total of 768GB RAM. The operating system employed is Ubuntu 20.04.
A.2 More Empirical Results on ImageNet-C for Section 4.2
Table 4 and Table present the omitted results from Section 4.2. The results show that Ada-Re outperforms the competing methods across nearly all tasks in the ImageNet-C dataset. These empirical findings confirm the effectiveness of our approach in adapting to non-stationary environments.
A.3 Additional Ablation Studies
The number of data points in each round a crucial measure of non-stationarity in the environment. As data accumulate continuously, and assuming that the data received in each round are generated from the same distribution, the number of data points per round serves as an indicator of the speed of distribution shifts. For fixed duration M, a smaller number of data points per round suggests
15

---

Table 5: The average classification error (in %) for the CoangeNNetto--mageNeer dataset under Sequential Shift. All results were averaged over 5 with different initializations. The numher of data points per round was set to No- with a duration of
10. The best results are highlighted in bold.
Method
Gauss.
shot
impul.
defoc.
glass
motin.
zoom
snow
first
Fog
brigh.
cantr:
elast.
pixel.
Ipeg
Mcan
Non-adapt
37.3
90.9
82.8
87.0
65.2
74.5
97.2
92.8
97.9
68.7
82.4
80.3
97.0
828
73.9
80.7
+0.11
+0.1
-0.2
+0.4
+0.6
+0.5
+0.66
+0.2
+0.3
+0.3
+04
+0.2
+0.4
+0.2
+0.5
+0.4
MEMO
36.3
81.2
80.1
63.8
58.2
69.4
93.5
86.8
92.4
60.1
65.8
62.0
91.4
69.3
59.6
71.3
=0.4
20,9
=0.7
20.5
=1.7
10.6
20.8
#1.2
#1.6
10.6
#0.5
20.4
20.7
20.5
20.4
20.9
TENT-RE
38.5
78.4
81,9
70.1
55.7
70.6
90.4
88.9
90.3
65.2
73.1
66.8
90.6
66.2
60.5
72.4
20.5
#1.5
=0.5
#1,2
=1.7
#1.2
#0.6
20,6
20.4
#1.5
#1.9
#1.1
204
20.8
20.5
#1.2
TENT-CT
38.9
48.1
83,9
49.7
43.8
72.7
91.6
92.1
88.6
54.3
57.1
47.7
92.0
56.7
52.7
64.6
+0.3
+1,9
-0.8
+1.1
-1.0
+-0.1
+0.2
+0.7
+0.5
+0.5
+0.6
+0.1
+04
+0,2
+1.4
TTAC
40.9
50.4
72.9
$1.6
44.6
60
71.5
71.1
82.8
$4.1
57.7
48.6
68.2
52.7
51.9
59.0
10.6
1188
=0,8
10.7
=1.3
10.77
20.5
10.4
20.6
10.4
20.6
=0.4
11.0
CoTTA
36.6
46.7
73.4
46.9
38,9
57.6
73.7
78.5
76.9
49.3
52.8
48.9
72.8
48.4
49.6
56.7
104
10.9
=0.6
1133
=18
211
20.6
20.7
10.6
=044
10.5
204
=0.4
10.6
10.9
SAR
36.2
46.3
74.0
47.2
37.2
54.0
68.8
76.6
74.4
51.6
65.9
45,3
65.7
48.8
49.1
56.0
+0.2
+1.4
-133
+1.5
-0.9
+1.
+0.8
+0.6
+0.5
+0.3
+066
+0.5
+0.5
+0.6
+0.8
+14
Ada-RcAlign
37,5
41.3
70.7
46.4
41.0
53.
65.1
74.7
69.8
50.0
55.3
45.1
64.8
50.2
49.1
54.7
404
+1.
-13
+11
=1.6
+0,9
+0.5
+0.9
+0.
+0.5
+0.
+0.4
40.6
404
+0.7
-1.2
Table 6: The Average Classification Error (%) for CIFARRO-AO-CIFARIICC Dataset under Sequential Shift. All results were evaluated using the largest corruption severity level 5 and averaged over 5 runs with different initial models. We set different number of data N, at each round with duration M
10.
Method
Ada-ReAlign (N-1)
Ade-Rel (N--5)
Ado-Re (N--10)
Ada- ReAlRee (N-220)
Ada MoA-RoAlign (N--00)
Classification Eroor
24.6 + 27
+1.1
20.3 +
19.5
2.
Table 7: Performance Comparisons CIFARIO- C---O-CIFAIIICCCCC continual test-time adaptation under different distribution shifts. All results were evaluated using the largest comuptiin severity level 5. 5 test runs were conducted with different initial models and the average classification error (%) as well as standard deviation are presented, with the best one emphasized in bold.
Method
Gauss
shot
impul.
defoc.
glass
motio.
zoom
snow
frust
log
brigh.
conir.
clast.
pixel.
Jpeg
N= SAR
22.7
22.8
23.5
9.54
24.7
10.8
6.33
12.6
11.9
11.6
5.60
7,80
14.3
12.9
15.6
14,1
108
10.4
-0.3
-099
10.6
10.4
10.4
20.6
10.5
10.6
10.3
10.4
10.77
M=
Ours
21.6
21.0
22.7
9.69
24.5
9.66
6.47
11.7
11.9
10.4
5.71
6.92
13.5
13.4
13.7
12.7
5
=0.4
+0.6
-0.3
+0.8
-0.5
+0.7
+0.5
+0.3
+0.33
+0.5
=0.5
+0.5
+0.44
+0.6
=0.4
+006
N=
SAR
21.6
20.2
22.6
8.79
24.8
9.88
6.84
10.9
11.6
10,8
5.79
7.73
13.5
12.3
14.6
13.1
5
-0.3
-0.4
10.6
10.7
10.4
10.6
20.4
10.3
10.5
10.4
10.3
M=
Ours
21.0
20.5
21.8
8.56
24.1
9.33
5.98
11.4
11.5
9.80
5.37
7.04
12.9
12.8
13.4
12.5
10
-0.6
+0.6
=0.4
+40.9
-0.5
+-0.7
+0.3
+0.6
+0.3
+0.4
-0.5
+0.33
+0055
+0.4
=0.4
+00.8
X=
SAR
21.4
19.5
22.3
8.35
24.3
9.61
6.53
11.4
11,9
9.70
4.63
6.98
13.9
11.5
13.8
12.8
10
=04
+0.4
=0.4
+00.9
-0.6
+0.77
+0066
+0.3
+0.6
+0.4
=0.2
+0.5
+0.2
+0.3
=0.6
+-0.3
M
Ours
20.9
19.7
21.8
8.81
23.9
8.56
5.69
10.6
11.5
9.42
4.37
6.51
12.34
12.4
12.9
11.8
5
=0.5
+0.6
=0.5
1..4
-0.9
+0066
#0077
+0.7
+0.5
+0.2
=0.2
+0.5
+0.4
+0.5
=0.4
1006
N=
SAR
20.6
19.3
21.9
8.00
24.1
9.13
5.96
10.4
10.7
9.21
4.12
6.92
13.2
11.3
13.4
12.6
10
=0.5
+0.3
=044
+1.
-0.7
+0.6
#0.6
+0.5
+0.4
+0.3
-0.3
+0.4
+0.2
+0.3
=0.3
+0.5
M
Ours
20.6
19.8
21.1
8.19
23.4
8.72
5,30
10.4
11.1
9.04
4.51
6.29
12.6
12.8
12.7
11.8
10
10.6
10.5
0.5
11.2
.966
10.8
10.5
10.4
10.3
10.1
10.3
10.5
10.1
10.2
10.4
10.7
rapid distribution shifts, while a larger number indicates slower shifts, with a prolonged period during which data are generated from a consistent distribution.
Table 6 presents the performance of our Ada- Reaggn algorithm with varying numbers of data per round. Notably, even with limited data per round, the algorithm maintains relatively strong performance.
We further evaluate the algorithm's 's performance across different values of M and N, where M represents the length of time during which the data distribution remains constant, and N is the number of data points available at each time step. Throughout the experiments, we maintain batch size of 32. When N < 32, the batch size is adjusted to N. A smaller M indicates more frequent distribution shifts within the unlabeled data stream.
From Tables 7 and 8, we observe that the Ada deAgRe algorithm consistently outperforms its closest competitor, the SAR algorithm, across various values of M and N, especially in scenarios involving sequential shifts. Both SAR and Ada-ReAlign experience performance degradation as distribution shifts become more frequent and fewer data points are available per time step. However, Ada-Re exhibits more modest degradation compared to SAR, demonstrating greater robustness in the face of rapid distribution shifts and limited data availability at each step.
16

---

Table 8: Performance Comparisons CIFAR CEF-O-CIFARROG continual test-time adaptation under different distrihution shifts, All results evaluated using the largest corruption severity level 5. 5 test runs were conducted with different initial models and the average classification error (%) as well as standard deviation are presented. with the best one emphasized in bold.
Method
Gauss.
shot
impul.
defoc.
glass
matio.
frost
Fog
brigh.
elast.
pixel.
ipeg
Mean
N= SAR
35.5
31.2
37.2
22.4
35.1
22.3
20.5
27.3
25.7
24.7
18.9
24.5
33.9
25.2
32.4
28.5
11.3
11.
10.8
11.5
11.2
11.2
10.8
11.1
10.9
10.8
10.4
10.5
10.3
10.9
10.4
12.4
M=
Ours
30.8
27.3
36.5
16.8
32.6
17.9
17.9
27.5
23.5
21.7
14.6
22,8
31.5
23.5
31.4
24.8
5
+1.7
=1.9
+1.5
=188
=14
#1.6
=0.6
=0.9
#0.8
=0.8
=0.4
=0.6
=0.6
#1.3
=0.4
=2.2
N=
SAR
35.4
30.7
37.0
21.9
34,4
21.5
19.9
27.2
25.3
23.8
18.5
23.7
33.2
24.6
31.7
27.9
5
+0.9
=0.8
+1.2
=1,4
=1.2
40.8
#0.6
#0.6
#0.8
=111
#0.6
=0.7
=0.5
#1.2
#0.6
+1.7
M=
Ours
28.0
25.2
34,6
15.0
30.4
16.7
15.3
25.2
22.1
19.9
13.5
20.4
28.8
20.4
28.6
22.5
10
+1.2
=1.
+0.8
=1.7x
=L1
+0,5
=0.5
=0.6
=0.8
=0.7
#0.6
=0.5
=0,4
=0.8
1:033
=1.8
N=
SAR
32.3
28.6
35.1
20.6
33.5
20.2
19.3
26.9
24.8
23.1
17.8
22.9
32.6
23.8
31.3
27.1
10
+1.5
=0.7
+0.5
=1.5
=1.2
+0.6
=0.4
#0.6
#0.7
+0.9
#0.7
=0.6
=0.8
+1.0
+006
+1.7
Ours
27.8
32.5
29.8
15.7
13.5
24.0
21.1
19.5
13.1
19.8
28.2
27.8
22.8
5
11.6
L11
10.4
+1.3
+1.8
10.7
+0.4
+0.7
10.6
0.88
+0.4
10.5
10.5
10.9
10.8
+220
N=
SAR
34.6
32.9
19.7
18.6
23.4
17.3
22.2
31.5
30.9
24.9
10
+1,1
=0.8
+0.7
=1.7
=1.0
+0.9
=0.5
#0.6
#0.9
#0.6
#0.4
=0.5
=0.4
#0.8
+0.3
+1.5
M
Ours
32.0
29.1
15.2
13.1
23,6
20.3
18.8
12.2
19.2
27.7
27.1
21.1
10
11.4
0.9
10.6
1.5
133
10.8
0.3
+0.7
+0.8
0.6
1..2
10.6
00.3
+0.9
10.2
+1,9
B Related Work
In this section, we introduce the relevant literature on test-time adaptation and learning algorithms designed for non-stationary environments.
TTA in Stationary Environment. TTA considers the problem in which the source labeled data are no longer accessible during the adaptation phase. In this task, the learner relies solely on the source model and seeks to adapt it to a fixed test dataset with distinct distribution. TTA methods can be broadly categorized into two groups based on whether they require a specific training process.
Test-Time Training [30] is the first group, involves optimizing the initial model with a combination of supervised and self-supervised losses, followed by self-supervised learning during test time to update the model. Common self-supervised losses include rotation prediction [30], contrastive self-supervised learning [23]. and others.
The second group of methods does not require a specific training process and can be directly applied to any neural network. These methods include adapting batch normalization statistics [26, 15, 22], entropy minimization [32, 25, 39), pseudo-labeling [34, 5], and more.
However, these approaches are designed for adaptation to fixed distribution and are not well suited for non-stationary environments, where the data distribution evolves over time.
Continual TTA in Non-stationary Environments. In recent years, TTA in non-stationary envi- ronments has gained significant attention. As streaming data evolve over time, the underlying data distribution naturally shifts. A straightforward approach involves resetting the model's parameters those of the initial model after each mini-batch adaptation, as seen in methods like MEMO [39], episodic TENT [32], and DDA [10]. However, these one-step adaptation methods often fall short due high variance from the limited data available per round and their inability to leverage accumulated historical data for improved performance.
To address these challenges, CoTTA [34] was introduced, employing robust pseudo-labels generated through a weighted average of historical models. CoTTA also preserves the initial model's parameters by stochastically replacing the model's parameters with those of the initial model each round. Similarly. SAR [25] estimates reliable entropy and resets the model to its initial state when the entropy exceeds predefined threshold. AdaNPC [40] tackles non-stationary shifts by constructing memory to store historical distributions. Additionally, continual test-time adaptation techniques have been extended to large language models [9].
While these approaches have demonstrated empirical success various real-world tasks, the challenge of effective representation alignment in -ta-staiionay environments remains underexplored.
Adapting to Non-stationary Environments with Offline Labeled Data. Online convex optimiza- tion [11] provides powerful paradigm to handle sequential prediction problems. Over the decades, variety of online learning algorithms have been proposed handle the changing environments by op- timizing the dynamic regret measure [46, 4, 43, 35] under different kinds of feedback information and
17

---

non-stationarity measures of environments. When data is weakly labeled, handling non stationaaon becomes extremely challenging as it is hard to estimate the loss at each round.
This line of research then consider certain kinds of distribution shift and adaptive learning with weighted source labeled data test unlabeled data with pseudo labels to adapt continuous distribution change. Previous work tackled the challenge of non-stationarity in the context of online label shift, where only the class prior is changing. In such scenarios, an unbiased loss estimator is constructed to estimate the loss at each round, enabling the use of dynamic regret minimization to handle non-stationary environments [2]. Another work investigated the problem of continuous covariate shift where only the input distribution changes [41]. They reframed this problem as an online density ratio estimation task and proposed a generic reduction of the density ratio estimation problem to dynamic regret optimization. However, these methods may not always be feasible to access offline labeled data for online adaptation.
In contrast to label shift or covariate shift, gradual domain adaptation consider the gradual shift of underlying distribution. An early work in this area is continuous manifold adaptation [14], which considers adaptation to evolving domains. More recently, self-training has shown promising results by pseudo labeling the unlabeled data stream and adaptively re-train the model based on the pseudo labeled data [19]. Theoretical analysis demonstrated that when the optimal classifier only undergoes slight shifts between consecutive batches, self self-training can provide a well-generalized classifier throughout the entire data stream [36, 33]. However, these approaches assume that the data stream satisfies this assumption, and may not handle outliers that deviate from it. To handle such outliers, several approaches employ active learning [6, 44] to alleviate their negative impact. Nevertheless, these methods are designed for specific types of data distribution change problems.
C Theoretical Analysis
In this section, we present the theoretical analysis of the guarantees for our proposed algorithm. The analysis is based on the convex optimization framework, assuming both the model and the loss function are convex. While our method does not strictly fit within the convex optimization framework. the analysis offers valuable insights that inform the design of an effective algorithm. Furthermore, the theoretically guided approach demonstrates strong empirical performance [44, 41].
We first introduce the following assumptions for our analysis.
Assumption 1. The gradients of all functions are bounded by G, i.e.
max [[V6( I G, e SEΦ
Assumption 2. The domain & contains the origin 0, and its diameter is bounded by D, i.e.,
max V - ø' 2| < D. 0. E
Assumption 3. The value of each function belongs to (0, 11, i.e.
0 < (.) < 1, 4, E [7].
As long as the loss functions are bounded, they can always be scaled and restricted to [0, 1].
C.1 Proof of Theorem
In this part, we provide the detailed proof for Theorem 1.
the information each round the update the model, this operation implicitily is an optimistic mirror descent where the optimism is the gradient of the empirical loss at that time. We firstly show that these two framework are equal, that can analyze our proposed algorithm with the optimistic mirror descent framework. The optimistic mirror descent works as follows, for t I,....
Proof. As
di = A². M)
T.41 = A -f.(
18

---

where f-(-) is the loss function each time, Therefore, we prove that our method is equal to optimistic the optimistic mirror descent mirror descent by choosing M, V (o.).. In the following, framework to analyze
Now we begin to prove the dynamic regret of the representation learning model. We finstly prove the static regret for the base model. Under the Assumption 1, and 3, according to Lemma 2, we have the following inequality for any comparator in any interval I,
E Σ Lo((r)
Σ Lo(u)] tef
S E
(L(()) di u) Σ 2(LD Te112).
(8)
TET
For the first term in Eqn. (8), according to we have the following inequality
Σ
(Vi())) 6: - u)
EE1
(V
Me - x(+1) + (M, dz -o+1) - (VI(()), uu)
IE1
G
D
2
2T
where the second inequality holds due to Theorem 1 in [43].
For the second term in Eqn. (8), considering update rule de II(:: mM), where Mr (o. according to the Lemma 1, we have
|| 5e112 S Mell S SG..
Therefore, we have
3Gn
D 2n
L((d))
L.) s E|
1|+
(9)
2
SET
sEl
By choosing O( (V),), we have
Σ
Le(dr)
Σ
L( & sO(V)T).
EET
TET
Secondly, the AdaNormalHedge the meta learner, according to Lemma 3, obtain the following strongly adaptive regret
E
(.())) Σ (L(o))ssON
RET
1ET
Now we use the guarantee of adaptive regret obtain the dynamic regret. Let Vr Et= sups
sups (r(() - ( is the functional variation, we have
T
T
E
Le( Σ (e()i)
M
M ΣΣ 192 TEE.
SE
L.(3))
Σ 12 tET.
L.
Li(07
En(0)) t=1
(10)
m= LET
where in the first inequality we introduce split of the whole time horizon, which can be arbitrary and we only use in the analysis. In the second inequality, the fisrt term the adaptive regret used in Lemma 3. For the second term can, we can follow the reasoning in [4] and subsequently simplified analysis in [43, Theorem to show that
M
Σ Σ L((7) - Σ L(())) Σ
Σ
- L.(o)))
m= TET...
m= TET...
19

---

M
(Le(0)m)) - Le(oi))
m= FEZm
Σ (Le(sem) Lim (0'mm) (0' - [x((t))
M
Σ
(Le(dsm) Lsm (1'm) ) + Liam (07) (1a - Le(
== tETm
M
T
sup - L4-10-
M
m= tEIm
T
Σ sup [L(() I2-1(0)
M
T
2B
V.R
(11)
M
T
where 5m = (m 1)T/M + 1 is the first time step at interval Im. In the above, the first inequality due to the optimality of o4 over the interval In The second inequality holds since 6 E arg ming R (0).
Combining Eqn. (10) and Eqn. (11), we can obtain
E
Σ
(e(
Σ
Le()t)
T=1
t=1
T
T
E
Vr
M
M
OTT2/SV///)
The third inequality is due to the AM-GM inequality. Now we complete the proof.
C.2 Technical Lemmas
This section provides several useful technical lemmas used in the proof. The first three lemmas the concentration on each time-stamp while the final one is a general inequality.
Lemma 1 (Stability lemma [7, Proposition 7]). Consider the following two updates: (i) X. arg mill (a, x) + (x, c), and (ii) x, arg minxex (a', x) + Bx c). When the regularizer : + R I-strongly convex convex function with respect to the norm ||, we have ||x, x,,1 S (c) a) (V+((c) a')l|= = ||a a'||..
Lemma (Lemma 2 in [44]). Under the Assumption 1, 2 and 3, we have the following inequality for u, t 1...T.
(L..(0.) L.(07) S E((V(())) o: - u.)) + BB(LD G) -
Lemma (Theorem 3 in [38D. Under the Assumption 2 and 3, running AdaNormallledgg as the meta learner, we have the following inequality for any interval that
L.(()) - Em(0r)
< SO(VID).
AEI
SE1
Impact Statements
This research investigates a general machine learning problem of test-time adaptation, where we consider the continuous distribution shift in the unlabeled data stream. The consequences system failure and bias in the data are not applicable.
20

---

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:
We summarize the main contributions in the abstract and introduction.
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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation 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: We analyze the number of base learner required for the proposed algorithm and its effects in computational efficiency in Remark in Section 3.3.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section 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 is low images are taken in low lighting. Or speech-to-text system might not 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 to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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]
21

---

We provide the full set of assumptions and results in Section 3,4 and in Appendix C.
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 or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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 properly referenced.
4. Experimental Result Reproducibility
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 of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
All the details of the experiments can be found in A.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, 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 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) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be 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 deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to 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?
22

---

Answer: [Yes]
Justification: All the details of the data can be found in A.I. Codes can be found in Supplementary Material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. ec/
oolloolioo icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/
wswsssolicccyiii for more details.
The authors should provide instructions 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the details of the experiments implementation can be found in A.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
All the error bars are reported in the experiments.
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).
23

---

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:
All the details of the experiments compute resources can be found A.1.
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
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:/
htte//ublcc/Etticceeesese ines?
Answer: [Yes]
Justification:
We have reviewed the NeurlPS Code of Ethics.
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 discuss the broader impacts in the end of the Appendix.
Guidelines:
The answer NA means that there is 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.

---

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:
This paper poses such risks.
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
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?
Question:
Answer: [NA]
Justification: This paper does not existing 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.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's '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: This paper does not release 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:
This paper does not involve crowdsourcing nor research with human subjects.
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: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not 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.
26


Reviews:
[{"review_id": "NGwzB8DVhB", "reviewer": "Reviewer_73Jf", "summary": "The paper investigates test-time adaptation in a non-stationary environment where unlabeled data batches arrive sequentially with changing data distributions. The authors propose non-stationary representation learning to project the changing distribution back to the original source data distribution and update the classifier with entropy minimization based on the projected representation. Theoretical analysis shows that the proposed method has solid dynamic regret guarantees. Experiments show that the method of representation adaptation is effective in mitigating the distribution shift.", "questions": "1. How does Theorem 1 apply to deep models, considering that the theory was originally formulated for linear models?\n\n2. In the sequential shift, the cyclicality period is fixed by $M$. How does the performance change when the cyclicality period varies?\n\n3. How stable is the performance of the proposed method on the iWildCam dataset with different hyperparameters? are there any ablation studies?", "limitations": "Yes", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The continuous test-time adaptation problem studied in the paper is a popular and crucial area of research for real-world applications of domain adaptation.\n\n2. The proposed non-stationary representation learning is novel and offers non-trivial technical contributions. The authors adapt techniques from online ensemble learning to test-time adaptation, addressing the challenges posed by unknown distribution changes and the problems of high bias and high variance due to the limited amount of unlabeled data available in each round in the data streams.\n\n3. The effectiveness of the method is validated through experiments on both benchmark datasets and a real-world application. In addition, its computational efficiency is well discussed.", "weaknesses": "1. The paper lacks a sufficient review of related work, particularly in the online learning literature. For instance, the method uses dynamic regret as a performance measure and uses techniques from online ensembles. However, readers unfamiliar with this area or these techniques may find it difficult to understand the underlying motivation. \n\n2. The theoretical guarantees focus primarily on convex models and losses, making it hard to adapt them to deep learning models.\n\n3. In the sequential shift, the cyclicality period is fixed by $M$. The performance under conditions of sudden changes or non-cyclic changes is not well studied. Ablation studies are mainly conducted on benchmark datasets, leaving the performance in real-world applications unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and thoughtful feedback. We will revise the manuscript accordingly. Specific questions are answered below.\n\n---\n\n**Q1:** How does Theorem 1 apply to deep models, considering that the theory was originally formulated for linear models?\n\n**A1:** Theorem 1 shows that AdaReAlign minimizes dynamic regret under convexity assumptions, allowing the learned model sequence to approximate the optimal one. This allows AdaReAlign to effectively adapt to unknown and continuously changing distributions. While these theoretical results depend on convexity assumptions, it may be possible to extend them to deep models by exploiting results on neural tangent kernels. However, this extension is beyond the primary scope of our paper. In addition, many studies show that the analysis for convex models can guide the algorithm design, and the convexity assumption does not limit the practical performance of the algorithm with non-convex models [1,2,3].\n\n---\n\n**Q2:** In the sequential shift, the cyclicality period is fixed by $M$. How does the performance change when the cyclicality period varies?\n\n**A2:** Thank you for your suggestions. We have added additional experiments in which the cyclicality period is sampled randomly from a fixed mean, and tested the proposed algorithm against other contenders. The experimental results are reported in Table 1 in the supplementary PDF. The results demonstrate that the proposed method is robust and also achieves better performance in this setting. \n\nWe will revise the draft accordingly to include the above results in the paper.\n\n---\n\n**Q3:** How stable is the performance of the proposed method on the iWildCam dataset with different hyper-parameters? are there any ablation studies?\n\n**A3:** Thank you for your suggestions. We evaluated the hyper-parameters on the iWildCam dataset to test the performance of our proposed algorithm. The results are reported in Table 2 in the supplementary PDF. The findings demonstrate that the proposed method is rather stable.\n\nWe will revise the draft accordingly to include the above results in the paper.\n\n---\n\n**Reference**\n\n[1] Kingma, Diederik P., and Jimmy Ba. Adam: A method for stochastic optimization. In: ICLR, 2015\n\n[2] Sun, Y, et al. Test-time training with self-supervision for generalization under distribution shifts. In: ICML, 2021\n\n[3] Bai, Y, et al. Adapting to online label shift with provable guarantees. In: NeurIPS, 2022", "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": "89nc7Y1ipn", "reviewer": "Reviewer_azfj", "summary": "This paper proposes a novel algorithm called Ada-ReAlign for sequentially adapting a model to non-stationary environments. The proposed algorithm uses a set of base learners, each equipped with different learning window sizes, with a meta learner that combines their outputs. This online ensemble allows an adaptive projection of the unlabeled data, which exhibits changing distributions, onto the source distribution. Subsequently, entropy minimization is applied to the unlabeled data, facilitating the refinement of representations according to the updated distributions. This paper provides theoretical analysis and empirical experiments to justify and validate the effectiveness of the proposed approach.", "questions": "Should the number of base learners used depend on the downstream problem? How is the number of base models determined and the size of the sliding window chosen? Large windows adapt to gradual changes over time, while small windows adapt to drastic changes. It seems that the window size does not depend on the specific problem.\n\nThe meta-learner seems rather complicated. Why this particular design?\n\nIn the proposed algorithm, the number of base learners seems to be fixed. What is the performance when the number of experts is limited to a fixed number, less than the required number?", "limitations": "Please see Weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ This paper is well organized and easy to follow, all the problem formulation and details of the proposed algorithm are well discussed, the experimental setup is clear to me and the result is convincing.\n\n+ The transformation of continuous test-time adaptation to dynamic regret minimization for representation alignment is novel to me. Based on this transformation, the proposed approach is versatile and capable of handling non-stationary environments without explicitly defining or identifying distribution shift boundaries. \n\n+ The proposed approach is theoretically sound. The dynamic exploration of different sliding window sizes of the data stream is novel and intriguing to me. The algorithm is sound with nice theoretical guarantees.\n\n+ Empirical results show superiority over competing algorithms on two simulated benchmark datasets and a wildlife species classification task of the iWildCam dataset. Many ablation studies are performed and the results seem convincing.", "weaknesses": "- The proposed algorithm requires the sketch of the source domain feature embeddings during the adaptation, which may limit the use of the proposed algorithm in practice.\n\n- Although the proposed approach uses only a small number of base learners, $n$ base learners means $n$ times slower than a traditional base learner algorithm, which increases the computational burden.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and thoughtful feedback. We will revise the manuscript accordingly. Specific questions are answered below.\n\n---\n\n**Q1:** Should the number of base learners used depend on the downstream problem? How is the number of base models determined and the size of the sliding window chosen? Large windows adapt to gradual changes over time, while small windows adapt to drastic changes. It seems that the window size does not depend on the specific problem.\n\n**A1:** Indeed, the number of base learners and the size of the sliding window depend on the properties of the downstream problem, such as the type and interval of the distribution shifts. If we have prior knowledge of these properties, we can adjust the number of base learners and the window size accordingly. For instance, if the distribution shift is piece-wise, we can use a single base learner and restart it whenever the shift occurs.\n\nUnfortunately, in real-world applications, the property of the downstream problem is usually **unknown and constantly changing**. Since the prior knowledge is unknown, we propose to use a set of base learners and a meta learner to allow the learning system to automatically adapt to unknown changes. We consider nearly all possible kinds of shifts and design the number of base learners and the corresponding window size based solely on the length of the entire time horizon. The proposed method can **automatically** adapt to the downstream problem without prior knowledge, since the meta learners can dynamically identify the most appropriate base learner.\n\nThis design is based on the dense geometric covering method [1] from the online non-stationary learning literature. The dense geometric covering generates a set of intervals with varying lengths that divide the entire sequence of size $T$, and the algorithm will create a base learner for each interval. Since our meta-learner can automatically track the best-performing base learner, it can adapt to different distribution changes by tracking the corresponding base learner. Intuively, when the distribution change slowly and the base learner in a rather long interval performs well, the proposed method will sign higher weights for this base learner. An illustration of dense geometric covering is provided in the PDF. \n\nWe will revise the draft accordingly to add the above discussion in the main paper.\n\n\n---\n\n**Q2:** The meta-learner seems rather complicated. Why this particular design?\n\n**A2:** The meta learner is designed to handle unknown distribution changes and the unknown optimal time-varying competitor. We can use Hedge [2] to simplify the meta learner, but AdaNormalHedge offers better properties both practically and theoretically. We use AdaNormalHedge because it is a parameter-free expert-tracking algorithm. It has two main advantages:\n1. *Parameter-Free Nature*: AdaNormalHedge does not require prior information. Unlike other meta algorithms such as Hedge, which achieve optimal regret only when the learning rate is finely tuned based on the competitor, AdaNormalHedge as a meta algorithm is parameter-free. This means that we do not need prior knowledge of the optimal competitor or the number of experts in advance.\n2. *More Adatpive Bound*: AdaNormalHedge provides a more adaptive bound that allows us to obtain a problem-dependent regret bound. This means that if the problem is relatively simple, with the optimal base learner experiencing small losses over the entire time horizon, the proposed algorithm can achieve a tighter regret bound.\n\n\n---\n\n**Q3:** In the proposed algorithm, the number of base learners seems to be fixed. What is the performance when the number of experts is limited to a fixed number, less than the required number?\n\n**A3:** In this case, we can eliminate some frequently restarted base learners with restart intervals of $1$ or $2$. These base learners are designed to ensure a dynamic regret bound in worst-case scenarios. In real-world tasks, however, we can drop these frequently restarted base learners because the distribution usually does not change so adversely.\n\n---\n\n**Reference**\n\n[1] Zhang, Lijun, Shiyin Lu, and Tianbao Yang. Minimizing dynamic regret and adaptive regret simultaneously. In AISTATS, 2020.\n\n[2] Yoav Freund and Robert E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 1999.", "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": "CU7gMpqu5i", "reviewer": "Reviewer_rMcB", "summary": "This paper proposes a test-time adaptation (TTA) method focusing on adapting to a non-stationary environment.\nThe proposed method DART aims at minimizing the cumulative loss over time steps, which is equivalent to minimize the distribution gap between the source and current features.\nTo capture unknown changing periods of the environment, DART employs multiple base learners that are reset at different periods.\nDART incorporates the outputs of the base learners with dynamically learned weights to make final predictions.\nExperimental results show that DART can follow continual environmental changes on image corruption datasets.", "questions": "- Q1: How do we determine the number of the base learners when $T$ is unknown?\n- Q2: Can we incorporate the idea of the meta-learner and base learners with other TTA methods?", "limitations": "Discussed in Appendix.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- S1: Addressing continual adaptation of non-stational environments is practical.\n- S2: Providing the theoretical insights is beneficial.\n- S3: It is interesting that minimizing the distribution gap results in minimizing the regret.", "weaknesses": "- W1: Equations should be presented accurately.   \n  - The argument of $\\hat{L}_t$ in Eq. (4) seems to be $\\hat{L}\\_t(\\phi\\_t,\\phi\\_0)$.  \n  - Softmax seems to be missing in the formulation of $\\ell\\_\\text{entro}^t$.  \n  - Ada-ReAlign minimizes the norms of the feature statistics between the source and current distributions, but Fig. 1 says that it minimizes KL divergence.\n- W2: Providing more detailed explanations of theoretical analyses in Sec. 3.4 would be beneficial. For example, where do $\\mathcal{O}(T^{-1/3})$ in L221 and $\\mathcal{O}(T)$ in L227 come from?\n- W3: Ada-ReAlign requires to keep $\\log T$ models, which is more than the baseline methods. Comparing memory consumption would be fair.\n- W4: Can we estimate the distribution gap in Eq. (3) accurately? When the batch size is smaller than the number of feature dimensions, the covariance matrix degenerates, i.e., the covariances cannot be estimated as we can take arbitrary subspaces that include all samples in the batch. Even if numerical stability is improved by adding a small constant to the diagonals of the covariance matrix (L153), this problem still remains unless the batch size is larger than the feature dimensions. It would be beneficial to evaluate the distribution gap with other metrics, e.g., optimal transport or MMD, at each round.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and thoughtful feedback. We will revise the manuscript accordingly. Specific questions are answered below.\n\n---\n\n**Question in W2:** Providing more detailed explanations of theoretical analyses in Sec. 3.4 would be beneficial. For example, where do $\\mathcal{O}(T^{-1/3})$ in L221 and $\\mathcal{O}(T)$ in L227 come from?\n\n**Answer for W2:** Thanks for the valuable suggestions. We will provide a brief explanation below and include a detailed discussion in the revised paper. \n\nAs shown in Theorem 1, the *cumulative regret* over the entire time horizon of length $T$ is of the order $\\mathcal{O}(T^{2/3}V_T^{1/3})$, where $V_T$ is a algorithm-independent variable measuring the degree of the non-stationarity of the environment. Dividing by $T$, the *average regret* is then of the order $\\mathcal{O}(T^{-1/3})$ in L221. \n\nIf we optimize Eqn. (3) directly each round, using only data from that round and not incorporating historical data, we will incur $\\mathcal{O}(T)$ cumulative regret. This is because the algorithm suffers a generalization error independent of $T$ in each round, because it uses empirical data only in that round for optimization, and this error accumulates over the entire time horizon, resulting in a cumulative regret of $\\mathcal{O}(T)$ in L227. Unlike using only the current round of data, our method explores the historical data, providing an opportunity to make the cumulative regret bound scale to the order of $\\mathcal{o}(T)$.\n\n---\n\n**Question in W4:** Can we estimate the distribution gap in Eq. (3) accurately? When the batch size is smaller than the number of feature dimensions, the covariance matrix degenerates... \n\n**Answer for W4:** Thank you for the insightful comments. Besides the metric we used, several effective methods can also be incorporated, such as optimal transport and MMD mentioned. Determining which one is superior remains an open question, particularly in continuous adaptation cases where the data is limited at each timestamp, posing a common challenge for all estimation methods. We will discuss them and propose alternative methods below.\n\nIn this paper, inspired by previous work showing satisfactory performance [1,2], we use a Gaussian distribution to approximate the representation distribution. The covariance matrix may degenerate when the batch size is significantly smaller than the number of feature dimensions. In such cases, we can use a pre-trained feature extractor to compress the original features to a size smaller than the batch size, or use data augmentation techniques [3] to increase the batch size for more accurate discrepancy estimation.\n\nMMD is a good alternative measure, but it may require careful design as it may be less accurate in measuring the distribution gap if the chosen kernel is inappropriate by definition. Since the use of other metrics is also feasible, we leave a detailed study of these for future work.\n\nWe will revise the paper accordingly and include this discussion in the main paper.\n\n---\n\n**Q1:** How do we determine the number of the base learners when $T$ is unknown?\n  \n**A1:** Thank you for pointing this out. The number of base learners can dynamically increase when $T$ is unknown. There are also mechanisms to handle cases where the number of base learners is constrained by resource limitations. Below, we propose alternative methods to enable the handling of an unknown $T$. \n\nWe can use the doubling trick [4] to handle the case when $T$ is unkown. Before running the algorithm, we initially set a value for $T$, e.g., $T=100,000$, then execute the algorithm. When the timestamp reaches $T$, we restart all the base learners and the meta learner, double the value of $T$, i.e., set $T = 2T$, introducing a new base learner, and rerun the algorithm. Theoretically, the bound will suffer an additional logarithmic term, changing from $\\mathcal{O}(T^{2/3}V_T^{1/3})$ to $\\mathcal{O}(T^{2/3}V_T^{1/3}\\log T)$. Since $\\log T$ is a relatively small term, its effect is minor.\n\nWhen $T$ is very large and the number of base learners is fixed by resource limitations, we can eliminate some frequently restarted base learners with restart intervals of $1$ or $2$, which are designed to ensure a dynamic regret bound in worst-case scenarios. In real-world tasks, however, we can drop these frequently restarted base learners since the distribution usually does not change very frequently. \n\nWe will revise the draft accordingly to add the above discussion in the main paper.\n\n---\n\n**Q2:** Can we incorporate the idea of the meta-learner and base learners with other TTA methods?\n\n**A2:** The two-layer structure is a general idea to handle unknown and continous distribution changes and can be incorporated into other TTA methods encountering such continous changes during deployment. For instance, given a black-box TTA algorithm $\\mathcal{A}$ and a measurement $M$, we can initialize a set of base learners using algorithm $\\mathcal{A}$ with varying restart intervals (such as geometric covering), and then run them simultaneously during testing. At each time step, we use $M$ to evaluate each base learner and adjust their corresponding weights accordingly. Intuitively, regardless of whether the distribution changes rapidly or slowly, the base learner that explores an appropriate period of time will achieve better performance. This design could allow the black-box algorithm to automatically adapt to unknown distribution changes.\n\n---\n\n\n**Reference**\n\n[1] Su, Yongyi, Xun Xu, and Kui Jia. Revisiting realistic test-time training: Sequential inference and adaptation by anchored clustering. In: NeurIPS, 2022.\n\n[2] Zellinger, Werner, et al. Central Moment Discrepancy (CMD) for Domain-Invariant Representation Learning. In: ICLR, 2022.\n\n[3] Zhang, Hongyi, et al. Mixup: Beyond Empirical Risk Minimization. In: ICLR, 2018.\n\n[4] Hazan, Elad. Introduction to online convex optimization. Foundations and Trends in Optimization, 2016.", "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:
We are very grateful to all reviewers for your valuable feedback, which has definitely helped in improving our paper. We respond to the questions raised respectively and report all the tables and figures in the supplementary PDF.

Meta-review: This paper proposes a novel algorithm called Ada-ReAlign for sequentially adapting a model to non-stationary environments. The proposed algorithm uses a set of base learners, each equipped with different learning window sizes, with a meta-learner that combines their outputs. The reviewers all believe that the proposed method could be a valuable contribution to the community.  I thus recommend accepting this paper.
Decision: Accept (poster)