# Still no free lunches: the price to pay for tighter PAC-Bayes bounds

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

## Key facts

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

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

- [Bayesian Learning for Neural Networks: an algorithmic survey](https://mlsanity.com/paper/2211.11865/) (2022)
- [Online PAC-Bayes Learning](https://mlsanity.com/paper/2206.00024/) (2022)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Empirical Risk Minimization with Relative Entropy Regularization](https://mlsanity.com/paper/2211.06617/) (2022)
- [On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregation](https://mlsanity.com/paper/2306.12380/) (2023)
- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [Empirical Risk Minimization with Relative Entropy Regularization: Optimality and Sensitivity Analysis](https://mlsanity.com/paper/2202.04385/) (2022)
- [The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms](https://mlsanity.com/paper/2411.12030/) (2024)
- [A General framework for PAC-Bayes Bounds for Meta-Learning](https://mlsanity.com/paper/2206.05454/) (2022)
- [Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysis](https://mlsanity.com/paper/2504.02957/) (2025)
- [On Certified Generalization in Structured Prediction](https://mlsanity.com/paper/2306.09112/) (2023)
- [A note on generalization bounds for losses with finite moments](https://mlsanity.com/paper/2403.16681/) (2024)
- [Empirical Risk Minimization with f-Divergence Regularization](https://mlsanity.com/paper/2601.13191/) (2026)
- [Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities](https://mlsanity.com/paper/2602.07999/) (2026)

## Abstract (arXiv)

"No free lunch" results state the impossibility of obtaining meaningful bounds on the error of a learning algorithm without prior assumptions and modelling. Some models are expensive (strong assumptions, such as as subgaussian tails), others are cheap (simply finite variance). As it is well known, the more you pay, the more you get: in other words, the most expensive models yield the more interesting bounds. Recent advances in robust statistics have investigated procedures to obtain tight bounds while keeping the cost minimal. The present paper explores and exhibits what the limits are for obtaining tight PAC-Bayes bounds in a robust setting for cheap models, addressing the question: is PAC-Bayes good value for money?