mlsanityData to 7 Oct 2026

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

arXiv 2510.25569 ↗First posted 29 Oct 2025cs.LGcited by 3

Not on the map. Why?

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.

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

Builds on

23 of 75 references.

References · 23

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  2. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  3. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  4. 2019A Primer on PAC-Bayesian Learningcited by 130
  5. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 125
  6. 2020Tighter risk certificates for neural networkscited by 112
  7. 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
  8. 2016A Strongly Quasiconvex PAC-Bayesian Boundcited by 54
  9. 2015Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithmcited by 50
  10. 2019Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networkscited by 38
  11. 2020Second Order PAC-Bayesian Bounds for the Weighted Majority Votecited by 34
  12. 2020Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networkscited by 29
11 more
  1. 2021A General Framework for the Practical Disintegration of PAC-Bayesian Boundscited by 21
  2. 2021Learning PAC-Bayes Priors for Probabilistic Neural Networkscited by 21
  3. 2023Compression, Generalization and Learningcited by 21
  4. 2018Sample Compression for Real-Valued Learnerscited by 19
  5. 2021Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Boundcited by 16
  6. 2021Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Votecited by 13
  7. 2021Self-Bounding Majority Vote Learning Algorithms by the Direct Minimization of a Tight PAC-Bayesian C-Boundcited by 8
  8. 2024Sample Compression Unleashed: New Generalization Bounds for Real Valued Lossescited by 4
  9. 2015On Generalizing the C-Bound to the Multiclass and Multi-label Settingscited by 1
  10. 2021PAC-Bayesian Learning of Aggregated Binary Activated Neural Networks with Probabilities over Representationscited by 1
  11. 2024Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Boundscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Bound to Disagree: Generalization Bounds via Certifiable Surrogatescited by 2
  2. 2026Smoothness-Based Derandomization of PAC-Bayes Boundscited by 1
  3. 2026PAC-Bayesian Generalization Guarantees for Fairness on Stochastic and Deterministic Classifierscited by 0