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 distributional non-stationarity remains unexplored. A key challenge is lacking 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 characterizing the learnability of TTA, introducing the notions of $(\epsilon,\delta)$-Recovery Complexity and $(\epsilon,\rho)$-TTA Learnability. Recovery complexity quantifies the minimal time required for a TTA algorithm to recover to a target excess risk following a distribution shift, and is further generalized to define $(\epsilon,\rho)$-TTA Learnability, which measures the long-term reliability of TTA algorithms over non-stationary data streams. Within this framework, we introduce a novel temporally dependent discrete surrogate method that models complex non-stationary test streams, enabling a unified and tractable analysis of both gradual and abrupt distribution shifts. We derive order-wise matching lower and upper bounds on recovery complexity through information-theoretic and optimization-based analysis. Our results uncover fundamental limits of TTA, highlight the intrinsic adaptivity-information trade-off of TTA algorithms, and provide the first unified learnability guarantees that go beyond regret-based perspectives.