# Tighter expected generalization error bounds via Wasserstein distance

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 48 references that are in the map.
- First posted on arXiv 22 Jan 2021.

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

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [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)
- [On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning](https://mlsanity.com/paper/1704.00805/) (2017)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [Individually Conditional Individual Mutual Information Bound on Generalization Error](https://mlsanity.com/paper/2012.09922/) (2020)
- [Calibrating Noise to Variance in Adaptive Data Analysis](https://mlsanity.com/paper/1712.07196/) (2017)
- [On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm](https://mlsanity.com/paper/2010.10994/) (2020)
- [Information-Theoretic Understanding of Population Risk Improvement with Model Compression](https://mlsanity.com/paper/1901.09421/) (2019)
- [An Optimal Transport View on Generalization](https://mlsanity.com/paper/1811.03270/) (2018)
- [Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data](https://mlsanity.com/paper/2005.05889/) (2020)

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [On the Generalization of Diffusion Model](https://mlsanity.com/paper/2305.14712/) (2023)
- [Generalization Bounds via Convex Analysis](https://mlsanity.com/paper/2202.04985/) (2022)
- [Single Trajectory Nonparametric Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2202.08311/) (2022)
- [Tighter Information-Theoretic Generalization Bounds from Supersamples](https://mlsanity.com/paper/2302.02432/) (2023)
- [Integral Probability Metrics PAC-Bayes Bounds](https://mlsanity.com/paper/2207.00614/) (2022)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [Information-Theoretic Analysis of Unsupervised Domain Adaptation](https://mlsanity.com/paper/2210.00706/) (2022)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [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)
- [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023)
- [Tighter Expected Generalization Error Bounds via Convexity of Information Measures](https://mlsanity.com/paper/2202.12150/) (2022)
- [On the Generalization for Transfer Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2207.05377/) (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)
- [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)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms](https://mlsanity.com/paper/2411.12030/) (2024)
- [Selective Risk Certification for LLM Outputs via Information-Lift Statistics: PAC-Bayes, Robustness, and Skeleton Design](https://mlsanity.com/paper/2509.12527/) (2025)
- [Learning distinct features helps, provably](https://mlsanity.com/paper/2106.06012/) (2021)
- [Learning Against Distributional Uncertainty: On the Trade-off Between Robustness and Specificity](https://mlsanity.com/paper/2301.13565/) (2023)
- [A General Theory for Compositional Generalization](https://mlsanity.com/paper/2405.11743/) (2024)
- [Generalization Bounds via Conditional f-Information](https://mlsanity.com/paper/2410.22887/) (2024)
- [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)
- [Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisation](https://mlsanity.com/paper/2304.07048/) (2023)

## Abstract (arXiv)

This work presents several expected generalization error bounds based on the Wasserstein distance. More specifically, it introduces full-dataset, single-letter, and random-subset bounds, and their analogues in the randomized subsample setting from Steinke and Zakynthinou [1]. Moreover, when the loss function is bounded and the geometry of the space is ignored by the choice of the metric in the Wasserstein distance, these bounds recover from below (and thus, are tighter than) current bounds based on the relative entropy. In particular, they generate new, non-vacuous bounds based on the relative entropy. Therefore, these results can be seen as a bridge between works that account for the geometry of the hypothesis space and those based on the relative entropy, which is agnostic to such geometry. Furthermore, it is shown how to produce various new bounds based on different information measures (e.g., the lautum information or several f-divergences) based on these bounds and how to derive similar bounds with respect to the backward channel using the presented proof techniques.