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.
arXiv commentAccepted to NeurIPS 2023
References in corpus (31)
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- Information-theoretic analysis of generalization capability of 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
- Constrained Deep Networks: Lagrangian Optimization via Log-Barrier Extensions
- Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression
- Simpler PAC-Bayesian Bounds for Hostile Data
- Tighter risk certificates for neural networks
- PAC-Bayesian Bound for the Conditional Value at Risk
- Bridging the Gap Between Practice and PAC-Bayes Theory in Few-Shot Meta-Learning
- Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms
- PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales
- Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks
- PAC-Bayes Un-Expected Bernstein Inequality
- 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
- Novel Change of Measure Inequalities with Applications to PAC-Bayesian Bounds and Monte Carlo Estimation
- PAC-Bayesian Contrastive Unsupervised Representation Learning
- On Margins and Derandomisation in PAC-Bayes
- No-Regret Reinforcement Learning with Heavy-Tailed Rewards
- Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practice
- An Optimal Transport View on Generalization
- Integral Probability Metrics PAC-Bayes Bounds
- Bayes meets Bernstein at the Meta Level: an Analysis of Fast Rates in Meta-Learning with PAC-Bayes
- Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisation
- Tighter PAC-Bayes Bounds Through Coin-Betting
- Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound
- PAC-Bayesian Offline Contextual Bandits With Guarantees