Is Algorithmic Stability Testable? A Unified Framework under Computational Constraints
This work addresses a foundational issue in machine learning theory for researchers and practitioners, showing that verifying stability is inherently hard across all data types, making it incremental by extending prior impossibility results to broader settings.
The paper tackles the problem of testing algorithmic stability for black-box algorithms under computational constraints, establishing that exhaustive search is the only universally valid method when data is limited, which implies fundamental limits on practical verification.
Algorithmic stability is a central notion in learning theory that quantifies the sensitivity of an algorithm to small changes in the training data. If a learning algorithm satisfies certain stability properties, this leads to many important downstream implications, such as generalization, robustness, and reliable predictive inference. Verifying that stability holds for a particular algorithm is therefore an important and practical question. However, recent results establish that testing the stability of a black-box algorithm is impossible, given limited data from an unknown distribution, in settings where the data lies in an uncountably infinite space (such as real-valued data). In this work, we extend this question to examine a far broader range of settings, where the data may lie in any space -- for example, categorical data. We develop a unified framework for quantifying the hardness of testing algorithmic stability, which establishes that across all settings, if the available data is limited then exhaustive search is essentially the only universally valid mechanism for certifying algorithmic stability. Since in practice, any test of stability would naturally be subject to computational constraints, exhaustive search is impossible and so this implies fundamental limits on our ability to test the stability property for a black-box algorithm.