# Pac-bayesian generalization guarantees for fairness on stochastic and deterministic classifiers

Julien Bastian, Benjamin Leblanc, Pascal Germain, Amaury Habrard, Christine Largeron, Guillaume Metzler, Emilie Morvant, Paul Viallard

► To cite this version:

Julien Bastian, Benjamin Leblanc, Pascal Germain, Amaury Habrard, Christine Largeron, et al. Pac-bayesian generalization guarantees for fairness on stochastic and deterministic classifiers. 2025. hal-05505285

HAL Id: hal-05505285

https://hal.science/hal-05505285v1

Preprint submitted on 11 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
PAC-BAYESIAN GENERALIZATION GUARANTEES FOR FAIRNESS
ON STOCHASTIC AND DETERMINISTIC CLASSIFIERS

Julien Bastian

Université Jean Monnet Saint-Étienne, CNRS, Institut d Optique Graduate School,
Laboratoire Hubert Curien UMR 5516, F-42023, Saint-Etienne, France
julien.bastian@univ-st-etienne.fr

Benjamin Leblanc,

Pascal Germain

Département d'informatique et de génie logiciel, Université Laval, Québec, Canada
benjamin.leblanc.2@ulaval.ca pascal.germain@ulaval.ca

Amaury Habrard

Université Jean Monnet Saint-Étienne, CNRS, Institut d Optique Graduate School,
Laboratoire Hubert Curien UMR 5516, Inria, F-42023, Saint-Etienne, France
Institut Universitaire de France
amaury.habrard@univ-st-etienne.fr

Christine Largeron

Université Jean Monnet Saint-Étienne, CNRS, Institut d Optique Graduate School,
Laboratoire Hubert Curien UMR 5516, F-42023, Saint-Etienne, France
christine.largeron@univ-st-etienne.fr

Guillaume Metzler

Université Lumière Lyon 2, Universite Claude Bernard Lyon 1, ERIC, 69007, Lyon, France
guillaume.metzler@univ-lyon2.fr

Emilie Morvant

Université Jean Monnet Saint-Étienne, CNRS, Institut d Optique Graduate School,
Laboratoire Hubert Curien UMR 5516, F-42023, Saint-Etienne, France
emilie.morvant@univ-st-etienne.fr

Paul Viallard

Univ Rennes, Inria, CNRS IRISA - UMR 6074, F35000 Rennes, France
paul.viallard@inria.fr

ABSTRACT

Classical PAC generalization bounds on the prediction risk of a classifier are insufficient to provide
theoretical guarantees on fairness when the goal is to learn models balancing predictive risk and
fairness constraints. We propose a PAC-Bayesian framework for deriving generalization bounds for
fairness, covering both stochastic and deterministic classifiers. For stochastic classifiers, we derive
a fairness bound using standard PAC-Bayes techniques. Whereas for deterministic classifiers, as
usual PAC-Bayes arguments do not apply directly, we leverage a recent advance in PAC-Bayes to
extend the fairness bound beyond the stochastic setting. 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 in which the learning procedure directly optimizes a trade-off
between generalization bounds on the prediction risk and on the fairness. We empirically evaluate
our framework with three classical fairness measures, demonstrating not only its usefulness but also
the tightness of our bounds.
# 1 Introduction

With the widespread use of machine learning on human-related data comes a major responsibility: Ensuring that learning algorithms do not incorporate the discriminative biases contained in the training data. As a consequence, understanding and mitigating these biases has become a major topic (e.g., Czarnowska et al., 2021; Mehrabi et al., 2021; Caton & Haas, 2024). In this paper, we focus on group fairness (that is, the ability to treat groups equitably without causing discrimination, see, e.g., Dwork et al., 2012; Ustun et al., 2019), and we propose a principled approach to learn fair prediction models by leveraging generalization bounds from statistical learning theory. Traditionally, such generalization bounds provide high-probability guarantees that the empirical error of a model is close to its true error on unseen data. However, most existing generalization guarantees typically concern predictive risk only and offer no guarantee on the fairness of the model.

Our work addresses this gap by deriving generalization bounds for the family of fairness measures that can be expressed as a difference of risks. This yields a general framework encompassing several classical group fairness measures, such as Demographic Parity (Dwork et al., 2012), Equalized Odds or Equal Opportunity (Hardt et al., 2016). Our analysis relies on PAC-Bayesian theory (Shawe-Taylor & Williamson, 1997; McAllester, 1998), which offers a key advantage among learning theory tools: It enables the derivation of generalization bounds computable from data and directly optimizable, leading to self-bounding algorithms (Freund, 1998). Related works in this direction remain limited. In particular, Oneto et al. (2019, 2020) derived the first PAC-Bayesian generalization bound for fairness, but this theoretical result has not been computationally exploited and is restricted to stochastic classifiers and Equal Opportunity. More broadly, existing approaches to fairness generalization (e.g., Laakom et al., 2025; Woodworth et al., 2017; Agarwal et al., 2018; Denis et al., 2024) typically provide post-hoc guarantees: The bounds apply to a fixed model or algorithm after training and do not intervene in the learning process itself. To our knowledge, we propose the first PAC-Bayesian generalization bound for such general fairness measures for deterministic classifiers by leveraging recent advances in PAC-Bayes (Leblanc & Germain, 2025). A key distinction with existing fairness generalization bounds is that ours lead to a self-bounding algorithm. Indeed, the learned model comes with its own intrinsic certification of both accuracy and fairness, thereby enhancing the model's trustworthiness.

**Organization of the paper.** Section 2 covers PAC-Bayesian background for binary classification. Section 3 reviews the group fairness setting, and discusses existing generalization bounds. In Section 4, we derive new PAC-Bayesian bounds for fairness, which are used in Section 5 to design a self-bounding algorithm, empirically evaluated in Section 6.

# 2 General Supervised Classification Setting

## 2.1 Setting and Notations

A supervised binary classification task is modeled by an unknown distribution $\mathcal{P}$ defined over $\mathcal{X} \times \mathcal{Y}$, where $\mathcal{X} \subseteq \mathbb{R}^d$ is the input space of dimension $d$ and $\mathcal{Y} = \{-1, +1\}$ is the output space ($\mathcal{P}_{\mathcal{X}}$, resp. $\mathcal{P}_{\mathcal{Y}}$, denotes the marginal distribution of $\mathcal{P}$ over $\mathcal{X}$, resp. $\mathcal{Y}$). A learning sample $S = \{(x_i, y_i)\}_{i=1}^m$ contains $m$ examples drawn i.i.d. from $\mathcal{P}$; We denote by $\mathcal{P}^m$ the distribution of such a $m$-sample. Let $\mathcal{H}$ be a hypothesis space, where each $h \in \mathcal{H}$ is a classifier $h: \mathcal{X} \to \mathcal{Y}$. In most machine learning literature, the learner's objective is to find the hypothesis $h$ that assigns a label $y \in \mathcal{Y}$ to an input $x$ as accurately as possible. Given a binary loss $\ell: \mathcal{Y}' \times \mathcal{Y} \to \{0, 1\}$, the true risk $R_{\mathcal{P}}(h)$ of a hypothesis $h$ on the distribution $\mathcal{P}$ is defined by

$$R_{\mathcal{P}}(h) := \mathbb{E}_{(x,y) \sim \mathcal{P}} \ell(h(x), y),$$

and the empirical risk is $\hat{R}_S(h) := \frac{1}{m} \sum_{i=1}^m \ell(h(x_i), y_i)$. Then, the learner aims to find the best hypothesis $h \in \mathcal{H}$ that minimizes $R_{\mathcal{P}}(h)$. Since $\mathcal{P}$ is unknown, statistical learning theory approaches (see, e.g., Vapnik, 1999) classically promote minimizing an upper bound on the generalization gap: $|R_{\mathcal{P}}(h) - \hat{R}_S(h)|$. This line of thought is notably represented by PAC (Probably Approximately Correct) generalization bounds (Valiant, 1984) that take the form

$$\mathbb{P}_{S \sim \mathcal{P}^m} \left[ \forall h \in \mathcal{H}, \left| R_{\mathcal{P}}(h) - \hat{R}_S(h) \right| \le \epsilon \left( \frac{1}{\delta}, \frac{1}{m} \right) \right] \ge 1 - \delta.$$

Put into words, with high-probability (at least $1-\delta$) over the random choice of the sample $S$, tight generalization guarantees are obtained when the deviation $|R_{\mathcal{P}}(h) - \hat{R}_S(h)|$ is low, i.e., one wants $\epsilon(\frac{1}{\delta}, \frac{1}{m})$ to be as small as possible.

Our work studies a specific family of generalization bounds known as PAC-Bayesian bounds, which have the advantage of providing tight bounds that can be estimable, allowing us to develop algorithms looking for the direct minimization of the bound. Such algorithms are referred to as self-bounding algorithms (Freund, 1998).
## 2.2 Classical PAC-Bayesian Theory

PAC-Bayesian theory, introduced by McAllester (1998); Shawe-Taylor & Williamson (1997), provides generalization bounds in expectation over the hypothesis space $\mathcal{H}$. It assumes a prior distribution $\pi$ over $\mathcal{H}$, encoding an apriori belief about the hypotheses before observing the learning sample $S$. Then, given $S$, $\pi$, and $\mathcal{H}$, the learner outputs a posterior distribution $\rho$ over $\mathcal{H}$. This framework studies the risk of the stochastic Gibbs classifier, denoted by $G_\rho$, which classifies an input $x \in \mathcal{X}$ by first sampling a hypothesis $h$ from $\rho$ and then outputting $h(x)$. Accordingly, the Gibbs risk (true risk) is defined by

$$R_{\mathcal{P}}(G_{\rho}) := \mathbb{E}_{h \sim \rho} R_{\mathcal{P}}(h) = \mathbb{E}_{h \sim \rho} \mathbb{E}_{(x,y) \sim \mathcal{P}} \ell(h(x), y). \quad (1)$$

Its empirical counterpart is $\hat{R}_S(G_\rho) := \mathbb{E}_{h \sim \rho} \hat{R}_S(h)$. Classical PAC-Bayesian theory provides high-probability upper bounds on the generalization gap for the Gibbs risk (e.g., McAllester, 2003; Catoni, 2007; Seeger, 2002; Maurer, 2004). We recall below the generalization bound of Seeger (2002) (improved by Maurer, 2004), where the generalization gap is captured by the KL-divergence between two Bernoulli distributions: $kl(q\|p) := q \ln(\frac{q}{p})+(1-q) \ln(\frac{1-q}{1-p})$.

**Theorem 2.1** (Seeger, 2002; Maurer, 2004). For any distribution $\mathcal{P}$, any hypothesis set $\mathcal{H}$, any prior $\pi$ on $\mathcal{H}$, and $\delta \in (0, 1]$, with probability at least $1-\delta$ on the random choice $S \sim \mathcal{P}^m$, we have for any distribution $\rho$ on $\mathcal{H}$,

$$kl(\hat{R}_S(G_\rho) \| R_{\mathcal{P}}(G_\rho)) \le \frac{1}{m} \left[ KL(\rho \| \pi) + \ln \frac{2\sqrt{m}}{\delta} \right],$$

where $KL(\rho\|\pi) := \mathbb{E}_{h \sim \rho} \ln \frac{\rho(h)}{\pi(h)}$ is the KL-divergence.

Theorem 2.1 gives a lower and an upper bound (resp. denoted by $\downarrow$ and $\uparrow$) on the Gibbs risk, i.e., under the same assumptions, we simultaneously have

$$R_{\mathcal{P}}(G_{\rho}) \le \underbrace{\bar{kl}\left(\hat{R}_{S}(G_{\rho}) \middle\| \frac{1}{m}\left[KL(\rho\|\pi) + \ln \frac{2\sqrt{m}}{\delta}\right]\right)}_{R_{S}^{\uparrow}(\rho, \pi, \delta, G_{\rho})}, \quad (2)$$

$$\text{and } R_{\mathcal{P}}(G_{\rho}) \ge \underbrace{kl\left(\hat{R}_{S}(G_{\rho}) \middle\| \frac{1}{m}\left[KL(\rho\|\pi) + \ln \frac{2\sqrt{m}}{\delta}\right]\right)}_{R_{S}^{\downarrow}(\rho, \pi, \delta, G_{\rho})}, \quad (3)$$

with $\bar{kl}(q\|\epsilon) := \max_{r \in [0,1]}\{r : kl(q\|r) \le \epsilon\}$ and $kl(q\|\epsilon) := \min_{r \in [0,1]}\{r : kl(q\|r) \le \epsilon\}$. The above bounds hold for the stochastic Gibbs classifier $G_\rho$. While studying $G_\rho$ is of interest for randomized algorithms (e.g., Dziugaite & Roy, 2017), in many practical settings one aims to learn a deterministic model. Some PAC-Bayesian approaches proposed to derive generalization bounds for deterministic classifiers. One such approach relies on commonly named disintegrated or derandomized PAC-Bayesian bounds (e.g., Catoni, 2007; Blanchard & Fleuret, 2007; Rivasplata et al., 2020; Viallard et al., 2024a,b). They provide high-probability bounds over the random choice of $S$, but also over the random choice of a single model $h$ drawn from a learned $\rho$. As a result, although the bound is stated for a single $h$, this model remains random.

To obtain PAC-Bayesian bounds for a “fully” deterministic classifier, another approach consists in considering the weighted majority vote over $\mathcal{H}$ according to $\rho$, where each $h \in \mathcal{H}$ is weighted according to its probability $\rho(h)$, i.e.,

$$\forall x \in \mathcal{X}, H_{\rho}(x) := \mathbb{E}_{h \sim \rho} h(x). \quad (4)$$

A family of work establishes inequalities that upper-bound the majority vote's risk $R_{\mathcal{P}}(H_\rho)$ in terms of the Gibbs risk $R_{\mathcal{P}}(G_\rho)$ (e.g., Langford & Shawe-Taylor, 2002; McAllester, 2003; Lacasse et al., 2006; Masegosa et al., 2020; Roy et al., 2011; Germain et al., 2015; Leblanc & Germain, 2025). These results imply that an upper bound on $R_{\mathcal{P}}(G_\rho)$ leads to an upper bound on $R_{\mathcal{P}}(H_\rho)$, up to additional terms depending on the inequality. The simplest and most classical inequality Langford & Shawe-Taylor (2002) is

$$R_{\mathcal{P}}(H_{\rho}) \le 2R_{\mathcal{P}}(G_{\rho}). \quad (5)$$

Consequently, any high-probability upper bound on the Gibbs risk (e.g., Equation (2)) yields a high-probability upper bound on the majority vote's risk, up to a factor 2. When one aims to learn a low-error classifier, such upper bounds are usually sufficient. However, in this work we study group fairness measures that can be expressed as a difference of risk. In this case, deriving a generalization bound requires both upper and lower bounds, since bounding a difference involves controlling deviations on both sides.
# 3 Group Fairness Setting

PAC-Bayesian bounds are usually used to certify generalization capacities in terms of accuracy. As we discuss in Section 3.2, only a few results exist that provide such certification for fairness abilities. We address this gap by deriving PAC-Bayesian generalization bounds for fairness in supervised binary classification under the group fairness setting (see, e.g., Dwork et al., 2012), which we recall below.

## 3.1 Setting and Fairness Measures

We now assume each input $x \in \mathcal{X}$ to be associated with a binary sensitive attribute $g \in \mathcal{G} = \{a, b\}$, which indicates the subgroup to which $x$ belongs. We consider an unknown distribution $\mathcal{D}$ over $\mathcal{X} \times \mathcal{G} \times \mathcal{Y}$, so that an example is a triplet $(x, g, y) \sim \mathcal{D}$. Accordingly, a learning sample is now $S = \{(x_i, g_i, y_i)\}_{i=1}^m \sim \mathcal{D}^m$. Let denote $\mathcal{D}_{|g} = \mathcal{D}((x_i, y_i)|g_i=g)$ the conditional distribution of $(x_i, y_i)$ given $g_i=g$. Therefore, the true risk associated with a subgroup $g \in \mathcal{G}$ is given by

$$R_{\mathcal{D}_{|g}}(h) := \mathbb{E}_{(x,y) \sim \mathcal{D}_{|g}} \ell(h(x), y).$$

The empirical risk associated with a subgroup $g$ is computed using the part of the learning sample $S$ conditioned on the value $g$ of the sensitive attribute $S_{|g} = \{(x_i, g_i, y_i) \in S : g_i=g\}$, that is,

$$\hat{R}_{S_{|g}}(h) := \frac{1}{m_g} \sum_{i=1}^{m_g} \ell(h(x_i), y_i),$$

with $m_g$ the size of $S_{|g}$. To ensure a fair decision between the subgroups for a classifier $h$, the objective is to limit the discrepancy between the risks of the subgroups, i.e., $R_{\mathcal{D}_{|a}}(h)$ and $R_{\mathcal{D}_{|b}}(h)$ should be similar.

**General fairness risk.** We define this risk discrepancy as the absolute difference between the two subgroup risks, called true fairness risk,

$$\mathrm{RF}_{\mathcal{D}}(h) := |R_{\mathcal{D}_{|a}}(h) - R_{\mathcal{D}_{|b}}(h)|, \qquad (6)$$

and the empirical fairness risk is

$$\widehat{\mathrm{RF}}_{S}(h) := |\hat{R}_{S_{|a}}(h) - \hat{R}_{S_{|b}}(h)|. \qquad (7)$$

A classifier $h$ is then considered fair when $\mathrm{RF}_{\mathcal{D}}(h) \approx 0$. Note that, $\mathrm{RF}_{\mathcal{D}}(G_{\rho})$ denotes the true fairness Gibbs risk and $\mathrm{RF}_{\mathcal{D}}(H_{\rho})$ the true fairness risk of the majority vote. As illustrated by the following examples, Equation (6) provides a general framework that encompasses fairness measures expressible as differences of risks. This is made possible through appropriate choices of loss $\ell$ and distribution $\mathcal{D}$, and it applies identically to $h \in \mathcal{H}$, or $G_{\rho}$, or $H_{\rho}$.

**Demographic Parity (DP, Dwork et al., 2012).** A classifier is said to satisfy DP if its predictions are independent of the sensitive attribute. In our setting, this notion can be expressed as a risk discrepancy by choosing the loss $\ell(h(x), y) = \ell(h(x), +1)$. We have

$$\mathrm{DP}_{\mathcal{D}}(h) := |R_{\mathcal{D}_{X|a}}(h) - R_{\mathcal{D}_{X|b}}(h)|,$$

where $\mathcal{D}_{X|g}$ is the marginal distribution of $\mathcal{X}$ restricted to group $g$. A classifier is considered fair under DP if it has the same expected positive prediction across sensitive groups, i.e., $\mathbb{E}_{x \sim \mathcal{D}_{X|a}} \ell(h(x), +1) = \mathbb{E}_{x \sim \mathcal{D}_{X|b}} \ell(h(x), +1)$.

**Equalized Odds (EO, Hardt et al., 2016).** A classifier satisfies EO if its predictions are independent of the sensitive attribute conditionally on the true label. In fact, EO is related to DP in that it compares expected predictions across groups. The key difference is that the risk discrepancy is performed separately for each class. For a class $y \in \mathcal{Y}$, and loss $\ell(h(x), y) = \ell(h(x), +1)$, we have

$$\mathrm{EO}_{\mathcal{D}}^{y}(h) := |R_{\mathcal{D}_{X|y,a}}(h) - R_{\mathcal{D}_{X|y,b}}(h)|,$$

with $\mathcal{D}_{X|y,g}$ the marginal distribution of $\mathcal{X}$ restricted to class $y$ and group $g$. The overall EO is obtained by aggregating the average between the classes of $\mathcal{Y} = \{-1, +1\}$:

$$\mathrm{EO}_{\mathcal{D}}(h) := \mathbb{P}_{y \sim \mathcal{D}_{\mathcal{Y}}} [y=1] \mathrm{EO}_{\mathcal{D}}^{+1}(h) + \mathbb{P}_{y \sim \mathcal{D}_{\mathcal{Y}}} [y=-1] \mathrm{EO}_{\mathcal{D}}^{-1}(h).$$

Intuitively, this means that $h$ should behave similarly across sensitive groups on both classes.

**Equal Opportunity (EOP, Hardt et al., 2016).** A classifier is said to satisfy EOP if its predictions are independent of the sensitive attributes for one class of interest $y \in \mathcal{Y}$. When this class is $y=+1$, with $\ell(h(x), y) = \ell(h(x), +1)$, EOP is

$$\mathrm{EOP}_{\mathcal{D}}(h) := \mathrm{EO}_{\mathcal{D}}^{+1}(h).$$
## 3.2 Generalization Bounds for Fairness

**Related Works.** There exist only a few works on generalization bounds for fairness measures. Among them, some concern the derivation of bounds for specific fairness measures, such as Woodworth et al. (2017) for EO, or Agarwal et al. (2018) for DP and EO, or Denis et al. (2024) for DP. It is noteworthy that all these bounds are derived for specific algorithms and classifiers. Recently, Laakom et al. (2025) established an information-theoretic general framework to derive generalization bounds for various fairness measures that they applied to DP and EO. While their results apply to a broad class of models, their resulting bounds do not lead to self-bounding algorithms. They provide post-hoc guarantees on the fairness of a learned predictor that are not directly exploitable as learning objectives.

**A PAC-Bayesian Bound.** The most closely related work is the PAC-Bayesian EOP-bound for the stochastic Gibbs classifier proposed by Oneto et al. (2019, 2020). For comparison purposes, we present in Theorem 3.1 a generalization of Oneto et al. (2020, Th. 1) to the general fairness risk of Equation (6). We discuss this result further in Appendix A.

**Theorem 3.1 (Generalization of Th. 1 of Oneto et al., 2020).** For any distribution $\mathcal{D}$, any hypothesis set $\mathcal{H}$, any prior $\mathcal{P}$ on $\mathcal{H}$, any $\delta \in (0, 1]$, with probability at least $1 - \delta$ on the random choice $S \sim \mathcal{D}^m$, we have for every $\rho$ on $\mathcal{H}$,

$$ \mathrm{RF}_{\mathcal{D}}(G_{\rho}) \leq |\hat{\mathrm{R}}_{S_b}(G_{\rho}) - \hat{\mathrm{R}}_{S_a}(G_{\rho})| + \sqrt{\frac{\mathrm{KL}(\rho\|\pi) + \ln \frac{4\sqrt{m_a}}{\delta}}{2m_a}} + \sqrt{\frac{\mathrm{KL}(\rho\|\pi) + \ln \frac{4\sqrt{m_b}}{\delta}}{2m_b}} $$

*Proof.* We apply the Oneto et al.'s proof process on the general fairness risk (instead of EOP). We have

$$ \begin{aligned} |\mathrm{RF}_{\mathcal{D}}(G_{\rho}) - \mathrm{RF}_{S}(G_{\rho})| &= |\mathrm{R}_{\mathcal{D}|_{a}}(G_{\rho}) - \mathrm{R}_{\mathcal{D}|_{b}}(G_{\rho})| - |\hat{\mathrm{R}}_{S|_{a}}(G_{\rho}) - \hat{\mathrm{R}}_{S|_{b}}(G_{\rho})| \\ &\leq |\mathrm{R}_{\mathcal{D}|_{a}}(G_{\rho}) - \hat{\mathrm{R}}_{S|_{a}}(G_{\rho})| + |\mathrm{R}_{\mathcal{D}|_{b}}(G_{\rho}) - \hat{\mathrm{R}}_{S|_{b}}(G_{\rho})|. \end{aligned} $$

We apply McAllester (2003)'s PAC-Bayes bound (see Theorem A.2) separately to each group, with probability at least $1 - \frac{\delta}{2}$. A union bound on the groups gives the result. $\square$

Although the results of Oneto et al. (2020, 2019) are purely theoretical and limited to EOP, they suggest a way (recalled in Appendix A) to define $\pi$ and $\rho$ to favor classifiers in $\mathcal{H}$ that achieve both good accuracy and good EOP, following a standard method in PAC-Bayes theory (e.g., Catoni, 2007; Lever et al., 2013). However, as noted by the authors, this method is hard to implement and may lead to numerical instabilities, especially when dealing with continuous distributions (thus, it is not evaluated in their work). Note that, this method is not self-bounding.

That said, since $\mathrm{RF}_{\mathcal{D}}(G_{\rho})$ involves a deviation between the subgroup risks, Theorem 3.1 only holds for the stochastic Gibbs classifier and cannot be used to obtain upper bounds for the risk of the deterministic majority vote $\mathrm{RF}_{\mathcal{D}}(H_{\rho})$.

# 4 Fairness Generalization Bounds

This section focuses on the derivation of PAC-Bayesian generalization bounds for the general fairness risk $\mathrm{RF}_{\mathcal{D}}(\cdot)$ (Equation (6)), paving the way to our fair self-bounding learning algorithm (Section 5). We first derive, in Section 4.1, a tighter bound than the one of Theorem 3.1 for the stochastic Gibbs classifier by relying on Theorem 2.1 (known to yield tighter bounds than Theorem A.2 on which Theorem 3.1 is based). Then, by leveraging a recent result in PAC-Bayes that allows adapting guarantees from stochastic to deterministic classifiers (Leblanc & Germain, 2025), we turn to deterministic classifiers in Section 4.2, and to a computable specialization to the majority vote in Section 4.3. Overall, our PAC-Bayesian bounds yield practical and theoretical benefits: (i) They can be instantiated to fairness measures that can be expressed as a risk discrepancy; (ii) They are computable from a learning sample $S$; (iii) When combined with a PAC-Bayesian generalization bound on the predictive risk $\mathrm{R}_{\mathcal{D}}(\cdot)$, they lead to a self-bounding algorithm to learn a model that directly minimizes a generalization bound on the trade-off between fairness and predictive risks.

## 4.1 Stochastic Classifier

Theorem 4.1 states our PAC-Bayesian bound on the general fairness risk of the Gibbs classifier $\mathrm{RF}_{\mathcal{D}}(G_{\rho})$.

**Theorem 4.1.** For any distribution $\mathcal{D}$, any hypothesis set $\mathcal{H}$, any prior $\pi$ on $\mathcal{H}$, any $\delta \in (0, 1]$, with probability at least $1 - \delta$ on the random choice $S \sim \mathcal{D}^m$, we have for any $\rho$ on $\mathcal{H}$,

$$ \mathrm{RF}_{\mathcal{D}}(G_{\rho}) \leq \max \{ \mathrm{R}_{S|_{a}}^{\dagger}(\rho, \pi, \frac{\delta}{4}, G_{\rho}) - \mathrm{R}_{S|_{b}}^{\dagger}(\rho, \pi, \frac{\delta}{4}, G_{\rho}), \mathrm{R}_{S|_{a}}^{\dagger}(\rho, \pi, \frac{\delta}{4}, G_{\rho}) - \mathrm{R}_{S|_{b}}^{\dagger}(\rho, \pi, \frac{\delta}{4}, G_{\rho}) \}. $$
**Proof.** We apply Theorem 2.1 to bound the Gibbs risk on each group with probability $1-\frac{\delta}{2}$: Equation (2) upper-bounds $R_{D|a}(G_\rho)$, Equation (3) lower-bounds $R_{D|b}(G_\rho)$. We combine them by a union bound. With probability at least $1-\frac{\delta}{2}$ on $S \sim D^m$, we have, for any $\rho$ on $\mathcal{H}$,

$$R_{D|a}(G_\rho) - R_{D|b}(G_\rho) \le R_{S|a}^\top(\rho, \pi, \frac{\delta}{4}, G_\rho) - R_{S|b}^\downarrow(\rho, \pi, \frac{\delta}{4}, G_\rho).$$

Since $RF_D(G_\rho) = |R_{D|a}(G_\rho) - R_{D|b}(G_\rho)|$, we apply the same argument symmetrically. By a union bound, the resulting bounds hold simultaneously. Taking their maximum yields the desired result. $\square$

In contrast to the proof of Theorem 3.1, which is restricted to McAllester's bound (Theorem A.2), a key feature of our proof is its generality: It can be instantiated with any PAC-Bayesian bound for the Gibbs risk that provides both a lower and an upper bound. Our result in Theorem 4.1 is based on the Seeger's bound (Theorem 2.1), which is tighter than McAllester's bound due to Pinsker's inequality: $\forall (p, q) \in [0, 1]^2$, $2(q-p)^2 \le kl(q\|p)$ (Wu, 2017; Canonne, 2022). Thus, our bound is tighter than Theorem 3.1.

While the stochastic Gibbs classifier is by nature the classical object of study of PAC-Bayes and shows interest for randomized algorithms, quantities such as $RF_D(G_\rho)$ might not be representative of its actual fairness: The next example illustrates a situation where the DP of each classifier in $\mathcal{H}$ is high, but where $RF_D(G_\rho)$ fails to convey this information.

**Example 4.2.** Let $\mathcal{H} = \{h_1, h_2\}$ and $\rho(h_1), \rho(h_2) = 0.5$. Suppose that $R_{D|a}(h_1) = R_{D|b}(h_2) = 1$, and $R_{D|b}(h_1) = R_{D|a}(h_2) = 0$. Since $R_{D|a}(G_\rho) = \frac{1}{2}(1+0) = \frac{1}{2}$, we have

$$\bullet \text{ RF}_D(h_1) = |R_{D|a}(h_1) - R_{D|b}(h_1)| = |1 - 0| = 1;$$

$$\bullet \text{ RF}_D(h_2) = |R_{D|a}(h_2) - R_{D|b}(h_2)| = |0 - 1| = 1;$$

$$\bullet \text{ RF}_D(G_\rho) = |R_{D|a}(G_\rho) - R_{D|b}(G_\rho)| = |\frac{1}{2} - \frac{1}{2}| = 0.$$

Therefore, in the following sections, we focus on the derivation of generalization bounds for deterministic classifiers.

## 4.2 Deterministic Classifiers

Recall that classical inequalities that upper-bound the majority vote's risk $R_D(H_\rho)$ in terms of the Gibbs risk $R_D(G_\rho)$ (e.g., Equation (5)) allow PAC-Bayesian upper bounds to be transferred from $G_\rho$ to $H_\rho$. However, such inequalities do not extend to differences of Gibbs risks, as required for the general fairness measure (as in Theorems 3.1 and 4.1). To overcome this limitation, we leverage a recent result by Leblanc & Germain (2025), which decomposes the risk of a single deterministic classifier $h \in \mathcal{H}$ into the Gibbs risk and two conditional expectations terms.

**Proposition 4.3 (Risk decomposition, Leblanc & Germain, 2025).** Assume that $\mathfrak{l}_D^\rho(h) - \mathfrak{o}_D^\rho(h) \neq 0$. Then, for any $h \in \mathcal{H}$ and distribution $\rho$ on $\mathcal{H}$, the true risk of $h$ satisfies

$$R_D(h) = \frac{R_D(G_\rho) - \mathfrak{o}_D^\rho(h)}{\mathfrak{l}_D^\rho(h) - \mathfrak{o}_D^\rho(h)}, \qquad (8)$$

$$\text{with } \mathfrak{o}_D^\rho(h) := \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \mathbb{E}_{h'\sim\rho} \ell(h'(x), y) \mid \ell(h(x), y) = 0 \right],$$

$$\text{and } \mathfrak{l}_D^\rho(h) := \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \mathbb{E}_{h'\sim\rho} \ell(h'(x), y) \mid \ell(h(x), y) = 1 \right].$$

**Proof.** The proof is recalled in Appendix B.1. $\square$

Equation (8) relates the risk of a classifier $R_D(h)$ to the Gibbs risk $R_D(G_\rho)$ and the terms $\mathfrak{o}_D^\rho(h)$ and $\mathfrak{l}_D^\rho(h)$ that measure how $\rho$ conditionally behaves on correct and incorrect predictions of $h$. This suggests that controlling $R_D(h)$ requires more than solely a bound on $R_D(G_\rho)$. Thus, bounding $R_D(h)$ reduces to obtaining simultaneous bounds on three quantities: $R_D(G_\rho)$, $\mathfrak{o}_D^\rho(h)$, and $\mathfrak{l}_D^\rho(h)$.

To be able to extend PAC-Bayesian bounds beyond the stochastic setting for $RF_D(h) = |R_{D|a}(h) - R_{D|b}(h)|$, we need both the following upper and lower bounds on the risk $R_D(h)$ of a deterministic classifier.

**Lemma 4.4 (Bounds on $R_D(h)$).** For any distribution $\mathcal{D}$, any hypothesis set $\mathcal{H}$, any prior $\pi$ on $\mathcal{H}$, let $\rho$ be a distribution on $\mathcal{H}$, and $h \in \mathcal{H}$, and $\delta \in (0, 1]$.

**Upper bound (Leblanc & Germain, 2025):** With probability at least $1-\delta$ on $S \sim D^m$, if
$$R_D(G_\rho) \le R_S^\dagger(\rho, \pi, \delta, G_\rho), \quad o_D^\rho(h) \ge o_D^\dagger(h, \rho), \quad 1_D^\rho(h) \ge 1_D^\dagger(h, \rho),$$
with $1_D^\dagger(h, \rho) > o_D^\dagger(h, \rho)$, then we have

$$R_D(h) \le \frac{R_S^\dagger(\rho, \pi, \delta, G_\rho) - o_D^\dagger(h, \rho)}{1_D^\dagger(h, \rho) - o_D^\dagger(h, \rho)} := \mathfrak{R}_S^\dagger(\rho, \pi, \delta, h). \quad (9)$$

**Lower bound:** With probability at least $1-\delta$ on $S \sim D^m$, if

$$R_D(G_\rho) \ge R_S^\dagger(\rho, \pi, \delta, G_\rho), \quad o_D^\rho(h) \le o_D^\dagger(h, \rho), \quad 1_D^\rho(h) \le 1_D^\dagger(h, \rho),$$
with $1_D^\dagger(h, \rho) > o_D^\dagger(h, \rho)$, then we have

$$R_D(h) \ge \frac{R_S^\dagger(\rho, \pi, \delta, G_\rho) - o_D^\dagger(h, \rho)}{1_D^\dagger(h, \rho) - o_D^\dagger(h, \rho)} := \mathfrak{R}_S^\dagger(\rho, \pi, \delta, h). \quad (10)$$

*Proof.* The proof is deferred to Appendix B.2. □

At this step, the upper $\dagger$ and lower $\downarrow$ bounds on $o_D^\rho(h)$ and $1_D^\rho(h)$ are assumed to exist. In fact, Equations (9) and (10) formalize that high-probability upper and lower bounds on the risk of a deterministic classifier $h$ is obtainable from a PAC-Bayesian bound on the Gibbs risk and additional bounds on the conditional expectations $o_D^\rho(h)$ and $1_D^\rho(h)$. Section 4.3 shows how one can compute these bounds when $h$ is a majority vote.

We now derive our main result: A high-probability upper bound for the fairness general measure of a deterministic $h$.

**Theorem 4.5.** For any distribution $D$, any hypothesis set $H$, any prior $\pi$ on $H$, and $\delta \in (0, 1]$, with probability at least $1-\delta$ over the random choice of $S \sim D^m$ we have for any $\rho$ over $H$ and any $h \in H$

$$\mathrm{RF}_D(h) \le \max \left\{ \mathfrak{R}_{S_{|a}}^{\dagger}(\rho, \pi, \frac{\delta}{4}, h) - \mathfrak{R}_{S_{|b}}^{\dagger}(\rho, \pi, \frac{\delta}{4}, h), \mathfrak{R}_{S_{|b}}^{\dagger}(\rho, \pi, \frac{\delta}{4}, h) - \mathfrak{R}_{S_{|a}}^{\dagger}(\rho, \pi, \frac{\delta}{4}, h) \right\}.$$

*Proof.* Using Proposition 4.3, we rewrite the risk difference for a classifier. For any $D$ on $X$, any $Q$ on $H$, and any $h \in H$ s.t. $o_{D|a}^\rho(h) \ne 1_{D|a}^\rho(h)$ and $o_{D|b}^\rho(h) \ne 1_{D|b}^\rho(h)$, we have

$$R_{D|a}(h) - R_{D|b}(h) = \frac{R_{D|a}(G_\rho) - o_{D|a}^\rho(h)}{1_{D|a}^\rho(h) - o_{D|a}^\rho(h)} - \frac{R_{D|b}(G_\rho) - o_{D|b}^\rho(h)}{1_{D|b}^\rho(h) - o_{D|b}^\rho(h)}$$

We apply Equation (9) to upper-bound the risk decomposition for group $a$ with probability $1-\frac{\delta}{4}$, and Equation (10) to lower-bound the decomposition for group $b$ with probability $1-\frac{\delta}{4}$. We combine them via a union bound to obtain, with probability at least $1-\frac{\delta}{2}$ on $S \sim D^m$, that for all $\rho$ on $H$,

$$R_{D|a}(h) - R_{D|b}(h) \le \mathfrak{R}_{S_{|a}}^{\dagger}(\rho, \pi, \frac{\delta}{4}, h) - \mathfrak{R}_{S_{|b}}^{\dagger}(\rho, \pi, \frac{\delta}{4}, h).$$

Using $|c-d| = \max\{c-d, d-c\}$, $\forall c, d \in \mathbb{R}$, we apply the same argument symmetrically. By union bound, both results hold simultaneously. Taking the maximum of the resulting upper bounds yields the desired result. □

Importantly, Theorem 4.5 differs from standard results in PAC-Bayes in two ways: (i) It provides a generalization guarantee on the difference of two risks instead of an upper bound on a single risk, in the same fashion as Theorem 4.1; (ii) It relates to a single deterministic classifier $h$. Point (ii) is of primary interest since, as we mentioned earlier, it is not possible to relate the difference between two risks defined for the deterministic majority vote $H_\rho$ with the difference of two Gibbs risks. Therefore, a bound on the latter quantity cannot be used to infer any information about $H_\rho$ (which is the major limitation of the result of Oneto et al. (2020)).

## 4.3 Specialization to Weighted Majority Votes

To make Theorem 4.5 computable, we need upper $\dagger$ and lower $\downarrow$ bounds on the conditional expectations $o_D^\rho(h)$ and $1_D^\rho(h)$. To do so, we follow the approach of Leblanc & Germain (2025). We assume a finite set of $n$ base classifiers $\mathcal{F} = \{f_1, \dots, f_n\}$, with $f_i: X \to Y$. Each hypothesis is represented as a weighted majority vote on $\mathcal{F}$, parameterized by a weight vector $\mathbf{w} \in \mathbb{R}^n$. Accordingly, the hypothesis set $\mathcal{H}$ is defined as

$$\mathcal{H} := \left\{ h_{\mathbf{w}} := \sum_{i=1}^{n} w_i f_i \mid \mathbf{w} \in \mathbb{R}^n \right\}. \quad (11)$$
Thus, a hypothesis $h_w \in \mathcal{H}$ is fully specified by its associated weight vector $w$. In this setting, a posterior distribution $\rho$ over $\mathcal{H}$ is equivalently defined as a distribution over the weight vectors $w$. Furthermore, we consider three families of posterior distributions, each parameterized by $\alpha \in \mathbb{R}^n$, which admit different sets of realizations $w$:

* Categorical $\mathcal{C}(\alpha)$, where $w \in \{0, 1\}^n$ with $\sum_i w_i = 1$,

* Dirichlet $\text{Dir}(\alpha)$, where $w$ lies on the probability simplex, i.e., $w \in [0, 1]^n$ with $\sum_i w_i = 1$,

* Unit-variance Gaussian $\mathcal{N}(\alpha, \mathbf{I}_{n \times n})$, where $w \in \mathbb{R}^n$.

In this context, Leblanc & Germain (2025) proposed to learn the deterministic classifier $h_\alpha \in \mathcal{H}$. When $\rho$ is Categorical or Gaussian (Langford & Shawe-Taylor, 2002), $\alpha$ acts both as the parameter of the studied classifier $h_\alpha$ and the parameters of a posterior distribution $\rho$ over $\mathcal{H}$ parametrized by $\alpha$.<fnref n="1" /> The latter expresses a majority vote $H_\rho$ as in Equation (4). It remains to bound $\mathcal{O}_D^\rho(h_\alpha)$ and $\mathbf{1}_D^\rho(h_\alpha)$. The trick is to find their smallest and biggest attainable value. This can be done by applying the partition problem algorithm to $\alpha$:

$$ \underset{\alpha_1, \alpha_2}{\operatorname{argmin}} \left\{ \left| \sum_{\alpha \in \alpha_1} \alpha - \sum_{\alpha \in \alpha_2} \alpha \right| : \{\alpha_1, \alpha_2\} \text{ is a partition of } \alpha \right\}. $$

Proposition 4.6 gives tractable upper and lower bounds on $\mathcal{O}_D^\rho(h_\alpha)$ and $\mathbf{1}_D^\rho(h_\alpha)$. The lower bounds are due to Leblanc & Germain (2025), while the upper bounds are novel.

**Proposition 4.6.** Let $\alpha_1$ and $\alpha_2$ be the result of the partition problem applied to $\alpha$. Let $\tilde{\alpha} = \max(\sum_{\alpha \in \alpha_1} \alpha, \sum_{\alpha \in \alpha_2} \alpha)$, and $\bar{\alpha} = |\sum_{\alpha \in \alpha_1} \alpha - \sum_{\alpha \in \alpha_2} \alpha|$. For any distribution $\mathcal{D}$, with $\ell(h_\alpha(x), y) = \mathbf{I}[\operatorname{sign}(h_\alpha(x)) \neq y]$, we have
1. If $\rho = \mathcal{C}(\alpha)$, then

$$ 0 \le \mathcal{O}_D^\rho(h_\alpha) \le 1 - \tilde{\alpha}, \text{ and } \tilde{\alpha} \le \mathbf{1}_D^\rho(h_\alpha) \le 1; $$

2. If $\rho = \text{Dir}(\alpha)$, with $I_{0.5}(\cdot)$ the regularized incomplete beta function evaluated at 0.5, then

$$ 0 \le \mathcal{O}_D^\rho(h_\alpha) \le I_{0.5}(\tilde{\alpha}, \|\alpha\|_1 - \tilde{\alpha}), \\ \text{and } I_{0.5}(\|\alpha\|_1 - \tilde{\alpha}, \tilde{\alpha}) \le \mathbf{1}_D^\rho(h_\alpha) \le 1; $$

3. If $\rho = \mathcal{N}(\alpha, \mathbf{I}_{n \times n})$, with $\Phi(k) := \frac{1}{2}[1 - \text{Erf}(\frac{k}{\sqrt{2}})]$ and $\text{Erf}(k) := \frac{2}{\sqrt{\pi}} \int_0^k e^{-t^2} dt$, then

$$ \Phi\left(\frac{\|\alpha\|_1}{\sqrt{n}}\right) \le \mathcal{O}_D^\rho(h_\alpha) \le \Phi\left(\frac{\bar{\alpha}}{\sqrt{n}}\right), \\ \text{and } 1 - \Phi\left(\frac{\bar{\alpha}}{\sqrt{n}}\right) \le \mathbf{1}_D^\rho(h_\alpha) \le 1 - \Phi\left(\frac{\|\alpha\|_1}{\sqrt{n}}\right). $$

*Proof.* The proof is deferred to Appendix B.3. □

The conditions required to apply Lemma 4.4 (namely, $\mathbf{1}_D^\perp(h, \rho) > \mathcal{O}_D^\perp(h, \rho)$ and $\mathbf{1}_D^\uparrow(h, \rho) > \mathcal{O}_D^\uparrow(h, \rho)$) are satisfied for each considered distribution in Proposition 4.6. This allows us to apply Theorem 4.5 to the deterministic majority vote $H_\rho$, and thus to learn a majority vote by minimizing the resulting bound as described in the next section.

# 5 A Fair Self-Bounding Algorithm

We now derive our learning procedure, which consists of the minimization of a trade-off between the prediction risk and a fairness measure. For a given hypothesis set $\mathcal{H}$ and a trade-off parameter $\lambda \in [0, 1]$, we want to solve

$$ \underset{h \in \mathcal{H}}{\operatorname{argmin}} (1 - \lambda) \mathcal{R}_{\mathcal{D}}(h) + \lambda \mathcal{R}_{\mathcal{D}}(h). \qquad (12) $$

Balancing this trade-off yields a fairness-aware learning problem (Menon & Williamson, 2018), where the emphasis on fairness depends on $\lambda$. Since $\mathcal{D}$ is unknown, Equation (12) cannot be solved directly. A common strategy is to use the empirical risk minimization (ERM) principle by replacing $\mathcal{R}_{\mathcal{D}}(\cdot)$ and $\mathcal{R}_{\mathcal{D}}(\cdot)$ with their empirical counterpart. In such a situation, generalization guarantees are typically obtained post-hoc, by deriving bounds for the learned classifier.

<footnote n="1">¹For the Dirichlet distribution, one needs to normalize $\alpha$, see Leblanc & Germain (Sec. 4.2, 2025) for details.</footnote>
**Algorithm 1 Fair Self-Bounding Learning Algorithm**

**Require:** Learning set $S = \{(x_i, y_i)\}_{i=1}^m$, epoch number $T$, prior $\pi$, confidence $\delta$, tradeoff param. $\lambda$, fairness measure (DP, EOP, or EP), Objective ($G_S(\rho)$, or $H_S(\rho)$).

1: **for** $t = 1$ to $T$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp;**for all** mini-batches $U \subset S$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute the empirical Gibbs risk $\hat{R}_U(G_\rho)$

4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute the empirical fairness risk $\hat{R}_F(U)(G_\rho)$,

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;given the chosen fairness measure

6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute the bound $G_U(\rho)$

7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Update $\rho$ using a gradient step

8: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

9: **end for**

10: **if** Objective is $H_S(\rho)$ **then**

11: &nbsp;&nbsp;&nbsp;&nbsp;Update $\rho$ using, in turn, Heuristics 5.1 to 5.3

12: **end if**

13: **Output:** Posterior distribution $\rho$

A novelty of our approach is to directly optimize generalization guarantees on $R_D(\cdot)$ and $RF_D(\cdot)$. This amounts to replacing them in Equation (12) by their respective generalization upper bounds using a union bound (the complete bounds are given in Theorems B.1 and B.2 in Appendix B.4). In the PAC-Bayesian setting of Section 4, where $\mathcal{H}$ is defined as in Equation (11) and the posterior $\rho$ is either $C(\alpha)$, Dir($\alpha$), or $\mathcal{N}(\alpha)$, this leads to learning either a stochastic classifier<fnref n="2" /> $G_\rho$ or a deterministic majority vote $H_\rho=h_\alpha$, depending on the bounds used as training objectives: $G_\rho$ is learned by optimizing the bounds from Theorem 2.1 and Theorem 4.1; $H_\rho$ is learned by optimizing the bounds from Lemma 4.4 (Equation (9)) and Theorem 4.5. Given a learning sample $S$, we respectively obtain the following learning objectives:

$$ G_S(\rho) = (1-\lambda) R_S^{\uparrow}(\rho, \pi, \frac{\delta}{2}, G_\rho) \\ + \lambda \max \left\{ R_{S|a}^{\uparrow}(\rho, \pi, \frac{\delta}{8}, G_\rho) - R_{S|b}^{\downarrow}(\rho, \pi, \frac{\delta}{8}, G_\rho), R_{S|b}^{\uparrow}(\rho, \pi, \frac{\delta}{8}, G_\rho) - R_{S|a}^{\downarrow}(\rho, \pi, \frac{\delta}{8}, G_\rho) \right\}, \quad (13) $$

$$ \text{and } H_S(\rho) = (1-\lambda) \mathfrak{R}_S^{\uparrow}(\rho, \pi, \frac{\delta}{2}, H_\rho) \\ + \lambda \max \left\{ \mathfrak{R}_{S|a}^{\uparrow}(\rho, \pi, \frac{\delta}{8}, H_\rho) - \mathfrak{R}_{S|b}^{\downarrow}(\rho, \pi, \frac{\delta}{8}, H_\rho), \mathfrak{R}_{S|b}^{\uparrow}(\rho, \pi, \frac{\delta}{8}, H_\rho) - \mathfrak{R}_{S|a}^{\downarrow}(\rho, \pi, \frac{\delta}{8}, H_\rho) \right\}. \quad (14) $$

Here, the fairness measure, the confidence $\delta$, and the prior $\pi$ are provided as inputs of the algorithm. The associated minimization problems $\text{argmin}_\rho G_S(\rho)$ and $\text{argmin}_\rho H_S(\rho)$ define self-bounding algorithms (Freund, 1998)<fnref n="3" />, in the sense that the learned classifier is obtained by directly minimizing its own generalization bound. Our overall minimization procedure is summarized in Algorithm 1. When learning a Gibbs classifier, we minimize $G_S(\rho)$ using a standard gradient descent approach (Lines 1 to 9). In contrast, when learning a majority vote $H_\rho$, directly minimizing $H_S(\rho)$ is not possible since the bounds on $\sigma_D^\rho(h)$ and $\iota_D^\rho(h)$, as described in Proposition 4.6, are by nature discrete. To address this issue, we propose a two-phase optimization. First, since the bounds in Theorems 2.1 and 4.1 (the content of $G_S(\rho)$) are the backbone of the bounds in Lemma 4.4 and Theorem 4.5 (the content of $H_S(\rho)$), we minimize $G_S(\rho)$. Then, we apply the three following heuristics, ensuring that the bounds of Proposition 4.6 on $\sigma_D^\rho(h_\alpha)$ and $\iota_D^\rho(h_\alpha)$, which play a crucial role in $H_S(\rho)$, are as tight as possible (Lines 10 to 12).

**Heuristic 5.1.** We clip the smallest absolute values of $\alpha$ to 0, increasing $\tilde{\alpha}$ and $\bar{\alpha}$ in proposition 4.6, until $H_S(\rho)$ does not decay anymore.

**Heuristic 5.2.** We apply a coordinate descent on the posterior values (increasing the largest components of $\alpha$ and decreasing the smallest ones), directly increasing $\tilde{\alpha}$ and $\bar{\alpha}$ in proposition 4.6, until $H_S(\rho)$ does not decay anymore.

**Heuristic 5.3.** Since $\tilde{\alpha}$ and $\bar{\alpha}$ grow linearly with $\|\alpha\|_1$, we apply a multiplicative growing factor to each element in $\alpha$ until $H_S(\rho)$ does not decay anymore.

# 6 Experiments<fnref n="4" />

**Datasets.** Following the suggestions of Han et al. (2024), we use the AI Fairness 360 toolkit (Bellamy et al., 2019) to empirically evaluate our theoretical framework on 5 different datasets: Adult Census Income (ADULT, Kohavi,

<footnote n="2">²The Gibbs classifier on a set of majority vote is also referred to as the stochastic majority vote (Zantedeschi et al., 2021).</footnote>

<footnote n="3">³Self-bounding algorithms have recently regained interest in PAC-Bayes, see e.g., Rivasplata (2022); Viallard (2023).</footnote>

<footnote n="4">⁴Our code is provided as supplementary material and will be publicly available upon publication.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: Test error and generalization bound of a stochastic majority vote classifier and its deterministic counterpart for Demographic Parity (DP).</figcaption></figure>

1996), ProPublica Recidivism (COMPAS, Angwin et al., 2016), German Credit (GERMAN, Hofmann, 1994), and Medical Expenditure Panel Surveys, version 1 (MEPS, AHRQ, 2015, 2016). In each dataset, two sensitive attributes are considered, selected from {age, gender, race}. The test set consists of a random 20% split of the available data. A thorough overview of the datasets is given in Appendix C.1.

**Models.** We consider majority votes of data-independent hypotheses consisting of axis-aligned decision stumps, with thresholds evenly spread over the input space (10 per feature). We independently experiment with all admissible posterior family (Categorical, Dirichlet, and Gaussian) and use a uniform prior from the same family as the posterior.

**Objective function.** Given a dataset and a sensitive attribute, the task is to minimize the learning objective given by Equations (13) or (14), instantiated by one fairness metric among DP, EO, or EOP, using Algorithm 1. Given a fixed objective function and a posterior distribution type, we consider $\lambda \in \{0, 0.1, 0.25, 0.5, 0.75, 0.9, 1\}$.

**Baselines.** We compare our approach to a self-bounding algorithm denoted by “O1”, obtained by the minimization of Equation (13) when instantiated by the bound of Oneto et al. (2019) (Theorem 3.1). For completeness, we consider the method (which is not self-bounding) suggested by Oneto et al. (2020) denoted by “O2” (recalled in Appendix A) and for which we compute post-hoc bounds on $RF_D(G_\rho)$ using a data-dependent prior. Developed for the EOP metric, we generalized it to the DP metric, but were not able to do so for the EO metric. Moreover, O2, unstable for continuous distributions, is only used with the Categorical distribution.

**Optimization.** The models are trained using SGD with the Adam optimizer Kingma & Ba (2015). We used a batch size equal to 1, 024, and a learning rate of 0.1 with a scheduler reducing this parameter by a factor of 10 with an epoch patience of 2. The maximal number of epochs is 100, and patience is 25 for performing early stopping.

**Model selection.** We report the results obtained by the model having the best average bound (over 5 random seeds) for $RF_D(h)$, out of the various $\lambda$ and distributions tested, for our method for deterministic classifiers and O1. For O2 and our method for a stochastic classifier, the criterion for model selection is the best bound on $RF_D(G_\rho)$.

**Analysis.** Figure 1 reports the results for Demographic Parity (numerical values, as well as results for EO and EOP, are provided in Appendix C.2).

*On bound tightness.* Except for the deterministic classifier on MEPS, our proposed bounds are tight for both risk and fairness while achieving competitive or improved risk and DP values. This behavior supports the use of self-bounding algorithms for learning models with their own guarantees. Note that, since the deterministic classifier is learned from the stochastic one (Lines 1 to 9 of Algorithm 1), the lack of tightness and degraded DP performance observed on MEPS
(the highest-dimensional dataset) are likely due to the increased difficulty of applying the heuristics (Line 10) for this
setting. Additionally, when comparing O1 and our stochastic classifier, our bounds are either tighter (for ADULT,
GERMAN, and MEPS-Gender) or similarly tight. This behavior is expected due to the nature of our bound based on a
tighter PAC-Bayesian guarantee (the one of Seeger, 2002). Lastly, since O2 is not a self-bounding algorithm, it does not
provide tighter bounds than ours and is often worse than O1.

*On the learned trade-off risk/DP.* Due to their similar nature, O1 and our stochastic classifier show very similar trade-offs. In contrast, our stochastic and deterministic classifiers may exhibit significantly different behaviors. In particular, for ADULT-gender, COMPAS, and MEPS-race, the learned trade-off for the deterministic classifier favors lower risk at the cost of a higher DP (probably a consequence of enforcing determinism). Note that O2 (stochastic and non-self-bounding) also behaves differently, yielding the lowest DP values on all datasets (except GERMAN-age); However, these improvements in DP are not significant and can come at the cost of a substantially higher risk (with the exception of ADULT-gender, COMPAS, and MEPS-race). Interestingly, the deterministic classifier displays an opposite trend to O2. This may come from the fact that minimizing a bound captures additional information about the trade-off.

*Take-home message.* Our results highlight that learning with self-certified fairness is not only theoretically sound but also practically effective: Tight PAC-Bayes bounds can be optimized, yielding reliable risk/fairness trade-offs in practice.

# 7 Conclusion

In this paper, we introduce PAC-Bayesian generalization bounds on a general fairness risk and its extension to various fairness metrics for group fairness. We instantiate such bounds on stochastic and deterministic classifiers defined as majority votes and demonstrate the effectiveness of minimizing bounds to obtain fair majority votes with tight theoretical guarantees. As future work, we plan to extend our framework to the multi-class setting and to non-binary sensitive attributes.

Acknowledgements.

This work was supported in part by the French Project FAMOUS ANR-23-CE23-0019. Pascal Germain is supported by the NSERC Discovery grant RGPIN-2020-07223. Benjamin Leblanc is supported by a Mitacs Acceleration grant, in partnership with Intact Financial Corporation. Paul Viallard is partially funded through Inria with the associate team PACTOL and the exploratory action HYPE.

References

Agarwal, A., Beygelzimer, A., Dudik, M., Langford, J., and Wallach, H. A reductions approach to fair classification. In *International Conference on Machine Learning*, 2018.

AHRQ. Medical expenditure panel survey data: 2015 full year consolidated data file, 2015.

AHRQ. Medical expenditure panel survey data: 2016 full year consolidated data file, 2016.

Angwin, J., Larson, J., Mattu, S., and Kirchner, L. Machine bias: There's software used across the country to predict future criminals. and its biased against blacks. ProPublica, 2016.

Bellamy, R. K. E., Dey, K., Hind, M., Hoffman, S. C., Houde, S., Kannan, K., Lohia, P., Martino, J., Mehta, S., Mojsilovic, A., Nagar, S., Ramamurthy, K. N., Richards, J., Saha, D., Sattigeri, P., Singh, M., Varshney, K. R., and Zhang, Y. AI Fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias. *IBM Journal of Research and Development*, 2019.

Blanchard, G. and Fleuret, F. Occam's hammer. In *Conference on Learning Theory*, 2007.

Canonne, C. L. A short note on an inequality between kl and tv. *arXiv preprint arXiv:2202.07198*, 2022.

Caton, S. and Haas, C. Fairness in machine learning: A survey. *ACM Computing Survey*, 2024.

Catoni, O. PAC-Bayesian supervised classification: The thermodynamics of statistical learning. *IMS Lecture Notes Monograph Series*, 2007.

Czarnowska, P., Vyas, Y., and Shah, K. Quantifying social biases in nlp: A generalization and empirical comparison of extrinsic fairness metrics. *Transactions of the Association for Computational Linguistics*, 2021.

Denis, C., Elie, R., Hebiri, M., and Hu, F. Fairness guarantees in multi-class classification with demographic parity. *Journal of Machine Learning Research*, 2024.

Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In *Innovations in Theoretical Computer Science Conference*, 2012.
Dziugaite, G. K. and Roy, D. M. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In *Conference on Uncertainty in Artificial Intelligence*, 2017.

Freund, Y. Self bounding learning algorithms. In *Conference on Computational Learning Theory*, 1998.

Germain, P., Lacasse, A., Laviolette, F., Marchand, M., and Roy, J. Risk bounds for the majority vote: From a PAC-Bayesian analysis to a learning algorithm. *Journal of Machine Learning Research*, 2015.

Han, X., Chi, J., Chen, Y., Wang, Q., Zhao, H., Zou, N., and Hu, X. FFB: A fair fairness benchmark for in-processing group fairness methods. In *International Conference on Learning Representations*, 2024.

Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. *Advances in Neural Information Processing Systems*, 2016.

Hofmann, H. Statlog (German Credit Data). UCI Machine Learning Repository, 1994.

Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In *International Conference on Learning Representations*, 2015.

Kohavi, R. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In *International Conference on Knowledge Discovery and Data Mining*, 1996.

Laakom, F., Chen, H., Schmidhuber, J., and Bu, Y. Fairness overfitting in machine learning: An information-theoretic perspective. In *International Conference on Machine Learning*, 2025.

Lacasse, A., Laviolette, F., Marchand, M., Germain, P., and Usunier, N. PAC-Bayes bounds for the risk of the majority vote and the variance of the Gibbs classifier. In *Advances in Neural Information Processing Systems*, 2006.

Langford, J. and Shawe-Taylor, J. PAC-Bayes & margins. *Advances in Neural Information Processing Systems*, 2002.

Leblanc, B. and Germain, P. A framework for bounding deterministic risk with PAC-Bayes: Applications to majority votes. *arXiv preprint arXiv:2510.25569*, 2025.

Lever, G., Laviolette, F., and Shawe-Taylor, J. Tighter PAC-Bayes bounds through distribution-dependent priors. *Theoretical Computer Science*, 2013.

Masegosa, A., Lorenzen, S. S., Igel, C., and Seldin, Y. Second order PAC-Bayesian bounds for the weighted majority vote. In *Advances in Neural Information Processing Systems*, 2020.

Maurer, A. A note on the PAC bayesian theorem. *arXiv preprint arXiv:cs.LG/0411099*, 2004.

McAllester, D. A. Some PAC-Bayesian theorems. *Machine Learning*, 1998.

McAllester, D. A. PAC-Bayesian stochastic model selection. *Machine Learning*, 2003.

Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., and Galstyan, A. A survey on bias and fairness in machine learning. *ACM computing surveys*, 2021.

Menon, A. K. and Williamson, R. C. The cost of fairness in binary classification. In *Conference on Fairness, Accountability and Transparency*, 2018.

Mertens, S. The easiest hard problem: Number partitioning. In *Computational Complexity and Statistical Physics*. Oxford University Press, 2005.

Oneto, L., Donini, M., and Pontil, M. PAC-Bayes and fairness: Risk and fairness bounds on distribution dependent fair priors. In *European Symposium on Artificial Neural Networks*, 2019.

Oneto, L., Donini, M., Pontil, M., and Shawe-Taylor, J. Randomized learning and generalization of fair and private classifiers: From PAC-Bayes to stability and differential privacy. *Neurocomputing*, 2020.

Rivasplata, O. PAC-Bayesian computation. PhD thesis, University College London, UK, 2022.

Rivasplata, O., Kuzborskij, I., Szepesvari, C., and Shawe-Taylor, J. PAC-Bayes analysis beyond the usual bounds. In *Advances in Neural Information Processing Systems*, 2020.

Roy, J., Laviolette, F., and Marchand, M. From PAC-Bayes bounds to quadratic programs for majority votes. In *International Conference on Machine Learning*, 2011.

Seeger, M. W. PAC-Bayesian generalisation error bounds for gaussian process classification. *Journal of Machine Learning Research*, 2002.

Shawe-Taylor, J. and Williamson, R. C. A PAC analysis of a bayesian estimator. In *Conference on Computational Learning Theory*, 1997.

Ustun, B., Liu, Y., and Parkes, D. Fairness without harm: Decoupled classifiers with preference guarantees. In *International Conference on Machine Learning*, 2019.
Valiant, L. A theory of the learnable. *Communications of the ACM*, 1984.

Vapnik, V. *The nature of statistical learning theory*. Springer science & business media, 1999.

Viallard, P. *PAC-Bayesian Bounds and Beyond: Self-Bounding Algorithms and New Perspectives on Generalization in Machine Learning*. PhD thesis, University Jean Monnet, France, 2023.

Viallard, P., Emonet, R., Habrard, A., Morvant, E., and Zantedeschi, V. Leveraging PAC-Bayes theory and gibbs distributions for generalization bounds with complexity measures. In *International Conference on Artificial Intelligence and Statistics*, 2024a.

Viallard, P., Germain, P., Habrard, A., and Morvant, E. A general framework for the practical disintegration of PAC-Bayesian bounds. *Machine Learning*, 2024b.

Woodworth, B., Gunasekar, S., Ohannessian, M. I., and Srebro, N. Learning non-discriminatory predictors. In *Conference on Learning Theory*, 2017.

Wu, Y. Lecture notes on information-theoretic methods for high-dimensional statistics. *Lecture Notes for ECE598YW (UIUC)*, 2017.

Zantedeschi, V., Viallard, P., Morvant, E., Emonet, R., Habrard, A., Germain, P., and Guedj, B. Learning stochastic majority votes by minimizing a PAC-Bayes generalization bound. *Advances in Neural Information Processing Systems*, 2021.

## A Detailed discussion of the results of Oneto et al. (2020)

Oneto et al. (2020) proposed a PAC-Bayesian fairness bound on the measure of Equal Opportunity Hardt et al. (2016) (we build upon the formalization of the Equal Opportunity risk from Section 3.1). Let $D_{X|+1,g}$ the marginal distribution of $X$ restricted to the class $y = +1$ and sensitive group $g \in \mathcal{G}$. The corresponding true Gibbs risk for any group $g \in \mathcal{G}$ is,

$$R_{D_{X|+1,g}}(G_{\rho}) = \mathbb{E}_{h \sim \rho x \sim D_{X|+1,g}} \ell(h(x), +1).$$

Similarly, for the empirical version, take the sample $S_{X|+1,g} = \{(x_i, g_i) \in S : g_i = g, y_i = +1\}$ and compute the risk,

$$\hat{R}_{S_{X|+1,g}}(G_{\rho}) = \frac{1}{m_{+1,g}} \sum_{i=1}^{m_{+1,g}} \mathbb{E}_{h \sim \rho} h(x_i)$$

with $m_{+1,g} = |S_{X|+1,g}|$. Therefore, in the binary fairness setting, the Equal Opportunity true risk is,

$$EOP_D(G_{\rho}) = \left| R_{D_{X|+1,a}}(G_{\rho}) - R_{D_{X|+1,b}}(G_{\rho}) \right|$$

and the empirical Equal Opportunity risk is,

$$\widehat{EOP}_S(G_{\rho}) = \left| \hat{R}_{S_{X|+1,a}}(G_{\rho}) - \hat{R}_{S_{X|+1,b}}(G_{\rho}) \right|$$

The upper bound on the EOP risk (Theorem A.1) is obtained by instantiating the classical PAC-Bayesian bound of McAllester (2003) (Theorem A.2) to the group-conditional Gibbs risks involved in the Equal Opportunity criterion.

**Theorem A.1 (Oneto et al., 2020).** For any distribution $D$, hypothesis set $H$, prior distribution $P$ over $H$, $\delta \in (0, 1]$, we have with probability at least $1 - \delta$ over the random choice $S \sim D^m$ that for every $\rho$ over $H$:

$$\left| \widehat{EOP}_S(\rho) - EOP_D(G_{\rho}) \right| \le \sqrt{\frac{1}{2m_{+1,a}} \left( \mathrm{KL}(G_{\rho} \| \pi) + \ln \left( \frac{4\sqrt{m_{+1,a}}}{\delta} \right) \right)} + \sqrt{\frac{1}{2m_{+1,b}} \left( \mathrm{KL}(\rho \| \pi) + \ln \left( \frac{4\sqrt{m_{+1,b}}}{\delta} \right) \right)}.$$

*Proof.* Note that from the triangle inequality, we have

$$\begin{aligned} \left| \widehat{EOP}_S(G_{\rho}) - EOP_D(G_{\rho}) \right| &= \left| \hat{R}_{S_{X|+1,a}}(G_{\rho}) - \hat{R}_{S_{X|+1,b}}(G_{\rho}) \right| - \left| R_{D_{X|+1,a}}(G_{\rho}) - R_{D_{X|+1,b}}(G_{\rho}) \right| \\ &\le \left| R_{D_{X|+1,a}}(G_{\rho}) - \hat{R}_{S_{X|+1,a}}(G_{\rho}) \right| + \left| R_{D_{X|+1,b}}(G_{\rho}) - \hat{R}_{S_{X|+1,b}}(G_{\rho}) \right|. \end{aligned}$$

Then apply the classical PAC-Bayes bound (Theorem A.2) separately to each subgroup, with probability at least $1 - \frac{\delta}{2}$. A union bound over the two subgroups gives the desired result. $\square$
**Theorem A.2 (McAllester, 2003).** For any distribution $\mathcal{D}$, hypothesis set $\mathcal{H}$, prior distribution $\pi$ over $\mathcal{H}$, $\delta \in (0, 1]$, with probability at least $1 - \delta$ over the random choice $S \sim \mathcal{D}^m$, we have for every $\rho$ over $\mathcal{H}$,

$$ \left| R_{\mathcal{D}}(G_{\rho}) - \hat{R}_{S}(G_{\rho}) \right| \le \sqrt{\frac{1}{2m} \left[ \text{KL}(\rho \| \pi) + \ln \frac{2\sqrt{m}}{\delta} \right]} $$

To define the posterior $\rho$ and the prior $\pi$, Oneto et al. (2020) propose to follow a standard PAC-Bayesian approach (e.g., Catoni, 2007; Lever et al., 2013) that intends to favor the classifier with good accuracy and EOP. Let $\lambda \in [0, +\infty[$ which denotes the trade-off parameter between accuracy and fairness. One can define the posterior distribution under this approach, denoted by $\rho_{\mathcal{D}}$, and defined as

$$ \rho_{\mathcal{D}}(h) \propto \exp \left( -\gamma \left[ \hat{R}_{S}(h) + \lambda \widehat{\text{EOP}}_{S}(h) \right] \right), \quad (15) $$

Similarly, the prior distribution is defined as

$$ \pi(h) \propto \exp \left( -\gamma \left[ R_{\mathcal{D}}(h) + \lambda \text{EOP}_{\mathcal{D}}(h) \right] \right). \quad (16) $$

However, the prior distribution defined in Equation (16) cannot be computed in practice, as it explicitly depends on the true risk $R_{\mathcal{D}}(h)$ and the true Equal Opportunity risk $\text{EOP}_{\mathcal{D}}(h)$, which are both unknown. Using the definition of the prior $\pi$ and posterior $\rho_{\mathcal{D}}$ from Equations (16) and (15), Oneto et al. (2020) derive the following bound on $\text{KL}(\rho_{\mathcal{D}} \| \pi)$.

**Theorem A.3 (Oneto et al., 2020).** Given the prior $\pi$ and posterior $\rho_{\mathcal{D}}$ defined in Equations (16) and (15), we have

$$ \mathbb{P}_{S \sim \mathcal{D}^m} [\text{KL}(\rho_{\mathcal{D}} \| \pi) \ge \text{KL}_2(\delta, m, m_{+1,a}, m_{+1,b})] \le 6\delta $$

where

$$ \text{KL}_2(\delta, m, m_{+1,a}, m_{+1,b}) = \varepsilon_1^2 + 2\varepsilon_1\sqrt{\varepsilon_2} + \varepsilon_2, $$

$$ \varepsilon_1 = \gamma \left( \sqrt{\frac{1}{2m}} + \lambda \left( \sqrt{\frac{1}{2m_{+1,a}}} + \sqrt{\frac{1}{2m_{+1,b}}} \right) \right), $$

$$ \varepsilon_1 = 2\gamma \left( \sqrt{\frac{1}{2m}} \ln \left( \frac{2\sqrt{m}}{\delta} \right) + \lambda \left( \sqrt{\frac{1}{2m_{+1,a}}} \ln \left( \frac{2\sqrt{m_{+1,a}}}{\delta} \right) + \sqrt{\frac{1}{2m_{+1,b}}} \ln \left( \frac{2\sqrt{m_{+1,b}}}{\delta} \right) \right) \right). $$

Then given Theorem A.3, Oneto et al. (2020) obtain the following bounds on the risk and the EOP risk by plugging Theorem A.3 into Theorem A.1.

**Theorem A.4 (Oneto et al., 2020).** Given the prior $\pi$ and posterior $\rho_{\mathcal{D}}$ defined in Equations (16) and (15), the risk and the fairness of the stochastic classifier can be bounded in the following way:

$$ \mathbb{P}_{S \sim \mathcal{D}^m} \left[ \left| R_{\mathcal{D}}(G_{\rho_{\mathcal{D}}}) - \hat{R}_{S}(G_{\rho_{\mathcal{D}}}) \right| \le \sqrt{\frac{1}{2m} \left[ \text{KL}_2(\delta, m, m_{+1,a}, m_{+1,b}) + \ln \frac{2\sqrt{m}}{\delta} \right]} \right] \le 7\delta, $$

$$ \text{and} \quad \mathbb{P}_{S \sim \mathcal{D}^m} \left[ \left| \widehat{\text{EOP}}_S(\rho_{\mathcal{D}}) - \text{EOP}_{\mathcal{D}}(\rho_{\mathcal{D}}) \right| \le \sqrt{\frac{1}{2m_{+1,a}} \left( \text{KL}_2(\delta, m, m_{+1,a}, m_{+1,b}) + \ln\left(\frac{2\sqrt{m_{+1,a}}}{\delta}\right) \right)} \right. \\ \left. \qquad + \sqrt{\frac{1}{2m_{+1,b}} \left( \text{KL}_2(\delta, m, m_{+1,a}, m_{+1,b}) + \ln\left(\frac{2\sqrt{m_{+1,b}}}{\delta}\right) \right)} \right] \le 8\delta. $$

Even though the prior $\pi$ is defined using $R_{\mathcal{D}}(h)$ and $\text{EOP}_{\mathcal{D}}(h)$, the result from Theorem A.4 can be computed thanks to the fact that the $\text{KL}_2(\delta, m, m_{+1,a}, m_{+1,b})$ w defined in Theorem A.3 does not not require to access $\pi$. The posterior $\rho_{\mathcal{D}}$ defined Equation (15) gives the classifier $G_{\rho_{\mathcal{D}}}$ of the method denote O2 in Section 6, the reported bounds are given by Theorem A.4.

# B Proofs of the main results

## B.1 Proof of Proposition 4.3

**Proposition 4.3 (Risk decomposition, Leblanc & Germain, 2025).** Assume that $1_{\mathcal{D}}^{\rho}(h) - \delta_{\mathcal{D}}^{\rho}(h) \ne 0$. Then, for any $h \in \mathcal{H}$ and distribution $\rho$ on $\mathcal{H}$, the true risk of $h$ satisfies

$$ R_{\mathcal{D}}(h) = \frac{R_{\mathcal{D}}(G_{\rho}) - \delta_{\mathcal{D}}^{\rho}(h)}{1_{\mathcal{D}}^{\rho}(h) - \delta_{\mathcal{D}}^{\rho}(h)}, \quad (8) $$
$$ \text{with } \mathcal{O}_D^\rho(h) := \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \mathbb{E}_{h' \sim \rho} \ell(h'(x), y) \mid \ell(h(x), y) = 0 \right], $$

$$ \text{and } \mathbf{1}_D^\rho(h) := \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \mathbb{E}_{h' \sim \rho} \ell(h'(x), y) \mid \ell(h(x), y) = 1 \right]. $$

*Proof.* For any distribution $\mathcal{D}$, distribution $\rho$ over $\mathcal{H}$ and classifier $h \in \mathcal{H}$ such that $\mathbf{1}_D^\rho(h) \neq \mathcal{O}_D^\rho(h)$, we have:

$$
\begin{align*}
R_{\mathcal{D}}(G_{\rho}) &= \mathbb{E}_{h \sim \rho} \mathbb{E}_{(x,y) \sim \mathcal{D}} \ell(h(x), y), \\
&= \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 1) \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \mathbb{E}_{h' \sim \rho} \ell(h'(x), y) \mid \ell(h(x), y) = 1 \right] \\
&\quad + \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 0) \mathbb{E}_{(x,y) \sim \mathcal{P}} \left[ \mathbb{E}_{h' \sim \rho} \ell(h'(x), y) \mid \ell(h(x), y) = 0 \right], \\
&= \mathbf{1}_{\mathcal{D}}^{\rho}(h) \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 1) + \mathcal{O}_{\mathcal{D}}^{\rho}(h) \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 0), \\
&= \mathbf{1}_{\mathcal{D}}^{\rho}(h) \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 1) + \mathcal{O}_{\mathcal{D}}^{\rho}(h) \left( 1 - \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 1) \right), \\
&= (\mathbf{1}_{\mathcal{D}}^{\rho}(h) - \mathcal{O}_{\mathcal{D}}^{\rho}(h)) \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 1) + \mathcal{O}_{\mathcal{D}}^{\rho}(h), \\
&= (\mathbf{1}_{\mathcal{D}}^{\rho}(h) - \mathcal{O}_{\mathcal{D}}^{\rho}(h)) \mathbb{E}_{(x,y) \sim \mathcal{D}} + \mathcal{O}_{\mathcal{D}}^{\rho}(h), \\
&= (\mathbf{1}_{\mathcal{D}}^{\rho}(h) - \mathcal{O}_{\mathcal{D}}^{\rho}(h)) R_{\mathcal{D}}(h) + \mathcal{O}_{\mathcal{D}}^{\rho}(h).
\end{align*}
$$

The result is then obtained by rearranging the terms and using the assumption: $\mathbf{1}_D^\rho(h) \neq \mathcal{O}_D^\rho(h)$. $\square$

<figure><img src="image_3.png" /></figure>

## B.2 Proof of Lemma 4.4

**Lemma 4.4 (Bounds on $R_D(h)$).** For any distribution $\mathcal{D}$, any hypothesis set $\mathcal{H}$, any prior $\pi$ on $\mathcal{H}$, let $\rho$ be a distribution on $\mathcal{H}$, and $h \in \mathcal{H}$, and $\delta \in (0, 1]$.

**Upper bound (Leblanc & Germain, 2025):** With probability at least $1-\delta$ on $S \sim \mathcal{D}^m$, if

$$ R_{\mathcal{D}}(G_{\rho}) \le R_S^{\uparrow}(\rho, \pi, \delta, G_{\rho}), \quad \mathcal{O}_{\mathcal{D}}^{\rho}(h) \ge \mathcal{O}_{\mathcal{D}}^{\downarrow}(h, \rho), \quad \mathbf{1}_{\mathcal{D}}^{\rho}(h) \ge \mathbf{1}_{\mathcal{D}}^{\downarrow}(h, \rho), \\ \text{with } \mathbf{1}_{\mathcal{D}}^{\downarrow}(h, \rho) > \mathcal{O}_{\mathcal{D}}^{\downarrow}(h, \rho), \text{ then we have} $$

$$ R_{\mathcal{D}}(h) \le \frac{R_S^{\uparrow}(\rho, \pi, \delta, G_{\rho}) - \mathcal{O}_{\mathcal{D}}^{\downarrow}(h, \rho)}{\mathbf{1}_{\mathcal{D}}^{\downarrow}(h, \rho) - \mathcal{O}_{\mathcal{D}}^{\downarrow}(h, \rho)} := \mathfrak{R}_S^{\uparrow}(\rho, \pi, \delta, h). \quad (9) $$

**Lower bound:** With probability at least $1-\delta$ on $S \sim \mathcal{D}^m$, if

$$ R_{\mathcal{D}}(G_{\rho}) \ge R_S^{\downarrow}(\rho, \pi, \delta, G_{\rho}), \quad \mathcal{O}_{\mathcal{D}}^{\rho}(h) \le \mathcal{O}_{\mathcal{D}}^{\uparrow}(h, \rho), \quad \mathbf{1}_{\mathcal{D}}^{\rho}(h) \le \mathbf{1}_{\mathcal{D}}^{\uparrow}(h, \rho), \\ \text{with } \mathbf{1}_{\mathcal{D}}^{\uparrow}(h, \rho) > \mathcal{O}_{\mathcal{D}}^{\uparrow}(h, \rho), \text{ then we have} $$

$$ R_{\mathcal{D}}(h) \ge \frac{R_S^{\downarrow}(\rho, \pi, \delta, G_{\rho}) - \mathcal{O}_{\mathcal{D}}^{\uparrow}(h, \rho)}{\mathbf{1}_{\mathcal{D}}^{\uparrow}(h, \rho) - \mathcal{O}_{\mathcal{D}}^{\uparrow}(h, \rho)} := \mathfrak{R}_S^{\downarrow}(\rho, \pi, \delta, h). \quad (10) $$

*Proof.* We consider any distribution $\mathcal{D}$, distribution $\rho$ over $\mathcal{H}$ and classifier $h \in \mathcal{H}$ such that $\mathbf{1}_D^\rho(h) \neq \mathcal{O}_D^\rho(h)$. We apply the same steps as done in the proof of Proposition 4.3 to have

$$ R_{\mathcal{D}}(G_{\rho}) = \mathbf{1}_{\mathcal{D}}^{\rho}(h) \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 1) + \mathcal{O}_{\mathcal{D}}^{\rho}(h) \left( 1 - \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 1) \right). $$

**Upper bound.** We use the lower bounds of both $\mathcal{O}_D^\rho(h)$ and $\mathbf{1}_D^\rho(h)$, i.e., $\mathcal{O}_D^\rho(h) \ge \mathcal{O}_D^{\downarrow}(h, \rho)$ and $\mathbf{1}_D^\rho(h) \ge \mathbf{1}_D^{\downarrow}(h, \rho)$, to write

$$ R_{\mathcal{D}}(G_{\rho}) = \mathbf{1}_{\mathcal{D}}^{\rho}(h) \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 1) + \mathcal{O}_{\mathcal{D}}^{\rho}(h) \left( 1 - \mathbb{P}_{(x,y) \sim \mathcal{D}} (\ell(h(x), y) = 1) \right) $$
$$
\begin{align*}
&\geq \mathbf{1}_D^{\perp}(h, \rho) \mathbb{P}_{(x,y)\sim\mathcal{D}}(\ell(h(x), y) = 1) + \mathbf{o}_D^{\perp}(h, \rho) \left(1 - \mathbb{P}_{(x,y)\sim\mathcal{D}}(\ell(h(x), y) = 1)\right) \\
&\geq (\mathbf{1}_D^{\perp}(h, \rho) - \mathbf{o}_D^{\perp}(h, \rho)) \mathbb{P}_{(x,y)\sim\mathcal{D}}(\ell(h(x), y) = 1) + \mathbf{o}_D^{\perp}(h, \rho) \\
&\geq (\mathbf{1}_D^{\perp}(h, \rho) - \mathbf{o}_D^{\perp}(h, \rho)) R_D(h) + \mathbf{o}_D^{\perp}(h, \rho).
\end{align*}
$$

By rearranging the terms, we have, with probability at least 1−δ on S~D^m

$$
R_D(h) \le \frac{R_D(G_\rho) - \mathbf{o}_D^\perp(h, \rho)}{\mathbf{1}_D^\perp(h, \rho) - \mathbf{o}_D^\perp(h, \rho)} \le \frac{R_S^\perp(\rho, \pi, \delta, G_\rho) - \mathbf{o}_D^\perp(h, \rho)}{\mathbf{1}_D^\perp(h, \rho) - \mathbf{o}_D^\perp(h, \rho)},
$$

where the last inequality comes from the lower bound on the Gibbs' risk $R_D(G_\rho) \le R_S^\perp(\rho, \pi, \delta, G_\rho)$ that holds with probability $1-\delta$ on $S \sim \mathcal{D}^m$ by assumption.

**Lower bound.** We use the upper bounds of both $\mathbf{o}_D^\rho(h)$ and $\mathbf{1}_D^\rho(h)$, i.e. $\mathbf{o}_D^\rho(h) \le \mathbf{o}_D^\perp(h, \rho)$ and $\mathbf{1}_D^\rho(h) \le \mathbf{1}_D^\perp(h, \rho)$, to write

$$
\begin{align*}
R_D(G_\rho) &= \mathbf{1}_D^\rho(h) \mathbb{P}_{(x,y)\sim\mathcal{D}}(\ell(h(x), y) = 1) + \mathbf{o}_D^\rho(h) \left(1 - \mathbb{P}_{(x,y)\sim\mathcal{D}}(\ell(h(x), y) = 1)\right) \\
&\le \mathbf{1}_D^\uparrow(h, \rho) \mathbb{P}_{(x,y)\sim\mathcal{D}}(\ell(h(x), y) = 1) + \mathbf{o}_D^\uparrow(h, \rho) \left(1 - \mathbb{P}_{(x,y)\sim\mathcal{D}}(\ell(h(x), y) = 1)\right) \\
&\le (\mathbf{1}_D^\uparrow(h, \rho) - \mathbf{o}_D^\uparrow(h, \rho)) \mathbb{P}_{(x,y)\sim\mathcal{D}}(\ell(h(x), y) = 1) + \mathbf{o}_D^\uparrow(h, \rho) \\
R_D(G_\rho) &\le (\mathbf{1}_D^\uparrow(h, \rho) - \mathbf{o}_D^\uparrow(h, \rho)) R_D(h) + \mathbf{o}_D^\uparrow(h, \rho).
\end{align*}
$$

By rearranging the terms, we have, with probability at least 1−δ on S~D^m, we have

$$
R_D(h) \ge \frac{R_D(G_\rho) - \mathbf{o}_D^\uparrow(h, \rho)}{\mathbf{1}_D^\uparrow(h, \rho) - \mathbf{o}_D^\uparrow(h, \rho)} \ge \frac{R_S^\perp(\rho, \pi, \delta, G_\rho) - \mathbf{o}_D^\uparrow(h, \rho)}{\mathbf{1}_D^\uparrow(h, \rho) - \mathbf{o}_D^\uparrow(h, \rho)},
$$

where the last inequality comes from the lower bound on the Gibbs' risk $R_D(G_\rho) \ge R_S^\perp(\rho, \pi, \delta, G_\rho)$ that holds with probability $1-\delta$ on $S \sim \mathcal{D}^m$ by assumption. $\square$

B.3 Proof of Proposition 4.6

**Proposition 4.6.** Let $\alpha_1$ and $\alpha_2$ be the result of the partition problem applied to $\alpha$. Let $\tilde{\alpha} = \max(\sum_{\alpha \in \alpha_1} \alpha, \sum_{\alpha \in \alpha_2} \alpha)$, and $\bar{\alpha} = |\sum_{\alpha \in \alpha_1} \alpha - \sum_{\alpha \in \alpha_2} \alpha|$. For any distribution $\mathcal{D}$, with $\ell(h_\alpha(x), y) = \mathbf{I}[\operatorname{sign}(h_\alpha(x)) \neq y]$, we have

1. If $\rho = \mathcal{C}(\alpha)$, then

$$
0 \le \mathbf{o}_D^\rho(h_\alpha) \le 1 - \tilde{\alpha}, \text{ and } \tilde{\alpha} \le \mathbf{1}_D^\rho(h_\alpha) \le 1;
$$

2. If $\rho = \mathrm{Dir}(\alpha)$, with $I_{0.5}(\cdot)$ the regularized incomplete beta function evaluated at 0.5, then

$$
\begin{align*}
0 \le \mathbf{o}_D^\rho(h_\alpha) &\le I_{0.5}(\tilde{\alpha}, \|\alpha\|_1 - \tilde{\alpha}), \\
\text{and } I_{0.5}(\|\alpha\|_1 - \tilde{\alpha}, \tilde{\alpha}) &\le \mathbf{1}_D^\rho(h_\alpha) \le 1;
\end{align*}
$$

3. If $\rho = \mathcal{N}(\alpha, \mathbf{I}_{n \times n})$, with $\Phi(k) := \frac{1}{2}[1 - \mathrm{Erf}(\frac{k}{\sqrt{2}})]$ and $\mathrm{Erf}(k) := \frac{2}{\sqrt{\pi}} \int_{0}^{k} e^{-t^2} dt$, then

$$
\begin{align*}
\Phi\left(\frac{\|\boldsymbol{\alpha}\|_1}{\sqrt{n}}\right) &\le \mathbf{o}_D^\rho(h_\alpha) \le \Phi\left(\frac{\bar{\boldsymbol{\alpha}}}{\sqrt{n}}\right), \\
\text{and } 1 - \Phi\left(\frac{\bar{\boldsymbol{\alpha}}}{\sqrt{n}}\right) &\le \mathbf{1}_D^\rho(h_\alpha) \le 1 - \Phi\left(\frac{\|\boldsymbol{\alpha}\|_1}{\sqrt{n}}\right).
\end{align*}
$$
**Proof.** We briefly recall that $\mathcal{O}_D^\rho(h)$ and $\mathbf{1}_D^\rho(h)$ are respectively defined by

$$ \mathcal{O}_D^\rho(h) := \mathbb{E}_{(x,y)\sim D} \left[ \mathbb{E}_{h'\sim\rho} \left. \ell(h'(x), y) \right| \ell(h(x), y) = 0 \right] \quad \text{and} \quad \mathbf{1}_D^\rho(h) := \mathbb{E}_{(x,y)\sim D} \left[ \mathbb{E}_{h'\sim\rho} \left. \ell(h'(x), y) \right| \ell(h(x), y) = 1 \right]. $$

Let us denote $\alpha^\pm = \sum_{i=1}^n \alpha_i \mathbf{I}\{f_i(x) \neq y\}$, the sum of the weights of the classifiers that misclassify $x$. Thus, for any $(x, y) \in \mathcal{X} \times \mathcal{Y}$, there exists $\mathbf{j} \in \{0, 1\}^n$ such that $\alpha^\pm = \mathbf{j} \cdot \alpha$. Indeed, $\mathbf{j}$ can be seen as a vector indexing the base classifiers that misclassify an instance $x$. This representation will be used to draw the link between $\mathcal{O}_D^\rho(h)$ and $\mathbf{1}_D^\rho(h)$ and the partition problem algorithm. We also recall that $\alpha_1$ and $\alpha_2$ are the result of the partition problem applied to $\alpha$, whereas $\tilde{\alpha} = \max(\sum_{\alpha \in \alpha_1} \alpha, \sum_{\alpha \in \alpha_2} \alpha)$, and $\bar{\alpha} = |\sum_{\alpha \in \alpha_1} \alpha - \sum_{\alpha \in \alpha_2} \alpha|$. Now, we focus on the lower and upper bounds of $\mathcal{O}_D^\rho(h)$ and $\mathbf{1}_D^\rho(h)$ for the three forms of $\rho$.

**Categorical distribution** $\rho = C(\alpha)$. We first prove the upper bound of $\mathcal{O}_D^\rho(h_\alpha)$ when $\rho = C(\alpha)$. Indeed, we have

$$
\begin{align*}
\mathcal{O}_D^\rho(h_\alpha) &= \mathbb{E}_{(x,y)\sim D} \left[ \mathbb{E}_{h'\sim C(\alpha)} \left. \ell(h'(x), y) \right| \ell(h_\alpha(x), y) = 0 \right] \\
&= \mathbb{E}_{(x,y)\sim D} \left[ \mathbb{E}_{h'\sim C(\alpha)} \mathbf{I}[\operatorname{sign}(h'(x)) \neq y] \left. \mathbf{I}[\operatorname{sign}(h_\alpha(x)) \neq y] \right| \right] \\
&= \mathbb{E}_{(x,y)\sim D} [\alpha^\pm | \alpha^\pm < 0.5] \tag*{\text{\textit{Leblanc & Germain (2025)}}} \\
&\le \max_{(x,y)\in\mathcal{X}\times\mathcal{Y}} [\alpha^\pm | \alpha^\pm < 0.5] \\
&\le \max_{\mathbf{i}\in\{0,1\}^n} [\mathbf{i} \cdot \alpha | \mathbf{i} \cdot \alpha < 0.5] \\
&= \min \left( \sum_{\alpha \in \alpha_1} \alpha, \sum_{\alpha \in \alpha_2} \alpha \right) \tag*{\text{\textit{Mertens (2005)}}} \\
&= 1 - \max \left( \sum_{\alpha \in \alpha_1} \alpha, \sum_{\alpha \in \alpha_2} \alpha \right) \\
&= 1 - \tilde{\alpha}.
\end{align*}
$$

Now, we focus on the lower bound of $\mathbf{1}_D^\rho(h_\alpha)$. We have

$$
\begin{align*}
\mathbf{1}_D^\rho(h_\alpha) &= \mathbb{E}_{(x,y)\sim D} [\alpha^\pm | \alpha^\pm \ge 0.5] \tag*{\text{\textit{Leblanc & Germain (2025)}}} \\
&\ge \min_{(x,y)\in\mathcal{X}\times\mathcal{Y}} [\alpha^\pm | \alpha^\pm \ge 0.5] \\
&\ge \min_{\mathbf{i}\in\{0,1\}^n} [\mathbf{i} \cdot \alpha | \mathbf{i} \cdot \alpha \ge 0.5] \\
&= \max \left( \sum_{\alpha \in \alpha_1} \alpha, \sum_{\alpha \in \alpha_2} \alpha \right) \tag*{\text{\textit{Mertens (2005)}}} \\
&= \tilde{\alpha}.
\end{align*}
$$

**Dirichlet distribution** $\rho = \operatorname{Dir}(\alpha)$. First of all, for the sake of clarity, we also denote $I_1$ the set of indexes of classifiers that err and $I_2$ the set of classifier that predict correctly. Following Zantedeschi et al. (2021), using the aggregation property of the Dirichlet distribution, we can write $(\sum_{i \in I_1} w_i, \sum_{i \in I_2} w_i)$ is drawn from $\operatorname{Dir}(\sum_{i \in I_1} \alpha_i, \sum_{i \in I_2} \alpha_i)$ which is no more than the Beta distribution with the same parameters.

Moreover, let us consider the random variable $S_w = \sum_{i \in I_1} w_i$ which represent the sum of the weights for classifiers that made mistakes. So $S_w \sim \text{Beta}(\sum_{i \in I_1} \alpha_i, \sum_{i \in I_2} \alpha_i)$. Let us now compute the probability that the sum $S_w$ is greater than 0.5, i.e., most of the classifiers wrongly classify the instance $x$. We have

$$ \mathbb{P}[S_w \ge 0.5] = 1 - \mathbb{P}[S_w \le 0.5] = 1 - I_{0.5} \left( \sum_{i \in I_1} \alpha_i, \sum_{i \in I_2} \alpha_i \right) = I_{0.5} \left( \sum_{i \in I_2} \alpha_i, \sum_{i \in I_1} \alpha_i \right) = I_{0.5} \left( \|\alpha\|_i - \alpha^\pm, \alpha^\pm \right). $$

We are now ready to prove the following upper bound $\mathcal{O}_D^\rho(h_\alpha) \le I_{0.5}(\tilde{\alpha}, \|\alpha\|_1 - \tilde{\alpha})$. We have

$$ \mathcal{O}_D^\rho(h_\alpha) = \mathbb{E}_{(x,y)\sim D} \left[ I_{0.5} \left( \|\alpha\|_1 - \alpha^\pm, \alpha^\pm \right) \middle| \alpha^\pm < \frac{\|\alpha\|_1}{2} \right] \quad \text{\textit{see Leblanc & Germain (2025)}} $$
$$
\begin{aligned}
&\leq \max_{(x,y) \in \mathcal{X} \times \mathcal{Y}} \left[ I_{0.5} \left( \|\boldsymbol{\alpha}\|_1 - \boldsymbol{\alpha}^{\pm}, \boldsymbol{\alpha}^{\pm} \right) \middle| \boldsymbol{\alpha}^{\pm} < \frac{\|\boldsymbol{\alpha}\|_1}{2} \right] \\
&\leq \max_{\mathbf{i} \in \{0,1\}^n} \left[ I_{0.5} \left( \|\boldsymbol{\alpha}\|_1 - \mathbf{i} \cdot \boldsymbol{\alpha}, \mathbf{i} \cdot \boldsymbol{\alpha} \right) \middle| \mathbf{i} \cdot \boldsymbol{\alpha} < \frac{\|\boldsymbol{\alpha}\|_1}{2} \right].
\end{aligned}
$$

Since $I_{0.5}(\cdot, \cdot)$ is decreasing in its first argument, and increasing in its second one, we have

$$
\underset{\mathbf{i} \in \{0,1\}^n}{\operatorname{argmax}} \left[ I_{0.5} \left( \|\boldsymbol{\alpha}\|_1 - \mathbf{i} \cdot \boldsymbol{\alpha}, \mathbf{i} \cdot \boldsymbol{\alpha} \right) \middle| \mathbf{i} \cdot \boldsymbol{\alpha} < \frac{\|\boldsymbol{\alpha}\|_1}{2} \right] = \underset{\mathbf{i} \in \{0,1\}^n}{\operatorname{argmax}} \left[ \mathbf{i} \cdot \boldsymbol{\alpha} \middle| \mathbf{i} \cdot \boldsymbol{\alpha} < \frac{\|\boldsymbol{\alpha}\|_1}{2} \right].
$$

Also, the function $\mathbf{i} \mapsto I_{0.5}(\|\boldsymbol{\alpha}\|_1 - \mathbf{i} \cdot \boldsymbol{\alpha}, \mathbf{i} \cdot \boldsymbol{\alpha})$ is maximized when $\mathbf{i} \cdot \boldsymbol{\alpha}$ is maximized. Based on the development for the Categorical distribution, we have

$$
\max_{\mathbf{i} \in \{0,1\}^n} \left[ \mathbf{i} \cdot \boldsymbol{\alpha} \mid \mathbf{i} \cdot \boldsymbol{\alpha} < \frac{\|\boldsymbol{\alpha}\|_1}{2} \right] = \min \left( \sum_{\alpha \in \alpha_1} \alpha, \sum_{\alpha \in \alpha_2} \alpha \right) = \|\boldsymbol{\alpha}\|_1 - \tilde{\alpha}.
$$

Thus, we have

$$
\max_{\mathbf{i} \in \{0,1\}^n} \left[ I_{0.5} \left( \|\boldsymbol{\alpha}\|_1 - \mathbf{i} \cdot \boldsymbol{\alpha}, \mathbf{i} \cdot \boldsymbol{\alpha} \right) \middle| \mathbf{i} \cdot \boldsymbol{\alpha} < \frac{\|\boldsymbol{\alpha}\|_1}{2} \right] = I_{0.5} \left( \tilde{\boldsymbol{\alpha}}, \|\boldsymbol{\alpha}\|_1 - \tilde{\boldsymbol{\alpha}} \right).
$$

Let us focus on the lower bound on $\mathbf{1}_D^\rho(h_\alpha)$. We have

$$
\begin{aligned}
\mathbf{1}_D^\rho(h_\alpha) &= \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ I_{0.5} \left( \|\boldsymbol{\alpha}\|_1 - \boldsymbol{\alpha}^{\pm}, \boldsymbol{\alpha}^{\pm} \right) \middle| \boldsymbol{\alpha}^{\pm} > \frac{\|\boldsymbol{\alpha}\|_1}{2} \right] \quad \langle \text{see Leblanc \& Germain (2025)} \rangle \\
&\geq \min_{(x,y) \in \mathcal{X} \times \mathcal{Y}} \left[ I_{0.5} \left( \|\boldsymbol{\alpha}\|_1 - \boldsymbol{\alpha}^{\pm}, \boldsymbol{\alpha}^{\pm} \right) \middle| \boldsymbol{\alpha}^{\pm} > \frac{\|\boldsymbol{\alpha}\|_1}{2} \right] \\
&\geq \min_{\mathbf{i} \in \{0,1\}^n} \left[ I_{0.5} \left( \|\boldsymbol{\alpha}\|_1 - \mathbf{i} \cdot \boldsymbol{\alpha}, \mathbf{i} \cdot \boldsymbol{\alpha} \right) \middle| \mathbf{i} \cdot \boldsymbol{\alpha} > \frac{\|\boldsymbol{\alpha}\|_1}{2} \right].
\end{aligned}
$$

Using the same properties on $\mathbf{i} \cdot \boldsymbol{\alpha} \mapsto I_{0.5}(\|\boldsymbol{\alpha}\|_1 - \mathbf{i} \cdot \boldsymbol{\alpha}, \mathbf{i} \cdot \boldsymbol{\alpha})$, we write

$$
\min_{\mathbf{i} \in \{0,1\}^n} \left[ \mathbf{i} \cdot \boldsymbol{\alpha} \mid \mathbf{i} \cdot \boldsymbol{\alpha} < \frac{\|\boldsymbol{\alpha}\|_1}{2} \right] = \max \left( \sum_{\alpha \in \alpha_1} \alpha, \sum_{\alpha \in \alpha_2} \alpha \right) = \tilde{\alpha}.
$$

Thus, using the same assumptions on $I_{0.5}$, we have

$$
\mathbf{1}_D^\rho(h_\alpha) \geq I_{0.5} \left( \|\boldsymbol{\alpha}\|_1 - \tilde{\alpha}, \tilde{\alpha} \right).
$$

**Normal distribution** $\rho = \mathcal{N}(\boldsymbol{\alpha}, \mathbf{I}_{n \times n})$. First of all, using the Gaussian assumption, we have

$$
\mathbb{P}_{h' \sim \rho} [h'(x) \neq y] = \mathbb{P}_{(w_1, \dots, w_n) \sim \mathcal{N}(\boldsymbol{\alpha}, \mathbf{I}_{n \times n})} \left[ y \sum_{i=1}^{n} w_i f_i(x) < 0 \right].
$$

Let us denote $\mathbf{w} = (w_1, \dots, w_n)$ and $\mathbf{f} = (f_1(x), \dots, f_n(x))$, then we can write:

$$
\mathbb{P}_{(w_1, \dots, w_n) \sim \mathcal{N}(\boldsymbol{\alpha}, \mathbf{I}_{n \times n})} \left[ y \sum_{i=1}^{n} w_i f_i(x) < 0 \right] = \mathbb{P}_{(w_1, \dots, w_n) \sim \mathcal{N}(\boldsymbol{\alpha}, \mathbf{I}_{n \times n})} [y \mathbf{w} \cdot \mathbf{f} < 0],
$$

where $\mathbf{w} \cdot \mathbf{f}(x) \sim \mathcal{N}(\boldsymbol{\alpha} \cdot \mathbf{f}(x), \|\mathbf{f}(x)\|_2)$. Since both $f_i(x)$ and $y$ belong in $\{-1, +1\}$, we have $\|\mathbf{f}(x)\|_2 = \sqrt{n}$ and we can finally write

$$
\mathbb{P}_{h' \sim \rho} [h'(x) \neq y] = \mathbb{P}_{(w_1, \dots, w_n) \sim \mathcal{N}(\boldsymbol{\alpha}, \mathbf{I}_{n \times n})} [y\mathbf{w} \cdot \mathbf{f}(x) < 0] = \tilde{\Phi} \left(-y \frac{\boldsymbol{\alpha} \cdot \mathbf{f}(x)}{\sqrt{n}}\right) = \Phi \left(y \frac{\boldsymbol{\alpha} \cdot \mathbf{f}(x)}{\sqrt{n}}\right),
$$

where $\tilde{\Phi}$ is the continuous density function of a centered and reduced Gaussian distribution with the relation:

$$
\forall k \in \mathbb{R} \quad \tilde{\Phi}(-k) = \frac{1}{2} \left( 1 - \operatorname{Erf}(k/\sqrt{2}) \right) = \Phi(k).
$$
We are now able to prove the lower and upper bounds on $\mathcal{O}_D^\rho(h_\alpha)$ and $\mathcal{I}_D^\rho(h_\alpha)$. We first prove the upper bound of $\mathcal{O}_D^\rho(h_\alpha)$.

$$
\begin{align*}
\mathcal{O}_D^\rho(h_\alpha) &= \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \mathbb{E}_{h'\sim\rho} \ell(h'(x), y) \middle| \ell(h_\alpha(x), y) = 0 \right], \\
&= \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \Phi \left( y \frac{\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})}{\sqrt{n}} \right) \middle| y \boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x}) > 0 \right], \\
&= \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \Phi \left( \frac{|\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \middle| y \boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x}) > 0 \right] \quad \langle \text{see Leblanc \& Germain (2025)} \rangle \\
&\le \max_{\mathbf{x} \in \mathcal{X}} \Phi \left( \frac{|\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \\
&\le \Phi \left( \frac{\min_{\mathbf{x} \in \mathcal{X}} |\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \quad \langle \text{\Phi is strictly decreasing.} \rangle \\
&\le \Phi \left( \frac{\min_{\mathbf{i} \in \{-1,1\}^n} |\boldsymbol{\alpha} \cdot \mathbf{i}|}{\sqrt{n}} \right).
\end{align*}
$$

Finally, note that

$$ \min_{\mathbf{i} \in \{-1,1\}^n} |\boldsymbol{\alpha} \cdot \mathbf{i}| = \min_{\boldsymbol{\alpha}_1, \boldsymbol{\alpha}_2} \left\{ \left| \sum_{\alpha \in \alpha_1} \boldsymbol{\alpha} - \sum_{\alpha \in \alpha_2} \boldsymbol{\alpha} \right| : \{\boldsymbol{\alpha}_1, \boldsymbol{\alpha}_2\} \text{ is a partition of } \boldsymbol{\alpha} \right\}, $$

which corresponds to the objective of the partition problem to be minimized. Plugging that into the development yields the main result, we have

$$ \mathcal{O}_D^\rho(h_\alpha) \le \Phi\left(\frac{\bar{\alpha}}{\sqrt{n}}\right). $$

We now prove the lower bound of $\mathcal{O}_D^\rho(h_\alpha)$. We have

$$
\begin{align*}
\mathcal{O}_D^\rho(h_\alpha) &= \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \mathbb{E}_{h'\sim\rho} \ell(h'(x), y) \middle| \ell(h_\alpha(x), y) = 0 \right], \\
&= \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \Phi \left( y \frac{\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})}{\sqrt{n}} \right) \middle| y \boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x}) > 0 \right], \\
&= \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \Phi \left( \frac{|\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \middle| y \boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x}) > 0 \right] \\
&\ge \min_{\mathbf{x} \in \mathcal{X}} \Phi \left( \frac{|\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \\
&\ge \Phi \left( \frac{\max_{\mathbf{x} \in \mathcal{X}} |\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \quad \langle \text{\Phi is strictly decreasing.} \rangle \\
&\ge \Phi \left( \frac{\max_{\mathbf{i} \in \{-1,1\}^n} |\boldsymbol{\alpha} \cdot \mathbf{i}|}{\sqrt{n}} \right) \\
&= \Phi \left( \frac{\|\boldsymbol{\alpha}\|_1}{\sqrt{n}} \right).
\end{align*}
$$

We now prove the upper bound of $\mathcal{I}_D^\rho(h_\alpha)$. We have

$$
\begin{align*}
\mathcal{I}_D^\rho(h_\alpha) &= \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \mathbb{E}_{h'\sim\rho} \ell(h'(x), y) \middle| \ell(h(x), y) = 1 \right], \\
&= \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \Phi \left( y \frac{\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})}{\sqrt{n}} \right) \middle| y \boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x}) < 0 \right],
\end{align*}
$$
$$
\begin{align*}
&= \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \Phi \left( \frac{-|\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \middle| y \boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x}) \le 0 \right], \\
&= 1 - \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \Phi \left( \frac{|\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \middle| y \boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x}) \le 0 \right] \quad \langle \text{see Leblanc & Germain (2025)} \rangle \\
&\le 1 - \min_{x \in \mathcal{X}} \Phi \left( \frac{|\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \\
&\le 1 - \Phi \left( \frac{\max_{x \in \mathcal{X}} |\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \quad \langle \Phi \text{ is strictly decreasing.} \rangle \\
&= 1 - \Phi \left( \frac{\|\boldsymbol{\alpha}\|_1}{\sqrt{n}} \right).
\end{align*}
$$

We now prove the lower bound of $\mathbf{1}_{\mathcal{D}}^{\rho}(h_{\alpha})$. We have

$$
\begin{align*}
\mathbf{1}_{\mathcal{D}}^{\rho}(h_{\alpha}) &= \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \mathbb{E}_{h' \sim \rho} \ell(h'(x), y) \middle| \ell(h(x), y) = 1 \right], \\
&= \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \Phi \left( y \frac{\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})}{\sqrt{n}} \right) \middle| y \boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x}) < 0 \right], \\
&= \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \Phi \left( \frac{-|\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \middle| y \boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x}) \le 0 \right], \\
&= 1 - \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \Phi \left( \frac{|\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \middle| y \boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x}) \le 0 \right] \\
&\le 1 - \max_{x \in \mathcal{X}} \Phi \left( \frac{|\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \\
&\le 1 - \Phi \left( \frac{\min_{x \in \mathcal{X}} |\boldsymbol{\alpha} \cdot \mathbf{f}(\mathbf{x})|}{\sqrt{n}} \right) \quad \langle \Phi \text{ is strictly decreasing.} \rangle \\
&= 1 - \Phi \left( \frac{\bar{\alpha}}{\sqrt{n}} \right).
\end{align*}
$$

□

## B.4 Trade-off upper bounds proofs

**Theorem B.1.** For any distribution $\mathcal{D}$, any hypothesis set $\mathcal{H}$, any prior $\pi$ on $\mathcal{H}$, and $\delta \in (0, 1]$, $\lambda > 0$ with probability at least $1-\delta$ on the random choice $S \sim \mathcal{D}^m$ we have for any $\rho$ over $\mathcal{H}$ and any $h \in \mathcal{H}$

$$
(1 - \lambda)\mathrm{R}_{\mathcal{D}}(G_{\rho}) + \lambda\mathrm{RF}_{\mathcal{D}}(G_{\rho}) \le (1 - \lambda) \mathrm{R}_{S}^{\uparrow}(\rho, \pi, \frac{\delta}{2}, G_{\rho}) + \\
\lambda \max \left\{ \begin{aligned} & \mathrm{R}_{S|a}^{\uparrow}(\rho, \pi, \frac{\delta}{8}, G_{\rho}) - \mathrm{R}_{S|b}^{\downarrow}(\rho, \pi, \frac{\delta}{8}, G_{\rho}), \\ & \mathrm{R}_{S|b}^{\uparrow}(\rho, \pi, \frac{\delta}{8}, G_{\rho}) - \mathrm{R}_{S|a}^{\downarrow}(\rho, \pi, \frac{\delta}{8}, G_{\rho}) \end{aligned} \right\},
$$

*Proof.* We apply Theorem 2.1 to upper-bound $(1 - \lambda)\mathrm{R}_{\mathcal{D}}(G_{\rho})$ and Theorem 4.1 to upper-bound $\lambda\mathrm{RF}_{\mathcal{D}}(G_{\rho})$, both with probability with probability $1 - \frac{\delta}{2}$. Combining them via union bound yields the stated result $\square$

**Theorem B.2.** For any distribution $\mathcal{D}$, any hypothesis set $\mathcal{H}$, any prior $\pi$ on $\mathcal{H}$, and $\delta \in (0, 1]$, $\lambda > 0$ with probability at least $1-\delta$ on the random choice $S \sim \mathcal{D}^m$ we have for any $\rho$ over $\mathcal{H}$ and any $h \in \mathcal{H}$

$$
(1 - \lambda)\mathrm{R}(h) + \lambda\mathrm{RF}_{\mathcal{D}}(h) \le (1 - \lambda) \mathfrak{R}_{S}^{\uparrow}(\rho, \pi, \frac{\delta}{2}, h) + \\
\lambda \max \left\{ \mathfrak{R}_{S|a}^{\uparrow}(\rho, \pi, \frac{\delta}{8}, h) - \mathfrak{R}_{S|b}^{\downarrow}(\rho, \pi, \frac{\delta}{8}, h), \mathfrak{R}_{S|b}^{\uparrow}(\rho, \pi, \frac{\delta}{8}, h) - \mathfrak{R}_{S|a}^{\downarrow}(\rho, \pi, \frac{\delta}{8}, h) \right\},
$$

*Proof.* We apply Lemma 4.4 to upper-bound $(1 - \lambda)\mathrm{R}(h_{\alpha})$ and Theorem 4.5 to upper-bound $\lambda\mathrm{RF}_{\mathcal{D}}(h_{\alpha})$, both with probability with probability $1 - \frac{\delta}{2}$. Combining them via union bound yields the stated result $\square$
# C Experimentations

We used an NVIDIA GeForce RTX 2080 Ti graphics card for the experiments. We used a batch size equal to 1024, and a learning rate equal to 0.1 with a scheduler reducing this parameter by a factor of 10 with an epoch patience of 2. The maximal number of epochs is set to 100, and patience is set to 25 for performing early stopping. For each distribution posterior family (Categorical, Dirichlet and Gaussian) we use a uniform prior from the same family as the prior. Let $\alpha_{\pi}$ be the parameter vector corresponding to the prior distribution $\pi$. We have for the three possible distribution family :

1. Categorical $\alpha_{\pi}^{\pi} = \frac{1}{n}$ and $\pi = C(\alpha^{\pi})$

2. Dirichlet $\alpha_{\pi}^{\pi} = 1$ and $\pi = \text{Dir}(\alpha^{\pi})$

3. Gaussian $\alpha_{\pi}^{\pi} = 0$ and $\pi = N(\alpha^{\pi}, I_{n \times n})$

## C.1 Datasets overview

<table><caption>Table 1: Overview of the datasets used in the experiments and their overall imbalance, where *m* refers to the number of observations and *d* the number of features.</caption><thead><tr><th>Dataset</th><th>m</th><th>d</th><th>P<sub>S</sub>(y = +1)</th></tr></thead><tbody><tr><td>ADULT</td><td>48842</td><td>6</td><td>0.24</td></tr><tr><td>COMPAS</td><td>5278</td><td>9</td><td>0.53</td></tr><tr><td>GERMAN</td><td>1000</td><td>10</td><td>0.70</td></tr><tr><td>MEPS</td><td>15839</td><td>41</td><td>0.82</td></tr></tbody></table>

<table><caption>Table 2: An overview of the various datasets used in the experiments, with the sensitive attributes available for each and the balance according to this attribute, where *m* refers to the number of observations and *d* the number of features.</caption><thead><tr><th>Dataset</th><th>Sens. attr.</th><th>m</th><th>d</th><th>P<sub>S</sub>(A = 0)</th><th>P<sub>S</sub>(y = +1 | A = 0)</th><th>P<sub>S</sub>(A = 1)</th><th>P<sub>S</sub>(y = +1 | A = 1)</th></tr></thead><tbody><tr><td rowspan="2">ADULT</td><td>RACE</td><td rowspan="2">48842</td><td rowspan="2">6</td><td>0.14</td><td>0.15</td><td>0.86</td><td>0.25</td></tr><tr><td>GENDER</td><td>0.33</td><td>0.11</td><td>0.67</td><td>0.30</td></tr><tr><td rowspan="2">COMPAS</td><td>RACE</td><td rowspan="2">5278</td><td rowspan="2">9</td><td>0.60</td><td>0.48</td><td>0.40</td><td>0.61</td></tr><tr><td>GENDER</td><td>0.80</td><td>0.50</td><td>0.20</td><td>0.64</td></tr><tr><td rowspan="2">GERMAN</td><td>AGE</td><td rowspan="2">1000</td><td rowspan="2">10</td><td>0.15</td><td>0.59</td><td>0.85</td><td>0.72</td></tr><tr><td>GENDER</td><td>0.31</td><td>0.65</td><td>0.69</td><td>0.72</td></tr><tr><td rowspan="2">MEPS</td><td>RACE</td><td rowspan="2">15839</td><td rowspan="2">41</td><td>0.64</td><td>0.87</td><td>0.36</td><td>0.74</td></tr><tr><td>GENDER</td><td>0.52</td><td>0.79</td><td>0.48</td><td>0.87</td></tr></tbody></table>

<table><caption>Table 3: Prediction task and sensitive attributes. For each dataset, we specify the favorable outcome ($y = +1$) and the sensitive attributes. When a sensitive attribute is non-binary, it is binarized by contrasting the privileged group against the rest (e.g., White vs. Non-White).</caption><thead><tr><th>Dataset</th><th>y = +1 definition</th><th>Attribute</th><th>Values</th></tr></thead><tbody><tr><td>ADULT</td><td>Annual income > 50k$</td><td>Gender<br>Race</td><td>Male / Female<br>White / Non-White</td></tr><tr><td>COMPAS</td><td>No recidivism after 2 years</td><td>Gender<br>Race</td><td>Male / Female<br>White / Non-White</td></tr><tr><td>GERMAN</td><td>Good credit</td><td>Gender<br>Age</td><td>Male / Female<br>≥ 25 years</td></tr><tr><td>MEPS</td><td>Fewer than 10 medical visits</td><td>Gender<br>Race</td><td>Male / Female<br>White / Non-White</td></tr></tbody></table>

## C.2 Detailed results

In Tables 4 and 5, we report the test performance and corresponding generalization bounds obtained when training under each fairness constraint (DP, EO, and EOP). Additionally, Figure 2 provides a visual illustration of the results for models trained with the EO constraint, while Figure 3 presents the analogous results for EOP. The results are consistent with what we discussed in Section 6 and confirm the meaningfulness of the obtained risk and fairness bounds.
<table><caption>Table 4: Average bound value, over 5 runs, and standard deviation of the risk and fairness for each measure considered for training. For EO the O2 method cannot be directly generalized because the fairness risk is a linear combination of risks; therefore, we do not report it.</caption><thead><tr><th>Dataset</th><th>Sens. attr.</th><th>Type</th><th>Risk</th><th>DP</th><th>Risk</th><th>EO</th><th>Risk</th><th>EOP</th></tr></thead><tbody><tr><td rowspan="10">ADULT</td><td rowspan="4">GENDER</td><td>Ours - det.</td><td>21.45 ± 0.07</td><td>5.33 ± 0.05</td><td>21.45 ± 0.07</td><td>3.87 ± 0.08</td><td>21.45 ± 0.07</td><td>10.95 ± 0.27</td></tr><tr><td>Ours - sto.</td><td>43.91 ± 0.18</td><td>4.6 ± 0.04</td><td>21.69 ± 0.07</td><td>6.79 ± 0.08</td><td>43.91 ± 0.18</td><td>9.65 ± 0.12</td></tr><tr><td>O1 - sto.</td><td>43.89 ± 0.18</td><td>4.5 ± 0.04</td><td>21.44 ± 0.07</td><td>3.87 ± 0.08</td><td>43.89 ± 0.18</td><td>9.59 ± 0.12</td></tr><tr><td>O2 - sto.</td><td>50.79 ± 0.01</td><td>3.5 ± 0.01</td><td>N/A</td><td>N/A</td><td>47.22 ± 0.06</td><td>8.5 ± 0.09</td></tr><tr><td rowspan="4">OTHER</td><td>Ours - det.</td><td>21.45 ± 0.07</td><td>4.07 ± 0.09</td><td>21.45 ± 0.07</td><td>3.76 ± 0.15</td><td>21.45 ± 0.07</td><td>10.61 ± 0.57</td></tr><tr><td>Ours - sto.</td><td>21.69 ± 0.07</td><td>6.99 ± 0.1</td><td>21.69 ± 0.07</td><td>7.44 ± 0.15</td><td>21.69 ± 0.07</td><td>12.31 ± 0.53</td></tr><tr><td>O1 - sto.</td><td>21.44 ± 0.07</td><td>4.06 ± 0.09</td><td>21.44 ± 0.07</td><td>3.76 ± 0.15</td><td>21.44 ± 0.07</td><td>10.6 ± 0.57</td></tr><tr><td>O2 - sto.</td><td>50.77 ± 0.01</td><td>4.41 ± 0.02</td><td>N/A</td><td>N/A</td><td>29.4 ± 0.13</td><td>10.35 ± 0.21</td></tr><tr><td rowspan="10">COMPAS</td><td rowspan="4">GENDER</td><td>Ours - det.</td><td>40.34 ± 0.45</td><td>24.15 ± 0.43</td><td>40.34 ± 0.45</td><td>25.86 ± 0.58</td><td>40.34 ± 0.45</td><td>20.73 ± 0.55</td></tr><tr><td>Ours - sto.</td><td>52.59 ± 0.17</td><td>12.97 ± 1.32</td><td>51.22 ± 0.15</td><td>18.28 ± 0.38</td><td>51.22 ± 0.15</td><td>16.28 ± 0.43</td></tr><tr><td>O1 - sto.</td><td>52.58 ± 0.17</td><td>12.91 ± 1.31</td><td>51.22 ± 0.15</td><td>17.97 ± 0.36</td><td>51.22 ± 0.15</td><td>15.99 ± 0.4</td></tr><tr><td>O2 - sto.</td><td>53.75 ± 0.0</td><td>13.6 ± 0.01</td><td>N/A</td><td>N/A</td><td>52.09 ± 0.04</td><td>16.9 ± 0.57</td></tr><tr><td rowspan="4">OTHER</td><td>Ours - det.</td><td>40.34 ± 0.45</td><td>27.05 ± 0.72</td><td>40.34 ± 0.45</td><td>28.44 ± 0.6</td><td>40.34 ± 0.45</td><td>23.81 ± 1.19</td></tr><tr><td>Ours - sto.</td><td>52.63 ± 0.13</td><td>11.51 ± 1.22</td><td>52.7 ± 0.11</td><td>16.17 ± 1.16</td><td>52.7 ± 0.11</td><td>15.18 ± 0.91</td></tr><tr><td>O1 - sto.</td><td>52.63 ± 0.13</td><td>11.45 ± 1.21</td><td>52.69 ± 0.11</td><td>16.03 ± 1.14</td><td>52.69 ± 0.11</td><td>15.05 ± 0.89</td></tr><tr><td>O2 - sto.</td><td>52.89 ± 0.04</td><td>10.73 ± 0.08</td><td>N/A</td><td>N/A</td><td>52.29 ± 0.06</td><td>14.18 ± 0.15</td></tr><tr><td rowspan="10">GERMAN</td><td rowspan="4">GENDER</td><td>Ours - det.</td><td>37.02 ± 0.45</td><td>9.93 ± 1.67</td><td>37.02 ± 0.45</td><td>14.38 ± 2.51</td><td>37.02 ± 0.45</td><td>8.2 ± 2.18</td></tr><tr><td>Ours - sto.</td><td>37.48 ± 0.42</td><td>27.77 ± 0.63</td><td>37.48 ± 0.42</td><td>40.08 ± 0.77</td><td>37.48 ± 0.42</td><td>33.65 ± 0.32</td></tr><tr><td>O1 - sto.</td><td>37.02 ± 0.45</td><td>9.92 ± 1.67</td><td>37.02 ± 0.45</td><td>14.38 ± 2.51</td><td>37.02 ± 0.45</td><td>8.2 ± 2.18</td></tr><tr><td>O2 - sto.</td><td>57.33 ± 0.0</td><td>22.14 ± 0.01</td><td>N/A</td><td>N/A</td><td>57.33 ± 0.0</td><td>26.57 ± 0.12</td></tr><tr><td rowspan="4">OTHER</td><td>Ours - det.</td><td>37.02 ± 0.45</td><td>19.15 ± 5.13</td><td>37.02 ± 0.45</td><td>26.75 ± 5.24</td><td>37.02 ± 0.45</td><td>20.03 ± 3.67</td></tr><tr><td>Ours - sto.</td><td>37.48 ± 0.42</td><td>33.86 ± 2.45</td><td>37.48 ± 0.42</td><td>47.81 ± 1.88</td><td>37.48 ± 0.42</td><td>40.96 ± 0.37</td></tr><tr><td>O1 - sto.</td><td>37.02 ± 0.45</td><td>19.15 ± 5.13</td><td>37.02 ± 0.45</td><td>26.75 ± 5.24</td><td>37.02 ± 0.45</td><td>20.02 ± 3.67</td></tr><tr><td>O2 - sto.</td><td>57.33 ± 0.0</td><td>26.55 ± 0.0</td><td>N/A</td><td>N/A</td><td>57.33 ± 0.0</td><td>33.18 ± 0.35</td></tr><tr><td rowspan="10">MEPS</td><td rowspan="4">GENDER</td><td>Ours - det.</td><td>21.9 ± 1.95</td><td>39.8 ± 12.4</td><td>21.9 ± 1.95</td><td>39.12 ± 12.58</td><td>21.9 ± 1.95</td><td>35.4 ± 12.02</td></tr><tr><td>Ours - sto.</td><td>19.81 ± 0.05</td><td>12.35 ± 0.94</td><td>19.31 ± 0.04</td><td>13.48 ± 0.34</td><td>19.31 ± 0.04</td><td>11.15 ± 0.28</td></tr><tr><td>O1 - sto.</td><td>19.01 ± 0.07</td><td>6.86 ± 0.94</td><td>18.57 ± 0.04</td><td>7.22 ± 0.6</td><td>18.57 ± 0.04</td><td>4.73 ± 0.49</td></tr><tr><td>O2 - sto.</td><td>51.6 ± 0.01</td><td>5.66 ± 0.02</td><td>N/A</td><td>N/A</td><td>51.6 ± 0.01</td><td>6.19 ± 0.0</td></tr><tr><td rowspan="4">OTHER</td><td>Ours - det.</td><td>21.46 ± 2.16</td><td>38.85 ± 13.76</td><td>21.46 ± 2.16</td><td>36.76 ± 13.73</td><td>21.46 ± 2.16</td><td>34.27 ± 13.36</td></tr><tr><td>Ours - sto.</td><td>47.53 ± 2.05</td><td>8.0 ± 0.88</td><td>17.65 ± 0.08</td><td>11.95 ± 0.24</td><td>17.65 ± 0.08</td><td>10.72 ± 0.13</td></tr><tr><td>O1 - sto.</td><td>47.52 ± 2.06</td><td>7.9 ± 0.82</td><td>17.04 ± 0.08</td><td>8.35 ± 0.25</td><td>17.04 ± 0.08</td><td>6.6 ± 0.14</td></tr><tr><td>O2 - sto.</td><td>51.6 ± 0.01</td><td>5.83 ± 0.02</td><td>N/A</td><td>N/A</td><td>51.6 ± 0.01</td><td>6.5 ± 0.01</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>(a) Sensitive attribute: Gender.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) Sensitive attribute: Race or Age (depending on availability).</figcaption></figure>

<caption>Figure 2: Test error and generalization bound of a stochastic majority vote classifier and its deterministic counterpart for Equalized Odds (EO). To compute the Equalized Odds risk, we replace $P[y = +1]$ and $P[y = 0]$ by their empirical estimate. In this case, the O2 method cannot be directly generalized because the fairness risk is a linear combination of risks; therefore, we do not report it.</caption>
<table><caption>Table 5: Average test value, over 5 runs, and standard deviation of the risk and fairness for each measure considered for training. For EO the O2 method cannot be directly generalized because the fairness risk is a linear combination of risks; therefore, we do not report it.</caption><thead><tr><th>Dataset</th><th>Sens. attr.</th><th>Type</th><th>Risk</th><th>DP</th><th>Risk</th><th>EO</th><th>Risk</th><th>EOP</th></tr></thead><tbody><tr><td rowspan="10">ADULT</td><td rowspan="4">GENDER</td><td>Ours - det.</td><td>20.27 ± 0.28</td><td>3.75 ± 0.21</td><td>20.27 ± 0.28</td><td>0.76 ± 0.34</td><td>20.27 ± 0.28</td><td>1.75 ± 1.07</td></tr><tr><td>Ours - sto.</td><td>42.64 ± 0.17</td><td>0.93 ± 0.07</td><td>20.27 ± 0.28</td><td>0.76 ± 0.34</td><td>42.64 ± 0.17</td><td>0.43 ± 0.26</td></tr><tr><td>O1 - sto.</td><td>42.64 ± 0.17</td><td>0.93 ± 0.07</td><td>20.27 ± 0.28</td><td>0.76 ± 0.34</td><td>42.64 ± 0.17</td><td>0.43 ± 0.26</td></tr><tr><td>O2 - sto.</td><td>49.6 ± 0.01</td><td>0.01 ± 0.01</td><td>N/A</td><td>N/A</td><td>46.02 ± 0.08</td><td>0.08 ± 0.07</td></tr><tr><td rowspan="4">OTHER</td><td>Ours - det.</td><td>20.27 ± 0.28</td><td>1.49 ± 0.38</td><td>20.27 ± 0.28</td><td>0.83 ± 0.48</td><td>20.27 ± 0.28</td><td>2.89 ± 2.03</td></tr><tr><td>Ours - sto.</td><td>20.27 ± 0.28</td><td>1.49 ± 0.38</td><td>20.27 ± 0.28</td><td>0.83 ± 0.48</td><td>20.27 ± 0.28</td><td>2.89 ± 2.03</td></tr><tr><td>O1 - sto.</td><td>20.27 ± 0.28</td><td>1.49 ± 0.38</td><td>20.27 ± 0.28</td><td>0.83 ± 0.48</td><td>20.27 ± 0.28</td><td>2.89 ± 2.03</td></tr><tr><td>O2 - sto.</td><td>49.58 ± 0.01</td><td>0.09 ± 0.01</td><td>N/A</td><td>N/A</td><td>28.13 ± 0.19</td><td>0.81 ± 0.42</td></tr><tr><td rowspan="10">COMPAS</td><td rowspan="4">GENDER</td><td>Ours - det.</td><td>36.34 ± 1.77</td><td>14.92 ± 1.73</td><td>36.34 ± 1.77</td><td>12.45 ± 2.63</td><td>36.34 ± 1.77</td><td>8.68 ± 3.14</td></tr><tr><td>Ours - sto.</td><td>49.41 ± 0.23</td><td>2.26 ± 1.32</td><td>47.8 ± 0.29</td><td>2.01 ± 0.46</td><td>47.8 ± 0.29</td><td>1.39 ± 0.46</td></tr><tr><td>O1 - sto.</td><td>49.41 ± 0.23</td><td>2.26 ± 1.32</td><td>47.8 ± 0.29</td><td>2.01 ± 0.46</td><td>47.8 ± 0.29</td><td>1.39 ± 0.46</td></tr><tr><td>O2 - sto.</td><td>49.82 ± 0.01</td><td>0.09 ± 0.03</td><td>N/A</td><td>N/A</td><td>48.41 ± 0.11</td><td>0.5 ± 0.21</td></tr><tr><td rowspan="4">OTHER</td><td>Ours - det.</td><td>36.34 ± 1.77</td><td>17.01 ± 2.98</td><td>36.34 ± 1.77</td><td>13.98 ± 2.53</td><td>36.34 ± 1.77</td><td>11.96 ± 5.12</td></tr><tr><td>Ours - sto.</td><td>49.46 ± 0.22</td><td>2.11 ± 1.42</td><td>49.53 ± 0.17</td><td>2.59 ± 1.36</td><td>49.53 ± 0.17</td><td>2.57 ± 1.36</td></tr><tr><td>O1 - sto.</td><td>49.46 ± 0.22</td><td>2.11 ± 1.42</td><td>49.53 ± 0.17</td><td>2.59 ± 1.36</td><td>49.53 ± 0.17</td><td>2.57 ± 1.36</td></tr><tr><td>O2 - sto.</td><td>49.19 ± 0.04</td><td>0.9 ± 0.12</td><td>N/A</td><td>N/A</td><td>48.65 ± 0.07</td><td>1.62 ± 0.2</td></tr><tr><td rowspan="10">GERMAN</td><td rowspan="4">GENDER</td><td>Ours - det.</td><td>29.4 ± 2.04</td><td>2.89 ± 1.61</td><td>29.4 ± 2.04</td><td>3.4 ± 1.58</td><td>29.4 ± 2.04</td><td>2.83 ± 2.05</td></tr><tr><td>Ours - sto.</td><td>29.4 ± 2.04</td><td>2.89 ± 1.61</td><td>29.4 ± 2.04</td><td>3.4 ± 1.58</td><td>29.4 ± 2.04</td><td>2.83 ± 2.05</td></tr><tr><td>O1 - sto.</td><td>29.4 ± 2.04</td><td>2.89 ± 1.61</td><td>29.4 ± 2.04</td><td>3.4 ± 1.58</td><td>29.4 ± 2.04</td><td>2.83 ± 2.05</td></tr><tr><td>O2 - sto.</td><td>49.78 ± 0.01</td><td>0.11 ± 0.02</td><td>N/A</td><td>N/A</td><td>49.78 ± 0.01</td><td>0.1 ± 0.01</td></tr><tr><td rowspan="4">OTHER</td><td>Ours - det.</td><td>29.4 ± 2.04</td><td>3.93 ± 4.27</td><td>29.4 ± 2.04</td><td>5.15 ± 3.92</td><td>29.4 ± 2.04</td><td>3.88 ± 3.77</td></tr><tr><td>Ours - sto.</td><td>29.4 ± 2.04</td><td>3.93 ± 4.27</td><td>29.4 ± 2.04</td><td>5.15 ± 3.92</td><td>29.4 ± 2.04</td><td>3.88 ± 3.77</td></tr><tr><td>O1 - sto.</td><td>29.4 ± 2.04</td><td>3.93 ± 4.27</td><td>29.4 ± 2.04</td><td>5.15 ± 3.92</td><td>29.4 ± 2.04</td><td>3.88 ± 3.77</td></tr><tr><td>O2 - sto.</td><td>49.78 ± 0.01</td><td>0.19 ± 0.01</td><td>N/A</td><td>N/A</td><td>49.78 ± 0.01</td><td>0.18 ± 0.02</td></tr><tr><td rowspan="10">MEPS</td><td rowspan="4">GENDER</td><td>Ours - det.</td><td>15.11 ± 0.33</td><td>4.47 ± 0.8</td><td>15.11 ± 0.33</td><td>2.53 ± 0.73</td><td>15.11 ± 0.33</td><td>2.29 ± 0.81</td></tr><tr><td>Ours - sto.</td><td>16.31 ± 0.16</td><td>2.42 ± 0.46</td><td>16.14 ± 0.16</td><td>1.5 ± 0.47</td><td>16.14 ± 0.16</td><td>1.45 ± 0.36</td></tr><tr><td>O1 - sto.</td><td>16.31 ± 0.16</td><td>2.42 ± 0.46</td><td>16.14 ± 0.16</td><td>1.5 ± 0.47</td><td>16.14 ± 0.16</td><td>1.45 ± 0.36</td></tr><tr><td>O2 - sto.</td><td>49.56 ± 0.01</td><td>0.02 ± 0.0</td><td>N/A</td><td>N/A</td><td>49.56 ± 0.01</td><td>0.03 ± 0.0</td></tr><tr><td rowspan="4">OTHER</td><td>Ours - det.</td><td>15.11 ± 0.33</td><td>6.34 ± 0.65</td><td>15.11 ± 0.33</td><td>2.57 ± 0.33</td><td>15.11 ± 0.33</td><td>2.2 ± 0.39</td></tr><tr><td>Ours - sto.</td><td>45.28 ± 2.09</td><td>1.21 ± 0.66</td><td>15.11 ± 0.33</td><td>2.56 ± 0.33</td><td>15.11 ± 0.33</td><td>2.19 ± 0.39</td></tr><tr><td>O1 - sto.</td><td>45.28 ± 2.09</td><td>1.21 ± 0.66</td><td>15.11 ± 0.33</td><td>2.56 ± 0.33</td><td>15.11 ± 0.33</td><td>2.19 ± 0.39</td></tr><tr><td>O2 - sto.</td><td>49.56 ± 0.01</td><td>0.02 ± 0.0</td><td>N/A</td><td>N/A</td><td>49.56 ± 0.01</td><td>0.02 ± 0.01</td></tr></tbody></table>

<figure><img src="image_6.png" /><figcaption>(a) Sensitive attribute: Gender.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Sensitive attribute: Race or Age (depending on availability).</figcaption></figure>

<caption>Figure 3: Test error and generalization bound of a stochastic majority vote classifier and its deterministic counterpart for Equal Opportunity (EOP).</caption>