# PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales arXiv: https://arxiv.org/abs/2210.00928 ยท HTML: https://mlsanity.com/paper/2210.00928/ ## Key facts - Cited by 24 papers in the map (data through 14 Oct 2026). - Builds on 25 of its 68 references that are in the map. - First posted on arXiv 3 Oct 2022. ## Builds on (most cited first, 25 of 25) - [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017) - [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021) - [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) - [PAC-Bayesian Theory Meets Bayesian Inference](https://mlsanity.com/paper/1605.08636/) (2016) - [PAC-Bayes Analysis Beyond the Usual Bounds](https://mlsanity.com/paper/2006.13057/) (2020) - [A Strongly Quasiconvex PAC-Bayesian Bound](https://mlsanity.com/paper/1608.05610/) (2016) - [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) - [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) - [PAC-Bayes with Backprop](https://mlsanity.com/paper/1908.07380/) (2019) - [Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks](https://mlsanity.com/paper/2006.12228/) (2020) - [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) - [Learning PAC-Bayes Priors for Probabilistic Neural Networks](https://mlsanity.com/paper/2109.10304/) (2021) - [On PAC-Bayesian reconstruction guarantees for VAEs](https://mlsanity.com/paper/2202.11455/) (2022) - [On Margins and Derandomisation in PAC-Bayes](https://mlsanity.com/paper/2107.03955/) (2021) - [PAC-Bayes under potentially heavy tails](https://mlsanity.com/paper/1905.07900/) (2019) - [Efron-Stein PAC-Bayesian Inequalities](https://mlsanity.com/paper/1909.01931/) (2019) - [Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables](https://mlsanity.com/paper/2206.00706/) (2022) - [Change of measure through the Legendre transform](https://mlsanity.com/paper/2202.05568/) (2022) - [On Margins and Generalisation for Voting Classifiers](https://mlsanity.com/paper/2206.04607/) (2022) - [PAC-Bayesian High Dimensional Bipartite Ranking](https://mlsanity.com/paper/1511.02729/) (2015) ## Built on by (most cited first, 24 of 24) - [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023) - [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) - [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023) - [Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures](https://mlsanity.com/paper/2309.14298/) (2023) - [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024) - [Generalization bounds for mixing processes via delayed online-to-PAC conversions](https://mlsanity.com/paper/2406.12600/) (2024) - [PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison](https://mlsanity.com/paper/2211.16110/) (2022) - [Anytime-valid, Bayes-assisted, Prediction-Powered Inference](https://mlsanity.com/paper/2505.18000/) (2025) - [Time-Uniform Confidence Spheres for Means of Random Vectors](https://mlsanity.com/paper/2311.08168/) (2023) - [Comparing Comparators in Generalization Bounds](https://mlsanity.com/paper/2310.10534/) (2023) - [Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss](https://mlsanity.com/paper/2405.14681/) (2024) - [Generalization and Robustness of the Tilted Empirical Risk](https://mlsanity.com/paper/2409.19431/) (2024) - [Gentle Local Robustness implies Generalization](https://mlsanity.com/paper/2412.06381/) (2024) - [Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisation](https://mlsanity.com/paper/2304.07048/) (2023) - [Data-dependent and Oracle Bounds on Forgetting in Continual Learning](https://mlsanity.com/paper/2406.09370/) (2024) - [PAC-Bayes Bounds for Multivariate Linear Regression and Linear Autoencoders](https://mlsanity.com/paper/2512.12905/) (2025) - [Federated Learning with Nonvacuous Generalisation Bounds](https://mlsanity.com/paper/2310.11203/) (2023) - [Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained models](https://mlsanity.com/paper/2503.07325/) (2025) - [PAC-Bayesian Reconstruction Guarantees for Time Series Variational Autoencoders](https://mlsanity.com/paper/2609.05212/) (2026) - [A note on generalization bounds for losses with finite moments](https://mlsanity.com/paper/2403.16681/) (2024) - [Information-Theoretic Generalization Bounds for Sequential Decision Making](https://mlsanity.com/paper/2605.12190/) (2026) - [A PAC-Bayesian View of Generalisation for Physics-Informed Machine Learning](https://mlsanity.com/paper/2605.26341/) (2026) - [On-Policy and Off-Policy Learning for Large Action Spaces](https://mlsanity.com/paper/2607.28408/) (2026) ## Abstract (arXiv) While PAC-Bayes is now an established learning framework for light-tailed losses (e.g., subgaussian or subexponential), its extension to the case of heavy-tailed losses remains largely uncharted and has attracted a growing interest in recent years. We contribute PAC-Bayes generalisation bounds for heavy-tailed losses under the sole assumption of bounded variance of the loss function. Under that assumption, we extend previous results from citetkuzborskij2019efron. Our key technical contribution is exploiting an extention of Markov's inequality for supermartingales. Our proof technique unifies and extends different PAC-Bayesian frameworks by providing bounds for unbounded martingales as well as bounds for batch and online learning with heavy-tailed losses.