A Function-Space Stability Boundary for Generalization in Interpolating Learning Systems
This work addresses a foundational theoretical gap for machine learning researchers, providing insights into generalization mechanisms in modern interpolating systems.
The paper tackles the problem of understanding when algorithmic stability explains generalization in interpolating learning systems, by proposing a function-space stability certificate and showing it predicts generalization differences in experiments, while also proving that stability is not a universal explanation in all interpolating regimes.
Modern learning systems often interpolate training data while still generalizing well, yet it remains unclear when algorithmic stability explains this behavior. We model training as a function-space trajectory and measure sensitivity to single-sample perturbations along this trajectory. We propose a contractive propagation condition and a stability certificate obtained by unrolling the resulting recursion. A small certificate implies stability-based generalization, while we also prove that there exist interpolating regimes with small risk where such contractive sensitivity cannot hold, showing that stability is not a universal explanation. Experiments confirm that certificate growth predicts generalization differences across optimizers, step sizes, and dataset perturbations. The framework therefore identifies regimes where stability explains generalization and where alternative mechanisms must account for success.