Is Algorithmic Stability Testable? A Unified Framework under Computational Constraints

Yuetian Luo, Rina Foygel Barber

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 satisfie…