# Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage

arXiv: https://arxiv.org/abs/1912.01439 · HTML: https://mlsanity.com/paper/1912.01439/

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2019.

## Built on by (most cited first, 30 of 48)

- [Information-theoretic generalization bounds for black-box learning algorithms](https://mlsanity.com/paper/2110.01584/) (2021)
- [Tighter expected generalization error bounds via Wasserstein distance](https://mlsanity.com/paper/2101.09315/) (2021)
- [Generalization Bounds via Convex Analysis](https://mlsanity.com/paper/2202.04985/) (2022)
- [Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms](https://mlsanity.com/paper/2203.02474/) (2022)
- [An Information-theoretical Approach to Semi-supervised Learning under Covariate-shift](https://mlsanity.com/paper/2202.12123/) (2022)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [On Rademacher Complexity-based Generalization Bounds for Deep Learning](https://mlsanity.com/paper/2208.04284/) (2022)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [Characterizing and Understanding the Generalization Error of Transfer Learning with Gibbs Algorithm](https://mlsanity.com/paper/2111.01635/) (2021)
- [Empirical Risk Minimization with Relative Entropy Regularization](https://mlsanity.com/paper/2211.06617/) (2022)
- [Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2102.02016/) (2021)
- [Information-Theoretic Characterization of the Generalization Error for Iterative Semi-Supervised Learning](https://mlsanity.com/paper/2110.00926/) (2021)
- [Tighter Expected Generalization Error Bounds via Convexity of Information Measures](https://mlsanity.com/paper/2202.12150/) (2022)
- [Chained Generalisation Bounds](https://mlsanity.com/paper/2203.00977/) (2022)
- [On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregation](https://mlsanity.com/paper/2306.12380/) (2023)
- [Information-Theoretic Generalization Bounds for Deep Neural Networks](https://mlsanity.com/paper/2404.03176/) (2024)
- [Generalization Error Bounds on Deep Learning with Markov Datasets](https://mlsanity.com/paper/2201.11059/) (2021)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [Improved Information Theoretic Generalization Bounds for Distributed and Federated Learning](https://mlsanity.com/paper/2202.02423/) (2022)
- [f-divergences and their applications in lossy compression and bounding generalization error](https://mlsanity.com/paper/2206.11042/) (2022)
- [Finite Littlestone Dimension Implies Finite Information Complexity](https://mlsanity.com/paper/2206.13257/) (2022)
- [From Generalisation Error to Transportation-cost Inequalities and Back](https://mlsanity.com/paper/2202.03956/) (2022)
- [Learning Algorithm Generalization Error Bounds via Auxiliary Distributions](https://mlsanity.com/paper/2210.00483/) (2022)
- [A unified framework for information-theoretic generalization bounds](https://mlsanity.com/paper/2305.11042/) (2023)
- [How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm?](https://mlsanity.com/paper/2210.08188/) (2022)
- [The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms](https://mlsanity.com/paper/2411.12030/) (2024)
- [Global Convergence Rate of Deep Equilibrium Models with General Activations](https://mlsanity.com/paper/2302.05797/) (2023)
- [Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized KL information](https://mlsanity.com/paper/2107.13656/) (2021)
- [Formal limitations of sample-wise information-theoretic generalization bounds](https://mlsanity.com/paper/2205.06915/) (2022)
- [An Information-Theoretic Framework for Out-of-Distribution Generalization with Applications to Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2403.19895/) (2024)

## Abstract (arXiv)

In this work, the probability of an event under some joint distribution is bounded by measuring it with the product of the marginals instead (which is typically easier to analyze) together with a measure of the dependence between the two random variables. These results find applications in adaptive data analysis, where multiple dependencies are introduced and in learning theory, where they can be employed to bound the generalization error of a learning algorithm. Bounds are given in terms of Sibson's Mutual Information, α-Divergences, Hellinger Divergences, and f-Divergences. A case of particular interest is the Maximal Leakage (or Sibson's Mutual Information of order infinity), since this measure is robust to post-processing and composes adaptively. The corresponding bound can be seen as a generalization of classical bounds, such as Hoeffding's and McDiarmid's inequalities, to the case of dependent random variables.