mlsanityData to 7 Oct 2026

User-friendly introduction to PAC-Bayes bounds

arXiv 2110.11216 ↗First posted 21 Oct 2021stat.ML cs.LG math.STcited by 234

Not on the map. Why?

Abstract (arXiv)

Aggregated predictors are obtained by making a set of basic predictors vote according to some weights, that is, to some probability distribution. Randomized predictors are obtained by sampling in a set of basic predictors, according to some prescribed probability distribution. Thus, aggregated and randomized predictors have in common that they are not defined by a minimization problem, but by a probability distribution on the set of predictors. In statistical learning theory, there is a set of tools designed to understand the generalization ability of such procedures: PAC-Bayesian or PAC-Bayes bounds. Since the original PAC-Bayes bounds of D. McAllester, these tools have been considerably improved in many directions (we will for example describe a simplified version of the localization technique of O. Catoni that was missed by the community, and later rediscovered as "mutual information bounds"). Very recently, PAC-Bayes bounds received a considerable attention: for example there was workshop on PAC-Bayes at NIPS 2017, "(Almost) 50 Shades of Bayesian Learning: PAC-Bayesian trends and insights", organized by B. Guedj, F. Bach and P. Germain. One of the reason of this recent success is the successful application of these bounds to neural networks by G. Dziugaite and D. Roy. An elementary introduction to PAC-Bayes theory is still missing. This is an attempt to provide such an introduction.

Key facts. Cited by 234 papers in the map (data through 7 Oct 2026). Builds on 83 of its 206 references that are in the map. First posted on arXiv 21 Oct 2021.

Builds on

83 of 206 references.

References · 83

  1. 2016Variational Inference: A Review for Statisticianscited by 1,466
  2. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,404
  3. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  4. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  5. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  6. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  7. 2013A General Framework for Updating Belief Distributionscited by 172
  8. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  9. 2019A Primer on PAC-Bayesian Learningcited by 130
  10. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 125
  11. 2015On the properties of variational approximations of Gibbs posteriorscited by 121
  12. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
38 more
  1. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  2. 2020Tighter risk certificates for neural networkscited by 112
  3. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  4. 2021The Bayesian Learning Rulecited by 95
  5. 2014Inconsistency of Bayesian Inference for Misspecified Linear Models, and a Proposal for Repairing Itcited by 92
  6. 2016PAC-Bayesian Theory Meets Bayesian Inferencecited by 87
  7. 2020PACOH: Bayes-Optimal Meta-Learning with PAC-Guaranteescited by 85
  8. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  9. 2017Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priorscited by 81
  10. 2017Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theorycited by 76
  11. 2013A PAC-Bayesian bound for Lifelong Learningcited by 69
  12. 2017Concentration of tempered posteriors and of their variational approximationscited by 66
  13. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
  14. 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
  15. 2019Normalized Flat Minima: Exploring Scale Invariant Definition of Flat Minima for Neural Networks using PAC-Bayesian Analysiscited by 58
  16. 2016A Strongly Quasiconvex PAC-Bayesian Boundcited by 54
  17. 2015Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithmcited by 50
  18. 2016Simpler PAC-Bayesian Bounds for Hostile Datacited by 45
  19. 2017Convergence Rates of Variational Posterior Distributionscited by 45
  20. 2013A PAC-Bayesian Tutorial with A Dropout Boundcited by 43
  21. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  22. 2020PAC-Bayes unleashed: generalisation bounds with unbounded lossescited by 43
  23. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  24. 2019Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networkscited by 38
  25. 2019PAC-Bayes Un-Expected Bernstein Inequalitycited by 36
  26. 2019PAC-Bayes with Backpropcited by 36
  27. 2018The Many Faces of Exponential Weights in Online Learningcited by 33
  28. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  29. 2015A New PAC-Bayesian Perspective on Domain Adaptationcited by 29
  30. 2017A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descentcited by 29
  31. 2020Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networkscited by 29
  32. 2021PAC-Bayes Information Bottleneckcited by 28
  33. 2016Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayescited by 27
  34. 2019Convergence Rates of Variational Inference in Sparse Deep Learningcited by 27
  35. 2015Calibrating general posterior credible regionscited by 26
  36. 2020A Limitation of the PAC-Bayes Frameworkcited by 24
  37. 2021How Tight Can PAC-Bayes be in the Small Data Regime?cited by 24
  38. 2019On the Generalization Gap in Reparameterizable Reinforcement Learningcited by 21

50 most cited of 83 All 83 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 38; 2023: 51; 2024: 55; 2025: 48; 2026: 39.

234 papers.

Sort:

By area:

  1. 2023The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learningcited by 63
  2. 2022Bayesian Model Selection, the Marginal Likelihood, and Generalizationcited by 56
  3. 2025Deep Learning is Not So Mysterious or Differentcited by 55
  4. 2022SAM as an Optimal Relaxation of Bayescited by 40
  5. 2022Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guaranteescited by 34
  6. 2023MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splittingcited by 33
  7. 2023Learning to Warm-Start Fixed-Point Optimization Algorithmscited by 32
  8. 2023A Rigorous Link between Deep Ensembles and (Variational) Bayesian Methodscited by 31
  9. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
  10. 2022Generalization Bounds via Convex Analysiscited by 27
  11. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 27
  12. 2024Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methodscited by 27
38 more
  1. 2023A unified recipe for deriving (time-uniform) PAC-Bayes boundscited by 25
  2. 2022PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingalescited by 23
  3. 2022Non-Vacuous Generalisation Bounds for Shallow Neural Networkscited by 22
  4. 2022Online PAC-Bayes Learningcited by 22
  5. 2022Bayesian Learning for Neural Networks: an algorithmic surveycited by 22
  6. 2022On PAC-Bayesian reconstruction guarantees for VAEscited by 20
  7. 2022Integral Probability Metrics PAC-Bayes Boundscited by 19
  8. 2022PAC-Bayesian Offline Contextual Bandits With Guaranteescited by 19
  9. 2024How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teacherscited by 18
  10. 2024Policy Adaptation via Language Optimization: Decomposing Tasks for Few-Shot Imitationcited by 18
  11. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  12. 2023Statistical Guarantees for Variational Autoencoders using PAC-Bayesian Theorycited by 16
  13. 2024Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learningcited by 16
  14. 2023Exponential Smoothing for Off-Policy Learningcited by 15
  15. 2023Decentralized SGD and Average-direction SAM are Asymptotically Equivalentcited by 15
  16. 2023Importance-Weighted Offline Learning Done Rightcited by 15
  17. 2024Towards a Theoretical Understanding of Synthetic Data in LLM Post-Training: A Reverse-Bottleneck Perspectivecited by 15
  18. 2023Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approachcited by 14
  19. 2023Tighter PAC-Bayes Bounds Through Coin-Bettingcited by 13
  20. 2023PAC-Bayesian Generalization Bounds for Adversarial Generative Modelscited by 13
  21. 2024A PAC-Bayesian Link Between Generalisation and Flat Minimacited by 13
  22. 2023Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixturescited by 12
  23. 2024A Survey to Recent Progress Towards Understanding In-Context Learningcited by 12
  24. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  25. 2022Adversarial robustness of sparse local Lipschitz predictorscited by 11
  26. 2022Evaluated CMI Bounds for Meta Learning: Tightness and Expressivenesscited by 11
  27. 2022Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practicecited by 11
  28. 2022Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal Statescited by 11
  29. 2024Forgetting, Ignorance or Myopia: Revisiting Key Challenges in Online Continual Learningcited by 11
  30. 2021Progress in Self-Certified Neural Networkscited by 10
  31. 2022Change of measure through the Legendre transformcited by 10
  32. 2022Chained Generalisation Boundscited by 10
  33. 2023Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithmcited by 10
  34. 2023A path-norm toolkit for modern networks: consequences, promises and challengescited by 10
  35. 2024More Flexible PAC-Bayesian Meta-Learning by Learning Learning Algorithmscited by 10
  36. 2025Uncertainty-Aware Decoding with Minimum Bayes Riskcited by 10
  37. 2022Robust Bayesian Learning for Reliable Wireless AI: Framework and Applicationscited by 9
  38. 2022Generalisation under gradient descent via deterministic PAC-Bayescited by 9

50 most cited of 234 All 234 (JSON)