mlsanityData to 7 Oct 2026

PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales

arXiv 2210.00928 ↗First posted 3 Oct 2022stat.ML cs.LG math.STcited by 23

Not on the map. Why?

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.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 25 of its 68 references that are in the map. First posted on arXiv 3 Oct 2022.

Builds on

25 of 68 references.

References · 25

  1. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  2. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  3. 2019A Primer on PAC-Bayesian Learningcited by 130
  4. 2015On the properties of variational approximations of Gibbs posteriorscited by 121
  5. 2020Tighter risk certificates for neural networkscited by 112
  6. 2016PAC-Bayesian Theory Meets Bayesian Inferencecited by 87
  7. 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
  8. 2016A Strongly Quasiconvex PAC-Bayesian Boundcited by 54
  9. 2016Simpler PAC-Bayesian Bounds for Hostile Datacited by 45
  10. 2020PAC-Bayes unleashed: generalisation bounds with unbounded lossescited by 43
  11. 2019Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networkscited by 38
  12. 2019PAC-Bayes Un-Expected Bernstein Inequalitycited by 36
13 more
  1. 2019PAC-Bayes with Backpropcited by 36
  2. 2020Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networkscited by 29
  3. 2022Non-Vacuous Generalisation Bounds for Shallow Neural Networkscited by 22
  4. 2022Online PAC-Bayes Learningcited by 22
  5. 2021Learning PAC-Bayes Priors for Probabilistic Neural Networkscited by 21
  6. 2022On PAC-Bayesian reconstruction guarantees for VAEscited by 20
  7. 2021On Margins and Derandomisation in PAC-Bayescited by 19
  8. 2019PAC-Bayes under potentially heavy tailscited by 16
  9. 2019Efron-Stein PAC-Bayesian Inequalitiescited by 15
  10. 2022Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variablescited by 11
  11. 2022Change of measure through the Legendre transformcited by 10
  12. 2022On Margins and Generalisation for Voting Classifierscited by 7
  13. 2015PAC-Bayesian High Dimensional Bipartite Rankingcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 8; 2024: 8; 2025: 3; 2026: 3.

23 papers.

Sort:

  1. 2023MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splittingcited by 33
  2. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  3. 2024A PAC-Bayesian Link Between Generalisation and Flat Minimacited by 13
  4. 2023Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixturescited by 12
  5. 2023Learning via Wasserstein-Based High Probability Generalisation Boundscited by 11
  6. 2024PAC-Bayes-Chernoff bounds for unbounded lossescited by 9
  7. 2022PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparisoncited by 7
  8. 2024Generalization bounds for mixing processes via delayed online-to-PAC conversionscited by 7
  9. 2025Anytime-valid, Bayes-assisted, Prediction-Powered Inferencecited by 7
  10. 2023Time-Uniform Confidence Spheres for Means of Random Vectorscited by 6
  11. 2023Comparing Comparators in Generalization Boundscited by 5
  12. 2024Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Losscited by 4
11 more
  1. 2024Generalization and Robustness of the Tilted Empirical Riskcited by 4
  2. 2024Gentle Local Robustness implies Generalizationcited by 4
  3. 2023Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisationcited by 3
  4. 2024Data-dependent and Oracle Bounds on Forgetting in Continual Learningcited by 3
  5. 2025PAC-Bayes Bounds for Multivariate Linear Regression and Linear Autoencoderscited by 3
  6. 2023Federated Learning with Nonvacuous Generalisation Boundscited by 2
  7. 2025Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained modelscited by 2
  8. 2026PAC-Bayesian Reconstruction Guarantees for Time Series Variational Autoencoderscited by 1
  9. 2024A note on generalization bounds for losses with finite momentscited by 0
  10. 2026Information-Theoretic Generalization Bounds for Sequential Decision Makingcited by 0
  11. 2026A PAC-Bayesian View of Generalisation for Physics-Informed Machine Learningcited by 0