The Bayesian Stability Zoo
This work provides a systematic taxonomy to clarify stability notions in learning theory, which is incremental but useful for researchers in the field.
The paper establishes equivalences between multiple definitions of stability in learning theory, showing that distribution-dependent and distribution-independent Bayesian stability encompass concepts like differential privacy and replicability, while also proving boosting results to amplify stability.
We show that many definitions of stability found in the learning theory literature are equivalent to one another. We distinguish between two families of definitions of stability: distribution-dependent and distribution-independent Bayesian stability. Within each family, we establish equivalences between various definitions, encompassing approximate differential privacy, pure differential privacy, replicability, global stability, perfect generalization, TV stability, mutual information stability, KL-divergence stability, and Rényi-divergence stability. Along the way, we prove boosting results that enable the amplification of the stability of a learning rule. This work is a step towards a more systematic taxonomy of stability notions in learning theory, which can promote clarity and an improved understanding of an array of stability concepts that have emerged in recent years.