# User-friendly introduction to PAC-Bayes bounds

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

## Key facts

- Cited by 239 papers in the map (data through 14 Oct 2026).
- Builds on 83 of its 206 references that are in the map.
- First posted on arXiv 21 Oct 2021.

## Builds on (most cited first, 30 of 83)

- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [A General Framework for Updating Belief Distributions](https://mlsanity.com/paper/1306.6430/) (2013)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [On the properties of variational approximations of Gibbs posteriors](https://mlsanity.com/paper/1506.04091/) (2015)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [The Bayesian Learning Rule](https://mlsanity.com/paper/2107.04562/) (2021)
- [Inconsistency of Bayesian Inference for Misspecified Linear Models, and a Proposal for Repairing It](https://mlsanity.com/paper/1412.3730/) (2014)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [PAC-Bayesian Theory Meets Bayesian Inference](https://mlsanity.com/paper/1605.08636/) (2016)
- [PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees](https://mlsanity.com/paper/2002.05551/) (2020)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors](https://mlsanity.com/paper/1712.09376/) (2017)
- [Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory](https://mlsanity.com/paper/1711.01244/) (2017)
- [A PAC-Bayesian bound for Lifelong Learning](https://mlsanity.com/paper/1311.2838/) (2013)
- [Concentration of tempered posteriors and of their variational approximations](https://mlsanity.com/paper/1706.09293/) (2017)
- [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018)
- [PAC-Bayes Analysis Beyond the Usual Bounds](https://mlsanity.com/paper/2006.13057/) (2020)
- [Normalized Flat Minima: Exploring Scale Invariant Definition of Flat Minima for Neural Networks using PAC-Bayesian Analysis](https://mlsanity.com/paper/1901.04653/) (2019)
- [A Strongly Quasiconvex PAC-Bayesian Bound](https://mlsanity.com/paper/1608.05610/) (2016)
- [Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm](https://mlsanity.com/paper/1503.08329/) (2015)
- [Simpler PAC-Bayesian Bounds for Hostile Data](https://mlsanity.com/paper/1610.07193/) (2016)

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

- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [Bayesian Model Selection, the Marginal Likelihood, and Generalization](https://mlsanity.com/paper/2202.11678/) (2022)
- [Deep Learning is Not So Mysterious or Different](https://mlsanity.com/paper/2503.02113/) (2025)
- [SAM as an Optimal Relaxation of Bayes](https://mlsanity.com/paper/2210.01620/) (2022)
- [Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guarantees](https://mlsanity.com/paper/2206.02659/) (2022)
- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [A Rigorous Link between Deep Ensembles and (Variational) Bayesian Methods](https://mlsanity.com/paper/2305.15027/) (2023)
- [Learning to Warm-Start Fixed-Point Optimization Algorithms](https://mlsanity.com/paper/2309.07835/) (2023)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods](https://mlsanity.com/paper/2408.14511/) (2024)
- [A New Family of Generalization Bounds Using Samplewise Evaluated CMI](https://mlsanity.com/paper/2210.06422/) (2022)
- [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)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Bayesian Learning for Neural Networks: an algorithmic survey](https://mlsanity.com/paper/2211.11865/) (2022)
- [Non-Vacuous Generalisation Bounds for Shallow Neural Networks](https://mlsanity.com/paper/2202.01627/) (2022)
- [Online PAC-Bayes Learning](https://mlsanity.com/paper/2206.00024/) (2022)
- [On PAC-Bayesian reconstruction guarantees for VAEs](https://mlsanity.com/paper/2202.11455/) (2022)
- [PAC-Bayesian Offline Contextual Bandits With Guarantees](https://mlsanity.com/paper/2210.13132/) (2022)
- [Integral Probability Metrics PAC-Bayes Bounds](https://mlsanity.com/paper/2207.00614/) (2022)
- [How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teachers](https://mlsanity.com/paper/2402.06323/) (2024)
- [Policy Adaptation via Language Optimization: Decomposing Tasks for Few-Shot Imitation](https://mlsanity.com/paper/2408.16228/) (2024)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Statistical Guarantees for Variational Autoencoders using PAC-Bayesian Theory](https://mlsanity.com/paper/2310.04935/) (2023)
- [Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning](https://mlsanity.com/paper/2405.14335/) (2024)
- [Exponential Smoothing for Off-Policy Learning](https://mlsanity.com/paper/2305.15877/) (2023)
- [Decentralized SGD and Average-direction SAM are Asymptotically Equivalent](https://mlsanity.com/paper/2306.02913/) (2023)
- [Importance-Weighted Offline Learning Done Right](https://mlsanity.com/paper/2309.15771/) (2023)
- [Towards a Theoretical Understanding of Synthetic Data in LLM Post-Training: A Reverse-Bottleneck Perspective](https://mlsanity.com/paper/2410.01720/) (2024)
- [Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approach](https://mlsanity.com/paper/2306.08553/) (2023)

## 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.