cs.LGOct 29, 2025

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

Authors: Benjamin Leblanc, Pascal Germain

Organizations: Université Laval

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 for extracting guarantees for a single hypothesis from PAC-Bayesian guarantees. We present a general derandomization framework, and derive from it a numerical bound for majority votes and for three different probability distributions over the posterior space. We study the empirical behaviour of our approach, showing that it consistently outperforms popular baselines in terms of generalization bounds for single classifiers (by up to a factor of 2), but sometimes requires a sacrifice in accuracy.

Figures & tables

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Smoothness-Based Derandomization of PAC-Bayes Bounds

    Jun 17, 2026Alexandre Lemire Paquin, Brahim Chaib-Draa, Philippe GiguèreNeural Network GeneralizationPAC-Bayesian Generalization Bounds

  2. Bound to Disagree: Generalization Bounds via Certifiable Surrogates

    Feb 26, 2026Mathieu Bazinet, Valentina Zantedeschi, Pascal GermainGeneralization Bounds