# A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 75 references that are in the map.
- First posted on arXiv 29 Oct 2025.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [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)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [PAC-Bayes Analysis Beyond the Usual Bounds](https://mlsanity.com/paper/2006.13057/) (2020)
- [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)
- [Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks](https://mlsanity.com/paper/1905.10259/) (2019)
- [Second Order PAC-Bayesian Bounds for the Weighted Majority Vote](https://mlsanity.com/paper/2007.13532/) (2020)
- [Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks](https://mlsanity.com/paper/2006.12228/) (2020)
- [A General Framework for the Practical Disintegration of PAC-Bayesian Bounds](https://mlsanity.com/paper/2102.08649/) (2021)
- [Learning PAC-Bayes Priors for Probabilistic Neural Networks](https://mlsanity.com/paper/2109.10304/) (2021)
- [Compression, Generalization and Learning](https://mlsanity.com/paper/2301.12767/) (2023)
- [Sample Compression for Real-Valued Learners](https://mlsanity.com/paper/1805.08254/) (2018)
- [Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound](https://mlsanity.com/paper/2106.12535/) (2021)
- [Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote](https://mlsanity.com/paper/2106.13624/) (2021)
- [Self-Bounding Majority Vote Learning Algorithms by the Direct Minimization of a Tight PAC-Bayesian C-Bound](https://mlsanity.com/paper/2104.13626/) (2021)
- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (2024)
- [On Generalizing the C-Bound to the Multiclass and Multi-label Settings](https://mlsanity.com/paper/1501.03001/) (2015)
- [PAC-Bayesian Learning of Aggregated Binary Activated Neural Networks with Probabilities over Representations](https://mlsanity.com/paper/2110.15137/) (2021)
- [Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds](https://mlsanity.com/paper/2411.06276/) (2024)

## Built on by (most cited first, 3 of 3)

- [Bound to Disagree: Generalization Bounds via Certifiable Surrogates](https://mlsanity.com/paper/2602.23128/) (2026)
- [Smoothness-Based Derandomization of PAC-Bayes Bounds](https://mlsanity.com/paper/2606.19105/) (2026)
- [PAC-Bayesian Generalization Guarantees for Fairness on Stochastic and Deterministic Classifiers](https://mlsanity.com/paper/2602.11722/) (2026)

## Abstract (arXiv)

PAC-Bayes is a popular and efficient framework for obtaining generalization guarantees in situations involving uncountable hypothesis spaces. Unfortunately, in its classical formulation, it only provides guarantees on the expected risk of a randomly sampled hypothesis. This requires stochastic predictions at test time, making PAC-Bayes unusable in many practical situations where a single deterministic hypothesis must be deployed. We propose a unified framework to extract guarantees holding for a single hypothesis from stochastic PAC-Bayesian guarantees. We present a general oracle bound and derive from it a numerical bound and a specialization to majority vote. We empirically show that our approach consistently outperforms popular baselines (by up to a factor of 2) when it comes to generalization bounds on deterministic classifiers.