# Efron-Stein PAC-Bayesian Inequalities

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2019.

## Built on by (most cited first, 16 of 16)

- [Non-Vacuous Generalization Bounds for Large Language Models](https://mlsanity.com/paper/2312.17173/) (2023)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [On PAC-Bayesian reconstruction guarantees for VAEs](https://mlsanity.com/paper/2202.11455/) (2022)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Exponential Smoothing for Off-Policy Learning](https://mlsanity.com/paper/2305.15877/) (2023)
- [PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison](https://mlsanity.com/paper/2211.16110/) (2022)
- [Improving Generalization of Complex Models under Unbounded Loss Using PAC-Bayes Bounds](https://mlsanity.com/paper/2305.19243/) (2023)
- [PAC-Bayesian Lifelong Learning For Multi-Armed Bandits](https://mlsanity.com/paper/2203.03303/) (2022)
- [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)
- [Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezing](https://mlsanity.com/paper/2502.10826/) (2025)
- [Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisation](https://mlsanity.com/paper/2304.07048/) (2023)
- [Federated Learning with Nonvacuous Generalisation Bounds](https://mlsanity.com/paper/2310.11203/) (2023)
- [Tighter Generalisation Bounds via Interpolation](https://mlsanity.com/paper/2402.05101/) (2024)
- [A note on a confidence bound of Kuzborskij and Szepesv'ari](https://mlsanity.com/paper/2101.04671/) (2021)
- [On-Policy and Off-Policy Learning for Large Action Spaces](https://mlsanity.com/paper/2607.28408/) (2026)

## Abstract (arXiv)

We prove semi-empirical concentration inequalities for random variables which are given as possibly nonlinear functions of independent random variables. These inequalities describe concentration of random variable in terms of the data/distribution-dependent Efron-Stein (ES) estimate of its variance and they do not require any additional assumptions on the moments. In particular, this allows us to state semi-empirical Bernstein type inequalities for general functions of unbounded random variables, which gives user-friendly concentration bounds for cases where related methods (e.g. bounded differences) might be more challenging to apply. We extend these results to Efron-Stein PAC-Bayesian inequalities which hold for arbitrary probability kernels that define a random, data-dependent choice of the function of interest. Finally, we demonstrate a number of applications, including PAC-Bayesian generalization bounds for unbounded loss functions, empirical Bernstein type generalization bounds, new truncation-free bounds for off-policy evaluation with Weighted Importance Sampling (WIS), and off-policy PAC-Bayesian learning with WIS.