An Information-Theoretic Framework for Stability-Based Generalization Bounds

We derive a family of novel bounds on the expected generalization error of learning algorithms. Our bounds simultaneously leverage two properties of the learning algorithm: 1) algorithmic stability and 2) information measures of the dependence between the training data and the learned hypothesis. Our approach establishes a general bound based on $f$-divergences and allows for various specializations under a series of new stability conditions. These conditions are weaker than established notions of stability from the literature which makes them applicable to a wider range of learning scenarios, especially when the loss function is unbounded. When evaluated with several concrete examples, our bounds strictly improve upon both the classical stability-based and information-theoretic bounds.