Active Test-Time Adaptation: Theoretical Analyses and An Algorithm
Authors: Shurui Gui
Xiner Li
Shuiwang Ji
Venue: ICLR 2024 poster (2024)
Keywords: Domain adaptation
Test-time adaptation
Distribution shift
Catastrophic forgetting
Primary area: transfer learning, meta learning, and lifelong learning
TL;DR: We propose ATTA, an innovative setting, standing as a cost-effective option for efficiency and effectiveness between Test-Time Adaptation and Active Domain Adaptation.

Abstract: Test-time adaptation (TTA) addresses distribution shifts for streaming test data in unsupervised settings. Currently, most TTA methods can only deal with minor shifts and rely heavily on heuristic and empirical studies. 
  To advance TTA under domain shifts, we propose the novel problem setting of active test-time adaptation (ATTA) that integrates active learning within the fully TTA setting.
  We provide a learning theory analysis, demonstrating that incorporating limited labeled test instances enhances overall performances across test domains with a theoretical guarantee. We also present a sample entropy balancing for implementing ATTA while avoiding catastrophic forgetting (CF). We introduce a simple yet effective ATTA algorithm, known as SimATTA, using real-time sample selection techniques. Extensive experimental results confirm consistency with our theoretical analyses and show that the proposed ATTA method yields substantial performance improvements over TTA methods while maintaining efficiency and shares similar effectiveness to the more demanding active domain adaptation (ADA) methods. Our code is available at https://github.com/divelab/ATTA.

Published as a conference paper at ICLR 2024
ACTIVE TEST-TIME ADAPTATION: ANALYSES AND AN ALGORITHM
THEORETICAL
Shurui Gui
Xiner Li"
Shuiwang Ji
Texas A&M University College Station, TX 77843 shurui gui @tamu. edu
Texas A&M University College Station, TX 77843 1xeêt.am.. edu
Texas A&M University College Station, TX 77843 sj1 1 @t.mm.. edu
ABSTRACT
Test-time adaptation (TTA) addresses distribution shifts for streaming test data unsupervised settings. Currently, most TTA methods can only deal with minor shifts and rely heavily on heuristic and empirical studies, To advance TTA under domain shifts, propose the novel problem setting of active test-time adaptation (ATTA) that integrates active learning within the fully TTA setting. We provide learning theory analysis, demonstrating that incorporating limited labeled test instances enhances overall performances across test domains with theoretical guarantee. We also present a sample entropy balancing for implementing ATTA while avoiding catastrophic forgetting (CF). We introduce simple yet effective ATTA algorithm, known as SimATTA, using real-time sample selection techniques. Extensive experimental results confirm consistency with our theoretical analyses and show that the proposed ATTA method yields substantial performance improvements over TTA methods while maintaining efficiency and shares similar effectiveness to the more demanding active domain adaptation (ADA) methods. Our code is available at httpps//jiitubb.coo//vvllaaaaa/
INTRODUCTION
Deep learning has achieved remarkable success across various fields, attaining high accuracy in numerous applications (Krizhevsky et al., Simonyan and Zisserman 2014). Nonetheless, When training and test data follow distinct distributions, models often experience significant performance degradation during test. This phenomenon, known as the distribution shift or out-of-distributinn (OOD) problem, is extensively studied within the context of both domain generalization (DG) (Gulra jani and Lopez-Pazz 2020: Koh et al. 202T Gui et al. 2022) and domain adaptation (DA) (Ganin 2016 Sun and Saenko 2016). While these studies involve intensive training of models with considerable generalization abilities towards target domains, they overlook an important application property; namely, continuous adaptivity real-time streaming data under privacy, resource, and efficiency constraints. This gap leads to the emergence of test-time adaptation (TTA) tasks, targeting on-the-fly adaptation to continuous new domains during the test phase or application deployment. The study of TTA encompasses two main categories; namely test-time training (TTT) methods (Sun)
let al. 2020 Liu et al. 2021c) and fully test-time adaptation (FTTA) (Niu et al.) 2023] Wang et al. 2021 The TTT pipeline incorporates retraining on the source data, whereas FTTA methods adapt arbitrary pre-trained models to the given test mini-batch by conducting entropy minimization, without access to the source data. Nevertheless, most TTA methods can only handle corrupted distribution shifts (Hendrycks and Dictterich, 2019b) (c.g., Gaussian noise,) and rely heavily on human intuition empirical studies. To bridge this gap, our paper focuses tackling significant domain distribution shifts real time with theoretical insights.
We investigate FTTA, which is more general and adaptable than TTT, particularly under data ac- cessibility, privacy, and efficiency constraints. Traditional FTTA aims at adapting a pre-trained model to streaming test-time data from diverse domains under unsupervised settings. However, recent works (Lin et al. 2022; Pearl 2009) prove that it is theoretically infeasible to achieve OOD generalization without extra information such as environment partitions. Since utilizing environment partitions requires heavy pretraining, contradicting the nature of TTA, we are motivated to incorporate extra information in a different way, i.e., integrating limited number of labeled test-time samples to alleviate distribution shifts, following the active learning (AL) paradigm (Settles) (009). To this end, we propose the novel problem setting of active test-time adaptation (ATTA) by incorporating
"Equal contributions

---

Published as a conference paper at ICLR 2024
AL within FTTA. ATTA faces two major challenges; namely, catastrophic forgetting (CF) (emmerr jet al., 2018: Li and Hoiem 2017) and real-time active sample selection. CF problem arises when a model continually trained on a sequence of domains experiences a significant performance drop on previously learned domains, due to the inaccessibility of the source data and previous test data. Real-time active sample selection requires AI. algorithms to select informative samples from a small buffer of streaming test data for annotation, without a complete view of the test distribution.
In this paper, we first formally define the ATTA setting. We then provide its foundational analysis under the learning theory's paradigm to guarantee the mitigation of distribution shifts and avoid CF. Aligned with our empirical validations, while the widely used entropy minimization (Wang ct al. 202T, Grandvalet and Bengio, 2004) can cause CF, can conversely become the key to preventing CF problems with our sample selection and balancing techniques. Building on the analyses, we then introduce simple yet effective ATTA algorithm, SimATTA, incorporating balanced sample selections and incremental clustering. Finally, we conducted a comprehensive experimental study to evaluate the proposed ATTA settings with three different settings in the order of low to high requirement restrictiveness, i.e., TTA, Enhanced TTA, and Active Domain Adaptation (ADA). Intensive experiments indicate that ATTA jointly equips with the efficiency of TTA and the effectiveness of ADA, rendering an uncompromising real-time distribution adaptation direction.
Comparison to related studies. Compared to TTA methods, ATTA requires extra active labels, but the failure of TTA methods (Sec. and the theoretical proof of Lin et al. (2022); Pearl (2009)
justify its necessity and rationality. Compared to active online learning, ATTA focuses on lightweight real-time fine-tuning without round-wise re-trainings as |arran et al. (0023) and emphasizes the importance of CF avoidance instead of resetting models and losing learned distributions. In fact, active online learning is partially similar our enhanced TTA setting (Sec. 5.2 Compared ADA methods (Prabhu et al., [021]] Ning et al.] [202T), ATTA does not presuppose access to source data, model parameters, or pre-collected target samples. Furthermore, without this information, ATTA can still perform on par with ADA methods (Sec. 5.3 The recent source-free active domain adaptation (SFADA) method SALAD (Kothandaraman et af., 2023) still requires access to model parameter gradients, pre- pre-collected target data, and training of additional networks. Our ATTA, in contrast, with non-regrettable active sample selection on streaming data, is much lighter and more realistic approach distinct from ADA and SFADA. More related- work discussions are provided in Appx.
2 THE ACTIVE TEST-TIME ADAPTATION FORMULATION
TTA methods aim to solve distribution shifts by dynamically optimizing pre-trained model based on streaming test data. We introduce the novel problem setting of Active Test-Time Adaptation (ATTA), which incorporates active learning during the test phase. In ATTA, the model continuously selects the most informative instances from the test batch to be labeled by an explicit or implicit oracle (e.g., human annotations, self-supervised signals) and subsequently learned by the model, aiming to improve future adaptations. Considering the labeling costs in real-world applications, a "budget" is established for labeled test instances. The model must effectively manage this budget distribution and ensure that the total number of label requests throughout the test phase does not surpass the budget.
We now present a formal definition of the ATTA problem. Consider a pre-trained model f(z; Φ) with parameters & trained on the source dataset Ds = (xx pg with each data sample x E X and a label y E V. We aim to adapt model parameters 0, initialized as o, to an unlabeled test-time data stream. The streaming test data exhibit distribution shifts from the source data and varies continuously with time, forming multiple domains to which we must continuously adapt. The test phase commences at time step f 1 and the streaming test data formulated in batches. The samples are then actively selected, labeled (by the oracle) and collected as (tc(t) = Alg.Al an active selection/labeting algorithm. The labeled samples Dte(t) are subsequently incorporated into the ATTA training set (L). Finally, we conclude time step by performing ATTA training, updating model parameters ((t) using (1), with ((1) initialized as the previous final state Ø(: 1).
where Act.Alg(-) denotes
Definition (The ATTA problem). Given a model f(x; with parameters 0, initialized with parameters 0(0) & obtained by pre-training on source domain data, and streaming test data batches Use (t) continually changing over time, the ATTA task aims to optimize the model at any time step t (with test phase commencing at = 1) as
o(t)* := argmin(
v)] Eo..eer
(1)
((t)
2

---

Published as a conference paper at ICLR 2024
where (1)
s.t. [D-(1)] S BB
(2)
1tu
8 1,
(te(t) = (t)) is actively selected and labeled, fce is the cross entropy loss, by is an unsupervised learning loss, and B the budget.
THEORETICAL STUDIES
In this section, we conduct an in-depth theoretical analysis of TTA based on learning theories. We mainly explore two questions: How can significant distribution shifts be effectively addressed under the TTA setting? How can we simultaneously combat the issue of CF? Sec. [.] provides a solution with theoretical guarantees to the first question, namely, active TTA (ATTA), along with the conditions under which distribution shifts can be well addressed. Sec. 3.2 answers the second question with underexplored technique, i.., selective entropy minimization, building upon the learning bounds established in Sec. 1.1. We further validate these theoretical findings through experimental analysis. Collectively, present a theoretically supported ATTA solution that effectively tackles both distribution shift and CF.
3.1 ALLEVIATING DISTRIBUTION SHIFTS THROUGH ACTIVE TEST-TIME ADAPTATION
Traditional TTA is performed in unsupervised or self-supervised context. In contrast, ATTA introduces supervision into the adaptation setting. In this subsection, we delve into learning bounds and establish generalization bounds to gauge the efficacy of ATTA in solving distribution shifts. We scrutinize the influence of active learning and evidence that the inclusion of labeled test instances markedly enhances overall performances across incremental test domains.
Following Kifer al. (2004), we examine statistical guarantees for binary classification. A hypothesis is function h X + {0, 11. which can serve the prediction function within this context. In the ATTA setting, the mapping of h varies with time as har, t). We use H HAA--diseeece following Ben David al. (0000), which essentially provides measure quantify the distribution shift between two distributions D, and D2, and can also be applied between datasets. The probability that an estimated hypothesis h disagrees with the true labeling function g X {0,1) 1} according distribution DD is defined as e(h(t), g) = E [f(,,, t) g[x)]], which we also refer to as the error or risk e(h(t)). While the source data inaccessible under ATTA settings, we consider the existence of source dataset Ds for accurate theoretical analysis. Thus, we initialize D.r as (c) = Ds. For every time step t, the test and training data can be expressed U.e (t) and (t, Ds U Dre (2) D.c(t))
Building upon two lemmas (provided in Appx. D). we establish bounds on domain errors under the ATTA setting when minimizing the empirical weighted error using the hypothesis at time
Theorem 1. Let H be hypothesis class of VC-dimension At time step for ATTA data domains Ds, (1), ... (t)...) S; are unlabeled samples of size m sampled from each of the t+1 domains respectively. The total number of samples
Der is N and the ratio of sample numbers in each component is X = (Au, -....... A.). If hi(t) E HH minimizes the empirical weighted error (h((t) with the weight vector w = (wo, ................................ wx) on (t), and ht)() = arg minne u e, (h(()) is the optimal hypothesis on the jth domain, then for any 5 E (0, 1), with probability of at least 8, we have
cj(h(t)) S (,(((())) +2
Σ wi x=
1 (ddAx(S.SS)) +2
2d 2d (2m)
log
+ +
2C,
m
(log(2N) and 7/ (hnhe)((((h(())) + ()(h()))) For future test domains 1 h (k > 0), assuming K' argmin ddan(((())) Use (t+ k)) and min duan (D(K), + k)) I 8p. where S 60 & too, then Vo, with probability of at least 5, we have
where C 1///0 E
(1+((h(()) (hin
Σ We
(nA Sw) + +4V
2d 20g((() + log
8n 2% 2C
The adaptation performance on a test domain is majorly bounded by the composition of (labeled) training data, estimated distribution shift, and ideal joint hypothesis performance, which correspond to C, dHAN (S. and 7h, respectively. The ideal joint hypothesis error 7/ gauges the inherent adaptability between domains. Further theoretical analysis in Appx.
3

---

Published as a conference paper at ICLR 2024
Ug 4
Loss mirimam for each
Loss niminan la woch
40-
Global minimum
233
235
06
430
N7
65
15
04
21
21
05
05
gth
4.0
26
R3
4.0
36
00
10
0.4
1o
(8)
W9
(b)
Figure 1: (a) Empirical validation of Thm. 1 We train a series of models on = 2000 samples
from the PACS (Li et al.] 2017) dataset given different Ås and and display the test domain loss of each model. Red points are the test loss minimums given a fixed Au The orange line is the reference where w/ Au We observe that we with loss minimums are located closed to the orange line but slightly smaller than Ao which validates our findings in Eq. (4). (b) Empirical analysis with an uncertainty balancing. Given source pre-trained models, fine-tune the models on 500 samples with different λg and wo, and display the combined error surface of test and source error. Although a small A is good for test domain error, it can lead to non-trivial source error exacerbation. Therefore, we can observe that the global loss minimum (green X) locates in a relatively high-Ao region.
If we consider the multiple test data distributions as a single test domain, i.e., Ui=1 (t) Thm. can be reduced into bounds for the source domain error eg and test domain error er. Given the optimal test/source hypothesis (1) = arg minke er (T(()) and (t) = arg minge es (t)),, we have
(er()(t)) er (hi S wo +
V
w Ao
+
(1 wo)2
1 Ao
B
(3a)
(1 w
(cs()(()) - cs (k)(())) 5 (1) w))
B,
(3b)
Ao
do
where the distribution divergence term A dHaM (So, Sr) 2d (ollo(mm) 3 +2%, the empirical gap
m
term B == 2 dloox(2N) Sr is sampled from Ul Use (1), and y = minge (oo(t))) + (r()())))- 2N
Our learning bounds demonstrates the trade-off between the small amount of budgeted test-time data and the large amount of less relevant source data. Next, we provide an approximation of the condition necessary to achieve optimal adaptation performance, which is calculable from finite samples and can be readily applied in practical ATTA scenarios. Following Eq. a3). with approximately B ci /d/N the optimal value wy to tighten the test error bound is a function of Ap and A:
N
w = An V otd - A >n)
for da 2a21
(4)
A
where is a constant, Note that do 2 1- n should be the satisfied condition in practical ATTA settings, where the budget is not sufficiently big while the source data amount is relatively large. The following theorem offers a direct theoretical guarantee that ATTA reduces the error bound on test domains comparison to TTA without the integration of active learning.
Let H be a hypothesis class of VC-dimension d For ATTA data domains Ds, (1) Ui.(2). Ut),t), considering the test-time data as a single test domain U Urali), if h(t)) E H minimizes the empirical weighted error &w (h(t)) with the weight vector w on Dzr(t), let the test error be upper-bounded with ler (f(()) ( (t)) S EBr X, N,t). Let w' and X be the weight and sample ratio vectors when no active learning is included, i.e, w' and X s.t. wh = 2 1 and
Theorem 2.
w! = Xx = 0 for 2 1, then for any X + X, there exists w s.I.
(B < EBr(w' N,N.I).
(5)
Therefore, the incorporation of labeled test instances in ATTA theoretically enhances the overall performance across test domains, substantiating the significance of the ATTA setting in addressing distribution shifts. All proofs are provided in Appx. E, Finally, we support the theoretical findings with experimental analysis and show the numerical results of applying the principles on real-world datasets, as shown in Fig. [ For rigorous analysis, note that our theoretical results rest the underlying condition that N should at least be of the same scale as d, according to the principles of VC-dimension theory. The empirical alignment of our experiments with the theoretical framework can be attributed to the assumption that fine-tuning a model is roughly equivalent to learning a model with a relatively small d. Experiment details and other validations can be found in Appx. H
4

---

Published as a conference paper at ICLR 2024
3.2 MITIGATING CATASTROPHIC FORGETTING WITH BALANCED ENTROPY MINIMIZATION
Catastrophic forgetting (CF), within the realm of Teme-Time/ Adaptation (TTA), principally manifests as significant declines in overall performance, most notably in the source domain. Despite the lack of well-developed learning theories for analyzing training with series data, empirical studies have convincingly illustrated the crucial role of data sequential arrangement in model learning, thereby accounting for the phenomenon of CF. Traditionally, the mitigation of CF in adaptation tasks involves intricate utilization of source domain data. However, under FTTA settings, access to the source dataset is unavailable, leaving the problem of CF largely unexplored in the data-centric view.
To overcome this challenge of source dataset ab- sence, we explore the acquisition of "source-like like" data. In TTA scenarios, it is generally assumed that the amount of source data is considerably large. We also maintain this assumption in ATTA, practically assuming the volume of source data greatly surpasses the test-time budget. As a re- sult, we can safely assume that the pre-trained model is well-trained on abundant source do- main data Ds. Given this adequately trained source model, we can treat it as a "true" source data labeling function (=; The model es- sentially describes a distribution, De.s(X.)) =
Table 1: Correlation analysis of high/low en- tropy samples and domains. We use source pre-trained model to select samples with low- est/highest entropy, and I reetrain the model on 2000 samples; 2.fine-tune the model on 300 sam- ples. We report losses on source/test domains for each setting, showing that low-entropy samples form distributions close the source domain.
Retrain
Fine-tune
Sample type
er'
er
Low entropy 0.5641
0,8022
0,0619
1.8888
High entropy
2.5117
0.3414
0.8539
0.7725
((x, 0) (X) | ú f(z Φ), x E Ds}. The entropy of the model prediction is defined as 1 = f(a;; ()) where e denotes the class. Lower entropy indicates
(T)) = = P(De) Plo)looogg that the model assigns high probability
one of the classes, suggesting high level of certainty or confidence in its prediction, which can be interpreted as the sample being well-aligned or fitting closely with the model's 's learned distribution. In other words, the model recognizes the sample as being similar to those it was trained on. Thus entropy can be used as an indicator of how closely a sample x aligns with the model distribution De.s. Since the model distribution is approximately the source distribution, selecting (and labeling) low-entropy samples using f(;; 6) essentially provides an estimate of sampling from the source dataset. Therefore, in place of the inaccessible Ds. we can feasibly include the source-like dataset into the ATTA training data at each time step t:
(1, = [(=, f(e 61) E U1, +)) < et).
(6)
where is the entropy threshold. The assumption that De.s(t) is an approximation of Ds can be empirically validated, as shown by the numerical results on PACS in Tab. D contrast, high-entropy test samples typically deviate more from the source data, from which we select (t) for active labeling. Following the notations in Thm. [ we are practically minimizing the empirical weighted error of hypothesis h(t) as
e.. (h(t)) = Σ (h(t()(t)) = We
Σ
[Mxxt) - f(x; Ø)1
+
Wy
Σ Die()
1b(x,t) -vl (7)
No
A
==0
TE (e
By substituting Ds with (t.s(t) in Thm. [ the bounds of Thm. T continue hold for the test domains. In the corollary below, we bound the source error for practical ATTA at each time step t.
Corollary 3. At time step t, for ATTA data domains (t), (1,, Uia()) (t),)))),,,,,,(()) S. are unla- beled samples of size m sampled from each of the t + domains respectively, and Sg is unlabeled samples of size m sampled from D3. If if((()) E H minimizes eno (N(()) while other conditions remain identical to Thm. 7 then
es (s(()) & cs(hb(0) + Σ wi (dnasu(5.. Ss) + +/
2d (2m) + log 3
273 + +2C,
m
with probability at least 1 - 6, where follows Thm. D Mand = (e. + es (b())))
Further analysis and proofs are in Appx. D and B The following corollary provides direct theoretical support that our strategy conditionally reduces the error bound on the source domain.
Corollary 4. At time step I, for ATTA data domains De,s(t), (..(()))..11) (1), (2)..... ,U,(((),, suppose that id(l) E H minimizes ewo (h(C) under identical conditions to Thm. 2 Let's denote the source error upper bound with (hs()()) ex(h S F. X, N,t). Let w' and X be the weight
5

---

Published as a conference paper at ICLR 2024
Streaming Test
Model
(t)
g
SimATTA
f(:0)
Update
f(:0)
Low Eatropy
Pretrreepeetrrnnndd Moriol f(=0)
Samples
Dd(e)
Labeling
High Einleopy Samples
Incretaental Cassterng
Dx(()
f(;;0)
1st Call
2nd Call
Next Call
Seoples
Clesteing
Anchers
Samptes Anchors
Clustering
Anchers
Figure 2:
Overview of the SimATTA framework.
and sample ratio vectors when st,s(t) is not included, i.e., w' and X s.t. w6 Xo 0. If dnan(Ds,, (o))(()) < duan (Ds.U Ui-n Ui)())) then any X & X, there exists S.t.
EBs(w, (,t,,,,N,,, N,t) < EBs(w', N,t.
(8)
Corollary 4 validates that the selected low-entropy samples mitigate the CF problem under the assumption that these samples are source-like, which is also empirically validated Fig. [ Note that strategy employs entropy minimization in selective manner, aiming to solve CF rather than the main adaptation issue. While many FTTA works use entropy minimization to adapt across domains without guarantees,
is more theoretically-soond.
4 AN ATTA ALGORITHM
Building on our theoretical findings, we introduce simple yet effective ATTA method, known as SimATTA, that innovatively integrates incremental clustering and selective entropy minimization techniques, as illustrated in Fig. 2 We start with an overview of our methodology, including the learning framework and the comprehensive sample selection strategies. We then proceed to discuss the details of the incremental clustering technique designed for real-time sample selections.
4.1 ALGORITIM OVERVIEW
Let (z, v) be labeled sample and f(::0) 6) be our neural network, where = f(z; 8) and @ represents the parameters. We have a model pre-trained on source domains with the pre-trained parameters di We initialize model parameters 0(0) and aim to adapt the model f(=:0) in real-time. During the test phase, the model continuously predicts labels for streaming-in test data and concurrently gets fine-tuned. We perform sample selection to enable active learning. As discussed in Sec. 3.2 we empirically consider informative high- samples for addressing distribution shifts and source-like low-entropy samples mitigate CF. As shown in Alg. [ each time step 1, we first partition unlabeled test samples (t) into high entropy and low entropy datasets, (t) and (t(t), using an entropy threshold. The cource-pretrainee model (:: is frozen predict pseudo labels for low entropy data. We obtain labeled low-entropy data Di(() by labeling (i()) with ((:)) and combining it with Di ( 1). In contrast, the selection high-entropy samples for active labeling is less straightforward. Since the complete test dataset is inaccessible for analyzing the target domain distribution, real-time sample selection is required. We design an incremental clustering sample selection technique to reduce sample redundancy and increase distribution coverage, detailed in Sec. The incremental clustering algorithm outputs the labeled test samples Dr (t), also referred to anchors, given (x 1) and Un (t). After sample selection, the model undergoes test-time training using the labeled test anchors (t) and pseudo-labeles source-like anchors D, (1). Following the analyses in Sec. 3.1 the training weights and sample numbers should satisfy w() X(t) for (t)
and (t) for optimal results. The analyses and results in Sec. 3.2 further indicate that balancing the source and target ratio the key to mitigating CF. However, when source-like samples significantly outnumber test samples, the optimal w (1) for test domains can deviate from X(1) according to Eq. (4).
4.2 INCREMENTAL CLUSTERING
We propose incremental clustering, novel continual clustering technique designed to select informa- tive samples in unsupervised settings under the ATTA framework. The primary goal of this strategy is to store representative samples for distributions seen so far. Intuitively, we apply clusters to cover all seen distributions while adding new clusters to cover newly seen distributions. During this process with new clusters added, old clusters may be merged due to the limit of the cluster budget. Since

---

Published as a conference paper at ICLR 2024
Algorithm SIMATTA: A SIMPLE ATTA ALGORITIIM
Require: A fixed source pre-trained model f(:: 6) and real-time adapting model f(: (()) with 8(0) v. Streaming test data (ta(t) time step Entropy of predictions (ū)
Ee p(Ae) p(..). Low entropy and high entropy thresholds and ea. The number of
cluster centroid budget NC(1) time step t. Centroid increase number k. Learning step size 1/.
1: for t= 1..,...,2 do
2:
Model inference on (te(t) using f(: - 1)).
3:
Di(t) + Di(t 1) U ((x, f(x; Ute(t), H(f(; <e)
4:
(t) < {a|l Ute(t), > ea)
5:
(t) -D((t 1) (), IC(D,(t (C), y Oracle(x))
6:
A(1) <
7:
mxtt) < (etW(A(t))
> Generally, GetW(A(t)) x(t) is a fair choice.
8:
0(1) < 0(t-1)
9:
for (21, v:) in Di and (2%, ya) in Dr. do
0(t) + 8(t) - mpo (f) (t)), u)) - 7(1 - Vo)V ((t)), 11: end for
10:
12: NC + 1) UpdatCCentoicNum(NcCO))
b Naive choice: NC(L + NC(() + k.
13:
end for
clusters cannot be stored efficiently, we store the representative samples of clusters, named anchors, instead. this work, we adopt weighted K-means (Krishna and Murty, (199)) as our base clustering method due to its popularity and suitability for new setting explorations.
When we apply clustering with new samples, a previously selected anchor should not weigh the same as new samples since the anchor is representation of cluster, i.e., a representation of many samples. Instead, the anchor should be considered as barycenter with weight of the sum of its cluster's sample weights. For a newly added cluster, its new anchor has the weight of the whole cluster. For clusters containing multiple old anchors, i.e., old clusters, the increased weights are distributed equally among these anchors. These increased weights are contributed by new samples that are close to these old anchors. Intuitively, this process of clustering is analogous to the process of planet formation. Where there are no planets, new planets (anchors) will be formed by the aggregation of the surrounding material (samples). Where there are planets, the matter is absorbed by the surrounding planets. This example is only for better understanding without specific technical meanings.
Specifically, we provide the detailed Alg. [[or for incremental clustering. In each iteration, we apply weighted K-Means for previously selected anchors Dan: and the new streaming-in unlabeled data Unew We first extract all sample features using the model from the previous step f(; 0(t 1)), and then cluster these weighted features. The initial weights of the new unlabeled samples are 1, while anchors inherit weights from previous iterations. After clustering, clusters including old anchors are old clusters, while clusters only containing new samples are newly formed ones. For each new cluster, we select the centroid- cloosest sample as the new anchor to store. As shown in line 10 of Alg. 2 for both old and new clusters, we distribute the sample weights in this cluster its anchors' weights. With incremental clustering, although we can control the number of clusters in each iteration, we cannot control the number of new clusters/new anchors. This indirect control makes the increase of new anchors adaptive to the change of distributions, but it also leads to indirect budget control. Therefore, in experimental studies, we set the budget limit, but the actual anchor budget will not reach this limit. The overall extra storage requirement is O(B) since the number of saved unlabeled samples is proportional to the number of saved labeled samples (anchors).
5 EXPERIMENTAL STUDIES
In this study, we aim to validate the effectiveness of our proposed method, as well as explore the various facets of the ATTA setting. Specifically, we design experiments around the following research questions: RQI: Can TTA methods address domain distribution shifts? RQ2: ATTA as efficient
as TTA? RQ3: How do the components of SimATTA perform? RQ4: Can ATTA perform par with stronger Active Domain Adaptation (ADA) methods? We compare ATTA with three settings, TTA (Tab. 2 enhanced 7TA (Tab. 3 and 5) and ADA (Tab. 4T.
To assess the OOD performance the TTA methods, we benchmark them using datasets from DomainBed (Gulrajani and Lopez-Paz] 2020) and Henddryck and Dietterich| (2019a). We employ PACS (Li et al. 2017). VLCS (Fang et al. 2013), Office-Home (Venkateswara et al.) 2017). and Tiny-ImaaeNNetCC datasets for our evaluations. For each dataset, designate one domain as
Datasets.
7

---

Published as a conference paper at ICLR 2024
Table 2: TTA comparisons on PACS and VLCS. This table includes the two data stream mentioned in the dataset setup and reports performances in accuracy. Results that outperform all TTA baselines are highlighted in bold font. N/A denotes the adaptations are not applied on the source domain.
PACS
Pommin-wise data stresm
Postsndiptation
Random data stream
Postsadiptarion
-+A--
-C-
-
P
5
-+4
P
59.38
28,03
42.91
19.701
28.03
42,91
43.44 44.44
23.44
43.44
04.44
99:70
28.03
42.91
adapt
65.07
64.85
54.57
74
54.57
03.50
74
54.57
(sope=
67.39
64.90
44.67
60
66.85
42.55
$6.35
$4.00
51.83
48.58
63.53
60.75
41.5
Tent (xcps=110
67.38
57.85
20.23
62.63
34.52
80.57
13.59
47.36
31.01
20.33
50.78
23.68
19.62
FATA
67.04
64.72
50.27
66-50
62,46
48.1
57.31
56.06
58.1
59.78
98.62
69.63
65.70
54.26
CoTTA
N/A
63.48
62.12
53.17
98.5 62
65. 48
63.10
53.78
06
54.33
57.16
57.42
96.62
65.97
62.97
54.62
SAR (stepsel)
N/A
06.75
63.82
49.58
98.32
56.94
62.99
45.74
56.78
50.35
56.08
36.70
98.44
68.16
64.28
52.53
SAR (amp--10)
N/A
09:38
68.33
49.02
96.47
62. 16
56.19
54.67
53.51
51.15
51.78
45,60
94.13
56.64
56.02
36.37
SimATTA (8 5 2000
N/A
76.86
70.90
75.39
98.80
84.47
82.25
81.52
69.47
76.49
K2.45
82.22
90.98
84.91
83.92
86.00
SimATTA (8 200)
NAA
77.93
76.02
76.30
98.62
88.33
83.49
83.74
08.46
78.22
80.91
83.49
99.16
$6.67
84.77
87.71
VLCS
Domain wibe data stream
Post-aduptation
Rundom data stream
Post-adaptaion
.L
:S >
L
12
(3
>
L
BN wlep
100.00
53.55
41. 10.10
49.05
100.00
53.55
41.10
40.0
41:23
41.23
41.23
41.25
100.00
53.55
41.10
49.05
BN w/ adapt
85.16
37.31
33:27
52.16
55.16
37.31
33:27
52.16
.0.91
50.91
-0.91
.00.91
55.16
37.31
33:27
$2.16
Tent 1s
N/A
38.55
34,40
53.88
$4.73
43.86
33.61
53.11
44.85
64.29
47.3
44.98
$5.30
43.49
37.81
53.35
Tent (0)pe-10)
N6A
45.41
31.44
32.32
42.54
37.65
27.79
38.12
46.13
42.31
43.51
39.48
$2.01
40.32
33.64
40.37
EATA
N/A
37.24
33.15
52.58
84.10
37.69
32.39
52.49
43.77
42.48
43.34
41.55
83.32
36.67
31.47
52.55
CoTTA
37.39
32.54
$2.25
82.12
37.65
$2,90
42.14
43.21
42.32
51.98
37.99
53.25
SAR (olep--))
16.18
34.43
53.46
53.90
90.72
52.37
44
41.93
09
40.70
53.02
SAR (steps=10)
35.32
34.10
51.66
41.49
53.08
42.53
41.15
$5.09
37.58
33.12
52.01
SimATTA (8 300)
N/A
62.61
65.08
74.38
99.93
69.50
66.67
77.34
62.33
73,20
71.93
99.93
69.43
72,46
M0.39
SimATTA (8 2 500)
N/A
63,52
68.01
76.13
99.51
70.56
73.10
78.35
62.29
70.45
73.50
72,02
99.43
70.29
72.55
80.18
the source domain and arrange the samples from the other domains form the test data stream. For DomainBed datasets, we adopt two stream order strategies. The first order uses a domain-wise data stream, i.e., we finish streaming samples from one domain before starting streaming another domain. The second order is random, where we shuffle samples from all target domains and partition them into four splits 1, 2, 3, and 4, as shown in Tab. 2 More dataset details are provided in Appx. G.I
Baselines. For baseline models, we start with the common source-only models, which either utilize pre-calculated batch statistics (BN w/o adapt) or test batch statistics (BN w/ adapt). For comparison with other TTA methods, we consider four state-of-the-an art TTA methods: Tent (Wang et al. (021). EATA (Niu et al. 2022). COTTA (Wang et al. 2022a), and SAR (Niu et al. 2023). The three of them except Tent provide extra design to avoid CF. To compare with ADA methods, we select algorithms that are partially comparable with our method, i.e., they should be efficient (e.g., uncertainty- based) without the requirements of additional networks. Therefore, we adopt random, entropy (Wang and Shang 2014), k-means (Krishna and Murty 1999). , and CLUE (Prabhu et al. 202I) for comparisons.
Settings. For TTA, we compare with general TTA baselines in streaming adaptation using the two aforementioned data streaming orders, domain-wise and random. We choose P in PACS and C in VLCS as source domains. For domain-wiss data stream, we use order A + C + S for PACS and L + V for VLCS. We report the real-time adaptation accuracy results for each split of the data stream, as well as the accuracy on each domain after all adaptations through the data stream (under "post-adaptation" columns). Enhanced TTA is built on TTA with access to extra random sample labels. TTA basclines are further fine-tuned with these random samples. To further improve enhanced TTA, we use long-term label storage and larger unlabeled sample pools. To its extreme where the model can access the whole test set samples, the setting becomes similar to ADA, thus we also use ADA methods for comparisons. ADA baselines have access to all samples in the pre-collected target datasets but not source domain data, whereas our method can only access the streaming test data.
5.1 THE FAILURE OF TEST-TIME ADAPTATION
The failure of TTA methods on domain distribution shifts is one of the main motivations of the ATTA setting. As shown in Tab. [ TTA methods cannot consistently outperform even the simplest baseline "BN w/ adapr" which uses test time batch statisties to make predictions, evideneing that current TTA methods cannot solve domain distribution shifts (RQI). Additionally, Tent (step=10) exhibits significant CF issues, where "step=10" indicates 10 test-time training updates, i.e., 10 gradient backpropagation iterations. This failure of TTA methods necessitates the position of ATTA, In contrast, SimATTA, with a budget B less than 300, outperforms all TTA methods on both source and target domains by substantial margins. Moreover, compared to the source-only baselines, our method improves the target domain performances significantly with negligible source performance loss. showing that ATTA is more practically effective setting for real-world distribution shifts.
5.2 EFFICIENCY & ENHANCED TTA SETTING COMPARISONS
To validate the efficiency of ATTA and broaden the dataset choice, we conduct this study on Tiny- ImageNet-C which, though does not focus on domain shifts, is much larger than PACS and VLCS. we
8

---

Published as a conference paper at ICLR 2024
Table 3: Comparisons with Enhanced TTA Imny-ImageNet-C (severity level 5).
Thny ImageNet
Time (982)
Nense
Bher
Weather
Diginl
Claso.
Shat
Ingul.
Defoc.
Glaas
Moiics
Zoom
Snow
Frost
Fog
Cout.
Elastic
Pisel
IPEG
Avg.
Test (acpe1)
68.83
9.32
11.97
5.85
10.45
7.50
12:20
14:34
15.58
15,46
13.55
3.99
13.31
17:79
18.51
12:17
Test (00gm10l)
436-90
0.36
0.63
0.52
11.32
0.55
0.54
0.50
0.50
0.50
0.50
0.50
0.50
11500
0.50
0.54
EATA
92.14
3.98
1:33
2.16
4:50
2:37
11:02
[1.4]
14:06
15.26
9.65
1.36
9.88
14.34
12.12
6:26
CoTTA
$38 78
563
7.12
6.31
8.66
5.74
9.68
10.55
11.75
12.00
11.15
4.87
5.35
7.80
8.00
6.16
SAR (step=1)
113.76
8.90
3.11
1.67
1:58
1447
1:35
1.19
1.03
1.04
0.93
0.83
1.00
0.74
0.77
1.83
SAR (step-10)
774.11
2.67
3,26
2.38
1.64
1.85
2.49
3,16
3,81
2.72
3.12
0.81
3.47
3.04
1,76
2.66
SIAATA (60g=100) 10)
736.28
9.68
19.40
12.14
30.28
17.08
42.36
43.10
31,96
40.08
29.24
3.31
34.56
45.24
45.74
28,86
enhance the TTA setting by fine-tuning baselines on randomly selected labeled samples. Specifically, the classifier of BesNet18-BN is pre-adapted to the brightness corruption (source domain) before test-time adapting. SimATTA's label budget is around 4,000, while all other TTA methods have budget 4,500 for randomly selected labeled samples. The data stream order is shown in Tab. 3 Time is measured across all corrupted images in the Noise and Blur noise types, and the values represent the average time cost for adapting 10,000 images. The results clearly evidence the efficiency of ATTA (RQ2), while substantially outperforming all enhanced TTA baselines. Simply accessing labeled samples cannot benefit TTA methods to match ATTA. With 10 training updates (step=10) for each batch, FTTA methods would suffer from severe CF problem. In contrast, ATTA covers a statistically significant distribution, achieving stronger performances with 10 training updates or even more steps till approximate convergences. In fact, longer training on Tent (step=10) leads to worse results (compared to step=1), which further motivates the design of the ATTA setting. The reason for higher absolute time cost in Tab. 3 is due to differences in training steps. In this experiment, SimATTA has a training step of 10, and similar time cost as SAR per step.
Note that if the enhanced TTA setting is further improved to maintain distributions with a balanced CF mitigation strategy and an incremental clustering design, the design approaches ATTA, Specifically, we compare SimATTA with its variants as the ablation study (RQ3) in Appx. 1.2
5.3 COMPARISONS TO A STRONGER SETTING: ACTIVE DOMAIN ADAPTATION
In addtion to the above comparisons with (en- hanced) TTA, which necessitate the requirement of extra information in the ATTA setting, we com- pare ATTA with stronger setting Active Domain Adaptation (ADA) to demonstrate another supe- riority of ATTA, i.e., weaker requirements for comparable performances (RQ4). ADA baselines are able to choose the global best active samples, while ATTA has to choose samples from a small sample buffer (e.g., size of 100) and discard the rest. Tab. presents the post-adaptation model per- formance results. All ADA results are averaged from 3 random runs, while ATTA results are the post-adaptation performances averaged from the two data stream orders. As can be observed, despite the lack of pre-collected target dataset, SimATTA produces better or competitive results against ADA methods. Moreover, without source data access, SimATTA's design for CF allows it to maintain superior source domain performances over ADA methods. Further experimental studies including the Office-Home dataset are provided in Appx. [
Table 4:
Comparisons to ADA baselines. Source domains are denoted as "(S)". Results are average accuracies (with standard deviations).
P(5)
Random
96.21 (0.80)
81.19
80.75 (1.27)
$4.34 (0)
Eatep 330
(0.64)
82.48 (1.71)
(1.01)
(1.50)
79.31
(0.65)
CLUB 5009
96.69 (0.17)
83.97
84.77 (0.88)
86,91 (0.26)
SimAFTA (8
98,89 (0.09)
84.89
09.09)
63,06 (2 24)
VEECS
(.05)
V
(1.65)
66,07
70.72 (0.30)
(1.71)
Entoppy 3001
29
(3.07)
Kinean 500)
(0.27)
67.57
70.77
CLUB (8 500)
85.70 (10.09)
65.29 (1.49)
(9.62
(5.05)
SimAFTA (8 3000
09.47
(7,90)
(1.83)
In conclusion, the significant improvement compared weaker settings (TTA, enhanced TTA) and the comparable performance with the stronger setting, ADA, rendering ATTA a setting that is as efficient as TTA and as effective as ADA. This implies its potential worthy of future explorations.
exploratis
6 CONCLUSION AND DISCUSSION
There's s no denying that OOD generalization can be extremely challenging without certain information, often relying on various assumptions easily compromised by different cireumstances. Thus. it's prudent to seek methods to achieve significant improvements with minimal cost, e.g., DG methods leveraging environment partitions and ATTA methods using budgeted annotations. As justified in our theoretical and experimental studies, ATTA stands as robust approach to achieve real-time OOD generalization. Although SimATTA sets a strong baseline for ATTA, there's 's considerable scope for further investigation within the ATTA setting, One potential direction involves developing alternatives to prevent CF in ATTA scenarios. While selective entropy minimization on low-entropy samples has prove to be empirically effective, it relies the quality of the pre-trained model and training on incorrectly predicted low- low-entropy samples may reinforce the errors. It might not be cost-effective to expend annotation budgets on low-entropy samples, but correcting them could be a viable alternative solution. We anticipate that our work will spur numerous further explorations in this field.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported in part by National Science Foundation grant IIS-200686] and National Institutes of Health grant U01A0070112.
REFERENCES
Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, and Mario Marchand. Domain- adversarial neural networks. arXiv preprint arXiv: 2014.
Lucas Baier, Tim Schlör, Jakob Schöffer, and Niklas Kühl. Detecting concept drift with neural network model uncertainty. In Hawaii International Conference on System Sciences, 2021. URL
Shai Ben- John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79:151-175, 2010.
Davide Cacciarelli and Murat Kulahci. A survey on online active learning, 2023.
Cheng Chen, Quande Liu, Yueming Jin, Qi Dou, and Pheng-Ann Heng. Source-free domain adaptive fundus image segmentation with denoised pscudo-labeling, In Medical Image Computing and Computer Assisted Intervention-MIICAA 2021: 24th International Conference, Strasbourg, France, September 27-October 2021, Proceedings, Part V 24, pages 225 235.. Springer, 2021.
Li Chen, Tutian Tang, Zhitian Cai, Yang Li, Penghao Wu, Hongyang Li, Jianping Shi, Junchi Yan, and Yu Qiao. Level autonomous driving on single device: Diving into the devils of openpilot. arXiv preprint arXiv:2206.08 00100000......... 2022a.
Weijie Chen, Luojun Lin, Shicai Yang, Di Xie, Shiliang Pu, and Yueting Zhuang. Self-supervised noisy label learning for cource-free unsupervised domain adaptation. In 2022 IEEÉ/RSJ In- ternational Conference on Intelligent Robots and Systems (IROS), pages 2022b.
IEEE,
Yining Chen, Colin Wei, Ananya Kumar, and Tengyu Ma. Self-training avoids using spurious features under domain shift. Advances in Neural Information Processing Systems, 33:21061-21071, 2020.
David A Cohn, Zoubin Ghahramani, and Michael Jordan. Active learning with statistical models. Journal of artificial intelligence research, 4: 4:129-145, 145, 1996.
Matthias De Lange, Rahaf Aljundi, Marc Masana, Sarah Parisot, Xu Jia, Aleš Leonardis, Gregory Slabaugh, and Tinne Tuytelaars. A continual learning survey: Defying forgetting in classification tasks. IEEE transactions on pattern analysis and machine intelligence, 44(7):3366-3388 2021.
Yuhe Ding, Lijun Sheng, Jian Liang, Aihua Zheng, and Ran He. Proxymix: Proxy-based mixup training with label refinery for source-free domain adaptation. arXiv preprint 2r5 2022.
Cian Eastwood, lan Mason, Christopher KI Williams, and Bernhard Schölkopf. Source- adaptation to measurement shift via bottom-up feature restoration. arXiv preprint
2021.
Jiahao Fan, Hangyu Zhu, Xinyu Jiang, Long Meng, Chen Chen, Cong Fu, Huan Yu, Chenyun Dai, and Wei Chen. Unsupervised domain adaptation by statistics alignment for deep sleep staging networks. IEEE Transactions Neural Systems and Rehabilitation Engineering, 30:205-216 2022.
Chen Fang, Ye Xu, and Daniel N Rockmore. Unbiased metric learning: On the utilization of multiple datasets and web images for softening bias. In Proceedings of the IEEE International Conference on Computer Vision, pages 1657-1664, 2013.
Yuqi Fang, Pew-Thian Yap. Weili Lin, Hongtu Zhu, and Mingxia Liu. Source-free unsupervised domain adaptation: A survey. arXiv preprint 1XXi:2301.00066, 2022.
Francois Fleuret et al. Uncertainty reduction for model adaptation in semantic segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9613-9623, 2021.
10

---

Published as a conference paper at ICLR 2024
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International conference machine learning, pages 1180-1189. PMLR, 2015.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural networks. The journal of machine learning research, 17(1):2096-200 2030, 2016.
Jakob Gawlikowski, Cedrique Rovile Njieutcheu Tassi, Mohsin Ali, Jongseok Lee, Matthias Humt, Jianxiang Feng, Anna Kruspe, Rudolph Triebel, Peter Jung, Ribana Roscher, et al. A survey of 2021.
uncertainty in deep neural networks. arXiv preprint orXiv:2107.06:
Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimization. Advances in neural information processing systems, 17, 2004.
Shurui Gui, Chaoyue Wang, Qihua Chen, and Dacheng Tao. Featureflow: Robust video interpolation via structure structure-to-texturee generation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 14004-14013 2020.
Shurui Gui, Xiner Li, Limei Wang. and Shuiwang Ji. GOOD: A graph out-of-distribution benchmark. In Thirty-sixth Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2022. URL http:///ppeevieeeeee///ouuunnnda
Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. arXiv preprint arXiv:2007.01434, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. March 2019a. doi: 10.48550AARXIV.190..222
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. arXiv preprint arXiv: 190. 2019b.
Steven CH Hoi, Rong Jin, Jianke Zhu, and Michael R Lyu. Semisupervised svm batch mode active learning with applications to image retrieval. ACM Transactions on Information Systems (TOIS), 27(3):1-29, 2009.
Yihan Hu, Jiazhi Yang. Li Chen, Keyu Li, Chonghao Sima, Xizhou Zhu, Siqi Chai, Senyao Du, Tianwei Lin, Wenhai Wang, et al. Planning-oriest oriented autonomous driving. In Proceedings of the IEFF/CVF Conference Computer Vision and Pattern Recognition, pages 17853-17862, 2023.
Jaxing Huang, Dayan Guan, Aoran Xiao, and Shijian Lu. Model adaptation: Historical contrastive learning for unsupervised domain adaptation without source data, Advances in Neural Information Processing Systems, 34:3635-3649, 2021.
Masato Ishii and Masashi Sugiyama. Source-free domain adaptation via distributional alignment by
matching batch normalization statistics. arXiv preprint 1rXiv:2101.10842, 2021.
Yusuke Iwasawa and Yutaka Matsuo. Test-time classifier adjustment module for model-agnostic domain generalization. Advances in Neural Information Processing Systems, 34:2427-244h 2021.
Suyog Dutt Jain and Kristen Grauman. Active image segmentation propagation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2864-2873, 2016.
Guoliang Kang, Lu Jiang, Yi Yang, and Alexander G Hauptmann. Contrastive adaptation network for unsupervised domain adaptation. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 4893-4902, 2019.
Ashish Kapoor, Kristen Grauman, Raquel Urtasun, and Trevor Darrell. Active learning with gaussian processes for object categorization. In 2007 IEEE 11th international conference computer vision, pages 1 1-8. IEEE, 2007.
Neerav Karani, Ertune Erdil, Krishna Chaitanya, and Ender Konukoglu. Test-time adaptable neural networks for robust medical image segmentation. Medical Image Analysis, 101901,,7 2021.

---

Published as a conference paper at ICLR 2024
Ronald Kemker, Marc McClure, Angelina Abitino, Tyler Hayes, and Christopher Kanan. Measuring catastrophic forgetting in neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Daniel Kifer, Shai Den-David, and Johannes Gehrke. Detecting change in data streams. In VLDB, volume 4, pages 180-191. Toronto, Canada, 2004.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho. Agnieszka Grabska-Baree Barwinsww, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114 (13):3521-3522) 2017.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: benchmark of wn-the-wild distribution shifts. In International Conference on Machine Learning, pages 5637-5664. PMLR, 2021.
Divya Kothandaraman, Sumit Shekhar, Abhilasha Sancheti, Manoj Ghuhan, Tripti Shukla, and Dinesh Manocha. Salad: Source-free active label-agnostic domain adaptation for classification, segmentation and detection. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 382-391, 2023.
K Krishna and M Narasimha Murty. Genetic k-means algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 29(3):433-439 1999.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Communications of the ACM, 60(6):84-90, 2017.
David Krueger, Ethan Caballero, Joern-Henrk Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of- -iitof--istiiuution generalization via risk extrap- olation (REx). In International Conference on Machine Learning, pages 5815-5826. PMLR, 2021.
Vinod K Kurmi, Venkatesh K Subramanian, and Vinay P Namboodiri. Domain impression: A source data free domain adaptation method. In Proceedings of the IEEE/CVF winter conference on applications of computer vision, pages 615-625, 2021.
David D Lewis and Jason Catlett. Heterogemeous uncertainty sampling for supervised learning. In Machine learning proceedings 1994, pages 148-156. Elsevier, 1994.
Aodong Li, Alex Boyd, Padhraic Smyth, and Stephan Mandt. Detecting and adapting to irregular distribution shifts in bayesian online learning. Advances in neural information processing systems, 34:6816-6822 2021a.
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M Hospedales. Deeper, broader and artier domain generalization. In Proceedings of the IEEE international conference on computer vision, pages 5542-5550, 2017.
Rui Li, Qianfen Jiao, Wenming Cao, Hau-San Wong, and Si Wu. Model adaptation: Unsupervised domain adaptation without source data. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pages 9641-9650, 2020.
Xianfeng Li, Weijie Chen, Di Xie, Shicai Yang, Peng Yuan, Shiliang Pu, and Yueting Zhuang. A free lunch for unsupervised domain adaptive object detection without source data. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 8474-8481, 2021b.
Zhizhong Li and Derek Hoiem. Learning without forgetting. IEEE transactions pattern analysis and machine intelligence, 40(12):2935-2947, 2017.
Jian Liang, Dapeng Hu, Ran He, and Jiashi Feng. Distill and fine-tune: Effective adaptation from a black-box source model. arXiv preprint arXiv:2104. 01539, 1(3), 2021.
Jian Liang, Dapeng Hu, Jiashi Feng, and Ran He. Dine: Domain adaptation from single and multiple black-box predictors. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8003-8013, 2022.
12

---

Published as a conference paper at ICLR 2024
Yong Lin, Shengyu Zhu, Lu Tan, and Peng Cui. Zin: When and how to learn invariance without environment partition? Advances in Neural Information Processing Systems, 35:24529-2445 2022.
Xiaofeng Liu, Fangxu Xing, Chao Yang, Georges El Fakhri, and Jonghye Woo. Adapting off-the- shelf source segmenter for target medical image segmentation. Medical Image Computing and Computer Assisted Intervention-MICCAI 2021: 24th International Conference, Strasbourg, France, September 27-October 1, 2021, Proceedings, Part II 24, pages 549-559. Springer, 2021 la
Xinyu Liu and Yixuan Yuan. A source-free domain adaptive polyp detection framework with style diversification flow. IEEE Transactions on Medical Imaging, 41(7):1 197--1908, 2022.
Yuang Liu, Wei Zhang, Jun Wang, and Jianyong Wang. Data-free knowledge transfer: survey. arXiv preprint 1r 15278, 2021
Yuejiang Liu, Parth Kothari, Bastien Van Delft, Baptiste Bellot-Gurlet, Taylor Mordan, and Alexandre Alahi. Tit++: When does self-supervised test-time training fail or thrive? Advances in Neural Information Processing Systems, 14:21808-21822 2021c
Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan. Learning transferable features with deep adaptation networks. In International conference on machine learning, pages 97-105. PMLR, 2015.
David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30, 2017.
Chaochao Lu, Yuhuai Wu, José Miguel Hernández-Lobato and Bernhard Schölkopf. Invariant causal representation learning for -id-tii-iitiittionn generalization. In International Conference on Learning Representations, 2021.
Xinhong Ma, Junyu Gao, and Changsheng Xu. Active universal domain adaptation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8968-8888 3968-8977, 8977, 2021.
Haitao Mao, Lun Du, Yujia Zheng, Qiang Fu, Zelin Li, Xu Chen, Shi Han, and Dongmei Zhang. Source free unsupervised graph domain adaptation. arXiv preprint arXiv:21
2021. Christoforos Mavrogiannis, Francesca Baldini, Allan Wang, Dapeng Zhao, Pete Trautman, Aaron Steinfeld, and Jean Oh. Core challenges of social robot navigation: A survey. ACM Transactions on Human-Robot Interaction, 12(3):133,, 2023.
Zachary Nado, Shreyas Padhy, D Sculley, Alexander D' Amour, Balaji Lakshminarayanan, and Jasper Snoek. Evaluating prediction-time batch normalization for robustness under covariate shift. arXiv preprint arXiv:2006. 10963, 2020.
Munan Ning, Donghuan Lu, Dong Wei, Cheng Bian, Chenglang Yuan, Shuang Yu, Kai Ma, and Yefeng Zheng. Multi-anchor active domain adaptation for semantic segmentation. Proceedings of the IEEE/CVF International Conference Computer Vision, pages 91 11-91222 2021.
Shuaicheng Niu, Jiaxiang Wu, Yifan Zhang, Yaofo Chen, Shijian Zheng, Peilin Zhao, and Mingkui Tan. Efficient test-time model adaptation without forgetting. In International conference machine learning, pages 16888-1668 16905. PMLR, 2022.
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 The Eleventh International Con- ference Learning Representations, 2023. htt.hh////ppporrreeeeeer//o////r
Sinno Jialin Pan, Ivor W Tsang, James T Kwok, and Qiang Yang. Domain adaptation via transfer component analysis. IEEE transactions on neural networks, 22(2):199-21) 190- 2010.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, segforeeffrmence deep learning library. Advances in neural information processing systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2024
Vishal M Patel, Raghuraman Gopalan, Ruonan Li, and Rama Chellappa. Visual domain adaptation: A survey of recent advances. IEEE signal processing magazine, 32(3):53 69, 2015.
Judea Pearl. Causality. Cambridge university press, 2009.
Fabian Pedregosa, Gaël Varoquaux. Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leamn Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 78(5):947-1012, 2016.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
Viraj Prabhu, Arjun Chandrasekaran, Kate Saenko, and Judy Hoffman. Active domain adaptation via clustering uncertainty wwiightd embeddings. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8505-8514, 2021.
Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. arXiv preprint arXiv:2010.05761, 2020.
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv:1911.0871 2019.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch normal- ization help optimization? Advances in neural information processing systems, 31, 2018.
Akanksha Saran, Safoora Yousefi, Akshay Krishnamurthy, John Langford, and Jordan T. Ash. Streaming active learning with deep neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 30005-30021. PMLR, 23-29 Jul 2023, URL URL https://proceeeiigss.n mir Dress/v202/saran222..mo
Harald Schafer, Eder Santana, Andrew Haden, and Riccardo Biasini. A commute in data: The comma2k19 dataset, 2018.
Tobias Scheffer, Christian Decomain, and Stefan Wrobel. Active hidden markov models for informa- tion extraction. In Advances in Intelligent Data Analysis: 4th International Conference, IDA 2001 Cascais, Portugal, September 13-15, 2001 Proceedings 4, pages 309-318. Springer, 2001.
Steffen Schneider, Evgenia Rusak, Luisa Eck, Oliver Bringmann, Wieland Brendel, and Matthias Betbge. Improving robustness against common corruptions by covariate shift adaptation. Advances in Neural Information Processing Systems, 33:1 1539-11551, 2020.
Burr Settles. Active learning literature survey. 2009.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409, 1556, 2014.
Jong-Chyi Su, Yi-Hsuan Tsai, Kihyuk Sohn, Buyu Liu, Subhransu Maji, and Manmohan Chandraker. Active adversarial domain adaptation. In Proceedings of the IEEE/CVF Winter Conference Applications of Computer Vision, pages 739-748, 2020.
Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation. In European conference on computer vision, pages 443-450, Springer, 2016.
Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt. Test-time training with self-superv for generalization under distribution shifts. In International conference on machine learning, pages 9229-92442 PMLR, 2020.
14

---

Published as a conference paper at ICLR 2024
Yi-Hsuan Tsai, Wei-Chih Hung, Samuel Schulter, Kihyuk Sohn, Ming- Asuan Yang, and Manmohan Chandraker. Learning to adapt structured output space for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7472-7481, 2018.
Eric Tzeng, Judy Hoffman, Trevor Darrell, and Kate Saenko. Simultaneous deep transfer across domains and tasks. In Proceedings of the IEEE international conference on computer vision, pages 4068-4076 2015.
Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7167-7176, 2017.
Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 5018-5027, 2017.
Sudheendra Vijayanarasimhan and Ashish Kapoor. Visual recognition and detection under bounded computational resources. In 2010 IEEE Computer Sociery Conference on Computer Vision and Pultern Recognition, pages 1006-1013. IEEE, 2010.
Dan Wang and Yi Shang. A new active labeling method for deep learning. In 2014 International joint conference on neural networks (IJCNN, pages 112-119. IEEE, 2014.
Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell. Tent: Fully test- time adaptation by entropy minimization. International Conference on Learning Representations, 2021. URL
Mei Wang and Weihong Deng. Deep visual domain adaptation: A survey, Neurocomputing, 312: 135-153, 2018.
Qin Wang, Olga Fink, Lue Van Gool, and Dengxin Dai. Continual test-time domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7201-7211, 2022a.
Rui Wang, Zuxuan Wu, Zejia Weng, Jingjing Chen, Guo-Jun Qi, and Yu-Gang Jiang. Cross-domain contrastive learning for unsupervised domain adaptation. IEEE Transactions on Multimedia, 2022b.
Garrett Wilson and Diane Cook. A survey of unsupervised deep domain adaptation. ACM Transactions on Intelligent Systems and Technology (TIST), 11(5):1-46, 2020.
Binhui Xie, Longhui Yuan, Shuang Li, Chi Harold Liu, Xinjing Cheng, and Guoren Wang. Active learning for domain adaptation: An energy-based approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages
2022.
Zhao Xu, Kai Yu, Volker Tresp, Xiaowei Xu, and Jizhi Wang. Representative sampling for text classification using support vector machines. In Advances Information Retrieval: 25th European Conference on IR Research, ECIR 2003, Pisa, Italy, April 14-66, 2003. Proceedings 25, pages 333 Springer, 2003.
Baoyao Yang, Hao-Wei Yeh, Tatsuya Harada, and Pong C Yuen. Model-induced generalization emror bound for information-theeretiic representation learning in source-data-fie unsupervised domain adaptation. IEEE Transactions on Image Processing, 31:419-432, 2021a.
Guanglei Yang, Hao Tang, Zhun Zhong, Mingli Ding, Ling Shao, Nicu Sebe, and Elisa Ricci. Transformer- source- free domain adaptation. arXiv preprint arXiv:2105.141:1 2021b.
Jianfei Yang, Xiangyu Peng, Kai Wang, Zheng Zhu, Jiashi Feng, Lihua Xie, and Yang You. Divide to adapt: Mitigating confirmation bias for domain adaptation of black-box predictors. arXiv preprint arXiv:2205. 14467, 2022.
H Yao, Yuhong Guo, and Chunsheng Yang. Source-free unsupervised domain adaptation with surrogate data generation. In Proceedings of NeurIPS 2021 Workshop on Distribution Shifts: Connecting Methods and Applications, 2021.
15

---

Published as a conference paper at ICLR 2024
Hao- Wei Yeh, Baoyao Yang, Pong Yuen, and Tatsuya Harada. Sofa: Source- Cource-data-ie feature alignment for unsupervised domain adaptation. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 474-483, 2021.
Fuming You, Jingjing Li, and Zhou Zhao. Test-time batch statistics calibration for covariate shift. arXiv preprini arXiv:21 2021.
Hu Yu, Jie Huang, Yajing Liu, Qi Zhu, Man Zhou, and Feng Zhao. Source-free domain adaptation for real-world image dehazing. In Proceedings of the 30th ACM International Conference on Multimedia, pages 6645-6654, 2022.
Haojian Zhang, Yabin Zhang, Kui Jia, and Lei Zhang. Unsupervised domain adaptation of black-box source models. arXiv preprint arXiv:2101.02855 2021.
Marvin Zhang, Sergey Levine, and Chelsea Finn. Memo: Test time robustness via adaptation and augmentation. Advances in Neural Information Processing Systems, 35:38629-38642, 2022a.
Yifan Zhang, Xue Wang, Kexin Jin, Kun Yuan, Zhang Zhang, Liang Wang, Rong Jin, and Tieniu Tan.
Adanpe: Exploring non-parametrie classifier for test-time adaptation. In International Conference on Machine Learning, pages 41 647-416676. PMLR, 2023.
Yizhe Zhang, Shubhankar Borse, Hong Cai, and Fatih Porikli. Auxadapt: Stable and efficient test-time adaptation for temporally consistent video semantic segmentation. Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 2339-2348, 2022b.
Bowen Zhao, Chen Chen, and Shu-Tao Xia. Delta: degradation-free fully test-time adaptation. arXiv preprint arXiv:2301. 13018, 2023a.
Hao Zhao, Yuejiang Liu, Alexandre Alahi, and Tao Lin. On pitfalls of test-time adaptation. In International Conference on Machine Learning (ICML), 2023b.
Chunting Zhou, Xuezhe Ma, Paul Michel, and Graham Neubig. Examining and combating spurious features under distribution shift. In International Conference Machine Learning, pages 12857- 12867. PMLR, 2021.
16

---

Published as a conference paper at ICLR 2024
Active Test-Time Adaptation: Foundational Analyses and An Algorithm Supplementary Material
A BROADER IMPACTS
The field of domain generalization primarily concentrates on enhancing a model's generalization abilities by preparing it thoroughly before deployment. However, it is equally important for deep learning applications to have the capacity for real-time adaptation, as no amount of preparation can account for all possible scenarios. Consequently, domain generalization and test-time adaptation complementary strategies: the former is more weighty and extensive, while the latter is more agile, lightweight and privacy-friendly.
This work delves into the development of a real-time model adaptation strategy that can be applied to any pre-trained models, including large language models, enhance their adaptive capabilities. Our research does not involve any human subjects or dataset releases, nor does it raise any ethical concerns. Since this work does not directly tie to specific applications, we do not foresee any immediate negative societal impacts. Nonetheless, we acknowledge that any technological advancement may carry potential risks, and we encourage the continued assessment the broader impacts of real-time adaptation methodologies in various contexts.
B FAQ & DISCUSSIONS
To facilitate the reviewing process, we summarize the answers to the questions that arose during the discussion of earlier version of this paper.
The major updates of this version are reorganized theoretical studies, incremental clustering details, experimental reorganization, and additional datasets and settings. We include more related field comparisons to distinguish different settings. We also cover the position this paper in literature and the main claims of this paper. Finally, we will frankly acknowledge the limitations of this paper, explain and justify the scope of coverage, and provide possible future directions.
Q1: What is the relationship between the proposed ATTA protocol and stream based active learning (Saaan et al.) 2023
A: We would like discuss the difference between our work and the referenced work.
Real-time Training Distinction: Saran al. 2023) doesn't 't operate in real-time capacity. This is evident from their experiments, where their model is trained only after completing a round. In contrast, our work involves training the model post each batch. This positions Saran et al. (2023)'s work intrinsic active learning technique, while our approach leans towards TTA methods.
2. Continual Training Nuance: Following the point above, Saran et al. 20233 stands out of the scope of continual training. As they mentioned 'each time new data are acquired, the ResNet is reset to the ImageNet pre-trainne pre-trained weights before being updated (aaran et al.) (2023) starts afresh with each iteration and is out of scope for CF discussions. Contrarily, our model is continuously trained on varying distributions, compelling us address the CF issue while preserving advantages derived from various stored distributions.
3. Comparative Complexity: Given the aforementioned distinctions, it's evident that our task presents a greater challenge compared to theirs. In addition, we have included comparisons with stronger active learning settings in Sec. 5.3
Q2: What are the insights from the theoretically foundational analysis?
A:
1. It sets a well-defined formulation and grounded theoretical framework for the ATTA setting.
2. While entropy minimizations can cause CF, balancing the learning rate and number of high/low entropy samples is conversely the key solution to both distribution shifts and
17

---

Published as a conference paper at ICLR 2024
CF by corresponding benefits. in that this simple operation can make methods either too conservative too aggressive without the correct balancing conditions.
Though adding low-entropy data is intuitive, it is crucial
3. The studies in Sec. 3.1 directly present a feasible and guaranteed solution for imple- menting ATTA to tackle shifts while avoiding CF. The aligned empirical validations of See. 3.2
also instruct the implementation of SimATTA.
Q3: In test-time adaptation, one important issue is that the number of testing samples in batch may be small, which means the sample size m will also be very small. May it affect the theorem and make them become very loose?
A: We consider this issue jointly from theoretical and empirical validations.
1. It is true that the theoretical bounds can be loose given a small size of m unlabeled test samples. This situation of the error bound is mathematically ascribed to the quotient between the VC-dimension d of the hypothesis class and m. Under the VC-dimension theory, the ResNet18 model we adopt should have d > m. However, practically we perform fine-tuning on pre-trained models instead of training from scratch, which significantly reduces the scale of parameter update. In this case, an assumption can be established that fine-tuning a model is roughly equivalent to learning model with a relatively small d (Appx. H). This assumption potentially underpinned by the empirical alignment of our validation experiments with the theoretical framework (Fig. []]. To this end, experiments indicate that d and m are practically of similar scale for our settings. This prevents our theoretical bounds from being very loose and meaningless in reality.
2. Regarding cases that our assumption does not apply, this issue would appear inevitable, since it is rigorously inherent in the estimation error of our streaming and varying test distributions. The distribution of a test stream can be hardly monitored when only a limited batch is allowed, which we consider directly implies the necessity of using a buffer for unlabeled samples. A good practice is to maintain a relatively comparable sample buffer scale.
limitation of TTA settings. Moreover, this issue
Q4: What distribution shifts can ATTA solve?
A: We would like to follow (but not limited to) the work (Zhao et al. 2023b) to discuss the distribution shifts ATTA can solve.
1. As elucidated in Sec. 3.1 and Sec. ATTA can solve domain generalization shifts. Domain generalization shifts include complex shifts on the joint data distribution P(X, Y), given X as the covariates and Y as the label variable. Since PY) P(X) X), ATTA can handle covariate shift (P(X)), label shift (P(Y)), and conditional shift (P(Y)X)). The shifts both covariate and conditional distributions can cover the shift on labels, but they (covariate + conditional shifts) are more complicated than pure label shifts, where only the marginal label distribution changes while the conditional distribution remains. Note that the conditional shifts are generally caused by spurious correlations, where the independent causal mechanism assumption (Pearl 2009) holds no concept drifts exist.
2. In our framework, the distribution support of X at different time steps can be different, but we don't 't cover the situation where the support of Y changes, i.e., class-incremental problems.
Q5: It is unclear how many samples are selected in each minibatch of testing samples. How the total budget is distributed across the whole testing data stream?
A: The number of selected samples for each minibatch is decided jointly by the incremental clustering and the cluster centroid number NC()). Intuitively, this sample selection a dynamic process, with NC(() restricting the budget and incremental clustering performing sample selection. For each batch, we increase applicable clustering centroids as a maximum limit, while the exact number of the selected samples is given by the incremental clustering by how many clusters are located in the scope of new distributions. e.g., if the incoming batch does not introduce new data distributions, then we select zero samples even with increased NC(L). In contrast, if the incoming batch contains data located in multiple new distributions, the incremental clustering tends to select more samples than the NC(t) limit, thus forcing to merging of multiple previous clusters into one new cluster.
18

---

Published as a conference paper at ICLR 2024
The incremental clustering is detailed in Sec. 4.2 and NC(1) is naively increased by a constant hyper-parameter k. Therefore, the budget is adaptively distributed according to the data streaming distribution with budgets controlled by k, which is also the reason why we compare methods under a budget limit.
Q6: Could compared methods have access to a few ground-truth labels as well? Making other algorithms be able to use the same amount of ground-truth labels randomly will produce fairer comparisons.
A:
1. The enhanced TTA setting exactly the setup we provide to produce fairer comparisons. See Tab. and Tab. 5 for comparison results.
2. ATTA also compares to stronger setting ADA which can access the whole test datasets multiple times.
Table 5: The table demonstrates the comparisons PACS where all enhanced TTA baselines have 300 budgets to randomly select labeled samples. The training steps of these labeled samples are the same the original TTA method training steps. For accumulated sample selection, please refer to our ablation studies.
Method
Domoin wise data stream
AVG
Random data straa
AVG
P-
-+A--
-C--
-48
A
C
Source only
BN wil adaaee
BN w/ adapt
09.30 70
08.74
68.07
50.38 38
64.85
78.01
42.91
54.57
99 70
78.74
68.07
59.3 58
64.85
25.03
54.57
42.91
62.50
43.44
43.44
62.50
62:50
43:44
41.44
62.35 00.50
99: 20
98.74
68:07
59.38
64.85
18.03
42.91
$4.57
Tent (stepec1)
N/A
70.07
68:41
64:42
07:72
14.17
77.61
68:92
61:20
62:
66 59
67.55 33
08.
74:37
70.26
66.07
Test (sttpe110)
N/A
76.27
63.78
49.
$9.46
38.62
48 65.45
55.03
56.20
53.22
52.55
55.55
58.
47.56
60:75
58.00
TTA
CoTTA
DATA
NIA
N1A
66.55
n9.55
63.14
66.94
61.42
59.91
90 12
98.36
69.38
61.87
66 65
66 60
66.83
67.68
60.34
57.26
59.81
97.36
63:46
68.38
65. 02
65.50 84
92. 22
98, 68
73.78
71.53
68.30
70.64
62.41
99.74
SAR ()tepe=11
N/A
66.60
63.78
50.34
98:15
67.6 87
64 04
4B
57.21
$6.06
56.78
57. 14
08. 38
68.80
64.50
$3.02
SAR (stops-10) 10)
N6A
69.09
66.55
49.07
96.23
62.50
59.34
46.53
49.76
52.74
48.51
49.06
95.39
57.13
54,51
38.76
Owm (8) i 2000
NAA
76.86
70.90
30
98 96.80
$4.47
62.25
81.52
69.47
76.49
82.45
82.22
98. 95
84.91
$3.92
86.00
Q7: What is the position of ATTA?
A: Comparisons with different settings are challenging. In this work, the design of our experiments (Sec.(5) is to overcome this challenge by comparing both weaker settings and stronger settings. While the significant performance over weaker settings renders the necessity of extra information, the comparable performance with stronger settings provides the potential to relax restricted requirements. Intuitively, ATTA is the most cost-effective option in the consideration of both efficiency and effectiveness. We further provide the following ATTA summary:
ATTA, which incorporates active learning in FTTA, is the light, real-time, source-free, widely applicable setting to achieve high generalization performances for dest-time adaptation.
1. Necessity: From the causality perspective, new information is necessary (Lin et al. 2022 Pearl 2009; Peters et al., (017) to attain generalizable over distribution shifts which are insurmountable within the current TTA framework.
2. Effectiveness: Compared to FTTA methods, ATTA produces substantially better perfor- mances, on-par with the costly active domain adaptation (ADA) methods as shown in Table
3 in the paper.
3. Efficiency: Relative to ADA methods, ATTA possesses superior efficiency, similar to general FTTA methods, as shown in Tab. 3
4. Applicability: ATTA is a model-agnostic setting. (1) Compared to domain generalization methods, ATTA do not require re-training and has the potential apply to any pre- pre-trained models. One interesting future direction is designing ATTA methods for large language models (LLMMs). where re-trainings are extremely expensive and source data may be in- accessible. (2) Compared to FTTA methods, ATTTA can protect model parameters from corrupting while learning new distributions by fine-tuning pre-trained models, rendering more feasible and practical.
In comparison with existing works, ATTA is motivated to mitigate the limitations of previous settings:
1. FTTA: Limited generalization performance.
19

---

Published as a conference paper at ICLR 2024
2. TTT: Not source-free; limited generalization performance.
3. ADA & domain adaptation/geenrralzzaiooo Expensive re-trainings; limited applicability to pre-trained models.
4. Online active learning: does not maintain and protect adaptation performances for multiple distributions in one model and does not consider the CF problem.
Q8: What is the potential practical utility of ATTA?
A:
1. Empirically, our method can generally finish round of sample selection/traiing of 100 frames in 5s, i.., 20 frames per sec, which is more than enough to handle multiple practical situations. Experiments on time complexity are provided in Tab. 3 where SimATTA has comparable time efficiency.
2. As a case analysis, the autopilot system (Hu et al., 2023; Chen et al. 2022a) presents an application scenario requiring high-speed low-latency adaptations, while these adaptations are largely underexplored. When entering an unknown environment, e.g., construction section, a system of ATTA setting can require the driver to take over the wheel. During the period of manual operation when the driver is handling the wheel, steering signals are generated, and the in-car system quickly adaptations. The system doesn't 't need to record 60 frames per second, since only the key steering operations and the corresponding dash cam frames are necessary, which can be handled by ATTA algorithms processing 20 frames per sec. In this case, the human annotations are necessary and indirect. ATTA makes use this information and adapts the short term instead of collecting videos and having a long-round fine-tuning (Schafer et al. 2018)).
3. In addition, many scenarios applicable for ATTA are less speed-demanding than the case above. One example is personalized chatbot that subtly prompts and gathers user labels during user interaction. In a home decoration setting, applications can request that users scan few crucial areas ensure effective adaptation. Social robots (Mavrogiannis et al. [023) e.g., vacuum robots, often require users to label critical obstacles they ve encountered.
4. Compared with ADA, ATTA stands out as the tailored solution for the above scenarios. does not require intensive retraining or server-dependee computational efficiency. Meanwhile, akin to other TTA methods, ATTA also ensures user privacy. While it might marginally exceed the cost of standard TTA methods, the superior generalization ability makes it compelling choice and justifies the additional expense.
fine-tuning offering both speed and
Q9: What can be covered by this paper?
A: This paper endeavors to establish the foundational framework for a novel setting referred to as ATTA. We target (1) positioning the ATTA setting, (2) solving the two major and basic challenges of ATTA, i.e., the mitigation of distribution shifts and the avoidance of catastrophic forgetting (CF). We achieve the first goal by building the problem formulation and analyses, and further providing extensive qualitative and well-organized experimental comparisons with TTA, enhanced TTA, and ADA settings. These efforts position ATTA the most cost-effective option between TTA and ADA, where ATTA inherits the efficiency of TTA and the effectiveness of ADA. With our theoretical analyses and the consistent algorithm design, we validate the success of our second goal through significant empirical performances.
Q10: What are not covered by this paper?
A: Constructing a new setting involves multifaceted complexities. Although there are various potential applications discussed above including scaling this setting up for large models and datasets, we cannot cover them in this single piece of work. There are three main reasons. First, the topics covered by a single paper are limited. Formally establishing ATTA setting and addressing its major challenges of ATTA takes precedence over exploring practical applications. Secondly, given the interrelations between ATTA and other settings, our experimental investigations are predominantly comparative, utilizing the most representative datasets from TTA and domain adaptation to showcase persuasive results. Thirdly, many practical applications necessitate task-specific configurations, rendering them unsuitable for establishing universal learning setting. While the current focus is on laying down the foundational aspects of ATTA, the exploration of more specialized applications remains prospective avenue for future work in the ATTA domain.
20

---

Published as a conference paper at ICLR 2024
C RELATED WORKS
The development of deep learning witnesses various applications (He et al. 2016; Gui et al. 2020 To tackle OOD problem, various domain generalization works emerge (Krueger et al. 2021 Sagawa et al.
2019).
C.I
UNSUPERVISED DOMAIN ADAPTATION
Unsupervised Domain Adaptation (UDA) (Pan et al. 2010: Patel al.) 2013 Wilson and Cook
2020 WWang and Deng 2018 aims at mitigating distribution shifts between a source domain and a target domain, given labeled source domain samples and unlabeled target samples. UDA methods generally rely on feature alignment techniques to eliminate distribution shifts by aligning feature distributions between source and target domains. Typical feature alignment techniques include
discrepancy minimization (Long et al. 2015 Sun and Saenko 2016 Kang et al. (2019) and adversarial training (Ganin and Lempitsky 2015 T Tsai et al.) 2018 Ajakan et al. [2014] Ganin et al. 2016 [ Tzeng al. 2017). Nevertheless, alignments
normally not guaranteed to be correct, leading the
alignment distortion problem as noted by Ning et al. (2021).
Source-free Unsupervised Domain Adaptation (SFUDA) (Fang et al. 2022 Liu et al. 202 lb)
algorithms aim to adapt a pre-trained model to unlabeled target domain samples without access to source samples. Based whether the algorithm access model parameters, these algorithms are categorized into white-box and black- -ox methods. White-box SFUDA typically considers data recovery (generation) and fine-tuning methods. The former focuses recovering source- like data (Ding et al.] 2022; Yao et al.] (02T)) e.g., training a Generative Adversarial Network
(GAN) (Kurmi al.] [202]] Li et al., 22020), while the latter employs various techniques (Mao et al.)
2021 such as knowledge distillation (Chen et al. 2022b Liu and Yuan 2022
Yang et al.
202 lb Yu
ct al.
2022 statistics--aat based domain alignment (Ishii and Sugiyamal 2021 Liu et al.
2021a Fan 2022b) and
et al.
2022 Eastwood et al.] [222]) contrastive learning (Huang et al. [0.1 Wang et al.
uncertainty- based adaptation (Gawlikowski al.) [021]]
| Fleuret et al.) 20]1] Chen et al.
202
et al.
b0 Black-box SFUDA cannot access model parameters and often relies on self-supervised
know edge distillation (Liang et al.) 2022; 202T), pseudo-label denoising (Zhang et al.
2021 Yang
ctt al. 2022), or generative distribution alignment (Ych et al. 202 Yang et al. 202
C.2
TEST-TIME ADAPTATION
Test-time Adaptation (TTA), especially Fully Test-time Adaptation (FTTA) algorithms WWan et al.
2021 Iwasawa and Matsuo 2021 Karani et al.) 2021 Nado et al. 2020 Schneider et 2020
Wang et al. 2022a] Zhao et al. 2023a Niu et al. 2022 Zhang et al.) 2022a Niu et al. 2023
You et al. 2021| Zhang et al. 2022b), can be considered as realistic and lightweight methods for domain adaptation. Built upon black-box SFUDA, FTTA algorithms eliminate the requirement of pre-collected target dataset and the corresponding training phase. Instead, they can only access an unlabeled data stream and apply real-time adaptation and training. In addition to FTTA, Test-time Training (TTT) (Sun et al. 2020 Liu et al. 2021c) often relies on appending the original network with self-supervised task. TTT methods require retraining on the source dataset transfer information through the self-supervised task. Although they do not access the source dataset during the test-time adaptation phase, TTT algorithms are not off-the- source-free methods. TTA is a promising and critical direction for real-worid applications, but current entropy minimization- based methods can be primarily considered as feature calibrations that require high high-quality pseudo-labels. This requirement, however, can be easily violated under larger distribution shifts.
Current TTA algorithms, inheriting UDA drawbacks, cannot promise good feature calibration results, which can be detrimental in real-world deployments. For instance, entropy minimization wrongly predicted target domain samples with relatively low entropy can only exacerbate spurious correla- tions (Chen et al.) 2020). Without extra information, this problem may be analogous to applying causal inference without intervened distributions, which is intrinsically unsolvable (Peters et al. 2016 Pearl 2009). This paper aims mitigate this issue with minimal labeled target domain samples. To minimize the cost, we tailor active learning techniques for TTA settings.
It is worth noting that recent work AdaNPC (Zhang et al., 2023) is essentially domain gener- alization method with a TTA phase attached, while our ATTA is built based on the FTTA setting. Specifically,, Current FTTA methods and our work cannot access the source domain. In contrast,
21

---

Published as a conference paper at ICLR 2024
AdaNPC accesses source data to build its memory bank, circumventing the catastrophic forgetting problem. Furthermore, AdaNPC requires multiple source domains and training before performing TTA. Thus AdaNPC uses additional information on domain labels and retraining resources for its memory bank, undermining the merits of FTTA. Regarding theoretical bounds, their target domain is bounded by source domain error and model estimations (in big-O expression), while we consider active sample learning and time variables for varying test distributions.
C.3 CONTINUAL DOMAIN ADAPTATION
Many domain adaptation methods focus on improving target domain performance, neglecting the performance on the source domain, which leads to the CF problem (Kemker et al. [018 Kirkpatrick
et al. 2017] Li and Hoiem [ Lopez-Paz and Ranzato 2017 De Lange et al. 2021 Wang et al. 2022a Niu et al. 2022). This issue arises when neural network, after being trained on a sequence of domains, experiences a significant degradation in its performance on previously learned domains as continues to learn new domains. Continual learning, also known lifelong learning, addresses this problem. Recent continual domain adaptation methods have made significant progress by employing gradient regularization, random parameter restoration, buffer sample mixture, and more. Although the CF problem is proposed in the continual learning field, it can occur in any source-free OOD settings since the degradation caused by CF is attributed to the network's parameters being updated to optimize performance on new domains, which may interfere with the representations learned for previous domains.
C.4 ACTIVE DOMAIN ADAPTATION
Active Domain Adaptation (ADA) (Prabhu et al.) 2021 Ning et al.) 2021; Su et al., 2020 Ma
ee al. [202 Xie et al. 2022) extends semi-supervised domain adaptation with active learning strate- gies (Cohn et al., 1996; Settles 2009), aiming to maximize target domain performance with a limited annotation budget. Therefore, the key challenge of active learning algorithms is selecting the most informative unlabeled data in target domains (Kapoor et al. 2007). Sample selection strategies are of- ten based uncertainty (Lewis and Catlett [994| Scheffer et al. 2001), diversity (Jain and Grauman 2016; Hoi et al. (2009). representativeness (Xu et al. 2003), expected error minimization (Vijaya narasimhan and Kapoor 20100), etc. Among these methods, uncertainty and diversity-based methods are simple and computationally efficient, making them the most suitable choices to tailor for TTA settings.
Adapting these strategies is non-trivial because, compared to typical active domain adaptation, our proposed Active Test-time Adaptation (ATTA) setting does not provide access source data, model parameters, or pre-collected target samples. This requirement demands that our active sample selection algorithm select samples for annotation during data streaming. Consequently, this active sampling selection process is non-regrettable, i.e., we can only meet every sample once in short period. To avoid possible confusion, compared to the recent Source-free Active Domain Adaptation (SFADA) method SALAD (Kothandaraman et al., 2023), gradients, training additional neural networks, or pre-collected target datasets. Therefore, our ATTA setting is quite different, much lighter, and more realistic than ADA and SFADA.
do not require access model parameter
C.5 ACTIVE ONLINE LEARNING
The most related branch of active online learning (AOL) (Cacciarelli and Kulahci 2023 is active online learning on drifting data stream (Zhou et al. 2021 Baier et al. 2021; Li et al. 2021a). Generally, these methods include two components, namely, detection and adaptation. Compared with ATTA, there are several distinctions. First, this line of studies largely focuses on the distribution shift detection problem, while ATTA focuses on multi-domain adaptations. Second, AOL on drifting data stream aims to detect and adapt to one current distribution in the stream, without considering preserving the adaptation abilities of multiple past distributions by maintaining and fine-tuning the original pre-trained models. In contrast, ATTA's goal is to achieve the OOD generalization optimums adaptable across multiple source and target distributions, leading to the consideration of CF problems. Third, while AOL requires one-by-one data input and discard, ATTA maintains a buffer for incoming data before selection decisions. This is because ATTA targets maintaining the original model without corrupting and replacing it, such that making statistically meaningful and high-quality decisions is
22

---

Published as a conference paper at ICLR 2024
critical for ATTA. In contrast, AOL allows resetting and retraining new models, whose target is more lean to cost saving and one-by-one manner.
D FURTHER THEORETICAL STUDIES
this section, we refine the theoretical studies with supplement analysis and further results.
We use the H4-divereence and PLA:Hddistance definitions following (Ben-David et al. 2010).
Definition 2 (H--ivergennce). For a function class H and two distributions D3 and D2 over domain X, the H-divergence between Dj and D2 is defined as
(Di, Dz) = sup Pa--DD [h(x)) = - PAND, [M() = 1]|-
hel
The H&AH-distance defined base on H-divergence. We use the HiN-distance definition follow- ing
al.) 2010).
Definition 3 (HAM-distanndd For two distributions Dj and D2 over domain X' and a hypothesis class H. the -iddiditt between D7 and D2 w.r.t H. is defined as
dxaH (Di, D2) = sup PAND, [M(x) # (((x)) + Pa- (M(a) ( # ('(x)) A.KCH
The HAH-distance essentially provides a measure to quantify the distribution shift between two distributions. measures the maximum difference the disagreement between two hypotheses in H for two distributions, providing a metries to quantify the distribution shift between Dr and D>, H-divergence and Hiddddittance have the advantage that they can be applied between datasets, iee. estimated from finite samples. Specifically, let S1, S2 be unlabeled samples of size sampled from Di and Dz: then we have estimated HAH--distance dx(Si, S2). This estimation can be bounded based on Theorem 3.4 of Kifer et al. (2004), which we state here for completeness.
Theorem 5. Let A be collection of subsets of some domain measure space, and assume that the VC-dimension is some finite Let P1 and Pz be probability distributions over that domain and St, Sa finite samples of sizes mı, m12 drawn ii.dd according 111, respectively. Then
Pm fm (SAA(S,, - oA(Pi,
I <(2m)²e-m 2 + (2m)) m2r2/1/
(10)
where Pmi+ma is the ma + m2 'th power of P the probability that P induces over the choice of samples.
Theorem bounds the probability for relativized discrepancy, and its applications in below lemmas and Theorem T help us bound the quantified distribution shifts between domains. The probability, according to a distribution DD that an estimated hypothesis h disagrees with the true labeling function g X + (0, }} is defined as e(h(t),g) or risk c(h(t)). While the source domain dataset is inaccessible under ATTA settings, we consider the existence of the source dataset Ds for the purpose of accurate theoretical analysis. Thus, we initialize (0) as Ds, i.e., (o) = Ds. For every time step t, the test and training data can be expressed as
[lb(,= t) g(x)]], which we also refer to as the error
(te(t) and (f) = Ds U (1) U (2a U U....U (t)
(11)
We use N to denote the total number of samples in (er(t) and À = (Au. du, Xx) to represent the ratio of sample numbers in each component subset. In particular, have
[D) = > (t) = Ao. [D.
DDsl
[Dre [D),.tt)
Xe,
(12)
where >t A; 1. Therefore, at time step f, the model has been trained on labeled data Der (t), which contains + components consisting of a combination of data from the source domain and multiple test-time domains. For each domain the model encounters, Ds, (1), (2, (t),t), let e, (I(C)) denote the error of hypothesis at time on the jth domain. Specifically, cu(h(()) = es (h(() represents the error of l((() on the source data Ds. and ()()(() for 1 denotes the error of h(()) on test data U.. Our optimization minimizes a convex combination of training error over the labeled samples from all domains. Formally, given the vector (wo; W1,".. wx) of domain emor
23

---

Published as a conference paper at ICLR 2024
weights with Σ = 1 and the sample number from each component N, = AyN, we minimize
the empirical weighted error of (t))
en (o) = =3)0(())))))) (.
W El((,,) N
(13)
==0
Note that w, À and are also functions of t, which we omit for simplicity.
We now establish two lemmas the preliminary for Theorem In the following lemma, we bound the difference between the weighted error (h())) and the domain error (,(h()))
Lemma 6. Let be a hypothesis space of VC-dimension At time step t, let the ATTA data domains be Ds, (1), (t)(2), -., Utalt), and S. be unlabeled samples of size m sampled from each of the t 4+ domains respectively. Then for any å (0, for every &s E H minimizing ew (h(()) on Drr()).
we have
Σ wi (ddns(()..) 2 (0
2d log(2m) log + +
(cc(((t))
m
with probability of at least 1- 6, where 7 minn minne + +,
In the following lemma, we provide an upper bound on the difference between the true and empirical weighted errors e (h(()) and ew (h(t)).
Lemma 7. Let be a hypothesis class. For Dir(t) = U ( at time t, if the total number of samples in De (t) is N, and the ratio of sample numbers each component is X3, then for any 8 E (0, 1) and h E H, with probability of at least - 5, we have
(h(cw(((tt) & (b(t)) 2 c 2exp -2N
2=0 X
Thus, as wy deviates from Aj, the feasible approximation (M(()) with a finite number of labeled samples becomes less reliable. The proofs for both lemmas provided in Appx. R Building upon the two preceding lemmas, we proceed to derive bounds on the domain errors under the ATTA setting when minimizing the empirical weighted error using the hypothesis h at time
Lemma X bounds the difference between the weighted error e (h())) and the domain error ()()))), which is majorly influenced by the estimated Hddd-dist and the quality of discrepancy estimation. During the ATTA process, the streaming test data can form multiple domains and distributions. However, if we consider all data during the test phase as single test domain, i.e., U Una (1), we can simplify Lemma 6 to obtain an upper bound for the test error as
Iew (h(tt) en (h(tt)) wno (1 ( Sr) + +2 2d (2m) + log
+7 +x))
(14)
where minncc(<c(MM(0)) + (r(()))), and Sr is sampled from U Uia(). To understand Lamma 7 need to understand Hoeffding's Inequality, which state below Proposition for completeness.
Proposition (Hoeffding's Inequality). Let be a set, DI...., Dj be probability distributions on X, and fi....,fe be real-valued functions on X such that ft X [ai, for i 1,...,t. Then for any
e <>0
( [(x - 20) < 2exp
2f2
(15)
Σi (b: a;)4
where Elf((x)) is the expected value of f((x).
Lamma 7 provides an upper bound on the difference between the true and empirical weighted errors (h(t)) and e (h)tt). Thus, as w,, deviates from Xy, the feasible approximation (w)()) with finite number of labeled samples becomes less reliable. Building upon the two preceding lemmas, we proceed to derive bounds on the domain emrors under the ATTA setting when minimizing the empirical weighted error using the hypothesis l at time 1. Theorem Jsssentially bounds the performance of ATTA the source and each test domains. The adaptation performance test domain is majorly
24

---

Published as a conference paper at ICLR 2024
bounded by the composition of (labeled) training data, estimated distribution shift, and ideal joint hypothesis performance, which correspond to C, duax 5,), and y. respectively. The ideal joint hypothesis error 7 gauges the inherent adaptability between domains.
If we consider the multiple data distributions during the test phase as single test domain, ie., U (t), Theorem 1 can be reduced into bounds for the source domain error eg and test domain error er. With the optimal test/source hypothesis ht( arg min (h((t)) and (t) = arg minne es (h(t)),
(er(h(()) er (hi s wo +
we
+
(1 wo)3
B,
(16a)
Au
1 Ao
(ex(((()) -
ex ex 1 ( (1--wo) 1 +
Wp
2
(1 - wo)
B,
(16b)
Ao
Ao
where the distribution divergence term A duam ST) +41
2d (0g( 1og $
+ 2%, the empirical gap
m
term B = 2 (2lgg22))-log(() Sy is sampled from Ui (i). and 7 = minge x (co(h(()) + er(h(())) Our learning bounds demonstrates the trade-off between the small amount of budgeted test-time data and the large amount of less relevant source data. Next, we provide an approximation of the condition necessary to achieve optimal adaptation performance, which is calculable from finite samples and can be readily applied in practical ATTA scenarios. Following Eq. aT)a), with approximately B = ei /d/NN, the optimal value w6 to tighten the test error bound is a function of Ao and A:
2N
A
d N
w = du - V Gd - N - Ao)
for Ao 2
(17)
where is a constant. Note that Ao 2 1 प.ズ should be the satisfied condition in practical ATTA settings, where the budget is not sufficiently big while the source data amount relatively large. When the budget is sufficiently large or the source data amount is not sufficiently large compared to the distribution shift A, the optimal vn for the test error bound w = 0, i.e., using no source data since possible error reduction from the data addition is always less than the error increase caused by large divergence between the source data and the test data.
Theorem 2 offers a direct theoretical guarantee that ATTA reduces the error bound on test domains in comparison to TTA without the integration of active learning. Following Theorem
I when no active
w wn]
learning included during TTA, i.e., we = Au = 1, the upper bound A when enabling ATTA, with whp = Ao # 1, we can easily achieve an upper bound wy A + B A A B. Therefore, the incorporation of labeled test instances in ATTA theoretically enhances the overall
Aa 1- B A+
performance across test domains, substantiating the significance of the ATTA setting in addressing distribution shifts.
Entropy quantifies the amount of information contained a probability distribution. In the context of classification model. lower entropy indicates that the model assigns high probability to one of the classes, suggesting a high level of certainty or confidence in its prediction. When a model assigns low entropy to sample, this high confidence can be interpreted as the sample being well-aligned or fitting closely with the model's 's learned distribution. In other words, the model "recognizes" the sample as being similar to those it was trained on, hence the high confidence in its prediction. While entropy is not a direct measure of distributional distance, it can be used as an indicator of how closely a sample aligns with the model's learned distribution. This interpretation is more about model confidence and the implied proximity rather than strict mathematical measure of distributional distance. The pre- pre-trained model is well-trained on abundant source domain data, and thus the model distribution is approximately the source distribution. Selecting low-entropy samples using essentially provides an estimate of sampling from the source dataset. Thus, (t), based on well-aligned with the model's learned distribution is an approximation of Ds.
When we consider the CF problem and feasibly include the source-like dataset Da.s(t) into the ATTA training data in place of the inaccessible Ds in Eq. (II), we can also derive bounds on the domain errors under this practical ATTA setting when minimizing the empirical weighted error e' (N(C) using the hypothesis at time similar to Theorem [ Let H be a hypothesis class of VC-dimension d. At time step I, for ATTA data domains Da.s U.. (1), (2, ... Une(C), , S, are unlabeled samples of size sampled from each of the t + 1 domains respectively. The total number of samples in Der (t) is
25

---

Published as a conference paper at ICLR 2024
N and the ratio of sample numbers in each component is A.. If h(t) E H. minimizes the empirical weighted error (h(()) with the weight vector on Di-(!), and hī (4) arg minner cy({(()) is the optimal hypothesis on the jth domain, then for any E (0, 1), we have
2d (2g( + log 2
(,((tt)) & (l))(()) -
Σ
+1
+ +
+ +CC
m
v (Ei (log(2N) (lgg(()) 2N
with probability of at least 1 8, where C
and 7
also apply for this practical ATTA setting. Further empirical validations for our theoretical results are provided in Appx. H
( Other derived results following Theorem |
E PROOFS
This section presents comprehensive proofs for all the lemmas, theorems, and corollaries mentioned in this paper, along with the derivation of key intermediate results.
Lemma 6. Let H be a hypothesis space of VC-dimension d. At time step i, let the ATTA data domains be Ds, Use (1), Ut.(2).... .U.u)) (t), and S, be unlabeled samples of size m sampled from each of the t + 1 domains respectively. Then for any 5 (0, 1), for every h E H minimizing Ew (h(t)) on D.r(
we have
Σ wi ( + 2V (m0,89h
2d l0g0mm2) log
((((((()))(((())))
+ 78
with probability of at least 1 6, where nye (einee (,((t)))
Proof. First we prove that given unlabeled samples of size m Si, S2 sampled from two distributions Di and D2, have
2d (og( + log }
duAn(Di, D2) s dHan((S) V
(18)
We start with Theorem 3.4 of Kifer al. (2004):
Pmg ( S2) (P Pa)1 > c) s (2m)de-miee
(
(19)
In Eq. 19 'd' is the VC-dimension of a collection of subsets of some domain measure space A, while in our case, df the VC-dimension of hypothesis space H. Following (Ben- David al., 2010), the HAH space is the set of disagreements between every two hypotheses in H. which can be represented as linear threshold network of depth with hidden units. Therefore, the VC-dimension of HAH H most twice the VC-dimension of H, and the VC-dimension of our domain measure space is 2d for Eq. 19 hold.
Given 5 (0, 1), we set the upper bound of the inequality to 6, and solve for
(2m)2de 2d
(0m))))-mm1//11 -m1e2/16
(2m) 2d aade-mm mmg 8/16
We rewrite the inequality as
m + -m222/18
(2m)2d
taking the logarithm of both sides, we get
2
log (2m)as = m3
+ log(1 + (my (ma m82)
16
26

---

Published as a conference paper at ICLR 2024
Assuming mi = me = m and defining a 16. we have
log (2m)ad = ma + log 2;
rearranging the equation, we then get
ma + log(5/2) 2d (2m))
Now, we can solve for at
2d lmgmmm) log
Recall that a 1g so we get:
= 4yā
2d 2dlog(2m) log
6 4=4/
With probability of at least 6, we have
2d 2dgom(2 + log
16a(S1, Sa) oe, s s
m
therefore,
2d log (2g) + log 3
duaN((D,, D2) S (s, + +1
(20)
Now we prove Lemma We use the triangle inequality for classification error in the derivation. For the domain error of hypothesis time on the jth domain ()(h()), given the definition of (hc))).
sww (h(1) - cx((())) = Σ wse wsee(h(1)) (h(t)) - (h(())
(v(t()((t)) - (h(t))
(x(la(((() ((hh()) (0) +=(00) ((((0)
(s(1()) (((())))
(v(eL(h + (((b(0)
Σ wi(w + (e(()(), (Z) (Z))).)
where 7 (c((b(tt, (((())
By the definition of HiHddistancce and our proved Eq. 20
sup (e:(h(t), k(())) cs(h(t),
K,KEH
PAND, [h(x) * N (-)) + PE-D, [l(x)) # [x))
2 (d.
2d l0g(m2) + log 2
< { dnan (St, S3) + S))++
m
27

---

Published as a conference paper at ICLR 2024
where D., D, denote the ith and jth domain. Therefore,
New (b((t) ()((tt))
Σ wi + -
Σ 1=0
wi + (d)))(Dr,P;))
(2m) log $ Σ wi + (,))
S.)+
m
Since es(h(t)) - e)(h(t)) when derive
Σ (dd +2
2d 20gg(2)
log 4
(enn()(t) - cg((tt)
(0,,
with probability of at least 1 6, where x minn +
This completes the proof.
Lemma 7. Let H be a hypothesis class. For Der(t) = Ds D Die(t)) at time t, if the total number of samples in Der(t) N, and the ratio of sample rumbers each component is Xj, then for any d E (0, 1) and & H, with probability of at least 8, we have
(b(()) en (h(1)) 2 c 2xxp
2N
Proof. We apply Hoeffding's Incquality in our proof:
P Σ ((x))
Σ E.w [i(())] 20)
exp
2
(21)
E aa)=
1=1
In the jth domain, there are N, samples. With the true labeling function g(æ), for each of the N, samples æ, let there be real-valued function f((x)
f((z) - X, M(x, 9(x)),
where fi(x)) (0, N1). Incorporating all the domains, we get
= Σ Ay
Ew (h((t) my (h(())(())
Σ A,N
f((x),
N
which corresponds to the El= fi(z) part in Hoeffding's Inequality.
Due to the linearity of expectations, calculate the sum of expectations as
N Σ
Ny (h(t)) Σ (h(e((((t) = ew (h(t)),
Bff(x))
which corresponds the 1 Dim Ez~D, [x(()] part in Hoeffding's Inequality. Therefore, can apply Hoeffding's s Inequality as
Plle - ew (h(t)) 2 < 2exp
-2N 2
range (f((z)))
= 2exp
2N 2
Ay w2) X,
2 2exp
-2Ne /
2,y
1=0
This completes the proof.
28

---

Published as a conference paper at ICLR 2024
Theorem 1. Let H be a hypothesis class of VC-dimension At time step I, for ATTA data domains Ds, Ur, (.,((), St are unlabeled samples of size sampled from each of the t + 1 domains respectively. The total number of samples in (1.(1) is N and the ratio of sample numbers in each component X, hft) H minimizes the empirical weighted error éw (h((t) with the weight vector w on Der and (f) = arg argminge e, (b((t)) is the optimal hypothesis on the jth domain, then for any E (0, 1), with probability of at least 6, we have
c,(((1) S (c)()(()) +2
E wi
1 dHA) + 2/
2d (2m) log
+ t,2 2C,
m
i=0,is)
and ? minseH (c((h(() + (x(()))) For future test domains j = 1 (k > 0), assuming k' = aeg duan Ute + k)) and min dnan (D(K),Uaol + k)) S 8D. where 0 6n & to0, then Vo, with probability of at least 6, we have
where C -1
/ (Ei= xi d (log(22))ooo(() 2N
(dnax(St, Sw) + +
2d (2m) + log 2
(+(x(h(t)) S (
Σ we
+5D + 2% 2C.
m
Proof. First we prove that for any E (0, 1) and H, with probability least 1 we have
Few (h(()) & (h((t))
Σ
un? A;
d log(d)
(22)
2N
We apply Theorem 3.2 of Kifer et al. (2004) and Lemma 7,
(l())))((t)))))>)))))))))))))))) en (h(()) 2 <) & (2N) exp
2Ne
Given 8 (0, 1). set the upper bound of the inequality to 6, and solve for
-2Ne E X3- )
8 (2NN exp
1=0
We rewrite the inequality as
6 2Ne -2Ne/1EE) (2N)² e
taking the logarithm of both sides, we get
log (2NY²
-2N
Rearranging the equation, we then get
w3 dllo((2N) -log8))
X,
2N
Therefore, with probability of at least have
New (f((t) - & (h((t)) S
Σ
wi²
( (dlog(2N) log(1)
(23)
A,
2N
29

---

Published as a conference paper at ICLR 2024
Based on Eq. 23 we now prove Theorem For the empirical domain error of hypothesis lt at time I on the jth domain cy(l(()), applying Lemma 6, Eq. 23 and the definition of (1), get
s,h(tt) S 60 (b(t))
Σ wi i=0,.
2 dS S3) + 22
2d log
7/
m
Σ wa
[dlog(2N) - log(())
I (
d,
2N
2d 2dlmm(2m) + log 2
Σ
2dnan(Si 2
+ 74
[0,,
2
m
Σ w²
d (2o) log(o)
(1)((())))+++++ +
d
2N
(mm
2d 2d1og(2m) + log $
S,) 21
+ +%
m
i=0,
S (l)()))))) +2
Σ
dllog(2N) log(6)
d
2.V
2d 2d log
ddnan(Ss Sz) +2
we
m
Σ wf
(loog(2N) log(d)
S {)(1(()))+ -2
d
2N
(d. + +2 2d + log 3
+2 Σ
2
+
(=0,1
Σ (dnan((...)) +2 +2
2d 2dlog(2m) + log + %
(t)((t)) +2
+ 2C
t=0,1%
with probability of at least - 5, where C v
wf (E
Σ1
Ei-
dlog(2N))
and %
A,
2N
+
For future test domains argmingr dHaH (D((() Uta(t++
t &o where & O. we have the assumption that k' +k)( k)) and min dHax (ta(t (t++)) s 8p. Here, slightly abuse the notation D(K') to represent D. if k and (k) if > O. Then we get
2dlog((mm) + log
<++* (h(t)) S (h(t)) +
Σ
2 dns S.tk) + 22
7
1m0
A (cm(((())) +
wi
2 (dnaH Se) + dHAN(SK, St+x)) + 2
2d log(2m) + log 3
+
1 (HA Sw) + jōn + 2/
2d 2dlog(2m) + log ?
S (c((t()))) + Σ wi
+ 78
m
(dlog(2N) - log(E)
< (c((t(())) +
Σ
de
2N
Σ wi
(dnaa(Si Sx) 0000 + 21
2d log(m)) log + 7
T=0
30

---

Published as a conference paper at ICLR 2024
wp X
d - log(d)
S Ew (hi++e)())) +
2NV
Σ 2m0
Ed + 2200 + 21
2d 20l0g(2m) log + 9/
c w Σ i=0
( (log(2N) - -l)g(5)
S cv (1)+++()) 1
d.
2.V
1
2d + log 76
Σ
2zd + +21
1=0
$ (e++ahi+stt)) +2
Σ
wp
ddlog(2N) log(d)
2NV
(dma + 80 + -1
2d 2dlog(2m)
log
+ 2 +
wi
+ 7/
m
=c4+)((44(()) + Σ ws (s, + VV
2d (2m) log
+ ön + 276
+ 2C.
1=0
m
with probability of at least 1 - 6, where C' = v (EiL m
(2lop(2N) -
),
minnen minnee((e(((())) +
2N
cx+* (k(1)), and 0 S on << +00.
This completes the proof.
Theorem 2. Let H. be hypothesis class of VC-dimension d For ATTA data domains Ds, Uto (1),
Uia(2). Une(t), (t), considering the test-time data as a single test domain Uiz1 Ute()), if h(t) E H minimizes the empirical weighted error &w (h(t)) with the weight vector w on (t,(t), let the lest error be upper-bounded with ler (h(()) (b) S. FBr(w, X, N,t). Let w and X be the weight and sample ratio vectors when no active learning included, ie.. w' and X' s.t. wh w! X ffr i 1, then for any X * X. there exists s.t.
1 and
EBr (w, A,N,A,NN,)) EBr(w N,N.
(24)
Proof. From Theorem [ we can derive the bound for the test error where the test-time data are considered as single test domain:
(er()(()) er & (Br
log(m) + log 2 5 22)
wolddan (So, ST) + +4V
m
w
(1 - wo)
d log(2N) log(o)
2
Ao
1 Ao
2NV
and we simplify the above equation as
(1 wo)
(er(f(())) ex wor +
B.
(25)
where the distribution divergence term A drax ST) +
2d logg +og 2%, the empirical gap
term 2
(oggg2)) Sy sampled from Ui= U.. (i) and 7 = min (innex((o(h(()))) (r(l())))))))))))))))))
2N
Since we have
(1
w2
(wo- 22)2 V Ao(1 Xa)
+
+ 2 1,
(26)
Au
1 An
31

---

Published as a conference paper at ICLR 2024
where Formula 26 obtains the minimum value if and only wh = Au; when enabling ATTA with any An 1, get
w
(1- w Ao 1 A
BBT A, N, woA +
B wo ++ + B,
(27)
where the minimum value EBy (w, X, N,t)mmn = Ao + B can be obtained with condition wp Ao o When no active learning is included, i.e., for weight and sample ratio vectors w' and X
w/b = X = and w X 0 for i 2 we have
EBr(W X N.I) woA
W X
(1- (1-w))
(28)
%
Since for (Br(w, X, N, min wn + wg
and
A, B > hold, derive
EBr(w, A. N, wn B < A + B EBr(w N,
(29)
This completes the proof.
Corollary 3. At time step t, for ATTA data domains (t,s(t),uud (2e Une (t), S. are unla- beled samples of size sampled from each of the t + domains respectively, and Ss unlabeled samples of size m sampled from Ds. if()) H. minimizes &w (h(t)) while other conditions remain identical to Theorem then
Σ wi (dnau((). + +4V u
2d (0 log
<s(h(()) & <s(hh(())
27 + 2C,
with probability at least
6, where follows Theorem 7 Aand 7; (e: es (t)))
Proof. For the empirical source error on De of hypothesis h at time t, similar to Theorem 1 we apply
Lemma 6 Eq. 23 to get
( [dnan((.. Ss) 21
2d log(mm)) + log a + 73 dloo((2N) log(d)
cs(h(()) & c (f(())
wi
m7
wp Σ
((x(1(())) +
A
2N
2d 2d + log 2
Σ wx ==0
(s.. + +21
78
up? Σ
(
(dlog(2N) log(d)
$ (b)((t))
A
2N
1=0
(duas(((, +
2d (2m) + log
1=0
of Σ
( (dlog(2N) log(5)
S (hg((t))) +2
X
2N
2d log(mmm) + log
Σ ux
(d Ss) +2
2
m
Σ
' wit
(dlog(2N) log(()
< <es(hs(t))+ +2
X
2N
+ Σ wi
(duan(Ss, 8s) +
2d log (2m) + log 76
2
1=0
32

---

Published as a conference paper at ICLR 2024
=s(h((t)) + Σ wi dnan((S, vV
2dlog(2m) log 2
+ 2%ss
+ 2C
i=0
m
with probability of at least 6, where C
oi (Eimo 2,
(1og(22))lozxt)
and 7
minneH (((h)))((((()))))))))))))))))))) ccs(())))))))))))) This completes the proof.
Corollary Al time step t, for ATTA data domains (s.s(t), (.ss(t)),,(()) Use 2 Ute(t), suppose that
h(t) e H minimizes èw (h(t)) under identical conditions to Theorem 2 Let's denote the source ervor upper bound with les(h(()) es (e))(())) & EBs(w: (w. X, N.I). Let w' and be the weight and sample ratio vectors when (t)s(1) is not included, ie.. w' and X s.t. w/ No 0. If dDs,((ss (o,s(t)) < CRnAn(Ds, Ui=1 Ut)(i)), then for any X + X, there exists w S.I.
EBs(w, N,N, < EBs(w', N,N.).
(30)
Proof. From Theorem considering the test-time data as a single test domain, we can derive the bound for the source error Ds:
(cs()(()) (O)) EBs(W,,,N,D
2d log (2m) + log 3
-mo(dHAR(SO,SS) + +4V
27)
m
2d + log 7 + +272)
+ (1 - wo wo)(dHH((Ss. ST) +1
m
w
(1-wa w2
(2.o log(d)
+
+//
1
2N
where S7 is sampled from U!_1 Use (t) minae (eo(t)))) and minsen (er(())
(b(()))) We have
W
wo)2
(wo )o)2 Aa(1 Ao)
1,
(31)
Aa
1
An
V
where the equality and the minimum value are obtained if and only if ww = Ao
When (t) is included, i.e., with the weight and sample ratio vectors w' and X' s.t. w/
using the empirical gap term dlog(2N) we have
2/
2d (dlog(2m) + log 2
w
(1 wo)
EBs(w', N,t) = dsan(Ss, + +4V
+ +
B
m
Ao
1 Ao
2d 20 + log
= Sr) +
+ + B.
When (t,s(t) is included with Ao + 0,
lolog(2m) - log m + +2y
EBs(w, A, A. (d + 1V
2d + log 3
+ (1 wo (dra + +
+ 2
m
w - (1-wn)
Ao
1 Ao
2d log (2m) - loog 2y)
wo wo Ss) + +11/
2d 2mmm + log ? +2y' + B,
- (dd=))dnnaH(Ss.S +
33

---

Published as a conference paper at ICLR 2024
Algorithm 2 INCREMENTAL CLUSTERING (IC)
Require: Given previously selected anchors, new unlabeled samples, and the cluster budget as Dane. Unews and NC. Global anchor weights wite (wi ..... wit (inel 1: For simplicity, we consider anchor weights w as global vector.
2: function aDCs Unew .CC)
Assign all new samples with weight 1. 4: + Extract the features from the penultimate layer of model f on a e Dane Unew order.
3: w <- Concat(w"" .
5: clusters + ---eeteed---Mea(((ee w NC)
6: new [ww_cluserrsssse &- {cluster, Veluster, E clusters, Var E Dme; x & clusters,)
7:
Xnew anchors +- {the closest sample to the centroid of cluster, Veluster, new cew_clusters] Kanchars c- far E Dane) U U. Nnew_aacchos
8:
9:
ane Concat(w" "t [XIxennastnnnl
Initialize new anchor weights.
# sample of cluster,
10: for anc E (w"h w. <- wit +
# anchor cluster, _.:" с cluster, b Weight accumulation.
11: Return Xanetsces
12:
end function
where the minimum value can be obtained with condition wi Ao *
In practical learning scenarios, we generally assume adaptation tasks are solvable; therefore, there should be a prediction function that performs well on two distinct domains. this case, and y duau((s, Sr), then we
should be relatively small, so we can assume y as y/. If dSa Ss) have
2d log(2m) + log 2
(Bs(w, N,N,0mss (So. + 11
+ 27)
m
2d log (2m) + log
+ (1= +41
+ +27)) +
m
2dlog(2m) + log 2
< Sr) + +41
+ 27 +
m
EBs(w N,N.
Therefore, we derive
(B, X, N. min < FBB(ww, X, N.
(32)
This completes the proof.
F INCREMENTAL CLUSTERING
F.1 ALGORITHM DETAILS
We provide the detailed algorithm for incremental clustering as Alg.
F.2 VISUALIZATION
To better illustrate the incremental clustering algorithm, provide visualization results on PACS to demonstrate the process. As shown in Fig. the initial step of IC is a normal K-Means clustering step, and ten anchors denoted as "X" are selected. The weights all samples in a clusters is aggregated into the corresponding anchor's weight. Therefore, these ten samples (anchors) are given larger sizes visually (i.e., larger weights) than that of other new test samples in the first IC step (Fig. 4 During the first IC step, several distributions are far away from the existed anchors and form clusters 1,7,9 and 10, which leads to 4 new selected anchors. While the number of cluster centroid is only increased by 1, 4 of the existing anchors are clustered into the same cluster 8 (purple). Thus IC produces 4 new anchors instead of 1. Similarly, in the second IC step (Fig. 5). the new streaming in test samples introduce new distribution; IC produces new clusters (4, and 11) and the corresponding number of anchors to cover them. The number of centroid is only increased by I, which implies that there are two wriginal-cuuser--eeree events. More IC step visualization results provided in Fig. b
34

---

Published as a conference paper at ICLR 2024
Clsters VEAMSOOE A1
Cisster visu31 botion with new selected prichor
20
-30
Figure 3: Initial IC step: normal clustering, Left: Clustering results. Right: Selecting new anchors.
Clustars
Caasbers visual nation with selected anchor
22
Hight
-32
PCL
Figure 4: The first IC step. Left: Weighted clustering results, Right: Selecting new anchors.
22
0
-12
Figure 5: The second IC step. Left: Weighted clustering results. Right: Selecting new anchors.
35

---

Published as a conference paper at ICLR 2024
Carders cloust Dation enlected
Irder
-10
ICL
Figure 6: The third IC step. Left: Weighted clustering results. Right: Selecting new anchors.
Dlader
-39
Figure 7: The fourth IC step. Left: Weighted clustering results. Right: Selecting anchors.
36

---

Published as a conference paper at ICLR 2024
G EXPERIMENT DETAILS
In this section, we provide more experimental details including the details of the datasets and training settings.
G.1 DETAILS ABOUT THE DATASETS
We adopt datasets PACS, VLCS, and Office-Home from DomainBed (Gulrajani and Lopez-Paz 2020) with the same domain splits, All available licenses are mentioned below.
PACS (Li al. 2017 includes four domains: art, cartoons, photos, and sketches. PACS is 7-class classification dataset with 9,991 images of dimension (3, 224, 224).
VLCS (Fang al. 2013) contains photographic domains: Caltech101. 101, LabelMe, SUN09, and VOC2007. This dataset includes 10,729 images of dimension (3, 224, 224) with classes.
Office-Home (Venkateswara et al., 2017) is 65-class dataset, including domains: art, clipart, product, and real. VLCS includes 10,729 images of dimension (3, 224, 244). (License)
MmnyyemageNet-C is 200-class dataset, including 15 corrupt types. Tiny- Liny-ImageNet-C includes 150,000 images of dimension (3, 224, 244). Since the class number 200 is less than ImageNet (1000), the model's last layer classifier needs to adapted. In this work, we use the brightness corruption domain to adapt.
In the source pretraining phase, we adopt the most ImageNet-like domain as our source domain. For PACS and Office-Homes we use domains "photos" and "real" as the source domains, respectively, while for VLCS, Caltech101 is assigned apply the source pretraining. We freeze the random seeds to generate the sample indices order for the two test data streams, namely, the domain-wise data stream and the random data stream.
For PACS, the domain-wise data stream inputs samples from domain art, cartoons, to sketches, while we shuffle all samples from these three domains in the random data stream. For VLCSS, we stream the domains in the order: LabelMe, SUN09, and VOC2007, the domain-wise data stream. For Office-Home, the domain -iise data stream order becomes art, clipart, and product.
G.2 TRAINING AND OPTIMIZATION SETTINGS
In this section, we extensively discuss the model architectures, optimization settings, and method settings.
G.2.1 ARCHITECTURES
PACS & VLCS. We adopt ResNet-18 as our model encoder followed by linear classifier. The initial parameters of ResNet-18 18 are ImageNet pre-trained weights. In our experiment, we remove the Dropout layer since we empirically found that using the Dropout layer might degrade the optimization process when the sample number is small. The specific implementation of the network is closely aligned with the implementation in DomainBed (Gulrajani and Lopez-Paz) 2020).
We employ ResNet-50 our model encoder for Office-Home. Except for the architecture, the other model settings are aligned with ResNet-18.
Office-Home.
Fin-lmmaeNNe-eG 18 is adapted from ImageNet to Image by training the last linear layer.
G.2.2 TRAINING & OPTIMIZATION
In this section, we describe the training configurations for both the source domain pre-training and test-time adaptation procedures.
Source domain pre-training, For the PACS and VLCS datasets, models are fine-tuned on the selected source domains for 3,000 iterations. The Adam optimizer is utilized with learning rate
37

---

Published as a conference paper at ICLR 2024
of 10 4 In contrast, for the Office- Home dataset, the model is fine-tuned for a longer duration of 10,000 iterations with slightly adjusted learning rate of x 10
Test-time adaptation. For test-time adaptation across PACS and VLCS, the pre-trained source model is further fine-tuned using the SGD optimizer with a learning rate of 10-3 While on Office-Home and Tiny--mageNNe-CC a learning rate 10-4 is adopted. For all TTA baselines, barring specific exceptions, faithfully adhere to the original implementation settings. A noteworthy exception is the EATA method, which requires a cosine similarity threshold. The default threshold of the original EATA implementation was suitable for the three datasets used in our study, necessitating an adjustment. We empirically set this threshold to 0.5 for training. Unlike Tent and SAR, which only require the optimization of batch normalization layers (Santurkar et al., 2018), SimATTA allows the training of all parameters in the networks. In experiments, we use tolerance count (tol) to control the training process. SimATTA will stop updating once the loss does not descrease for more than steps. However, for Finy-ImageNet-CC SimATTA uses 'steps=10" for time comparisons since other methods apply at most 10 steps.
G.2.3 METHOD SETTINGS
Tent. In our experiments, we apply the official implementation of Ten Specifically, we evaluate Tent with 1 test-time training step and 10 steps, respectively.
EATA. Our EATA implementation follows its official code") In our experiments, EATA has 2000 fisher training samples, Es 0.4 log(# class), < 0.5.
COTTA. For CoTTA, we strictly follow all the code and settings from its official implementatior?
SAR. With SAR's official implementationf) set Eg 0.4 x log(# class) and co 0.1 in experiments.
ADA baselines. For ADA baselines, we follow the architecture of the official implementation of CLUE (Prabhu et al. 2021
SimATTA Implementation. Our implementation largely involves straightforward hyperparameter settings. The higher entropy bound ед = 10 should exceed the lower entropy bound es. but equal values are acceptable. Empirically, the lower entropy bound can be set to 10-3 for VLCS and Office-Home, or 10 for PACS. The choice of is largely dependent on the number of source-like samples obtained. lower et may yield higher-accuracy low-entropy samples, but this could lead to unstable training due to sample scarcity.
Though experimentation with different hyperparameters is encouraged, our findings suggest that maintaining a non-trivial number of low-entropy samples and setting an appropriate Ao are of primary importance. If An < 0.5, CF may ensue, which may negate any potential improvement.
Regarding the management of budgets, numerous strategies can be adopted. In our experiments, we utilized a simple hyperparameter k varying from to 3, to regulate the increasing rate of budget consumption. This strategy is fairly elementary and can be substituted by any adaptive techniques.
G.3 SOFTWARE AND HARDWARE
We conduct our experiments with PyTorch (Paszke et al. 2019) and scikit-learn (Pedregosa et al. 2011) on Ubuntu 20.04. The Ubuntu server includes 112 Intel(R) Xeon(R) Gold 6258R CPU @2.70GHz, 1.47TB memory, and NVIDIA A A100 80GB PCIe graphics cards. The training process costs graphics memory less than 10GB, and it requires CPU computational resources for seikit-learn K-Means clustering calculations. Our implementation also includes a GPU-based PyTorch K- K-Means method for transferring calculation loads from CPUs to GPUs. However, for consistency, the results of our experiments obtained with the original scikit-learn K-Means implementation.
https://tthhbccmm//euuaaaaaaaaa
huts::/github http://hhhhh.ooo////nnne//////tt
https://gthub.comm. http://mmmrggglll/SSSRRRR
38

---

Published as a conference paper at ICLR 2024
Wo = λy
Loss minimum for each λo
1.0
1.0
0.9
0.9
0.8
0.8
0.7
0.6
0.6
0.5
0.5
0.4
0.95
0.95
0.90
0.90
7 0.85
7 0.85
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.75
0.2
Wo
0.75
0.2
Wo
0.0
Figure 8: Target loss surface on 2000 samples without source pre-training. The red points denote the loss minimum for fixed λg The orange line denote the place where Ag-
Wp = λy
Loss minimum for each λo
1.0
1.0
0.9
0.8
0.8
0.7
0.7
0.6
0.6
0.5
1.00
1.00
0.95
0.95
0.90
0.90
0.85
0.85 0.85
0.80
0.75
0.0
0.2
0.4
Wo
0.6
0.8
1.0
0.80
0.0
0.2
0.4
Wo
0.6
0.8
1.0
Figure 9: Target loss surface on 2000 samples with source pre-training.
H EMPIRICAL VALIDATIONS FOR THEORETICAL ANALYSIS
In this section, undertake empirical validation of our learning theory, which encompasses multiple facets awaiting verification. In contemporary computer vision fields, pre-trained models play pivotal role, and performance would significantly decline without the use of pre-trained features. The learning theory suggests that given the vast VC-dimension of complete ResNets, without substantial data samples, the training error cannot be theoretically tight-bounded. However, we show empirically in the following experiments that fine-tuning pre-trained models is behaviorally akin to training model with low VC-dimension.
Training on 2000 Samples Without Source Domain Pre-training, For an ImageNet pre-trained ResNet-18 model, we trained using 2000 samples from the PACS dataset. To ascertain the optimal value wp in Equation 4 we trained multiple models for different and λu pairings. For each pair, we derived the target domain loss (from art, cartoons, and sketches) post- post-traiinng and plotted this loss on the z-axis. With wn and An serving the xy-axes, Figure X As the results show, given Ao. the optimal wy typically aligns with the line A = wo, with slight downward shift, which aligns with Equation 4
drafted the target domain loss er surface in
39

---

Published as a conference paper at ICLR 2024
λo
Loss minimum for each λo
0.9
0.9
0.8
0.8
0.7
0.7
0.6
0.6
1.0
1.0
0.8
0.6
0
0.4
7 0.4
0.2
0.4
0.6
0.2
0.4
0.6
0.0
0.2
Wo
0.0
0.2
Wo
Figure 10: Target loss surface on 500 samples with source pre-training.
Wp = λ
Loss minimum for each λo
1.
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.0
0.0
0.2
0.2
0.4
0.6
7
0.6
0.2
0.8
0.4
0.8
0.4
0.6
1.0
Wo
1.0
Wo
Figure 11: Source loss surface on 500 samples with source pre-training.
40

---

Published as a conference paper at ICLR 2024
Wo = λy
Loss minimum for each λo
4.0
4.0
Global minimum
3.5
3.0
2.5
2.5
2.0
1.5
1.5
10
1.0
0.8
0.8
0.6
0
0.4
1.0
3 0.4
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.0
Wo
0.0
Wo
0.0
Figure 12: Target and source loss surface on 500 samples with source pre-training.
Table 6: TTA comparisons
Office-Home, This table includes the data stream settings mentioned in the dataset setup and reports performances in accuracy. Results that outperform all TTA baselines highlighted in bold font. N/A denotes the adaptations are not applied on the source domain.
Office Home
Domain data
Post adaptazion
Random
Post adaptation
adapt
adapt
92.38
50.88
63.53
Tent (stepe1]
N/A
49.61
39.31
63.87
92.47
49.57
39.89
63.89
49.95
50.27
50.23
$2.06
92.40
49.24
50.68
63.08
Tent (step==10)
N/A
19.61
39.04
61.41
87.08
44.79
38.37
60.49
$0.05
49.31
48.74
47.79
R5.31
42.85
37.89
S8.71
EATA
N/A
49.65
39.04
63.53
91,60
49.61
38.65
63.48
49.73
50.27
49 45
$1.07
91.05
49.11
38 38.26
62.99
CaTTA
NIA
.9.61
38.76
61.84
87.81
46,95
59.04
49.84
50.43
86.99
43.68
34.73
$7.56
(steps=1)
SAR (stepo-10)
38.81
61.50
98.94
59.41
SimATTA 3000
N/A
56.20
48.38
71.66
95.75
60.07
$2.62
74.70
58.57
60.88
62.91
63.67
62,01
$4.95
74.70
SimATTA (8 2000
NIA
58.71
51.11
74.36
96.03
62.05
57.41
76.98
S8.85
62.63
63.41
64.31
95.91
63.78
57.87
77.09
Training on 2000 Samples with Source Domain Pre-training. To further assess the effects of
source pre-traines ResNet-18. 18. The results are depicted in Figure 9 This experiment provides empirical guidance on selecting we source domain pre-trained situations. The findings suggest that the optimal wi non-trivially shifts away from the line Au = towards lower-value regions. Considering the source pre-training process as using greater quantity of source domain samples, implies that when the number of source samples greatly exceeds target samples, a lower can enhance target domain results.
source pre-training, we repeated the same experiment
Training on 500 Samples with Source Domain Pre-training. We proceed fine-tune the source domain pre-trained 18 using only 500 samples, thereby simulating active TTA settings. We train models with various un and Ao pairings, then graph the target domain losses, source domain losses, and the combined losses. As shown in Figure [0] the target losses still comply with our theoretical deductions where the local minima are close to the line λo = wo and marginally shift towards lower values. Considering the challenge of CF, the source domain results in Figure [] suggest reverse trend compared to the target domain, where lower Ag and we values yield superior target domain results but inferior source domain results. Thus, curb CF, the primary strategy is to maintain a relatively higher Ag. When considering both target and source domains, a balance emerges depicted in Figure 12 The global minimum is located in the middle region, demonstrating the trade-off between the target domain and source domain performance.
I ADDITIONAL EXPERIMENT RESULTS
In this section, we provide additional experiment results. The Office-Home results and ablation studies will be presented in similar way the main paper. In the full results Sec. [.3 will post more detailed experimental results with specific budget numbers and intermediate performance during the test-time adaptation.
41

---

Published as a conference paper at ICLR 2024
Table Comparisons to ADA baselines on Office-Home. The souree domain is denoted as "(S)"
in the table. Results are average accuracies with standard deviations).
Pffice-Home
R (S)
A
C
P
Random (B 300)
95.04 (0.20)
57.54 (1.16)
53.43 (1.17)
73.46 (0.97)
Entropy (B 300)
94.39 (0.49)
61.21 (0.71)
56.53 (0.71)
72.31 (0.28)
Kmeans (B 300)
95.09 (0.14)
57.37 (0.90)
71.81 (0.39)
CLUE (B 300)
95.20 (0.23)
60.18 (0.98)
58.05 (0.43)
73.72 (0.70)
Ours (B < 300)
95.82 (0.07)
61.04 (0.97)
53.80 (1.18)
74.70 (0.00)
I.1 RESULTS ON OFFICE-HOmE
We conduct experiments Office- Hiice-Homeeee and get the test-time performances and post-adaptation performances for two data streams. As shown in Tab. SimATTA can outperform all TTA baselines with huge margins. Compared ADA baselines under the source-free settings, shown in Tab, 7 SimATTA obtains comparable results.
I.2
ABLATION STUDIES
PACS Domain-wise Stream
VLCS Domain-wise Stream
70
Mean Accuracy
Mean Accuracy
60
60
55
50
LE=0, IC=0
LE=0, IC=0
40
LE-0, IC-1
LE-0, IC-1
LE-1, IC-0
LE-1, IC-0
LE=1, IC=1
LE=1, IC=1
100
200
300
400
500
100
200
300
400
500
600
700
800
Budget
Budget
PACS Random Stream
VLCS Random Stream
80
70
75
Mean Accuracy
Mean Accuracy
80
70
65
LE=0, IC=0
LE=0, IC=0
LE-0, IC+1
50
LE-0, IC-1
60
LE=1, IC=0
LE=1, IC=0
LE=1,
LE=1, IC=1
100
200
300
400
500
600
100
200
300
400
500
600
700
Budget
Budget
Figure 13: Ablation study PACS and VLCS. "IC=0" denotes removing incremental clustering (IC) selection. "LE=0" denotes removing the low-entropy (LE) sample training. Domain-wiss stream and random stream are applied on first and second rows, respectively. The accuracy values averaged across all splits/domains.
In this section, we explore three variations of our method to examine the individual impacts of its components. The first variant replaces the incremental clustering selection with entropy selection,
42

---

Published as a conference paper at ICLR 2024
where only the samples with the highest entropy are chosen. The second variant eliminates low- entropy sample training. The third variation combines the first and second variants. We perform this ablation study on the PACS and VLCS as outlined Fig. 13 We denote the use of incremental clustering (IC) and low-entropy training (LEE) respectively IC=1 and LF=1.
The experiments essentially reveals the effectiveness of incremental clustering and low-entropy- sample training. As we have detailed in 3.2 these techniques are designed to to select informative samples, increase distribution coverage, and mitigate catastrophic forgetting. These designs appositely serve the ATTA setting where the oracle has costs and the budget is limited. Therefore, their effectiveness is prominent particularly when the budget is small. As the results show, when the budget S 100 or B < 300, removing the components observably impairs performances. When B gets large. more active samples cover larger distribution; thus the performance gap from random selection and informative selection gets smaller. the extreme case where B - no, all samples are selected and thus the superiority of our meticulously-designee techniques are not manifested.
Specifically, our analysis yields several insights. First, SimATTA (LE=1, IC=1) comprehensively outperforms other variants on both datasets, different streams, and different budgets. Second, variants without low-entropy training (LE=0, IC=0/1) easily fail to produce stable results (e.g., domain-wise stream in VLCS). Third, SimATTA's performance surpasses this variant on PACS's 's domain-wise stream clearly especially when the budgets are low. This indicates these variants fail to retrieve the most informative style shift (PACS's s shifts) samples, which implies the advantage of incremental clustering when the budget is tight.
In addition, these results show that IC has its unique advantage domain-wise streams where distributions change abruptly instead of random streams. Therefore, compared to PACS's domain- wise stream results, the reason for the smaller performance improvement of SimATTA over the variant (LE=1, IC=0) on VLCS's domain foomann-wise stream is that images in VLCS are all photos that do not include those severe style shifts PACS (i.e., art, cartoons, and sketches). That is, when the shift is not severe, we don't 't need IC to cover very different distributions, and selecting samples using entropy can produce good results. brief, IC is extraordinary for severe distribution shifts and quick adaptation.
is worth mentioning that low budget comparison is essential to show the informative sample retrieval ability, since as the budget increases, all AL techniques will tend to perform closely.
1.3 COMPLETE EXPERIMENT RESULTS
We provide complete experimental results in this section. As shown in Tab. we present the full results for two data streams. The test-time adaptation accuracies shown in the "Current domain" row, while the "Budgets" row denotes the used budget by the end of the domain. The rest four rows denote the four domain results by the end of the real-time adaptation of the current domain, where the first column results are the test accuracy before the test-time adaptation phase. N/A represents "do not apply".
Table 8: Tent (steps=1) PACS.
Domain wise data stream
Random data stream
Tent (steps=1)
P
A
CC+
S
1-
+2-
++3
-4
Current domain
N/A
67.29
64.59
44.67
56.35
54.09
51.83
48.58
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
99.70
98.68
98.38
97.60
98.56
98.08
97.72
97.19
A
59.38
69.09
68.95
66.85
68.07
67.33
65.58
63.53
28.03
64.04
65.19
64.08
64.85
65.19
62.97
60.75
S
42.91
53.65
47.39
42.58
54.57
49.83
44.13
41.56
J CHALLENGES AND PERSPECTIVES
Despite advancements, test-time adaptation continues pose considerable challenges. As previously discussed, without supplementary information and assumptions, the ability to guarantee model generalization capabilities is limited. However, this is not unexpected given that recent progress
43

---

Published as a conference paper at ICLR 2024
Table Tent (steps=10) on PACS.
Domain-wird wise data stream
Random data stream
Tent (steps=10)
P
+
C
S
1 1-
-22
-+3
-
Current domain
N/A
67.38
57.85
20.23
47.36
31.01
22.84
20.33
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
99.70
95.45
87.43
62.63
93.83
81.32
65.39
50.78
59.38
64.94
55.03
34.52
55.32
40.28
28.27
23.68
28.03
55.89
56.70
40.57
54.52
39.68
27.22
20.95
42.91
36.96
26.27
13.59
32.25
23.16
20.95
19.62
Table 10: EATA on PACS.
Domain-wise data stream
Random data stream
EATA
P
+A+
+C
SS
14
+2
+3
-4
Current domain
N/A
67.04
64.72
50.27
57.31
56.06
58.17
59.78
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
99.70
98.62
98.50
98.62
98.68
98.62
98.50
98.62
A
59.38
68.90
68.16
66.50
68.65
68.95
69.34
69.63
28.03
63.74
65.36
62.46
65.19
66.00
65.57
65.70
S
42.91
54.01
52.89
48.18
55.71
55.64
54.09
54.26
Table 11: COTTA PACS.
Domain-wiid wise data stream
Random data stream
CoTTA
P
+
CC+
S
1->
+2-
+33
->4
Current domain
N/A
65.48
62.12
53.17
56.06
54.33
57.16
57.42
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
99.70
98.68
98.62
98.62
98.62
98.62
98.56
98.62
A
59.38
65.82
65.87
65.48
66.02
65.87
66.31
65.97
28.03
62.63
63.05
63.10
63.01
62.88
63.01
62.97
S
42.91
53.88
54.03
53.78
54.67
55.31
55.10
54.62
Table 12: SAR (steps=1) PACS.
Domain wise data stream
Random data stream
SAR (steps=1)
P
+A+
CC+
1-
+2-
+3
-4
Current domain
N/A
66.75
63.82
49.58
56.78
56.35
56.68
56.70
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
99.70
98.68
98.50
98.32
98.74
98.56
98.50
98.44
A
59.38
68.02
68.07
66.94
67.87
68.65
68.55
68.16
28.03
62.84
64.97
62.93
63.82
64.89
64.46
64.38
S
42.91
53.47
52.07
45.74
54.92
55.46
53.68
52.53
Table SAR (steps=10) on PACS.
Domain -ise data stream
Random data stream
SAR (steps=10)
+
C
S
14
+22
-
-4
Current domain
N/A
69.38
68.26
49,02
53.51
51.15
51.78
45.60
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
P
99.70
98.20
95.39
96.47
97.13
97.78
97.72
94.13
59.38
72.36
66.60
62.16
62.74
64.94
66.11
56.64
C
28.03
63.44
68.30
56.19
59.77
61.73
62.03
56.02
S
42.91
53.37
44.59
54.62
41.00
49.66
48.79
36.37
44

---

Published as a conference paper at ICLR 2024
Table 14: SimATTA < 300) on PACS.
Domain-wiss data stream
Random data stream
SimATTA (B & 300)
P
AA
-C-
1-
-
-
-4-
Current domain
N/A
76.86
70.90
75.39
69.47
76.49
82.45
82.22
Budgets
N/A
75
145
223
66
142
203
267
99.70
98.44
98.86
98.80
97.96
98.68
99.04
98.98
59.38
80.71
82.32
84.47
73.97
80.52
81.10
84.91
C
28.03
48.12
82.00
82.25
72.35
81.06
83.36
83.92
S
42.91
32.78
56.25
81.52
79.49
83.10
84.78
86.00
Table SimATTA (5 < 500) on PACS.
Domain wwie data stream
Random data stream
SimATTA (B 500)
+A
+C
1
+2
+3
+4
Current domain
N/A
77.93
76.02
76.30
68.46
78.22
80.91
85.49
Budgets
N/A
121
230
358
102
221
343
425
P
99.70
98.92
98.86
98.62
98.20
99.46
99.10
99.16
59.38
87.01
87.60
88.33
73.39
79.20
84.91
86.67
C
28.03
54.78
83.96
83.49
68.43
74.40
84.22
84.77
S
42.91
46.37
63.53
83.74
81.34
81.04
86.66
87.71
Table 16: Tent (steps=1) on VLCS.
Domain-wise data stream
Random data stream
Tent (steps=1)
+
+S+
+V
1+
+2-
+3-+
+4
Current domain
N/A
38.55
34.40
53.88
44.85
44.29
47.38
44.98
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
C
100.00
84.81
85.44
84.73
84.95
85.16
85,80
85.30
L
33.55
40.02
43.11
43.86
39.68
41.98
43.11
43,49
S
41.10
33.39
35.41
33.61
36.29
37.90
38.27
37.81
V
49.08
53.20
54.06
53.11
53.76
54.18
53.76
53.35
Table 17: Tent (steps=10) on VLCS.
Domain-wir wise data stream
Random data stream
Tent (steps=10)
+
+S
+V
1+
+2
+3
+4
Current domain
N/A
45.41
31.44
32.32
46.13
42.31
43.51
39.48
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
C
100.00
73.07
48.34
42.54
74.13
62.19
56.54
52.01
L
33.55
46.61
38.44
37.65
44.88
45.93
43.41
40.32
S
41.10
31.75
28.82
27.79
35.37
36.14
35.28
33.64
V
49.08
48.05
40.14
33.12
50.50
44.49
42.48
40.37
Table 18: EATA VLCS.
Domain-wise data stream
Random data stream
EATA
L
S
+V
1-
+2-
+
++
Current domain
N/A
37.24
33.15
52.58
43.77
42.48
43.34
41.55
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
C
100.00
85.16
85.02
84.10
84.73
84.52
84.10
83.32
L
33.55
37.16
37.24
37.69
37.09
36.78
36.90
36.67
S
41.10
33.39
33.49
32.39
33.33
32.54
31.84
31.47
V
49.08
51.87
52.16
52.49
52.07
52.43
52.64
52.55
45

---

Published as a conference paper at ICLR 2024
Table 19: CoTTA on VLCS.
Domain-wise data stream
Random data stream
COTTA
->
S
1
+2
-
->4
Current domain
N/A
37.39
32.54
52.25
43.69
42.14
43.21
42.32
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
C
100.00
81.55
81.98
82.12
82.61
82.47
82.12
81.98
I.
33.55
37.20
37.91
37.65
38.48
38.22
38.40
37.99
S
41.10
30.71
32.78
33.12
34.00
33.70
33.97
33.52
V
49.08
52.01
52.64
52.90
53.64
53.14
53.08
53.23
Table 20: SAR (steps=1) on VLCS.
Domain wise data stream
Random data stream
SAR (steps=1)
L>
S
+V
1-
+2
3>3_.
-
Current domain
N/A
36.18
34.43
52.46
43.64
43.04
44.20
41.93
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
C
100.00
84.31
84.17
83.96
85.09
85.23
85.23
85.09
I.
33.55
35.62
38.29
39.72
38.55
39.34
40.21
40.70
S
41.10
33.24
36.41
36.53
34.37
35.62
36.29
36.44
V
49.08
51.75
52.61
52.37
52.90
52.75
53.05
53.02
Table 21: SAR (steps=10) VLCS.
Domain wise data stream
Random data stream
SAR (steps=10)
+
S
-V
14
-+2
->3
-4
Current domain
N/A
35.32
34.10
51.66
43.56
42.05
42.53
41.16
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
100.00
83.96
83.04
82.12
84.03
84.24
85.23
85.09
L
33.55
34.07
35.92
41.49
39.53
38.37
37.65
37.58
41.10
31.93
34.89
33.94
35.19
32.94
33.88
33.12
V
49.08
51.33
51.51
53.08
52.78
52.34
51.78
52.01
Table 22: SimATTA (B < 300) on VLCS.
Domain-wist data stream
Random data stream
SimATTA (B < 300)
C
+
S
+V
1-
+2+
+33
+4
Current domain
N/A
62.61
65.08
74.38
62.33
69.33
73.20
71.93
Budgets
N/A
79
175
272
71
135
208
262
C
100.00
99.51
98.52
99.93
99.86
99.79
100.00
99.93
L
33.55
68.11
69.92
69.50
62.61
66.64
68.45
69.43
S
41.10
55.24
68.89
66.67
65.54
69.29
71.79
72.46
49.08
66.08
70.94
77.34
73.79
76.87
78.82
80.39
Table 23: SimATTA (8 < 500) on VLCS.
Domain- wise data stream
Random data stream
SimATTA (B 500)
+++
+
+V
1-+
++2
+33
+
Current domain
N/A
63.52
68.01
76.13
62.29
70.45
73.50
72.02
Budgets
N/A
113
266
446
107
203
283
356
C
100,00
99.29
98.59
99.51
99.93
99.86
99.86
99.43
33.55
62.95
70.63
70.56
66.57
67.09
67.24
70.29
S
41.10
51.31
73.83
73.10
65.33
71.79
72.91
72.55
V
49.08
59.36
71.65
78.35
73.58
77.84
80.01
80.18
46

---

Published as a conference paper at ICLR 2024
Table 24: Tent (steps=1) on Office-Home.
Domain-win wise data stream
Random data stream
Tent (steps=1)
R
-
C
1->
-+2
-+3
-
Current domain
N/A
49.61
39.31
63.87
49.95
50.27
50.23
52.06
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
96.44
92.33
92.36
92.47
92.38
92.45
92.45
92.40
57.07
49.73
49.73
49.57
49.69
49.73
49.57
49.24
C
44.97
39.27
39.54
39.89
39.45
39.68
39.73
39.68
73.15
63.60
63.66
63.89
63.60
63.82
63.93
63.98
Table 25: Tent (steps=10) on Office-Home.
Domain-wise data stream
Random data stream
Tent (steps=10)
R
+A
C
P
1->
+2-
+3
-+4+
Current domain
N/A
49.61
39.04
61.41
50.05
49.31
48.74
47.79
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
96.44
91.99
89.14
87.08
92.08
90.80
88.59
85.31
57.07
49.94
46.77
44.79
49.44
48.21
45.69
42.85
44.97
38.58
39.11
38.37
40.18
40.02
38.63
37.89
73.15
63.28
61.03
60.49
64.36
63.64
61.12
58.71
Table 26: EATA on Office-Home.
Domain-wiss data stream
Random data stream
EATA
R
+
+C+
+P
14
+2-
-3
+4
Current domain
N/A
49.65
39.04
63.53
49.73
50.27
49.45
51.07
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
R
96.44
92.36
92.17
91.60
92.38
92.22
91.71
91.05
57.07
49.57
49.53
49.61
49.69
49.40
49.36
49.11
C
44.97
39.08
39.01
38.65
39.27
39.01
38.42
38.26
73.15
63.42
63.42
63.48
63.51
63.37
63.33
62.99
Table 27: COTTA on Office-Home.
Domain- wise data stream
Random data stream
CoTTA
R
+
CC+
+P
1-
+2
+3
-4
Current domain
N/A
49.61
38.76
61.84
49.84
49.84
48.95
50.43
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
96.44
90.38
88.02
87.81
90.48
89.37
88.00
86.99
A
57.07
48.58
45.53
44.95
47.34
46.35
44.62
43.68
44.97
36.66
35.58
35.92
37.55
36.40
35.44
34.73
73.15
60.40
57.74
59.04
61.12
59.63
58.35
57.56
Table 28: SAR (steps=1) on Office-Home.
Domain-wise data stream
Random data stream
SAR (steps=1)
R
+
CC
+P
1-
+2-
+3
-4
Current domain
N/A
49.65
39.24
63.53
49.84
50.05
49.91
51.67
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
R
96.44
92.38
92.31
92.45
92.40
92.36
92.36
92.38
57.07
49.65
49.57
49.73
49.69
49.61
49.57
49.57
C
44.97
39.34
39.22
39.36
39.34
39.56
39.47
39.50
73.15
63.51
63.51
63.69
63.60
63.71
63.71
63.87
47

---

Published as a conference paper at ICLR 2024
Table 29: SAR (steps=10) on Office-Home.
Domain wise data stream
Random data stream
SAR (steps=10)
R
+A+
+C+
+P
14
+2-
+3-
+4-
Current domain
N/A
49.53
38.81
61.50
50.09
50.30
49.77
49.22
Budgets
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
R
96.44
92.20
92.06
88.94
92.40
92.47
91.53
89.14
57.07
49.40
49.77
46.15
49.81
50.02
48.91
46,23
C
44.97
39.20
38.63
37.04
39.50
39.29
38.65
36.31
P
73.15
63.53
62.69
59.41
64.18
64.18
62.83
59.45
Table 30: SimATTA (8 300) on Office-Homee
Domain data stream
Random data stream
SimATTA (B 300)
+
+C+
+P
1-
-2
+3
+4
Current domain
N/A
56.20
48.38
71.66
58.57
60.88
62.91
63.67
Budgets
N/A
75
187
277
79
147
216
278
R
96.44
95.43
95.43
95.75
95.91
95.96
96.01
95.89
57.07
57.56
59.50
60.07
58.34
59.91
61.15
62.01
C
44.97
42.25
52.46
52.62
51.66
52.30
54.75
54.98
P
73.15
68.84
70.13
74.70
72.45
73.10
74.50
74.70
Table 31: SimATTA (B 500) on Office-Home.
Domain- wise data stream
Random data stream
SimATTA (B < 500)
R
+A
+C+
+P
1-
+2
++3+
+4+
Current domain
N/A
58.71
51.11
74.36
58.85
62.63
63.41
64.31
Budgets
N/A
107
284
440
126
248
361
467
96.44
95.69
95.71
96.03
96.26
96.19
95.87
95.91
57.07
61.43
61.43
62.05
58.18
61.15
61.52
63.78
44.97
46.41
57.73
57.41
53.17
55.14
56.79
57.87
P
73.15
70.74
71.98
76.98
73.51
74.18
75.78
77.09
48

---

Published as a conference paper at ICLR 2024
in deep learning heavily relies on large-scale data. Consequently, two promising paths emerge: establishing credible assumptions and leveraging additional information.
Firstly, developing credible assumptions can lead to comprehensive comparisons across various stud- ies. Given that theoretical guarantees highlight the inherent differences between methods primarily based on the application limits of their assumptions, comparing these assumptions becomes critical. Without such comparative studies, empirical evaluations may lack precise guidance and explanation.
Secondly. while we acknowledge the value real-world data (observations), discussions surrounding the of extra information remain pertinent. Considerations include the strategies to acquire this supplementary information and the nature of the additional data needed.
Despite the myriad of works domain generalization, domain adaptation, and test-time adaptation, a comprchensive survey or benchmark encapsulating the aforementioned comparisons remains an unmet need. Moreover, potential future directions for out-of-distribution generalization extend beyond domain generalization and test-time adaptation. One promising avenue is bridging the gap between causal inference and deep learning, for instance, through causal representation learning.
In conclusion, our hope is that this work not only offers novel practical setting and algorithm but also illuminates meaningful future directions and research methodologies that can benefit the broader scientific community.
49


Reviews:
[{"review_id": "mxERJIJBMH", "reviewer": "Reviewer_cDV9", "summary": "This paper proposes a new setting, namely ATTA (Active Test-Time Adaptation), to integrate active learning (a limited number of labeled test samples) within test-time adaptation (TTA) to enhance TTA under domain shifts. The problem itself is practically important and the paper presents a theoretical guarantee and a sound solution (SimATTA) that combines incremental clustering and entropy selection to conduct online sample selection, avoiding catastrophic forgetting issues. The simplicity of the proposed algorithm and its successful application on real datasets are commendable. A thorough empirical study (including ablations) with encouraging results (both in the paper and its supplementary material) shows the effectiveness of the approach in terms of its effectiveness and generalization performance. The paper's clear contribution to the TTA community is evident, and I recommend its acceptance.", "questions": "1. As an active sampling algorithm, how to define an informative test sample, especially on streaming data? The authors might provide some visualization results for better understanding.\n\n2. How about the cost of the ATA training set?  It seems that the SimATTA algorithm will keep a training set (the maximum size is $\\mathcal{B}$?) during the test-time adaptation, would this strategy violate the nature of test-time adaptation, i.e., real-time?\n\n3. There are many hyper-parameters in this work, such as two entropy thresholds $e_l$ and $e_h$, number of cluster centroid budget $NC(t)$, centroid increase number $k$, etc. The question is how to choose them for different datasets. In some sense, this is not the weakness/limitation of this particular paper but rather applies to the whole AL paradigm.\n\n4. It is unclear what the meaning of `steps=10` is. And what is the config of SimATTA? SimATTA (`steps=1`) or SimATTA (`steps=10`)?\n\n5. How to deal with an extreme situation in which only one sample is in a mini-batch, i.e., the batch size is 1.\n\n6. Another minor question is, why the performance of Enhanced TTA on Tiny-ImageNet-C (severity level 5) is poor? Also, why the baseline results (CLUE) on VLCS of Tab. 4 are too low, even worse than that of the Random method?\n\n7. In Section 5.2, \"randomly select labeled samples and fine-tune them with `their selected pseudo-label samples.`\" Is it a mistake?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "**Originality**: The paper introduces a novel setting, active test-time adaptation (ATTA) with theoretical guarantees for alleviating distribution shifts and mitigating catastrophic forgetting and extensive experiments on several benchmarks under domain generalization shifts. Additionally, the Section FAQ & Discussions in supplementary material is highly praiseworthy.\n\n**Quality**: The paper provides a thorough experimental evaluation of the SimATTA algorithm on four datasets (PACS, VLCS, Office-Home, and Tiny-ImageNet-C). The paper also conducts ablation studies to analyze the impact of different components of SimATTA. The paper demonstrates that SimATTA can achieve superior performance and maintain efficiency.\n\n**Clarity**: The paper provides sufficient background information including theory and closely related works to situate the contribution of the ATTA setting and the SimATTA algorithm.\n\n**Significance**: The paper proposes an important and challenging setting of active test-time adaptation (ATTA) and a detailed comparison with related settings (DA/DG, TTA, ADA, ASFDA, and AOL) highlights the value of the proposed ATTA. ATTA also has many potential practical utilities such as an autopilot system and a personalized chatbot discussed in supplementary material.", "weaknesses": "**Insufficient visualization**: Though the authors have provided detailed algorithms (Alg. 1 and Alg. 2) to show the proposed SimATTA algorithm, it is still hard to follow the whole picture quickly. Thus it could be better to provide a clear diagram to illustrate the framework of the SimATTA algorithm.\n\n**Insufficient justifications**: For example, regarding the **efficiency** and **applicability** of ATTA, some justifications are missing in this paper. First, as shown in Tab. 3, the time cost of ATTA is around ten times than general FTTA (Tent: 68.83, EATA: 93.14, SimATTA: 736.28). The reason might be the clustering-based selection process and fully fine-tuning pre-trained models? Second, though the authors state that \"ATTA can be applied to any pre-trained models including large language models (LLMs)\", they provide no experimental results. \n\n**Inconsistent results**: results of SimATTA ($B\\le$500) in Table 2 (TTA comparisons on PACS) and Table 8 (Ablation study on PACS) are different.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZdFuEs8nqb", "reviewer": "Reviewer_BXz7", "summary": "This paper proposes a novel, formal problem setting of Active Test-Time Adaptation (ATTA), which incorporates active learning to perform test-time adaptation (TTA). It attempts to mitigate distribution shifts and catastrophic forgetting, while not being provided access to source data, model parameters, or pre-collected target samples. \n\nA theoretical analysis of ATTA in the setting of binary classification is provided. First, the theory establishes a learning bound that has the notions of composition of training data, estimated distribution shift, and ideal joint hypothesis performance. Second, the fore-mentioned theory is utilized to shown that catastrophic forgetting can be mitigated by performing selective sample selection through entropy minimization. \n\nSimATTA, a practical algorithm built upon the ATTA theory, is then developed. It integrates incremental learning and selective entropy minimization techniques. Empirical evaluations on four benchmarks simulating distribution shifts demonstrate the effectiveness of SimATTA when compared to the existing work. It achieves state-of-the-art accuracy under distribution shifts while maintaining the computational complexity that is not significantly higher than that of the prior work.", "questions": "The “budget” term appears to be a significant factor in the algorithm. However, I’ve not been able to identify its relationship to the cluster centroid number. Could the authors please provide clarification on this matter?\n\nI’m looking forward to seeing the code implementation of SimATTA.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "$\\textbf{Novelty and significance}$:\nIn my opinion, the empirical results, especially addressing RQ1, clearly set this paper apart from previous research, paving the way to overcome distribution shifts under the TTA setting. The proposed algorithm, SimATTA, significantly surpasses the existing TTA algorithms in terms of performance accuracy under distribution shifts. It also appears to exhibit greater resilience to catastrophic forgetting. Additionally, it is supported by a robust theoretical framework.\n\n$\\textbf{Completeness and comprehensiveness}$:\nThe main manuscript and the supplementary material offer a comprehensive context and detailed information about the proposed work. Furthermore, related work addressing distribution shifts under various settings is also adequately discussed.", "weaknesses": "I found no major weakness from this paper. One minor aspect I would like to highlight concerns the clarity of the experimental settings, such as domain-wise data stream, random stream, post-adaptation, and so on. It took me some time to grasp all of these distinct settings. Perhaps including a dedicated section to explain about these settings would be more helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d5fpjNSW7q", "reviewer": "Reviewer_5EyE", "summary": "The paper titled \"Active Test-Time Adaptation: Theoretical Analyses and An Algorithm\" delves into a novel approach for machine learning models that dynamically adapt during test-time  under domain shifts. Traditionally, models rely heavily on heuristic and empirical studies without further adaptation. The authors challenge this convention by introducing a mechanism that allows the model to actively query an oracle (typically a human) during test-time to obtain labels for certain instances. The objective is to enhance the model's performance on the test set by leveraging this limited interaction with the oracle.\n\nThe primary contributions of the paper are as follows:\n\n1. Introduction of the Active Test-Time Adaptation (ATTA) framework.\n2. A novel algorithm for determining which instances should be queried from the oracle, based on their potential impact on the model's performance.\n3. Experimental validation of the ATTA framework on several benchmark datasets, demonstrating significant improvement in performance over non-adaptive baselines.", "questions": "See Weaknesses.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The concept of actively adapting a model during test-time based on interactions with an oracle is innovative. This breaks away from the conventional train-test paradigm, paving the way for more dynamic and adaptive models.\n\n2. The authors provide a theoretical foundation for the ATTA framework, making a compelling case for its viability and potential benefits.\n\n3. The proposed method is model-agnostic, meaning it can be applied to a wide range of machine learning algorithms, from simple linear classifiers to complex deep learning architectures.\n\n4. The extensive experiments on benchmark datasets provide strong empirical evidence supporting the effectiveness of the ATTA framework. The improvements over non-adaptive baselines are both statistically significant and practically relevant.", "weaknesses": "1. The ATTA framework's effectiveness hinges on the availability and accuracy of an oracle. In real-world scenarios, obtaining such an oracle (especially a human expert) might be challenging, time-consuming, or expensive.\n\n2. While the approach shows promise on benchmark datasets, its scalability to very large datasets or real-world applications remains untested. The computational overhead of deciding which instances to query and updating the model during test-time could be prohibitive in some scenarios.\n\n3. The paper assumes a limited budget of queries to the oracle. In many real-world scenarios, determining this budget or ensuring its strict adherence might be challenging.\n\n4. Continually adapting the model during test-time based on feedback from the oracle could lead to overfitting, especially if the test set is not representative of the broader data distribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mhiqHpsTMd", "reviewer": "Reviewer_yeNU", "summary": "This paper points out that achieving domain generalization is theoretically impossible without additional information. Therefore, this paper introduces active test-time-training(ATTA), combining active learning with test-time-training, and proposes an effective ATTA algorithm, SimATTA, that innovatively integrates incremental clustering and selective entropy minimization to address catastrophic forgetting and real-time active sample selection issues.", "questions": "Entropy does not directly measure the distributional distance between the model's distribution and the test sample，so the theoretical foundation presented in the paper is shaky. How do you view this issue?\n\nAfter reading the rebuttal, I decided to raise my score.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "（1）This paper innovatively combines active learning with TTA, enhancing performance across test domains. and present sample entropy balancing to avoid catastrophic forgetting.\n（2）The paper conducted extensive experiments and compared with the latest state-of-the-art methods on multiple datasets, achieving superior results.\n（3）The paper is well-organized, and it provides extensive proofs for the theorems mentioned.", "weaknesses": "1. In Section 3.2, the authors state that entropy is essentially a measure of the distribution distance between the model distribution and a test sample, which is not true. While entropy can provide information about the uncertainty of the model, it does not directly measure the distributional distance between the model's distribution and the test samples. This fundamental flaw casts doubt on the proposed method.\n2. Table 3 indicates that, in terms of efficiency, SimATTA takes longer than all previous methods, making it less efficient.\n3. In Appx. H.2., when B<=500, the performance of SimATTA is close to that of other methods, with no distinct advantage\n4. The ablation study is not comprehensive enough to effectively prove the efficacy of both the incremental clustering and selective entropy minimization methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)