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

arXiv: https://arxiv.org/abs/2605.28057 · HTML: https://mlsanity.com/paper/2605.28057/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 49 references that are in the map.
- First posted on arXiv 27 May 2026.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Benchmarking Neural Network Robustness to Common Corruptions and Perturbations](https://mlsanity.com/paper/1903.12261/) (2019)
- [In Search of Lost Domain Generalization](https://mlsanity.com/paper/2007.01434/) (2020)
- [Continual Test-Time Domain Adaptation](https://mlsanity.com/paper/2203.13591/) (2022)
- [Efficient Test-Time Model Adaptation without Forgetting](https://mlsanity.com/paper/2204.02610/) (2022)
- [Towards Stable Test-Time Adaptation in Dynamic Wild World](https://mlsanity.com/paper/2302.12400/) (2023)
- [Test-Time Prompt Tuning for Zero-Shot Generalization in Vision-Language Models](https://mlsanity.com/paper/2209.07511/) (2022)
- [A Comprehensive Survey on Test-Time Adaptation under Distribution Shifts](https://mlsanity.com/paper/2303.15361/) (2023)
- [Parameter-free Online Test-time Adaptation](https://mlsanity.com/paper/2201.05718/) (2022)
- [Robust Test-Time Adaptation in Dynamic Scenarios](https://mlsanity.com/paper/2303.13899/) (2023)
- [NOTE: Robust Continual Test-time Adaptation Against Temporal Correlation](https://mlsanity.com/paper/2208.05117/) (2022)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [A Unified View of Label Shift Estimation](https://mlsanity.com/paper/2003.07554/) (2020)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [On Pitfalls of Test-Time Adaptation](https://mlsanity.com/paper/2306.03536/) (2023)
- [Beyond Model Adaptation at Test Time: A Survey](https://mlsanity.com/paper/2411.03687/) (2024)
- [Test-Time Learning for Large Language Models](https://mlsanity.com/paper/2505.20633/) (2025)
- [AdaNPC: Exploring Non-Parametric Classifier for Test-Time Adaptation](https://mlsanity.com/paper/2304.12566/) (2023)
- [In Search of Lost Online Test-time Adaptation: A Survey](https://mlsanity.com/paper/2310.20199/) (2023)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approach](https://mlsanity.com/paper/2408.07511/) (2024)
- [Persistent Test-time Adaptation in Recurring Testing Scenarios](https://mlsanity.com/paper/2311.18193/) (2023)
- [Active Test-Time Adaptation: Theoretical Analyses and An Algorithm](https://mlsanity.com/paper/2404.05094/) (2024)
- [A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning](https://mlsanity.com/paper/2510.15444/) (2025)
- [Lifting Traces to Logic: Programmatic Skill Induction with Neuro-Symbolic Learning for Long-Horizon Agentic Tasks](https://mlsanity.com/paper/2605.01293/) (2026)
- [Fully Test-time Adaptation for Tabular Data](https://mlsanity.com/paper/2412.10871/) (2024)
- [Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability](https://mlsanity.com/paper/2506.10616/) (2025)
- [VT-Bench: A Unified Benchmark for Visual-Tabular Multi-Modal Learning](https://mlsanity.com/paper/2605.08146/) (2026)
- [Quantitative Estimation of Target Task Performance from Unsupervised Pretext Task in Semi/Self-Supervised Learning](https://mlsanity.com/paper/2508.07299/) (2025)

## Built on by (most cited first, 2 of 2)

- [When is Test-Time Adaptation Identifiable From Unlabeled Evidence?](https://mlsanity.com/paper/2609.11235/) (2026)
- [Gradient-Free Warm-Start Library Recovery: an Amortized-Regret Separation](https://mlsanity.com/paper/2606.21253/) (2026)

## Abstract (arXiv)

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.