aiqbench analysis
This paper establishes the first theoretical framework for test-time adaptation (TTA) by defining recovery complexity and learnability metrics that quantify long-term reliability under non-stationary data streams. By deriving matching lower and upper bounds, the authors reveal fundamental limits on TTA performance and an intrinsic trade-off between adaptivity and information constraints. These findings provide rigorous learnability guarantees that complement existing regret-based analyses, offering a principled basis for evaluating model robustness in evolving environments.
On the Learnability of Test-Time Adaptation: A Recovery Complexity Perspective
arXiv:2605.28057v2 Announce Type: replace Abstract: 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.
Abstract: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 (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2605.28057 [cs.LG]
(or arXiv:2605.28057v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2605.28057 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 269 words
Related coverage
Geometry-Guided Constraint Learning for LLM Safety Classification
arXiv · Jul 23, 2026
Amortized Nonlinear Variable Selection with Prior-Data Fitted Networks
arXiv · Nov 4, 2026
PAC-Causal Learnability: From Identification to Finite-Sample Guarantees
arXiv · Oct 16, 2026
From Perspective to Fisheye Depth Estimation and Open-Vocabulary Segmentation
arXiv · Sep 1, 2026