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

Benjamin Leblanc, Pascal Germain
10/29/2025
cs.LG

No official code found. Best implementation: benjaminlblanc/DeterministicPACBayes (0 stars, last commit 2026-03-04).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

benjaminlblanc/DeterministicPACBayesCommunity70%

Source code of the article "A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes".

00Shell, PythonApr 24, 20257 months ago

Similar Papers

A unified recipe for deriving (time-uniform) PAC-Bayes bounds

84% match2023

Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds

82% match2024

More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity

81% match2023

Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets

80% match2024

Leveraging PAC-Bayes Theory and Gibbs Distributions for Generalization Bounds with Complexity Measures

80% match2024

Misclassification excess risk bounds for PAC-Bayesian classification via convexified loss

80% match2024

Cite this paper

@article{leblanc2025framework,
  title  = {A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes},
  author = {Benjamin Leblanc and Pascal Germain},
  year   = {2025},
  eprint = {2510.25569},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2510.25569v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2510.25569.svg)](https://codeofpaper.com/paper/2510.25569)

Discussion