On the Learnability of Test-Time Adaptation: A Recovery Complexity Perspective

Test-time adaptation (TTA) aims to adapt models to maintain reliable performance on non-stationary test streams without requiring labeled data. Despite its empirical success, the learnability of TTA under non-stationary streams remains unexplored. A key challenge is the lack of a principled theoretical framework that simultaneously aligns with the TTA objective and captures both continuously evolving distribution shifts and intrinsic information constraints. To address this gap, we propose the first theoretical framework for studying the learnability of TTA and introduce $(\epsilon,\delta)$-Recovery Complexity and $(\epsilon,\rho)$-TTA Learnability. Recovery complexity measures the post-shift time needed to maintain excess risk below a target level with high probability, and is further extended to TTA learnability, which measures the long-term reliability of TTA. Within this framework, we introduce a novel discrete surrogate for non-stationary test streams, enabling a unified and tractable analysis of both gradual and abrupt shifts. We derive order-wise matching lower and upper bounds on recovery complexity, revealing fundamental limits of TTA and an intrinsic adaptivity-information trade-off. These results provide unified learnability guarantees for TTA that complement regret-based analyses.

Machine learning models are often trained once and then deployed in real-world environments that continuously change. As a result, a model that works well at first may become less accurate once it is used in the real world. Test-time adaptation aims to help the model keep adjusting to new data on its own, without asking humans to provide new labels, so that it can continue to make reliable predictions. Although many test-time adaptation methods work well in experiments, we still do not fully understand when such adaptation is actually possible. In this work, we develop a theoretical framework to study this question. We introduce a way to measure how long a model needs to recover good performance after the test data changes, and whether it can remain reliable over a long, evolving stream of data. Our analysis covers both sudden and gradual changes. It reveals fundamental limits of test-time adaptation and identifies an important trade-off: faster adaptation requires sufficient useful information from the unlabeled test data. These results help explain when reliable adaptation can and cannot be expected, and provide a theoretical foundation for future work on test-time adaptation.