# Simpler PAC-Bayesian Bounds for Hostile Data

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2016.

## Built on by (most cited first, 30 of 46)

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [A Rigorous Link between Deep Ensembles and (Variational) Bayesian Methods](https://mlsanity.com/paper/2305.15027/) (2023)
- [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)
- [How Tight Can PAC-Bayes be in the Small Data Regime?](https://mlsanity.com/paper/2106.03542/) (2021)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Online PAC-Bayes Learning](https://mlsanity.com/paper/2206.00024/) (2022)
- [Position: Understanding LLMs Requires More Than Statistical Generalization](https://mlsanity.com/paper/2405.01964/) (2024)
- [On PAC-Bayesian reconstruction guarantees for VAEs](https://mlsanity.com/paper/2202.11455/) (2022)
- [Integral Probability Metrics PAC-Bayes Bounds](https://mlsanity.com/paper/2207.00614/) (2022)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [Instance-Dependent Generalization Bounds via Optimal Transport](https://mlsanity.com/paper/2211.01258/) (2022)
- [Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2102.02016/) (2021)
- [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023)
- [Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practice](https://mlsanity.com/paper/2211.07206/) (2022)
- [Change of measure through the Legendre transform](https://mlsanity.com/paper/2202.05568/) (2022)
- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [Shedding a PAC-Bayesian Light on Adaptive Sliced-Wasserstein Distances](https://mlsanity.com/paper/2206.03230/) (2022)
- [Stopping Criterion for Active Learning Based on Error Stability](https://mlsanity.com/paper/2104.01836/) (2021)
- [On the Importance of Gradient Norm in PAC-Bayesian Bounds](https://mlsanity.com/paper/2210.06143/) (2022)
- [Improving Generalization of Complex Models under Unbounded Loss Using PAC-Bayes Bounds](https://mlsanity.com/paper/2305.19243/) (2023)
- [Tight PAC-Bayesian Risk Certificates for Contrastive Learning](https://mlsanity.com/paper/2412.03486/) (2024)
- [Comparing Comparators in Generalization Bounds](https://mlsanity.com/paper/2310.10534/) (2023)
- [PAC-Bayesian Learning of Optimization Algorithms](https://mlsanity.com/paper/2210.11113/) (2022)
- [PAC-Bayesian bounds for learning LTI-ss systems with input from empirical loss](https://mlsanity.com/paper/2303.16816/) (2023)
- [Better-than-KL PAC-Bayes Bounds](https://mlsanity.com/paper/2402.09201/) (2024)
- [Generalization and Robustness of the Tilted Empirical Risk](https://mlsanity.com/paper/2409.19431/) (2024)
- [How good is PAC-Bayes at explaining generalisation?](https://mlsanity.com/paper/2503.08231/) (2025)
- [Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisation](https://mlsanity.com/paper/2304.07048/) (2023)

## Abstract (arXiv)

PAC-Bayesian learning bounds are of the utmost interest to the learning community. Their role is to connect the generalization ability of an aggregation distribution ρ to its empirical risk and to its Kullback-Leibler divergence with respect to some prior distribution π. Unfortunately, most of the available bounds typically rely on heavy assumptions such as boundedness and independence of the observations. This paper aims at relaxing these constraints and provides PAC-Bayesian learning bounds that hold for dependent, heavy-tailed observations (hereafter referred to as hostile data). In these bounds the Kullack-Leibler divergence is replaced with a general version of Csisz'ar's f-divergence. We prove a general PAC-Bayesian bound, and show how to use it in various hostile settings.