# PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 17 Jun 2021.

## Builds on (most cited first, 16 of 16)

- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [PAC-Bayes Un-Expected Bernstein Inequality](https://mlsanity.com/paper/1905.13367/) (2019)
- [Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes](https://mlsanity.com/paper/1605.00252/) (2016)
- [A Limitation of the PAC-Bayes Framework](https://mlsanity.com/paper/2006.13508/) (2020)
- [Fast-rate PAC-Bayes Generalization Bounds via Shifted Rademacher Processes](https://mlsanity.com/paper/1908.07585/) (2019)
- [Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning](https://mlsanity.com/paper/1605.06439/) (2016)
- [A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexity](https://mlsanity.com/paper/1710.07732/) (2017)
- [A Direct Sum Result for the Information Complexity of Learning](https://mlsanity.com/paper/1804.05474/) (2018)

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [A New Family of Generalization Bounds Using Samplewise Evaluated CMI](https://mlsanity.com/paper/2210.06422/) (2022)
- [Single Trajectory Nonparametric Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2202.08311/) (2022)
- [Tighter Information-Theoretic Generalization Bounds from Supersamples](https://mlsanity.com/paper/2302.02432/) (2023)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Importance-Weighted Offline Learning Done Right](https://mlsanity.com/paper/2309.15771/) (2023)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [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)
- [On the Generalization for Transfer Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2207.05377/) (2022)
- [Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal States](https://mlsanity.com/paper/2211.10691/) (2022)
- [Minimum Description Length and Generalization Guarantees for Representation Learning](https://mlsanity.com/paper/2402.03254/) (2024)
- [Minimax risk classifiers with 0-1 loss](https://mlsanity.com/paper/2201.06487/) (2022)
- [Stability Based Generalization Bounds for Exponential Family Langevin Dynamics](https://mlsanity.com/paper/2201.03064/) (2022)
- [FSL-SAGE: Accelerating Federated Split Learning via Smashed Activation Gradient Estimation](https://mlsanity.com/paper/2505.23182/) (2025)
- [Fast Rate Generalization Error Bounds: Variations on a Theme](https://mlsanity.com/paper/2205.03131/) (2022)
- [Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/2303.10758/) (2023)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Variational Inference of overparameterized Bayesian Neural Networks: a theoretical and empirical study](https://mlsanity.com/paper/2207.03859/) (2022)
- [Fast Rate Information-theoretic Bounds on Generalization Errors](https://mlsanity.com/paper/2303.14658/) (2023)
- [Generalization Bounds via Conditional f-Information](https://mlsanity.com/paper/2410.22887/) (2024)
- [Local Risk Bounds for Statistical Aggregation](https://mlsanity.com/paper/2306.17151/) (2023)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing](https://mlsanity.com/paper/2602.00906/) (2026)
- [Information-Theoretic Bayes Risk Lower Bounds for Realizable Models](https://mlsanity.com/paper/2111.04579/) (2021)
- [Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds](https://mlsanity.com/paper/2411.06276/) (2024)
- [Streaming PAC-Bayes Gaussian process regression with a performance guarantee for online decision making](https://mlsanity.com/paper/2210.08486/) (2022)
- [How Learning Dynamics Drive Adversarially Robust Generalization?](https://mlsanity.com/paper/2410.07719/) (2024)
- [Block-Sample MAC-Bayes Generalization Bounds](https://mlsanity.com/paper/2602.12605/) (2026)

## Abstract (arXiv)

We give a novel, unified derivation of conditional PAC-Bayesian and mutual information (MI) generalization bounds. We derive conditional MI bounds as an instance, with special choice of prior, of conditional MAC-Bayesian (Mean Approximately Correct) bounds, itself derived from conditional PAC-Bayesian bounds, where `conditional' means that one can use priors conditioned on a joint training and ghost sample. This allows us to get nontrivial PAC-Bayes and MI-style bounds for general VC classes, something recently shown to be impossible with standard PAC-Bayesian/MI bounds. Second, it allows us to get faster rates of order O left((KL/n)γright) for γ > 1/2 if a Bernstein condition holds and for exp-concave losses (with γ=1), which is impossible with both standard PAC-Bayes generalization and MI bounds. Our work extends the recent work by Steinke and Zakynthinou [2020] who handle MI with VC but neither PAC-Bayes nor fast rates, the recent work of Hellstr"om and Durisi [2020] who extend the latter to the PAC-Bayes setting via a unifying exponential inequality, and Mhammedi et al. [2019] who initiated fast rate PAC-Bayes generalization error bounds but handle neither MI nor general VC classes.