Untangle Generalization Errors for Better Test-Time Adaptation in Overparameterized Linear Regression

Test-time adaptation (TTA) is a strategy that leverages unlabeled test data to adjust a pretrained model, improving robustness against distribution shifts. Recent advances in this research area are mostly driven by heuristic or empirical approaches with limited theoretical guidance. In particular, there is little theoretical analysis on what factors are important in TTA and how they impact the adaptation performance. We derive a closed form of expected generalization errors of overparameterized linear models in consideration of a general TTA setup involving sequentially different environments. As revealed by this theorem, well-trained models can be dynamically updated in response to test data shifts, demonstrating the advantages of TTA over the traditional "train-test" paradigm. This theorem further explains how key factors, such as overparameterization along with tradeoffs between the pretrained models and the adaptation algorithms, influence the performance of TTA. Based on these insights, we propose a novel test-time adapter, test-time adapter via prototypes (TAPs), to improve dynamic adaptation performance by pretrained knowledge enhancement. TAP employs a memory bank to store probabilistic representations and label pairs during training and uses ready-made knowledge to gradually update the memory and prediction during inference. Extensive experiments on domain generalization benchmarks confirm that the proposed adapter is computationally lightweight and outperforms traditional TTA methods.