# The Generalization Error of Supervised Machine Learning Algorithms

Samir M. Perlaza, Xinying Zou

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

## To cite this version:

Samir M. Perlaza, Xinying Zou. The Generalization Error of Supervised Machine Learning Algorithms. 2024. [https://arxiv.org/abs/2407.04867](https://arxiv.org/abs/2407.04867)

HAL Id: hal-04789606

https://inria.hal.science/hal-04789606v2

Preprint submitted on 8 Jan 2026

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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_2.png" /></figure>
# The Generalization Error of Supervised Machine Learning Algorithms

Samir M. Perlaza and Xinying Zou

*Abstract*—In this paper, the method of gaps, a technique for deriving closed-form expressions in terms of information measures for the generalization error of supervised machine learning algorithms is introduced. The method relies on the notion of *gaps*, which characterize the variation of the expected empirical risk (when either the model or dataset is kept fixed) with respect to changes in the probability measure on the varying parameter (either the dataset or the model, respectively). This distinction results in two classes of gaps: Algorithm-driven gaps (fixed dataset) and data-driven gaps (fixed model). In general, the method relies on two central observations: (i) The generalization error is the expectation of an algorithm-driven gap or a data-driven gap. In the first case, the expectation is with respect to a measure on the datasets; and in the second case, with respect to a measure on the models. (ii) Both, algorithm-driven gaps and data-driven gaps exhibit closed-form expressions in terms of relative entropies. In particular, algorithm-driven gaps involve a Gibbs probability measure on the set of models, which represents a supervised Gibbs algorithm. Alternatively, data-driven gaps involve a worst-case data-generating (WCDG) probability measure on the set of data points, which is also a Gibbs probability measure. Interestingly, such Gibbs measures, which are exogenous to the analysis of generalization, place both the supervised Gibbs algorithm and the WCDG probability measure as natural references for the analysis of supervised learning algorithms. All existing exact expressions for the generalization error of supervised machine learning algorithms can be obtained with the proposed method. Also, this method allows obtaining numerous new exact expressions, which allows establishing connections with other areas in statistics, e.g., hypothesis testing and Pythagorean identities involving mutual information, lautum information, and/or relative entropies.

*Index Terms*—Generalization Error, Supervised Learning, Worst-Case Data Generating Probability Measure; Gibbs Algorithm, Hypothesis tests, and Pythagorean Identities.

## I. INTRODUCTION

The generalization error of a supervised machine learning algorithm is the expectation (w.r.t. the joint probability distribution of datasets and models) of the difference between its population risk and its empirical risk [1]–[11]. The generalization error has become a key metric for assessing an algorithm’s performance and its ability to generalize beyond training data. Traditional approaches for analyzing the generalization error generally fall into two categories. The first category derives upper bounds on the generalization error based on properties

of the hypothesis class, such as Rademacher complexity, VC dimension [12]–[20]; covering numbers, or metric entropy [21]–[23]. However, for many architectures of deep neural networks, the VC dimension is extremely large (even infinite), which limits the relevance of generalization analyses based on such a metric [24], [25].

The second category examines the dependency between learning algorithms and data distributions through various information-theoretic metrics [26]–[34]. The initial first characterizations of generalization error using information measures were introduced for the Gibbs algorithm in [2], [6]. Later, such a result was extended for the case of Gibbs algorithms using $\sigma$-finite reference measures [9]. For learning algorithms beyond Gibbs, two main types of guarantees are provided under the information-theoretic framework. The first type is often referred to as *guarantees in probability*, which assert that with high probability over the probability measure of the datasets, the expected risk induced by the learning algorithm is bounded above by a certain threshold. This type of guarantees is referred to as PAC-Bayesian generalization bounds as in [35]–[42]. In parallel, *guarantees in expectation* provide bounds on the generalization error. To account for the dependence between the learning algorithm and the data distribution, mutual information is a common metric in these analyses. Such information measure was first introduced in [43] and later in [4]. Chaining techniques were incorporated in [29], [31] to derive upper bounds, with similar bounds appearing in [10], [44]. Alternative metrics such as Wasserstein distance [7], [27], [30], [34], maximal leakage [28], [45], mutual $f$-information [46], and Jensen-Shannon divergence [5] have also been used to derive generalization bounds. Comprehensive literature reviews of these guarantees can be found in [47] and, more recently, in [48]. Nonetheless, for any specific use, the tightness of many of these bounds cannot be guaranteed, as noted in [49] and [50]–[52]. This highlights the need of exact characterizations of the generalization error for supervised machine learning algorithms, as those presented in [53] and [54]. These new exact expressions involve several information measures, e.g., relative entropy, mutual information and lautum information [55], and significantly motivated this work.

The present work is dedicated to deriving closed-form expressions for the generalization error of machine learning algorithms through the lens of information theory. The main contribution is a general method for such a purpose, which has been coined *the method of gaps*. Interestingly, all existing exact expressions for the generalization error of machine learning algorithms can be obtained with the proposed method.

Samir M. Perlaza and Xinying Zou are with INRIA, Centre Inria d'Université Côte d'Azur, 06902 Sophia Antipolis, France (e-mail: samir.perlaza@inria.fr, xinying.zou@inria.fr).

Samir M. Perlaza is also with the Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544 USA; and also with the GAATI Mathematics Laboratory, University of French Polynesia, 98702 Faaa, French Polynesia.
## A. Gaps and the Method of Gaps

The method of gaps owes its name to the notion of gap. The empirical risk depends on a model and a dataset. A gap characterizes the variation of the expectation on the empirical risk, when either the model or the dataset is kept fixed, and the probability measure of the varying parameter changes from an initial measure to a final measure. From this perspective, two classes of gaps might be considered. When the dataset is kept fixed and the probability distribution on the set of models is let to vary, an algorithm-driven gap is obtained. Alternatively, when the model is kept fixed and the probability distribution on the set of datasets varies, a data-driven gap is obtained. Hence, a gap depends on three parameters: Either a model or a dataset; an initial probability measure; and a final probability measure. Certain algorithm-driven and data-driven gaps have been shown to have closed-form expressions in terms of relative entropies. The first closed-form expressions of an algorithm-driven gap were presented in [56, Theorem 1] to quantify the variation of the expected empirical risk due to a deviation from the Gibbs algorithm to an alternative algorithm. This foundational result serves as a key building block in this work for deriving closed-form expressions for algorithm-driven gaps due to transitions between arbitrary algorithms. See for instance, Theorem 26 in Section VII-D. Alternatively, the first-closed form expression for a data-driven gap due to a change from a worst-case data-generating (WCDG) probability measure to an arbitrary measure was presented in [57, Theorem 5.2]. This crucial result formed the basis for deriving the closed-form expressions for data-driven gaps due to a change from and to arbitrary probability measures in [53, Theorem 8]. In a nutshell, exact expressions for algorithm-driven gaps involve the Gibbs algorithm studied in [9], while exact expressions for data-driven gaps involve the WCDG probability measure introduced in [57]. In both cases, these expressions are surprisingly simple and flexible, as they contain free parameters that can be chosen subject to few constraints.

From this perspective, two variants of the method of gaps can be identified. The former, which is based on algorithm-driven gaps, involves two steps: (i) To express the generalization error as the expectation (with respect to a probability measure on the datasets) of a particular algorithm-driven gap (see Lemma 3 in Section IV-B); and (ii) To exploit the closed-form expressions for algorithm-driven gaps presented in Section VII-D to obtain expressions for the generalization error. The method of gaps via algorithm-driven gaps, was implicitly used to obtain the exact expression of the generalization error of the Gibbs algorithm in [9, Theorem 17]<fnref n="1" />. Albeit no particular mention to a method is made therein, [9, Theorem 16] can be associated to step one of the method of gaps; and [9, Theorem 17] to step two. Unfortunately, the closed-form expressions for algorithm-driven gaps developed in [8], [9] are limited to transitions from the Gibbs algorithm to alternative algorithms. This limits such a theoretical framework to obtain exact expressions for the

generalization error of arbitrary algorithms. Nonetheless, these findings are essential for obtaining the results presented in this work.

The second variant of the method of gaps, which is based on data-driven gaps also consists of two steps: (i) To express the generalization error as the expectation (with respect to a probability measure on the models) of a particular data-driven gap (see [53, Equation (75)]); and (ii) To exploit the closed-form expressions for data-driven gaps presented in Section VIII to obtain expressions for the generalization error. This second variant was the method of proof used in [53] to obtain the first exact expression [53, Theorem 10] for the generalization error of arbitrary machine learning algorithms. Using the same method of proof, other closed-form expressions [54, Theorem 11 and Theorem 13] have been obtained. The expressions obtained via this second variant of the method of gaps are surprisingly flexible, as they depend on parameters that can be arbitrarily chosen subject to mild conditions. However, these expressions are developed under the assumption that datasets consist of data points that are independent and identically distributed. Interestingly, this assumption has been relaxed in [58] while adapting the method of gaps, as presented in this work, to the case of federated supervised machine learning algorithms.

Each variant of the method of gaps leads to different equivalent expressions for the generalization error of supervised machine learning algorithms. Interestingly, these new expressions lead to new perspectives from which the generalization error can be studied. In particular, strong connections with mismatched hypothesis testing [59] and classical hypothesis testing [60] are identified. Moreover, as a byproduct, several Phytagorean identities involving the generalization error and relative entropy are established.

## B. Notation

Sets are denoted by calligraphic uppercase letters, except sets of probability measures. Given a set $\mathcal{M}$ and a sigma-field $\mathcal{F}$ on $\mathcal{M}$, the set of all probability measures that can be defined on the measurable space $(\mathcal{M}, \mathcal{F})$ is denoted by $\Delta(\mathcal{M}, \mathcal{F})$ or simply $\Delta(\mathcal{M})$, when the sigma-field is fixed in the analysis. If $\mathcal{M} \subseteq \mathbb{R}^d$, then the Borel sigma-field on $\mathcal{M}$ is denoted by $\mathcal{B}(\mathcal{M})$. The subset of measures in $\Delta(\mathcal{M})$ that are absolutely continuous with a probability measure $Q$ is denoted by $\Delta_Q(\mathcal{M})$. Given a measure $P \in \Delta_Q(\mathcal{M})$, the Radon-Nikodym derivative of $P$ with respect to $Q$ is denoted by $\frac{dP}{dQ}$. Given a set $\mathcal{N}$, the set of all probability measures defined on $(\mathcal{M}, \mathcal{F})$ conditioned on an element of $\mathcal{N}$ is denoted by $\Delta(\mathcal{M}|\mathcal{N})$. More specifically, given a measure $P_{\mathcal{M}|\mathcal{N}} \in \Delta(\mathcal{M}|\mathcal{N})$ and $n \in \mathcal{N}$, the measure $P_{\mathcal{M}|\mathcal{N}=n}$ is in $\Delta(\mathcal{M})$.

The relative entropy is defined below as the extension to $\sigma$-finite measures of the relative entropy usually defined for probability measures.

**Definition 1 (Relative Entropy):** Given two $\sigma$-finite measures $P_1$ and $P_2$ on the same measurable space, such that $P_2$ is

<footnote n="1">¹Such a exact expression was first presented in [2]. Nonetheless, the method of proof used therein cannot be related to the method of gaps</footnote>
absolutely continuous with respect to $P_1$, the relative entropy of $P_2$ with respect to $P_1$ is

$$D(P_2 \| P_1) = \int \frac{dP_2}{dP_1}(x) \log \left( \frac{dP_2}{dP_1}(x) \right) dP_1(x), \quad (1)$$

where the function $\frac{dP_2}{dP_1}$ is the Radon-Nikodym derivative of $P_2$ with respect to $P_1$.

Given a probability measure $P_N \in \Delta(\mathcal{M})$, the mutual information (see [61] and [62]) and lautum information (see [55]) induced by the measures $P_{M|N}$ and $P_N$ are denoted respectively by

$$I(P_{M|N}; P_N) = \int D(P_{M|N=n} \| P_M) dP_N(n), \quad \text{and} \quad (2)$$

$$L(P_{M|N}; P_N) = \int D(P_M \| P_{M|N=n}) dP_N(n), \quad (3)$$

with $P_M \in \Delta(\mathcal{M})$ being the marginal measure induced by $P_{M|N}$ and $P_N$; and $D(\cdot \| \cdot)$ being the relative entropy in (1).

## II. STATISTICAL SUPERVISED MACHINE LEARNING

Let $\mathcal{M}, \mathcal{X}$ and $\mathcal{Y}$, with $\mathcal{M} \subseteq \mathbb{R}^d$, be sets of models, patterns, and labels, respectively. A pair $(x, y) \in \mathcal{X} \times \mathcal{Y}$ is referred to as a labeled pattern or as a data point. A training dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$ is a tuple of $n$ data points of the form:

$$z = ((x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)) \in (\mathcal{X} \times \mathcal{Y})^n. \quad (4)$$

Let the function $f: \mathcal{M} \times \mathcal{X} \to \mathcal{Y}$ be such that the label assigned to the pattern $x$ according to the model $\theta \in \mathcal{M}$ is $f(\theta, x)$. The function $f(\theta, \cdot) : \mathcal{X} \to \mathcal{Y}$ might for instance represent a neural network whose weights are vectorized into $\theta$. Let the function

$$\hat{\ell}: \mathcal{Y} \times \mathcal{Y} \to [0, +\infty], \quad (5)$$

be the risk or loss function. Such a function is often of the form $\hat{\ell}(\mu, \nu) = |\mu - \nu|^p$, with $p \ge 1$; or $\hat{\ell}(\mu, \nu) = 1_{\{\mu=\nu\}}$. In the following, the risk function $\hat{\ell}$ is assumed to be a nonnegative function and for all $y \in \mathcal{Y}$, $\hat{\ell}(y, y) = 0$.

In general, given a labelled pattern $(x, y) \in \mathcal{X} \times \mathcal{Y}$, the risk induced by a model $\theta \in \mathcal{M}$ is $\hat{\ell}(f(\theta, x), y)$. For the ease of notation, consider the function $\ell: \mathcal{X} \times \mathcal{Y} \times \mathcal{M} \to [0, +\infty]$ such that

$$\ell(x, y, \theta) = \hat{\ell}(f(\theta, x), y). \quad (6)$$

The problem of supervised machine learning boils down to devising an algorithm that takes as input a training dataset, as $z$ in (4), and outputs a model $\theta$, with certain probability to satisfy some performance metric. The notion of machine learning algorithm is formally introduced hereunder.

**Definition 2 (Algorithm):** A conditional probability measure $P_{\Theta|Z} \in \Delta(\mathcal{M}|(\mathcal{X} \times \mathcal{Y})^n)$ is said to represent a supervised machine learning algorithm.

Let $P_{\Theta|Z} \in \Delta(\mathcal{M}|(\mathcal{X} \times \mathcal{Y})^n)$ be an algorithm. Hence, the instance of such an algorithm trained upon the dataset $z$ in (4)

is denoted by $P_{\Theta|Z=z}$, which is simply a probability measure in $\Delta(\mathcal{M})$.

A central performance metric for a fixed model is the empirical risk it induces with respect to a given dataset. Such a metric is defined as follows.

**Definition 3 (Empirical Risk):** The empirical risk induced by a model $\theta \in \mathcal{M}$ with respect to the dataset $z$ in (4) is determined by the function $L: (\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M} \to [0, +\infty]$, which satisfies

$$L(z, \theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(x_i, y_i, \theta). \quad (7)$$

The expectation of the empirical risk $L(z, \theta)$ in (7) requires particular notations depending on whether such an expectation is with respect to a measure on the models or the datasets. More specifically, given a model $\theta$, which is kept fixed, the expectation of $L(z, \theta)$ under the assumption that the dataset $z$ is drawn from a probability measure $P \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$ is denoted using the functional $R_{\theta}: \Delta((\mathcal{X} \times \mathcal{Y})^n) \to \mathbb{R}$, which satisfies

$$R_{\theta}(P) = \int L(z, \theta) dP(z). \quad (8)$$

Alternatively, given a dataset $z$, which is kept fixed, the expectation of $L(z, \theta)$ under the assumption that the model $\theta$ is drawn from a probability measure $P \in \Delta(\mathcal{M})$ is denoted using the functional $R_z: \Delta(\mathcal{M}) \to \mathbb{R}$, which satisfies

$$R_z(P) = \int L(z, \theta) dP(\theta). \quad (9)$$

The following section introduces the generalization error. Later, it is shown that the generalization error of any supervised machine learning algorithm can be characterized by studying the sensitivity of the functionals $R_{\theta}$ in (8) and $R_z$ in (9).

## III. GENERALIZATION ERROR

In a practical setting, the generalization capability of a supervised machine learning algorithm is evaluated via test datasets, which are different to the training dataset [56].

In particular, given an algorithm $P_{\Theta|Z} \in \Delta(\mathcal{M}|(\mathcal{X} \times \mathcal{Y})^n)$, a test dataset $u \in (\mathcal{X} \times \mathcal{Y})^n$, and a training dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$, a typical evaluation of the generalization capability of the instance $P_{\Theta|Z=z}$ of such an algorithm consists in calculating the difference between the expected empirical risk it induces on the test dataset $u$ and on the training dataset $z$. That is, the difference

$$R_u(P_{\Theta|Z=z}) - R_z(P_{\Theta|Z=z}), \quad (10)$$

where the functionals $R_u$ and $R_z$ are both defined as in (9). In a nutshell, the evaluation consists in calculating the variation of the expected empirical risk induced by the algorithm $P_{\Theta|Z=z}$ with respect to a data set that changes from the training dataset $z$ to the test dataset $u$. A small variation is interpreted as a good capability of the algorithm $P_{\Theta|Z}$ to generalize the training dataset $z$ into the test dataset $u$. While the difference
in (10) being smaller than certain threshold for certain test datasets is not a guarantee of good generalization into other test datasets, this is the most popular tool used by practitioners for evaluating machine learning algorithms. This is in part, because in most cases, test and training datasets are the only data actually available.

The analysis of the generalization capabilities of an algorithm $P_{\Theta|Z}$ can be deepened if further assumptions are adopted. For instance, it can be assumed that test and training datasets are both independently drawn from the same probability measure. This is indeed, one of the most popular assumptions, and the one adopted to define the generalization error. In a nutshell, the generalization error induced by an algorithm $P_{\Theta|Z}$ is the expectation of the variation in (10) under the assumption that both test and training datasets are independently sampled from the same probability measure in $\Delta((\mathcal{X} \times \mathcal{Y})^n)$.

**Definition 4 (Generalization Error):** The generalization error induced by the algorithm $P_{\Theta|Z} \in \Delta(\mathcal{M}|(\mathcal{X} \times \mathcal{Y})^n)$ under the assumption that training and test datasets are independently sampled from a probability measure $P_Z \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$, which is denoted by $\overline{\overline{\mathcal{G}}}(P_{\Theta|Z}, P_Z)$, is

$$ \overline{\overline{\mathcal{G}}}(P_{\Theta|Z}, P_Z) \\ \triangleq \iint (R_u(P_{\Theta|Z=z}) - R_z(P_{\Theta|Z=z})) dP_Z(u) dP_Z(z). \quad (11) $$

Often, the generalization error $\overline{\overline{\mathcal{G}}}(P_{\Theta|Z}, P_Z)$ is defined as the expectation of the difference between the population error and the empirical risk. The population error, induced by a model $\theta \in \mathcal{M}$ under the assumption that datasets are drawn from the probability measure $P_Z$, is $R_{\theta}(P_Z)$, where the functional $R_{\theta}$ is defined in (8). Alternatively, the training error induced by the model $\theta$ with respect to a training dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$ is $L(z, \theta)$, where the function $L$ is defined in (7). Using these elements, the following lemma introduces an alternative expression for the generalization error $\overline{\overline{\mathcal{G}}}(P_{\Theta|Z}, P_Z)$ in terms of the population error and the empirical risk, cf., [2, Equation 2] and [4, Equation 4].

**Lemma 1:** The generalization error $\overline{\overline{\mathcal{G}}}(P_{\Theta|Z}, P_Z)$ in (11) satisfies

$$ \overline{\overline{\mathcal{G}}}(P_{\Theta|Z}, P_Z) = \iint (R_{\theta}(P_Z) - L(z, \theta)) dP_{\Theta|Z=z}(\theta) dP_Z(z), \quad (12) $$

where the functional $R_{\theta}$ is defined in (8) and the function $L$ is defined in (7).

*Proof:* The proof follows from (11) by observing the following equalities:

$$ \iint R_u (P_{\Theta|Z=z}) dP_Z (u) dP_Z (z) \\ = \iint \int L(u, \theta) dP_{\Theta|Z=z}(\theta) dP_Z (u) dP_Z (z) \quad (13) $$

$$ = \iint \left( \int L(u, \theta) dP_Z(u) \right) dP_{\Theta|Z=z}(\theta) dP_Z(z) \quad (14) $$

$$ = \iint R_{\theta}(P_Z) dP_{\Theta|Z=z}(\theta) dP_Z(z), \quad (15) $$

where the equality in (13) follows from (9); the equality in (14) follows from [63, Theorem 2.6.6]; and the equality in (15) follows from (8). The proof follows by observing that

$$ \iint R_z (P_{\Theta|Z=z}) dP_Z (u) dP_Z (z) \\ = \iint L(z, \theta) dP_{\Theta|Z=z}(\theta) dP_Z(z), \quad (16) $$

where the equality in (16) follows from (9). Finally, using (15) and (16) in (11) leads to

$$ \overline{\overline{\mathcal{G}}}(P_{\Theta|Z}, P_Z) = \iint (R_{\theta}(P_Z) - L(z, \theta)) dP_{\Theta|Z=z}(\theta) dP_Z(z), \quad (17) $$

which completes the proof.

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

The main contribution of this manuscript is a method that allows constructing explicit expressions for the generalization error in (11). In the following, such method is referred to as *the method of gaps* and is introduced in the next section.

## IV. THE METHOD OF GAPS

The method of gaps is a two-step technique to construct explicit expressions for the generalization error $\overline{\overline{\mathcal{G}}}(P_{\Theta|Z}, P_Z)$ in (11) in terms of information measures. The method is based on the analysis of the variations of the functionals $R_{\theta}$ in (8) and $R_z$ in (9). More specifically, given two probability measures $P_1$ and $P_2$ in $\Delta(\mathcal{M})$ and two probability measures $Q_1$ and $Q_2$ in $\Delta((\mathcal{X} \times \mathcal{Y})^n)$, the differences $R_z(P_1) - R_z(P_2)$ and $R_{\theta}(Q_1) - R_{\theta}(Q_2)$ capture the variation of the functionals $R_z$ and $R_{\theta}$ due to the change of measure from $P_2$ to $P_1$, and from $Q_2$ to $Q_1$, respectively. These differences are referred to as *gaps*. In a nutshell, the first step of the method of gaps consists in expressing the generalization error as either: (a) an expectation (with respect to some probability measure $Q \in \Delta((\mathcal{X} \times \mathcal{Y})^n))$ of the gap $R_z(P_1) - R_z(P_2)$, for some specific measures $P_1$ and $P_2$; or (b) an expectation (with respect to some probability measure $P \in \Delta(\mathcal{M}))$ of the gap $R_{\theta}(Q_1) - R_{\theta}(Q_2)$, for some specific measures $Q_1$ and $Q_2$. The second step consists in leveraging the properties of such gaps for expressing the expectations mentioned above in terms of information measures. To formalize the presentation of the method, the notion of gap is developed hereunder.
A. Gaps

The variations of the functional $R_\theta$ in (8), for some fixed model $\theta \in \mathcal{M}$; and those of the functional $R_z$ in (9), for some fixed dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$, due to changes in their arguments, are referred to as gaps. These gaps are studied via the following functionals:

$$G : (\mathcal{X} \times \mathcal{Y})^n \times \Delta (\mathcal{M}) \times \Delta (\mathcal{M}) \to \mathbb{R}; \text{ and} \quad (18)$$

$$G : \mathcal{M} \times \Delta (\mathcal{X} \times \mathcal{Y}) \times \Delta (\mathcal{X} \times \mathcal{Y}) \to \mathbb{R}, \quad (19)$$

where the former satisfies

$$G(z, P_1, P_2) = R_z(P_1) - R_z(P_2), \quad (20)$$

and the latter satisfies

$$G(\theta, Q_1, Q_2) = \int \ell(x, y, \theta) dQ_1(x, y) - \int \ell(x, y, \theta) dQ_2(x, y), \quad (21)$$

with the function $\ell$ defined in (6). Note that the measures $P_1$ and $P_2$ in (20) are in $\Delta(\mathcal{M})$, while the measures $Q_1$ and $Q_2$ in (21) are in $\Delta(\mathcal{X} \times \mathcal{Y})$. Despite the same notation $G$ for the functionals in (20) and in (21), their distinction is immediate from their arguments, and thus, there is no ambiguity.

Given a fixed dataset $z$; and two algorithms $P_{\Theta|Z} \in \Delta(\mathcal{M}|(\mathcal{X} \times \mathcal{Y})^n)$ and $Q_{\Theta|Z} \in \Delta(\mathcal{M}|(\mathcal{X} \times \mathcal{Y})^n)$ respectively trained upon some datasets $z_1$ and $z_2$, the gap $G(z, P_{\Theta|Z=z_1}, Q_{\Theta|Z=z_2})$ characterizes the variation of the expected empirical risk $R_z$ when the algorithm $Q_{\Theta|Z=z_1}$ changes to $P_{\Theta|Z=z_2}$. This justifies coining the gap $G(z, P_1, P_2)$ in (20) algorithm-driven gap, as $P_1$ and $P_2$ can be seen as instances of particular algorithms.

Similarly, the gap $G(\theta, Q_1, Q_2)$ in (21) characterizes the variation of the expected empirical risk $R_\theta$ in (8) when datasets are formed by $n$ data points independently sampled from $Q_1$ instead of $Q_2$. This observation becomes clearer by considering two product probability measures $P_Z \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$ and $Q_Z \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$ formed by the measures $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$ and $Q_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$. More specifically, for all measurable subsets of $(\mathcal{X} \times \mathcal{Y})^n$ of the form $A_1 \times A_2 \times \dots \times A_n$, it holds that

$$P_Z(A_1 \times A_2 \times \dots \times A_n) = \prod_{t=1}^{n} P_Z(A_t), \text{ and} \quad (22)$$

$$Q_Z(A_1 \times A_2 \times \dots \times A_n) = \prod_{t=1}^{n} Q_Z(A_t). \quad (23)$$

Under this assumption, the following lemma presents an important property of the functional $R_\theta$ in (8).

**Lemma 2:** Consider a probability measure $P_Z \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$ that satisfies (22) for some $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$. Then, the functional $R_\theta$ in (8) satisfies

$$R_\theta(P_Z) = \int \ell(\theta, x, y) dP_Z(x, y), \quad (24)$$

where the function $\ell$ is defined in (6).

*Proof:* Note that from (8), it follows that

$$\begin{align}
R_{\theta}(P_{Z}) &= \int \mathcal{L}(z, \theta) dP_{Z}(z) \nonumber \\
&= \int \frac{1}{n} \sum_{t=1}^{n} \ell(\theta, x_t, y_t) dP_{Z}(z) \tag{25}
\end{align}$$

$$= \int \ell(\theta, x, y) dP_Z(x, y), \quad (26)$$

where the equality in (25) follows from (7); and the equality in (26) follows from [63, Theorem 1.6.3]. This completes the proof. ■

Lemma 2, given a fixed model $\theta \in \mathcal{M}$ and the probability measures $P_Z$ and $Q_Z$ that respectively satisfy (22) and (23), for some $P_Z$ and $Q_Z$ in $\Delta(\mathcal{X} \times \mathcal{Y})$, leads to the following equality:

$$G(\theta, P_Z, Q_Z) = R_{\theta}(P_Z) - R_{\theta}(Q_Z), \quad (27)$$

which is the variation of the functional $R_\theta$ when its argument changes from $Q_Z \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$ to $P_Z \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$. This justifies coining the gap $G(\theta, Q_1, Q_2)$ in (21) the data-driven gap, as $P_Z$ and $Q_Z$ are interpreted as statistical descriptions of the datasets. Note the limitation due to the fact that the analysis of the variations of the functional $R_\theta$ via the functional $G$ in (21), implicitly assumes that datasets are formed by $n$ independent and identically distributed data points (see (22)). This limitation is not present while studying the variation of the functional $R_z$ via the functional $G$ in (20). This induces two different variants of the method of gaps, the first one for the case of algorithm-driven gaps; and a more limited variant for the case of data-driven gaps.

B. Method of Algorithm-driven Gaps

1) Step One: The first step of the method of algorithm-driven gaps consists in writing the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) in terms of the functional $G$ in (20), as the expectation of an algorithm-driven gap. The following lemma formalizes this first step.

**Lemma 3:** Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that for all $z$, the probability measure $P_{\Theta|Z=z}$ is absolutely continuous with respect to a probability measure $P_{\Theta} \in \Delta(\mathcal{M})$ that satisfies for all measurable subsets $C$ of $\mathcal{M}$,

$$P_{\Theta}(C) = \int P_{\Theta|Z=z}(C) dP_Z(z). \quad (28)$$

Then,

$$\bar{\bar{G}}(P_{\Theta|Z}, P_Z) = \int G(z, P_{\Theta}, P_{\Theta|Z=z}) dP_Z(z), \quad (29)$$

where the functional $G$ is defined in (20).

*Proof:* The proof is presented in Appendix B. ■

Given a training dataset $z$, as the one in (4), a probability measure $P_{\Theta|Z=z}$ represents the specific instance of an algorithm $P_{\Theta|Z}$ obtained by training such an algorithm on the training dataset $z$. From this perspective, each dataset $z$
in $(\mathcal{X} \times \mathcal{Y})^n$ generates an instance of the algorithm $P_{\Theta|Z}$. Hence, the measure $P_{\Theta}$ in (28) can be understood as the baricenter of the algorithm $P_{\Theta|Z}$. This is in the sense that the measure $P_{\Theta}$ is the convex combination of all possible instances of the algorithm $P_{\Theta|Z}$, where the coefficients of such a combination are determined by the probability measure on the datasets $P_Z$. Within this context, Lemma 3 presents the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) as the expectation (when $z$ is assumed to be drawn from $P_Z$) of the variations of the empirical risk $R_z$ in (9) when the instance $P_{\Theta|Z=z}$ of the algorithm, is replaced by the algorithm's baricenter $P_{\Theta}$.

2) Step Two: The second step consists in exploiting the fact that algorithm-driven gaps exhibit closed form expressions involving the conditional Gibbs probability measure studied in [9], [64]–[68] and used in [69]–[73]. In order to formally describe this step, such a conditional Gibbs probability measure is introduced. Consider two parameters: (a) A $\sigma$-finite measure $Q \in \Delta(\mathcal{M})$; and (b) A positive real $\lambda$. These parameters are often referred to as the reference measure; and the temperature coefficient. A Gibbs probability measure, parametrized by $Q$ and $\lambda$, and conditioned on a training dataset $z$ in $(\mathcal{X} \times \mathcal{Y})^n$, is denoted by $P_{\Theta|Z=z}^{(Q,\lambda)} \in \Delta(\mathcal{M})$. This notation is chosen to explicitly highlight the parameters $Q$, $\lambda$, and the training dataset $z$. Before introducing an explicit expression for such a measure, two mathematical objects of central importance are introduced. First, let the function $K_{Q,z}: \mathbb{R} \to \mathbb{R} \cup \{+\infty\}$ be such that

$$K_{Q,z}(t) = \log \left( \int \exp(t \mathbf{L}(z, \boldsymbol{\theta})) dQ(\boldsymbol{\theta}) \right), \quad (30)$$

where the function $\mathbf{L}$ is defined in (7). The function $K_{Q,z}$, often referred to as the log-partition function of the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$, is nondecreasing, convex, and differentiable infinitely many times [9, Lemma 15 and Lemma 16]. Let also the set $K_{Q,z} \subset (0, +\infty)$ be

$$K_{Q,z} \triangleq \{s > 0 : K_{Q,z} \left(-\frac{1}{s}\right) < +\infty\}. \quad (31)$$

The set $K_{Q,z}$ is either empty or a convex interval including the interval $(0, b)$, for some real $b \in (0, +\infty]$. See for instance, [9, Lemma 1]. Interestingly, when $Q$ is a probability measure, it follows that $K_{Q,z} = (0, +\infty)$. Let also the set $K_Q$ be

$$K_Q \triangleq \bigcap_{z \in \text{supp} Q} K_{Q,z}. \quad (32)$$

Using this notation, the Gibbs algorithm is defined as follows.

**Definition 5 (Gibbs Algorithm):** An algorithm, denoted by $P_{\Theta|Z}^{(Q,\lambda)} \in \Delta(\mathcal{M}|(\mathcal{X} \times \mathcal{Y})^n)$, is said to be a Gibbs algorithm with parameters $Q \in \Delta(\mathcal{M})$ and $\lambda \in K_Q$, with $K_Q$ in (32), if the instance of such algorithm obtained by training it upon the dataset $z$ in (4), denoted by $P_{\Theta|Z=z}^{(Q,\lambda)} \in \Delta(\mathcal{M})$, satisfies for all $\boldsymbol{\theta} \in \text{supp} Q$,

$$\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) = \exp \left( -K_{Q,z} \left(-\frac{1}{\lambda}\right) - \frac{1}{\lambda} \mathbf{L}(z, \boldsymbol{\theta}) \right), (33)$$

where the nonnegative function $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}: \mathcal{M} \to (0, +\infty)$ is the Radon-Nikodym derivative of the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ with respect to $Q$; and the functions $\mathbf{L}$ and $K_{Q,z}$ are respectively defined in (7) and (30).

Using this notation, the second step of the method of gaps is formalized as follows.

**Lemma 4:** Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that for all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the measures $P_{\Theta|Z=z}$, $P_{\Theta}$ in (28), and the $\sigma$-finite measure $Q$ in (33) satisfy $P_{\Theta|Z=z} \ll P_{\Theta} \ll Q$. Then,

$$\begin{aligned} \bar{\bar{G}}(P_{\Theta|Z}, P_Z) &= \lambda \int \left( D(P_{\Theta} \| P_{\Theta|Z=z}^{(Q,\lambda)}) - D(P_{\Theta|Z=z} \| P_{\Theta|Z=z}^{(Q,\lambda)}) \right. \\ & \qquad \left. + D(P_{\Theta|Z=z} \| Q) - D(P_{\Theta} \| Q) \right) dP_Z(z), \end{aligned} \quad (34)$$

where the measure $P_{\Theta|Z=z}^{(Q,\lambda)} \in \Delta(\mathcal{M})$ is defined in (33); and $\lambda \in K_Q$, with $K_Q$ in (32).

**Proof:** The proof follows immediately from Lemma 3 and Theorem 26, which is introduced later in Section VII-D. ■

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

Note that while the right-hand side of the equality in (34) depends on the measure $Q$ and a real $\lambda$, the left-hand side does not depend upon these parameters. This shows the paramount relevance of the equality in (34) as particular choices of $Q$ and $\lambda$ would yield different equivalent expressions for the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11). Section V explores some of these choices and presents some interesting explicit expressions for $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ emerging from (34).

### C. Method of Data-driven Gaps

1) Step One: The first step of the method of data-driven gaps consists in writing the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) in terms of the functional $\mathbf{G}$ in (21), as the expectation of a data-driven gap. To achieve such an objective, the central observation is that the joint probability measure $P_{\Theta|Z}P_Z \in \Delta(\mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n)$ shares common properties with the measure $P_{Z|\Theta}P_{\Theta} \in \Delta((\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M})$, where $P_{\Theta}$ is in (28) and the conditional probability measure $P_{Z|\Theta} \in \Delta((\mathcal{X} \times \mathcal{Y})^n | \mathcal{M})$ satisfies for all measurable subsets $\mathcal{B}$ of $(\mathcal{X} \times \mathcal{Y})^n$,

$$P_Z(\mathcal{B}) = \int P_{Z|\Theta=\theta}(\mathcal{B}) dP_{\Theta}(\theta). \quad (35)$$

These common properties are discussed in detail in Appendix A. In the following, it is assumed that the probability measure $P_Z$ in (35) is a product measure formed by the measure

$$P_Z \in \Delta(\mathcal{X} \times \mathcal{Y}). \quad (36)$$

That is, the probability measures $P_Z$ and $P_Z$ satisfy the equality in (22). For all $\boldsymbol{\theta} \in \mathcal{M}$, the marginal measures of the probability measure $P_{Z|\Theta=\theta}$, denoted by $P_{Z_t|\Theta=\theta} \in \Delta(\mathcal{X} \times \mathcal{Y})$ with $t \in \{1, 2, \dots, n\}$, are probability measures satisfying
the following conditions. Given $m \in \{1, 2, \dots, n\}$ and a measurable subset $\mathcal{A} \subseteq (\mathcal{X} \times \mathcal{Y})$, let the set $\tilde{\mathcal{B}}_m \subseteq (\mathcal{X} \times \mathcal{Y})^n$ be

$$ \mathcal{B}_m = \mathcal{A}_1 \times \mathcal{A}_2 \times \dots \times \mathcal{A}_m \times \dots \times \mathcal{A}_n, \quad (37) $$

where for all $t \in \{1, 2, \dots, n\} \setminus \{m\}$, $\mathcal{A}_t = \mathcal{X} \times \mathcal{Y}$; and $\mathcal{A}_m = \mathcal{A}$. The marginal probability measure $P_{Z_m|\Theta=\theta}$ satisfies

$$ P_{Z_m|\Theta=\theta}(\mathcal{A}) = P_{Z|\Theta=\theta}(\mathcal{B}_m). \quad (38) $$

Under the above assumptions on $P_Z$ and $P_Z$, the marginal measures $P_{Z_1|\Theta=\theta}$, $P_{Z_2|\Theta=\theta}$, ..., $P_{Z_n|\Theta=\theta}$ turn out to be identical to some $P_{Z|\Theta=\theta}$, as shown by the following lemma.

**Lemma 5:** Consider the conditional probability measure $P_{Z|\Theta} \in \Delta((\mathcal{X} \times \mathcal{Y})^n|\mathcal{M})$ and the probability measures $P_{\Theta}$ and $P_Z$ in (35). If $P_Z$ satisfies (22) for some probability measure $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$, then, for all measurable sets $\mathcal{A}$ of $(\mathcal{X} \times \mathcal{Y})$, for all $\theta \in \mathcal{M}$, and for all $m \in \{1, 2, \dots, n\}$, the measure $P_{Z_m|\Theta=\theta}$ in (38) satisfies,

$$ P_{Z_m|\Theta=\theta}(\mathcal{A}) = P_{Z|\Theta=\theta}(\mathcal{A}), \quad (39) $$

for some probability measure $P_{Z|\Theta=\theta} \in \Delta(\mathcal{X} \times \mathcal{Y})$ that satisfies,

$$ P_Z(\mathcal{A}) = \int P_{Z|\Theta=\theta}(\mathcal{A}) dP_{\Theta}(\theta). \quad (40) $$

*Proof:* Consider a fixed $m \in \{1, 2, \dots, n\}$ and the sets $\tilde{\mathcal{B}}_m$ and $\mathcal{A}_m = \mathcal{A}$ in (37). Note that

$$ P_Z(\mathcal{A}) = P_Z(\mathcal{A}_m) \quad (41) $$

$$ = P_Z(\mathcal{B}_m) \quad (42) $$

$$ = \int P_{Z|\Theta=\theta}(\mathcal{B}_m) dP_{\Theta}(\theta) \quad (43) $$

$$ = \int P_{Z_m|\Theta=\theta}(\mathcal{A}) dP_{\Theta}(\theta), \quad (44) $$

where the equality in (42) follows from the construction in (37) and the assumption in (22); the equality in (43) follows from (35); and the equality in (44) follows from (38). Note that the right-hand side of (44) depends on $m$, while the left-hand side does not. Hence, the proof focuses on showing that the conditional measures $P_{Z_1|\Theta}$, $P_{Z_2|\Theta}$, ..., $P_{Z_n|\Theta}$ in (44) are identical, and thus, independent of the choice of $m$. For doing so, given the set $\mathcal{A}$ in (37), let the function $g_A: \mathcal{M} \to [0, 1]$ be

$$ g_A(\theta) = P_{Z_m|\Theta=\theta}(\mathcal{A}), \quad (45) $$

and thus, Borel measurable. From the equality in (44), it follows that

$$ P_Z(\mathcal{A}) = \int g_A(\theta) dP_{\Theta}(\theta). \quad (46) $$

Moreover, from [63, Theorem 5.3.1], such a function $g_A$ is unique almost surely with respect to $P_{\Theta}$. The proof is completed by noticing that the choice of $m$ and $\mathcal{A}$ in (45) are irrelevant and thus, the conditional measures $P_{Z_1|\Theta}$, $P_{Z_2|\Theta}$, ..., $P_{Z_n|\Theta}$ are identical to a conditional measure $P_{Z|\Theta}$ almost

surely with respect to $P_{\Theta}$. That is, $g_A(\theta) = P_{Z|\Theta=\theta}(\mathcal{A})$, with $P_{Z|\Theta}$ in (39).

The following lemma formalizes the first step of the method of data-driven gaps.

**Lemma 6:** Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that

(a) The probability measure $P_Z$ satisfies (22) for some $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$;

(b) For all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measures $P_{\Theta|Z=z}$ and $P_{\Theta}$ in (28) are mutually absolutely continuous; and

(c) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ in (35) are mutually absolutely continuous.

Then,

$$ \bar{\bar{G}}(P_{\Theta|Z}, P_Z) = \int G(\theta, P_Z, P_{Z|\Theta=\theta}) dP_{\Theta}(\theta), \quad (47) $$

where the functional $G$ is defined in (21); and the conditional probability measure $P_{Z|\Theta}$ satisfies (40).

*Proof:* The proof is presented in Appendix C. ■

From a Bayesian perspective, if the algorithm $P_{\Theta|Z=z}$ is understood as the posterior of the prior $P_{\Theta}$ after the observation of the training dataset $z$, then, the probability measure $P_{Z|\Theta=\theta}$ in (39) can be understood as the likelihood of the datasets after the observation of the model $\theta$. From this perspective, Lemma 6 presents the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) as the expectation (when $\theta$ is assumed to be drawn from $P_{\Theta}$ in (28)) of the variations of the empirical risk $R_{\theta}$ in (8) when the measure on the data points changes from the likelihood $P_{Z|\Theta=\theta}$ to the ground-truth probability distribution $P_Z$, which is invariant with respect to the models.

It is important to highlight the impact on Lemma 6 of the assumption in (22). In particular, note that the gap $G(\theta, P_Z, P_{Z|\Theta=\theta})$ in (47) depends exclusively on the measure $P_Z$ (instead of the joint measure $P_Z$) and the marginal measure $P_{Z|\Theta=\theta}$ (instead of the joint measure $P_{Z|\Theta=\theta}$). This simplification follows from Lemma 5 and plays an important role allowing to involve the WCDG probability measure introduced in [57].

2) Step Two: The second step consists in exploiting the fact that data-driven gaps exhibit closed-form expressions involving the WCDG probability measure introduced in [57] and further studied in [53]. The WCDG probability measure is conditioned on a model $\theta \in \mathcal{M}$; and parametrized by a real $\beta > 0$ and a probability measure $P_S$ in $\Delta(\mathcal{X} \times \mathcal{Y})$. Such a WCDG probability measure is denoted by $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)} \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$. Defining an explicit expression for $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ requires defining the following mathematical objects. Let $J_{P_S, \theta}: \mathbb{R} \to \mathbb{R}$ be the function

$$ J_{P_S, \theta}(t) = \log \left( \int \exp(t\ell(\theta, x, y)) dP_S(x, y) \right), \quad (48) $$

where the function $\ell$ is defined in (6). The function $J_{P_S, \theta}$ in (48) is convex, nondecreasing, and differentiable infinitely many times in the interior of $\{t \in \mathbb{R}: J_{P_S, \theta}(t) < +\infty\}$ [53,
Lemma 1]. Let also the sets $\mathcal{J}_{P_S, \theta} \subseteq (0, +\infty)$ and $\mathcal{J}_{P_S} \subseteq (0, +\infty)$ be

$$ \mathcal{J}_{P_S, \theta} \triangleq \left\{ t \in (0, +\infty) : \mathcal{J}_{P_S, \theta} \left( \frac{1}{t} \right) < +\infty \right\}, \quad (49) $$

and

$$ \mathcal{J}_{P_S} \triangleq \bigcap_{\theta \in \text{supp } P_S} \mathcal{J}_{P_S, \theta}. \quad (50) $$

The set $\mathcal{J}_{P_S, \theta}$ is either empty or an interval including the interval $(b, +\infty)$, for some real $b \in (0, +\infty]$. See for instance, [53, Lemma 2]. Using this notation, the WCDG conditional probability measure is defined as follows.

**Definition 6 (The WCDG conditional probability measure):** A conditional probability measure, denoted by $P_{\hat{Z}|\Theta}^{(P_S, \beta)} \in \Delta(\mathcal{X} \times \mathcal{Y}|\mathcal{M})$, is said to be a WCDG conditional probability measure with parameters $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$ and $\beta \in \mathcal{J}_{P_S}$, with $\mathcal{J}_{P_S}$ in (50), if for all $\theta \in \mathcal{M}$ and for all $(x, y) \in \text{supp } P_S$,

$$ \frac{\mathrm{d}P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{\mathrm{d}P_S}(x, y) = \exp\left(\frac{1}{\beta}\ell(\theta, x, y) - \mathcal{J}_{P_S, \theta}\left(\frac{1}{\beta}\right)\right), \quad (51) $$

where the function $\frac{\mathrm{d}P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{\mathrm{d}P_S} : \mathcal{X} \times \mathcal{Y} \to (0, +\infty)$ is the Radon-Nikodym derivative of the measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ with respect to $P_S$; and the functions $\ell$ and $\mathcal{J}_{P_S, \theta}$ are defined in (6) and (48).

Using this notation, the second step of the method of data-driven gaps is formalized as follows.

**Lemma 7:** Consider the generalization error $\overline{\mathcal{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that:

(a) The probability measure $P_Z$ satisfies (22) for some $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$;

(b) For all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measures $P_{\Theta|Z=z}$ and $P_{\Theta}$ in (28) are mutually absolutely continuous;

(c) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ in (35) are mutually absolutely continuous; and

(d) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ satisfy (40) and are both absolutely continuous with the probability measure $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$ in (51).

Then,

$$ \overline{\mathcal{G}}(P_{\Theta|Z}, P_Z) = \beta \iint \left( D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) - D(P_{Z|\Theta=\theta} \| P_S) + D(P_Z \| P_S) \right) \mathrm{d}P_{\Theta}(\theta), \quad (52) $$

where the probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ is defined in (51); and $\beta \in \mathcal{J}_{P_S}$, with $\mathcal{J}_{P_S}$ in (50).

**Proof:** Under Assumptions (a) and (c), Lemma 37 and Lemma 38 (in Appendix A) imply that for all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ are mutually absolutely continuous. Hence, the proof follows immediately

from Lemma 6 and Theorem 32, which is introduced later in Section VIII.

Note that while the right-hand side of the equality in (52) depends on the probability measure $P_S$ and $\beta$, the left-hand side does not depend upon these parameters. This shows the paramount relevance of the equality in (52) as particular choices of $P_S$ and $\beta$ would yield different equivalent expressions for the generalization error $\overline{\mathcal{G}}(P_{\Theta|Z}, P_Z)$ in (11).

The proof of Lemma 7 uses Lemma 5 and thus, it is written in terms of the marginal measure $P_Z$ and the marginal conditional measure $P_{Z|\Theta}$ instead of the joint probability measure $P_Z$ and the joint conditional probability measure $P_{Z|\Theta}$. This is the key step that allows using the WCDG probability measure $P_{\hat{Z}|\Theta}^{(P_S, \beta)}$ defined in (51) for obtaining (52). Section VI explores the equality in (52) and presents new explicit expressions for $\overline{\mathcal{G}}(P_{\Theta|Z}, P_Z)$ in (11).

## V. EXPLICIT EXPRESSIONS OBTAINED VIA THE METHOD OF ALGORITHM-DRIVEN GAPS

This section focuses on constructing novel explicit expressions for the generalization error $\overline{\mathcal{G}}(P_{\Theta|Z}, P_Z)$ in (11) by algebraically manipulating the expression in (34). In these expressions, the central mathematical object is the Gibbs probability measure $P_{\Theta|Z}^{(Q, \lambda)}$ (Definition 5). From this perspective, these expressions are obtained, at least in part, by comparing the algorithm $P_{\Theta|Z}$ with the Gibbs algorithm $P_{\Theta|Z}^{(Q, \lambda)}$.

This section is divided in four subsections. The first three subsections provide explicit expressions for the generalization error $\overline{\mathcal{G}}(P_{\Theta|Z}, P_Z)$ aiming at establishing connections to existing results in statistics (statistical hypothesis testing), information theory (information measures), and Euclidian geometry (Pythagorean Theorems). The last subsection reviews the generalization error for the special case of the Gibbs algorithm.

### A. Connections to Statistical Hypothesis Testing

The equality in (34) can be alternatively expressed as shown by the following theorem.

**Theorem 8:** Consider the generalization error $\overline{\mathcal{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that for all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the measures $P_{\Theta|Z=z}$, $P_{\Theta}$ in (28), and the $\sigma$-finite measure $Q$ in (33) satisfy $Q \ll P_{\Theta|Z=z} \ll P_{\Theta} \ll Q$. Then,

$$ \begin{aligned} \overline{\mathcal{G}}(P_{\Theta|Z}, P_Z) = & \lambda \iint \left( \log \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q, \lambda)}}{\mathrm{d}Q}(\theta) \right) \mathrm{d}P_{\Theta|Z=z}(\theta) P_Z(z) \\ & - \lambda \iint \left( \log \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q, \lambda)}}{\mathrm{d}Q}(\theta) \right) \mathrm{d}P_{\Theta}(\theta) \mathrm{d}P_Z(z), \end{aligned} \quad (53) $$

where the Radon-Nikodym derivative $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q, \lambda)}}{\mathrm{d}Q}$ is defined in (33); and $\lambda \in \mathcal{K}_Q$, with $\mathcal{K}_Q$ in (32).
*Proof:* Given the assumptions, Lemma 4 holds. The proof follows by observing that the differences $D(P_{\Theta}\|P_{\Theta|Z=z}^{(Q,\lambda)}) - D(P_{\Theta}\|Q)$ and $D(P_{\Theta|Z=z}\|Q) - D(P_{\Theta|Z=z}\|P_{\Theta|Z=z}^{(Q,\lambda)})$ in (34) respectively satisfy the following equalities:

$$ 
\begin{align} 
& D(P_{\Theta}\|P_{\Theta|Z=z}^{(Q,\lambda)}) - D(P_{\Theta}\|Q) \nonumber \\
&= \int \left( \log \frac{dP_{\Theta}}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) - \log \frac{dP_{\Theta}}{dQ}(\theta) \right) dP_{\Theta}(\theta) \tag{54} \\
&= -\int \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta}(\theta), \tag{55}
\end{align} 
$$

where the equality in (55) follows from the fact that the measures $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ are mutually absolutely continuous [9, Lemma 3] and [74, Theorem 4]. Using the same arguments,

$$ 
\begin{align} 
& D(P_{\Theta|Z=z}\|Q) - D(P_{\Theta|Z=z}\|P_{\Theta|Z=z}^{(Q,\lambda)}) \nonumber \\
&= \int \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta|Z=z}(\theta). \tag{56}
\end{align} 
$$

Plugging both (55) and (56) into (34) yields (53), which completes the proof. ■

The relevance of Theorem 8 lies on the fact that it allows framing the generalization error $\bar{G}(P_{\Theta|Z}, P_Z)$ in (11) within the context of a mismatched hypothesis test. See [59] and [75]. Consider a hypothesis test in which the objective is to determine whether an observation $(\theta, z) \in \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n$ is generated from either a probability distribution $P_{\Theta|Z}^{(Q,\lambda)}P_Z \in \Delta(\mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n)$ ($H_0$, null hypothesis) or from the alternative distribution $QP_Z \in \Delta(\mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n)$ ($H_1$, alternative hypothesis):

$$ 
\left\{ 
\begin{array}{ll} 
H_0: & (\theta, z) \sim P_{\Theta|Z}^{(Q,\lambda)} P_Z \\ 
H_1: & (\theta, z) \sim QP_Z. 
\end{array} 
\right. 
\tag{57} 
$$

Such a hypothesis test is said to be mismatched because none of the hypotheses matches the assumptions on the probability distribution of the observations. More specifically, the hypothesis test in (57) is studied twice under different assumptions. First, the observation $(\theta, z)$ is assumed to be sampled from the joint probability measure $P_{\Theta|Z}P_Z$. Second, the observation $(\theta, z)$ is assumed to be sampled from the product of the marginals $P_{\Theta}P_Z$. The first case correspond to the scenario in which the pairs $(\theta, z)$ are such that $z$ is sampled from $P_Z$ and is the training dataset of the algorithm $P_{\Theta|Z}$ under study. At the same time, the model $\theta$ is an output of such an instance of the algorithm, i.e., the model $\theta$ is sampled from $P_{\Theta|Z=z}$. The second case corresponds to the scenario in which models are independent of the datasets. Independently of such scenarios, the log-likelihood ratio to decide based upon the observation $(\theta, z)$ on the null or alternative hypothesis in (57) is $\log \frac{dP_{\Theta|Z}^{(Q,\lambda)}P_Z}{dQP_Z}(\theta, z)$. Essentially, given a $\gamma > 0$, if $\log \frac{dP_{\Theta|Z}^{(Q,\lambda)}P_Z}{dQP_Z}(\theta, z) \ge \gamma$, then the null hypothesis is accepted. Alternatively, the null hypothesis

is rejected if $\log \frac{dP_{\Theta|Z}^{(Q,\lambda)}P_Z}{dQP_Z}(\theta, z) < \gamma$. Interestingly, the term $\frac{dP_{\Theta|Z}^{(Q,\lambda)}P_Z}{dQP_Z}(\theta, z)$ satisfies

$$ \frac{dP_{\Theta|Z}^{(Q,\lambda)} P_Z}{dQP_Z}(\theta, z) = \frac{dP_{\Theta|Z}^{(Q,\lambda)} P_Z}{dP_{\Theta}^{(Q,\lambda)} P_Z}(\theta, z) \frac{dP_{\Theta}^{(Q,\lambda)} P_Z}{dQP_Z}(\theta, z) \tag{58} $$

$$ = \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta}^{(Q,\lambda)}}(\theta) \frac{dP_{\Theta}^{(Q,\lambda)} P_Z}{dQP_Z}(\theta, z) \tag{59} $$

$$ = \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta}^{(Q,\lambda)}}(\theta) \frac{dP_{\Theta}^{(Q,\lambda)}}{dQ}(\theta, z) \tag{60} $$

$$ = \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta), \tag{61} $$

where the probability measure $P_{\Theta}^{(Q,\lambda)} \in \Delta(\mathcal{M})$ in (58) is the marginal in $\Delta(\mathcal{M})$ of the joint probability measure $P_{\Theta|Z}^{(Q,\lambda)}P_Z$. That is, for all measurable sets $A$ in $\mathcal{M}$,

$$ P_{\Theta}^{(Q,\lambda)}(A) = \int P_{\Theta|Z=z}^{(Q,\lambda)}(A) dP_Z(z). \tag{62} $$

The equality in (58) follows from [74, Theorem 4]; the equality in (59) follows from [74, Theorem 11]; the equality in (60) follows from [74, Theorem 8]; and the equality in (61) follows from [74, Theorem 4]. The equality in (61), allows re-stating the hypotheses $H_0$ and $H_1$ in (57) as follows:

$$ 
\left\{ 
\begin{array}{ll} 
H_0: & \theta \sim P_{\Theta|Z=z}^{(Q,\lambda)} \\ 
H_1: & \theta \sim Q. 
\end{array} 
\right. 
\tag{63} 
$$

This is essentially because both (57) and (63) exhibit the same log-likelihood ratio. In (63), the objective is to determine whether the model $\theta$ is sampled from a Gibbs algorithm whose reference measure is $Q$ and has been trained upon the dataset $z$ ($H_0$ null hypothesis); or from the reference measure $Q$ ($H_1$ alternative hypothesis), which is invariant with respect to the dataset $z$. Interestingly, both measures, $P_{\Theta|Z}^{(Q,\lambda)}$ and $Q$ are exogenous to the algorithm under study $P_{\Theta|Z}$. More importantly, both $Q$ and $\lambda$ can be arbitrarily chosen subject to the conditions of the theorem. From this perspective, the connection between the hypothesis test in (63) and the generalization error in (11) appears via the assumptions on the observations $(\theta, z)$. In this context, the role of the parameter $\gamma$ mentioned above plays a central role. More specifically, consider the set

$$ \mathcal{A}_{\gamma} = \left\{ (\theta, z) \in \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n : \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \ge \gamma \right\}, \tag{64} $$

which is the acceptance region of the null hypothesis. That is, if a given observation $(\theta, z)$ satisfies $(\theta, z) \in \mathcal{A}_{\gamma}$, then the null hypothesis $H_0$ in (57) is adopted. Consider also the following probabilities

$$ P_{\Theta|Z}P_Z(\mathcal{A}_{\gamma}) = 1 - P_{\Theta|Z}P_Z(\mathcal{A}_{\gamma}^{\mathrm{c}}), \quad \text{and} \tag{65} $$

$$ P_{\Theta}P_Z(\mathcal{A}_{\gamma}) = 1 - P_{\Theta}P_Z(\mathcal{A}_{\gamma}^{\mathrm{c}}). \tag{66} $$

The term $P_{\Theta|Z}P_Z(\mathcal{A}_{\gamma})$ represents the probability of choosing $H_0$ under the assumption that observations $(\theta, z)$ are obtained
by sampling $P_{\Theta|Z}P_Z$. Alternatively, the term $P_{\Theta}P_Z(A_{\gamma})$ represents the probability of choosing $H_0$ under the assumption that observations $(\theta, z)$ are sampled from $P_{\Theta}P_Z$.

The connection between the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and the hypothesis test in (57) becomes more evident thanks to the following theorem, which uses the following parameters:

$$ \bar{\gamma} \triangleq \sup \left\{ \log \frac{d P_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} (\theta) \in \mathbb{R} : (\theta, z) \in \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n \right\} \quad (67) $$

and

$$ \underline{\gamma} \triangleq \inf \left\{ \log \frac{d P_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} (\theta) \in \mathbb{R} : (\theta, z) \in \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n \right\} \quad (68) $$

**Theorem 9:** Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that for all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the measures $P_{\Theta|Z=z}$, $P_{\Theta}$ in (28), and the $\sigma$-finite measure $Q$ in (64) satisfy $Q \ll P_{\Theta|Z=z} \ll P_{\Theta} \ll Q$. Then,

$$ \begin{aligned} & \lambda(\underline{\gamma} - \gamma) P_{\Theta|Z} P_Z(A_{\gamma}^c) + \lambda(\gamma - \bar{\gamma}) P_{\Theta} P_Z(A_{\gamma}) \\ & \le \bar{\bar{G}}(P_{\Theta|Z}, P_Z) \le \\ & \lambda(\bar{\gamma} - \gamma) P_{\Theta|Z} P_Z(A_{\gamma}) + \lambda(\gamma - \underline{\gamma}) P_{\Theta} P_Z(A_{\gamma}^c), \end{aligned} \quad (69) $$

where $\gamma$ satisfies

$$ \underline{\gamma} \le \gamma \le \bar{\gamma}, \quad (70) $$

and $\bar{\gamma}$ and $\underline{\gamma}$ are respectively defined in (67) and (68); the set $A_{\gamma}$ is defined in (64); and the measures $P_{\Theta|Z}P_Z$ and $P_{\Theta}P_Z$ are both in $\triangle (\mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n)$.

*Proof:* The proof is presented in Appendix D. ■

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

The interest of Theorem 9 is beyond the tightness of the bounds in (69), which can be optimized with respect to $\gamma$, $\lambda$, and $Q$. The key observation is the central role played by the hypothesis test in (57) in the analysis of the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11). In particular, note that the constants $\bar{\gamma}$ in (67) and $\underline{\gamma}$ in (68) are independent of the algorithm $P_{\Theta|Z}$ under study. The dependence on the algorithm $P_{\Theta|Z}$ and the probability measure on the datasets $P_Z$ is via the probabilities $P_{\Theta|Z}P_Z(A_{\gamma})$ and $P_{\Theta}P_Z(A_{\gamma})$, which depend on $\gamma$, $\lambda$, and $Q$; and inform on the probability of choosing the null hypothesis in (57) under two different assumptions. The former is under the assumption that models are drawn from the specific instance of the algorithm $P_{\Theta|Z=z}$ and the training dataset $z$ is drawn from $P_Z$. The latter is under the assumptions that models are drawn from $P_{\Theta}$ (Barycenter of the algorithm $P_{\Theta|Z}$) and the training dataset $z$ is drawn from $P_Z$.

## B. Connections to Information Measures

The following theorem shows an expression for the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) in terms of the sum of the mutual information $I(P_{\Theta|Z}; P_Z)$ and the lautum information $L(P_{\Theta|Z}; P_Z)$.

**Theorem 10:** Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that for all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measures $P_{\Theta|Z=z}$ and $P_{\Theta}$ in (28) satisfy $Q \ll P_{\Theta|Z=z} \ll P_{\Theta} \ll Q$, for some $\sigma$-finite measure $Q \in \triangle (\mathcal{M})$. Then,

$$ \begin{aligned} \bar{\bar{G}}(P_{\Theta|Z}, P_Z) = & \lambda (I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z)) \\ & + \lambda \iint \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}} (\theta) dP_{\Theta|Z=z} (\theta) dP_Z (z) \\ & - \lambda \iint \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}} (\theta) dP_{\Theta} (\theta) dP_Z (z), \end{aligned} \quad (71) $$

where the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is defined in (33); and $\lambda \in \mathcal{K}_Q$, with $\mathcal{K}_Q$ in (32).

*Proof:* The proof follows from Lemma 4, which holds under the current assumptions. More specifically, the proof is divided into two parts. The first part focuses on the difference $\int (D(P_{\Theta|Z=z}\|Q) - D(P_{\Theta}\|Q)) dP_Z(z)$ in (34), which satisfies the following equalities:

$$ \begin{aligned} & \int (D(P_{\Theta|Z=z}\|Q) - D(P_{\Theta}\|Q)) dP_Z(z) \\ &= \int D(P_{\Theta|Z=z}\|Q) dP_Z(z) - D(P_{\Theta}\|Q) \end{aligned} \quad (72) $$

$$ = \int \left( \int \log \left( \frac{dP_{\Theta|Z=z}}{dQ}(\theta) \right) dP_{\Theta|Z=z}(\theta) \right) P_Z(z) - D(P_{\Theta}\|Q) \quad (73) $$

$$ = \int \left( \int \log \left( \frac{dP_{\Theta|Z=z}}{dQ}(\theta) \right) dP_{\Theta|Z=z}(\theta) \right) dP_Z(z) - \int \log \left( \frac{dP_{\Theta}}{dQ}(\theta) \right) dP_{\Theta}(\theta) \quad (74) $$

$$ = \int \left( \int \log \left( \frac{dP_{\Theta|Z=z}}{dQ}(\theta) \right) dP_{\Theta|Z=z}(\theta) \right) dP_Z(z) - \int \left( \int \log \left( \frac{dP_{\Theta}}{dQ}(\theta) \right) dP_{\Theta|Z=z}(\theta) \right) dP_Z(z) \quad (75) $$

$$ = \int \left( \int \log \left( \frac{dP_{\Theta|Z=z}}{dP_{\Theta}}(\theta) \right) dP_{\Theta|Z=z}(\theta) \right) dP_Z(z) \quad (76) $$

$$ = I(P_{\Theta|Z}; P_Z), \quad (77) $$

where the equality in (76) follows from [74, Theorem 4]. Plugging (77) into (34) leads to

$$ \begin{aligned} \bar{\bar{G}}(P_{\Theta|Z}, P_Z) = & \lambda I(P_{\Theta|Z}; P_Z) \\ & + \lambda \int (D(P_{\Theta}\|P_{\Theta|Z=z}^{(Q,\lambda)}) - D(P_{\Theta|Z=z}\|P_{\Theta|Z=z}^{(Q,\lambda)})) dP_Z(z). \end{aligned} \quad (78) $$

The second part of the proof focuses on the term $\int D(P_{\Theta}\|P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(z)$ in (78). Hence, the
following holds

$$
\begin{align}
& \int D(P_{\Theta} \| P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(z) \nonumber \\
& = \iint \log \frac{dP_{\Theta}}{dP_{\Theta|Z=z}^{(Q,\lambda)}} (\theta) dP_{\Theta}(\theta) dP_Z(z) \tag{79}
\end{align}
$$

$$
= \iint \log \left( \frac{dP_{\Theta}}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \frac{dP_{\Theta|Z=z}}{dP_{\Theta|Z=z}(\theta)} \right) dP_{\Theta}(\theta) dP_Z(z) \quad (80)
$$

$$
= \iint \log \frac{dP_{\Theta|Z=z}}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) dP_{\Theta}(\theta) dP_Z(z) \\
+ \iint \log \frac{dP_{\Theta}}{dP_{\Theta|Z=z}}(\theta) dP_{\Theta}(\theta) dP_Z(z) \quad (81)
$$

$$
= \iint \log \frac{dP_{\Theta|Z=z}}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) dP_{\Theta}(\theta) dP_Z(z) + L(P_{\Theta|Z}; P_Z), \quad (82)
$$

where the equality in (80) follows from [74, Theorem 3]; and the equality in (81) follows from [74, Theorem 4] and [9, Lemma 3]. Finally, plugging (82) into (78) completes the proof. ■

In Theorem 10, the term

$$
\begin{align}
& \lambda \iint \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\theta) dP_{\Theta|Z=z}(\theta) dP_Z(z) \nonumber \\
& \quad - \lambda \iint \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\theta) dP_{\Theta}(\theta) dP_Z(z), \tag{83}
\end{align}
$$

is of the same form as the one in the right-hand side of (53). Thus, it can also be interpreted in the context of a hypothesis test. Consider the training dataset $z$ in (4), which is obtained by sampling from the measure $P_Z$. Assume that both the algorithm $P_{\Theta|Z}$ and the Gibbs algorithm $P_{\Theta|Z}^{(Q,\lambda)}$ are trained upon the same dataset $z$. Hence, the hypothesis test consists in determining whether a model $\theta$ has been obtained from the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$, which represents a Gibbs algorithm trained upon $z$ ($H_0$ null hypothesis); or from the probability measure $P_{\Theta|Z=z}$, which represents the algorithm under study trained upon $z$ ($H_2$ alternative hypothesis). That is,

$$
\left\{
\begin{array}{ll}
H_0: & \theta \sim P_{\Theta|Z=z}^{(Q,\lambda)} \\
H_1: & \theta \sim P_{\Theta|Z=z}.
\end{array}
\right.
\qquad (84)
$$

The main objective of such a hypothesis test, is to determine
whether models are being sampled from a Gibbs algorithm
or the algorithm under study, assuming that both algorithms
have been trained upon the same dataset. The resulting log-
likelihood ratio to decide on either hypothesis in (84), based on
the observation of the pair (θ, z), is log (dP<sub>Θ|Z=z</sub><sup>(Q,λ)</sup> / dP<sub>Θ|Z=z</sub><sup>(Q,λ)</sup>) (θ). Hence,
given a nonnegative real γ, the null hypothesis is accepted if
log (dP<sub>Θ|Z=z</sub><sup>(Q,λ)</sup> / dP<sub>Θ|Z=z</sub><sup>(Q,λ)</sup>) (θ) ≥ γ. Conversely, the alternative hypothesis is
accepted if log (dP<sub>Θ|Z=z</sub><sup>(Q,λ)</sup> / dP<sub>Θ|Z=z</sub><sup>(Q,λ)</sup>) (θ) < γ. The acceptance region of the
null hypothesis is the set

$$
\mathcal{B}_{\gamma} \triangleq \left\{ (\theta, z) \in \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n : \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \ge \gamma \right\}. (85)
$$

Consider the following probabilities

$$
P_{\Theta|Z} P_Z (\mathcal{B}_{\gamma}) = 1 - P_{\Theta|Z} P_Z (\mathcal{B}_{\gamma}^{\mathrm{c}}), \quad \text{and} \quad (86)
$$

$$
P_{\Theta} P_Z (\mathcal{B}_{\gamma}) = 1 - P_{\Theta} P_Z (\mathcal{B}_{\gamma}^{c}). \quad (87)
$$

The former represents the probability of choosing the null
hypothesis under the assumption that the observation (θ, z)
is sampled from the joint probability measure P<sub>Θ|Z</sub>P<sub>Z</sub>. The
latter represents the probability of choosing the null hypothesis
under the assumption that the observation (θ, z) is sampled
from the product probability measure P<sub>Θ</sub>P<sub>Z</sub>. Consider also
the following values

$$
\bar{\gamma} \triangleq \sup \left\{ \log \frac{d P_{\Theta|Z=z}^{(Q,\lambda)}}{d P_{\Theta|Z=z}}(\theta) \in \mathbb{R} : (\theta, z) \in \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n \right\} \quad (88)
$$

and

$$
\gamma \triangleq \inf \left\{ \log \frac{d P_{\Theta|Z=z}^{(Q,\lambda)}}{d P_{\Theta|Z=z}}(\theta) \in \mathbb{R} : (\theta, z) \in \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n \right\}. (89)
$$

Using this notation, the following theorem strengthens the
connexion between the generalization error $\overline{\mathcal{G}}(P_{\Theta|Z}, P_Z)$
in (11) and the hypothesis test in (84).

Theorem 11: Consider the generalization error $\overline{\mathcal{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that for all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the measures $P_{\Theta|Z=z}$, $P_{\Theta}$ in (28), and the $\sigma$-finite measure $Q$ in (85), satisfy $Q \ll P_{\Theta|Z=z} \ll P_{\Theta} \ll Q$. Then,

$$
\begin{align}
& \lambda (\underline{\gamma} - \gamma) P_{\Theta|Z} P_Z (\mathcal{B}_{\gamma}^{\mathrm{c}}) + \lambda (\gamma - \bar{\gamma}) P_{\Theta} P_Z (\mathcal{B}_{\gamma}) \nonumber \\
& \le \overline{\mathcal{G}} (P_{\Theta|Z}, P_Z) - \lambda (I (P_{\Theta|Z}; P_Z) + L (P_{\Theta|Z}; P_Z)) \le \nonumber \\
& \lambda (\bar{\gamma} - \gamma) P_{\Theta|Z} P_Z (\mathcal{B}_{\gamma}) + \lambda (\gamma - \underline{\gamma}) P_{\Theta} P_Z (\mathcal{B}_{\gamma}^{\mathrm{c}}), \tag{90}
\end{align}
$$

where $\gamma$ satisfies

$$
\underline{\gamma} \le \gamma \le \bar{\gamma}, \tag{91}
$$

and $\bar{\gamma}$ and $\underline{\gamma}$ are respectively defined in (88) and (89); the set $\mathcal{B}_{\gamma}$ is defined in (85); and the measures $P_{\Theta|Z}P_Z$ and $P_{\Theta}P_Z$ are both in $\triangle (\mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n)$.

Proof: The proof is presented in Appendix E.

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

The lower and upper bounds in Theorem 11 are tight in
at least two cases. First, consider that the algorithm un-
der study is the Gibbs algorithm, i.e., $P_{\Theta|Z}^{(Q,\lambda)}$ in (33). In
such a case, $\bar{\gamma} = \underline{\gamma} = 0$ and thus, $\overline{\mathcal{G}}(P_{\Theta|Z}^{(Q,\lambda)}, P_Z) =$
$\lambda(I(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) + L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z))$. This case is studied
in more detail in Section V-D. The second case is for
an algorithm whose output is independent of the training
dataset, i.e., an algorithm such that for all $z \in (\mathcal{X} \times \mathcal{Y})^n$,
$D(P_{\Theta|Z=z} \| P_{\Theta}) = 0$. In this case, the generalization er-
ror $\overline{\mathcal{G}}(P_{\Theta|Z}, P_Z)$ in (11) is zero. Moreover,

$$
0 = I(P_{\Theta|Z}; P_Z) \tag{92}
$$

$$
= L(P_{\Theta|Z}; P_Z) \tag{93}
$$

$$
= \iint \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\theta) dP_{\Theta|Z=z}(\theta) dP_Z(z) \\
- \iint \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\theta) dP_{\Theta}(\theta) dP_Z(z). \quad (94)
$$
Beyond the tightness of these bounds, which might be optimized by strategically choosing the value of $\gamma$ in the case of any arbitrary algorithm $P_{\Theta|Z}$, the interest of Theorem 11 lies on the following observation. The generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (71) is the sum of two quantities: (a) A first quantity that characterizes the dependence of the models on the training data via the mutual and lautum information, i.e., $\lambda(I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z))$; and (b) a second quantity that characterizes a statistical distance between the algorithm under study and a Gibbs algorithm via the expression in (83). While the first quantity (a) is always nonnegative, the second quantity (b) might be negative, zero, or positive. As shown in (94), it is zero when the algorithm under study is the Gibbs algorithm $P_{\Theta|Z}^{(Q,\lambda)}$.

Clearly, a variation in any of these quantities, (a) or (b), implies a variation on the other, and thus, cannot be separately optimized. Nonetheless, these quantities place Gibbs algorithms as natural references to evaluate the generalization capabilities of supervised machine learning algorithms. For instance, the deviation of the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) from the first quantity $\lambda(I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z))$ is upper and lower bounded by a function of the smallest and the largest log-likelihoods in the hypothesis test problem in (84). More specifically, Theorem 11, using $\gamma^* \triangleq \frac{\bar{\gamma}+\gamma}{2}$, with $\bar{\gamma}$ in (88) and $\gamma$ in (89), leads to

$$ 
\begin{aligned}
& -\lambda\left(\frac{\bar{\gamma}-\gamma}{2}\right) P_{\Theta|Z}P_Z(\mathcal{B}_{\gamma^*}^c) - \lambda\left(\frac{\bar{\gamma}-\gamma}{2}\right) P_{\Theta}P_Z(\mathcal{B}_{\gamma^*}) \\
& \le \bar{\bar{G}}(P_{\Theta|Z}, P_Z) - \lambda\left(I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z)\right) \\
& \le \lambda\left(\frac{\bar{\gamma}-\gamma}{2}\right) P_{\Theta|Z}P_Z(\mathcal{B}_{\gamma^*}) + \lambda\left(\frac{\bar{\gamma}-\gamma}{2}\right) P_{\Theta}P_Z(\mathcal{B}_{\gamma^*}^c). \quad (95)
\end{aligned}
$$

This implies that the largest deviation of the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) from the quantity $\lambda(I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z))$ is at most $\lambda(\frac{\bar{\gamma}-\gamma}{2})$, which is the difference between the lower and upper bounds in (95). This leads to the conclusion that the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) can be well approximated by $\lambda(I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z))$, when the algorithm $P_{\Theta|Z}$ is close enough to the Gibbs algorithm $P_{\Theta|Z}$. More specifically, if the absolute value of the statistical distance in (83) is smaller than or equal to some $\delta \ge 0$, that is,

$$ \left| \int \left( 1 - \frac{dP_{\Theta}}{dP_{\Theta|Z=z}}(\boldsymbol{\theta}) \right) \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\boldsymbol{\theta}) dP_{\Theta|Z} P_Z(\boldsymbol{\theta}, z) \right| \le \frac{\delta}{\lambda}, \quad (96) $$

then,

$$ \left| \bar{\bar{G}}(P_{\Theta|Z}, P_Z) - \lambda \left( I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z) \right) \right| \le \delta, \quad (97) $$

which justifies such an approximation.

### C. Connections to Euclidian Geometry

Another expression for the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11), which leads to interesting connections to Euclidian geometry is presented hereunder.

**Theorem 12:** Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that for all $z \in (\mathcal{X} \times \mathcal{Y})^n$, $P_{\Theta|Z=z} \ll Q$, for some $\sigma$-finite measure $Q \in \triangle(\mathcal{M})$. Then,

$$ \bar{\bar{G}}(P_{\Theta|Z}, P_Z) = \lambda \iint \left( D(P_{\Theta|Z=z} \| P_{\Theta|Z=u}^{(Q,\lambda)}) - D(P_{\Theta|Z=z} \| P_{\Theta|Z=u}^{(Q,\lambda)}) \right) dP_Z(u) dP_Z(z), \quad (98) $$

where the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ satisfies (33); and $\lambda \in K_Q$, with $K_Q$ in (32).

**Proof:** The proof consists in re-writing the difference $R_u(P_{\Theta|Z=z}) - R_z(P_{\Theta|Z=z})$ in (10) in terms of an algorithm-driven gap, i.e., using the functional $G$ in (20). More specifically, consider the equalities

$$ R_u(P_{\Theta|Z=z}) = G(u, P_{\Theta|Z=z}, P_{\Theta|Z=u}^{(Q,\lambda)}) + R_u(P_{\Theta|Z=u}^{(Q,\lambda)}) \quad (99) $$

and

$$ R_z(P_{\Theta|Z=z}) = G(z, P_{\Theta|Z=z}, P_{\Theta|Z=u}^{(Q,\lambda)}) + R_z(P_{\Theta|Z=u}^{(Q,\lambda)}), \quad (100) $$

that implies,

$$ 
\begin{aligned}
& R_u(P_{\Theta|Z=z}) - R_z(P_{\Theta|Z=z}) \\
&= G(u, P_{\Theta|Z=z}, P_{\Theta|Z=u}^{(Q,\lambda)}) + R_u(P_{\Theta|Z=u}^{(Q,\lambda)}) \\
&\quad - G(z, P_{\Theta|Z=z}, P_{\Theta|Z=u}^{(Q,\lambda)}) - R_z(P_{\Theta|Z=u}^{(Q,\lambda)})
\end{aligned}
\quad (101) $$

$$ 
\begin{aligned}
&= R_u(P_{\Theta|Z=u}^{(Q,\lambda)}) + \lambda D(P_{\Theta|Z=u}^{(Q,\lambda)} \| Q) \\
&\quad - R_z(P_{\Theta|Z=u}^{(Q,\lambda)}) - \lambda D(P_{\Theta|Z=u}^{(Q,\lambda)} \| Q) \\
&\quad + \lambda \left( D(P_{\Theta|Z=u}^{(Q,\lambda)} \| P_{\Theta|Z=u}^{(Q,\lambda)}) - D(P_{\Theta|Z=u}^{(Q,\lambda)} \| P_{\Theta|Z=u}^{(Q,\lambda)}) \right) \quad (102)
\end{aligned}
$$

$$ 
\begin{aligned}
&= R_u(Q) - \lambda D(Q \| P_{\Theta|Z=u}^{(Q,\lambda)}) \\
&\quad - R_z(Q) + \lambda D(Q \| P_{\Theta|Z=u}^{(Q,\lambda)}) \\
&\quad + \lambda \left( D(P_{\Theta|Z=u}^{(Q,\lambda)} \| P_{\Theta|Z=u}^{(Q,\lambda)}) - D(P_{\Theta|Z=u}^{(Q,\lambda)} \| P_{\Theta|Z=u}^{(Q,\lambda)}) \right), \quad (103)
\end{aligned}
$$

where the equality in (102) follows from [56, Theorem 1], which holds under the assumption of the theorem and [9, Lemma 3]; and the equality in (103) follows from [9, Lemma 20]. Finally, from (103) and Definition 4, it follows that

$$ 
\begin{aligned}
& \bar{\bar{G}}(P_{\Theta|Z}, P_Z) \\
&= \iint (R_u(P_{\Theta|Z=z}) - R_z(P_{\Theta|Z=z})) dP_Z(u) dP_Z(z) \quad (104)
\end{aligned}
$$

$$ 
\begin{aligned}
&= \iint (R_u(Q) - \lambda D(Q \| P_{\Theta|Z=u}^{(Q,\lambda)})) dP_Z(u) dP_Z(z) \\
&\quad - \iint (R_z(Q) - \lambda D(Q \| P_{\Theta|Z=u}^{(Q,\lambda)})) dP_Z(u) dP_Z(z) \\
&\quad + \lambda \iint \left( D(P_{\Theta|Z=u} \| P_{\Theta|Z=u}^{(Q,\lambda)}) - D(P_{\Theta|Z=u} \| P_{\Theta|Z=u}^{(Q,\lambda)}) \right) dP_Z(u) dP_Z(z) \quad (105)
\end{aligned}
$$

$$ = \lambda \iint \left( D(P_{\Theta|Z=z} \| P_{\Theta|Z=u}^{(Q,\lambda)}) \right) dP_Z(z) \quad (106) $$

$$ -D(P_{\Theta|Z=z} \| P_{\Theta|Z=u}^{(Q,\lambda)}) dP_Z(u) dP_Z(z), \quad (107) $$
which completes the proof.

Theorem 12 expresses the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) as the difference between the expectations of two relative entropies. The first relative entropy compares the algorithm $P_{\Theta|Z}$ to the Gibbs algorithm $P_{\Theta|Z}^{(Q,\lambda)}$, under the assumption that such algorithms are trained on independent datasets drawn from the same probability distribution $P_Z$. The second relative entropy compares these algorithms under the assumption that they are trained on the same dataset drawn from $P_Z$. In particular, the first relative entropy satisfies the following property.

**Lemma 13:** Consider a probability measure $P_Z \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$ and a conditional probability measure $P_{\Theta|Z} \in \Delta(\mathcal{M} | (\mathcal{X} \times \mathcal{Y})^n)$ and assume that for all $z \in (\mathcal{X} \times \mathcal{Y})^n$,

* The measures $P_{\Theta|Z=z}$ and $P_{\Theta}$ in (28) are absolutely continuous with respect to some measure $Q \in \Delta(\mathcal{M})$;

* The measure $P_{\Theta|Z=z}$ is absolutely continuous with respect to $P_{\Theta}$.

Then,

$$ \iint D(P_{\Theta|Z=u} \| P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(u) dP_Z(z) \\ = \iint (D(P_{\Theta|Z=z} \| P_{\Theta}) + D(P_{\Theta} \| P_{\Theta|Z=z}^{(Q,\lambda)})) dP_Z(z), \quad (108) $$

where the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ satisfies (33); and $\lambda \in \mathcal{K}_Q$, with $\mathcal{K}_Q$ in (32).

*Proof:* The proof follows by noticing that

$$ \begin{align*} & \iint D(P_{\Theta|Z=u} \| P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(u) dP_Z(z) \\ &= \iint \log \left( \frac{dP_{\Theta|Z=u}(\theta)}{dP_{\Theta|Z=z}^{(Q,\lambda)}} \right) dP_{\Theta|Z=u}(\theta) dP_Z(u) dP_Z(z) \\ &= \iint \log \left( \frac{dP_{\Theta}}{dP_{\Theta}^{(Q,\lambda)}}(\theta) \right) dP_{\Theta|Z=u}(\theta) dP_Z(u) dP_Z(z) \\ &\quad + \iint \log \left( \frac{dP_{\Theta|Z=u}(\theta)}{dP_{\Theta}}(\theta) \right) dP_{\Theta|Z=u}(\theta) dP_Z(u) dP_Z(z) \\ &= \iint \log \left( \frac{dP_{\Theta}}{dP_{\Theta}^{(Q,\lambda)}}(\theta) \right) dP_{\Theta}(\theta) dP_Z(z) \\ &\quad + \iint \log \left( \frac{dP_{\Theta|Z=u}(\theta)}{dP_{\Theta}}(\theta) \right) dP_{\Theta|Z=u}(\theta) dP_Z(u) \tag{109} \\ &= \iint (D(P_{\Theta} \| P_{\Theta|Z=z}^{(Q,\lambda)}) + D(P_{\Theta|Z=z} \| P_{\Theta})) dP_Z(z), \tag{110} \end{align*} $$

which completes the proof.

The converse of the Pythagorean theorem [76, Book I, Proposition 48] together with Lemma 13, lead to the geometric construction shown in Figure 1. Such interpretation becomes

<figure><img src="image_7.png" /><figcaption>Fig. 1. Geometric interpretation of Lemma 13 involving only relative entropies. Note that $\iint D(P_{\Theta|Z=z} \| P_{\Theta}) dP_Z(z) = I(P_{\Theta|Z}; P_Z)$.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 2. Geometric interpretation of Lemma 13 involving the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11).</figcaption></figure>

more interesting by noticing that, from Theorem 12, the square of the hypotenuse of the triangle in Figure 1 satisfies

$$ \iint D(P_{\Theta|Z=u} \| P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(u) dP_Z(z) = \frac{1}{\lambda} \bar{\bar{G}}(P_{\Theta|Z}, P_Z) + \int D(P_{\Theta|Z=z} \| P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(z), \quad (111) $$

which involves the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11); and the length $\sqrt{\iint D(P_{\Theta|Z=z} \| P_{\Theta}) dP_Z(z)}$ is the square root of a mutual information, i.e., $\sqrt{I(P_{\Theta|Z}; P_Z)}$. This leads to the alternative interpretation shown in Figure 2.

## D. Generalization Error of the Gibbs Algorithm

The generalization error of the Gibbs algorithm $P_{\Theta|Z}^{(Q,\lambda)}$ in (33), can be immediately obtained from Theorem 8 or Theorem 10. The following corollary formalizes this observation.
<figure><img src="image_9.png" /><figcaption>Fig. 3. Geometric interpretation of Lemma 13 for the Gibbs algorithm $P_{\Theta|Z}^{(Q,\lambda)}$ (Definition 5).</figcaption></figure>

**Corollary 14:** The generalization error $\bar{\bar{G}}(P_{\Theta|Z}^{(Q,\lambda)}, P_Z)$ in (11), with the measure $P_{\Theta|Z}^{(Q,\lambda)}$ in (33), is

$$ \bar{\bar{G}}(P_{\Theta|Z}^{(Q,\lambda)}, P_Z) = \lambda (I(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) + L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z)). \quad (112) $$

Corollary 14 has been proved numerous times before using several techniques. For instance, a proof for the case in which $Q$ is a probability measure appears in [2] and [6]. A proof for the case in which $Q$ is a probability measure and datasets are formed by independent and identically distributed data points is presented in [57]. The more general case in which $Q$ is a $\sigma$-finite measure is proved in [9]. Interestingly, independently of the choice of $\lambda$ and $Q$ in (112), such an expression does not simplify beyond the product of $\lambda$ and the sum of a mutual information and a lautum information. Figure 3 shows a geometric interpretation of Corollary 14, which is reminiscent of the Pythagorean theorem mentioned in the previous subsection.

**Theorem 12** provides another expression for the generalization error of the Gibbs algorithm $P_{\Theta|Z}^{(Q,\lambda)}$ in (33), as shown by the following corollary.

**Corollary 15:** The generalization error $\bar{\bar{G}}(P_{\Theta|Z}^{(Q,\lambda)}, P_Z)$ in (11), with the measure $P_{\Theta|Z}^{(Q,\lambda)}$ in (33), is

$$ \bar{\bar{G}}(P_{\Theta|Z}^{(Q,\lambda)}, P_Z) = \lambda \iint D(P_{\Theta|Z=u}^{(Q,\lambda)} | P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(u) dP_Z(z). \quad (113) $$

Corollary 15 shows that the generalization error of the Gibbs algorithm $P_{\Theta|Z}^{(Q,\lambda)}$ in (33) is equal to the average (expectation with respect to $P_Z P_Z$) of a pair-wise comparison via relative entropy of all the instances of such an algorithm. The expression in (113) appears to be the simplest form in which the generalization error $\bar{\bar{G}}(P_{\Theta|Z}^{(Q,\lambda)}, P_Z)$ can be written. As in the previous case, Corollary 14, the choice of $\lambda$ and $Q$ do not appear to lead to further simplification.

## VI. EXPLICIT EXPRESSIONS OBTAINED VIA THE METHOD OF DATA-DRIVEN GAPS

This section focuses on constructing novel explicit expressions for the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) by exploring different choices of the parameters $P_S$ and $\beta$ in (52). It is important to highlight that in these expressions, the central

building-block is the conditional WCDG probability measure $P_{\hat{Z}|\Theta}^{(P_S,\beta)} \in \Delta(\mathcal{X} \times \mathcal{Y}|\mathcal{M})$ in (51) (Definition 6). The first three subsections provide explicit expressions for the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ aiming at establishing connections to existing results in statistics (statistical hypothesis testing), information theory (information measures), and Euclidian geometry (Pythagorean Theorems), respectively.

## A. Connections to Hypothesis Testing

A first connection to statistical hypothesis testing is made by the following theorem.

**Theorem 16:** Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that:

(a) The probability measure $P_Z$ satisfies (22) for some $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$;

(b) For all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measures $P_{\Theta|Z=z}$ and $P_{\Theta}$ in (28) are mutually absolutely continuous;

(c) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ in (35) are mutually absolutely continuous; and

(d) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ satisfy (40) and are both mutually absolutely continuous with the probability measure $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$ in (51).

Then,

$$ \bar{\bar{G}}(P_{\Theta|Z}, P_Z) = -\beta \left( \iint \log \left( \frac{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}{dP_S}(z) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) + \iint \log \left( \frac{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}{dP_S}(z) \right) dP_Z(z) dP_{\Theta}(\theta) \right), \quad (114) $$

where the probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}$ is the WCDG probability measure in (51); and $\beta \in \mathcal{J}_{P_S}$, with $\mathcal{J}_{P_S}$ in (50).

**Proof:** Under Assumptions (a), (b), (c), and (d), Lemma 7 holds. Then, the proof follows by observing that the differences $D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}) - D(P_{Z|\Theta=\theta} \| P_S)$ and $D(P_Z \| P_S) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)})$ in (52) respectively satisfy the following equalities:

$$ D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}) - D(P_{Z|\Theta=\theta} \| P_S) = \int \left( \log \frac{dP_{Z|\Theta=\theta}}{dP_{\hat{Z}|\Theta=\theta}}(z) - \log \frac{dP_{Z|\Theta=\theta}}{dP_S}(z) \right) dP_{Z|\Theta=\theta}(z) \quad (115) $$

$$ = \int \log \frac{dP_S}{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}(z) dP_{Z|\Theta=\theta}(z) \quad (116) $$

$$ = - \int \log \frac{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}{dP_S}(z) dP_{Z|\Theta=\theta}(z), \quad (117) $$
where the equality in (116) follows from the Assumption (d) and [74, Theorem 4]; and the equality in (117) follows from [74, Theorem 5]. Similarly,

$$D(P_Z \| P_S) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}) = \int \left( \log \frac{dP_Z}{dP_S}(z) - \log \frac{dP_Z}{dP_{\hat{Z}|\Theta=\theta}}(z) \right) dP_Z(z) \quad (118)$$

$$= - \int \log \frac{dP_S}{dP_{\hat{Z}|\Theta=\theta}}(z) dP_Z(z) \quad (119)$$

$$= \int \log \frac{dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{dP_S}(z) dP_Z(z), \quad (120)$$

where the equality in (119) follows from Assumption (d) and [74, Theorem 4]; and the equality in (120) follows from [74, Theorem 5].

Plugging both (116) and (119) into (52) yields (114), which completes the proof. ■

Theorem 16 is reminiscent of Theorem 8, and thus, it admits a similar analysis in terms of mismatched hypothesis tests [59], [75]. Consider for instance a hypothesis test in which the objective is to determine whether an observed data point $z \in \Delta(\mathcal{X} \times \mathcal{Y})$ is generated from either the WCDG probability measure given a model $\theta$, i.e., the measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \in \Delta(\mathcal{X} \times \mathcal{Y})$ in (51) ($H_0$, null hypothesis); or from the reference probability measure $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$, regardless of the model $\theta$, ($H_1$, alternative hypothesis):

$$\left\{ \begin{array}{ll} H_0: & z \sim P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \\ H_1: & z \sim P_S. \end{array} \right. \quad (121)$$

As in Section V-A, the hypothesis test in (121) is said to be mismatched because none of the hypotheses matches the assumptions on the probability distribution of the observations. More specifically, the hypothesis test in (121) is studied in two different settings. First, the pair $(z, \theta)$ is assumed to be sampled from the joint probability measure $P_{Z|\Theta}P_\Theta$, with $P_\Theta$ in (28) and $P_{Z|\Theta}$ in (40). Second, the observation $(z, \theta)$ is assumed to be sampled from the product measure $P_Z P_\Theta$. Independently of such scenarios, the log-likelihood ratio to decide based upon the pair $(z, \theta)$ on the null or alternative hypothesis in (121) is $\log \frac{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{dP_S}(z)$. Essentially, given a $\eta \ge 0$, if $\log \frac{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{dP_S}(z) \ge \eta$, then the null hypothesis is accepted. Alternatively, the null hypothesis is rejected if $\log \frac{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{dP_S}(z) < \eta$. From these assumptions, the acceptance region of the null hypothesis is the set

$$C_\eta = \left\{ (z, \theta) \in (\mathcal{X} \times \mathcal{Y}) \times \mathcal{M} : \log \frac{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{dP_S}(z) \ge \eta \right\}. \quad (122)$$

That is, given an observation $(z, \theta)$, the null hypothesis is accepted if $(z, \theta) \in C_\eta$; or rejected otherwise, i.e., $(z, \theta) \in C_\eta^c$. Consider the following probabilities

$$P_{Z|\Theta} P_{\Theta}(C_{\eta}) = 1 - P_{Z|\Theta} P_{\Theta}(C_{\eta}^{c}), \quad \text{and} \quad (123)$$

$$P_Z P_\Theta(C_\eta) = 1 - P_Z P_\Theta(C_\eta^c). \quad (124)$$

The term $P_{Z|\Theta}P_\Theta(C_\eta)$ represents the probability of choosing $H_0$ under the assumption that observations $(z, \theta)$ are obtained by sampling $P_{Z|\Theta}P_\Theta$. Alternatively, the term $P_Z P_\Theta(C_\eta)$ represents the probability of choosing $H_0$ under the assumption that observations $(z, \theta)$ are sampled from $P_Z P_\Theta$. Consider also the following constants

$$\bar{\eta} \triangleq \sup \left\{ \log \frac{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{dP_S}(z) \in \mathbb{R} : (z, \theta) \in (\mathcal{X} \times \mathcal{Y}) \times \mathcal{M} \right\}. \quad (125)$$

and

$$\underline{\eta} \triangleq \inf \left\{ \log \frac{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{dP_S}(z) \in \mathbb{R} : (z, \theta) \in (\mathcal{X} \times \mathcal{Y}) \times \mathcal{M} \right\}. \quad (126)$$

The reference measure $P_S$ and the WCDG probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ in the hypothesis test in (121), are both exogenous to the study of the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11). Nonetheless, a strong connection exists as shown by the following theorem.

**Theorem 17:** Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that:

(a) The probability measure $P_Z$ satisfies (22) for some $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$;

(b) For all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measures $P_{\Theta|Z=z}$ and $P_\Theta$ in (28) are mutually absolutely continuous;

(c) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ in (35) are mutually absolutely continuous; and

(d) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ satisfy (40) and are both mutually absolutely continuous with the probability measure $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$ in (51).

Then,

$$\begin{aligned} & -\beta(\bar{\eta} - \eta) P_{Z|\Theta} P_{\Theta}(C_{\eta}) - \beta(\eta - \underline{\eta}) P_Z P_{\Theta}(C_{\eta}^{c}) \\ & \le \bar{\bar{G}}(P_{\Theta|Z}, P_Z) \le \\ & \beta(\eta - \underline{\eta}) P_{Z|\Theta} P_{\Theta}(C_{\eta}^{c}) + \beta(\bar{\eta} - \eta) P_Z P_{\Theta}(C_{\eta}), \end{aligned} \quad (127)$$

where $\eta$ satisfies

$$\underline{\eta} \le \eta \le \bar{\eta}, \quad (128)$$

and $\bar{\eta}$ and $\underline{\eta}$ are respectively defined in (125) and (126); the set $C_\eta$ is defined in (122); and the measures $P_{Z|\Theta}P_\Theta$ and $P_Z P_\Theta$ are both in $\Delta((\mathcal{X} \times \mathcal{Y}) \times \mathcal{M})$.

**Proof:** The proof follows the same steps as those in the proof of Theorem 9. ■

The upper and lower bounds in Theorem 17 can be optimized by strategically choosing the parameter $\beta$ and $P_S$ of the conditional Gibbs probability measure $P_{\hat{Z}|\Theta}^{(P_S, \beta)} \in \Delta(\mathcal{X} \times \mathcal{Y})$; and the nonnegative real $\eta$. Nonetheless, the interest of Theorem 17 lies on the fact that it unveils a connection between the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and the hypothesis test in (121), in which both hypothesis are determined by the WCDG probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ and its corresponding reference measure $P_S$.
## B. Connections to Information Measures

The following theorem is reminiscent of Theorem 10, which provides an expression for the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) involving the sum of a mutual and a lautum information between models and datapoints.

**Theorem 18:** Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that:

(a) The probability measure $P_Z$ satisfies (22) for some $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$;

(b) For all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measures $P_{\Theta|Z=z}$ and $P_{\Theta}$ in (28) are mutually absolutely continuous;

(c) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ in (35) are mutually absolutely continuous; and

(d) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ satisfy (40) and are both mutually absolutely continuous with the probability measure $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$ in (51).

Then,

$$ 
\begin{aligned}
\bar{\bar{G}}(P_{\Theta|Z}, P_Z) = & -\beta(I(P_{Z|\Theta}; P_{\Theta}) + L(P_{Z|\Theta}; P_{\Theta})) \\
& -\beta \iint \log \left( \frac{dP_{Z|\Theta=\theta}^{(P_S, \beta)}}{dP_{Z|\Theta=\theta}}(z) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \\
& +\beta \iint \log \left( \frac{dP_{Z|\Theta=\theta}^{(P_S, \beta)}}{dP_{Z|\Theta=\theta}}(z) \right) dP_Z(z) dP_{\Theta}(\theta),
\end{aligned} 
\quad (129) 
$$

where the probability measure $P_{Z|\Theta=\theta}^{(P_S, \beta)}$ is defined in (51); $\beta \in \mathcal{J}_{P_S}$, with $\mathcal{J}_{P_S}$ in (50).

*Proof:* The proof follows from Lemma 7, which holds under Assumptions (a), (b), (c), and (d). More specifically, the proof is divided into two parts. The first part focuses on the difference $\int (D(P_{Z|\Theta=\theta}\|P_S) - D(P_Z\|P_S)) dP_{\Theta}(\theta)$ in (52). Following similar steps as in the proof of Theorem 10, it can be verified that

$$ 
\begin{aligned}
& \int (D(P_{Z|\Theta=\theta}\|P_S) - D(P_Z\|P_S)) dP_{\Theta}(\theta) \\
& = I(P_{Z|\Theta}; P_{\Theta}).
\end{aligned} 
\quad (130) 
$$

Using (130) in (52) yields

$$ 
\begin{aligned}
\bar{\bar{G}}(P_{\Theta|Z}, P_Z) = & -\beta I(P_{Z|\Theta}; P_{\Theta}) + \beta \int D(P_{Z|\Theta=\theta}\|P_{Z|\Theta=\theta}^{(P_S, \beta)}) dP_{\Theta}(\theta) \\
& -\beta \int D(P_Z\|P_{Z|\Theta=\theta}^{(P_S, \beta)}) dP_{\Theta}(\theta).
\end{aligned} 
\quad (131) 
$$

The second part of the proof focuses on the term

$$ 
\begin{aligned}
& \int D(P_Z \| P_{Z|\Theta=\theta}^{(P_S, \beta)}) dP_{\Theta}(\theta) \text{ in (131), which satisfies} \\
& = \iint D(P_Z \| P_{Z|\Theta=\theta}^{(P_S, \beta)}) dP_{\Theta}(\theta) \\
& = \iint \log \left( \frac{dP_Z}{dP_{Z|\Theta=\theta}^{(P_S, \beta)}}(z) \frac{dP_{Z|\Theta=\theta}}{dP_{Z|\Theta=\theta}^{(P_S, \beta)}}(z) \right) dP_Z(z) dP_{\Theta}(\theta) \quad (132) \\
& = \iint \left( \int \log \left( \frac{dP_Z}{dP_{Z|\Theta=\theta}^{(P_S, \beta)}}(z) \right) dP_Z(z) \right) \\
& \qquad + \int \log \left( \frac{dP_{Z|\Theta=\theta}}{dP_{Z|\Theta=\theta}^{(P_S, \beta)}}(z) \right) dP_Z(z) dP_{\Theta}(\theta) \quad (133) \\
& = L(P_{Z|\Theta}; P_{\Theta}) \\
& \qquad + \iint \log \left( \frac{dP_{Z|\Theta=\theta}}{dP_{Z|\Theta=\theta}^{(P_S, \beta)}}(z) \right) dP_Z(z) dP_{\Theta}(\theta), \quad (134)
\end{aligned} 
$$

where the equality in (132) follows from [74, Theorem 3]; the equality in (133) follows from [74, Theorem 4] and Lemma 38 (in Appendix A). The proof ends by using the equality (134) into (131), which yields (129). ■

In Theorem 18, the term

$$ 
\begin{aligned}
& -\beta \iint \log \left( \frac{dP_{Z|\Theta=\theta}^{(P_S, \beta)}}{dP_{Z|\Theta=\theta}}(z) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \\
& +\beta \iint \log \left( \frac{dP_{Z|\Theta=\theta}^{(P_S, \beta)}}{dP_{Z|\Theta=\theta}}(z) \right) dP_Z(z) dP_{\Theta}(\theta),
\end{aligned} 
\quad (135) 
$$

admits a similar analysis as the term in (83) in the context of a hypothesis test. In this case, the hypothesis test consists in determining whether a datapoint $z$ has been drawn from the WCDG probability distribution $P_{Z|\Theta=\theta}^{(P_S, \beta)}$ or from the likelihood of such a datapoint $z$ given the observation of the model $\theta$. This can be formulated as follows

$$ 
\left\{ 
\begin{array}{ll}
H_0: & z \sim P_{Z|\Theta=\theta}^{(P_S, \beta)} \\
H_1: & z \sim P_{Z|\Theta=\theta},
\end{array}
\right. 
\quad (136) 
$$

and leads to conclusions similar to those in Section V-B.

## C. Connections to Euclidian Geometry

The following lemma presents an alternative expression for the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11), in terms of the variation of the functional $R_{\theta}$ in (8) due to changes of the parameter $\theta \in \mathcal{M}$.

**Lemma 19:** Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that for all $\theta \in \mathcal{M}$

(a) The probability measures $P_{\Theta}$ in (28) and the probability measure $P_{Z|\Theta=\theta}$ satisfy (35);

(b) for all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ are mutually absolutely continuous; and

(c) For all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measures $P_{\Theta|Z=z}$ and $P_{\Theta}$ in (28) are mutually absolutely continuous.
Then,

$$ \begin{aligned} & \bar{\bar{G}}(P_{\Theta|Z}, P_Z) \\ &= \iint \left( R_{\nu}(P_{Z|\Theta=\theta}) - R_{\theta}(P_{Z|\Theta=\theta}) \right) dP_{\Theta}(\nu) dP_{\Theta}(\theta), \end{aligned} \quad (137) $$

where the functional $R_{\theta}$ is defined in (8).

*Proof:* The proof follows from observing two series of equalities. The first equalities are:

$$ = \iint \left( \int L(z, \nu) dP_{Z|\Theta=\theta}(z) \right) dP_{\Theta}(\nu) dP_{\Theta}(\theta) \quad (138) $$

$$ = \iint \left( \int L(z, \nu) dP_{\Theta}(\nu) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \quad (139) $$

$$ = \iint R_z(P_{\Theta}) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \quad (140) $$

$$ = \iint R_z(P_{\Theta}) \frac{dP_{Z|\Theta=\theta}}{dP_Z}(z) dP_Z(z) dP_{\Theta}(\theta) \quad (141) $$

$$ = \int R_z(P_{\Theta}) \left( \int \frac{dP_{Z|\Theta=\theta}}{dP_Z}(z) dP_{\Theta}(\theta) \right) dP_Z(z) \quad (142) $$

$$ = \int R_z(P_{\Theta}) dP_Z(z), \quad (143) $$

where the equality in (138) follows from (8); the equality in (139) follows by exchanging the order of the integrals [63, Theorem 2.6.6]; the equality in (140) follows from (9); the equality in (141) follows from Assumption (b) and [74, Theorem 2]; the equality in (142) follows from [63, Theorem 2.6.3]; and the equality in (143) follows from [74, Theorem 10]. The second equalities are:

$$ = \iint R_{\theta}(P_{Z|\Theta=\theta}) dP_{\Theta}(\nu) dP_{\Theta}(\theta) \quad (144) $$

$$ = \iint L(z, \theta) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \quad (145) $$

$$ = \iint L(z, \theta) \frac{dP_{Z|\Theta=\theta}}{dP_Z}(z) dP_Z(z) dP_{\Theta}(\theta) \quad (146) $$

$$ = \iint L(z, \theta) \frac{dP_{Z|\Theta=\theta}}{dP_Z}(z) dP_{\Theta}(\theta) dP_Z(z) \quad (147) $$

$$ = \iint L(z, \theta) \frac{dP_{Z|\Theta=\theta}}{dP_Z}(z) \frac{dP_{\Theta}}{dP_{\Theta|Z=z}}(\theta) dP_{\Theta|Z=z}(\theta) dP_Z(z) \quad (148) $$

$$ = \iint L(z, \theta) dP_{\Theta|Z=z}(\theta) dP_Z(z) \quad (149) $$

$$ = \int R_z(P_{\Theta|Z=z}) dP_Z(z), \quad (150) $$

where the equality in (145) follows from (8); the equality in (146) follows from Assumption (b) and [74, Theorem 2]; the equality in (147) follows from [63, Theorem 2.6.6]; the equality in (148) follows from Assumption (c) and [74, Theorem 2]; the equality in (149) follows from Assumptions (b) and (c), [74, Theorem 5]; and [74, Theorem 11]; and the equality in (150) follows from (9).

From (143) and (150), it follows that

$$ = \iint \left( R_{\nu}(P_{Z|\Theta=\theta}) - R_{\theta}(P_{Z|\Theta=\theta}) \right) dP_{\Theta}(\nu) dP_{\Theta}(\theta) \quad (151) $$

$$ = \int G(z, P_{\Theta}, P_{\Theta|Z=z}) dP_Z(z) \quad (153) $$

$$ = \bar{\bar{G}}(P_{\Theta|Z}, P_Z), \quad (154) $$

where the equality in (153) follows from (20); and the equality in (154) follows from Lemma 3. This completes the proof.

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

Lemma 19 introduces an alternative expression for the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ that is reminiscent of the expression in (11). More specifically, Lemma 19 presents $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ as the expectation of the variation

$$ R_{\nu}(P_{Z|\Theta=\theta}) - R_{\theta}(P_{Z|\Theta=\theta}), $$

under the assumption that models $\nu$ and $\theta$ are independently sampled from the same probability measure $P_{\Theta} \in \Delta(\mathcal{M})$ in (28). The following theorem leverages this observation to obtain an equivalent expression for the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ that is of a similar form to the one introduced by Theorem 12.

*Theorem 20:* Consider the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) and assume that:

(a) The probability measure $P_Z$ satisfies (22) for some $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$;

(b) The probability measures $P_{\Theta}$ in (28) and the probability measure $P_{Z|\Theta=\theta}$ satisfy (35);

(c) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ are mutually absolutely continuous;

(d) For all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measures $P_{\Theta|Z=z}$ and $P_{\Theta}$ in (28) are mutually absolutely continuous; and

(e) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ satisfy (40) and are both mutually absolutely continuous with the probability measure $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$ in (51).

Then,

$$ \bar{\bar{G}}(P_{\Theta|Z}, P_Z) = \beta \iint \left( D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}) - D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}) \right) dP_{\Theta}(\nu) dP_{\Theta}(\mu), \quad (155) $$

where the measure $P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}$ is the WCDG probability measure in (51); and $\beta \in \mathcal{J}_{P_S}$, with $\mathcal{J}_{P_S}$ in (50).

*Proof:* The proof follows from Lemma 19, which holds under Assumptions (b), (c), and (d). More specifically, the proof consists of re-writing the difference $R_{\nu}(P_{Z|\Theta=\mu}) - R_{\mu}(P_{Z|\Theta=\mu})$ in (137) using the functional $G$ in (21). Under Assumption (a) and Lemma 5, note that for all $(\nu, \mu) \in \mathcal{M} \times \mathcal{M}$,

$$ R_{\nu}(P_{Z|\Theta=\mu}) = \int \ell(\nu, x, y) dP_{Z|\Theta=\mu}(x, y), \quad (156) $$
where the conditional probability measure $P_{Z|\Theta}$ satisfies (40). Hence, the following holds for all $(\boldsymbol{\mu}, \boldsymbol{\nu}) \in \mathcal{M} \times \mathcal{M}$,

$$ R_{\nu} (P_{Z|\Theta=\mu}) = G(\nu, P_{Z|\Theta=\mu}, P_{\hat{Z}|\Theta=\nu}^{(P_{S}, \beta)}) + \int \ell(\nu, x, y) dP_{\hat{Z}|\Theta=\nu}^{(P_{S}, \beta)}(x, y), (157) $$

and

$$ R_{\mu} (P_{Z|\Theta=\mu}) = G(\mu, P_{Z|\Theta=\mu}, P_{\hat{Z}|\Theta=\mu}^{(P_{S}, \beta)}) + \int \ell(\mu, x, y) dP_{\hat{Z}|\Theta=\mu}^{(P_{S}, \beta)}(x, y), (158) $$

where the functional $G$ is defined in (21). From Assumption (e) and Lemma 31 (in Section VIII), it holds that

$$ G(\nu, P_{Z|\Theta=\mu}, P_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)}) = \beta \left( D(P_{Z|\Theta=\mu} \| P_S) - D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)}) - D(P_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)} \| P_S) \right), \quad (159) $$

and

$$ G(\mu, P_{Z|\Theta=\mu}, P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}) = \beta \left( D(P_{Z|\Theta=\mu} \| P_S) - D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}) - D(P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)} \| P_S) \right). \quad (160) $$

Using these equalities, it follows from (157) and (158) that

$$ \begin{align} R_{\nu} (P_{Z|\Theta=\mu}) - R_{\mu} (P_{Z|\Theta=\mu}) & = G(\nu, P_{Z|\Theta=\mu}, P_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)}) + \int \ell(\nu, x, y) dP_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)}(x, y) \nonumber \\ & \quad - G(\mu, P_{Z|\Theta=\mu}, P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}) - \int \ell(\mu, x, y) dP_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}(x, y) \tag{161} \\ & = \beta \left( -D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)}) - D(P_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)} \| P_S) \right) \nonumber \\ & \quad - \beta \left( -D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}) - D(P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)} \| P_S) \right) \nonumber \\ & \quad + \int \ell(\nu, x, y) dP_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)}(x, y) \nonumber \\ & \quad - \int \ell(\mu, x, y) dP_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}(x, y) \tag{162} \\ & = \beta D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}) & - \beta D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)}) \nonumber \\ & + \int \ell(\nu, x, y) dP_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)}(x, y) & - \beta D(P_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)} \| P_S) \nonumber \\ & - \int \ell(\mu, x, y) dP_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}(x, y) & + \beta D(P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)} \| P_S) \tag{163} \end{align} $$

where the equality in (162) follows from both (159) and (160).

Therefore, from Lemma 19, it follows that

$$ \begin{align} \bar{G}(P_{\Theta|Z}, P_Z) &= \iint R_{\nu}(P_{Z|\Theta=\mu}) - R_{\mu}(P_{Z|\Theta=\mu}) dP_{\Theta}(\nu) dP_{\Theta}(\mu) \tag{164} \\ &= \beta \iint \left( D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\mu}^{(P_S, \beta)}) - D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)}) \right) dP_{\Theta}(\nu) dP_{\Theta}(\mu), \tag{165} \end{align} $$

which completes the proof. ■

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

Theorem 20 expresses the generalization error as the difference between the expectations of two relative entropies. The first relative entropy compares the likelihood $P_{Z|\Theta=\theta}$ to the WCDG probability measure $P_{\hat{Z}|\Theta=\theta}$, under the observation of the same model $\theta$, which is drawn from $P_{\Theta}$ in (28). The second relative entropy compares these two conditional probability measures under the case that the observed models are dawned independently from the same probability measure $P_{\Theta}$. More interestingly, the second relative entropy satisfies the following property.

**Lemma 21:** Consider a probability measure $P_Z \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$ and a conditional probability measure $P_{\Theta|Z} \in \Delta(\mathcal{M} | (\mathcal{X} \times \mathcal{Y})^n)$ and assume that:

(a) The probability measure $P_Z$ satisfies (22) for some $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$;

(b) The probability measures $P_{\Theta}$ in (28) and the probability measure $P_{Z|\Theta=\theta}$ satisfy (35);

(c) For all $\theta \in \mathcal{M}$, the probability measure $P_{Z|\Theta=\theta}$ is absolutely continuous with respect to $P_Z$; and

(d) For all $\theta \in \mathcal{M}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_Z$ satisfy (40) and are both absolutely continuous with the probability measure $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$ in (51).

Then,

$$ \iint D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\nu}^{(P_S, \beta)}) dP_{\Theta}(\nu) dP_{\Theta}(\theta) = \int \left( D(P_{Z|\Theta=\theta} \| P_Z) + D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) \right) dP_{\Theta}(\theta), $$

where the probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ is defined in (51); $\beta \in \mathcal{J}_{P_S}$, with $\mathcal{J}_{P_S}$ in (50).
*Proof:* The proof follows by noticing that

$$
\begin{align*}
& \iint D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\nu}^{(P_{S,\beta})}) dP_{\Theta}(\nu) dP_{\Theta}(\theta) \\
&= \iint \iint \log \frac{dP_{Z|\Theta=\theta}}{dP_{\hat{Z}|\Theta=\nu}^{(P_{S,\beta})}}(z) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\nu) dP_{\Theta}(\theta) \quad (166) \\
&= \iint \iint \log \frac{dP_{Z|\Theta=\theta}}{dP_{Z}}(z) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \\
&\quad + \iint \iint \log \frac{dP_{Z}}{dP_{\hat{Z}|\Theta=\nu}^{(P_{S,\beta})}}(z) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\nu) dP_{\Theta}(\theta), \quad (167) \\
&= \int D(P_{Z|\Theta=\theta} \| P_{Z}) dP_{\Theta}(\theta) \\
&\quad + \iint \iint \log \frac{dP_{Z}}{dP_{\hat{Z}|\Theta=\nu}^{(P_{S,\beta})}}(z) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\nu) dP_{\Theta}(\theta), \quad (168)
\end{align*}
$$

where the equality in (167) follows from Assumptions (a)
and (c) together with Lemma 37 (in Appendix A) and [74,
Theorem 2].

The rest of the proof follows from (168) by noticing
that

$$
\begin{align}
& \iiint \log \frac{dP_Z}{dP_{\hat{Z}|\Theta=\nu}^{(P_{S,\beta})}}(z) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\nu) dP_{\Theta}(\theta) \nonumber \\
&= \iint \log \left( \frac{dP_Z}{dP_{\hat{Z}|\Theta=\nu}^{(P_{S,\beta})}}(z) \right) \frac{dP_{Z|\Theta=\theta}}{dP_Z}(z) dP_Z(z) dP_{\Theta}(\nu) dP_{\Theta}(\theta) \tag{169} \\
&= \iint \log \left( \frac{dP_Z}{dP_{\hat{Z}|\Theta=\nu}^{(P_{S,\beta})}}(z) \right) \left( \int \frac{dP_{Z|\Theta=\theta}}{dP_Z}(z) dP_{\Theta}(\theta) \right) dP_Z(z) dP_{\Theta}(\nu) \tag{170} \\
&= \iint \log \left( \frac{dP_Z}{dP_{\hat{Z}|\Theta=\nu}^{(P_{S,\beta})}}(z) \right) dP_Z(z) dP_{\Theta}(\nu) \tag{171} \\
&= \int D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{S,\beta})}) dP_{\Theta}(\theta), \tag{172}
\end{align}
$$

where the equality in (169) follows from Assumptions (a)
and (c) together with Lemma 37 (in Appendix A) and [74,
Theorem 2]; the equality in (170) follows by exchanging the
order of the integrals [63, Theorem 2.6.6]; the equality in (171)
follows from [74, Theorem 10]. The proof is completed by
plugging (172) into (168).
■

The converse of the Pythagorean theorem [76, Book I, Propo-
sition 48] together with Lemma 21, lead to the geometric con-
struction shown in Figure 4. Note the duality between Figure 1
and Figure 4. From Theorem 20, it follows that

$$
\begin{align}
& \iint D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\nu}^{(P_{S,\beta})}) dP_{\Theta}(\nu) dP_{\Theta}(\mu) \nonumber \\
&= \int D(P_{Z|\Theta=\mu} \| P_{\hat{Z}|\Theta=\mu}^{(P_{S,\beta})}) dP_{\Theta}(\mu) - \frac{1}{\beta} \bar{G}(P_{\Theta|Z}, P_Z), \tag{173}
\end{align}
$$

<figure><img src="image_12.png" /><figcaption>Fig. 4. Geometric interpretation of Lemma 21 involving only relative entropies. Note that $\int D(P_{Z|\Theta=\theta} \| P_Z) dP_{\Theta}(\theta) = I(P_{Z|\Theta}; P_{\Theta})$.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Fig. 5. Geometric interpretation of Lemma 21 involving only relative entropies. Note that $\int D(P_{Z|\Theta=\theta} \| P_Z) dP_{\Theta}(\theta) = I(P_{Z|\Theta}; P_{\Theta})$.</figcaption></figure>

which involves the generalization error $\overline{\overline{G}}(P_{\Theta|Z}, P_Z)$ in (11).
This observation leads to the construction in Figure 5, which
exhibits a duality with Figure 2.

VII. ALGORITHM-DRIVEN GAPS

The purpose of this section is to provide explicit expressions
for the algorithm-driven gap G(z, P₁, P₂) in (20) for an
arbitrary dataset z and two arbitrary probability measures P₁
and P₂ in Δ(M). In particular, these expressions are in terms
of the Gibbs probability measure P<sub>Θ|Z=z</sub><sup>(Q,λ)</sup> in (33), which
represents a Gibbs algorithm. For the ease of presentation,
the analysis of G(z, P₁, P₂) is performed using the fact that
G(z, P₁, P₂) = G(z, P₁, P<sub>Θ|Z=z</sub><sup>(Q,λ)</sup>) - G(z, P₂, P<sub>Θ|Z=z</sub><sup>(Q,λ)</sup>).
Thus, the focus is on the gap G(z, P, P<sub>Θ|Z=z</sub><sup>(Q,λ)</sup>), for an
arbitrary measure P ∈ Δ(M).

A. *Deviations from the Gibbs Measure*

The variation or sensitivity of the functional Rz in (9) to
deviations from the probability measure P<sub>Θ|Z=z</sub><sup>(Q,λ)</sup> in (33) to
an alternative probability measure P is

$$G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)}) = R_z(P) - R_z(P_{\Theta|Z=z}^{(Q,\lambda)}), \quad (174)$$

where the functional G is defined in (20). The following theorem introduces an explicit expression for $G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)})$.

**Lemma 22 (Theorem 1 in [56]):** The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (33) satisfies for all $P \in \Delta_Q(\mathcal{M})$,

$$G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)}) = \lambda \left( D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) + D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}) - D(P \| Q) \right), (175)$$

where the functional G is defined in (20).

An interesting observation from Lemma 22 is that when the reference measure Q is a probability measure, it holds that $D(P\|Q) \ge 0$ [9, Theorem 1], which leads to the following corollary of Lemma 22.

**Corollary 23:** If Q is a probability measure, then the gap $G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)})$ in (174) satisfies

$$G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)}) \le \lambda (D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) + D(P \| P_{\Theta|Z=z}^{(Q,\lambda)})), (176)$$

with equality if and only if $D(P\|Q) = 0$.

The gap $G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)})$ in (174) is nonnegative. This follows immediately from [9, Lemma 20] and Lemma 22, as suggested in the following corollary.

**Corollary 24:** The gap $G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)})$ in (174) satisfies

$$G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)}) \ge 0 \quad (177)$$

with equality if $D(P\|P_{\Theta|Z=z}^{(Q,\lambda)}) = 0$.

## B. Priors and Postersiors

From Lemma 22, under the assumption that Q is a probability measure, it follows that

$$R_z(Q) - R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) = \lambda (D(Q \| P_{\Theta|Z=z}^{(Q,\lambda)}) + D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q)),$$

where the right-hand side is a symmetrized Kullback-Liebler divergence, also known as Jeffrey's divergence [77], between the measures Q and $P_{\Theta|Z=z}^{(Q,\lambda)}$. More importantly, when Q is a probability measure, it follows from [9, Theorem 1] that $D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \ge 0$ and $D(Q \| P_{\Theta|Z=z}^{(Q,\lambda)}) \ge 0$, which reveals the fact that the expected empirical risk induced by the Gibbs probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is smaller than or equal to the expected empirical risk induced by the reference measure Q. This observation is formalized by the following corollary of Lemma 22.

**Corollary 25:** If Q is a probability measure, then the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (33) satisfies

$$R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) \le R_z(Q), \quad (178)$$

where the function $R_z$ is defined in (9).

Note that the reference measure Q in Corollary 25 can be chosen independently of the dataset z. From this perspective,

<figure><img src="image_14.png" /><figcaption>Fig. 6. Geometric interpretation of the gap $G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)})$ in (174).</figcaption></figure>

the measure Q can be interpreted as a prior on the models, while the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ can be interpreted as a posterior once the prior Q is confronted with the training dataset z.

## C. A Geometric Interpretation

In Lemma 22, note that if Q is a probability measure, then it holds from [9, Theorem 1] that $D(P\|Q) \ge 0$, $D(P\|P_{\Theta|Z=z}^{(Q,\lambda)}) \ge 0$, and $D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \ge 0$. Thus, from (174), it holds that

$$G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D(P\|Q) = R_z(P) + \lambda D(P\|Q) - R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) \quad (179)$$

$$\ge R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) - R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) \quad (180)$$

$$= \lambda D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q), \quad (181)$$

and moreover,

$$G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D(P\|Q) = \lambda \left( D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) + D(P\|P_{\Theta|Z=z}^{(Q,\lambda)}) \right) \quad (182)$$

$$\ge \lambda D(P\|P_{\Theta|Z=z}^{(Q,\lambda)}), \quad (183)$$

where the inequality in (180) follows from (33); and the equality in (182) follows from Lemma 22.

Hence, under the assumption that the measure Q is a probability measure, the equality in (175) can be written as follows:

$$\left(\sqrt{\frac{1}{\lambda} G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)}) + D(P\|Q)}\right)^2 = \left(\sqrt{D(P_{\Theta|Z=z}^{(Q,\lambda)}\|Q)}\right)^2 + \left(\sqrt{D(P\|P_{\Theta|Z=z}^{(Q,\lambda)})}\right)^2, \quad (184)$$

which together with (182) and (183) imply that a right-angled triangle can be constructed such that the hypotenuse exhibits length $\sqrt{\frac{1}{\lambda}G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)}) + D(P\|Q)}$ and the short sides exhibit lengths $\sqrt{D(P_{\Theta|Z=z}^{(Q,\lambda)}\|Q)}$ and $\sqrt{D(P\|P_{\Theta|Z=z}^{(Q,\lambda)})}$, respectively. Figure 6 shows this interpretation of the gap $G(z, P, P_{\Theta|Z=z}^{(Q,\lambda)})$ in (174).
### D. Sensitivity from/to Arbitrary Deviations

Given two probability measures $P_1$ and $P_2$, both in $\Delta(\mathcal{M})$, and a dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$, the focus is on the variation of the functional $\mathbb{R}_z$ in (9) from $P_2$ to $P_1$. In terms of the functional $G$ in (20), such a variation is $G(z, P_1, P_2)$. The following theorem provides an exact expression for such a variation.

**Theorem 26:** If the probability measures $P_1$ and $P_2$ are both absolutely continuous with respect to the $\sigma$-finite measure $Q$ in (33), then the gap $G(z, P_1, P_2)$ in (20) satisfies

$$G(z, P_1, P_2) = \lambda \left( D(P_1 \| P_{\Theta|Z=z}^{(Q, \lambda)}) - D(P_2 \| P_{\Theta|Z=z}^{(Q, \lambda)}) + D(P_2 \| Q) - D(P_1 \| Q) \right), \quad (185)$$

where the probability measure $P_{\Theta|Z=z}^{(Q, \lambda)}$ is defined in (33).

*Proof:* The proof follows from Lemma 22 and by noticing that $G(z, P_1, P_2) = G(z, P_1, P_{\Theta|Z=z}^{(Q, \lambda)}) - G(z, P_2, P_{\Theta|Z=z}^{(Q, \lambda)})$.

In Theorem 26, as long as the probability measures $P_1$ and $P_2$ are both absolutely continuous with respect to the $\sigma$-finite measure $Q$, the reference measure $Q$ can be arbitrarily chosen. Similarly, the parameter $\lambda$ can be arbitrarily chosen within the set $\mathcal{K}_{Q,z}$ in (31). Some notions of optimality for the choice of $\lambda$ have been studied in [78]. This flexibility in the choice of these parameters is essentially because only the right-hand side of (185) depends on them. Another interesting observation is that none of the terms in the right-hand side of (185) depends simultaneously on both $P_1$ and $P_2$. These observations highlight the significant flexibility of the expression in (185) to construct closed-form expressions for the gap $G(z, P_1, P_2)$.

### E. Choice of the Reference Measure

The choice of $Q$ in (185) is subject to the constraint that both probability measures $P_1$ and $P_2$ must be absolutely continuous with respect to $Q$. From this perspective, the measure $Q$ can be seen as a free parameter, which can be strategically chosen.

1) **Probability Measures:** Two choices of $Q$, as a probability measure, for which the expression in the right-hand side of (185) significantly simplifies are $Q = P_1$ and $Q = P_2$, which leads to the following corollary of Theorem 26.

**Corollary 27:** If $P_1$ is absolutely continuous with $P_2$, then $G(z, P_1, P_2)$ in (185) satisfies:

$$G(z, P_1, P_2) = \lambda \left( D(P_1 \| P_{\Theta|Z=z}^{(P_2, \lambda)}) - D(P_1 \| P_2) - D(P_2 \| P_{\Theta|Z=z}^{(P_2, \lambda)}) \right). \quad (186)$$

Alternatively, if $P_2$ is absolutely continuous with $P_1$ then

$$G(z, P_1, P_2) = \lambda \left( D(P_1 \| P_{\Theta|Z=z}^{(P_1, \lambda)}) + D(P_2 \| P_1) - D(P_2 \| P_{\Theta|Z=z}^{(P_1, \lambda)}) \right), \quad (187)$$

where for all $i \in \{1, 2\}$, the probability measure $P_{\Theta|Z=z}^{(P_i, \lambda)}$ satisfies (33) under the assumption that $Q = P_i$.

In the case in which none of the measures is absolutely continuous with respect to its counterpart, choosing $Q$ as a convex combination of $P_1$ and $P_2$ guarantees an explicit expression for $G(z, P_1, P_2)$ in (185). The following corollary formalizes this observation.

**Corollary 28:** For all $\alpha \in (0, 1)$, $G(z, P_1, P_2)$ in (185) satisfies

$$G(z, P_1, P_2) = \lambda \left( D(P_1 \| P_{\Theta|Z=z}^{(\alpha P_1 + (1-\alpha)P_2, \lambda)}) - D(P_2 \| P_{\Theta|Z=z}^{(\alpha P_1 + (1-\alpha)P_2, \lambda)}) + D(P_2 \| \alpha P_1 + (1-\alpha)P_2) - D(P_1 \| \alpha P_1 + (1-\alpha)P_2) \right), \quad (188)$$

where the probability measure $P_{\Theta|Z=z}^{(\alpha P_1 + (1-\alpha)P_2, \lambda)}$ satisfies (33) under the assumption that $Q = \alpha P_1 + (1-\alpha)P_2$.

The measure $Q$ in (33) can also be chosen as a $\sigma$-finite measure, e.g., the counting measure or the Lebesgue measure.

2) **The Counting Measure:** Assume for instance that the set of models $\mathcal{M}$ is countable and the reference measure $Q$ is the counting measure. Under this assumption, any probability measure $P \in \Delta(\mathcal{M})$ is absolutely continuous with respect to the counting measure $Q$. The Radon-Nikodym derivative of $P$ with respect to $Q$ is the probability mass function of $P$, denoted by $p: \mathcal{M} \to [0, 1]$. Interestingly, under the current assumption, $D(P\|Q)$ is equal to negative Shannon's discrete entropy of $P$. That is, $D(P\|Q) = \sum_{\theta \in \mathcal{M}} p(\theta) \log(p(\theta)) \triangleq -H(P)$. This observation leads to the following corollary of Theorem 26.

**Corollary 29:** Let the set $\mathcal{M}$ be countable and let $Q$ in (33) be the corresponding counting measure. Then, the gap $G(z, P_1, P_2)$ in (20) satisfies

$$G(z, P_1, P_2) = \lambda \left( D(P_1 \| P_{\Theta|Z=z}^{(Q, \lambda)}) - D(P_2 \| P_{\Theta|Z=z}^{(Q, \lambda)}) - H(P_2) + H(P_1) \right), \quad (189)$$

where the probability measure $P_{\Theta|Z=z}^{(Q, \lambda)}$ is defined in (33); and the terms $H(P_1)$ and $H(P_2)$ represent Shannon's discrete entropy of the probability measures $P_1$ and $P_2$, respectively.

From [9, Theorem 3], it follows that the probability mass function of the measure $P_{\Theta|Z=z}^{(Q, \lambda)}$ in (189), denoted $p_{\lambda,z}: \mathcal{M} \to [0, 1]$, satisfies

$$p_{\lambda,z}(\theta) = \frac{d P_{\Theta|Z=z}^{(Q, \lambda)}}{dQ}(\theta) \quad (190)$$

$$= \frac{\exp(-\frac{1}{\lambda}L(z, \theta))}{\sum_{\nu \in \mathcal{M}} \exp(-\frac{1}{\lambda}L(z, \nu))}, \quad (191)$$

where the function $\frac{d P_{\Theta|Z=z}^{(Q, \lambda)}}{dQ}$ is in (33).

An important observation from Corollary 29 is that for all $i \in \{1, 2\}$, while the term $D(P_i \| P_{\Theta|Z=z}^{(Q, \lambda)})$ is convex in $P_i$, the term $H(P_i)$ is concave in $P_i$ [9, Theorem 2]. Interestingly,
the term $H(P_i)$ is independent of the dataset $z$, the choice of the loss function $\ell$ in (6), and the regularization factor $\lambda$. Moreover, while the term $D(P_i||P_{\Theta|Z=z}^{(Q,\lambda)})$ is minimized when $P_i = P_{\Theta|Z=z}^{(Q,\lambda)}$, the term $H(P_i)$ is minimized when $P_i$ is concentrated on any singleton of $\mathcal{M}$. This shows the trade-off arising in model selection between randomly choosing the models by sampling the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ and choosing a model with probability one.

3) The Lebesgue Measure: Assume that the set $\mathcal{M}$ is a subset of $\mathbb{R}^d$, and the reference measure $Q$ is the corresponding Lebesgue measure. Under these assumptions, the Radon-Nikodym derivative of a given absolutely continuous probability measure $P$ with respect to $Q$ is the probability density function of $P$, denoted by $p: \mathcal{M} \to [0,1]$. Under the current assumption, $D(P||Q)$ is equal to negative Shannon's differential entropy of $P$. That is, $D(P||Q) = \int p(\theta) \log(p(\theta)) d\theta \triangleq -h(P)$. This observation leads to the following corollary of Theorem 26.

Corollary 30: Let the set $\mathcal{M}$ be a subset of $\mathbb{R}^d$, and let $Q$ in (33) be the corresponding Lebesgue measure. Then, the gap $G(z, P_1, P_2)$ in (20) satisfies

$$G(z, P_1, P_2) = \lambda \left( D(P_1 \| P_{\Theta|Z=z}^{(Q,\lambda)}) - D(P_2 \| P_{\Theta|Z=z}^{(Q,\lambda)}) - h(P_2) + h(P_1) \right), \quad (192)$$

where the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is defined in (33); and the terms $h(P_1)$ and $h(P_2)$ represent Shannon's differential entropy of the probability measures $P_1$ and $P_2$, respectively.

From [9, Theorem 3], it follows that the probability density function of the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (192), denoted $p_{\lambda,z}: \mathcal{M} \to [0,1]$, satisfies

$$p_{\lambda,z}(\theta) = \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \quad (193)$$

$$= \frac{\exp\left(-\frac{1}{\lambda}\mathbf{L}(z, \theta)\right)}{\int \exp\left(-\frac{1}{\lambda}\mathbf{L}(z, \nu)\right) d\nu}, \quad (194)$$

where the function $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ is in (33). Despite the fact that for all $i \in \{1,2\}$, the convexity of $D(P_i||P_{\Theta|Z=z}^{(Q,\lambda)})$ and the concavity of $h(P_i)$ with respect to $P_i$ hold as in the previous case, these terms do not lead to useful interpretations as, for instance, the differential entropy $h(P_i)$ might be negative and unboundedly increase or decrease.

VIII. DATA-DRIVEN GAPS

The purpose of this section is to provide explicit expressions for the data-driven gap $G(\theta, Q_1, Q_2)$ in (21) for an arbitrary model $\theta \in \mathcal{M}$ and two arbitrary probability measures $Q_1$ and $Q_2$ in $\triangle(\mathcal{X} \times \mathcal{Y})$. Interestingly, these expressions are in terms of the a WCDG probability measure $P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}$ in (51).

A. Deviations from the WCDG probability measure

The variation or sensitivity of the functional $R_\theta$ in (8) to deviations from the WCDG probability measure $P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}$ in (51) to an alternative probability measure $P \in \triangle(\mathcal{X} \times \mathcal{Y})$ is

$$G(\theta, P, P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}) = R_{\theta}(P) - R_{\theta}(P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}), \quad (195)$$

where the functional $G$ is defined in (21). The following lemma introduces an explicit expression for $G(\theta, P, P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)})$.

Lemma 31 ([53, Theorem 6]): The probability measure $P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}$ in (51) satisfies, for all $P \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$,

$$G(\theta, P, P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}) = \beta(D(P\|P_S) - D(P\|P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}) - D(P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}\|P_S)), (196)$$

where the functional $G$ is defined in (21).

B. Sensitivity from/to Arbitrary Deviations

Given two probability measures $P_1$ and $P_2$, both in $\triangle(\mathcal{X} \times \mathcal{Y})$, and a model $\theta \in \mathcal{M}$, the focus is on the variation of the function $R_\theta$ in (8) from $P_2$ to $P_1$. In terms of the functional $G$ in (21), such a variation is $G(\theta, P_1, P_2)$. The following theorem provides an exact expression for such a variation.

Theorem 32 ([53, Theorem 8]): For all $P_1 \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$ and $P_2 \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$, and for all $\theta \in \mathcal{M}$,

$$G(\theta, P_1, P_2) = \beta \left( D(P_2 \| P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}) - D(P_1 \| P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}) - D(P_2 \| P_S) + D(P_1 \| P_S) \right), \quad (197)$$

where the functional $G$ is defined in (21); and the parameter $\beta$, the model $\theta$, and the measures $P_S$ and $P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}$ jointly satisfy (51).

C. Choice of the Reference Measure

The choice of the reference measure $P_S$ in (197) is subject to the constraint that both probability measures $P_1$ and $P_2$ must be absolutely continuous with respect to $P_S$. Despite this constraint, the reference measure $P_S$ can be seen as a free parameter, which can be strategically chosen. Two choices of $P_S$, for which the expression in the right-hand side of (197) significantly simplifies are $P_S = P_1$ and $P_S = P_2$, which leads to the following corollary of Theorem 32.

Corollary 33 ([57, Corollary 3]): If $P_1$ is absolutely continuous with $P_2$, then the gap $G(\theta, P_1, P_2)$ in (21) satisfies:

$$G(\theta, P_1, P_2) = \beta \left( D(P_2 \| P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}) - D(P_1 \| P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}) + D(P_1 \| P_2) \right). \quad (198)$$

Alternatively, if $P_2$ is absolutely continuous with $P_1$ then,

$$G(\theta, P_1, P_2) = \beta \left( D(P_2 \| P_{\tilde{Z}|\Theta=\theta}^{(P_1,\beta)}) - D(P_1 \| P_{\tilde{Z}|\Theta=\theta}^{(P_1,\beta)}) - D(P_2 \| P_1) \right), \quad (199)$$
<figure><img src="image_15.png" /><figcaption>Fig. 7. Geometric interpretation of the gap $G(\theta, P, P^{(P_S, \beta)}_{\hat{Z}|\Theta=\theta})$ in (196).</figcaption></figure>

where for all $i \in \{1, 2\}$, the probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_i, \beta)}$ satisfies (51) under the assumption that $P_S = P_i$.

Interestingly, absolute continuity of $P_1$ with respect to $P_2$ or $P_2$ with respect to $P_1$ is not necessary for obtaining an expression for the gap $G(\theta, P_1, P_2)$ in (21). In the case in which none of the measures is absolutely continuous with respect to its counterpart, choosing $P_S$ as a convex combination of $P_1$ and $P_2$ always guarantees an explicit expression for the gap $G(\theta, P_1, P_2)$. The following corollary formalizes this observation.

**Corollary 34:** For all $P_1 \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$ and $P_2 \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$, for all $\theta \in \mathcal{M}$, and for all $\alpha \in (0, 1)$,

$$ 
\begin{aligned}
& G(\theta, P_1, P_2) \\
&= \beta \left( D(P_2 \| P_{\hat{Z}|\Theta=\theta}^{(\alpha P_1 + (1-\alpha)P_2, \beta)}) - D(P_1 \| P_{\hat{Z}|\Theta=\theta}^{(\alpha P_1 + (1-\alpha)P_2, \beta)}) \right. \\
& \qquad \left. - D(P_2 \| \alpha P_1 + (1-\alpha)P_2) + D(P_1 \| \alpha P_1 + (1-\alpha)P_2) \right), (200)
\end{aligned}
$$

where the functional $G$ is defined in (21); and the parameter $\beta$, the model $\theta$, and the measures $\alpha P_1 + (1 - \alpha)P_2$ and $P_{\hat{Z}|\Theta=\theta}^{(\alpha P_1 + (1-\alpha)P_2, \beta)}$ jointly satisfy (51).

### D. A Geometric Interpretation

In Lemma 31, the reference measure $P_S$ is a probability measure. Then, from [9, Theorem 1], it follows that $D(P\|P_S) \ge 0$, $D(P\|P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) \ge 0$ and $D(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}\|P_S) \ge 0$. This observation together with (196) lead to the following inequality:

$$ 
\begin{aligned}
0 &\le D(P\|P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) + D(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}\|P_S) \\
&= D(P\|P_S) - \frac{1}{\beta}G(\theta, P, P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}).
\end{aligned}
\quad (201) $$

Moreover,

$$ 
\begin{aligned}
& \beta D(P \| P_S) - G(\theta, P, P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) \\
&= -(R_{\theta}(P) - \beta D(P \| P_S)) + R_{\theta}(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) \\
&\ge -(R_{\theta}(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) - \beta D(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}\|P_S)) \\
&\quad + R_{\theta}(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) \\
&= \beta D(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}\|P_S),
\end{aligned}
\quad (203) $$

where the equality in (202) follows from [53, Lemma 3]. Similarly,

$$ 
\begin{aligned}
& \beta D(P \| P_S) - G(\theta, P, P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) \\
&= \beta D(P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) + \beta D(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}\|P_S) \quad (204)
\end{aligned}
$$

$$ \ge \beta D(P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}), \quad (205) $$

where (204) follows from Lemma 31.

From these observations, the equality in (196) can be written as follows:

$$ 
\begin{aligned}
& \left( \sqrt{D(P \| P_S)} - \frac{1}{\beta} G(\theta, P, P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) \right)^2 \\
&= \left( \sqrt{D(P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)})} \right)^2 + \left( \sqrt{D(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S)} \right)^2.
\end{aligned}
\quad (206) $$

The equality in (206) together with the inequalities in (203) and (205) imply that a right-angled triangle can be constructed such that the hypotenuse exhibits length $\sqrt{D(P \| P_S) - \frac{1}{\beta}G(\theta, P, P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)})}$ and the short sides exhibit lengths $\sqrt{D(P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)})}$ and $\sqrt{D(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S)}$, respectively. Figure 7 shows this geometric interpretation.

## IX. CONCLUSIONS AND FINAL REMARKS

In this work, closed-form expressions for the generalization error of supervised machine learning algorithms have been derived in terms of information-theoretic measures. Two distinct classes of expressions are identified. The first class encompasses formulations involving the Gibbs algorithm, as defined by the Gibbs probability measure in Definition 5. The second class pertains to expressions incorporating the WCDG probability measure, defined in Definition 6. While the former represents a more general framework, as it imposes no specific conditions on the probability distribution of datasets, both classes offer unique and complementary insights. These insights establish connections between the generalization error and concepts such as hypothesis testing, information measures, and Euclidean geometry. However, these connections have been only briefly explored in this work, and their full potential to enhance the understanding of generalization error remains an open avenue for further research.

It is important to note that the derived expressions do not significantly simplify the numerical computation of the generalization error. This is unsurprising, as the primary goal of this study is to provide a deeper conceptual understanding of the generalization error from an information-theoretic perspective. Specifically, the established connections between the generalization error, the Gibbs algorithm, and the WCDG probability measure represent a significant advancement in this goal. Concerning the connection to the Gibbs algorithm, probably, the expression that best unveils the relevance of these findings is the one in Theorem 12. Note that such expression implies that the generalization error of an arbitrary machine learning
algorithm can be understood as a comparison, via relative entropy, of all possible instances of the algorithm under study with all possible instances of the Gibbs algorithm in two scenarios: (a) Both algorithms are trained upon the same training datasets drawn from the same probability distribution; and (b) Both algorithms are trained upon training datasets independently drawn from the same probability distribution. Alternatively, concerning the connection to the WCDG probability measure, probably, the expression that best unveils the relevance of these findings is the one in Theorem 20. The expression therein implies that the generalization error of a given machine learning algorithm consists of a comparison, via relative entropy, of all possible likelihoods on the data-points induced by the algorithm under study; and the WCDG probability measure in two scenarios: (a) both probability measures, e.g., likelihood and WCDG probability measures, are conditioned on the same model drawn from the same probability distribution; and (b) both probability measures are respectively conditioned upon models independently drawn from the same probability distribution.

Another important finding, e.g., from Theorem 10, is that the generalization error is the sum of two quantities: (a) A first quantity that characterizes the dependence of the models on the training data via the mutual and lautum information; and (b) a second quantity that characterizes a statistical distance between the algorithm under study and a Gibbs algorithm. While the first quantity (a) is always nonnegative, the second quantity (b) might be negative, zero, or positive. Clearly, a variation in any of these quantities, (a) or (b), implies a variation on the other, and thus, they cannot be separately optimized for algorithm design. Nonetheless, these quantities place Gibbs algorithms as natural references to evaluate the generalization capabilities of supervised machine learning algorithms.

## REFERENCES

[1] O. Bousquet and A. Elisseeff, "Stability and generalization," *Journal of Machine Learning Research*, vol. 2, no. 1, pp. 499–526, Mar. 2002.

[2] G. Aminian, Y. Bu, L. Toni, M. Rodrigues, and G. Wornell, "An exact characterization of the generalization error for the Gibbs algorithm," in *Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS)*, vol. 34, Dec. 2021, pp. 8106–8118.

[3] D. Russo and J. Zou, "How much does your data exploration overfit? Controlling bias via information usage," *IEEE Transactions on Information Theory*, vol. 66, no. 1, pp. 302–323, Jan. 2019.

[4] A. Xu and M. Raginsky, "Information-theoretic analysis of generalization capability of learning algorithms," in *Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS)*, vol. 30, Dec. 2017, pp. 1–10.

[5] G. Aminian, L. Toni, and M. R. Rodrigues, "Jensen-Shannon information based characterization of the generalization error of learning algorithms," in *Proceedings of the IEEE Information Theory Workshop (ITW)*, Kanazawa, Japan, Oct. 2021, pp. 1–5.

[6] G. Aminian, Y. Bu, L. Toni, M. R. D. Rodrigues, and G. W. Wornell, "Information-theoretic characterizations of generalization error for the Gibbs algorithm," *IEEE Transactions on Information Theory*, vol. 70, no. 1, pp. 632–655, Jan. 2024.

[7] G. Aminian, Y. Bu, G. W. Wornell, and M. R. Rodrigues, "Tighter expected generalization error bounds via convexity of information measures," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Aalto, Finland, Jun. 2022, pp. 2481–2486.

[8] S. M. Perlaza, G. Bisson, I. Esnaola, A. Jean-Marie, and S. Rini, "Empirical risk minimization with relative entropy regularization: Optimality and sensitivity," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Espoo, Finland, Jul. 2022, pp. 684–689.

[9] ——, "Empirical risk minimization with relative entropy regularization," *IEEE Transactions on Information Theory*, vol. 70, no. 7, pp. 5122–5161, Jul. 2024.

[10] Y. Bu, S. Zou, and V. V. Veeravalli, "Tightening mutual information-based bounds on generalization error," *IEEE Journal on Selected Areas in Information Theory*, vol. 1, no. 1, pp. 121–130, Jan. 2020.

[11] A. R. Esposito, M. Gastpar, and I. Issa, "Generalization error bounds via Rényi-, f-divergences and maximal leakage," *IEEE Transactions on Information Theory*, vol. 67, no. 8, pp. 4986–5004, May 2021.

[12] V. Vapnik, *Estimation of dependences based on empirical data*. Springer Science & Business Media, 2006.

[13] N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler, "Scale-sensitive dimensions, uniform convergence, and learnability," *Journal of the ACM*, vol. 44, no. 4, pp. 615–631, 1997.

[14] M. Mohri and A. Rostamizadeh, "Rademacher complexity bounds for non-iid processes," in *Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS)*, vol. 21, 2008.

[15] S. Shalev-Shwartz and S. Ben-David, *Understanding Machine Learning: From Theory to Algorithms*, 1st ed. New York, NY, USA: Cambridge University Press, 2014.

[16] V. Cherkassky, X. Shao, F. M. Mulier, and V. N. Vapnik, "Model complexity control for regression using VC generalization bounds," *IEEE Transactions on Neural Networks*, vol. 10, no. 5, pp. 1075–1089, Sep. 1999.

[17] S. Sachs, T. van Erven, L. Hodgkinson, R. Khanna, and U. Şimşekli, "Generalization guarantees via algorithm-dependent Rademacher complexity," in *Proceedings of the Conference on Learning Theory (COLT)*, 2023, pp. 4863–4880.

[18] P. L. Bartlett and S. Mendelson, "Rademacher and Gaussian complexities: Risk bounds and structural results," *Journal of machine learning research*, vol. 3, no. Nov. pp. 463–482, 2002.

[19] V. Koltchinskii, "Local Rademacher complexities and oracle inequalities in risk minimization," *The Annals of Statistics*, vol. 34, no. 6, pp. 2593–2656, Dec. 2006.

[20] P. L. Bartlett, O. Bousquet, and S. Mendelson, "Localized Rademacher complexities," in *Proceedings of the Conference on Learning Theory (COLT)*, 2002, pp. 44–58.

[21] J. C. Duchi and H. Namkoong, "Learning models with uniform performance via distributionally robust optimization," *The Annals of Statistics*, vol. 49, no. 3, pp. 1378–1406, 2021.

[22] D. Haussler, "Decision theoretic generalizations of the PAC model for neural net and other learning applications," *Information and computation*, vol. 100, no. 1, pp. 78–150, 1992.

[23] R. C. Williamson, A. J. Smola, and B. Schölkopf, "Entropy numbers of linear function classes," in *Proceedings of the Conference on Learning Theory (COLT)*, 2000, pp. 309–319.

[24] P. L. Bartlett, A. Montanari, and A. Rakhlin, "Deep learning: A statistical viewpoint," *Acta numerica*, vol. 30, pp. 87–201, 2021.

[25] V. Nagarajan and J. Z. Kolter, "Uniform convergence may be unable to explain generalization in deep learning," in *Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS)*, vol. 32, Vancouver, Canada, 2019.

[26] J. Jiao, Y. Han, and T. Weissman, "Dependence measures bounding the exploration bias for general measurements," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Aachen, Germany, Jun. 2017, pp. 1475–1479.

[27] H. Wang, M. Diaz, J. C. S. Santos Filho, and F. P. Calmon, "An information-theoretic view of generalization via Wasserstein distance," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Paris, France, Jul. 2019, pp. 577–581.
[28] I. Issa, A. R. Esposito, and M. Gastpar, "Strengthened information-theoretic bounds on the generalization error," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Paris, France, Jul. 2019, pp. 582–586.

[29] A. Asadi, E. Abbe, and S. Verdú, "Chaining mutual information and tightening generalization bounds," in *Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS)*, Dec. 2018, pp. 7245–7254.

[30] A. T. Lopez and V. Jog, "Generalization error bounds using Wasserstein distances," in *Proceedings of the IEEE Information Theory Workshop (ITW)*, Guangzhou, China, Nov. 2018, pp. 1–5.

[31] A. R. Asadi and E. Abbe, "Chaining meets chain rule: Multilevel entropic regularization and training of neural networks." *Journal of Machine Learning Research*, vol. 21, no. 139, pp. 1–32, Jun. 2020.

[32] H. Hafez-Kolahi, Z. Golgooni, S. Kasaei, and M. Soleymani, "Conditioning and processing: Techniques to improve information-theoretic generalization bounds," in *Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS)*, virtual conference, Dec. 2020, pp. 16457–16467.

[33] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite, "Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms," in *Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS)*, Montréal, Canada, Dec. 2018, pp. 9925–9935.

[34] B. Rodríguez Gálvez, G. Bassi, R. Thobaben, and M. Skoglund, "Tighter expected generalization error bounds via Wasserstein distance," in *Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS)*, vol. 34, New Orleans, LA, USA, Dec. 2021, pp. 19109–19121.

[35] O. Catoni, PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning, 1st ed. Beachwood, OH, USA: Institute of Mathematical Statistics Lecture Notes - Monograph Series, 2007, vol. 56.

[36] P. Viallard, M. Haddouche, U. Simsekli, and B. Guedj, "Learning via Wasserstein-based high probability generalisation bounds," in *Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS)*, vol. 36, 2024, pp. 56108–56137.

[37] P. Alquier, "User-friendly introduction to PAC-Bayes bounds," *Foundations and Trends® in Machine Learning*, vol. 17, no. 2, pp. 174–303, Jan. 2024.

[38] J. Shawe-Taylor and R. C. Williamson, "A PAC analysis of a Bayesian estimator," in *Proceedings of the 10th Annual Conference on Computational Learning Theory (COLT)*, Nashville, TN, USA, Jul. 1997, pp. 2–9.

[39] B. Guedj and L. Pujol, "Still no free lunches: The price to pay for tighter PAC-Bayes bounds," *Entropy*, vol. 23, no. 11, Nov. 2021.

[40] D. A. McAllester, "PAC-Bayesian stochastic model selection," *Machine Learning*, vol. 51, no. 1, pp. 5–21, Apr. 2003.

[41] M. Haddouche, B. Guedj, O. Rivasplata, and J. Shawe-Taylor, "PAC-Bayes unleashed: Generalisation bounds with unbounded losses," *Entropy*, vol. 23, no. 10, pp. 1–20, Oct. 2021.

[42] G. K. Dziugaite and D. M. Roy, "Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data," in *Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI)*, 2017.

[43] D. Russo and J. Zou, "Controlling bias in adaptive data analysis using information theory," in *Proceedings of the 19th International Conference on Artificial Intelligence and Statistics*, vol. 51, Cadiz, Spain, May 2016, pp. 1232–1240.

[44] B. Rodríguez-Gálvez, G. Bassi, and M. Skoglund, "Upper bounds on the generalization error of private algorithms for discrete data," *IEEE Transactions on Information Theory*, vol. 67, no. 11, pp. 7362–7379, 2021.

[45] A. R. Esposito, M. Gastpar, and I. Issa, "Robust generalization via α-mutual information," arXiv preprint arXiv:2001.06399, Jan. 2020.

[46] S. Masiha, A. Gohari, and M. H. Yassaee, "f-divergences and their applications in lossy compression and bounding generalization error," *IEEE Transactions on Information Theory*, pp. 7245–7254, Apr. 2023.

[47] F. Hellström, G. Durisi, B. Guedj, and M. Raginsky, "Generalization bounds: Perspectives from information theory and PAC-Bayes," *Foundations and Trends in Machine Learning*, vol. 18, no. 1, pp. 1–223, 2023.

[48] B. Rodríguez Gálvez, "An information-theoretic approach to generalization theory," Ph.D. dissertation, KTH Royal Institute of Technology, Apr. 2024.

[49] Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio, "Fantastic generalization measures and where to find them," in *Proceedings of the International Conference on Learning Representations*, Addis Ababa, Ethiopia, Apr. 2020.

[50] M. Gastpar, I. Nachum, J. Shafer, and T. Weinberger, "Fantastic generalization measures are nowhere to be found," in *International Conference on Learning Representations (ICLR)*, Vienna, Austria, May 2024.

[51] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals, "Understanding deep learning requires rethinking generalization," in *Proceedings of the International Conference on Learning Representations*, 2017.

[52] M. Belkin, D. Hsu, S. Ma, and S. Mandal, "Reconciling modern machine-learning practice and the classical bias-variance trade-off," *Proceedings of the National Academy of Sciences*, vol. 116, no. 32, pp. 15849–15854, 2019.

[53] X. Zou, S. M. Perlaza, I. Esnaola, E. Altman, and H. V. Poor, "The worst-case data-generating probability measure in statistical learning," *IEEE Journal on Selected Areas in Information Theory*, vol. 5, p. 175–189, Apr. 2024.

[54] X. Zou, I. Perlaza, Samir M. Esnaola, E. Altman, and H. V. Poor, "An exact characterization of the generalization error of machine learning algorithms," INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France, Tech. Rep. RR-9439, Jan. 2024.

[55] D. P. Palomar and S. Verdú, "Lautum information," *IEEE Transactions on Information Theory*, vol. 54, no. 3, pp. 964–975, Mar. 2008.

[56] S. M. Perlaza, I. Esnaola, G. Bisson, and H. V. Poor, "On the validation of Gibbs algorithms: Training datasets, test datasets and their aggregation," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Taipei, Taiwan, Jun. 2023.

[57] X. Zou, S. M. Perlaza, I. Esnaola, and E. Altman, "Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure," in *Proceedings of the AAAI Conference on Artificial Intelligence*, Vancouver, Canada, Feb. 2024.

[58] Y. Bermudez, S. M. Perlaza, I. Esnaola, and H. V. Poor, "Statistical federated learning and generalization," INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France, Tech. Rep. RR-9599, October 2025.

[59] P. Boroumand and A. G. i Fàbregas, "Mismatched binary hypothesis testing: Error exponent sensitivity," *IEEE Transactions on Information Theory*, vol. 68, no. 10, pp. 6738–6761, 2022.

[60] E. L. Lehmann, J. P. Romano, and G. Casella, *Testing statistical hypotheses*, 3rd ed. New York, NY, USA: Springer, 2005.

[61] C. E. Shannon, "A mathematical theory of communication," *The Bell System Technical Journal*, vol. 27, pp. 379–423, Jul. 1948.

[62] —, "A mathematical theory of communication," *The Bell System Technical Journal*, vol. 27, pp. 623–656, Oct. 1948.

[63] R. B. Ash and C. A. Doleans-Dade, *Probability and Measure Theory*, 2nd ed. Burlington, MA, USA: Harcourt Academic Press, 2000.

[64] F. Daunas, I. Esnaola, S. M. Perlaza, and H. V. Poor, "Equivalence of empirical risk minimization to regularization on the family of f-divergences," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Athens, Greece, July 2024, pp. 759–764.

[65] —, "Asymmetry of the relative entropy in the regularization of empirical risk minimization," *IEEE Transactions on Information Theory*, vol. 71, no. 8, pp. 6198–6226, Aug. 2025.
[66] —, “Analysis of the relative entropy asymmetry in the regularization of empirical risk minimization,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT), Taipei, Taiwan, Jun. 2023.

[67] —, “Empirical risk minimization with relative entropy regularization type-II,” INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France, Tech. Rep. RR-9508, May. 2023.

[68] —, “Empirical risk minimization with f-divergence regularization in statistical learning,” INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France, Tech. Rep. RR-9521, Oct. 2023.

[69] O. Catoni, Statistical Learning Theory and Stochastic Optimization: Ecole d'Eté de Probabilités de Saint-Flour, XXXI-2001, 1st ed. New York, NY, USA: Springer Science & Business Media, 2004, vol. 1851.

[70] L. Zdeborová and F. Krzakala, “Statistical physics of inference: Thresholds and algorithms,” Advances in Physics, vol. 65, no. 5, pp. 453–552, Aug. 2016.

[71] P. Alquier, J. Ridgway, and N. Chopin, “On the properties of variational approximations of Gibbs posteriors,” Journal of Machine Learning Research, vol. 17, no. 1, pp. 8374–8414, Dec. 2016.

[72] T. Zhang, “From $\epsilon$-entropy to KL-entropy: Analysis of minimum information complexity density estimation,” The Annals of Statistics, vol. 34, no. 5, pp. 2180–2210, Oct. 2006.

[73] —, “Information-theoretic upper and lower bounds for statistical estimation,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1307–1321, Apr. 2006.

[74] Y. Bermudez, G. Bisson, I. Esnaola, and S. M. Perlaza, “Proofs for folklore theorems on the Radon-Nikodym derivative,” INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France, Tech. Rep. RR-9591, July 2025.

[75] S. Dutta, D. Wei, H. Yueksel, P.-Y. Chen, S. Liu, and K. Varshney, “Is there a trade-off between fairness and accuracy? A perspective using mismatched hypothesis testing,” in Proceedings of the 37th International Conference on Machine Learning, vol. 119, Vienna, Austria, July 2020, pp. 2803–2813.

[76] T. L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. New York: Dover Publications, Inc., 1956.

[77] H. Jeffreys, “An invariant form for the prior probability in estimation problems,” Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, vol. 186, no. 1007, pp. 453–461, Sep. 1946.

[78] Y. Bu, “Towards optimal inverse temperature in the Gibbs algorithm,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT), Athens, Greece, July 2024, pp. 2257–2262.

## APPENDIX A
### STATISTICAL PROPERTIES OF ALGORITHMS

An algorithm $P_{\Theta|Z} \in \Delta(\mathcal{M}|(\mathcal{X} \times \mathcal{Y})^n)$ and a probability measure $P_Z \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$ determine two unique probability measures in $\Delta((\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M})$ and $\Delta(\mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n)$, respectively. Such probability measures are respectively denoted by $P_{Z,\Theta}$ and $P_{\Theta,Z}$ and for all measurable sets $\mathcal{A} \subset (\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M}$, it follows that

$$P_{Z,\Theta}(\mathcal{A}) = \int P_{\Theta|Z=z}(\mathcal{A}_z) dP_Z(z), \quad (207)$$

where $\mathcal{A}_z$ is the section of the set $\mathcal{A}$ determined by $z$, namely,

$$\mathcal{A}_z \triangleq \{\theta \in \mathcal{M} : (z, \theta) \in \mathcal{A}\}. \quad (208)$$

Alternatively, for all measurable sets $\mathcal{B} \subset \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n$, it follows that

$$P_{\Theta,Z}(\mathcal{B}) = \int P_{\Theta|Z=z}(\mathcal{B}_z) dP_Z(z), \quad (209)$$

where $\mathcal{B}_z$ is the section of the set $\mathcal{B}$ determined by $z$, namely,

$$\mathcal{B}_z \triangleq \{\theta \in \mathcal{M} : (\theta, z) \in \mathcal{B}\}. \quad (210)$$

If the sets $\mathcal{A}$ and $\mathcal{B}$ are of the form $\mathcal{A} = \mathcal{C} \times \mathcal{D}$ and $\mathcal{B} = \mathcal{D} \times \mathcal{C}$, for some $\mathcal{C} \subseteq (\mathcal{X} \times \mathcal{Y})^n$ and $\mathcal{D} \subseteq \mathcal{M}$, then, it holds that

$$P_{Z,\Theta}(\mathcal{C} \times \mathcal{D}) = \int_{\mathcal{C}} P_{\Theta|Z=z}(\mathcal{D}) dP_Z(z) = P_{\Theta,Z}(\mathcal{D} \times \mathcal{C}). \quad (211)$$

In particular, if $\mathcal{C} = (\mathcal{X} \times \mathcal{Y})^n$ in (211), then, it follows that

$$P_{Z,\Theta}((\mathcal{X} \times \mathcal{Y})^n \times \mathcal{D}) = P_{\Theta,Z}(\mathcal{D} \times (\mathcal{X} \times \mathcal{Y})^n) = P_{\Theta}(\mathcal{D}), \quad (212)$$

where the probability measure $P_{\Theta} \in \Delta(\mathcal{M})$ also satisfies (28).

Alternatively, if $\mathcal{D} = \mathcal{M}$ in (211), then, it holds that

$$P_{Z,\Theta}(\mathcal{C} \times \mathcal{M}) = P_{\Theta,Z}(\mathcal{M} \times \mathcal{C}) = P_Z(\mathcal{C}). \quad (213)$$

Hence, in the following, the measures $P_{\Theta}$ in (212) and $P_Z$ in (213) are said to be the marginals of the joint probability measures $P_{Z,\Theta}$ in (207) and $P_{\Theta,Z}$ in (209).

The instance $P_{\Theta|Z=z}$ of the algorithm $P_{\Theta|Z}$, for some dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$, can be interpreted as the posterior probability measure of the prior $P_{\Theta}$ after the observation of the dataset $z$. Let the conditional probability measure $P_{Z|\Theta} \in \Delta((\mathcal{X} \times \mathcal{Y})^n | \mathcal{M})$ be such that for all measurable sets $\mathcal{C} \subset (\mathcal{X} \times \mathcal{Y})^n$,

$$P_Z(\mathcal{C}) = \int P_{Z|\Theta=\theta}(\mathcal{C}) dP_{\Theta}(\theta), \quad (214)$$

with $P_{\Theta}$ in (212) and $P_Z$ in (213). Such a conditional probability measure $P_{Z|\Theta}$ exists and is unique almost surely with respect to $P_{\Theta}$ [63, Theorem 5.3.1]. The probability measure $P_{Z|\Theta}$ can be interpreted as the likelihood (on the datasets) induced by the posterior $P_{\Theta|Z}$ and the ground-truth probability distribution of the datasets $P_Z$. The joint probability measures $P_{Z,\Theta}$ and $P_{\Theta,Z}$ can be described via the conditional probability measure $P_{\Theta|Z}$ and the probability measure $P_Z$ as in (207) and in (209); or via the conditional probability measure $P_{Z|\Theta}$ and the probability measure $P_{\Theta}$. More specifically, for all measurable sets $\mathcal{A} \in (\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M}$, it follows that

$$P_{Z,\Theta}(\mathcal{A}) = \int P_{Z|\Theta=\theta}(\mathcal{A}_{\theta}) dP_{\Theta}(\theta), \quad (215)$$

where $\mathcal{A}_{\theta}$ is the section of the set $\mathcal{A}$ determined by $\theta$, namely,

$$\mathcal{A}_{\theta} = \{z \in (\mathcal{X} \times \mathcal{Y})^n : (z, \theta) \in \mathcal{A}\}. \quad (216)$$

Alternatively, for all measurable sets $\mathcal{B} \subset \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n$, it follows that

$$P_{\Theta,Z}(\mathcal{B}) = \int P_{Z|\Theta=\theta}(\mathcal{B}_{\theta}) dP_{\Theta}(\theta), \quad (217)$$
where the section $\mathcal{B}_{\theta}$ of the set $\mathcal{B}$ is

$$ \mathcal{B}_{\theta} = \{z \in (\mathcal{X} \times \mathcal{Y})^n : (\theta, z) \in \mathcal{B}\}. \quad (218) $$

For all measurable sets $\mathcal{A} \in (\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M}$, let the set $\hat{\mathcal{A}} \in \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n$ be

$$ \hat{\mathcal{A}} = \{(\theta, z) \in \mathcal{M} \times (\mathcal{X} \times \mathcal{Y})^n : (z, \theta) \in \mathcal{A}\}, \quad (219) $$

then, from (215) and (217), it holds that

$$ P_{Z,\Theta}(\mathcal{A}) = P_{\Theta,Z}(\hat{\mathcal{A}}). \quad (220) $$

The following lemmas, Lemma 35 and Lemma 36, present some properties of the probability measures mentioned above, which are known, but given their central roles in this work, are presented and proved using the current notation.

**Lemma 35 (Theorem 11 in [58]):** Consider the conditional probability measures $P_{\Theta|Z}$ and $P_{Z|\Theta}$; and the probability measures $P_{\Theta}$ and $P_Z$ that jointly satisfy (28) and (214). Assume that:

(a) For all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measure $P_{\Theta|Z=z}$ is absolutely continuous with respect to $P_{\Theta}$; and

(b) For all $\theta \in \mathcal{M}$, the probability measure $P_{Z|\Theta=\theta}$ is absolutely continuous with respect to $P_Z$.

Then, for all $(z, \theta) \in (\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M}$,

$$ \frac{\mathrm{d}P_{Z|\Theta=\theta}}{\mathrm{d}P_Z}(z) = \frac{\mathrm{d}P_{\Theta|Z=z}}{\mathrm{d}P_{\Theta}}(\theta), \quad (221) $$

almost surely with respect to the product measure $P_Z P_{\Theta} \in \Delta((\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M})$.

**Lemma 36 (Theorem 12 in [58]):** Consider the conditional probability measures $P_{\Theta|Z}$ and $P_{Z|\Theta}$; and the probability measures $P_{\Theta}$ and $P_Z$ that jointly satisfy (28) and (214). Assume that:

(a) For all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measure $P_{\Theta}$ is absolutely continuous with respect to $P_{\Theta|Z=z}$; and

(b) For all $\theta \in \mathcal{M}$, the probability measure $P_Z$ is absolutely continuous with respect to $P_{Z|\Theta=\theta}$.

Then, for all $(z, \theta) \in (\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M}$,

$$ \frac{\mathrm{d}P_Z}{\mathrm{d}P_{Z|\Theta=\theta}}(z) = \frac{\mathrm{d}P_{\Theta}}{\mathrm{d}P_{\Theta|Z=z}}(\theta), \quad (222) $$

almost surely with respect to the measure $P_{Z,\Theta} \in \Delta((\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M})$ in (207).

The following lemmas, Lemma 37 and Lemma 38, introduce other properties for the particular case in which $P_Z$ satisfies (22) for some $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$.

**Lemma 37:** Consider the conditional probability measure $P_{Z|\Theta}$ and the probability measure $P_Z$, both in (214). Assume that:

(a) The probability measure $P_Z$ satisfies (22) for some $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$; and

(b) For all $\theta \in \mathcal{M}$, the probability measure $P_{Z|\Theta=\theta}$ is absolutely continuous with respect to $P_Z$.

Then, for all $\theta \in \mathcal{M}$, the probability measure $P_{Z|\Theta=\theta}$ in (40) is absolutely continuous with respect to $P_Z$.

**Proof:** For all measurable sets $\mathcal{A} \subset (\mathcal{X} \times \mathcal{Y})^n$ and for all $\theta \in \mathcal{M}$,

$$ P_{Z|\Theta=\theta}(\mathcal{A}) = \int_{\mathcal{A}} \mathrm{d}P_{Z|\Theta=\theta}(z) \quad (223) $$

$$ = \int_{\mathcal{A}} \frac{\mathrm{d}P_{Z|\Theta=\theta}}{P_Z}(z) \mathrm{d}P_Z(z) \quad (224) $$

$$ = \iint_{\mathcal{A}_z} \frac{\mathrm{d}P_{Z|\Theta=\theta}}{P_Z}(z, \nu) \mathrm{d}P_{Z-1}(\nu) \mathrm{d}P_Z(z), \quad (225) $$

where the equality in (224) follows from Assumption (b) and [58, Theorem 2]; and the equality in (225) follows from Assumption (a), where the set $\mathcal{A}_z$ is the section of the set $\mathcal{A}$ determined by $z \in \mathcal{X} \times \mathcal{Y}$:

$$ \mathcal{A}_z = \{ \nu \in (\mathcal{X} \times \mathcal{Y})^{n-1} : (z, \nu) \in \mathcal{A} \}, \quad (226) $$

and the measure $P_{Z-1}$ is a product distribution in $\Delta((\mathcal{X} \times \mathcal{Y})^{n-1})$ formed by $P_Z$. That is, the product measure $P_Z P_{Z-1}$ is identical to the measure $P_Z$ in (22).

Given a measurable set $\mathcal{B} \subset \mathcal{X} \times \mathcal{Y}$, consider the set $\mathcal{A}$ that satisfies:

$$ \mathcal{A} = \mathcal{B} \times \mathcal{A}^{(2)} \times \mathcal{A}^{(3)} \times \dots \times \mathcal{A}^{(n)}, \quad (227) $$

where

$$ \mathcal{A}^{(2)} = \mathcal{A}^{(3)} = \dots = \mathcal{A}^{(n)} = \mathcal{X} \times \mathcal{Y}. \quad (228) $$

Hence, for all $z \in \mathcal{B}$, it follows that the section of the set $\mathcal{A}$ in (227) determined by $z$ is

$$ \mathcal{A}_z = (\mathcal{X} \times \mathcal{Y})^{n-1}. \quad (229) $$

Using such a fact, it follows that for the sets $\mathcal{A}$ and $\mathcal{B}$ in (227), and for all $\theta \in \mathcal{M}$,

$$ P_{Z|\Theta=\theta}(\mathcal{B}) = P_{Z|\Theta=\theta}(\mathcal{A}) \quad (230) $$

$$ = \iint_{\mathcal{A}_z} \frac{\mathrm{d}P_{Z|\Theta=\theta}}{P_Z}(z, \nu) \mathrm{d}P_{Z-1}(\nu) \mathrm{d}P_Z(z) \quad (231) $$

$$ = \iint_{\mathcal{A}_z} \frac{\mathrm{d}P_{Z|\Theta=\theta}}{P_Z}(z, \nu) \mathrm{d}P_{Z-1}(\nu) \mathrm{d}P_Z(z), \quad (232) $$

where the equality in (230) follows from (38) and the observation that under Assumption (a), Lemma 5 holds; the equality in (231) follows from (225); and the equality in (232) follows from (229).

Hence, given that the set $\mathcal{B}$ can be any measurable subset of $\mathcal{X} \times \mathcal{Y}$, the equality in (232), together with [60, Theorem 2.2.3], imply that the probability measure $P_{Z|\Theta=\theta}$ is absolutely continuous with respect to $P_Z$. Moreover, the Radon-Nikodym derivative of $P_{Z|\Theta=\theta}$ with respect to $P_Z$, denoted by $\frac{\mathrm{d}P_{Z|\Theta=\theta}}{\mathrm{d}P_Z}$, is

$$ \frac{\mathrm{d}P_{Z|\Theta=\theta}}{\mathrm{d}P_Z}(z) = \int \frac{\mathrm{d}P_{Z|\Theta=\theta}}{P_Z}(z, \nu) \mathrm{d}P_{Z-1}(\nu), \quad (233) $$

which completes the proof.

<figure><img src="image_16.png" /></figure>
**Lemma 38:** Consider the probability measure $P_Z$ and the conditional probability measure $P_{Z|\Theta}$, both in (214). Assume that:

(a) The probability measure $P_Z$ satisfies (22) for some $P_Z \in \bigtriangleup (\mathcal{X} \times \mathcal{Y})$; and

(b) For all $\theta \in \mathcal{M}$, the probability measure $P_Z$ is absolutely continuous with respect to $P_{Z|\Theta=\theta}$.

Then, for all $\theta \in \mathcal{M}$, the probability measure $P_Z$ is absolutely continuous with respect to $P_{Z|\Theta=\theta}$ in (40).

*Proof:* The proof follows along the lines of the proof of Lemma 37. For all measurable sets $A \subset (\mathcal{X} \times \mathcal{Y})^n$ and for all $\theta \in \mathcal{M}$,

$$P_Z(A) = \int_A dP_Z(z) \quad (234)$$

$$= \int_A \frac{dP_Z}{dP_{Z|\Theta=\theta}}(z) dP_{Z|\Theta=\theta}(z) \quad (235)$$

$$= \iint_{A_z} \frac{dP_Z}{dP_{Z|\Theta=\theta}}(z, \nu) dP_{Z_{-1}|Z_1=z, \Theta=\theta}(\nu) dP_{Z_1|\Theta=\theta}(z) \quad (236)$$

$$= \iint_{A_z} \frac{dP_Z}{dP_{Z|\Theta=\theta}}(z, \nu) dP_{Z_{-1}|Z_1=z, \Theta=\theta}(\nu) dP_{Z|\Theta=\theta}(z), \quad (237)$$

where the equality in (235) follows from Assumption (b) and [60, Theorem 2.2.3]; and in the equality (236), the set $A_z$ is defined in (226) and the probability measure $P_{Z_{-1}|Z_1=z, \Theta=\theta} \in \bigtriangleup ((\mathcal{X} \times \mathcal{Y})^{n-1})$ is the one that satisfies for all measurable subsets $C$ of $(\mathcal{X} \times \mathcal{Y})^{n-1}$,

$$P_{Z|\Theta=\theta}((\mathcal{X} \times \mathcal{Y}) \times C) = \int P_{Z_{-1}|Z_1=z, \Theta=\theta}(C) dP_{Z_1|\Theta=\theta}(z), \quad (238)$$

where the measure $P_{Z_1|\Theta=\theta}$ is the marginal defined in (38); and finally, the equality (237) follows from Assumption (a) and Lemma 5.

The proof continues by noticing that for a given measurable subset $B$ of $\mathcal{X} \times \mathcal{Y}$, the set $A$ in (227) satisfies for all $\theta \in \mathcal{M}$,

$$P_Z(B) = P_Z(A) \quad (239)$$

$$= \iint_{A_z} \frac{dP_Z}{dP_{Z|\Theta=\theta}}(z, \nu) dP_{Z_{-1}|Z_1=z, \Theta=\theta}(\nu) dP_{Z|\Theta=\theta}(z), \quad (240)$$

$$= \iint \frac{dP_Z}{dP_{Z|\Theta=\theta}}(z, \nu) dP_{Z_{-1}|Z_1=z, \Theta=\theta}(\nu) dP_{Z|\Theta=\theta}(z), \quad (241)$$

where the equality in (239) follows from Assumption (a); the equality in (240) follows from (237); and the equality in (241) follows from (229). Hence, given that the set $B$ can be any measurable subset of $\mathcal{X} \times \mathcal{Y}$, the equality in (241), together with [60, Theorem 2.2.3], imply that the probability measure $P_Z$ is absolutely continuous with respect to $P_{Z|\Theta=\theta}$. Moreover, the Radon-Nikodym derivative of $P_Z$ with respect to $P_{Z|\Theta=\theta}$, denoted by $\frac{dP_Z}{dP_{Z|\Theta=\theta}}$, is

$$\frac{dP_Z}{dP_{Z|\Theta=\theta}}(z) = \int \frac{dP_Z}{dP_{Z|\Theta=\theta}}(z, \nu) dP_{Z_{-1}|Z_1=z, \Theta=\theta}(\nu), \quad (242)$$

which completes the proof.

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

Lemma 37 and Lemma 38 lead to the following corollary.

*Corollary 39:* Consider the probability measure $P_Z$ and the conditional probability measure $P_{Z|\Theta}$, both in (214). Assume that:

(a) The probability measure $P_Z$ satisfies (22) for some $P_Z \in \bigtriangleup (\mathcal{X} \times \mathcal{Y})$; and

(b) For all $\theta \in \mathcal{M}$, the probability measures $P_Z$ and $P_{Z|\Theta=\theta}$ are mutually absolutely continuous.

Then, for all $\theta \in \mathcal{M}$, the probability measures $P_Z$ and $P_{Z|\Theta=\theta}$ in (40) are mutually absolutely continuous.

This appendix ends by stating the following property of the functionals $R_\theta$ in (8) and $R_z$ in (9).

**Lemma 40:** Consider the conditional probability measures $P_{\Theta|Z}$ and $P_{Z|\Theta}$; and the probability measures $P_\Theta$ and $P_Z$ that jointly satisfy (28) and (214). Then, the functionals $R_\theta$ in (8) and $R_z$ in (9), satisfy

$$\int R_z(P_\Theta) dP_Z(z) = \int R_\theta(P_Z) dP_\Theta(\theta). \quad (243)$$

Consider also the following assumptions:

(a) For all $z \in (\mathcal{X} \times \mathcal{Y})^n$, the probability measure $P_{\Theta|Z=z}$ is absolutely continuous with respect to $P_\Theta$; and

(b) For all $\theta \in \mathcal{M}$, the probability measure $P_{Z|\Theta=\theta}$ is absolutely continuous with respect to $P_Z$.

Then, the functionals $R_\theta$ and $R_z$ also satisfy:

$$\int R_z(P_\Theta|Z=z) dP_Z(z) = \int R_\theta(P_Z|\Theta=\theta) dP_\Theta(\theta). \quad (244)$$

*Proof:* The proof of (243) follows from observing that

$$\int R_z(P_\Theta) dP_Z(z) = \iint L(z, \theta) dP_\Theta(\theta) dP_Z(z) \quad (245)$$

$$= \iint L(z, \theta) dP_Z(z) dP_\Theta(\theta) \quad (246)$$

$$= \int R_\theta(P_Z) dP_\Theta(\theta). \quad (247)$$

where the equality in (245) follows from (9); the equality in (246) follows by exchanging the order of the integrals [63, Theorem 2.6.6]; and finally, the equality in (247) follows from (8). This completes the proof of (243).
The proof of (244) follows from observing that

$$ \int \mathbb{R}_z (P_{\Theta|Z=z}) dP_Z(z) \\ = \iint \mathbb{L}(z, \theta) dP_{\Theta|Z=z}(\theta) dP_Z(z) \quad (248) $$

$$ = \iint \mathbb{L}(z, \theta) \frac{dP_{\Theta|Z=z}}{dP_{\Theta}}(\theta) dP_{\Theta}(\theta) dP_Z(z) \quad (249) $$

$$ = \iint \mathbb{L}(z, \theta) \frac{dP_{\Theta|Z=z}}{dP_{\Theta}}(\theta) dP_Z(z) dP_{\Theta}(\theta) \quad (250) $$

$$ = \iint \mathbb{L}(z, \theta) \frac{dP_{Z|\Theta=\theta}}{dP_Z}(z) dP_Z(z) dP_{\Theta}(\theta) \quad (251) $$

$$ = \iint \mathbb{L}(z, \theta) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \quad (252) $$

$$ = \int \mathbb{R}_{\theta} (P_{Z|\Theta=\theta}) dP_{\Theta}(\theta), \quad (253) $$

where the equality in (248) follows from (9); the equality in (249) follows from the assumption that $P_{\Theta|Z=z}$ is absolutely continuous with $P_{\Theta}$ and [74, Theorem 2]; the equality in (250) follows by exchanging the order of the integrals [63, Theorem 2.6.6]; the equality in (251) follows from Lemma 35; the equality in (252) follows from [74, Theorem 2]; and finally, the equality in (253) follows from (8). This completes the proof of (243). ■

## APPENDIX B
PROOF OF LEMMA 3

The proof is essentially algebraic and follows from Definition 4. More specifically,

$$ \bar{G}(P_{\Theta|Z}, P_Z) = \iint (\mathbb{R}_u(P_{\Theta|Z=z}) - \mathbb{R}_z(P_{\Theta|Z=z})) dP_Z(u) dP_Z(z) \quad (254) $$

$$ = \iint \int \mathbb{L}(u, \theta) dP_{\Theta|Z=z}(\theta) dP_Z(u) dP_Z(z) \\ - \int \mathbb{R}_z(P_{\Theta|Z=z}) dP_Z(z), \quad (255) $$

where the equality in (255) follows from (9). The proof follows by noticing that

$$ \iint \int \mathbb{L}(u, \theta) dP_{\Theta|Z=z}(\theta) dP_Z(u) dP_Z(z) = \iint \left( \int \mathbb{L}(u, \theta) dP_Z(u) \right) dP_{\Theta|Z=z}(\theta) dP_Z(z) \quad (256) $$

$$ = \iint \mathbb{R}_{\theta}(P_Z) dP_{\Theta|Z=z}(\theta) dP_Z(z) \quad (257) $$

$$ = \iint \mathbb{R}_{\theta}(P_Z) \frac{dP_{\Theta|Z=z}}{dP_{\Theta}}(\theta) dP_{\Theta}(\theta) dP_Z(z) \quad (258) $$

$$ = \int \mathbb{R}_{\theta}(P_Z) \left( \int \frac{dP_{\Theta|Z=z}}{dP_{\Theta}}(\theta) dP_Z(z) \right) dP_{\Theta}(\theta) \quad (259) $$

$$ = \int \mathbb{R}_{\theta}(P_Z) dP_{\Theta}(\theta) \quad (260) $$

$$ = \int \mathbb{R}_z(P_{\Theta}) dP_Z(z), \quad (261) $$

where the equality in (256) follows by exchanging the order of the integrals [63, Theorem 2.6.6]; the equality in (257) follows

from (8); the equality in (258) follows from the assumption that $P_{\Theta|Z=z}$ is absolutely continuous with $P_{\Theta}$ and [74, Theorem 2]; the equality in (259) follows by exchanging the order of the integrals [63, Theorem 2.6.6]; the equality in (260) follows from [74, Theorem 10]; and finally, the equality in (261) follows from Lemma 40 (in Appendix A).

Plugging the equality (261) in (255) yields

$$ \bar{G}(P_{\Theta|Z}, P_Z) = \int \mathbb{R}_z (P_{\Theta}) dP_Z(z) - \int \mathbb{R}_z (P_{\Theta|Z=z}) dP_Z(z) \quad (262) $$

$$ = \int (\mathbb{R}_z (P_{\Theta}) - \mathbb{R}_z (P_{\Theta|Z=z})) dP_Z(z) \quad (263) $$

$$ = \int G(z, P_{\Theta}, P_{\Theta|Z=z}) dP_Z(z), \quad (264) $$

which completes the proof.

## APPENDIX C
PROOF OF LEMMA 6

The proof is essentially algebraic and follows from Definition 4. More specifically,

$$ \bar{G}(P_{\Theta|Z}, P_Z) = \iint (\mathbb{R}_u(P_{\Theta|Z=z}) - \mathbb{R}_z(P_{\Theta|Z=z})) dP_Z(u) dP_Z(z) \quad (265) $$

$$ = \iint \int (\mathbb{L}(u, \theta) - \mathbb{L}(z, \theta)) dP_{\Theta|Z=z}(\theta) dP_Z(u) dP_Z(z) \quad (266) $$

$$ = \iint \left( \int \mathbb{L}(u, \theta) dP_Z(u) \right) dP_{\Theta|Z=z}(\theta) dP_Z(z) \\ - \iint \mathbb{L}(z, \theta) dP_{\Theta|Z=z}(\theta) dP_Z(z), \quad (267) $$

$$ = \iint (\mathbb{R}_{\theta}(P_Z) - \mathbb{L}(z, \theta)) dP_{\Theta|Z=z}(\theta) dP_Z(z), \quad (268) $$

where the equality in (266) follows from (9); the equality in (267) follows by exchanging the order of the integrals [63, Theorem 2.6.6]; and the equality in (268) follows from (8).

The proof continues by noticing that:

$$ \iint \mathbb{R}_{\theta}(P_Z) dP_{\Theta|Z=z}(\theta) dP_Z(z) = \iint \mathbb{R}_{\theta}(P_Z) \frac{dP_{\Theta|Z=z}}{dP_{\Theta}}(\theta) dP_{\Theta}(\theta) dP_Z(z) \quad (269) $$

$$ = \int \mathbb{R}_{\theta}(P_Z) \left( \int \frac{dP_{\Theta|Z=z}}{dP_{\Theta}}(\theta) dP_Z(z) \right) dP_{\Theta}(\theta) \quad (270) $$

$$ = \int \mathbb{R}_{\theta}(P_Z) dP_{\Theta}(\theta) \quad (271) $$

$$ = \iint \left( \frac{1}{n} \sum_{t=1}^{n} \ell(x_t, y_t, \theta) \right) dP_Z(z) dP_{\Theta}(\theta) \quad (272) $$

$$ = \frac{1}{n} \sum_{t=1}^{n} \iint (\ell(x, y, \theta)) dP_Z(x, y) dP_{\Theta}(\theta) \quad (273) $$

$$ = \iint (\ell(x, y, \theta)) dP_Z(x, y) dP_{\Theta}(\theta), \quad (274) $$
where the equality (269) follows from Assumption (b) and [74, Theorem 2]; the equality in (270) follows by exchanging the order of the integrals [63, Theorem 2.6.6]; the equality in (271) follows from [74, Theorem 10]; the equality in (272) follows from (7) and (8); and finally, the equality in (273) follows from [63, Theorem 1.6.3].

Finally, note that

$$= \iint L(z, \theta) dP_{\Theta|Z=z}(\theta) dP_Z(z) \qquad (275)$$

$$= \iint L(z, \theta) \frac{dP_{\Theta|Z=z}}{dP_{\Theta}}(\theta) dP_Z(z) dP_{\Theta}(\theta) \qquad (276)$$

$$= \iint L(z, \theta) \frac{dP_{\Theta|Z=z}}{dP_{\Theta}}(\theta) \frac{dP_Z}{dP_{Z|\Theta=\theta}}(z) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \qquad (277)$$

$$= \iint L(z, \theta) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \qquad (278)$$

$$= \iint \left( \frac{1}{n} \sum_{t=1}^{n} \ell(x_t, y_t, \theta) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \qquad (279)$$

$$= \frac{1}{n} \sum_{t=1}^{n} \iint \ell(x, y, \theta) dP_{Z_t|\Theta=\theta}(x, y) dP_{\Theta}(\theta) \qquad (280)$$

$$= \iint \ell(x, y, \theta) dP_{Z|\Theta=\theta}(x, y) dP_{\Theta}(\theta), \qquad (281)$$

where the equality (275) follows from Assumption (b) and [74, Theorem 2]; the equality in (276) follows by exchanging the order of the integrals [63, Theorem 2.6.6]; the equality (277) follows from Assumption (c) and [74, Theorem 2]; the equality in (278) follows from Lemma 35 and Lemma 36 (in Appendix A); and [74, Theorem 5], which imply that for all $(z, \theta) \in (\mathcal{X} \times \mathcal{Y})^n \times \mathcal{M}$,

$$\frac{dP_{\Theta|Z=z}}{dP_{\Theta}}(\theta) \frac{dP_Z}{dP_{Z|\Theta=\theta}}(z)=1; \qquad (282)$$

the equality in (279) follows from (7); the equality in (280) follows from [63, Theorem 1.6.3]; and finally, the equality in (281) follows from Lemma 5, which holds under Assumption (a).

The proof ends by using (274) and (281) in (268), which yields

$$\bar{\bar{G}}(P_{\Theta|Z}, P_Z) = \iint \ell(x, y, \theta) dP_Z(x, y) dP_{\Theta}(\theta) - \iint \ell(x, y, \theta) dP_{Z|\Theta=\theta}(x, y) dP_{\Theta}(\theta) \qquad (283)$$

$$= \int G(\theta, P_Z, P_{Z|\Theta=\theta}) dP_{\Theta}(\theta), \qquad (284)$$

where the equality in (284) follows from (21). This completes the proof.

## APPENDIX D
### PROOF OF THEOREM 9

The proof follows along the lines of the proof of [58, Theorem 18]. From Theorem 8, it follows that the generalization error $\bar{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (11) satisfies:

$$\bar{\bar{G}}(P_{\Theta|Z}, P_Z) = \lambda \int \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} \right) dP_{\Theta|Z} P_Z(\theta, z) \qquad (285)$$

$$-\lambda \int \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} \right) dP_{\Theta} P_Z(\theta, z) \qquad (285)$$

$$= \lambda \int_{A_{\gamma}} \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} \right) dP_{\Theta|Z} P_Z(\theta, z) \qquad (286)$$

$$+\lambda \int_{A_{\gamma}^{c}} \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} \right) dP_{\Theta|Z} P_Z(\theta, z) \qquad (286)$$

$$-\lambda \int_{A_{\gamma}} \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} \right) dP_{\Theta} P_Z(\theta, z) \qquad (286)$$

$$-\lambda \int_{A_{\gamma}^{c}} \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} \right) dP_{\Theta} P_Z(\theta, z) \qquad (286)$$

$$\geq \lambda\gamma P_{\Theta|Z} P_Z(A_{\gamma}) + \lambda\bar{\gamma} P_{\Theta|Z} P_Z(A_{\gamma}^c) \qquad (287)$$

$$-\lambda\bar{\gamma} P_{\Theta} P_Z(A_{\gamma}) - \lambda\gamma P_{\Theta} P_Z(A_{\gamma}^c) \qquad (288)$$

$$= \lambda (\bar{\gamma} - \gamma) P_{\Theta|Z} P_Z(A_{\gamma}^c) + \lambda (\gamma - \bar{\gamma}) P_{\Theta} P_Z(A_{\gamma}), \qquad (289)$$

where the inequality in (288) follows from the definition of the set $A_{\gamma}$ in (64); and the extrema in (67) and (68). Finally, the equality in (289) follows from (65) and (66). This completes the proof of the lower bound.

The proof of the upper bound follows a similar argument. From the equality in (286), the following holds,

$$\bar{\bar{G}}(P_{\Theta|Z}, P_Z) \leq \lambda\bar{\gamma} P_{\Theta|Z} P_Z(A_{\gamma}) + \lambda\gamma P_{\Theta|Z} P_Z(A_{\gamma}^c) \qquad (290)$$

$$-\lambda\gamma P_{\Theta} P_Z(A_{\gamma}) - \lambda\bar{\gamma} P_{\Theta} P_Z(A_{\gamma}^c) = \lambda(\bar{\gamma} - \gamma) P_{\Theta|Z} P_Z(A_{\gamma}) + \lambda(\gamma - \bar{\gamma}) P_{\Theta} P_Z(A_{\gamma}^c), \qquad (291)$$

where the inequality in (290) follows from the definition of the set $A_{\gamma}$ in (64); and the extrema in (67) and (68). Finally, the equality in (291) follows from (65) and (66). This completes the proof of the upper bound.

## APPENDIX E
### PROOF OF THEOREM 11

The proof follows along the lines of the proof of [58, Theorem 18]. From Theorem 10, it follows that the dif-
ference $\overline{\mathcal{G}}(P_{\Theta|Z}, P_Z) - \lambda(I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z))$ satisfies:

$$ \begin{aligned} & \overline{\mathcal{G}}(P_{\Theta|Z}, P_Z) - \lambda(I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z)) \\ &= \lambda \int \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\theta) \right) dP_{\Theta|Z}P_Z(\theta, z) \end{aligned} \quad (292) $$

$$ -\lambda \int \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\theta) \right) dP_{\Theta}P_Z(\theta, z) \quad (293) $$

$$ \begin{aligned} & = \lambda \int_{\mathcal{B}_{\gamma}} \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\theta) \right) dP_{\Theta|Z}P_Z(\theta, z) \\ & \quad + \lambda \int_{\mathcal{B}_{\gamma}^c} \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\theta) \right) dP_{\Theta|Z}P_Z(\theta, z) \\ & \quad - \lambda \int_{\mathcal{B}_{\gamma}} \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\theta) \right) dP_{\Theta}P_Z(\theta, z) \\ & \quad - \lambda \int_{\mathcal{B}_{\gamma}^c} \left( \log \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta|Z=z}}(\theta) \right) dP_{\Theta}P_Z(\theta, z) \end{aligned} \quad (294) $$

$$ \geq \lambda\gamma P_{\Theta|Z}P_Z(\mathcal{B}_{\gamma}) + \lambda\bar{\gamma} P_{\Theta|Z}P_Z(\mathcal{B}_{\gamma}^c) \quad (295) $$

$$ -\lambda\bar{\gamma} P_{\Theta}P_Z(\mathcal{B}_{\gamma}) - \lambda\gamma P_{\Theta}P_Z(\mathcal{B}_{\gamma}^c) \quad (296) $$

$$ = \lambda(\gamma - \bar{\gamma}) P_{\Theta|Z}P_Z(\mathcal{B}_{\gamma}^c) + \lambda(\gamma - \bar{\gamma}) P_{\Theta}P_Z(\mathcal{B}_{\gamma}), \quad (297) $$

where the inequality in (296) follows from the definition of the set $\mathcal{B}_{\gamma}$ in (85); and the extrema in (88) and (89). Finally, the equality in (297) follows from (86) and (87). This completes the proof of the lower bound. The proof of the upper bound follows a similar argument. From the equality in (294), the following holds,

$$ \begin{aligned} & \overline{\mathcal{G}}(P_{\Theta|Z}, P_Z) \\ & \leq \lambda\bar{\gamma} P_{\Theta|Z}P_Z(\mathcal{B}_{\gamma}) + \lambda\gamma P_{\Theta|Z}P_Z(\mathcal{B}_{\gamma}^c) \\ & \quad -\lambda\gamma P_{\Theta}P_Z(\mathcal{B}_{\gamma}) - \lambda\bar{\gamma} P_{\Theta}P_Z(\mathcal{B}_{\gamma}^c) \end{aligned} \quad (298) $$

$$ = \lambda(\bar{\gamma} - \gamma) P_{\Theta|Z}P_Z(\mathcal{B}_{\gamma}) + \lambda(\gamma - \bar{\gamma}) P_{\Theta}P_Z(\mathcal{B}_{\gamma}^c), \quad (299) $$

where the inequality in (298) follows from the definition of the set $\mathcal{B}_{\gamma}$ in (85); and the extrema in (88) and (89). Finally, the equality in (299) follows from (86) and (87). This completes the proof of the upper bound.