Learning via Wasserstein-Based High Probability Generalisation Bounds
arXiv:2306.04375
Abstract
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.
Accepted to NeurIPS 2023
References in corpus (19)
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- Exponential inequalities for self-normalized martingales with applications
- A Note on the PAC Bayesian Theorem
- On the properties of variational approximations of Gibbs posteriors
- Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression
- PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales
- Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms
- PAC-Bayesian Lifelong Learning For Multi-Armed Bandits
- PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization
- A unified recipe for deriving (time-uniform) PAC-Bayes bounds
- Generalization Bounds via Convex Analysis
- Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practice
- No-Regret Reinforcement Learning with Heavy-Tailed Rewards
- Integral Probability Metrics PAC-Bayes Bounds
- Bayes meets Bernstein at the Meta Level: an Analysis of Fast Rates in Meta-Learning with PAC-Bayes
- Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound
- Tighter PAC-Bayes Bounds Through Coin-Betting
- Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisation
- PAC-Bayesian Offline Contextual Bandits With Guarantees