mlsanityData to 7 Oct 2026

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

arXiv 1910.04460 ↗First posted 10 Oct 2019cs.LG math.ST stat.MLcited by 14

Not on the map. Why?

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?

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

14 papers.

Sort:

  1. 2022Online PAC-Bayes Learningcited by 22
  2. 2022Bayesian Learning for Neural Networks: an algorithmic surveycited by 22
  3. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  4. 2022Empirical Risk Minimization with Relative Entropy Regularizationcited by 13
  5. 2023On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregationcited by 10
  6. 2024PAC-Bayes-Chernoff bounds for unbounded lossescited by 9
  7. 2022Empirical Risk Minimization with Relative Entropy Regularization: Optimality and Sensitivity Analysiscited by 8
  8. 2024The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithmscited by 5
  9. 2022A General framework for PAC-Bayes Bounds for Meta-Learningcited by 3
  10. 2025Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysiscited by 1
  11. 2023On Certified Generalization in Structured Predictioncited by 0
  12. 2024A note on generalization bounds for losses with finite momentscited by 0
2 more
  1. 2026Empirical Risk Minimization with f-Divergence Regularizationcited by 0
  2. 2026Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalitiescited by 0