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

arXiv:2510.25569 · cs.LG · Submitted 2025-10-29 · Read on arXiv

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

Where the paper says it

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.

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. They develop an oracle bound that is independent of the hypothesis space, the prior and posterior distributions form. p. 0

Where the paper says it

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.

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. p. 0
Where the paper says it

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.

Finally, they test and compare their approach on many binary and multiclass classification tasks, providing empirical evidence of the tightness of their approach. p. 1
Where the paper says it

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.

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

Where the paper says it

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 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

Where the paper says it

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).

Similarly, for the Dirichlet distribution Q = D(p), Proposition 4 gives E w∼D(p) l(hw(x), y) = I0. p. 3
Where the paper says it

Proposition 4 (Majority vote–Dirichlet S2D). In the context of Proposition 1: let Q = D(p) be a Dirichlet distribution with parameters p.

5 (p1 − pF, pF), and Proposition 5 provides a lower bound on c D(p) D (hp). p. 3
Where the paper says it

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).

For the Gaussian distribution Q = N (p,I), Proposition 6 gives E w∼N(p,I) l(hw(x), y) = Φ y p · f(x) f(x), and Proposition 7 provides a lower bound on c N(p,I) D (hp). p. 4
Where the paper says it

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).

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

Where the paper says it

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.

5 for c C(p) D (hp). This leads to an upper bounding of LD(h) that is better than the factor-2 bound. p. 3
Where the paper says it

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.

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

Where the paper says it

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].

Furthermore, training heuristics are applied after optimizing the PAC-Bayesian objective Eh'∼QLD(h') to improve the partition bound.

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

Where the paper says it

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.

The PAC-Bayes-based approaches are more robust to this issue by providing those with a weight similar to that of the prior distribution. p. 7
Where the paper says it

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.

The authors conclude that their S2D approach is consistent with existing PAC-Bayesian bounding methods and opens directions for future work, such as extending beyond majority votes to neural networks. p. 7
Where the paper says it

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.

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

Where the paper says it

"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.

The VC-dimension approach is also considered as an alternative paradigm for bounding deterministic risk. p. 6
Where the paper says it

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.

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

Where the paper says it

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.

The experimental section details how they train models using Stochastic Gradient Descent (SGD) with Adam

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

Where the paper says it

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.

The paper also provides a checklist for reproducibility. p. 0
Where the paper says it

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.

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

Where the paper says it

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 authors also note that a pseudo-polynomial time dynamic programming solving algorithm exists for the partition problem. p. 5
Where the paper says it

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].

The experimental section details how they train models using Stochastic Gradient Descent (SGD) with Adam and reports results over 5 random seeds. p. 7
Where the paper says it

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].

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

  1. 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.

  2. 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.

  3. 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.

  4. 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

Related papers