# Generalization Bounds: Perspectives from Information Theory and PAC-Bayes

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

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2023.

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

- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [A PAC-Bayesian Link Between Generalisation and Flat Minima](https://mlsanity.com/paper/2402.08508/) (2024)
- [More Flexible PAC-Bayesian Meta-Learning by Learning Learning Algorithms](https://mlsanity.com/paper/2402.04054/) (2024)
- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [Generalization and Informativeness of Conformal Prediction](https://mlsanity.com/paper/2401.11810/) (2024)
- [Generalization bounds for mixing processes via delayed online-to-PAC conversions](https://mlsanity.com/paper/2406.12600/) (2024)
- [AI Agents as Universal Task Solvers](https://mlsanity.com/paper/2510.12066/) (2025)
- [Leveraging PAC-Bayes Theory and Gibbs Distributions for Generalization Bounds with Complexity Measures](https://mlsanity.com/paper/2402.13285/) (2024)
- [Asymmetry of the Relative Entropy in the Regularization of Empirical Risk Minimization](https://mlsanity.com/paper/2410.02833/) (2024)
- [Confidence-calibrated covariate shift correction for few-shot classification in Vision-Language Models](https://mlsanity.com/paper/2502.07847/) (2025)
- [Comparing Comparators in Generalization Bounds](https://mlsanity.com/paper/2310.10534/) (2023)
- [The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms](https://mlsanity.com/paper/2411.12030/) (2024)
- [From Mutual Information to Expected Dynamics: New Generalization Bounds for Heavy-Tailed SGD](https://mlsanity.com/paper/2312.00427/) (2023)
- [Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds](https://mlsanity.com/paper/2410.21702/) (2024)
- [Generalization Bounds via Conditional f-Information](https://mlsanity.com/paper/2410.22887/) (2024)
- [Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Bounds](https://mlsanity.com/paper/2601.08100/) (2026)
- [How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysis](https://mlsanity.com/paper/2406.09745/) (2024)
- [Variations on the Expectation due to Changes in the Probability Measure](https://mlsanity.com/paper/2502.02887/) (2025)
- [Empirical PAC-Bayes Bounds for Markov Chains](https://mlsanity.com/paper/2509.20985/) (2025)
- [Generalization or Memorization: Dynamic Decoding for Mode Steering](https://mlsanity.com/paper/2510.22099/) (2025)
- [PAC-Bayes Bounds for Multivariate Linear Regression and Linear Autoencoders](https://mlsanity.com/paper/2512.12905/) (2025)
- [Federated Learning with Nonvacuous Generalisation Bounds](https://mlsanity.com/paper/2310.11203/) (2023)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Tighter Generalisation Bounds via Interpolation](https://mlsanity.com/paper/2402.05101/) (2024)
- [The Capabilities and Limitations of Weak-to-Strong Generalization: Generalization and Calibration](https://mlsanity.com/paper/2502.01458/) (2025)
- [Uncertainty Quantification and Data Efficiency in AI: An Information-Theoretic Perspective](https://mlsanity.com/paper/2512.05267/) (2025)
- [Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing](https://mlsanity.com/paper/2602.00906/) (2026)
- [Bound to Disagree: Generalization Bounds via Certifiable Surrogates](https://mlsanity.com/paper/2602.23128/) (2026)
- [A note on regularised NTK dynamics with an application to PAC-Bayesian training](https://mlsanity.com/paper/2312.13259/) (2023)
- [Convex SGD: Generalization Without Early Stopping](https://mlsanity.com/paper/2401.04067/) (2024)

## Abstract (arXiv)

A fundamental question in theoretical machine learning is generalization. Over the past decades, the PAC-Bayesian approach has been established as a flexible framework to address the generalization capabilities of machine learning algorithms, and design new ones. Recently, it has garnered increased interest due to its potential applicability for a variety of learning algorithms, including deep neural networks. In parallel, an information-theoretic view of generalization has developed, wherein the relation between generalization and various information measures has been established. This framework is intimately connected to the PAC-Bayesian approach, and a number of results have been independently discovered in both strands. In this monograph, we highlight this strong connection and present a unified treatment of PAC-Bayesian and information-theoretic generalization bounds. We present techniques and results that the two perspectives have in common, and discuss the approaches and interpretations that differ. In particular, we demonstrate how many proofs in the area share a modular structure, through which the underlying ideas can be intuited. We pay special attention to the conditional mutual information (CMI) framework; analytical studies of the information complexity of learning algorithms; and the application of the proposed methods to deep learning. This monograph is intended to provide a comprehensive introduction to information-theoretic generalization bounds and their connection to PAC-Bayes, serving as a foundation from which the most recent developments are accessible. It is aimed broadly towards researchers with an interest in generalization and theoretical machine learning.