A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.
Tom: We're looking at the paper: "A Framework for Bounding Deterministic Risk with PAC-Bayes".
Jane: Here's the gist of the paper. A unified framework is proposed to extract guarantees holding for a single hypothesis from stochastic PAC-Bayesian guarantees The authors present a general oracle bound, and derive from it a numerical bound and a specialization to majority vote Empirically, their approach consistently outperforms popular baselines (by up to a factor of 2) when it comes to generalization bounds on deterministic classifiers.
Tom: Pruning redundant reasoning tokens The paper introduces the Stochastic-to-Deterministic (S2D) bounds framework to obtain a deterministic bound for a single hypothesis from stochastic PAC-Bayesian guarantees This framework is called "Stochastic-to-Deterministic (S2D) bounds".
Jane: They develop an oracle bound that is independent of the hypothesis space, the prior and posterior distributions form.
Tom: The key contributions include proposing this unified framework for obtaining generalization bounds on the risk of single hypotheses using PAC-Bayes bounds as a building block They also specialize this to majority votes with either Categorical, Dirichlet, or Gaussian distributions.
Paper summary: Jane: We've covered the main points of this paper, which is this new Stochastic-to-Deterministic bounds framework that uses PAC-Bayes to get deterministic guarantees for single hypotheses.
Tom: Right, the authors focus on deriving a general oracle bound, turning it into a numerical bound and specializing it for majority votes with Categorical, Dirichlet, or Gaussian distributions.
Lu: The most important thing is that they show this approach consistently outperforms popular baselines by up to a factor of two when we look at generalization bounds on deterministic classifiers.
Jane: So, the implication is that we have a more robust and potentially tighter way to get those risk estimates for single models than what was available before.
Tom: It provides a concrete tool that connects stochastic PAC-Bayes guarantees to actual deployment scenarios for specific voting schemes.
Jane: It opens up directions for future research, like extending this beyond majority votes to neural networks and developing better approximations for the partition problem they used in their analysis.
Conclusion: Tom: So we've been looking at this paper, "A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes." Basically, they took these stochastic PAC-Bayesian guarantees and turned them into a solid tool for getting a deterministic bound on risk for just one hypothesis.
Jane: That sounds dense. So what does that actually mean for us who are trying to build models that make decisions? What’s the simplest way to explain this new framework?
Lu: It means they created this unified structure, we call it Stochastic-to-Deterministic bounds, that works regardless of your hypothesis space or your prior and posterior distributions. It’s a building block for bounding risk using PAC-Bayes results.
Meng: But I'm wondering about the practical side. They specialize this for majority votes with Categorical, Dirichlet, or Gaussian distributions. How much does that actually help when we're trying to deploy something at scale?
Tom: Well, they show how to get a numerical bound from that general oracle bound and then apply it specifically to those voting schemes. And empirically, their approach consistently beats the baselines by up to a factor of two on deterministic classifiers. That’s a solid number.
Jane: A factor of two improvement is pretty significant for generalization bounds, right? So what's the biggest thing this paper changes for someone just listening who isn't deep into math?
Lalam: It means we can get much tighter, more reliable estimates on how well a single model will actually perform on new data before we even deploy it. It connects those complex stochastic guarantees to real-world risk calculation.
Tom: Exactly. They’ve shown this method is consistent with existing PAC-Bayesian bounding methods, which is good because it means they aren't inventing something entirely new; they are just connecting the dots better for these specific voting scenarios.
Jane: So the main takeaway here is that we have a more direct path to getting strong guarantees on single models using these established techniques. But what does this leave open?
Lu: They’re already looking at extending this beyond simple majority votes to neural networks, and they're trying to get better approximations for that partition problem they use in their analysis. That’s where the next big push is going to be.
Benjamin Leblanc, Pascal Germain
Université Laval
cs.LG
Submitted: 2025-10-29
Updated: 2026-11-09
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 86/100
The gist: A unified framework is proposed to extract guarantees holding for a single hypothesis from stochastic PAC-Bayesian guarantees The authors present a general oracle bound…
Key concepts
- Stochastic-to-Deterministic (S2D) bounds
- This is the unified framework proposed to convert stochastic PAC-Bayesian guarantees into a deterministic bound for a single hypothesis. It uses an oracle bound independent of the hypothesis space, prior, and posterior distributions as its foundation.
- Proposition 1 (Stochastic-deterministic relation)
- This mathematical tool relates deterministic risk to stochastic risks by decomposing them into correct and incorrect predictions. It provides a formula allowing the deterministic risk LD(h) to be bounded using three simultaneously derived PAC-Bayesian bounds.
- Majority Vote Specialization
- The framework is specialized for majority votes using various posterior distributions, such as Categorical, Dirichlet, and Gaussian. Specific propositions are developed for each distribution to derive tighter bounds on the deterministic risk.
Terminology
Summary
A unified framework is proposed to extract guarantees holding for a single hypothesis from stochastic PAC-Bayesian guarantees The authors present a general oracle bound, and derive from it a numerical bound and a specialization to majority vote Empirically, their approach consistently outperforms popular baselines (by up to a factor of 2) when it comes to generalization bounds on deterministic classifiers. p. 0 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.Where the paper says it
Pruning redundant reasoning tokens
The paper introduces the Stochastic-to-Deterministic (S2D) bounds framework to obtain a deterministic bound for a single hypothesis from stochastic PAC-Bayesian guarantees This framework is called We call this conversion Stochastic-toDeterministic (S2D) bounds. • We develop such an oracle bound that is independent of the hypothesis space, the prior and
posterior distributions form. Our key contributions. • To leverage the tightness of PAC-Bayes bounds,
yet to address the concerns regarding their practical use, we propose a unified framework for obtaining generalization bounds on the risk of single
hypotheses using PAC-Bayes bounds as a building block. A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes
• We then specialize it to majority votes with either
Categorical, Dirichlet, or Gaussian distributions. • Finally, we test (and compare to several benchmarks) our approach on many binary and multiclass classification tasks, providing empirical evidence of the tightness of our approach.Stochastic-to-Deterministic (S2D) bounds
. They develop an oracle bound that is independent of the hypothesis space, the prior and posterior distributions form. p. 0Where the paper says it
Where the paper says it
Where the paper says it
How the training signal is built
The core mathematical tool is Proposition 1 (Stochastic-deterministic relation), which relates deterministic risk to stochastic risks by decomposing them into correct and incorrect predictions. This proposition states that for any data distribution D, distribution Q over H and classifier h ∈ H such that c Q D(h) ≠ b Q D(h), the deterministic risk LD(h) is given by LD(h) = E h'∼Q LD(h') − b Q D(h) c Q D(h) − b Q D(h). This result allows bounding the deterministic risk using three simultaneously derived PAC-Bayesian bounds. p. 2 Benjamin Leblanc, Pascal Germain
statements hold with probability at least 1 − δ for all
Q over H simultaneously:
kl
cb
Q
S
(h)
b
Q
D(h)
≤
1
m(h,0)
KL(Q||P)+ln
2
√
m
δ
,
kl
cc
Q
S
(h)
c
Q
D(h)
≤
1
m(h,1)
KL(Q||P)+ln
2
√
m
δ
,
where cb
Q
S
(h)= E
h′∼Q
LbS(h,0) (h
′
),
cc
Q
S
(h)= E
h′∼Q
LbS(h,1) (h
′
),
S(h,a)={(x, y)∈S : ℓ(h(x), y)=a}, and |S(h,a)
|=m(h,a)
. The following result uses Theorem 1 to bound the
quantities involved in Proposition 1: we end up bounding the deterministic risk of any hypothesis by using
simultaneously three PAC-Bayesian bounds.Where the paper says it
Where the gains come from
The authors specialize the S2D framework to majority votes with different posterior distributions Q, including Categorical, Dirichlet, and Gaussian For the Categorical distribution Q = C(p), Proposition 2 shows that E w∼C(p) l(hw(x), y) = pF, b C(p) D (hp) = E (x,y)∼D [pF pF < 0.5], and c C(p) D (hp) = E (x,y)∼D [pF pF ≥ 0.5]. Proposition 3 provides a lower bound on c C(p) D (hp), which involves the partition problem. p. 3 Given a set of
non-negative numbers a, the partition problem consists in finding
argmin
a1,a2
(
X
a∈a1
a −
X
a∈a2
a
: {a1, a2} is a partition of a
)
. Proposition 3 (Weights partitioning lower bound—
Categorical). Proposition 4 (Majority vote–Dirichlet S2D). In the
context of Proposition 1: let Q = D(p) be a Dirichlet
distribution with parameters p. Given a set of
non-negative numbers a, the partition problem consists in finding
argmin
a1,a2
(
X
a∈a1
a −
X
a∈a2
a
: {a1, a2} is a partition of a
)
. Proposition 3 (Weights partitioning lower bound—
Categorical). Also, since every base
classifier has a prediction in {−1, +1}, for every x, we
have ||f(x)|| =
√
n, we can lower-bound c
Q
D(hp) as in
Sections 4. Proposition 7 (Weights partitioning lower bound–Binary Gaussian).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The authors establish a worst-case scenario where LD(h) ≤ 2 E h'∼C(p) LD(h') by substituting the bounds from Proposition 1 into the general relationship. They then show how to attain tighter bounds by identifying the smallest subset of p such that its sum is at least 0 for b C(p) D (hp) and at least 0. p. 3 We
now show how to attain tighter bounds by improving
the deterministic lower bound on c
C(p)
D (hp). We do so by identifying the smallest subset of p such
that its sum is at least 0 for b
C(p)
D (hp) and at least 0. While the resulting lower bound for b
C(p)
D (hp) trivially
leads to 0, the lower bound on c
C(p)
D (hp) can turn out
to be quite bigger than 0. 5, thus leading to an upper
bounding of LD(h) that is better then the factor-2
bound.Where the paper says it
Where the paper says it
The framework allows for data-dependent hypothesis selection through Corollary 2, which uses deterministic lower bounds for b Q D(h) and c Q D(h). The paper details methods to obtain these lower bounds by solving the partition problem, noting that while NP-complete, there exists a pseudo-polynomial time dynamic programming solving algorithm. p. 5 The worst-case analysis cannot yield any satisfying estimate for b
Q
D(h) in most scenarios, so we use Proposition 8 when Q is Gaussian and k = 2, and we use the
trivial bound b
Q
D(h) ≥ 0 otherwise. The partition problem computation The lowerbounding of c
Q
D(h) relies on solving the partition problem, and while this problem is NP-complete, there
exists a pseudo-polynomial time dynamic programming solving algorithm, and there are heuristics that
solve the problem in many instances [Mertens, 2005].Where the paper says it
The empirical results show that on a total of 12 datasets in the two different learning paradigms, the proposed approach’s generalization bound is always at least as good as the baselines. The VC-dim-based approach provides loose generalization bounds because it penalizes proportional to the base classifier set size, even when some of these classifiers end up having a small role in the majority vote. p. 7 1 Discussion
Table 2 shows that, on a total of 12 datasets in the two
different learning paradigms, the proposed approach’s
generalization bound is always at least as good as the
baselines’. The VC-dim-based approach provides loose
generalization bounds because the bound is penalized
proportionally to the base classifier set size, even when
some of these classifiers end up having a small role in
the majority vote; the PAC-Bayes-based approaches
are more robust to this issue by providing those with
a weight similar to that of the prior distribution. 1 Discussion
Table 2 shows that, on a total of 12 datasets in the two
different learning paradigms, the proposed approach’s
generalization bound is always at least as good as the
baselines’. The VC-dim-based approach provides loose
generalization bounds because the bound is penalized
proportionally to the base classifier set size, even when
some of these classifiers end up having a small role in
the majority vote; the PAC-Bayes-based approaches
are more robust to this issue by providing those with
a weight similar to that of the prior distribution. We test (and compare to several benchmarks) our approach on many binary and
multi-class classification tasks, providing empirical evidence of the tightness of our approach. Our S2D is consistent with existing PAC-Bayesian
bounding methods and opens several directions for future work: extending beyond majority votes to neural networks, deriving tighter multi-class Gaussian
bounds, and developing end-to-end differentiable approximations to the partition problem.Where the paper says it
Where the paper says it
Where the paper says it
The paper discusses existing S2D approaches via Bayes Risk, noting that the equality LD(h) = BD(Q) is always valid for majority vote classifiers with the Categorical or Gaussian distributions, but not the Dirichlet distribution. They review several influential methods for bounding Bayes risk, such as the first-order bound (FO), second-order bound (SO), binomial bound (Bin), and C-bound (CBnd). p. 6 "Part" refers to "partition bound". 7 NUMERICAL EXPERIMENTS
We compare our proposed approach for bounding deterministic risk, the partition bound (Part), to all
of the baselines discussed in Section 6: First-order
(FO), Second-order (SO), Binomial (Bin), the CBound (CBnd) and finally, the VC-dim bound. Optimizing the C-bound is a research topic of its own [Viallard et al. 2 A baseline based on the VC-dimension
Finally, we consider an alternative paradigm for
bounding the deterministic risk of hypotheses that
does not involve PAC-Bayes: the VC-dimension (VCdim) [Vapnik, 2000], which is a measure of the expressive power of hypothesis sets.Where the paper says it
Where the paper says it
The comparison in Table 2 shows that the proposed approach’s generalization bound is always at least as good as the baselines In many cases, the proposed bound corresponds to about half the best runner-up bound (ADULT, CODRNA, SVMG, etc.) The authors note that even though the Categorical distribution definitely seems to have an advantage over both the Dirichlet and the Gaussian distribution when it comes to generalization bound, the latter two distributions show impressive test error results. p. 7 To further analyze this discrepancy,
we display in Table 3 the partition bound obtained for
each distribution. Even though the Categorical distribution definitely seems to have an advantage over both
the Dirichlet and the Gaussian distribution when it
comes to the generalization bound, the latter two distributions show impressive test error results, justifying
the development and use of all three of them.Where the paper says it
The paper concludes by summarizing its development of a general framework for deriving deterministic generalization guarantees from PAC-Bayes bounds: Stochastic-to-Deterministic (S2D) bounds. They emphasize that their S2D is consistent with existing PAC-Bayesian bounding methods and opens several directions for future work, such as extending beyond majority votes to neural networks, deriving tighter multi-class Gaussian bounds, and developing end-to-end differentiable approximations to the partition problem. p. 7 We test (and compare to several benchmarks) our approach on many binary and
multi-class classification tasks, providing empirical evidence of the tightness of our approach. Our S2D is consistent with existing PAC-Bayesian
bounding methods and opens several directions for future work: extending beyond majority votes to neural networks, deriving tighter multi-class Gaussian
bounds, and developing end-to-end differentiable approximations to the partition problem. A Framework for Bounding Deterministic Risk with PAC-Bayes:
Applications to Majority Votes
Benjamin Leblanc Pascal Germain
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.Where the paper says it
Where the paper says it
The authors provide a checklist for reproducibility which includes checking if models include a clear description of the mathematical setting, assumptions, algorithm, and/or model They also check if theoretical claims include statements of the full set of assumptions and complete proofs For empirical results in figures and tables, they check if they include code, data, and instructions needed to reproduce the main experimental results. The paper notes that no method from the literature permits the use of the Dirichlet distribution, and that they provide an objective for many baselines to use the Gaussian distribution for multi-class tasks. p. 6 3 Contributions contextualization
We show in Table 1 the applicability of the various
ways to bound deterministic risks using stochastic risk
found in the literature, and regarding our proposed
approaches. We emphasize that no method from the
literature permits the use of the Dirichlet distribution,
and that we provide an objective for many baselines
to use the Gaussian distribution for multi-class tasks. The worst-case analysis cannot yield any satisfying estimate for b
Q
D(h) in most scenarios, so we use Proposition 8 when Q is Gaussian and k = 2, and we use the
trivial bound b
Q
D(h) ≥ 0 otherwise. The partition problem computation The lowerbounding of c
Q
D(h) relies on solving the partition problem, and while this problem is NP-complete, there
exists a pseudo-polynomial time dynamic programming solving algorithm, and there are heuristics that
solve the problem in many instances [Mertens, 2005]. In the first
setting, we considered the following tasks: ADULT,
CODRNA, HABER, MUSH, PHIS, SVMG, TTT; in
the second, we considered the following: FASHION,
MNIST, PEND, PROTEIN, SENSOR. We train the models by Stochastic Gradient Descent
(SGD) using Adam [Kingma and Ba, 2015].Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Generalization Bounds for Single Deterministic Hypotheses: The Stochastic-to-Deterministic (S2D) framework allows researchers to obtain a deterministic risk bound for a single hypothesis h from stochastic PAC-Bayesian guarantees, addressing the limitation of classical PAC-Bayes which only bounds the expected risk of a randomly sampled hypothesis.
-
Majority Vote Risk Bounding with Specific Distributions: The framework can be specialized to majority votes using Categorical, Dirichlet, or Gaussian distributions, providing tailored generalization bounds for these specific voting schemes.
-
Tight Generalization Bounds via Partitioning: Deterministic lower-bounding of the stochastic risk quantities bQ D(h) and cQ D(h) enables the use of Corollary 2 (Triple bound), which provides a deterministic upper bound on LD(h) that is tighter than the factor-2 worst-case scenario, especially when combined with heuristics to improve the partition bound.
-
Data-Dependent Hypothesis Selection: By using data-dependent lower bounds for bQ D(h) and cQ D(h), Corollary 2 can be applied to enable data selection for hypothesis h, allowing the system to choose a specific hypothesis based on the training data S instead of relying solely on priors.
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.
Sources
- A Primer on PAC-Bayesian Learning
- Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds
- Learning PAC-Bayes Priors for Probabilistic Neural Networks
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis