Block-Sample MAC-Bayes Generalization Bounds
Not on the map. Why?
Abstract (arXiv)
We present a family of novel block-sample MAC-Bayes bounds (mean approximately correct). While PAC-Bayes bounds (probably approximately correct) typically give bounds for the generalization error that hold with high probability, MAC-Bayes bounds have a similar form but bound the expected generalization error instead. The family of bounds we propose can be understood as a generalization of an expectation version of known PAC-Bayes bounds. Compared to standard PAC-Bayes bounds, the new bounds contain divergence terms that only depend on subsets (or blocks) of the training data. The proposed MAC-Bayes bounds hold the promise of significantly improving upon the tightness of traditional PAC-Bayes and MAC-Bayes bounds. This is illustrated with a simple numerical example in which the original PAC-Bayes bound is vacuous regardless of the choice of prior, while the proposed family of bounds are finite for appropriate choices of the block size. We also explore the question whether high-probability versions of our MAC-Bayes bounds (i.e., PAC-Bayes bounds of a similar form) are possible. We answer this question in the negative with an example that shows that in general, it is not possible to establish a PAC-Bayes bound which (a) vanishes with a rate faster than O(1/log n) whenever the proposed MAC-Bayes bound vanishes with rate O(n-1/2) and (b) exhibits a logarithmic dependence on the permitted error probability.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 39 references that are in the map. First posted on arXiv 13 Feb 2026.
Builds on
24 of 39 references.
References · 24
- 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
- 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
- 2021User-friendly introduction to PAC-Bayes boundscited by 234
- 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
- 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
- 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
- 2020Tighter risk certificates for neural networkscited by 112
- 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
- 2015Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithmcited by 50
- 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
- 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
- 2016Simpler PAC-Bayesian Bounds for Hostile Datacited by 45
12 more
- 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
- 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
- 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
- 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
- 2021How Tight Can PAC-Bayes be in the Small Data Regime?cited by 24
- 2022Online PAC-Bayes Learningcited by 22
- 2022Fast Rate Generalization Error Bounds: Variations on a Themecited by 6
- 2023Fast Rate Information-theoretic Bounds on Generalization Errorscited by 5
- 2023Comparing Comparators in Generalization Boundscited by 5
- 2023Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problemcited by 4
- 2024Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Losscited by 4
- 2022Formal limitations of sample-wise information-theoretic generalization boundscited by 3
Built on by
Not cited yet.