Active Test-Time Adaptation: Theoretical Analyses and An Algorithm

Dear Reviewer yeNU,

Thank you for your constructive comments and valuable suggestions! We have revised the paper following your suggestions and we provide responses for each concern here.

W1. 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.

Thank you for raising this point! We realize the potential misconception here and have revised the section for more rigorous descriptions following your suggestion. However, we would like to clarify that whether entropy directly measures a distributional distance does not impair the theoretical foundation in Sec. 3.2 and the later proposed method.

• Relationship between low-entropy samples and source samples: The core point of Sec. 3.2 and mitigating catastrophic forgetting is the assumption that the low-entropy sample distribution selected by the source-pretrained-model, $D_{\phi,S}(t)$, serves the model training similarly to source samples in terms of CF. When a model assigns low entropy to a sample, this indicates a high level of certainty or confidence in its prediction and can be interpreted as the sample being well-aligned or fitting closely with the model's learned distribution. The pre-trained model is well-trained on abundant source data, and thus low entropy can be used as an indicator of a sample closely aligned with the model distribution, in this case, a source-like sample. These source-like samples form a distribution that fits/supports the original model predictions. Intuitively, these supports prevent the model from violating the original high-confident predictions, thus maintaining the model's original distribution. This behavior is different from minimizing the distance between the current model parameters and the original model parameters. Instead, these samples only serve as the original model's "anchor points" to avoid catastrophic forgetting. More detailed explanations and clarification are in Appx.D.
• Theoretical validity: With no further condition than the above assumption, the theoretical results in Sec 3.2 and the method design in Sec 4 hold, giving credence to the validity of our paper.
• Bridging the theory and practical implementations: In Table 1, we empirically validate our assumption that low-entropy samples, similar to samples from the source distribution, can serve to avoid catastrophic forgetting. This assumption with its empirical validation is the bridge between our theorems and our practical implementations.

W2. Table 3 indicates that, in terms of efficiency, SimATTA takes longer than all previous methods, making it less efficient.

We have revised Sec 5 to add information and avoid misunderstandings.

• Regarding Table 3, we'd like to clarify that ATTA is of very similar time efficiency with SAR on Tiny-ImageNet-C (time per step). ATTA does not have time-consuming steps, instead the training time is due to the number of interaction steps till convergence. Since SimATTA's training is statistically significant instead of one sample training, several training steps are necessary to make use of information and improve performance. This is a trade-off between effectiveness and efficiency, and we believe the performance improvement is worth this training.
• Real-world application: In our opinion, many real-time applications like robotics, autonomous vehicles, medical imaging adaptations, and user interface personalizations, are not very time-sensitive. For example, retraining a personalized user interface recommendation system may require hours, days, or weeks, but ATTA can fine-tune the model in a second scale, which should be considered a real-time manner. As we have demonstrated (detailed in Appx B.Q8), the speed of ATTA is sufficiently fast for an autopilot system, and the speed requirements of the other applications listed above are safely within the limit of ATTA. Therefore, we believe ATTA is a real-time setting.

Dear Reviewer 5EyE,

Thank you for your constructive comments and valuable suggestions! We have made paper revisions following your suggestions and would like to provide responses for each concern here.

W1. 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.

• Reliance on an oracle or expert input is a fundamental aspect of active learning, which is a long-standing field. While obtaining an oracle might be challenging or expensive, the cost should be weighed against the benefits of significantly improved model performance and reduced need for vast amounts of labeled data.
• Application of active strategies: In many practical situations, the benefits of active learning outweigh the challenges of obtaining an oracle. For instance, in medical diagnosis, scientific research, or complex engineering problems, the cost and effort of consulting an expert are justified by the significant improvements in model accuracy and efficiency. Technological advancements, such as semi-automated systems or sophisticated algorithms, can also serve as oracles or assist human experts, making the process more feasible and efficient.
• Application of ATTA: ATTA has its specific application scenarios. One potential application direction is for human-machine cooperated semi-automated applications, where we can obtain passive oracle input without extra efforts. One example is autopilot systems we mentioned in our FAQ (Appx B.Q8: What is the potential practical utility of ATTA?).
• Finally, we regard this point as a general challenge of active learning rather than a drawback of the ATTA framework itself. Therefore, it can be viewed as a consideration/limitation in the application. We specify this discussion in Appx.J to add rigor to the paper.

W2. 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.

• Time complexity: As in Table 3, ATTA is of very similar time efficiency with TTA method SAR (time per step). ATTA does not have time-consuming steps, instead the training time is due to the number of interaction steps till convergence. This training time is a trade-off for significant improvements in performances.
• Real-world application: In our opinion, many real-time applications like robotics, autonomous vehicles, medical imaging adaptations, and user interface personalizations, are not very time-sensitive. For example, retraining a personalized user interface recommendation system may require hours, days, or weeks, but ATTA can fine-tune the model in a second scale, which should be considered a real-time manner. As we have demonstrated (detailed in Appx B.Q8), the speed of ATTA is sufficiently fast for an autopilot system, and the speed requirements of the other applications listed above are safely within the limit of ATTA. Therefore, we believe ATTA is a real-time setting. Rigorously, we acknowledge that the application scopes of ATTA and FTTA are not completely overlapping. FTTA can handle applications that are extremely time-sensitive, while ATTA provides results of much higher quality.
• Finally, our paper focuses on catastrophic forgetting, domain shift solving, and the establishment of a new setting. We conduct experiments on domain generalization datasets and emphasize the comparisons for different settings. We acknowledge that scalability is not a focus of this paper. Therefore, we consider this valuable suggestion as a possible future direction instead of a weakness, which we discuss in FAQ (Appx.B.Q10: What are not covered by this paper?).

Q3

• In experimental settings, $k$ is selected to approximate the budget limit $\mathcal{B}$ we would like to observe, which is for comparison purposes. Selecting $e_l$ is a trade-off between accuracy and the number of low-entropy samples. We select $e_l$ as low as possible while the number of low-entropy samples can still maintain the low/high entropy balance. Therefore, the $e_l$ selection is related to the distribution of the entropy in the specific dataset.

• The hyperparameter searching spaces used in the paper are provided as follows:

  • $e_l: \{10^{-4}, 10^{-3}\}$

  • $e_h: 10^{-2}$

  • $k: [0, 3]$

  • $NC(t)$ is controlled by $k$, $i.e.$, $NC(t)=10 + kt$, where 10 is the initial number of centroid.

• In real-world scenarios, we should select $k$ according to our oracle resource available. Instead of using $e_l$ independently, we believe considering both the threshold $e_l$ and an extra selection ratio can be a good practice.

Q4

• steps=10 indicates 10 gradient backpropagation iterations for one test-time adaptation batch. The hyperparameter steps should be set for Tent and SAR not only because of their original settings but also because their pseudo-label training lacks statistical significance and thus requires a hyperparameter to control the training process. In experiments, we found that using a tolerance count (tol) is more natural because SimATTA maintains a statistically significant training set. SimATTA will stop updating once the loss does not decrease for more than 5 steps.
• For TinyImageNetC in Table 3, SimATTA uses steps=10 for time comparisons with others since other methods use at most 10 steps. We have added this information to the table.

Q5

• ATTA handles this extreme situation by accumulating these samples into a buffer. Sample selections and training are executed once the buffer is full, e.g., setting it to the length of 100. This process is less efficient than TTA but necessary since one of the fundamental differences between ATTA and FTTA is that ATTA tries to fine-tune the model using a statistically significant distribution. This is a trade-off between effectiveness and efficiency.

Q6

• (1) Enhanced TTA, though having access to labeled samples, is essentially an FTTA setting, i.e., it does not maintain a statistically significant training set. Therefore, these enhanced TTA methods still suffer from CF problems. The Tiny-ImageNet-C comparisons aim to address the potential question of whether access to labeled samples is the only reason for improvements and for corresponding fairness concerns.

• (2) In 3 runs, CLUE has source domain results: $74.06$, $84.38$, and $98.66$. This indicates CLUE suffers from severe CF problems in 2 out of 3 runs. One simple explanation for these failures is that the selected samples are too far from the source distribution, which induces CF and overfitting problems. To be specific, the high entropy consideration of CLUE leads to the failure of choosing low-entropy samples. As demonstrated in Sec. 3.2, compared to our mitigation of CF with balanced high/low entropy samples, CLUE fails to maintain this balance in VLCS and shows catastrophic performances.

• The reason why the method Entropy does not suffer from CF problems is that the ADA training process includes 10 selection rounds in their settings so that a possible minor CF problem after the first round leads to the abrupt entropy increase of source-like samples. These samples are then selected by the Entropy method in the 2nd round, thus preventing further CF problems. In contrast, CLUE fails to select these source-like samples in time (before severe CF) because of diversity considerations. Therefore, we can conclude the failure of CLUE as that, considering uncertainty and diversity leads to better informative sample selections but may cause worse source-like sample selections.

Q7

• Sorry for the confusion. We have revised the unclear expression. This sentence means that, in addition to each TTA's original updates, we further enhance these TTA methods by fine-tuning the model with randomly selected labeled samples. Traditional TTA methods are generally designed to update models using their own pseudo-labeled samples.

Besides the above points, we also provide further experiments and make an effort to clear the concerns and improve the clarity and organization of our paper in multiple aspects following the advice from other reviewers. Please refer to the revised paper and appendices for details.

We sincerely thank you for your time! Hope we have addressed your concerns through practical efforts and shown the significance of our work. We look forward to your reply and further discussions, thanks!

Sincerely,

Authors

Dear Reviewer cDV9,

Thank you for your acknowledgment of our work and insightful comments! We have made paper revisions following your suggestions and would like to address your concerns by answering your questions one by one as follows.

W1. Insufficient visualization

• Thank you for your suggestion. We have created a figure (Fig.2) in the revised paper to demonstrate the algorithm more intuitively. We inserted the figure in the main paper and moved Alg. 2 to the appendix due to the space limit. We hope this modification is satisfactory.

W2. Insufficient justifications

• Following your suggestion, we have added additional justifications in the revised paper. For your convenience, we summarize important changes and explanations as follows.

• Efficiency: ATTA's higher time cost is due to the difference in training steps. In this experiment, SimATTA has a training step of 10 and a similar time cost as SAR per step. In Table 3, we aim to show that 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 problems. 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 in Tent (step=10) leads to worse results (compared to step=1), which further motivates the design of the ATTA setting. In brief, ATTA is able to apply statistically significant training processes without CF, which requires sufficient training and is the reason for the extra time cost.

• Applicability: "ATTA can be applied to any pre-trained models including large language models (LLMs)" demonstrates a possible future direction. In essence, ATTA is model agnostic, which is theoretically applicable to various machine learning models. In contrast, many FTTA methods only allow training the batch normalization layers. However, we acknowledge that we do not cover LLM experiments in this work, and applying ATTA to LLM may encounter unknown results.

W3. Inconsistent results

• Thanks for pointing out. These inconsistent results come from a different hyperparameter $k$ selection in the ablation study to ensure that different variants have the number of budgets as similar as possible. We adjusted one $k$ in the ablation study since, in that part of the experiment, the budget number was much less than other variants. To clarify this ablation comparison issue and eliminate confusion, we have extended the ablation study by conducting experiments with more budget-limit selections and using line charts instead of tables for comprehensive comparisons. Please refer to our revised ablation study (Appx I.2) for more details.

Q1

• Thanks for the advice. We have added visualization results and explanations in Appx F.2 for better illustration. In each batch, after the high/low entropy sample selection, we examine the high entropy samples to select informative ones. Assume we have 3 previously selected anchors, and we now apply a Kmeans of 4 centroids. After clustering, assume 3 centroids are located near the 3 old anchors since the 3 anchors' weights are much larger than other samples in this batch. Then the left centroid should statistically locate at the center of the distribution representing new test samples, which should be far from the 3 old anchors (thus, has not been covered by them). These new samples that are far from the previously known anchors are informative to us. Finally, we choose the closest sample to the centroid as a new anchor, i.e., the informative test sample.

Q2

• (1) Yes, the number of labeled training sets is limited by $\mathcal{B}$, and we also keep an unlabeled low-entropy training set of similar scale. Therefore, the overall space complexity is $O(\mathcal{B})$.

• (2) In our opinion, many real-time applications such as robotics, autonomous vehicles, medical imaging adaptations, and user interface personalizations, are not very time-sensitive. For example, retraining a personalized user interface recommendation system may require hours, days, or weeks, but ATTA can fine-tune the model in a second (or seconds) that should be considered in a real-time manner. As we have demonstrated (detailed in Appx B.Q8), the speed of ATTA is sufficiently fast for an autopilot system, and the speed requirements of the other applications listed above are safely within the limit of ATTA. Therefore, we believe ATTA is a real-time setting.

• Rigorously, we do acknowledge that the application scopes of ATTA and FTTA are not completely overlapping. FTTA can handle applications that are extremely time-sensitive, while ATTA provides results of much higher quality.

Dear Reviewer BXz7,

We would like to extend our gratitude for your acknowledgment! We have made paper revisions following your suggestions to address your presentation concerns and would like to answer your questions as follows.

Weakness: 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 these settings would be more helpful.

• Thank you for the valuable suggestion! We have restructured Sec 5 to include a separate paragraph explaining experimental settings, as well as describe the experimental settings in detail in Appx.G.

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?

• Thank you for the question. We have revised descriptions to improve clarity. We also explain here.
• The number of selected samples for each minibatch is decided jointly by the incremental clustering algorithm, the cluster centroid number $NC(t)$, and the stream in-coming distributions. Intuitively, this sample selection is a dynamic process, with $NC(t)$ restricting the budget and incremental clustering performing sample selection. For each batch, we increase $NC(t)$ 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(t)$. In contrast, if the incoming batch contains data located in multiple new distributions, the incremental clustering "wants" to select more samples than the $NC(t)$ limit, but is forced by the limit to merge multiple previous clusters into one new cluster. Therefore, $NC(t)$ can restrict the budget but cannot determine the budget alone since the budget is also strongly affected by the data stream distributions.
• The incremental clustering is detailed in Alg 2 (Appendix F), and $NC(t)$ 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 as shown in Table 2.

I'm looking forward to seeing the code implementation of SimATTA.

• We would like to provide our code through this anonymous link: https://anonymous.4open.science/r/tta-C807/

Besides the above points, we also provide further experiments and make an effort to clear the concerns and improve the clarity and organization of our paper in multiple aspects following the advice from other reviewers. We add visualization experiments and extend the ablation studies. Please refer to the revised paper and appendices for details.

We sincerely thank you for your time! Hope we have addressed your concerns through practical efforts and shown the significance of our work. We look forward to your reply and further discussions, thanks!

Sincerely,

Authors