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

• URL: http://arxiv.org/abs/2510.25569v1
• Date: Wed, 29 Oct 2025 14:38:35 GMT
• Title: A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes
• Authors: Benjamin Leblanc, Pascal Germain,
• Abstract summary: PAC-Bayes is a popular framework for obtaining generalization guarantees in uncountable hypothesis spaces.<n>We propose a unified framework to extract guarantees holding for a single hypothesis from PAC-Bayesian guarantees.
• Score: 4.664367264604233
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Epistemic Filtering and Collective Hallucination: A Jury Theorem for Confidence-Calibrated Agents [2.28438857884398]
  We investigate the collective accuracy of heterogeneous agents who learn to estimate their own reliability over time and selectively abstain from voting.<n>While classical voting results assume fixed participation, real-world aggregation often benefits from allowing agents to say I don't know'
  arXiv  Detail & Related papers  (2026-02-25T21:09:14Z)
• Towards Anytime-Valid Statistical Watermarking [63.02116925616554]
  We develop the first e-value-based watermarking framework, Anchored E-Watermarking, that unifies optimal sampling with anytime-valid inference.<n>Our framework can significantly enhance sample efficiency, reducing the average token budget required for detection by 13-15% relative to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-02-19T18:32:26Z)
• PAC-Bayesian Generalization Guarantees for Fairness on Stochastic and Deterministic Classifiers [8.438034474012044]
  We propose a PAC-Bayesian framework for deriving generalization bounds for fairness.<n>Our framework has two advantages: (i) It applies to a broad class of fairness measures that can be expressed as a risk discrepancy, and (ii) it leads to a self-bounding algorithm.
  arXiv  Detail & Related papers  (2026-02-12T08:49:34Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Optimal Conformal Prediction under Epistemic Uncertainty [61.46247583794497]
  Conformal prediction (CP) is a popular framework for representing uncertainty.<n>We introduce Bernoulli prediction sets (BPS) which produce the smallest prediction sets that ensure conditional coverage.<n>When given first-order predictions, BPS reduces to the well-known adaptive prediction sets (APS)
  arXiv  Detail & Related papers  (2025-05-25T08:32:44Z)
• How good is PAC-Bayes at explaining generalisation? [13.084336891814054]
  We discuss necessary conditions for a PAC-Bayes bound to provide a meaningful generalisation guarantee.<n>Our analysis reveals that the optimal generalisation guarantee depends solely on the distribution of the risk induced by the prior distribution.
  arXiv  Detail & Related papers  (2025-03-11T09:51:21Z)
• Probabilistic Conformal Prediction with Approximate Conditional Validity [81.30551968980143]
  We develop a new method for generating prediction sets that combines the flexibility of conformal methods with an estimate of the conditional distribution. Our method consistently outperforms existing approaches in terms of conditional coverage.
  arXiv  Detail & Related papers  (2024-07-01T20:44:48Z)
• Mitigating LLM Hallucinations via Conformal Abstention [70.83870602967625]
  We develop a principled procedure for determining when a large language model should abstain from responding in a general domain. We leverage conformal prediction techniques to develop an abstention procedure that benefits from rigorous theoretical guarantees on the hallucination rate (error rate) Experimentally, our resulting conformal abstention method reliably bounds the hallucination rate on various closed-book, open-domain generative question answering datasets.
  arXiv  Detail & Related papers  (2024-04-04T11:32:03Z)
• Conformal Off-Policy Prediction in Contextual Bandits [54.67508891852636]
  Conformal off-policy prediction can output reliable predictive intervals for the outcome under a new target policy. We provide theoretical finite-sample guarantees without making any additional assumptions beyond the standard contextual bandit setup.
  arXiv  Detail & Related papers  (2022-06-09T10:39:33Z)
• Efficient Conformal Prediction via Cascaded Inference with Expanded Admission [43.596058175459746]
  We present a novel approach for conformal prediction (CP) We aim to identify a set of promising prediction candidates -- in place of a single prediction. This set is guaranteed to contain a correct answer with high probability.
  arXiv  Detail & Related papers  (2020-07-06T23:13:07Z)
• PAC-Bayes Analysis Beyond the Usual Bounds [16.76187007910588]
  We focus on a learning model where the learner observes a finite set of training examples. The learned data-dependent distribution is then used to make randomized predictions.
  arXiv  Detail & Related papers  (2020-06-23T14:30:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.