# From Generalisation Error to Transportation-cost Inequalities and Back

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 16 references that are in the map.
- First posted on arXiv 8 Feb 2022.

## Builds on (most cited first, 5 of 5)

- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)

## Built on by (most cited first, 6 of 6)

- [On the Generalization for Transfer Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2207.05377/) (2022)
- [Asymmetry of the Relative Entropy in the Regularization of Empirical Risk Minimization](https://mlsanity.com/paper/2410.02833/) (2024)
- [Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problem](https://mlsanity.com/paper/2305.00876/) (2023)
- [Generalization Bounds via Conditional f-Information](https://mlsanity.com/paper/2410.22887/) (2024)
- [Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakage](https://mlsanity.com/paper/2302.14518/) (2023)
- [Bounds on the Excess Minimum Risk via Generalized Information Divergence Measures](https://mlsanity.com/paper/2505.24117/) (2025)

## Abstract (arXiv)

In this work, we connect the problem of bounding the expected generalisation error with transportation-cost inequalities. Exposing the underlying pattern behind both approaches we are able to generalise them and go beyond Kullback-Leibler Divergences/Mutual Information and sub-Gaussian measures. In particular, we are able to provide a result showing the equivalence between two families of inequalities: one involving functionals and one involving measures. This result generalises the one proposed by Bobkov and G"otze that connects transportation-cost inequalities with concentration of measure. Moreover, it allows us to recover all standard generalisation error bounds involving mutual information and to introduce new, more general bounds, that involve arbitrary divergence measures.