On the Learnability of Test-Time Adaptation: A Recovery Complexity Perspective
For researchers studying TTA, this provides a principled theoretical foundation that was previously missing, though the results are theoretical and not yet validated empirically.
This paper proposes the first theoretical framework for test-time adaptation (TTA) under non-stationary streams, introducing recovery complexity and TTA learnability to measure post-shift adaptation speed and long-term reliability. It derives matching lower and upper bounds, revealing fundamental limits and an adaptivity-information trade-off.
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 $(ε,δ)$-Recovery Complexity and $(ε,ρ)$-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.