테스트 시간 적응의 학습 가능성에 대한 연구: 복구 복잡성 관점

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

테스트 시간 적응(TTA)은 레이블이 없는 데이터를 필요로 하지 않으면서 모델을 조정하여 비정상적인 테스트 데이터 스트림에서 안정적인 성능을 유지하는 것을 목표로 합니다. 경험적으로 성공적이지만, TTA의 학습 가능성은 비정상적인 데이터 스트림 하에서 여전히 탐구되지 않았습니다. 주요 과제는 TTA의 목적과 일치하고 지속적으로 변화하는 분포 변화와 내재된 정보 제약을 모두 포괄하는 체계적인 이론적 프레임워크가 부족하다는 것입니다. 이러한 격차를 해소하기 위해, 우리는 TTA의 학습 가능성을 연구하기 위한 최초의 이론적 프레임워크를 제안하고 $(ε,δ)$-복구 복잡성과 $(ε,ρ)$-TTA 학습 가능성을 소개합니다. 복구 복잡성은 목표 수준 이하로 초과 위험을 유지하는 데 필요한 시간을 측정하며, TTA 학습 가능성으로 확장되어 TTA의 장기적인 신뢰성을 측정합니다. 이 프레임워크 내에서, 우리는 비정상적인 테스트 데이터 스트림에 대한 새로운 이산적 근사치를 도입하여 점진적 및 급격한 변화 모두에 대한 통일되고 다루기 쉬운 분석을 가능하게 합니다. 우리는 복구 복잡성에 대한 순서 기반의 하한 및 상한 경계를 도출하여 TTA의 기본적인 한계와 내재적인 적응성-정보 간의 절충 관계를 밝힙니다. 이러한 결과는 후회 기반 분석을 보완하는 TTA에 대한 통일된 학습 가능성을 제공합니다.

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.