# Learning via Wasserstein-Based High Probability Generalisation Bounds

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 77 references that are in the map.
- First posted on arXiv 7 Jun 2023.

## Builds on (most cited first, 30 of 45)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [On the properties of variational approximations of Gibbs posteriors](https://mlsanity.com/paper/1506.04091/) (2015)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees](https://mlsanity.com/paper/2002.05551/) (2020)
- [Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory](https://mlsanity.com/paper/1711.01244/) (2017)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [Simpler PAC-Bayesian Bounds for Hostile Data](https://mlsanity.com/paper/1610.07193/) (2016)
- [PAC-Bayes unleashed: generalisation bounds with unbounded losses](https://mlsanity.com/paper/2006.07279/) (2020)
- [Tighter expected generalization error bounds via Wasserstein distance](https://mlsanity.com/paper/2101.09315/) (2021)
- [Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks](https://mlsanity.com/paper/1905.10259/) (2019)
- [PAC-Bayes Un-Expected Bernstein Inequality](https://mlsanity.com/paper/1905.13367/) (2019)
- [Constrained Deep Networks: Lagrangian Optimization via Log-Barrier Extensions](https://mlsanity.com/paper/1904.04205/) (2019)
- [Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability](https://mlsanity.com/paper/2102.06589/) (2021)
- [Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks](https://mlsanity.com/paper/2006.12228/) (2020)
- [Generalization Bounds via Convex Analysis](https://mlsanity.com/paper/2202.04985/) (2022)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [Non-Vacuous Generalisation Bounds for Shallow Neural Networks](https://mlsanity.com/paper/2202.01627/) (2022)
- [Online PAC-Bayes Learning](https://mlsanity.com/paper/2206.00024/) (2022)
- [Bridging the Gap Between Practice and PAC-Bayes Theory in Few-Shot Meta-Learning](https://mlsanity.com/paper/2105.14099/) (2021)
- [PAC-Bayesian Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1910.04464/) (2019)
- [On PAC-Bayesian reconstruction guarantees for VAEs](https://mlsanity.com/paper/2202.11455/) (2022)

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

- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [A PAC-Bayesian Link Between Generalisation and Flat Minima](https://mlsanity.com/paper/2402.08508/) (2024)
- [The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms](https://mlsanity.com/paper/2411.12030/) (2024)
- [How good is PAC-Bayes at explaining generalisation?](https://mlsanity.com/paper/2503.08231/) (2025)
- [Tighter Generalisation Bounds via Interpolation](https://mlsanity.com/paper/2402.05101/) (2024)
- [A note on regularised NTK dynamics with an application to PAC-Bayesian training](https://mlsanity.com/paper/2312.13259/) (2023)
- [Learning via Surrogate PAC-Bayes](https://mlsanity.com/paper/2410.10230/) (2024)
- [Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?](https://mlsanity.com/paper/2509.26149/) (2025)
- [PAC-Bayesian Reinforcement Learning Trains Generalizable Policies](https://mlsanity.com/paper/2510.10544/) (2025)
- [Stability-based Generalization Bounds for Variational Inference](https://mlsanity.com/paper/2502.12353/) (2025)
- [A PAC-Bayesian View of Generalisation for Physics-Informed Machine Learning](https://mlsanity.com/paper/2605.26341/) (2026)
- [Optimal Transport PAC-Bayes Bounds](https://mlsanity.com/paper/2610.16560/) (2026)

## Abstract (arXiv)

Minimising upper bounds on the population risk or the generalisation gap has been widely used in structural risk minimisation (SRM) -- this is in particular at the core of PAC-Bayesian learning. Despite its successes and unfailing surge of interest in recent years, a limitation of the PAC-Bayesian framework is that most bounds involve a Kullback-Leibler (KL) divergence term (or its variations), which might exhibit erratic behavior and fail to capture the underlying geometric structure of the learning problem -- hence restricting its use in practical applications. As a remedy, recent studies have attempted to replace the KL divergence in the PAC-Bayesian bounds with the Wasserstein distance. Even though these bounds alleviated the aforementioned issues to a certain extent, they either hold in expectation, are for bounded losses, or are nontrivial to minimize in an SRM framework. In this work, we contribute to this line of research and prove novel Wasserstein distance-based PAC-Bayesian generalisation bounds for both batch learning with independent and identically distributed (i.i.d.) data, and online learning with potentially non-i.i.d. data. Contrary to previous art, our bounds are stronger in the sense that (i) they hold with high probability, (ii) they apply to unbounded (potentially heavy-tailed) losses, and (iii) they lead to optimizable training objectives that can be used in SRM. As a result we derive novel Wasserstein-based PAC-Bayesian learning algorithms and we illustrate their empirical advantage on a variety of experiments.