informatics mathematics
Inria

# An Exact Characterization of the Generalization Error of Machine Learning Algorithms

Xinying Zou, Samir M. Perlaza, Iñaki Esnaola, Eitan Altman, and H. Vincent Poor

## RESEARCH REPORT

Nº 9539

February 2024

Project-Team NEO

ISSN 0249-6399 ISRN INRIA/RR-9539-FR+ENG
<figure><img src="image_1.png" /></figure>
<figure><img src="image_2.png" /></figure>

# An Exact Characterization of the Generalization Error of Machine Learning Algorithms

Xinying Zou, Samir M. Perlaza, Iñaki Esnaola, Eitan Altman, and H. Vincent Poor

Project-Team NEO

Research Report n° 9539 — version 3 — initial version February 2024 — revised version May 2024 — 80 pages

RESEARCH CENTRE
SOPHIA ANTIPOLIS – MÉDITERRANÉE

2004 route des Lucioles - BP 93
06902 Sophia Antipolis Cedex

<footnote>Xinying Zou, Samir M. Perlaza, and Eitan Altman are with INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis 06902, France. Iñaki Esnaola is with the Department of Automatic Control and Systems Engineering, University of Sheffield, Sheffield S1 3JD, UK. H. Vincent Poor, Samir M. Perlaza, and Iñaki Esnaola are with the Department of Electrical and Computer Engineering, Princeton University, Princeton NJ 08544, USA. Samir M. Perlaza is also with the GAATI Laboratory at the Université de la Polynésie Française, Faaa 98702, French Polynesia. Eitan Altman is also with the Laboratoire d'Informatique d'Avignon (LIA), Université d'Avignon, France.</footnote>
**Abstract:** The worst-case data-generating (WCDG) probability measure is introduced as a tool for characterizing the generalization capabilities of machine learning algorithms. Such a WCDG probability measure is shown to be the unique solution to two different optimization problems: (a) The maximization of the expected loss over the set of probability measures on the datasets whose relative entropy with respect to a reference measure is not larger than a given threshold; and (b) The maximization of the expected loss with regularization by relative entropy with respect to the reference measure. Such a reference measure can be interpreted as a prior on the datasets. The WCDG cumulants are finite and bounded in terms of the cumulants of the reference measure. To analyze the concentration of the expected empirical risk induced by the WCDG probability measure, the notion of $(\epsilon, \delta)$-robustness of models is introduced. Closed-form expressions are presented for the sensitivity of the expected loss for a fixed model. These results lead to a novel expressions for the generalization error of arbitrary machine learning algorithms. These expressions can be broadly divided into two classes. The first one involves a WCDG probability measure, while the second one involves a Gibbs algorithm. This finding reveals that an exploration into the generalization error of the Gibbs algorithm facilitates the derivation of overarching insights applicable to any machine learning algorithm.

**Key-words:** Statistical Machine Learning, Generalization Error, and Gibbs Algorithm
Une caractérisation exacte de l'erreur de
généralisation pour des algorithmes
d'apprentissage automatique

**Résumé** : La mesure de probabilité de génération de données dans le pire des cas (GDPC) est présentée comme un outil permettant de caractériser les capacités de généralisation des algorithmes d'apprentissage automatique. Une telle mesure de probabilité de GDPC s'avère être la solution unique à deux problèmes d'optimisation différents : (a) La maximisation de la perte (ou risque) espérée sur l'ensemble des mesures de probabilité des données dont l'entropie relative par rapport à une mesure de référence n'est pas supérieure à un seuil donné ; et (b) La maximisation de la perte espérée avec une régularisation par entropie relative par rapport à la mesure de référence. Une telle mesure de référence peut être interprétée comme un à priori sur les données. Les cumulants de la perte espérée lorsque les données sont obtenues en échantillonnant la mesure de GDPC s'avèrent majorés et minorés en termes des cumulants de la mesure de référence. Des expressions sous forme fermée sont présentées pour la sensibilité de la perte espérée pour un modèle fixe. Ces outils aboutissent à la caractérisation des nouvelles expressions pour l'erreur de généralisation applicables à n'importe quel algorithme d'apprentissage automatique. Ces expressions peuvent être globalement divisées en deux classes. La première implique une mesure de probabilité GDPC, tandis que la seconde implique un algorithme de Gibbs. Cette découverte révèle qu'une exploration de l'erreur de généralisation de l'algorithme de Gibbs facilite la dérivation de conclusions globales applicables à tout algorithme d'apprentissage automatique.

**Mots-clés** : Apprentissage Statistique, Error de généralisation, et algorithme de Gibbs.
Contents

<table><tr><td>1</td><td>Introduction</td><td>6</td></tr><tr><td>1.1</td><td>Existing Results</td><td>7</td></tr><tr><td>1.2</td><td>Contributions</td><td>8</td></tr><tr><td>1.3</td><td>Notation</td><td>9</td></tr><tr><td>2</td><td>Problem Formulation</td><td>9</td></tr><tr><td>3</td><td>The Worst-Case Data-Generating Probability Measure</td><td>10</td></tr><tr><td>3.1</td><td>General Discussion</td><td>10</td></tr><tr><td>3.2</td><td>Relative Entropy Case</td><td>12</td></tr><tr><td>3.3</td><td>Choice of the Reference Measure</td><td>16</td></tr><tr><td>4</td><td>Cumulants of the Expected Loss</td><td>17</td></tr><tr><td>5</td><td>(ε, δ)-Robustness and Algorithm Design</td><td>20</td></tr><tr><td>6</td><td>Sensitivity of the Expected Loss</td><td>22</td></tr><tr><td>6.1</td><td>Sensitivity of the Empirical-Risk</td><td>24</td></tr><tr><td>6.2</td><td>Analysis of the Generalization Gap</td><td>26</td></tr><tr><td>7</td><td>Generalization Error</td><td>27</td></tr><tr><td>7.1</td><td>Generalization Error of the Gibbs Algorithm</td><td>29</td></tr><tr><td>7.2</td><td>Expressions Involving a WCDG Probability Measure</td><td>31</td></tr><tr><td>7.3</td><td>Expressions Involving a Gibbs Algorithm</td><td>36</td></tr><tr><td>8</td><td>Conclusions and Final Remarks</td><td>37</td></tr><tr><td colspan="2">Appendices</td><td>38</td></tr><tr><td>A</td><td>Proof of Lemma 1</td><td>38</td></tr><tr><td>B</td><td>Proof of Lemma 2</td><td>40</td></tr><tr><td>C</td><td>Proof of Theorem 1</td><td>40</td></tr><tr><td>D</td><td>Proof of Lemma 3</td><td>44</td></tr><tr><td>E</td><td>Proof of Lemma 4</td><td>45</td></tr><tr><td>F</td><td>Proof of Lemma 5</td><td>46</td></tr><tr><td>G</td><td>Proof of Theorem 2</td><td>50</td></tr><tr><td>H</td><td>Proof of Theorem 3</td><td>51</td></tr><tr><td>I</td><td>Proof of Lemma 6</td><td>52</td></tr></table>
<table><tr><td>J</td><td>Proof of Theorem 4</td><td>52</td></tr><tr><td>K</td><td>Proof of Theorem 5</td><td>56</td></tr><tr><td>L</td><td>Proof of Theorem 6</td><td>57</td></tr><tr><td>M</td><td>Proof of Theorem 7</td><td>58</td></tr><tr><td>N</td><td>Proof of Theorem 8</td><td>62</td></tr><tr><td>O</td><td>Proof for Lemma 7</td><td>62</td></tr><tr><td>P</td><td>Proof of Theorem 11</td><td>62</td></tr><tr><td>Q</td><td>Proof of Theorem 12</td><td>63</td></tr><tr><td>R</td><td>Proof of Lemma 11</td><td>63</td></tr><tr><td></td><td>R.1 Preliminaries</td><td>63</td></tr><tr><td></td><td>R.2 The Proof</td><td>67</td></tr><tr><td>S</td><td>Proof of Lemma 12</td><td>70</td></tr><tr><td>T</td><td>Proof of Theorem 13</td><td>71</td></tr><tr><td></td><td>T.1 Preliminaries</td><td>71</td></tr><tr><td></td><td>T.2 The Proof</td><td>72</td></tr></table>
# 1 Introduction

The problem of supervised machine learning is often formulated as an empirical risk minimization (ERM) problem in which the optimization domain is a set of models [1]. This formulation is based on the observation that the empirical risk is the expectation of the loss function with respect to the empirical probability measure induced by the training dataset. See for instance, Lemma 7. This empirical measure is known in the realm of information theory as a type [2] (see Definition 3). If the ground-truth data-generating (GTDG) probability measure were available, optimal models would be the minimizers of the expectation of the loss with respect to the GTDG probability measure, also known as the *true risk* or *population risk* [1]. From this perspective, the type induced by the training dataset is a replacement for the GTDG probability measure. That is, models are chosen as the minimizers of the empirical risk instead of minimizers of the true risk. Interestingly, large datasets might lead to types that are sufficiently *close* to the GTDG probability measure with high probability [3]. Typically, such a closeness is often measured in terms of a *statistical distance*, e.g., the relative entropy of the type with respect to the GTDG probability measure.

The driving idea in this work is that the GTDG probability measure is likely to be within a *neighbourhood* of the type induced by the training dataset. Side information might also lead to a *prior* on the data, and thus, the GTDG probability measure is also likely to be within a *neighbourhood* of such a prior. From this perspective, one can adopt a *reference measure*, which can be the type, a prior, or a mixture of both, and form a unique *neighbourhood* around such a *reference measure*. This *neighbourhood* includes all probability measures on the datasets that are at a *statistical distance* smaller than or equal to a given threshold. A robust choice of models is choosing them as the minimizers of the expectation of the loss with respect to the worst-case data-generating (WCDG) probability measure within such a neighbourhood. In this case, the WCDG probability measure is assumed to be the measure that maximizes the expectation of the loss for a fixed model. This problem formulation is a distributionally robust optimization (DRO) problem [4,5] in which the *statistical distance* might be the relative entropy as in [6], a Wasserstein distance as in [7,8], an *f*-divergence as in [9,10], among others. This problem can also be formulated via the maximum entropy principle [11,12] as in [13,14]. Every choice of *statistical distance* leads to a WCDG probability measure with particular properties.

When the *statistical distance* is the relative entropy, the resulting WCDG probability measure exhibits numerous properties that are central in the analysis of key generalization metrics, namely, the generalization gap (GG); the expected generalization gap (EGG); and the doubly-expected generalization gap (D-EGG). In the literature, the D-EGG is also referred to as the *generalization error* (GE). The GG is calculated for a specific model and training dataset as the difference between the true risk and the empirical risk induced by the model on such a training dataset. While the GG does not provide a generalization guarantee for a given model, it allows studying the impact of the training
dataset on the generalization capabilities. This observation is central to the
results presented in this work. When models are chosen by sampling a proba-
bility measure conditioned on the training dataset, the EGG is the expectation
of the GG with respect to such a probability measure. This probability mea-
sure is often referred to as the statistical learning algorithm. In this setting,
the dependence of the EGG on the training dataset is twofold. Firstly, via the
algorithm, which depends on the training dataset; and secondly, via the GG,
which involves the calculation of the empirical risk on the training dataset. The
D-EGG is the expectation of the EGG with respect to the GTDG probability
measure.

1.1 Existing Results

The GG, EGG, and D-EGG (or GE) are central performance metrics for the
analysis of the generalization capabilities of machine learning algorithms, see
for instance [15–19] and [20]. In particular, the D-EGG characterizes the ability
of the learning algorithm to correctly find patterns in datasets that are not
available during the training stage. Closed-form expressions for the EGG are
only known for the Gibbs algorithm in the case in which the reference measure is
a probability measure [15]; and for the case in which the reference measure is a σ-
finite measure [21]. In the case of other algorithms, the D-EGG is characterized
by various upper-bounds leveraging different techniques [22, 23]. The metric
of mutual information is first proposed in [24], further developed in [17] and
combined with chaining methods in [25, 26]. Similar bounds are obtained in
[18, 27–30] and references therein. Other information measures such as the
Wasserstein distance [16, 31, 32], maximal leakage [33, 34], mutual f-information
[35], and Jensen-Shannon divergence [36] are also explored in the literature.
Unfortunately, none of the existing bounds has been shown to be uniformly
tight in relevant practical cases [37, 38].

To circumvent the dependence of the D-EGG on the statistical description of the
training dataset and the specific learning algorithm in generalization analyses,
tools from combinatorics [39]; probability theory [40–42]; and information theory
[15, 17, 43] have been used with partial success. The main drawback of these
analytical approaches is that they provide guarantees that entail worst-case
dataset generation analysis but do not identify the data-generating measures
that curtail the generalization capability of the algorithm [38]. This, in turn,
results in descriptions of the D-EGG for which the dependence on the training
dataset and the selected algorithm is not made evident. Recent efforts for
highlighting the dependence of generalization capabilities on the training dataset
have led to explicit expressions for the GG and EGG when the models are
sampled using the Gibbs algorithm in [20, 44]. This line of work paved the way
to the study in this paper of the WCDG probability measures and their effect
on the D-EGG.
## 1.2 Contributions

The first contribution consists of the derivation of a probability measure over the datasets coined WCDG probability measure. The WCDG probability measure can be defined as the measure that maximizes the expectation of the loss over a set of measures that are at a “statistical distance” with respect to a reference measure that is not larger than a given threshold. Alternatively, the WCDG probability measure can be defined as the measure that maximizes the expectation of the loss subject to a regularization by such a “statistical distance” with respect to the reference measure. When the “statistical distance” is the relative entropy, both definitions are shown to be identical, under specific conditions. Despite the limitations of relative entropy concerning its asymmetry [10, 45] and the need of absolute continuity with respect to the reference measure [9], the resulting WCDG probability measure is a Gibbs probability measure (Theorem 1) parametrized by the reference measure; the regularization parameter; and the loss function. This Gibbs probability measure is shown to exhibit relevant properties in statistical machine learning. In particular, for a fixed model, the loss resulting from the assumption that datapoints are sampled from the WCDG probability measure is a sub-Gaussian random variable. Moreover, the variation of the expectation of the loss when the probability measure changes from the WCDG probability measure to an alternative measure has an explicit expression involving relative entropy terms. Using this result, the variation of the expectation of the loss when the measure changes from an arbitrary measure to any alternative measure is presented (Theorem 8). This is a significant result as the reference measure and the regularization parameter can be arbitrarily chosen, which leads to numerous closed-form expressions for such a variation.

The second contribution leverages the observation that under the assumption that datasets are tuples of independent and identically distributed datapoints, datasets can be represented by their corresponding types, which are empirical probability measures [2]. Interestingly, the empirical risk induced by a model with respect to a given dataset is proved to be equal to the expectation of the loss with respect to the corresponding type (Lemma 7). This observation allows using Theorem 8 to provide an explicit expression to the difference between two empirical risks induced by the same model on two different datasets. This difference is referred to as the sensitivity of the empirical risk. Using the same arguments, closed-form expressions involving relative entropy terms are provided for the GG induced by a fixed model.

The final contribution consists in using the WCDG probability measure to obtain exact expressions for the D-EGG for any machine learning algorithm. These expressions can be broadly divided into two classes. The first one involves a WCDG probability measure, while the second one involves a Gibbs algorithm. This reveals the central place of the Gibbs algorithm in statistical machine learning. Indeed, the Gibbs algorithm facilitates the derivation of overarching insights into the D-EGG applicable to any machine learning algorithm.
## 1.3 Notation

Given a measurable space $(\Omega, \mathcal{F})$, the notation $\triangle(\Omega)$ is used to represent the set of $\sigma$-finite measures that can be defined over $(\Omega, \mathcal{F})$. Often, when the sigma-algebra $\mathcal{F}$ is fixed, it is hidden to ease notation. Given a measure $Q \in \triangle(\Omega)$, the subset $\triangle_Q(\Omega)$ of $\triangle(\Omega)$ contains all $\sigma$-finite measures that are absolutely continuous with respect to the measure $Q$. Given a second measurable space $(\mathcal{X}, \mathcal{G})$, the notation $\triangle(\Omega|\mathcal{X})$ is used to represent the set of $\sigma$-finite measures defined over $(\Omega, \mathcal{F})$ conditioned on an element of $\mathcal{X}$.

# 2 Problem Formulation

Let $\mathcal{M}, \mathcal{X}$ and $\mathcal{Y}$, with $\mathcal{M} \subseteq \mathbb{R}^d$ and $d \in \mathbb{N}$, 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. Let the probability measure

$$P_Z \in \triangle(\mathcal{X} \times \mathcal{Y}) \qquad (1)$$

be the one from which data points are independently sampled. While the probability measure $P_Z$ is unknown in a practical setting, a finite set of datapoints is made available via a dataset. Given $n$ data points, with $n \in \mathbb{N}$, denoted by $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$, a dataset is represented by the tuple:

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

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

Let also the function

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

be such that given a data point $(x, y) \in \mathcal{X} \times \mathcal{Y}$, the loss induced by a model $\theta \in \mathcal{M}$ is $\hat{\ell}(f(\theta, x), y)$. In the following, the loss function $\hat{\ell}$ is assumed to be non-negative and for all $y \in \mathcal{Y}$, $\hat{\ell}(y, y) = 0$.

For the ease of notation, let the function $\ell: \mathcal{M} \times \mathcal{X} \times \mathcal{Y} \to [0, +\infty]$ be such that for all $(x, y) \in \mathcal{X} \times \mathcal{Y}$,

$$\ell(\theta, x, y) = \hat{\ell}(f(\theta, x), y). \qquad (4)$$

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

$$\mathcal{L}(z, \theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(\theta, x_i, y_i), \qquad (5)$$

where the function $\ell$ is defined in (4).
Using this notation, the model selection problem is formulated as an ERM problem, which consists of the following optimization problem:

$$ \min_{\theta \in \mathcal{M}} \mathbf{L}(z, \theta). \qquad (6) $$

The ERM problem is prone to overfitting since the set of solutions to (6) are models selected specifically for the given data set $z$ in (2), which limits the generalization capability of the resulting optimal model. One way to compensate for overfitting and adding more stability to the learning algorithm by adding a regularization term to the optimization problem in (6). Such a regularization term can be represented by a function $R: \mathcal{M} \to \mathbb{R}$, which yields the regularized ERM problem

$$ \min_{\theta \in \mathcal{M}} \mathbf{L}(z, \theta) + \lambda R(\theta), \qquad (7) $$

where $\lambda$ is a nonnegative real that acts as a regularization parameter. The regularization function constraints the choice of the model, which can be interpreted as requiring a finite space for the models or limiting the “complexity” of the model [1]. One common choice for $R$ is $R(\theta) = \|\theta\|_p$, with $p \ge 1$. The norm is often used to account for the model complexity. Alternatively, the regularization parameter $\lambda$ determines the weight that regularization carries in the model selection.

The main interest in this work is to study the generalization capability for a given model $\theta \in \mathcal{M}$ independently from how such a model is chosen.

# 3 The Worst-Case Data-Generating Probability Measure

## 3.1 General Discussion

Given a probability measure $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$, which can be interpreted as a prior on the set of data points, and a model $\theta \in \mathcal{M}$, looking for a WCDG probability measure might lead to two different optimization problems. Both can be defined in terms of the expectation of $\ell$ in (4) with respect to a probability measure $P$ in $\Delta(\mathcal{X} \times \mathcal{Y})$, for a fixed model $\theta$. Before introducing such optimization problems, some notation is specified. Let the functional $R_{\theta}: \Delta(\mathcal{X} \times \mathcal{Y}) \to [0, +\infty]$ be such that

$$ R_{\theta}(P) = \int \ell(x, y, \theta)dP(x, y). \qquad (8) $$

Using this notation, the expected loss is defined as follows.

**Definition 1 (Expected Loss)** Let $P$ be a probability measure in $\Delta(\mathcal{X} \times \mathcal{Y})$. The expected loss with respect to a fixed model $\theta \in \mathcal{M}$ induced by the measure $P$ is $R_{\theta}(P)$.
To define the first optimization problem, a neighborhood around $P_S$ is established through a statistical distance $d: \Delta(\mathcal{X} \times \mathcal{Y}) \times \Delta(\mathcal{X} \times \mathcal{Y}) \to [0, +\infty)$. In view of this, the WCDG measure is a probability measure that maximizes the expectation of the loss within such a neighborhood. This view leads to the following problem:

$$ \max_{P \in \Delta(\mathcal{X} \times \mathcal{Y})} R_{\theta}(P) \qquad (9a) $$

$$ \text{s.t.} \quad d(P, P_S) \le \gamma, \qquad (9b) $$

where $\gamma > 0$ determines the neighborhood around $P_S$ as the set $\{P \in \Delta(\mathcal{X} \times \mathcal{Y}): d(P, P_S) \le \gamma\}$ and the functional $R_{\theta}$ is defined in (8).

To introduce the second optimization problem, a WCDG measure can be interpreted as a probability measure that trades off the maximization of the expectation of the loss and the minimization of the statistical distance with respect to $P_S$. This point of view leads to an optimization problem of the form:

$$ \max_{P \in \Delta(\mathcal{X} \times \mathcal{Y})} R_{\theta}(P) - \beta d(P, P_S), \qquad (10) $$

where the functional $R_{\theta}$ is defined in (8); and $\beta > 0$ determines the trade-off between maximization of the expectation of the loss and the statistical distance to $P_S$. In this case, the convexity of $d(P, P_S)$ with respect to $P$ is a valuable property for solving the optimization problem.

Depending on the choice of the statistical distance $d$ in (9) and (10), numerous WCDG probability measures might be obtained. In either case, such WCDG probability measures are subject to the limitations concerning the asymmetry of $d$; limitations concerning the absolute continuity requirements with respect to $P_S$; or limitations derived from the need for $\mathcal{X} \times \mathcal{Y}$ to be equipped with a metric so as to form a Polish metric space. These limitations can lead the problems in (9) and (10) to be ill posed, difficult to solve, to exhibit no solution, or to exhibit solutions with poor properties for the analysis of generalization in statistical machine learning. In particular, the statistical distance $d$ can be chosen as an $f$-divergence [46]. See for instance the examples in [9]. In this case,

$$ d(P, P_S) = \int f\left(\frac{dP}{dP_S}(x, y)\right) dP(x, y), \qquad (11) $$

where the function $f: (0, +\infty) \to \mathbb{R}$ is assumed to be concave and $f(1) = 0$; and the function $\frac{dP}{dP_S}: \mathcal{X} \times \mathcal{Y} \to [0, +\infty)$ is the Radon-Nikodym derivative of $P$ with respect to $P_S$. For some choices of the function $f$, the corresponding $f$-divergence can be symmetric, e.g., Jeffrey's divergence [47]; or be asymmetric, e.g., Kullback-Leibler divergence [48]. An interesting discussion on the impact of asymmetry in optimization problems similar to the one in (10) is presented in [10] and [9]. In any case, if $d$ is chosen as an $f$-divergence, the optimization
domain shall be restricted to the set of measures that are absolutely continuous with $P_S$. This is essentially because the existence of a Radon-Nikodym derivative with respect to $P_S$ is required.

An alternative choice for the statistical distance $d$ in (9) and (10) is

$$d(P, P_S) = \sup \left\{ \int f(x, y)dP(x, y) - \int f(x, y)dP_S(x, y) : f \in \mathcal{D} \right\}, \quad (12)$$

where $\mathcal{D}$ is a particular set of functions $\mathcal{X} \times \mathcal{Y} \to \mathbb{R}$. In such a formulation for $d$ in (12), while $P$ is not required to be absolutely continuous with respect to $P_S$, other requirements must be ensured. For instance, in the case in which the set $\mathcal{D}$ is such that if $f \in \mathcal{D}$, then for all $(x, y) \in \mathcal{X} \times \mathcal{Y}$ and for all $(u, v) \in \mathcal{X} \times \mathcal{Y}$,

$$|f(x, y) - f(u, v)| \le d((x, y), (u, v)), \quad (13)$$

with $d$ being a metric on the set $\mathcal{X} \times \mathcal{Y}$, the resulting statistical distance is the Kantorovich-Rubinstein distance, also known as the Wasserstein distance of order one [49, Remark 6.5]. Note that this choice of $\mathcal{D}$ imposes the need of the set $\mathcal{X} \times \mathcal{Y}$ to be equipped with the metric $d$ in (13). Moreover, $(\mathcal{X} \times \mathcal{Y}, d)$ must be a Polish metric space.

From the above, it becomes clear that every choice for the statistical distance $d$ comes with particular requirements. Thus, the search for an optimal choice for $d$ reduces to evaluating the properties of the resulting WCDG probability measures and their impact in the analysis of generalization of machine learning algorithms. In the following, it is argued that the choice of $d$ as the relative entropy, despite the limitations concerning its asymmetry and the restriction of the optimization domains to measures that are absolutely continuous with $P_S$, leads to a variety of properties that are central in the analysis of generalization.

## 3.2 Relative Entropy Case

This section focuses on the special cases in which the statistical distance $d$ in (9) and (10) is chosen as the relative entropy. The relative entropy is the $f$-divergence resulting from the choice of $f(x) = x \log(x)$ in (11). See for instance [50]. Given two probability measures $P$ and $Q$ on the same measurable space such that $P$ is absolutely continuous with respect to $Q$, the relative entropy of $P$ with respect to $Q$ is

$$D(P \| Q) = \int \frac{dP}{dQ}(x) \log \left( \frac{dP}{dQ}(x) \right) dQ(x), \quad (14)$$

where the function $\frac{dP}{dQ}$ is the Radon-Nikodym derivative of $P$ with respect to $Q$. Using this notation, the optimization problems of interest are

$$\max_{P \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})} R_{\theta}(P) \quad (15a)$$

$$\text{s.t.} \quad D(P \| P_S) \le \gamma, \quad (15b)$$
and

$$ \max_{P \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})} \mathbf{R}_{\theta}(P) - \beta D(P \| P_S). \qquad (16) $$

The optimization problems in (15) and (16) exhibit a major difference in the following case. If for all $P \in \Delta_{P_S}$, the functional $\mathbf{R}_{\theta}$ in (8) is such that $\mathbf{R}_{\theta}(P) = c$, for some fixed $c \ge 0$, then all the measures in $\{P \in \Delta(\mathcal{X} \times \mathcal{Y}) : D(P \| P_S) \le \gamma\}$ are solutions to the optimization problem in (15). Alternatively, the problem in (16) exhibits a unique solution, which is $P_S$. Hence, while the former exhibits infinitely many solutions, the latter exhibits only one. Although this difference holds substantial mathematical importance, its practical relevance is limited, as it only emerges in settings for which the expectation of the loss $\mathbf{R}_{\theta}(P)$ is invariant with respect to the measure $P$. In order to avoid the above case, the notion of separable loss functions, which is analogous to [21, Definition 5], is introduced as follows.

**Definition 2** Given a model $\theta \in \mathcal{M}$, the function $\ell$ in (4), is said to be separable with respect to the probability measure $P \in \Delta(\mathcal{X} \times \mathcal{Y})$, if there exist a positive real $c > 0$ and two subsets $\mathcal{A}$ and $\mathcal{B}$ of $\mathcal{X} \times \mathcal{Y}$ that are nonnegligible with respect to $P$, and for all $((x_1, y_1), (x_2, y_2)) \in \mathcal{A} \times \mathcal{B}$,

$$ \ell(\theta, x_1, y_1) < c < \ell(\theta, x_2, y_2) < +\infty. \qquad (17) $$

When the function $\ell$ in (4) is nonseparable with respect to the reference measure $P_S$, it is a constant almost surely with respect to such a measure. More specifically, there exists a real $a \ge 0$, such that

$$ P_S(\{(x, y) \in \mathcal{X} \times \mathcal{Y} : \ell(\theta, x, y) = a\}) = 1, \qquad (18) $$

and as a consequence, for all probability measures $P \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$, it holds that $P(\{(x, y) \in \mathcal{X} \times \mathcal{Y} : \ell(\theta, x, y) = a\}) = 1$. With this pathological case of nonseparable loss functions out of the way, the optimization problems in (15) and (16) exhibit considerable similarity. This similarity is formalized in Theorem 1 below. Given a model $\theta \in \mathcal{M}$, 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), \qquad (19) $$

where the function $\ell$ is defined in (4). The following lemma describes some properties of the function $J_{P_S, \theta}$ in (19).

**Lemma 1** The function $J_{P_S, \theta}$ in (19) is convex, nondecreasing, and differentiable infinitely many times in the interior of $\{t \in \mathbb{R} : J_{P_S, \theta}(t) < +\infty\}$. If the function $\ell$ in (4) is separable with respect to $P_S$, then the function $J_{P_S, \theta}$ is strictly convex.

*Proof:* The proof is presented in Appendix A.

<figure><img src="image_3.png" /></figure>
Let also the set $\mathcal{J}_{P_S, \theta}$ be the set

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

which exhibits the following property.

**Lemma 2** The set $\mathcal{J}_{P_S, \theta}$ in (20) is either the empty set or an interval satisfying $(b, +\infty) \subseteq \mathcal{J}_{P_S, \theta}$, for some $b \in [0, +\infty)$.

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

Using this notation, the following theorem formalizes the fact that the optimization problems in (15) and (16) exhibit the same unique solution.

**Theorem 1** If the function $\ell$ in (4) is separable with respect to the measure $P_S$ and $\beta \in \mathcal{J}_{P_S, \theta}$, with $\mathcal{J}_{P_S, \theta}$ in (20), then the probability measure $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)} \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$ that satisfies for all $(x, y) \in \text{supp } P_S$,

$$ \frac{\mathrm{d}P_{\tilde{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 (21) $$

with the function $\mathcal{J}_{P_S, \theta}$ defined in (19) and

$$ D\left(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S\right) = \gamma, \quad (22) $$

is the unique solution to the optimization problems in (15) and (16).

*Proof:* A proof can be found at [6, Proposition 1]. An alternative proof is presented in Appendix C. ■

The probability measure $P_S$ in Theorem 1 can be arbitrarily chosen, that is, independent of the model $\theta$. From this perspective, when the measure $P_S$ is interpreted as a prior on the datasets, the WCDG probability measure $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ can be interpreted as the worst probability measure for model $\theta$ in the neighborhood of the prior $P_S$. The reference measure $P_S$ can also be chosen to be dependent on the models. This particular case is studied later.

The parameter $\gamma$ of the optimization problem in (15) does not explicitly appear in the expression of the solution $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21). Nonetheless, the probability measure $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ does depend on $\gamma$. This dependence is shown via the equality in (22). Later, in Lemma 6, it is shown that $D\left(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S\right)$ in (22) is monotone with $\beta$. More importantly, if the function $\ell$ in (4) is separable, the relative entropy $D\left(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S\right)$ is strictly decreasing with $\beta$. This implies that there exists a one-to-one mapping between $\beta$ and $\gamma$, and thus, the analysis can be indistinctly carried out either for $\beta$ or $\gamma$.
The probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21) is a Gibbs probability measure [51].

In the remainder of this work, the probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ is referred to as the WCDG probability measure and the function $J_{P_S, \theta}$ in (19) is referred to as the log-partition function [52]. The WCDG probability measure exhibits a number of interesting properties. The following lemma introduces two of these properties, which are shown to be central in the remainder of this work.

**Lemma 3** The probability measures $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ and $P_S$ in (21) are mutually ab-
solutely continuous. Moreover, they satisfy

$$
\beta J_{P_S, \theta} \left( \frac{1}{\beta} \right) = R_{\theta} \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) - \beta D \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S \right) \quad (23)
$$

$$
= \sup_{P \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})} R_{\theta}(P) - \beta D(P \| P_S) \quad (24)
$$

$$
= R_{\theta}(P_S) + \beta D(P_S \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}), \quad (25)
$$

where the functional $R_{\theta}$ and the function $J_{P_S, \theta}$ are defined in (8) and (19), respectively.

Proof: The proof of (24) follows from Theorem 1. The proofs of (23) and (25)
are presented in Appendix D.

In Lemma 3, the equality

$$
\beta J_{P_S, \theta} \left( \frac{1}{\beta} \right) = \sup_{P \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})} R_{\theta}(P) - \beta D(P \| P_S) \quad (26)
$$

also appears in [49, Equation (22.7)] obtained using the Legendre representation
of the relative entropy.

Lemma 3 implicitly characterizes the difference of the expected losses induced
by the WCDG probability measure and the reference measure. That is,

$$
R_{\theta} \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) - R_{\theta} \left( P_S \right) = \beta \left( D \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S \right) + D \left( P_S \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) \right), \quad (27)
$$

where $D(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S) + D(P_S \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)})$ is Jeffrey's divergence between $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ and $P_S$.

In the remainder of this work, the GTDG probability measure of the datapoints
is denoted by $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$. The probability measure $P_Z$ is the measure
induced by a random variable $Z$ on the measurable space of the datapoints.
Under the assumption that datasets are formed by $n$ independent and identi-
cally distributed datapoints, the GTDG probability measure of such datasets
is denoted by $P_Z \in \Delta((\mathcal{X} \times \mathcal{Y})^n)$, which is a product measure formed by $P_Z$.
Alternatively, the probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21) is induced by a random
variable $\hat{Z}$ on the measurable space of the datapoints. Under the assump-
tion that datasets are formed by $n$ independent datapoints sampled from the
WCDG probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}$, the probability measure of such datasets is denoted by $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}$, which is the product measure formed by $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}$. In a nutshell, datapoints and datasets sampled from the GTDG probability measure are represented by the random variables $Z$ and $\hat{Z}$, respectively. Similarly, datapoints and datasets sampled from a WCDG probability measure are represented by the random variables $\hat{Z}$ and $\hat{\hat{Z}}$, respectively.

### 3.3 Choice of the Reference Measure

Probably, the most intuitive choice of $P_S$ is to be based on the training datasets. In order to introduce this intuition, the notion of a type induced by a dataset [2] is presented hereunder.

**Definition 3 (Type of a dataset)** The type induced by the dataset $z$ in (2) is a probability measure in $\Delta(\mathcal{X} \times \mathcal{Y})$, denoted by $P_z$, such that for all measurable subsets $A$ of $\mathcal{X} \times \mathcal{Y}$,

$$P_z(A) = \frac{1}{n} \sum_{t=1}^{n} 1\{(x_t, y_t) \in A\}. \qquad (28)$$

For large values of $n$, it might be expected that the type $P_z$ induced by the training dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$ be within a neighborhood of the GTDG probability distribution $P_Z$. More specifically, under the assumption that the sets $\mathcal{X}$ and $\mathcal{Y}$ are discrete, such a neighborhood might be of the form

$$\mathcal{N}(P_Z, \gamma) \triangleq \{P \in \Delta(\mathcal{X} \times \mathcal{Y}) : D(P \| P_Z) \le \gamma\}, \qquad (29)$$

for some $\gamma > 0$. Nonetheless, the GTDG probability measure $P_Z$ being unknown, it appears reasonable to choose the reference measure $P_S$ identical to the type $P_z$. This leads to an optimization problem of the form in (15), whose optimization domain is

$$\mathcal{N}(P_z, \gamma) \triangleq \{P \in \Delta_{P_z}(\mathcal{X} \times \mathcal{Y}) : D(P \| P_z) \le \gamma\}. \qquad (30)$$

This choice presumes that the training dataset is sufficiently large to consider that the GTDG probability measure is absolutely continuous with respect to the type $P_z$ such that the GTDG probability measure $P_Z$ is within $\mathcal{N}(P_z, \gamma)$. Another alternative for the choice of $P_S$ in the optimization problems in (15) and (16) is for instance a convex combination between the type $P_z$ and an arbitrary probability measure known to be absolutely continuous with $P_Z$.

In any case, the choice of $P_S$ imposes a condition on the optimization domain of the problems in (15) and (16) that translates into a strong inductive bias that dominates the evidence provided by the training data. More specifically, the optimization domain becomes a subset of the set of measures that are absolutely continuous with respect to $P_S$.
# 4 Cumulants of the Expected Loss

The log-partition function $J_{P_S, \theta}$ in (19) can be interpreted also as the cumulant generating function of the random variable

$$V_{\theta} \triangleq \ell(\theta, X, Y), \qquad (31)$$

with the function $\ell$ in (4) and $(X, Y) \sim P_S$, with $P_S$ in (21), for some given model $\theta$ that remains fixed. In particular, if the function $J_{P_S, \theta}$ is differentiable around zero, its derivative of order $n$ evaluated at zero reveals the $n$-th cumulant of the random variable $V_{\theta}$ in (31). More interestingly, the function $J_{P_S, \theta}$ in (19) is intimately related to the cumulant generating function of the random variable

$$W_{\theta} \triangleq \ell(\theta, X, Y), \qquad (32)$$

where $(X, Y) \sim P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$, with $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21), for some given model $\theta$ that remains fixed. In particular, the cumulant generating function of the random variable $W_{\theta}$, which is denoted by $J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}: \mathbb{R} \to \mathbb{R}$, satisfies

$$J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}(t) = \log \left( \int \exp(t\ell(\theta, x, y)) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(x, y) \right), \qquad (33)$$

where the function $\ell$ is defined in (4). The following lemma shows the exact relation between these two cumulant generating functions.

**Lemma 4** The function $J_{P_S, \theta}$ in (21) and the function $J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}$ in (33) satisfy

$$J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}(t) = J_{P_S, \theta}\left(t + \frac{1}{\beta}\right) - J_{P_S, \theta}\left(\frac{1}{\beta}\right). \qquad (34)$$

*Proof:* The proof is presented in Appendix E.

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

Let the $m$-th derivative of the function $J_{P_S, \theta}$ in (19) be denoted by $J_{P_S, \theta}^{(m)}$, with $m \in \mathbb{N}$. Hence, for all $t \in \mathbb{R}$ such that $J_{P_S, \theta}(t) < +\infty$,

$$J_{P_S, \theta}^{(m)}(t) \triangleq \left. \frac{d^m}{ds^m} J_{P_S, \theta}(s) \right|_{s=t}. \qquad (35)$$

Moreover, let the $m$-th derivative of the function $J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}$ in (19) be denoted by $J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}^{(m)}$, with $m \in \mathbb{N}$. Hence, for all $t \in \mathbb{R}$ such that $J_{P_S, \theta}(t + \frac{1}{\beta}) < +\infty$,

$$J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}(t) \triangleq J_{P_S, \theta}^{(m)}\left(t + \frac{1}{\beta}\right). \qquad (36)$$

The following lemma capitalizes on the observations above and provides explicit expressions for the first, second and third derivatives of the function $J_{P_S, \theta}$ in (19) and its connections with the cumulants of the random variables $V_{\theta}$ and $W_{\theta}$ in (31) and (32), respectively.
**Lemma 5** For all $t \in \mathcal{J}_{P_S, \theta}$, with $\mathcal{J}_{P_S, \theta}$ in (20), the first, second and third derivatives of the function $\mathcal{J}_{P_S, \theta}$ in (19), denoted respectively by $\mathcal{J}_{P_S, \theta}^{(1)}$, $\mathcal{J}_{P_S, \theta}^{(2)}$ and $\mathcal{J}_{P_S, \theta}^{(3)}$, satisfy that

$$ \mathcal{J}_{P_S, \theta}^{(1)} \left( \frac{1}{t} \right) = \int \ell(\theta, x, y) dP_{\hat{Z}|\Theta=\theta}^{(P_S, t)}(x, y), \quad (37) $$

$$ \mathcal{J}_{P_S, \theta}^{(2)} \left( \frac{1}{t} \right) = \int \left( \ell(\theta, x, y) - \mathcal{J}_{P_S, \theta}^{(1)} \left( \frac{1}{t} \right) \right)^2 dP_{\hat{Z}|\Theta=\theta}^{(P_S, t)}(x, y), \quad (38) $$
and

$$ \mathcal{J}_{P_S, \theta}^{(3)} \left( \frac{1}{t} \right) = \int \left( \ell(\theta, x, y) - \mathcal{J}_{P_S, \theta}^{(1)} \left( \frac{1}{t} \right) \right)^3 dP_{\hat{Z}|\Theta=\theta}^{(P_S, t)}(x, y), \quad (39) $$

where the function $\ell$ is in (4) and the measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, t)}$ is in (21). The value $\mathcal{J}_{P_S, \theta}^{(2)} \left( \frac{1}{t} \right)$ is strictly positive if and only if the function $\ell$ is separable with respect to $P_S$. Moreover, if there exists real $\delta > 0$ such that the function $\mathcal{J}_{P_S, \theta}$ is differentiable within $(-\delta, \delta)$, then

$$ \mathcal{J}_{P_S, \theta}^{(1)} (0) = \int \ell(\theta, x, y) dP_S(x, y), \text{ and} \quad (40) $$

$$ \mathcal{J}_{P_S, \theta}^{(2)} (0) = \int \left( \ell(\theta, x, y) - \mathcal{J}_{P_S, \theta}^{(1)} (0) \right)^2 dP_S(x, y), \text{ and} \quad (41) $$

$$ \mathcal{J}_{P_S, \theta}^{(3)} (0) = \int \left( \ell(\theta, x, y) - \mathcal{J}_{P_S, \theta}^{(1)} (0) \right)^3 dP_S(x, y). \quad (42) $$

*Proof:* The proof is presented in Appendix F.

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

From Lemma 5, it follows that the random variable $W_\theta$ in (32) possesses a mean, variance, and third cumulant that are equivalent to $\mathcal{J}_{P_S, \theta}^{(1)} \left( \frac{1}{\beta} \right)$ in (37), $\mathcal{J}_{P_S, \theta}^{(2)} \left( \frac{1}{\beta} \right)$ in (38), and $\mathcal{J}_{P_S, \theta}^{(3)} \left( \frac{1}{\beta} \right)$ in (39), respectively. Alternatively, under the assumptions of the lemma, the random variable $V_\theta$ in (31) possesses a mean, variance, and third cumulant that are equivalent to $\mathcal{J}_{P_S, \theta}^{(1)} (0)$ in (40), $\mathcal{J}_{P_S, \theta}^{(2)} (0)$ in (41), and $\mathcal{J}_{P_S, \theta}^{(3)} (0)$ in (42), respectively. The following corollary of Lemma 5 highlights the monotonicity of $\mathcal{J}_{P_S, \theta}^{(1)} \left( \frac{1}{\beta} \right)$ with respect to $\beta$.

**Corollary 1** The expected loss $\mathcal{J}_{P_S, \theta}^{(1)} \left( \frac{1}{t} \right)$ in (37) is nonincreasing with respect to $t$ in the interior of $\{s \in \mathbb{R} : \mathcal{J}_{P_S, \theta} \left( \frac{1}{s} \right) < +\infty\}$. Moreover, if the loss function $\ell$ in (4) is separable with respect to $P_S$, $\mathcal{J}_{P_S, \theta}^{(1)} \left( \frac{1}{t} \right)$ is strictly decreasing with $t$ in $\{s \in \mathbb{R} : \mathcal{J}_{P_S, \theta} \left( \frac{1}{s} \right) < +\infty\}$.

More generally, under the assumptions of the lemma, the random variables $V_\theta$ in (31) and $W_\theta$ in (32) possess finite cumulants of all orders. That is, the values $\mathcal{J}_{P_S, \theta}^{(m)}(0)$ and $\mathcal{J}_{P_S, \theta}^{(m)} \left( \frac{1}{\beta} \right)$, which are the $m$-th cumulants of the random variables $V_\theta$ and $W_\theta$, respectively, for all integers $m > 0$, are both finite. This observation
together with the mean value theorem [53, Theorem 5.10] lead to the following characterization of the cumulants $J_{P_S, \theta}^{(m)}(\frac{1}{\beta})$ and $J_{P_S, \theta}^{(m)}(0)$.

**Theorem 2** Assume that there exists real $\delta > 0$ such that the function $J_{P_S, \theta}$ in (19) is differentiable within $(-\delta, \delta)$. Then, for all $m \in \mathbb{N}$, the function $J_{P_S, \theta}^{(m)}$ in (35) satisfies for all $t \in \mathcal{J}_{P_S, \theta}$, with $\mathcal{J}_{P_S, \theta}$ in (20),

$$J_{P_S, \theta}^{(m)}(0) + \frac{1}{t}c_{m,2} \le J_{P_S, \theta}^{(m)}(\frac{1}{t}) \le J_{P_S, \theta}^{(m)}(0) + \frac{1}{t}c_{m,1}, \quad (43)$$

and

$$c_{m,1} = \max_{s \in (t, +\infty)} J_{P_S, \theta}^{(m+1)}(\frac{1}{s}), \quad \text{and} \quad (44)$$

$$c_{m,2} = \min_{s \in (t, +\infty)} J_{P_S, \theta}^{(m+1)}(\frac{1}{s}), \quad (45)$$

are both finite.

*Proof:* The proof is presented in Appendix G.

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

In Theorem 2, the case $m = 1$ is of little interest as $J_{P_S, \theta}^{(1)}(0) = R_{\theta}(P_S)$ and $J_{P_S, \theta}^{(1)}(\frac{1}{\beta}) = R_{\theta}(P_{\hat{Z}|\Theta=\theta})$, and thus, the difference $R_{\theta}(P_{\hat{Z}|\Theta=\theta}) - R_{\theta}(P_S)$ is well characterized by Jeffrey's divergence in (27). Nonetheless, while the inequality $J_{P_S, \theta}^{(1)}(0) < J_{P_S, \theta}^{(1)}(\frac{1}{\beta})$ is always verified, Theorem 2 shows that such inequality is not necessarily observed on the higher order cumulants. In the case of the variance ($m = 2$), it might be observed that $J_{P_S, \theta}^{(2)}(0) > J_{P_S, \theta}^{(2)}(\frac{1}{\beta})$ if $c_{2,1} < 0$. That is, the WCDG probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21) leads to a larger expected loss than the one obtained with the reference measure $P_S$ and at the same time it induces a lower variance than the variance associated with the reference measure $P_S$. Interestingly, the case in which the WCDG probability measure induces both a larger expected loss and higher variance is also possible when $c_{2,2} > 0$. A similar observation holds for cumulants of order $m > 2$.

The following theorem shows that the cumulant generating function $J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}$ of the random variable $W_{\theta}$ in (32) exhibits an important upper bound.

**Theorem 3** For all $t \in \{\alpha \in \mathbb{R} : J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}(\alpha) < +\infty\}$, the function $J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}$ in (33) satisfies the following inequality:

$$J_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}(t) \le t J_{P_S, \theta}^{(1)}(\frac{1}{\beta}) + \frac{1}{2}t^2 \zeta_{P_S, \theta}^2, \quad (46)$$

where $\zeta_{P_S, \theta}$ is finite, and satisfies

$$\zeta_{P_S, \theta} \triangleq \sup \left\{ \sqrt{J_{P_S, \theta}^{(2)}(\xi)} : \xi \in (-\infty, b - \frac{1}{\beta}) \right\}, \quad (47)$$
with

$$b \triangleq \sup \{\alpha \in \mathbb{R} : \mathcal{J}_{P_S, \theta}(\alpha) < +\infty\}, \quad (48)$$

and the functions $\mathcal{J}_{P_S, \theta}^{(1)}$ and $\mathcal{J}_{P_S, \theta}^{(2)}$ are defined in (35).

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

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

The relevance of Theorem 3 lies on the fact that it implies that the random variable $W_{\theta}$ in (32) is a sub-Gaussian random variable with sub-Gaussian parameter $\zeta_{P_S, \theta}$ in (47). An interesting discussion on the impact of the random variable $W_{\theta}$ being sub-Gaussian is presented in [17, Theorem 1].

Finally, leveraging the properties of sub-Gaussian random variables, e.g., [54, Equation 2.9], the following holds for all $\alpha > 0$:

$$P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}\left(\left\{(x, y) \in \mathcal{X} \times \mathcal{Y} : \left|\ell(\theta, x, y)-\mathcal{J}_{P_S, \theta}^{(1)}\left(\frac{1}{\beta}\right)\right| \geq \alpha\right\}\right) \leq 2 \exp \left(-\frac{\alpha^2}{2 \zeta_{P_S, \theta}^2}\right), (49)$$

where $\zeta_{P_S, \theta}$ is defined in (47) and $\mathcal{J}_{P_S, \theta}^{(1)}(\frac{1}{\beta})$ is the expected loss in (37). This type of concentration inequality allows the study of the robustness of the model $\theta$ when it faces data sampled from WCDG probability distributions, which leads to interesting guidelines for algorithm design.

# 5 $(\epsilon, \delta)$-Robustness and Algorithm Design

An important observation on the dependence of the WCDG probability distribution $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21) on the parameter $\gamma$ in (22) is that for all $P \in \mathcal{N}(P_S, \gamma)$, with $\mathcal{N}(P_S, \gamma)$ given by

$$\mathcal{N}(P_S, \gamma) \triangleq \{P \in \Delta(\mathcal{X} \times \mathcal{Y}) : D(P \| P_S) \le \gamma\}, \quad (50)$$

it holds that

$$\mathbb{R}_{\theta}(P) \le \mathbb{R}_{\theta}\left(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}\right). \quad (51)$$

Essentially, the WCDG probability measure $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ is the measure that induces the largest expected loss within the neighborhood $\mathcal{N}(P_S, \gamma)$ of $P_S$. The following lemma unveils the fact that such a neighborhood expands as $\gamma$ increases or equivalently, as $\beta$ decreases.

**Lemma 6** The relative entropy $D(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S)$ in (22) satisfies

$$\frac{d}{d\beta} D\left(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S\right) = -\frac{1}{\beta^3} \mathcal{J}_{P_S, \theta}^{(2)}\left(\frac{1}{\beta}\right) \le 0, \quad (52)$$

where the function $\mathcal{J}_{P_S, \theta}^{(2)}$ is defined in (38). Moreover, the inequality is strict if and only if the function $\ell$ in (4) is separable with respect to $P_S$.
Proof: The proof is presented in Appendix I.

The key observation from Lemma 6 is that if the function $\ell$ is separable with respect to $P_S$, there exists a bijection between $\gamma$ and $\beta$ induced by the equality in (22). Another interesting observation is that the variations of $D(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}||P_S)$ in (22) and the expected loss $\mathcal{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta})$ in (37), with respect to $\beta$ (or $\gamma$), obey a revealing relation. Note that

$$ \frac{d}{d\beta} D(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}||P_S) = \frac{1}{\beta} \frac{d}{d\beta} \mathcal{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta}), \quad (53) $$

which implies that both $D(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}||P_S)$ and $\mathcal{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta})$ are decreasing with $\beta$. Nonetheless, their variations to changes in $\beta$ significantly differ. For values of $\beta$ around one, given that $1 \in \mathcal{J}_{P_S,\theta}$, with $\mathcal{J}_{P_S,\theta}$ in (20), the variations of $D(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}||P_S)$ and $\mathcal{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta})$ to changes in $\beta$ are identical. On the contrary, for values away from one, the variations of these quantities might be radically different.

The following definition describes a performance metric for a given data-generating probability measure $P \in \Delta((X \times Y)^n)$ and a model $\theta \in \mathcal{M}$ that leverages the observations above and provides guidelines for the choice of the values of $\beta$ (or $\gamma$).

**Definition 4** (($\epsilon, \delta$)-Robustness) Given a pair of positive reals $(\delta, \epsilon)$ with $\epsilon < 1$, a model $\theta \in \mathcal{M}$ is said to be $(\delta, \epsilon)$-robust to a probability measure $P \in \Delta((X \times Y)^n)$, if

$$ P(\{z \in (\text{supp } P_S)^n : L(z, \theta) \ge \delta\}) \le \epsilon. \quad (54) $$

This notion of robustness enables the study of the performance guarantees that a model $\theta$ yields when faced with data generated by the WCDG probability measure for specific parameters $\beta$ and $P_S$. An important issue that arises from this definition is the characterization of the largest value of $\gamma$ (or smallest value of $\beta$) that achieves $(\epsilon, \delta)$-robustness, i.e. how much can the WCDG probability measure deviate from the reference $P_S$ while the guarantee still holds. The following theorem establishes a link between $\beta$, the reference $P_S$, the expected loss, and the $(\epsilon, \delta)$-robustness that a given model $\theta$ achieves.

**Theorem 4** The probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}$ in (21) satisfies that for all $\delta > \mathcal{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta})$, with $\mathcal{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta})$ in (37),

$$ P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}(\{z \in (X \times Y)^n : L(\theta, z) \ge \delta\}) \le \exp(-nD(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}||P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)})), \quad (55) $$

where $\beta^* \in (0, \beta) \cap \mathcal{J}_{P_S,\theta}$, with $\mathcal{J}_{P_S,\theta}$ in (20), satisfies

$$ \mathcal{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta^*}) = \delta; \quad (56) $$
the function L is defined in (5); and the measure $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)} \in \bigtriangleup ((\mathcal{X} \times \mathcal{Y})^n)$ is a product measure formed by $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}$.

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

Theorem 4 describes the $(\epsilon, \delta)$-robustness of a model $\theta$ to the WCDG probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)} \in \bigtriangleup ((\mathcal{X} \times \mathcal{Y})^n)$. Note such a probability measure describes test datasets that are formed by $n$ datapoints independently and identically distributed with $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}$ in (21). Notably, such a description is in terms of another WCDG probability distribution $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}$, where $\beta^* < \beta$. Interestingly, the WCDG probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}$ induces an expected loss that is equal to $\delta$ and is greater than the expected loss induced by the WCDG probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}$. In a nutshell, for all $t \in (0, \beta) \cap \mathcal{J}_{P_S,\theta}$, let $\delta_t = \text{J}_{P_S,\theta}^{(1)}(\frac{1}{t})$ and $\epsilon_t = \exp(-nD(P_{\hat{Z}|\Theta=\theta}^{(P_S,t)} || P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)})$. Then, the model $\theta$ is $(\epsilon_t, \delta_t)$-robust to the WCDG probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}$.

The following theorem provides a $(\epsilon, \delta)$-robust guarantee to any product probability measure formed by a measure in the neighborhood $\mathcal{N}(P_S, \gamma)$ in (50).

**Theorem 5** For all models $\theta \in \mathcal{M}$ and for all $P_Z \in \mathcal{N}(P_S, \gamma)$, with $\mathcal{N}(P_S, \gamma)$ in (29) and $\beta$ in (22), it follows that for all $\delta > \text{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta})$, with $\text{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta})$ in (37),

$$P_Z(\{z \in (\mathcal{X} \times \mathcal{Y})^n : \mathcal{L}(\theta, z) \ge \delta\}) \le \frac{1}{\delta} \text{J}_{P_S, \theta}^{(1)}(\frac{1}{\beta}), \quad (57)$$

where the function $\ell$ is defined in (4) and the product probability measure $P_Z$ is formed by $P_Z$.

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

The relevance of Theorem 5 is that given a model $\theta$, it establishes that for all $\delta > \text{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta})$ and $\epsilon_\delta \triangleq \frac{1}{\delta}\text{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta})$, such a model $\theta$ is $(\epsilon_\delta, \delta)$-robust to all probability measures in $\mathcal{N}(P_S, \gamma)$, with $\mathcal{N}(P_S, \gamma)$ in (50). This observation raises the question of whether performing model selection based on the minimization of $\text{J}_{P_S,\theta}^{(1)}(\frac{1}{\beta})$ is an alternative for classical approaches based on empirical risk minimization (ERM) as in [55]; or statistical ERM as in [21] and [9].

# 6 Sensitivity of the Expected Loss

Given a model $\theta \in \mathcal{M}$, the variation of the expected loss when the probability measure from which data points are sampled varies to another measure is referred to as the sensitivity of the expected loss. Such a sensitivity can be
quantified using the functional $G: \mathcal{M} \times \Delta(\mathcal{X} \times \mathcal{Y}) \times \Delta(\mathcal{X} \times \mathcal{Y}) \to \mathbb{R}$,

$$G(\theta, P_1, P_2) = R_{\theta}(P_1) - R_{\theta}(P_2), \qquad (58)$$

where the functional $R_{\theta}$ is defined in (8). The value $G(\theta, P_1, P_2)$ represents the sensitivity of the expected loss $R_{\theta}$ when the data-generating probability measure changes from $P_2$ to $P_1$. This section characterizes the sensitivity $G(\theta, P_1, P_2)$ for arbitrary measures $P_1$ and $P_2$. To achieve this goal, the first result is the characterization of the sensitivity of the expected loss to variations from the measure $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21) to an alternative measure, which is presented in the following theorem.

**Theorem 6 (Sensitivity of the Expected Loss) The probability measure**
$P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21) 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)), \quad (59)$$

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

*Proof:* The proof is presented in Appendix L.

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

The following theorem introduces an upper bound on the absolute value of the sensitivity $G(\theta, P, P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}) \le 0$ in (59), which requires the calculation of only one of the relative entropies in Theorem 6.

**Theorem 7 The probability measure** $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21) satisfies for all $P \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$,

$$|G(\theta, P, P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)})| \le \sqrt{2\hat{\zeta}_{P_S, \theta}^2 D(P\|P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)})}, \quad (60)$$

where $\hat{\zeta}_{P_S, \theta}$ satisfies

$$\hat{\zeta}_{P_S, \theta}^2 \triangleq \sup \left\{ \sqrt{\mathcal{J}_{P_S, \theta}^{(2)}(\xi)} : \xi \in \left(0, b - \frac{1}{\beta}\right) \right\}, \quad (61)$$

with

$$b \triangleq \sup\{\alpha \in (0, +\infty) : \mathcal{J}_{P_S, \theta}(\alpha) < +\infty\}, \quad (62)$$

where the function $\mathcal{J}_{P_S, \theta}$ is defined in (19); the function $\mathcal{J}_{P_S, \theta}^{(2)}$ is defined in (38); and the functional $G$ is defined in (58).

*Proof:* The proof is presented in Appendix M.

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

Equipped with the exact characterization of the sensitivity from the measure $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ to any alternative measure $P$ provided by Theorem 6, it is possible to characterize the variation from and to arbitrary measures, as shown by the following theorem.
**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 \left( P_2 \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) - D \left( P_1 \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) - D(P_2 \| P_S) + D(P_1 \| P_S) \right), \quad (63) $$

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

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

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

Note that the parameters $\beta$ and $P_S$ in (63) can be arbitrarily chosen. This is essentially because only the right-hand side of (63) depends on $P_S$ and $\beta$. Another interesting observation is that none of the terms in the right-hand side of (63) depends simultaneously on both $P_1$ and $P_2$. Interestingly, these terms dependent exclusively on the pair formed by $P_i$ and $P_S$, with $i \in \{1, 2\}$. These observations highlight the significant flexibility of the expression in (63) to construct closed-form expressions for the sensitivity $G(\theta, P_1, P_2)$ in (58). The only constraint on the choice of $P_S$ is that both measures $P_1$ and $P_2$ must be absolutely continuous with respect to $P_S$. The following corollary follows by adopting particular choices for $P_S$. Two choices of $P_S$ for which the expression in the right-hand side of (63) significantly simplifies are $P_S = P_1$ and $P_S = P_2$, which leads to the following corollary of Theorem 8.

**Corollary 2** If $P_1$ is absolutely continuous with $P_2$, then the value $G(\theta, P_1, P_2)$ in (58) satisfies:

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

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

$$ G(\theta, P_1, P_2) = \beta \left( D \left( P_2 \| P_{\hat{Z}|\Theta=\theta}^{(P_1, \beta)} \right) - D \left( P_1 \| P_{\hat{Z}|\Theta=\theta}^{(P_1, \beta)} \right) - D(P_2 \| P_1) \right), \quad (65) $$

where for all $i \in \{1, 2\}$, the probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_i, \beta)}$ satisfies (21) 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 value $G(\theta, P_1, P_2)$ in (58). Note by choosing $P_S$ as a convex combination of $P_1$ and $P_2$, always guarantees an explicit expression for $G(\theta, P_1, P_2)$ independently of whether these measures are absolutely continuous with respect to each other.

## 6.1 Sensitivity of the Empirical-Risk

The following lemma shows that the empirical risk $L(z, \theta)$ in (5) can be written as the expectation of the loss with respect to the type $P_z$ in (28). This is formalized by the following lemma.
**Lemma 7 (Empirical Risks and Types)** The empirical risk $L(z, \theta)$ in (5) satisfies

$$L(z, \theta) = \int \ell(\theta, x, y)dP_z(x, y) = R_{\theta}(P_z), \qquad (66)$$

where the measure $P_z$ is the type induced by the dataset $z$; and the function $\ell$ and the functional $R_{\theta}$ are defined in (4) and (8), respectively.

*Proof:* The proof is presented in Appendix O.

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

Equipped with the result in Lemma 7, for a fixed model, the sensitivity of the empirical risk to changes on the datasets can be characterized using the function $G$ in (58). Consider two datasets $z_1 \in (\mathcal{X} \times \mathcal{Y})^{n_1}$ and $z_2 \in (\mathcal{X} \times \mathcal{Y})^{n_2}$ that induce the types $P_{z_1}$ and $P_{z_2}$, respectively. The sensitivity of the empirical risk when the dataset changes from $z_2$ to $z_1$, for a fixed model $\theta \in \mathcal{M}$, is

$$G(\theta, P_{z_1}, P_{z_2}) = L(z_1, \theta) - L(z_2, \theta). \qquad (67)$$

where the functional $G$ is defined in (58). The following theorem characterizes the sensitivity of the empirical risk.

**Theorem 9** Given two datasets $z_1 \in (\mathcal{X} \times \mathcal{Y})^{n_1}$ and $z_2 \in (\mathcal{X} \times \mathcal{Y})^{n_2}$, whose types $P_{z_1}$ and $P_{z_2}$ are absolutely continuous with respect to the measure $P_S$ in (21), it holds that for all $\theta \in \mathcal{M}$,

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

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

*Proof:* The proof follows from the equality in (67), which together with Theorem 8 completes the proof.

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

In Theorem 9, the reference measure $P_S$ can be arbitrarily chosen as long as both types $P_{z_1}$ and $P_{z_2}$ are absolutely continuous with $P_S$. A choice that satisfies this constraint is the type induced by the aggregation of both datasets $z_1$ and $z_2$, which is denoted by $z_0 = (z_1, z_2) \in (\mathcal{X} \times \mathcal{Y})^{n_0}$, with $n_0 = n_1 + n_2$. The type induced by the aggregated dataset $z_0$, denoted by $P_{z_0}$, is a convex combination of the types $P_{z_1}$ and $P_{z_2}$, that is, $P_{z_0} = \frac{n_1}{n_0} P_{z_1} + \frac{n_2}{n_0} P_{z_2}$ [20], which satisfies the absolute continuity condition in Theorem 9.

From Theorem 9, it appears that the difference between a test empirical risk $L(z_1, \theta)$ and the training empirical risk $L(z_2, \theta)$ of a given model $z$ is determined by two values: (a) the difference of the “statistical distance” from the types induced by the training and test datasets to the WCDG probability measure, i.e., $D(P_{z_2} \| P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}) - D(P_{z_1} \| P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)})$; and (b) the difference of the “statistical distance” from the types to the reference measure $P_S$, i.e., $D(P_{z_1} \| P_S) - D(P_{z_2} \| P_S)$.
## 6.2 Analysis of the Generalization Gap

Given a model $\theta \in \mathcal{M}$ obtained from the training dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$, the generalization gap it induces, under the assumption that training and test data-points are independent and identically distributed according to the probability measure $P_Z \in \Delta(\mathcal{X} \times \mathcal{Y})$, is

$$G(\theta, P_Z, P_z) = R_{\theta}(P_Z) - R_{\theta}(P_z). \qquad (69)$$

where the functional $G$ is defined in (58) and the function $R_{\theta}$ is defined in (8). The term $R_{\theta}(P_z) = L(z, \theta)$ is the training empirical risk, see for instance [1, Equation (3.4)]. Alternatively, the term $R_{\theta}(P_Z)$ is the expected loss under the assumption that the data-generating probability measure is the GTDG probability measure $P_Z$. This term is often referred to as the true risk or population risk. In view of this, the value $G(\theta, P_Z, P_z)$ in (69) describes the variation of the expected empirical risk when the distribution of the datasets changes from the type $P_z$ to the GTDG probability measure $P_Z$, which is characterized by the following lemma.

**Lemma 8** The generalization gap $G(\theta, P_Z, P_z)$ in (69) satisfies:

$$G(\theta, P_Z, P_z) = \beta \left( D \left( P_z \| P_{\hat{Z}|\Theta=\theta}^{(P_Z, \beta)} \right) - D(P_z \| P_Z) - D \left( P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_Z, \beta)} \right) \right), \quad (70)$$

where the measure $P_{\hat{Z}|\Theta=\theta}^{(P_Z, \beta)}$ is defined in (21) under the assumption that $P_S = P_Z$.

*Proof:* The proof follows from Corollary 2 by noticing that the type $P_z$ is absolutely continuous with respect to $P_Z$. ■

Lemma 8 highlights the intuition that if the type $P_z$ induced by the training dataset $z$ is at arbitrary small “statistical distance” of the GTDG probability measure $P_Z$, the generalization gap $G(\theta, P_Z, P_z)$ in (69) is arbitrarily close to zero. This is revealed by the facts that $D(P_z \| P_Z)$ would be arbitrarily small; and so would be the difference $D(P_z \| P_{\hat{Z}|\Theta=\theta}^{(P_Z, \beta)}) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_Z, \beta)})$.

A more general expression for the generalization gap $G(\theta, P_Z, P_z)$ in (69) is provided by the following corollary of Theorem 8.

**Corollary 3** The generalization gap $G(\theta, P_Z, P_z)$ in (69) satisfies:

$$G(\theta, P_Z, P_z) = \beta \left( D \left( P_z \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) - D \left( P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) - D(P_z \| P_S) + D(P_Z \| P_S) \right), \quad (71)$$

where the measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ is in (21).

Note that several expressions for the generalization gap $G(\theta, P_Z, P_z)$ in (69) can be obtained from Corollary 3 by choosing the reference $P_S$ and the parameter $\beta$ in (71).
# 7 Generalization Error

Consider a conditional probability measure $P_{\Theta|Z} \in \Delta(M|(X \times Y)^n)$, such that given a training dataset $z \in (X \times Y)^n$, the measure $P_{\Theta|Z=z} \in \Delta(M)$ is used to perform model selection, e.g., by sampling such a measure. In the following, the conditional measure $P_{\Theta|Z}$ is referred to as a statistical learning algorithm. Alternatively, the measure $P_{\Theta|Z=z}$ is referred to as the instance of the algorithm $P_{\Theta|Z}$ when it has been trained upon the dataset $z$.

This section provides explicit expressions for the expectation of the generalization gap $G(\theta, P_Z, P_z)$ in (69) when models $\theta$ are sampled from the probability measure $P_{\Theta|Z=z}$, for some training dataset $z$. This section also provides explicit expressions for the double expectation of the generalization gap $G(\theta, P_Z, P_z)$ when both models $\theta$ and datasets $z$ are respectively sampled from the probability measures $P_{\Theta|Z=z}$ and $P_Z$, where $P_Z$ is a product measure formed by $P_Z$ in (1). These generalization metrics are referred to as *expected generalization gap* and *doubly-expected generalization gap*. The latter is also known as *generalization error*.

In order to formally define the *expected generalization gap*, let $\bar{G}: \Delta(M) \times \Delta(X \times Y) \times \Delta(X \times Y) \to \mathbb{R}$ be a functional such that

$$ \bar{G}(Q, P_1, P_2) = \int G(\theta, P_1, P_2)dQ(\theta), \qquad (72) $$

where the functional $G$ is defined in (69). Using this notation, the expected generalization gap induced by the algorithm $P_{\Theta|Z}$, when the training dataset is $z$, is

$$ \bar{G}(P_{\Theta|Z=z}, P_Z, P_z) = \int G(\theta, P_Z, P_z)dP_{\Theta|Z=z}(\theta). \qquad (73) $$

From Corollary 3, by strategically choosing the reference measure $P_S$ and the parameter $\beta$ in (71), numerous closed-form expressions for the expected generalization gap induced by the algorithm $P_{\Theta|Z}$, when the training dataset is $z$, are obtained.

The expected generalization gap $\bar{G}(P_{\Theta|Z=z}, P_Z, P_z)$ in (73) depends on the training dataset $z$. The doubly-expected generalization gap is obtained by taking the expectation of $\bar{G}(P_{\Theta|Z=z}, P_Z, P_z)$ when $z \in (X \times Y)^n$ is sampled from $P_Z \in \Delta((X \times Y)^n)$, which is assumed to be a product distribution formed by $P_Z$ in (1).

In order to formally define the *doubly-expected generalization gap*, consider the function $\bar{\bar{G}}: \Delta(M|(X \times Y)^n) \times \Delta(X \times Y)^n \to \mathbb{R}$ such that

$$ \bar{\bar{G}}(P_{\Theta|Z}, P_Z) = \int \int G(\theta, P_Z, P_z)dP_{\Theta|Z=z}(\theta)dP_Z(z), \qquad (74) $$

where the measure $P_Z$ is the type induced by a dataset $z \in (X \times Y)^n$; the measure $P_Z$ is a product measure formed by $P_Z$; and the functional $G$ is defined in (69).
Using this notation, the doubly-expected generalization gap induced by the algorithm $P_{\Theta|Z}$, when the training and test datasets are both formed by independent and identically distributed datapoints sampled from the measure $P_Z$ in (1), is $\bar{G}(P_{\Theta|Z}, P_Z)$ in (74).

In existing literature, the doubly-expected generalization gap is simply referred to as generalization error, and thus, the distinction with generalization gaps that are dependent on specific models and training datasets is often neglected. See for instance [15], [17] and [21]. In this work, such a distinction is important. Nonetheless, for the ease of presentation, in the remaining of this work, “generalization error” is used more often than “doubly-expected generalization gap”.

The main result of this section are closed-form expressions for the generalization error $\bar{G}(P_{\Theta|Z}, P_Z)$ in (74), where $P_{\Theta|Z}$ is an arbitrary algorithm. Some expressions involve a WCDG probability measure, while others involve a Gibbs algorithm. Before introducing such results, some notation is reviewed:

$$I(P_{\Theta|Z}; P_Z) \triangleq \int D(P_{\Theta|Z=\nu} \| P_{\Theta}) dP_Z(\nu) \quad (75)$$

$$= \int D(P_{Z|\Theta=\theta} \| P_Z) dP_{\Theta}(\theta); \text{ and} \quad (76)$$

$$L(P_{\Theta|Z}; P_Z) \triangleq \int D(P_{\Theta} \| P_{\Theta|Z=\nu}) dP_Z(\nu) \quad (77)$$

$$= \int D(P_Z \| P_{Z|\Theta=\theta}) dP_{\Theta}(\theta), \quad (78)$$

where $P_Z$ is the product measure formed by $P_Z$ in (1); and $P_{\Theta}$ is a probability measure such that for all measurable subsets $A$ of $M$,

$$P_{\Theta}(A) = \int P_{\Theta|Z=\nu}(A) dP_Z(\nu); \quad (79)$$

and the conditional probability measure $P_{Z|\Theta}$ satisfies for all measurable subsets $B$ of $(X \times Y)^n$,

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

Note that for all $\theta \in M$, the measure $P_{Z|\Theta=\theta}$ is a product measure formed by a probability measure $P_{Z|\Theta=\theta} \in \Delta(X \times Y)$. More specifically, for all measurable sets of the form $A_1 \times A_2 \times \dots \times A_n$ in $(X \times Y)^n$,

$$P_{Z|\Theta=\theta}(A_1 \times A_2 \times \dots \times A_n) = \prod_{t=1}^{n} P_{Z|\Theta=\theta}(A_t), \quad (81)$$

and for all $t \in \{1, 2, \dots, n\}$,

$$P_Z(A_t) = \int P_{Z|\Theta=\theta}(A_t) dP_{\Theta}(\theta), \quad (82)$$
where the probability measure $P_{\Theta}$ is defined in (79).

The quantity $I(P_{\Theta|Z}; P_Z)$ in (75) is the mutual information [56] between the random variables $\Theta$ and $Z$, which represent the models and (training and test) datasets, when they are jointly sampled from the probability measure $P_{\Theta Z} \in \Delta(M \times (X \times Y)^n)$, whose marginals are $P_{\Theta}$ and $P_Z$ in (79) and (80), respectively. Alternatively, the quantity $L(P_{\Theta|Z}; P_Z)$ in (77) is the lautum information [57] between such random variables $\Theta$ and $Z$. The equality in (81) justifies the following equalities

$$ \frac{1}{n} I(P_{\Theta|Z}; P_Z) = \int D(P_{Z|\Theta=\theta} \| P_Z) dP_{\Theta}(\theta) \quad \text{and} \quad (83) $$

$$ \frac{1}{n} L(P_{\Theta|Z}; P_Z) = \int D(P_Z \| P_{Z|\Theta=\theta}) dP_{\Theta}(\theta), \quad (84) $$

which are well known properties of mutual information [58] and lautum information [57].

## 7.1 Generalization Error of the Gibbs Algorithm

A typical example of a statistical learning algorithm is the Gibbs algorithm, which is parametrized by a positive real $\lambda$ and by a $\sigma$-measure $Q \in \Delta(M, \mathcal{B}(M))$. See for instance, [21]. In the following, the focus is on the case in which $Q$ is a probability measure. Under this assumption, the probability measure representing such an algorithm, which is denoted by $P_{\Theta|Z}^{(Q, \lambda)}$ with $\lambda > 0$, satisfies for all $\theta \in \text{supp} Q$ and for all $z \in (X \times Y)^n$,

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

where the dataset $z$ represents the training dataset; and the function $K_{Q,z}$ : $\mathbb{R} \to \mathbb{R}$ satisfies

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

The generalization error induced by the Gibbs algorithm with parameters $Q$ and $\lambda$, under the assumption that datasets are sampled from a product distribution $P_Z \in \Delta((X \times Y)^n)$ formed by the measure $P_Z$ in (1) is

$$ \bar{\bar{G}}(P_{\Theta|Z}^{(Q, \lambda)}, P_Z), \quad (87) $$

where the functional $\bar{\bar{G}}$ is defined in (74). Such a generalization error satisfies the following property.

**Lemma 9 (Generalization Error of the Gibbs Algorithm)** *The generalization error $\bar{\bar{G}}(P_{\Theta|Z}^{(Q, \lambda)}, P_Z)$ in (87) satisfies*

$$ \bar{\bar{G}}(P_{\Theta|Z}^{(Q, \lambda)}, P_Z) = \lambda \left( I(P_{\Theta|Z}^{(Q, \lambda)}; P_Z) + L(P_{\Theta|Z}^{(Q, \lambda)}; P_Z) \right), \quad (88) $$
where the terms $I(P_{\Theta|Z}^{(Q,\lambda)}; P_Z)$ and $L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z)$ are, respectively, a mutual information and a lautum information:

$$ I(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) \triangleq \int D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \| P_{\Theta}^{(Q,\lambda)}) dP_Z(\nu); \text{ and} \quad (89) $$

$$ L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) \triangleq \int D(P_{\Theta}^{(Q,\lambda)} \| P_{\Theta|Z=\nu}^{(Q,\lambda)}) dP_Z(\nu), \quad (90) $$

with $P_{\Theta}^{(Q,\lambda)}$ being a measure such that for all measurable subsets $A$ of $M$,

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

*Proof:* This result has been proved before in the case in which $Q$ is a probability measure in [15]; and in the more general case in which $Q$ is a $\sigma$-finite measure in [21]. A proof for the particular case in which $Q$ is a probability measure and datasets are formed by independent and identically distributed datapoints is presented in [59] ■

Note that the measures $P_{\Theta}$ in (79); $P_{Z|\Theta=\theta}$ in (80); and $P_{Z|\Theta=\theta}$ in (81) that are specific to the Gibbs algorithm $P_{\Theta|Z}^{(Q,\lambda)}$ in (85) are denoted $P_{\Theta}^{(Q,\lambda)}$; $P_{Z|\Theta=\theta}^{(Q,\lambda)}$; and $P_{Z|\Theta=\theta}^{(Q,\lambda)}$, respectively. That is, $P_{Z|\Theta}^{(Q,\beta)} \in \bigtriangleup ((\mathcal{X} \times \mathcal{Y})^n | M)$ is the conditional probability measure that satisfies

$$ P_Z(B) = \int P_{Z|\Theta=\theta}^{(Q,\beta)}(B) dP_{\Theta}^{(Q,\beta)}(\theta), \quad (92) $$

where $P_{\Theta}^{(Q,\lambda)}$ is defined in (91). For all $\theta \in M$, the measure $P_{Z|\Theta=\theta}^{(Q,\beta)}$ is a product measure formed by a measure $P_{Z|\Theta=\theta}^{(Q,\beta)} \in \bigtriangleup (\mathcal{X} \times \mathcal{Y}|M)$ that satisfies for all measurable sets of the form $A_1 \times A_2 \times \dots \times A_n$ in $(\mathcal{X} \times \mathcal{Y})^n$,

$$ P_{Z|\Theta=\theta}^{(Q,\beta)}(A_1 \times A_2 \times \dots \times A_n) = \prod_{t=1}^{n} P_{Z|\Theta=\theta}^{(Q,\beta)}(A_t) \quad (93) $$

and for all $t \in \{1, 2, \dots, n\}$,

$$ P_Z(A_t) = \int P_{Z|\Theta=\theta}^{(Q,\beta)}(A_t) dP_{\Theta}^{(Q,\beta)}(\theta). \quad (94) $$

Using this notation, it follows that $I(P_{\Theta|Z}^{(Q,\lambda)}; P_Z)$ in (89) and $L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z)$ in (90) also satisfy that

$$ I(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) = I(P_{Z|\Theta=\theta}^{(Q,\lambda)}; P_{\Theta}^{(Q,\lambda)}) \quad (95) $$

$$ = \int D(P_{Z|\Theta=\theta}^{(Q,\lambda)} \| P_Z) dP_{\Theta}^{(Q,\lambda)}(\nu); \text{ and} \quad (96) $$

$$ L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) = L(P_{Z|\Theta=\theta}^{(Q,\lambda)}; P_{\Theta}^{(Q,\lambda)}) \quad (97) $$

$$ = \int D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)}) dP_{\Theta}^{(Q,\lambda)}(\nu). \quad (98) $$
## 7.2 Expressions Involving a WCDG Probability Measure

The generalization error $\overline{\overline{G}}(P_{\Theta|Z}, P_Z)$ in (74) can be re-written as follows:

$$ \overline{\overline{G}}(P_{\Theta|Z}, P_Z) = \iint G(\theta, P_Z, P_z) dP_{\Theta|Z=z}(\theta) dP_Z(z) \quad (99) $$

$$ = \iint G(\theta, P_Z, P_z) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \quad (100) $$

$$ = \iint \left( \int \ell(\theta, x, y) dP_Z(x, y) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) - \iint \left( \int \ell(\theta, x, y) dP_Z(x, y) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \quad (101) $$

$$ = \iint \ell(\theta, x, y) dP_Z(x, y) dP_{\Theta}(\theta) - \iint \left( \frac{1}{n} \sum_{t=1}^{n} \ell(\theta, x_t, y_t) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \quad (102) $$

$$ = \iint \left( \int \ell(\theta, x, y) dP_Z(x, y) - \iint \ell(\theta, x, y) dP_{Z|\Theta=\theta}(z) \right) dP_{\Theta}(\theta) \quad (103) $$

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

where the measures $P_{\Theta|Z}$, $P_{Z|\Theta}$, $P_{\Theta}$, $P_Z$, and $P_Z$ jointly satisfy (79), (80), (81), and (82). In particular, the equality in (100) follows from (79) and (80); the equality in (101) follows from (69); the equality in (102) follows from (28); the equality in (103) follows from the fact that the probability measure $P_{Z|\Theta=\theta}$ is a product measure as in (81); and the equality in (104) follows from (58).

The remaining of this section consists in studying the following expression, which follows immediately from the equality in (104) and Theorem 8,

$$ \overline{\overline{G}}(P_{\Theta|Z}, P_Z) = \beta \int \left( D(P_{Z|\Theta=\theta} \| P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}) - D(P_Z \| P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}) - D(P_{Z|\Theta=\theta} \| P_S) + D(P_Z \| P_S) \right) dP_{\Theta}(\theta), \quad (105) $$

where $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ is the WCDG probability measure defined in (21), whose parameters $P_S$ and $\beta$ have been chosen such that for all $\theta \in \text{supp } P_{\Theta}$, the probability measures $P_Z$ and $P_{Z|\Theta=\theta}$ are absolutely continuous with $P_S$; and for all $\theta \in \text{supp } P_{\Theta}$, $\beta \in \mathcal{J}_{P_S, \theta}$, with the set $\mathcal{J}_{P_S, \theta}$ defined in (20).

The following theorem shows one closed-form expression for the generalization error $\overline{\overline{G}}(P_{\Theta|Z}, P_Z)$ in (74) involving the mutual information in (75).
**Theorem 10** The generalization error $\overline{\overline{G}}(P_{\Theta|Z}, P_Z)$ in (74) satisfies:

$$ \overline{\overline{G}}(P_{\Theta|Z}, P_Z) = -\frac{\beta}{n} I(P_{\Theta|Z}; P_Z) + \beta \int D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) dP_{\Theta}(\theta) \\ - \beta \int D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) dP_{\Theta}(\theta), \quad (106) $$

where the term $I(P_{\Theta|Z}; P_Z)$ is in (75); the measures $P_{\Theta|Z}$, $P_{Z|\Theta}$, $P_{\Theta}$, $P_Z$, and $P_Z$ jointly satisfy (79), (80), (81), and (82); the measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ is the WCDG probability measure in (21), with $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$ being such that for all $\theta \in \text{supp } P_{\Theta}$, the measures $P_Z$ and $P_{Z|\Theta=\theta}$ are absolutely continuous with respect to $P_S$; and for all $\theta \in \text{supp } P_{\Theta}$, $\beta \in \mathcal{J}_{P_S, \theta}$, with the set $\mathcal{J}_{P_S, \theta}$ defined in (20).

*Proof:* The proof follows from the equality in (105) and by noticing that if $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$, then

$$ \int (D(P_{Z|\Theta=\theta} \| P_S) - D(P_Z \| P_S)) dP_{\Theta}(\theta) \quad (107) $$

$$ = \iint \log \left( \frac{dP_{Z|\Theta=\theta}}{dP_S}(z) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) - D(P_Z \| P_S) \quad (108) $$

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

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

$$ = \iint \log \left( \frac{dP_{Z|\Theta=\theta}}{dP_Z}(z) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) \\ + \iint \log \left( \frac{dP_Z}{dP_S}(z) \right) dP_{Z|\Theta=\theta}(z) dP_{\Theta}(\theta) - D(P_Z \| P_S) \quad (111) $$

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

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

$$ = I(P_{Z|\Theta}; P_{\Theta}) \quad (114) $$

$$ = \frac{1}{n} I(P_{\Theta|P_Z}; P_Z), \quad (115) $$

where the equality in (110) follows from observing that if for some measurable set $A \subseteq \mathcal{X} \times \mathcal{Y}$, the probability measure $P_Z$ in (82) satisfies

$$ 0 = P_Z(A) \quad (116) $$

$$ = \int P_{Z|\Theta=\theta}(A) dP_{\Theta}(\theta) \quad (117) $$
then, $P_{\Theta}(\{\theta \in \mathcal{M} : P_{Z|\Theta=\theta}(\mathcal{A}) = 0\}) = 1$, which follows from [60, Theorem 1.6.6]. This implies that for all $\theta \in \text{supp} \mathcal{M}$, the probability measure $P_{Z|\Theta=\theta}$ is absolutely continuous with respect to $P_Z$, almost surely with respect to $P_{\Theta}$. Moreover, the equality in (115) follows from (83). This completes the proof. ■

Note that the proof of Theorem 10 relies on restricting the reference measure $P_S$ to be independent of the model $\theta$. That is, $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$ and cannot be, for instance, $P_S \in \Delta(\mathcal{X} \times \mathcal{Y}|\mathcal{M})$. This observation is important as other results, e.g., Theorem 11, require $P_S \in \Delta(\mathcal{X} \times \mathcal{Y}|\mathcal{M})$.

The generalization error can be strictly negative for a special class of algorithms. The following lemma formalizes this observation.

**Lemma 10** Let $P_{\Theta|Z} \in \Delta(\mathcal{M} | (\mathcal{X} \times \mathcal{Y})^n)$ be an algorithm such that for all $\theta \in \text{supp } P_{\Theta}$, with $P_{\Theta}$ in (79), it satisfies

(a) the probability measure $P_{Z|\Theta=\theta}$ in (81) is identical to the WCDG probability measure $P_{\tilde{Z}|\Theta=\theta}$ in (21), for some reference $P_S \in \Delta(\mathcal{X} \times \mathcal{Y})$ and some real $\beta > 0$; and

(b) the probability measure $P_Z$ in (82) is mutually absolutely continuous with respect to $P_{Z|\Theta=\theta}$ in (81).

Then, the generalization error $\overline{\overline{G}}(P_{\Theta|Z}, P_Z)$ in (74) satisfies:

$$ \overline{\overline{G}}(P_{\Theta|Z}, P_Z) = -\frac{\beta}{n} (I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z)) \le 0, \quad (118) $$

where the terms $I(P_{\Theta|Z}; P_Z)$ and $L(P_{\Theta|Z}; P_Z)$ are defined in (75) and (77).

*Proof:* Under the first assumption of the lemma, it follows that for all $\theta \in \text{supp } P_{\Theta}$, the probability measures $P_{Z|\Theta=\theta}$ in (81) and $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21) are identical. Hence, for all $\theta \in \text{supp } P_{\Theta}$,

$$ D(P_{Z|\Theta=\theta} \| P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}) = 0. \quad (119) $$

Moreover, from the second assumption of the lemma,

$$ \int D(P_Z \| P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}) dP_{\Theta}(\theta) = \int D(P_Z \| P_{Z|\Theta=\theta}) dP_{\Theta}(\theta) \quad (120) $$

$$ = L(P_{Z|\Theta}; P_{\Theta}) \quad (121) $$

$$ = \frac{1}{n} L(P_{\Theta|Z}; P_Z), \quad (122) $$

where (122) follows from (84). Plugging (119) and (122) in Theorem 10 yields the desired equality in (118). The inequality follows from the fact that $\beta > 0$ and both mutual and lautum information are nonnegative, which concludes the proof. ■

Note that if the algorithm $P_{\Theta|Z}$ in Theorem 10 is such that models are chosen independently of the training dataset, i.e., for all $(u, v) \in (\text{supp } P_Z)^n \times (\text{supp } P_Z)^n$,
it holds that $D(P_{\Theta|Z=u} || P_{\Theta|Z=v}) = 0$, then, $I(P_{\Theta|Z}; P_Z) = 0$ and moreover, for all $\theta \in \text{supp } P_{\Theta}$, it holds that

$$D(P_{Z|\Theta=\theta} || P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}) = D(P_Z || P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}), \quad (123)$$

which implies that $\overline{\bar{G}}(P_{\Theta|Z}, P_Z) = 0$. That is, algorithms that neglect the training datasets induce zero generalization error, which is a well-known result.

The following theorem introduces another expression for the generalization error $\overline{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (74) involving the lautum information in (77).

**Theorem 11** Let $P_{\Theta|Z} \in \Delta(M | (\mathcal{X} \times \mathcal{Y})^n)$ be an algorithm such that for all $\theta \in \text{supp } P_{\Theta}$, with $P_{\Theta}$ in (79), the probability measure $P_Z$ in (82) is absolutely continuous with respect to $P_{Z|\Theta=\theta}$ in (81). Then, the generalization error $\overline{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (74) satisfies

$$\overline{\bar{G}}(P_{\Theta|Z}, P_Z) = \frac{\beta}{n} L(P_{\Theta|Z}; P_Z) + \beta \int D\left(P_{Z|\Theta=\theta} || P_{\tilde{Z}|\Theta=\theta}^{(P_Z|\Theta=\theta, \beta)}\right) dP_{\Theta}(\theta) \\ - \beta \int D\left(P_Z || P_{\tilde{Z}|\Theta=\theta}^{(P_Z|\Theta=\theta, \beta)}\right) dP_{\Theta}(\theta), \quad (124)$$

where the term $L(P_{\Theta|Z}; P_Z)$ is defined in (77); the measures $P_{\Theta|Z}$, $P_{Z|\Theta}$, $P_{\Theta}$, $P_Z$, and $P_Z$ jointly satisfy (79), (80), (81), and (82); and the measure $P_{\tilde{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta, \beta})}$ is a WCDG probability measure defined as in (21), such that for all $\theta \in \text{supp } P_{\Theta}$, $\beta \in \mathcal{J}_{P_{Z|\Theta=\theta, \theta}}$, with the set $\mathcal{J}_{P_{Z|\Theta=\theta, \theta}}$ defined as in (20).

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

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

Under the assumptions of Theorem 11 there might exist a $\beta$ that satisfies for all $\theta \in \text{supp } P_{\Theta}$,

$$D(P_Z || P_{\tilde{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta, \beta})}) = 0, \quad (125)$$

which leads to the equality $\overline{\bar{G}}(P_{\Theta|Z}, P_Z) = \frac{\beta}{n} (I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z))$. The following theorem formalizes such an observation.

**Theorem 12** The generalization error $\overline{\bar{G}}(P_{\Theta|Z}, P_Z)$ in (74) satisfies

$$\overline{\bar{G}}(P_{\Theta|Z}, P_Z) = \frac{\beta}{n} (I(P_{\Theta|Z}; P_Z) + L(P_{\Theta|Z}; P_Z)), \quad (126)$$

where the terms $I(P_{\Theta|Z}; P_Z)$ and $L(P_{\Theta|Z}; P_Z)$ are in (75) and (77); the measures $P_{\Theta|Z}$, $P_{Z|\Theta}$, $P_{\Theta}$, and $P_Z$ jointly satisfy (79), (80), (81), and (82); and for all $\theta \in \text{supp } P_{\Theta}$, $\beta$ satisfies (125) and $\beta \in \mathcal{J}_{P_{Z|\Theta=\theta, \theta}}$, with the set $\mathcal{J}_{P_{Z|\Theta=\theta, \theta}}$ defined as in (20).
Proof: The proof is presented in Appendix Q.

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

Note that the exact calculation of the expression in Theorem 11 requires solving a problem of the form in (15) or (16), with a reference measure $P_{Z|\Theta=\theta}$, with $\theta \in \text{supp } P_{\Theta}$. In a nutshell, one WCDG probability measure must be calculated for each model in supp $P_{\Theta}$. Calculating the expression in Theorem 12 is not easier. Obtaining the $\beta$ in (126) requires to verify (125) at least once for all models in supp $P_{\Theta}$. Despite this disproportionate complexity, thanks to this characterization in terms of the WCDG probability measure, Theorem 8 and Theorem 12 might lead to conjecturing that the Gibbs algorithm $P_{\Theta|Z}^{(Q,\lambda)} \in \Delta(M|(X \times Y)^n)$ in (85), with $\beta = n\lambda$, satisfies the equality in (125). The following lemma shows that it is true under a very restrictive condition.

**Lemma 11** Let $P_{\Theta|Z}^{(Q,\lambda)} \in \Delta(M|(X \times Y)^n)$ be the Gibbs algorithm in (85). Then, for all $\theta \in \text{supp } P_{\Theta}^{(Q,\lambda)}$,

$$D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) = 0, \qquad (127)$$

if and only if

$$P_Z\left(\left\{z \in (X \times Y)^n : K_{Q,z}\left(-\frac{1}{\lambda}\right) = c\right\}\right) = 1, \qquad (128)$$

for some real $c \le 0$, where the function $K_{Q,z}$ is defined in (86); the measures $P_{\Theta|Z}^{(Q,\lambda)}$, $P_Z$, $P_{Z|\Theta=\theta}^{(Q,\lambda)}$ and $P_{Z|\Theta=\theta}^{(Q,\lambda)}$ jointly satisfy (91), (92), (93), and (94); and the measure $P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}$ is a WCDG probability measure defined as in (21).

Proof: The proof is presented in Appendix R.

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

The equality in (128) implies that the function $K_{Q,z}$ is invariant with respect to $z$, almost surely with $P_Z$. Note that this is always true if for all $\theta \in \mathcal{M}$, the function $\ell(\cdot, \cdot, \theta)$ in (4) is nonseparable with respect to $P_Z$ (Definition 2). That is, for all $\theta \in \mathcal{M}$,

$$P_Z(\{(x, y) \in X \times Y : \ell(x, y, \theta) = a(\theta)\}) = 1, \qquad (129)$$

for some function $a: \mathcal{M} \to [0, +\infty)$. Nonetheless, this case is uninteresting in the context of machine learning, as the loss function $\ell$ in (4) is invariant with respect to the datapoints almost surely with $P_Z$ in (1). Alternatively, if the function $\ell$ is separable, it is not clear whether the equality in (128) can be met.

The following lemma presents a property of the Gibbs algorithm that leads to the equality $\overline{\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))$, without the need of verifying (127).

**Lemma 12** Let $P_{\Theta|Z}^{(Q,\lambda)} \in \Delta(M|(X \times Y)^n)$ be the Gibbs algorithm in (85). For all $\theta \in \text{supp } P_{\Theta}^{(Q,\lambda)}$, let the measure $P_Z$ in (94) be absolutely continuous with
respect to $P_{Z|\Theta=\theta}^{(Q,\lambda)}$ in (93). Let also $\beta \triangleq n\lambda$ be such that for all $\theta \in \text{supp } P_{\Theta}^{(Q,\lambda)}$, $\beta \in \mathcal{J}_{P_{Z|\Theta=\theta,\theta}^{(Q,\lambda)}}$, with the set $\mathcal{J}_{P_{Z|\Theta=\theta}^{(Q,\lambda)}}$ defined as in (20). Then,

$$ \frac{1}{n} I(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) = \int D(P_{Z|\Theta=\theta}^{(Q,\lambda)} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)},\beta)}) dP_{\Theta}^{(Q,\lambda)}(\theta) \\ - \int D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)},\beta)}) dP_{\Theta}^{(Q,\lambda)}(\theta), \quad (130) $$

where the measures $P_{\Theta|Z}^{(Q,\lambda)}$, $P_Z$, $P_{\hat{Z}}$, $P_{\Theta}^{(Q,\lambda)}$ and $P_{\hat{Z}|\Theta=\theta}^{(Q,\lambda)}$ jointly satisfy (91), (92), (93), and (94).

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

Note that Lemma 12, together with Theorem 11, form an alternative proof for Lemma 9.

## 7.3 Expressions Involving a Gibbs Algorithm

The following lemma introduces another expression for the generalization error $\bar{G}(P_{\Theta|Z}, P_Z)$ in (74) involving a mutual information in (75) and the Gibbs algorithm in (85).

**Theorem 13** Let $P_{\Theta|Z} \in \Delta(\mathcal{M} | (\mathcal{X} \times \mathcal{Y})^n)$ be an algorithm and let $Q \in \Delta(\mathcal{M})$ be a probability measure. If for all $z \in \text{supp } P_Z$, it holds that:

(a) the measures $P_{\Theta|Z=z}$ and $Q$ are mutually absolutely continuous; and

(b) the measure $P_{\Theta|Z=z}$ and $P_{\Theta}$ are mutually absolutely continuous,

then, the generalization error $\bar{G}(P_{\Theta|Z}, P_Z)$ in (74) satisfies:

$$ \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), \quad (131) $$

where the measures $P_{\Theta|Z}$, $P_{\Theta}$, and $P_Z$ jointly satisfy (79), (80), (81), and (82); and the measure $P_{\Theta|Z}^{(Q,\lambda)} \in \Delta(\mathcal{M} | (\mathcal{X} \times \mathcal{Y})^n)$ is defined in (85), with $\lambda > 0$.

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

Theorem 13 allows the calculation of the generalization error of an arbitrary algorithm $P_{\Theta|Z}$ by comparing it with the Gibbs algorithm $P_{\Theta|Z}^{(Q,\lambda)}$ in (85), whose reference measure $Q$ is chosen such that all the instances of the algorithm $P_{\Theta|Z=z}$, obtained with all possible training datasets $z$, are absolutely continuous with $Q$.
# 8 Conclusions and Final Remarks

The WCDG probability measure in Theorem 1 has been shown to be a cornerstone of statistical machine learning. This is backed by the fact that fundamental performance metrics, such as the sensitivity of the expected loss, the sensitivity of the empirical risk, the expected generalization gap, and the generalization error are shown to have closed-form expressions involving such a measure. Interestingly, the WCDG probability measure is a Gibbs probability measure that, for a fixed model, induces an empirical risk that is a sub-Gaussian random variable. All the cumulants of the WCDG are finite and explicit expressions for upper and lower bounds on all cumulants are derived in terms of the cumulants of the reference measure. This analysis has led to the notion of $(\epsilon, \delta)$-robustness, which allows the study of the generalization capabilities of any model when it faces data generated from the WCDG probability measure.

Finally, thanks to the WCDG, the first explicit expressions in terms of information measures of the generalization error for any statistical learning algorithm have been presented. These expressions can be broadly divided into two classes. The first one involves a WCDG probability measure, while the second one involves a Gibbs algorithm. These expressions are formed by the sum of three terms. The first term is either a mutual or lautum information induced by the algorithm between the models and the datasets. The second and third terms are different for the two classes. In the first class, the second term compares via Kullback-Leibler divergence (relative entropy) the posterior probability distribution induced by the algorithm on the datasets with a WCDG probability measure; and the third term compares via KL divergence the marginal of such posterior with the same WCDG probability measure. In the second class, the second term compares via KL divergence the distributions induced on the models by the algorithm and a Gibbs algorithm when both have been training with the same dataset; the third term compares via KL divergence the marginal of the distribution on the models induced by the algorithm with the same Gibbs algorithm. For Gibbs algorithms, the second and third terms jointly become either mutual or lautum information, recovering existing results. This observation reveals the central role of the Gibbs algorithm in the characterization of the generalization error.
# Appendices

## A Proof of Lemma 1

*Proof:* The proof of convexity is as follows. Let $(\gamma_1, \gamma_2) \in \mathbb{R}^2$, with $\gamma_1 \neq \gamma_2$ being fixed. Assume that $J_{P_S, \theta}(\gamma_1) < +\infty$ and $J_{P_S, \theta}(\gamma_2) < +\infty$. Then, for all $\alpha \in (0, 1)$, the following holds

$$ \alpha J_{P_S, \theta}(\gamma_1) + (1 - \alpha) J_{P_S, \theta}(\gamma_2) = \alpha \log \left( \int \exp(\gamma_1 t) dP_S(t) \right) + (1 - \alpha) \log \left( \int \exp(\gamma_2 t) dP_S(t) \right) \quad (132) $$

$$ = \log \left( \left( \int \exp(\gamma_1 t) dP_S(t) \right)^\alpha \right) + \log \left( \left( \int \exp(\gamma_2 t) dP_S(t) \right)^{1-\alpha} \right) \quad (133) $$

$$ = \log \left( \left( \int \exp(\gamma_1 t) dP_S(t) \right)^\alpha \left( \int \exp(\gamma_2 t) dP_S(t) \right)^{1-\alpha} \right) \quad (134) $$

$$ = \log \left( \left( \int \exp(\gamma_1 \alpha t)^p dP_S(t) \right)^{\frac{1}{p}} \left( \int \exp(\gamma_2 (1-\alpha)t)^q dP_S(t) \right)^{\frac{1}{q}} \right) \quad (135) $$

$$ \geq \log \left( \int \exp(\gamma_1 \alpha t) \exp(\gamma_2 (1-\alpha)t) dP_S(t) \right) \quad (136) $$

$$ = \log \left( \int \exp(\gamma_1 \alpha t + \gamma_2 (1-\alpha)t) dP_S(t) \right) \quad (137) $$

$$ = J_{P_S, \theta}(\gamma_1 \alpha + \gamma_2 (1-\alpha)), \quad (138) $$

where the equality in (135) follows with $\alpha \triangleq \frac{1}{p}$ and $1-\alpha \triangleq \frac{1}{q}$; and the inequality in (136) follows from Hölder's inequality [60, Theorem 2.4.5]. This proves the convexity of the function $J_{P_S, \theta}$.

Note that, also from Hölder's inequality [60, Theorem 2.4.5], the equality in (136) holds if and only if there exist two constants $\beta_1$ and $\beta_2$, not simultaneously equal to zero, such that the set

$$ \mathcal{A} = \{ (x, y) \in \mathcal{X} \times \mathcal{Y} : \beta_1 \exp(\gamma_1 \ell(\theta, x, y)) = \beta_2 \exp(\gamma_2 \ell(\theta, x, y)) \} \quad (139) $$

$$ = \left\{ (x, y) \in \mathcal{X} \times \mathcal{Y} : \exp\left(\left(\gamma_1 - \gamma_2\right)\ell(\theta, x, y)\right) = \frac{\beta_2}{\beta_1} \right\} \quad (140) $$

$$ = \left\{ (x, y) \in \mathcal{X} \times \mathcal{Y} : \ell(\theta, x, y) = \frac{\log\left(\frac{\beta_2}{\beta_1}\right)}{(\gamma_1 - \gamma_2)} \right\}, \quad (141) $$

satisfies $P_S(\mathcal{A}) = 1$. Note that if such a set $\mathcal{A}$ exists, the loss function $\ell$ is nonseparable (Definition 2). This proves the strict convexity for separable loss functions.

The proof of monotonicity follows from noticing that for all $(t_1, t_2) \in \{t \in \mathbb{R} : J_{P_S, \theta}(t) < +\infty\}^2$, such that $t_1 < t_2$, it follows that for all $\theta \in \mathcal{M}$ and for all
$(x, y) \in \text{supp } P_S$, the inequality $\exp(t_1\ell(\boldsymbol{\theta}, x, y)) \le \exp(t_2\ell(\boldsymbol{\theta}, x, y))$ holds. This implies that $J_{P_S, \boldsymbol{\theta}}(t_1) \le J_{P_S, \boldsymbol{\theta}}(t_2) < +\infty$, which proves that the function is nondecreasing. Moreover, the equality holds if and only if $P_S(\{(x, y) \in \mathcal{X} \times \mathcal{Y} : \ell(\boldsymbol{\theta}, x, y) = 0\}) = 1$.

The continuity of the function $J_{P_S, \boldsymbol{\theta}}$ follows from observing that for all $\alpha \in \{t \in \mathbb{R} : J_{P_S, \boldsymbol{\theta}}(t) < +\infty\}$, it holds that

$$ \lim_{t \to \alpha} J_{P_S, \boldsymbol{\theta}}(t) = \lim_{t \to \alpha} \log \left( \int \exp(t\ell(\boldsymbol{\theta}, x, y)) dP_S(x, y) \right) \quad (142) $$

$$ = \log \left( \lim_{t \to \alpha} \int \exp(t\ell(\boldsymbol{\theta}, x, y)) dP_S(x, y) \right) \quad (143) $$

$$ = \log \left( \int \lim_{t \to \alpha} \exp(t\ell(\boldsymbol{\theta}, x, y)) dP_S(x, y) \right) \quad (144) $$

$$ = \log \left( \int \exp(\alpha \ell(\boldsymbol{\theta}, x, y)) dP_S(x, y) \right) \quad (145) $$

$$ = J_{P_S, \boldsymbol{\theta}}(\alpha), \quad (146) $$

where equalities in (143) and (145) follow from the fact that both the logarithmic and exponential functions are continuous; and equality in (144) follows from the dominated convergence theorem [60, Theorem 1.6.9]. This proves that the function $J_{P_S, \boldsymbol{\theta}}$ is continuous in the interior of $\{t \in \mathbb{R} : J_{P_S, \boldsymbol{\theta}}(t) < +\infty\}$.

The proof of differentiability follows by considering the transport of the measure $P_S$ from $(\mathcal{X} \times \mathcal{Y}, \mathcal{F}_{\mathcal{X} \times \mathcal{Y}})$ to $([0, +\infty], \mathcal{B}([0, +\infty]))$ through the function $g_{\boldsymbol{\theta}} : \mathcal{X} \times \mathcal{Y} \to [0, +\infty]$ such that $g_{\boldsymbol{\theta}}(x, y) = \ell(\boldsymbol{\theta}, x, y)$, with $\ell$ in (4). Denote the resulting probability measure in $([0, +\infty], \mathcal{B}([0, +\infty]))$ by $T_{P_S, \boldsymbol{\theta}}$. That is, for all $A \in \mathcal{B}([0, +\infty])$,

$$ T_{P_S, \boldsymbol{\theta}}(A) = P(g_{\boldsymbol{\theta}}^{-1}(A)), \quad (147) $$

where the term $g_{\boldsymbol{\theta}}^{-1}(A)$ represents the set

$$ g_{\boldsymbol{\theta}}^{-1}(A) \triangleq \{(x, y) \in \mathcal{X} \times \mathcal{Y} : g_{\boldsymbol{\theta}}(x, y) \in A\}. $$

Hence, the following holds

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

$$ = \log \left( \int \exp(tv) dT_{P_S, \boldsymbol{\theta}}(v) \right), \quad (149) $$

where equality in (149) follows from [60, Theorem 1.6.12].

Denote by $\phi$ the Laplace transform of the measure $P_S$. That is for all $t \in \{x \in \mathbb{R} : J_{P_S, \boldsymbol{\theta}}(x) < +\infty\}$,

$$ \phi(t) = \int \exp(tv) dT_{P_S, \boldsymbol{\theta}}(v). \quad (150) $$
Hence, $\phi(t) = \exp(J_{P_S, \theta}(t))$. From [61, Theorem 1a (page 439)], it follows that the function $\phi$ has derivatives of all orders in $\{t \in \mathbb{R} : J_{P_S, \theta}(t) < +\infty\}$, and thus, so does the function $J_{P_S, \theta}$ in the interior of $\{t \in \mathbb{R} : J_{P_S, \theta}(t) < +\infty\}$. This completes the proof. ■

## B Proof of Lemma 2

*Proof:* Under the assumption that the set $\mathcal{J}_{P_S, \theta}$ is not empty, there always exists a positive $b \in \mathcal{J}_{P_S, \theta}$, such that $J_{P_S, \theta}(\frac{1}{b}) < +\infty$. From Lemma 1, it follows that the function $J_{P_S, \theta}$ is nondecreasing, which implies that $[b, +\infty) \in \mathcal{J}_{P_S, \theta}$. Moreover, let $b^* \in [0, +\infty)$ be

$$b^* \triangleq \inf \mathcal{J}_{P_S, \theta}. \qquad (151)$$

Hence, it follows that $(b^*, +\infty) \in \mathcal{J}_{P_S, \theta}$, which completes the proof. ■

## C Proof of Theorem 1

*Proof:* The optimization problem in (16) can be written as follows:

$$\max_{P \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})} \quad \int \ell(\boldsymbol{\theta}, x, y) \frac{dP}{dP_S}(x, y) dP_S(x, y) \\ - \beta \int \frac{dP}{dP_S}(x, y) \log \left( \frac{dP}{dP_S}(x, y) \right) dP_S(x, y) \qquad (152a)$$

$$\text{s.t.} \quad \int \frac{dP}{dP_S}(x, y) dP_S(x, y) = 1. \qquad (152b)$$

The remainder of the proof focuses on the problem in which the optimization is over the Radon-Nikodym derivative $\frac{dP}{dP_S}$ instead of the measure $P$. This is due to the fact that for all $P \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$, the Radon-Nikodym derivative $\frac{dP}{dP_S}$ is unique up to sets of zero measure with respect to $P_S$.

Let $\mathcal{M}$ be the set of measurable functions $\mathcal{X} \times \mathcal{Y} \to \mathbb{R}$ with respect to the measurable spaces $(\mathcal{X} \times \mathcal{Y}, \mathcal{F}_{\mathcal{X} \times \mathcal{Y}})$ and $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$. Let $\mathcal{S}$ be the subset of $\mathcal{M}$ including all nonnegative functions that are absolutely integrable with respect to $P_S$. That is, for all $h \in \mathcal{S}$, it holds that

$$\int |h(x, y)| dP_S(x, y) < \infty. \qquad (153)$$

Note that the set $\mathcal{M}$ forms a real vector space and the set $\mathcal{S}$ is a convex subset of $\mathcal{M}$. Note also that the constraint in (152b) is satisfied by the probability measure $P_S$, which also satisfies $P_S \in \Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$. Hence, the constraint does not induce an empty feasible set. Finally, note that the optimization problem
in (152) can be written as a minimization of the form:

$$ \min_{g \in \mathcal{S}} - \int g(x, y) \ell(\boldsymbol{\theta}, x, y) dP_S(x, y) + \beta \int g(x, y) \log(g(x, y)) dP_S(x, y), \quad (154a) $$

$$ \text{s. t.} \quad \int g(x, y) dP_S(x, y) = 1, \qquad (154b) $$

where the expression $-\int g(x, y) \ell(\boldsymbol{\theta}, x, y) dP_S(x, y)$ is linear with $g$; the expression $\beta \int g(x, y) \log(g(x, y)) dP_S(x, y)$ is convex with $g$; and $\int g(x, y) dP_S(x, y)$ is linear with $g$.

The proof continues by assuming that the problem in (154) possesses a solution, which is denoted by $g^* \in \mathcal{S}$. Let $\mu_0 \in [0, +\infty)$ be

$$ \mu_0 \triangleq \min_{g \in \mathcal{S}} - \int g(x, y) \ell(\boldsymbol{\theta}, x, y) dP_S(x, y) + \beta \int g(x, y) \log(g(x, y)) dP_S(x, y) $$

$$ = - \int g^*(x, y) \ell(\boldsymbol{\theta}, x, y) dP_S(x, y) + \beta \int g^*(x, y) \log(g^*(x, y)) dP_S(x, y). \quad (155b) $$

Let the Lagrangian of the optimization problem in (154) be the functional $L: \mathcal{S} \times \mathbb{R} \to \mathbb{R}$ such that

$$ L(g, \lambda) = - \int g(x, y) \ell(\boldsymbol{\theta}, x, y) dP_S(x, y) + \beta \int g(x, y) \log(g(x, y)) dP_S(x, y) \\ + \lambda \left( \int g(x, y) dP_S(x, y) - 1 \right), \qquad (156) $$

where $\lambda$ is a real that acts as Lagrangian multiplier for the constraint in (152b). Let $h: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$ be a function in $\mathcal{S}$. The Gateaux differential of the function $L$ in (156) at $(h, \lambda) \in \mathcal{S} \times \mathbb{R}$ in the direction of $g$, if it exists, is

$$ \partial L(g, \lambda; h) \triangleq \frac{d}{d\alpha} r(\alpha) \Big|_{\alpha=0}, \qquad (157) $$

where the function $r: \mathbb{R} \to \mathbb{R}$ is such that for all $\alpha \in (-\epsilon, \epsilon)$, with $\epsilon > 0$ arbitrarily small,

$$ r(\alpha) = - \int (g(x, y) + \alpha h(x, y)) \ell(\boldsymbol{\theta}, x, y) dP_S(x, y) \\ + \beta \int (g(x, y) + \alpha h(x, y)) \log(g(x, y) + \alpha h(x, y)) dP_S(x, y) \\ + \lambda \int (g(x, y) + \alpha h(x, y)) dP_S(x, y) - \lambda, \qquad (158) $$
which can be rewritten as follows,

$$r(\alpha) = \int (\lambda - \ell(\boldsymbol{\theta}, x, y))(g(x, y) + \alpha h(x, y)) dP_S(x, y) \quad (159)$$

$$+\beta \int (g(x, y) + \alpha h(x, y)) \log (g(x, y) + \alpha h(x, y)) dP_S(x, y) - \lambda. \quad (160)$$

Note that the first term in (158) is linear with $\alpha$; the second term can be written using the function $\hat{r}: \mathbb{R} \to \mathbb{R}$ such that

$$\hat{r}(\alpha) = \int (g(x, y) + \alpha h(x, y)) \log (g(x, y) + \alpha h(x, y)) dP_S(x, y); \quad (161)$$

and the third term is independent of $\alpha$.

Hence, based on the fact the function $\hat{r}$ in (161) is differentiable at zero [62, Lemma 9], so is the function $r$ in (158), which implies that the Gateaux differential of $\partial L(g, \lambda; h)$ in (157) exists.

The derivative of the real function $r$ is

$$\frac{d}{d\alpha} r(\alpha) = \frac{d}{d\alpha} \left( \int (\lambda - \ell(\boldsymbol{\theta}, x, y))(g(x, y) + \alpha h(x, y)) dP_S(x, y) \right. \quad (162)$$

$$+\beta \int (g(x,y)+\alpha h(x,y)) \log (g(x,y)+\alpha h(x,y)) dP_S(x,y) - \lambda \right)$$

$$= \int (\lambda - \ell(\boldsymbol{\theta}, x, y)) h(x, y) dP_S(x, y) \quad (163)$$

$$+\beta \int \frac{d}{d\alpha} \left( (g(x,y)+\alpha h(x,y)) \log (g(x,y)+\alpha h(x,y)) \right) dP_S(x,y) \quad (163)$$

$$= \int (\lambda - \ell(\boldsymbol{\theta}, x, y)) h(x, y) dP_S(x, y) \quad (164)$$

$$+\beta \int h(x, y) (1 + \log (g(x, y) + \alpha h(x, y))) dP_S(x, y), \quad (164)$$

where equality in (163) follows from [62, Theorem 5].

From equation (157) and (164), it follows that

$$\partial L(g, \lambda; h) = \int (\lambda - \ell(\boldsymbol{\theta}, x, y)) h(x, y) dP_S(x, y) \quad (165)$$

$$+\beta \int h(x, y) (1 + \log (g(x, y))) dP_S(x, y), \quad (165)$$

$$= \int (\lambda - \ell(\boldsymbol{\theta}, x, y) + \beta (1 + \log (g(x, y)))) h(x, y) dP_S(x, y). \quad (166)$$

A necessary condition [63, Theorem 1, Page 178] for the functional $L$ in (156)

to have an extremum at $\left( \frac{dP_{P_S(\lambda, \beta)}}{dP_S, \lambda} \right) \in \mathcal{S} \times \mathbb{R}$ is that for all functions $h \in \mathcal{S}$,
the following holds,

$$
\begin{align}
0 &= \partial L \left( \frac{\mathrm{d}P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{\mathrm{d}P_S}, \lambda; h \right) \nonumber \\
&= \int h(x,y) \left( \lambda - \ell(\boldsymbol{\theta}, x, y) + \beta \left( 1 + \log \left( \frac{\mathrm{d}P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{\mathrm{d}P_S}(x,y) \right) \right) \right) \mathrm{d}P_S(x,y). \tag{167}
\end{align}
$$

The equality in (167) holds for all functions $h \in \mathcal{S}$ if and only if for all $(x, y) \in$
supp $P_S$, the function $\frac{\mathrm{d}P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{\mathrm{d}P_S}$ satisfies:

$$
\lambda - \ell(\boldsymbol{\theta}, x, y) + \beta \left( 1 + \log \left( \frac{\mathrm{d}P_{\hat{Z}|\boldsymbol{\Theta}=\boldsymbol{\theta}}^{(P_S, \beta)}}{\mathrm{d}P_S}(x, y) \right) \right) = 0. \quad (168)
$$

That is,

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

where $\lambda$ is chosen to satisfy (152b). That is,

$$
\frac{\mathrm{d} P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{\mathrm{d} P_S}(x, y) = \frac{\exp\left(\frac{\ell(\theta, x, y)}{\beta}\right)}{\int \exp\left(\frac{\ell(\theta, x, y)}{\beta}\right) \mathrm{d} P_S(x, y)} \quad (170)
$$

$$
= \exp\left(\frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} - J_{P_S, \boldsymbol{\theta}}\left(\frac{1}{\beta}\right)\right). \quad (171)
$$

The proof continues by verifying that the measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ that satisfies (170)
is the unique solution to the optimization problem in (16). Such verification is
done by showing that the objective function in (16) is strictly concave with the
optimization variable. Let $P_1$ and $P_2$ be two different probability measures in
$\Delta_{P_S}(\mathcal{X} \times \mathcal{Y})$ and let $\alpha$ be in (0,1). Hence,

$$
\begin{align}
& \int \ell(\boldsymbol{\theta}, x, y) \mathrm{d}(\alpha P_1 + (1-\alpha)P_2)(x, y) - \beta D (\alpha P_1 + (1-\alpha)P_2 \| P_S) \nonumber \\
&= \alpha \int \ell(\boldsymbol{\theta}, x, y) \mathrm{d}P_1(x, y) + (1-\alpha) \int \ell(\boldsymbol{\theta}, x, y) \mathrm{d}P_2(x, y) \nonumber \\
& \quad - \beta D (\alpha P_1 + (1-\alpha)P_2 \| P_S) \tag{172}
\end{align}
$$

$$
\begin{align}
&< \alpha \left( \int \ell(\boldsymbol{\theta}, x, y) dP_1(x, y) - \beta D (P_1 \| P_S) \right) \nonumber \\
&\quad + (1-\alpha) \left( \int \ell(\boldsymbol{\theta}, x, y) dP_2(x, y) - \beta D (P_2 \| P_S) \right), \tag{173}
\end{align}
$$

where equality in (172) follows from properties of the Lebesgue integral, while
the inequality in (173) follows from [21, Theorem 2]. Hence, the uniqueness
of the solution is due to the strict concavity of the objective function. This completes the proof of uniqueness.

Based on [59, Theorem 3.1], for the case in which the function $\ell$ is separable (Definition 18), it is proved that if $\beta \in \mathcal{J}_{P_S, \theta}$, is chosen to satisfy

$$D\left(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}\|P_S\right) = \gamma, \qquad (174)$$

with $\gamma$ in (15b), then the solutions to the optimization problems in (15) and (16), denoted by $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$, are identical and satisfy

$$\frac{\mathrm{d}P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{\mathrm{d}P_S}(x, y) = \exp\left(\frac{\ell(\theta, x, y)}{\beta} - J_{P_S, \theta}\left(\frac{1}{\beta}\right)\right), \qquad (175)$$

where the functions $\ell$ and $J_{P_S, \theta}$ are defined in (4) and (19), respectively. This completes the proof. ■

## D Proof of Lemma 3

First, the proof of absolute continuity is presented. For all $C \in \mathcal{F}_{X \times Y}$,

$$P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(C) = \int_C \frac{\mathrm{d}P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{\mathrm{d}P_S}(x, y)\mathrm{d}P_S(x, y), \qquad (176)$$

and thus, if $P_S(C) = 0$, then

$$P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(C) = 0, \qquad (177)$$

which implies the absolute continuity of $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ with respect to $P_S$. Alternatively, given a set $C \in \mathcal{F}_{X \times Y}$, assume that $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(C) = 0$. Hence, it follows that

$$0 = P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(C) = \int_C \frac{\mathrm{d}P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{\mathrm{d}P_S}(x, y)\mathrm{d}P_S(x, y). \qquad (178)$$

From Theorem 1, it holds that 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{\ell(\theta, x, y)}{\beta} - J_{P_S, \theta}\left(\frac{1}{\beta}\right)\right). \qquad (179)$$

Note that if a solution to the optimization problem (16) exists, then $J_{P_S, \theta}(\frac{1}{\beta}) < +\infty$, which implies that $\exp(-J_{P_S, \theta}(\frac{1}{\beta})) > 0$. Moreover, $\exp(\frac{\ell(\theta, x, y)}{\beta}) > 0$, where the strict inequality is due to the fact that for all $(x, y) \in \text{supp } P_S$, the function $\ell$ in (4) is nonnegative. Hence, 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{\ell(\theta, x, y)}{\beta} - J_{P_S, \theta}\left(\frac{1}{\beta}\right)\right) > 0, \qquad (180)$$
which implies that $P_S(C) = 0$ and the absolute continuity of $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ with respect to $P_S$. This completes the first part of the proof.

The second part of the proof continues with the following equalities:

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

$$= \int \log \left( \exp\left(\frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} - J_{P_S, \boldsymbol{\theta}}\left(\frac{1}{\beta}\right)\right) \right) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(x, y) \quad (182)$$

$$= \int \frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(x, y) - J_{P_S, \boldsymbol{\theta}}\left(\frac{1}{\beta}\right) \quad (183)$$

$$= \frac{1}{\beta} \mathbf{R}_{\boldsymbol{\theta}}(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) - J_{P_S, \boldsymbol{\theta}}\left(\frac{1}{\beta}\right), \quad (184)$$

where equality in (182) follows from (21) and the functional $\mathbf{R}_{\boldsymbol{\theta}}$ is defined in (8). This proves the equality in (23).

The equality in (25) is proved as follows:

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

$$= \int \log \left( \exp\left(-\frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} + J_{P_S, \boldsymbol{\theta}}\left(\frac{1}{\beta}\right)\right) \right) dP_S(x, y) \quad (186)$$

$$= - \int \frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} dP_S(x, y) + J_{P_S, \boldsymbol{\theta}}\left(\frac{1}{\beta}\right) \quad (187)$$

$$= -\frac{1}{\beta} \mathbf{R}_{\boldsymbol{\theta}}(P_S) + J_{P_S, \boldsymbol{\theta}}\left(\frac{1}{\beta}\right), \quad (188)$$

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

## E Proof of Lemma 4

The proof of equality in (34) is based on the fact that for a given $t \in \{\nu \in \mathbb{R} : \mathcal{J}_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \boldsymbol{\theta}}(\nu) < +\infty\}$, the function $\mathcal{J}_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \boldsymbol{\theta}}$ satisfies

$$\mathcal{J}_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \boldsymbol{\theta}}(t) = \log \left( \int \exp(t\ell(\boldsymbol{\theta}, x, y)) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(x, y) \right) \quad (189)$$

$$= \log \left( \int \exp(t\ell(\boldsymbol{\theta}, x, y)) \frac{dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}}{dP_S}(x, y) dP_S(x, y) \right) \quad (190)$$

$$= \log \left( \int \exp\left(\left(t + \frac{1}{\beta}\right) \ell(\boldsymbol{\theta}, x, y)\right) dP_S(x, y) - \mathcal{J}_{P_S, \boldsymbol{\theta}}\left(\frac{1}{\beta}\right) \right) \quad (191)$$

$$= \mathcal{J}_{P_S, \boldsymbol{\theta}}\left(t + \frac{1}{\beta}\right) - \mathcal{J}_{P_S, \boldsymbol{\theta}}\left(\frac{1}{\beta}\right), \quad (192)$$
where the equality in (191) follows from (21). Moreover, from Lemma 1, it follows that the function $J_{P_{\hat{Z}|\Theta=\theta}, \theta}^{(P_S, \beta)}$ is continuous and nondecresasing. Hence, for all $s \in (-\infty, t)$, it holds that $J_{P_{\hat{Z}|\Theta=\theta}, \theta}^{(P_S, \beta)}(s) \le J_{P_{\hat{Z}|\Theta=\theta}, \theta}^{(P_S, \beta)}(t) < +\infty$.

Let $t^* \in \mathbb{R} \cup \{+\infty\}$ be defined by

$$t^* \triangleq \sup\{\nu \in \mathbb{R} : J_{P_{\hat{Z}|\Theta=\theta}, \theta}^{(P_S, \beta)}(\nu) < \infty\}. \quad (193)$$

If $t^* = +\infty$, then for all $s \in \mathbb{R}$, $J_{P_{\hat{Z}|\Theta=\theta}, \theta}^{(P_S, \beta)}(s) < +\infty$, and the proof for (34) is completed. Alternatively, if $t^* < +\infty$, it follows that for all $s > t^*$, $J_{P_{\hat{Z}|\Theta=\theta}, \theta}^{(P_S, \beta)}(s) = +\infty$, which implies that $J_{P_S, \theta}(s + \frac{1}{\beta}) = +\infty$, as the function $J_{P_S, \theta}$ is also continuous (Lemma 1) and $J_{P_S, \theta}(\frac{1}{\beta}) < +\infty$ (due to the choice of $\beta$). Hence, in this case, the equality in (34) is of the form $+\infty = +\infty$. This completes the proof of (34).

# F Proof of Lemma 5

*Proof:* Note that for all $t \in \text{int}\mathcal{J}_{P_S, \theta}$, it holds that

$$J_{P_S, \theta}^{(1)}\left(\frac{1}{t}\right) = \left. \frac{d}{ds} \log \left( \int \exp(s\ell(\boldsymbol{\theta}, x, y)) dP_S(x, y) \right) \right|_{s=\frac{1}{t}} \quad (194)$$

$$= \left. \frac{\frac{d}{ds} \int (\exp(s\ell(\boldsymbol{\theta}, x, y))) dP_S(x, y)}{\int \exp(s\ell(\boldsymbol{\theta}, x, y)) dP_S(x, y)} \right|_{s=\frac{1}{t}} \quad (195)$$

$$= \left. \frac{\int \frac{d}{ds} (\exp(s\ell(\boldsymbol{\theta}, x, y))) dP_S(x, y)}{\int \exp(s\ell(\boldsymbol{\theta}, x, y)) dP_S(x, y)} \right|_{s=\frac{1}{t}} \quad (196)$$

$$= \frac{\int \ell(\boldsymbol{\theta}, x, y) \exp\left(\frac{1}{t}\ell(\boldsymbol{\theta}, x, y)\right) dP_S(x, y)}{\int \exp\left(\frac{1}{t}\ell(\boldsymbol{\theta}, x, y)\right) dP_S(x, y)} \quad (197)$$

$$= \exp\left(-J_{P_S, \theta}\left(\frac{1}{t}\right)\right) \int \ell(\boldsymbol{\theta}, x, y) \exp\left(\frac{1}{t}\ell(\boldsymbol{\theta}, x, y)\right) dP_S(x, y) \quad (198)$$

$$= \int \ell(\boldsymbol{\theta}, x, y) \exp\left(\frac{1}{t}\ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}\left(\frac{1}{t}\right)\right) dP_S(x, y) \quad (199)$$

$$= \int \ell(\boldsymbol{\theta}, x, y) dP_{\hat{Z}|\Theta=\theta}^{(P_S, t)}(x, y), \quad (200)$$

where the equality in (196) follows from the dominated convergence theorem [60, Theorem 1.6.9]; and the equality in (200) follows from (21). This completes the proof of (37).
The proof of (38) is as follows,

$$J_{P_S, \theta}^{(2)} \left( \frac{1}{t} \right) = \left. \frac{d}{ds} J_{P_S, \theta}^{(1)}(s) \right|_{s=\frac{1}{t}} \qquad (201)$$

$$= \left. \frac{d}{ds} \left( \int \ell(\boldsymbol{\theta}, x, y) \exp \left( s\ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}(s) \right) dP_S(x, y) \right) \right|_{s=\frac{1}{t}} \qquad (202)$$

$$= \int \frac{d}{ds} \left( \ell(\boldsymbol{\theta}, x, y) \exp \left( s\ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}(s) \right) \right) dP_S(x, y) \Big|_{s=\frac{1}{t}} \qquad (203)$$

$$= \int \ell(\boldsymbol{\theta}, x, y) (\ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}^{(1)}(\frac{1}{t})) \exp\left(\frac{1}{t}\ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}(\frac{1}{t})\right) dP_S(x, y) \qquad (204)$$

$$= \int \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}^{(1)}(\frac{1}{t}) \right)^2 \exp \left( t\ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}(\frac{1}{t}) \right) dP_S(x, y) \\ + \int \ell(\boldsymbol{\theta}, x, y) J_{P_S, \theta}^{(1)}(\frac{1}{t}) \exp \left( \frac{1}{t}\ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}(\frac{1}{t}) \right) dP_S(x, y)$$

$$- J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right)^2 \int \exp \left( \frac{1}{t} \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta} \left(\frac{1}{t}\right) \right) dP_S(x, y) \qquad (205)$$

$$= \int \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}^{(1)}(\frac{1}{t}) \right)^2 \exp \left( \frac{1}{t} \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}(\frac{1}{t}) \right) dP_S(x, y) \\ + J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right)^2 - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right)^2 \int dP_{\tilde{Z}|\Theta=\theta}^{(P_S,t)}(x, y) \qquad (206)$$

$$= \int \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}^{(1)}(\frac{1}{t}) \right)^2 \exp \left( \frac{1}{t} \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}(\frac{1}{t}) \right) dP_S(x, y) \qquad (207)$$

$$= \int \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}^{(1)}(\frac{1}{t}) \right)^2 dP_{\tilde{Z}|\Theta=\theta}^{(P_S,t)}(x, y), \qquad (208)$$

where the equality in (203) follows from the dominated convergence theorem [60, Theorem 1.6.9]; and the equalities in (206) and (208) follow from (21). This completes the proof of (38).

The second part of the proof of Lemma 1 is divided into two parts. First, it is shown that if the function $\ell$ in (4) is nonseparable with respect to the measure $P_S$ (Definition 2), then for all $t \in \{s \in (0, +\infty) : J_{P_S, \theta}(\frac{1}{s}) < +\infty\}$, $J_{P_S, \theta}^{(2)}(\frac{1}{t}) = 0$. Secondly, it shows that if the function $\ell$ is separable, then, for all $t \in \{s \in (0, +\infty) : J_{P_S, \theta}(\frac{1}{s}) < +\infty\}$, $J_{P_S, \theta}^{(2)}(\frac{1}{t}) > 0$.

The first part is as follows. Assume that the function $\ell$ in (4) is nonseparable with respect to the measure $P_S$, i.e., there exists a real $a \ge 0$, such that

$$P_S(\{(x, y) \in \mathcal{X} \times \mathcal{Y} : \ell(\boldsymbol{\theta}, x, y) = a\}) = 1. \qquad (209)$$
Note that from (21) and (38), it holds that

$$J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) = \int \ell(\theta, x, y) dP_{\hat{Z}|\Theta=\theta}^{(P_S, t)}(x, y) \quad (210)$$

$$= \int \ell(\theta, x, y) \exp\left(\frac{1}{t}\ell(\theta, x, y) - J_{P_S, \theta}\left(\frac{1}{t}\right)\right) dP_S(x, y) \quad (211)$$

$$= \int a \exp\left(\frac{a}{t} - \frac{a}{t}\right) dP_S(x, y) \quad (212)$$

$$= a. \quad (213)$$

Note also that from (21) and (38), it holds that

$$J_{P_S, \theta}^{(2)} \left(\frac{1}{t}\right) = \int \left( \ell(\theta, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^2 dP_{\hat{Z}|\Theta=\theta}^{(P_S, t)}(x, y) \quad (214)$$

$$= \int \left( \ell(\theta, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^2 \exp\left(\frac{1}{t}\ell(\theta, x, y) - J_{P_S, \theta} \left(\frac{1}{t}\right)\right) dP_S(x, y) \quad (215)$$

$$= \int (a - a) \exp\left(\frac{a}{t} - \frac{a}{t}\right) dP_S(x, y) \quad (216)$$

$$= 0, \quad (217)$$

which proves that if the function $\ell$ is nonseparable, then $J_{P_S, \theta}^{(2)}(\frac{1}{t}) = 0$. This completes the first part of the proof.

The second part is as follows. Assume that the function $\ell$ is separable with respect to the measure $P_S$. That is, there exists a positive $a$; and two subsets $\mathcal{A}$ and $\mathcal{B}$ of $\mathcal{X} \times \mathcal{Y}$ that are nonnegligible with respect to $P_S$ and verify that for all $(x_1, y_1) \in \mathcal{A}$ and for all $(x_2, y_2) \in \mathcal{B}$,

$$\ell(\theta, x_1, y_1) < a < \ell(\theta, x_2, y_2). \quad (218)$$

Note that the sets $\mathcal{A}$ and $\mathcal{B}$ are disjoint. Hence, from (38), it holds that

$$J_{P_S, \theta}^{(2)} \left(\frac{1}{t}\right) = \int \left( \ell(\theta, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^2 dP_{\hat{Z}|\Theta=\theta}^{(P_S, t)}(x, y) \quad (219)$$

$$= \int_{\mathcal{A}} \left( \ell(\theta, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^2 dP_{\hat{Z}|\Theta=\theta}^{(P_S, t)}(x, y) \\ + \int_{\mathcal{B}} \left( \ell(\theta, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^2 dP_{\hat{Z}|\Theta=\theta}^{(P_S, t)}(x, y)$$

$$+ \int_{\mathcal{X} \times \mathcal{Y} \setminus (\mathcal{A} \cup \mathcal{B})} \left( \ell(\theta, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^2 dP_{\hat{Z}|\Theta=\theta}^{(P_S, t)}(x, y) \quad (220) \\ > 0, \quad (221)$$

where the inequality in (221) is based on the following facts. First, if $a < J_{P_S, \theta}^{(1)}(\frac{1}{t})$, with $a$ in (218), then for all $(x, y) \in \mathcal{A}$, it holds that $\ell(\theta, x, y) < a < J_{P_S, \theta}^{(1)}(\frac{1}{t})$, and thus,

$$\left( \ell(\theta, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^2 > \left( a - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^2. \quad (222)$$
This implies that

$$ \int_A \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \boldsymbol{\theta}}^{(1)} \left(\frac{1}{t}\right) \right)^2 dP_{\tilde{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, t)}(x, y) \quad (223) $$

$$ > \int_A \left( a - J_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{t} \right) \right)^2 dP_{\tilde{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, t)} (x, y) \quad (224) $$

$$ > \left( a - J_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{t} \right) \right)^2 P_{\tilde{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, t)} (A) \quad (225) $$

$$ > 0, \quad (226) $$

where the inequality in (226) follows from the fact that the probability measures $P_{\tilde{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, t)}$ and $P_S$ are mutually absolutely continuous (Lemma 3). Second, if $a \ge J_{P_S, \boldsymbol{\theta}}^{(1)}(\frac{1}{t})$, with $a$ in (218), then for all $(x, y) \in \mathcal{B}$, it holds that $\ell(\boldsymbol{\theta}, x, y) > a \ge J_{P_S, \boldsymbol{\theta}}^{(1)}(\frac{1}{t})$, and thus,

$$ \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{t} \right) \right)^2 > \left( a - J_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{t} \right) \right)^2, \quad (227) $$

which implies

$$ \int_{\mathcal{B}} \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{t} \right) \right)^2 dP_{\tilde{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, t)} (x, y) \quad (228) $$

$$ > \int_{\mathcal{B}} \left( a - J_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{t} \right) \right)^2 dP_{\tilde{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, t)} (x, y) \quad (229) $$

$$ > \left( a - J_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{t} \right) \right)^2 P_{\tilde{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, t)} (\mathcal{B}) \quad (230) $$

$$ > 0, \quad (231) $$

where the inequality in (231) follows from the fact that the probability measures $P_{\tilde{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, t)}$ and $P_S$ are mutually absolutely continuous (Lemma 3). This completes the second part of the proof.
Finally, the proof of (39) is as follows,

$$ J_{P_S, \theta}^{(3)} \left( \frac{1}{t} \right) = \frac{d}{ds} J_{P_S, \theta}^{(2)}(s) \Big|_{s=\frac{1}{t}} \qquad (232) $$

$$ = \int \frac{d}{ds} \left( \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}^{(1)}(s) \right)^2 \exp\left(s\ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}(s)\right) \right) \Big|_{s=\frac{1}{t}} dP_S(x, y) \quad (233) $$

$$ = \int 2J_{P_S, \theta}^{(2)} \left(\frac{1}{t}\right) \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right) \exp \left( \frac{1}{t} \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta} \left(\frac{1}{t}\right) \right) \\ + \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^3 \exp \left( \frac{1}{t} \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta} \left(\frac{1}{t}\right) \right) dP_S(x, y) \quad (234) $$

$$ = 2J_{P_S, \theta}^{(2)} \left(\frac{1}{t}\right) \int \ell(\boldsymbol{\theta}, x, y) dP_{\tilde{Z}|\Theta=\theta}^{(P_S, t)}(x, y) - 2J_{P_S, \theta}^{(2)} \left(\frac{1}{t}\right) J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \\ + \int \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^3 dP_{\tilde{Z}|\Theta=\theta}^{(P_S, t)}(x, y) \quad (235) $$

$$ = \int \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \theta}^{(1)} \left(\frac{1}{t}\right) \right)^3 dP_{\tilde{Z}|\Theta=\theta}^{(P_S, t)}(x, y), \quad (236) $$

where the equality in (233) follows from the dominated convergence theorem [60, Theorem 1.6.9]; and the equalities in (235) and (236) follow from (21), (37) and (38). This completes the proof of (39).

The proofs for the equalities in (40), (41) and (42) follow along the same arguments as above. ■

## G Proof of Theorem 2

*Proof:* A direct result from Lemma 1 and the mean value theorem [53, Theorem 5.10] is

$$ J_{P_S, \theta}^{(m)} \left( \frac{1}{t} \right) - J_{P_S, \theta}^{(m)}(0) = \frac{1}{t} J_{P_S, \theta}^{(m+1)} \left( \frac{1}{s} \right) < +\infty, \quad (237) $$

for some $s \in (t, +\infty)$. Under the assumption that there exists real $\delta > 0$ such that the function $J_{P_S, \theta}$ in (19) is differentiable within $(-\delta, \delta)$, it follows that the function $J_{P_S, \theta}^{(m+1)}$ is continuous in $(-\delta, +\infty)$, where $\delta > 0$. Hence, for all $t > 0$, the function $J_{P_S, \theta}^{(m+1)}$ achieves a maximum and a minimum within the interval $[0, \frac{1}{t}]$. Such extremas allow providing lower and upper bounds on $J_{P_S, \theta}^{(m)}(\frac{1}{t})$ along with $J_{P_S, \theta}^{(m)}(0)$. This completes the proof. ■
H Proof of Theorem 3

*Proof:* The proof of Theorem 3 uses the following preliminary result.

**Theorem 14** For all $t \in \mathbb{R}$, the function $J_{P_{\tilde{Z}|\Theta=\theta}, \theta}$ in (33) verifies the following equality

$$J_{P_{\tilde{Z}|\Theta=\theta}, \theta}(t) = t J_{P_S, \theta}^{(1)}\left(\frac{1}{\beta}\right) + \frac{1}{2} t^2 J_{P_S, \theta}^{(2)}(\zeta_t), \quad (238)$$

with

$$\zeta_t \in \left( \min\left\{\frac{1}{\beta}, t + \frac{1}{\beta}\right\}, \max\left\{\frac{1}{\beta}, t + \frac{1}{\beta}\right\} \right), \quad (239)$$

where the functions $J_{P_S, \theta}^{(1)}$ and $J_{P_S, \theta}^{(2)}$ are defined in (37) and (38), respectively.

*Proof:* From Lemma 1, it follows that the function $J_{P_S, \theta}$ is continuous, monotone, increasing and differentiable infinitely many times. Then, a Taylor expansion of $J_{P_S, \theta}$ at the point $\frac{1}{\beta}$ yields for all $t \in \{\nu \in \mathbb{R} : J_{P_S, \theta}(\nu) < +\infty\}$,

$$J_{P_S, \theta}(t) = J_{P_S, \theta}\left(\frac{1}{\beta}\right) + \sum_{s=1}^{+\infty} \frac{J_{P_S, \theta}^{(s)}\left(\frac{1}{\beta}\right)}{s!} \left(t - \frac{1}{\beta}\right)^s. \quad (240)$$

Choosing $t = \alpha + \frac{1}{\beta}$ in (240) with $\alpha \in \{\nu \in \mathbb{R} : J_{P_S, \theta}(\nu + \frac{1}{\beta}) < +\infty\}$, it holds from the Taylor-Lagrange theorem [64, Theorem 2.5.5] that

$$J_{P_S, \theta}\left(\alpha + \frac{1}{\beta}\right) = J_{P_S, \theta}\left(\frac{1}{\beta}\right) + \alpha J_{P_S, \theta}^{(1)}\left(\frac{1}{\beta}\right) + \frac{1}{2}\alpha^2 J_{P_S, \theta}^{(2)}(\xi), \quad (241)$$

where $\xi \in \left(\min\left\{\frac{1}{\beta}, \alpha + \frac{1}{\beta}\right\}, \max\left\{\frac{1}{\beta}, \alpha + \frac{1}{\beta}\right\}\right)$.

The equality in (241) leads to the following equality:

$$J_{P_S, \theta}\left(\alpha + \frac{1}{\beta}\right) - J_{P_S, \theta}\left(\frac{1}{\beta}\right) = \alpha J_{P_S, \theta}^{(1)}\left(\frac{1}{\beta}\right) + \frac{1}{2}\alpha^2 J_{P_S, \theta}^{(2)}(\zeta_t), \quad (242)$$

where $\zeta_t$ is chosen as in (239).

Let $s^* \in \mathbb{R} \cup \{+\infty\}$ be defined by

$$s^* \triangleq \sup\{\alpha \in \mathbb{R} : J_{P_S, \theta}\left(\alpha + \frac{1}{\beta}\right) < \infty\} \quad (243)$$

If $s^* = +\infty$, then for all $\alpha \in \mathbb{R}$, $J_{P_S, \theta}(\alpha + \frac{1}{\beta}) - J_{P_S, \theta}(\frac{1}{\beta}) < +\infty$, thus, the proof is completed by noticing that from Lemma 4, it holds that $J_{P_{\tilde{Z}|\Theta=\theta}, \theta}(\alpha) = J_{P_S, \theta}(\alpha + \frac{1}{\beta}) - J_{P_S, \theta}(\frac{1}{\beta})$. Hence, choosing $\zeta_t$ as in (239) leads to the desired equality in (238).
Alternatively, if $s^* < +\infty$, it follows that for all $\alpha > s^*$, $J_{P_S, \theta}(\alpha + \frac{1}{\beta}) = +\infty$. From Lemma 4, it follows that $J_{P_{\hat{Z}|\Theta=\theta}, \theta}(\alpha) = +\infty$, which implies that $+\infty = \alpha J_{P_S, \theta}(\frac{1}{\beta}) + \frac{1}{2}\alpha^2 J_{P_S, \theta}(\zeta_t)$, and thus $J_{P_S, \theta}^{(2)}(\zeta_t) = +\infty$. Hence, in this case, the inequality in (46) is of the form $+\infty = +\infty$. This completes the proof. ■

Finally, the proof of the inequality in (46) follows from Theorem 14 and by
noticing that from Lemma 2 and Lemma 4, it holds that

$$
\{\alpha \in \mathbb{R} : J_{P_{\hat{Z}|\Theta=\theta}}^{(P_S, \beta)}(\theta)(\alpha) < +\infty\} = \{\alpha \in \mathbb{R} : J_{P_S, \theta}(\alpha + \frac{1}{\beta}) < +\infty\}, (244)
$$

which implies that the set $\{\alpha \in \mathbb{R} : \mathcal{J}_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(\theta)(\alpha) < +\infty\}$ is an interval of the
form $(-\infty, b - \frac{1}{\beta})$, which justifies the choice of $\zeta_{P_S, \theta}$ in (47).

I Proof of Lemma 6

*Proof:* The proof follows from the following equalities,

$$
\frac{d}{d\beta} D \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S \right) = \frac{d}{d\beta} \left( \frac{1}{\beta} \mathbf{R}_{\theta} \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) - J_{P_S, \theta} \left( \frac{1}{\beta} \right) \right) \quad (245)
$$

$$
= \frac{d}{d\beta} \left( \frac{1}{\beta} \mathcal{J}_{P_S, \theta}^{(1)} \left( \frac{1}{\beta} \right) - \mathcal{J}_{P_S, \theta} \left( \frac{1}{\beta} \right) \right) \quad (246)
$$

$$
= -\frac{1}{\beta^2} \mathcal{J}_{P_S, \theta}^{(1)} \left( \frac{1}{\beta} \right) - \frac{1}{\beta^3} \mathcal{J}_{P_S, \theta}^{(2)} \left( \frac{1}{\beta} \right) + \frac{1}{\beta^2} \mathcal{J}_{P_S, \theta}^{(1)} \left( \frac{1}{\beta} \right) \quad (247)
$$

$$
= -\frac{1}{\beta^3} \mathcal{J}_{P_S, \theta}^{(2)} \left( \frac{1}{\beta} \right), \qquad (248)
$$

where the equality in (245) follows from (23) and the equality in (246) follows
from (37). This completes the proof.
■

J Proof of Theorem 4

*Proof:* Let $\mathcal{A}$ be a set such that

$$
\mathcal{A} \triangleq \{z \in (\mathcal{X} \times \mathcal{Y})^n : \exp(t\mathcal{L}(\theta, z)) \ge \exp(t\delta)\}, \quad (249)
$$

with $t \in \mathcal{J}_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}$ and $\delta > \mathcal{J}_{P_{S, \theta}^{(1)}, \theta}(\frac{1}{\beta})$, where the set $\mathcal{J}_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}$ is defined as
in (20). Hence, it follows that

$$
\exp \left( \mathcal{J}_{P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}, \theta}(t) \right) = \int \exp (tL(\theta, z)) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(z) \quad (250)
$$

$$
\geq \int_{\mathcal{A}} \exp(tL(\theta, z)) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(z) \quad (251)
$$

$$
\geq \exp(t\delta) \int_{\mathcal{A}} dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(z) \quad (252)
$$

$$
= \exp(t\delta) P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(\mathcal{A}), \quad (253)
$$
where equality in (250) follows from (19) with $P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}$ as a product measure constructed by $P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}$ in (21).

Note that

$$ \mathcal{A} = \{z \in (\mathcal{X} \times \mathcal{Y})^n : \exp(t\mathbf{L}(\theta, z)) \geq \exp(t\delta)\}, \quad (254) $$

is equivalent to

$$ \mathcal{A} = \{z \in (\mathcal{X} \times \mathcal{Y})^n : \mathbf{L}(\theta, z) \geq \delta\}, \quad (255) $$

from the fact that $t > 0$.

Hence, it follows from (253) and (255) that

$$ \begin{aligned} & P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}(\{z \in (\mathcal{X} \times \mathcal{Y})^n : \mathbf{L}(\theta, z) \geq \delta\}) \\ & \leq \frac{\exp\left(\mathbf{J}_{P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}(\theta)}(t)\right)}{\exp(t\delta)} \end{aligned} \quad (256) $$

$$ = \frac{\int \exp(t\mathbf{L}(\theta, z)) dP_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}(z)}{\exp(t\delta)} \quad (257) $$

$$ = \frac{\int \exp\left(t \frac{1}{n} \sum_{i=1}^{n} \ell(\theta, x_i, y_i)\right) dP_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}(z)}{\exp(t\delta)} \quad (258) $$

$$ = \frac{\left(\int \exp\left(\frac{t}{n}\ell(\theta, x, y)\right) dP_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}(x, y)\right)^n}{\exp(t\delta)} \quad (259) $$

$$ = \frac{\left(\exp\left(\mathbf{J}_{P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}(\theta)}\left(\frac{t}{n}\right)\right)\right)^n}{\exp(t\delta)} \quad (260) $$

$$ = \exp\left(n\mathbf{J}_{P_S,\theta}\left(\frac{t}{n} + \frac{1}{\beta}\right) - n\mathbf{J}_{P_S,\theta}\left(\frac{1}{\beta}\right) - t\delta\right), \quad (261) $$

where equality in (261) follows from (34).

Furthermore,

$$ \begin{aligned} & P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}(\{z \in (\mathcal{X} \times \mathcal{Y})^n : \mathbf{L}(\theta, z) \geq \delta\}) \\ & \leq \exp\left(n\mathbf{J}_{P_S,\theta}\left(\frac{t^*}{n} + \frac{1}{\beta}\right) - n\mathbf{J}_{P_S,\theta}\left(\frac{1}{\beta}\right) - t^*\delta\right) \end{aligned} \quad (262) $$

$$ = \exp\left(n\left(\mathbf{J}_{P_S,\theta}\left(\frac{t^*}{n} + \frac{1}{\beta}\right) - \mathbf{J}_{P_S,\theta}\left(\frac{1}{\beta}\right) - \frac{t^*}{n}\delta\right)\right), \quad (263) $$

where $t^* \in \mathcal{J}_{P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}, \theta}$ is

$$ t^* \in \arg \min_{t \in \mathcal{J}_{P_{\tilde{Z}|\Theta=\theta}^{(P_S,\beta)}, \theta}} \mathbf{J}_{P_S, \theta}\left(\frac{t}{n} + \frac{1}{\beta}\right) - \frac{t}{n}\delta. \quad (264) $$
Note that $J_{P_S, \theta}(\frac{t}{n} + \frac{1}{\beta}) - \frac{t}{n}\delta$ is strictly convex with $t$. Hence, there always exists a $t$ that satisfies the following:

$$0 = \frac{d}{dt} \left( J_{P_S, \theta} \left( \frac{t}{n} + \frac{1}{\beta} \right) - \frac{t}{n} \delta \right) \quad (265)$$

$$= \frac{1}{n} J_{P_S, \theta}^{(1)} \left( \frac{t}{n} + \frac{1}{\beta} \right) - \frac{1}{n} \delta. \quad (266)$$

Let $\beta^* > 0$ be

$$\frac{1}{\beta^*} \triangleq \frac{t^*}{n} + \frac{1}{\beta}. \quad (267)$$

Hence, from (266), it holds that $\beta^*$ satisfies

$$\delta = J_{P_S, \theta}^{(1)} \left( \frac{1}{\beta^*} \right), \quad (268)$$

and the inequality in (262) becomes

$$\begin{aligned} & P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(\{z \in (\mathcal{X} \times \mathcal{Y})^n : \mathcal{L}(\theta, z) \ge \delta\}) \\ & \le \exp \left( n \left( J_{P_S, \theta}\left(\frac{1}{\beta^*}\right) - J_{P_S, \theta}\left(\frac{1}{\beta}\right) - \left(\frac{1}{\beta^*} - \frac{1}{\beta}\right) J_{P_S, \theta}^{(1)}\left(\frac{1}{\beta^*}\right) \right) \right), \quad (269) \end{aligned}$$

Note that

$$\begin{aligned} & J_{P_S, \theta} \left( \frac{1}{\beta^*} \right) - J_{P_S, \theta} \left( \frac{1}{\beta} \right) - \left( \frac{1}{\beta^*} - \frac{1}{\beta} \right) \int \ell(\theta, x, y) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta^*)}(x, y) \\ &= \frac{1}{\beta^*} \int \ell(\theta, x, y) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta^*)}(x, y) - D \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta^*)} \| P_S \right) - J_{P_S, \theta} \left( \frac{1}{\beta} \right) \\ &\quad - \left( \frac{1}{\beta^*} - \frac{1}{\beta} \right) \int \ell(\theta, x, y) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta^*)}(x, y) \end{aligned} \quad (270)$$

$$= \frac{1}{\beta} \left( \int \ell(\theta, x, y) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta^*)}(x, y) - \int \ell(\theta, x, y) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(x, y) \right) \\ + D \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S \right) - D \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta^*)} \| P_S \right), \quad (271)$$

$$= \frac{1}{\beta} \left( \mathbf{R}_{\theta} \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta^*)} \right) - \mathbf{R}_{\theta} \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) \right) \quad (272)$$

$$+ D \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S \right) - D \left( P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta^*)} \| P_S \right), \quad (273)$$

where equalities in (270) and (273) both follow from (23); and the function $\mathbf{R}_{\theta}$ is in (8).
Note that the relative entropy $D(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)} || P_S)$ satisfies:

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

$$= \int \left( \frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} - J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right) \right) dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}(x, y) \quad (275)$$

$$= \int \frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}(x, y) - J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right) \quad (276)$$

$$= \frac{1}{\beta} R_{\theta}(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}) - J_{P_S, \theta} \left( \frac{1}{\beta} \right), \quad (277)$$

where the equality in (275) follows from (21).

The proof continues by noticing that the relative entropies $D(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)} || P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)})$ and $D(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)} || P_S)$ satisfy:

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

$$= \int \left( \log \left( \frac{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}}{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}(x, y) \right) - \log \left( \frac{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}}{dP_S}(x, y) \right) \right) dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}(x, y) \quad (279)$$

$$= \int \log \left( \frac{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}}{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}(x, y) \frac{dP_S}{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}}(x, y) \right) dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}(x, y) \quad (280)$$

$$= \int \log \left( \frac{dP_S}{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}(x, y) \right) dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}(x, y) \quad (281)$$

$$= \int \log \left( \exp \left( -\frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} + J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right) \right) \right) dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}(x, y) \quad (282)$$

$$= \int \left( -\frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} + J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right) \right) dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}(x, y) \quad (283)$$

$$= - \int \frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}(x, y) + J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right) \quad (284)$$

$$= -\frac{1}{\beta} R_{\theta}(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta^*)}) + J_{P_S, \theta} \left( \frac{1}{\beta} \right). \quad (285)$$
Therefore, from (277) and (285), it follows that

$$ 
\begin{aligned}
& D(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta^*)} \| P_S) - D(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta^*)} \| P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}) - D(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S) \\
&= \frac{1}{\beta} \mathrm{R}_{\theta}(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta^*)}) - \frac{1}{\beta} \mathrm{R}_{\theta}(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}).
\end{aligned} 
\quad (286) $$

Plugging (286) into (273) yields

$$ 
\begin{aligned}
& J_{P_S, \theta} \left( \frac{1}{\beta^*} \right) - J_{P_S, \theta} \left( \frac{1}{\beta} \right) - \left( \frac{1}{\beta^*} - \frac{1}{\beta} \right) \int \ell(\theta, x, y) d P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta^*)}(x, y) \\
&= -D \left( P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta^*)} \| P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)} \right).
\end{aligned} 
\quad (287) $$

Plugging (287) into (269) yields

$$ P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}(\{z \in (\mathcal{X} \times \mathcal{Y})^n : \mathbf{L}(\theta, z) \ge \delta\}) \le \exp(-nD(P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta^*)} \| P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)})). \quad (288) $$

This completes the proof.

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

## K Proof of Theorem 5

Consider the random variable $\ell(\theta, X, Y)$, with $(X, Y) \sim P_Z$, with $P_Z \in \mathcal{N}(P_S, \gamma)$. From Chebyshev's inequality [60, Section 2.4.9], it follows that

$$ P_Z(\{z \in (\mathcal{X} \times \mathcal{Y})^n : \mathbf{L}(\theta, z) \ge \delta\}) \le \frac{1}{\delta} \mathrm{R}_{\theta}(P_Z) \quad (289) $$

$$ \le \frac{1}{\delta} J_{P_S, \theta}^{(1)} \left( \frac{1}{\beta} \right), \quad (290) $$

where the functional $\mathrm{R}_{\theta}$ is defined in (8) and the inequality in (290) follows from the fact that for all $P_Z \in \mathcal{N}(P_S, \gamma)$,

$$ \mathrm{R}_{\theta}(P_Z) \le \mathrm{R}_{\theta} \left( P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)} \right) = J_{P_S, \theta}^{(1)} \left( \frac{1}{\beta} \right), \quad (291) $$

with the measure $P_{\tilde{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21). This completes the proof.
L Proof of Theorem 6

The proof follows from Theorem 1 and by noticing that the relative entropy $D(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}||P_S)$ satisfies:

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

$$= \int \left( \frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} - J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right) \right) dP_{\hat{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, \beta)}(x, y) \quad (293)$$

$$= \int \frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} dP_{\hat{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, \beta)}(x, y) - J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right) \quad (294)$$

$$= \frac{1}{\beta} R_{\boldsymbol{\theta}}(P_{\hat{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, \beta)}) - J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right), \quad (295)$$

where the equality in (293) follows from (21) and the function $R_{\boldsymbol{\theta}}$ is in (8). The proof continues by noticing that the relative entropies $D(P||P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)})$ and $D(P||P_S)$ satisfy:

$$D(P||P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}) - D(P||P_S) = \int \log \left( \frac{dP}{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}(x,y) \right) dP(x,y) - \int \log \left( \frac{dP}{dP_S}(x,y) \right) dP(x,y) \quad (296)$$

$$= \int \left( \log \left( \frac{dP}{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}(x,y) \right) - \log \left( \frac{dP}{dP_S}(x,y) \right) \right) dP(x,y) \quad (297)$$

$$= \int \log \left( \frac{dP}{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}(x,y) \frac{dP_S}{dP}(x,y) \right) dP(x,y) \quad (298)$$

$$= \int \log \left( \frac{dP_S}{dP_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}}(x,y) \right) dP(x,y) \quad (299)$$

$$= \int \log \left( \exp \left( -\frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} + J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right) \right) \right) dP(x, y) \quad (300)$$

$$= \int \left( -\frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} + J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right) \right) dP(x, y) \quad (301)$$

$$= - \int \frac{\ell(\boldsymbol{\theta}, x, y)}{\beta} dP(x, y) + J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right) \quad (302)$$

$$= -\frac{1}{\beta} R_{\boldsymbol{\theta}}(P) + J_{P_S, \boldsymbol{\theta}} \left( \frac{1}{\beta} \right). \quad (303)$$
Therefore, from (295) and (303), it follows that

$$ 
\begin{aligned}
& D(P\|P_S) - D(P\|P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}) - D(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}\|P_S) \\
&= \frac{1}{\beta}R_{\theta}(P) - \frac{1}{\beta}R_{\theta}(P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)})
\end{aligned} 
\quad (304) $$

$$ = \frac{1}{\beta} G(\theta, P, P_{\hat{Z}|\Theta=\theta}^{(P_S,\beta)}), \quad (305) $$

which completes the proof.

## M Proof of Theorem 7

The proof of Theorem 7 requires the following lemma.

**Lemma 13** Given two probability measures $P_1$ and $P_2$ over the measurable space $(\mathcal{X} \times \mathcal{Y}, \mathcal{F}_{\mathcal{X}\times\mathcal{Y}})$, with $P_2$ absolutely continuous with respect to $P_1$, the following holds for all $\theta \in \mathcal{M}$,

$$ G(\theta, P_2, P_1) \le \inf_{t>0} \left( \frac{D(P_2\|P_1)}{t} + \frac{1}{t} \log \left( \int \exp \left( t \left( \ell(\theta, x, y) - \int \ell(\theta, x, y)dP_1(x, y) \right) \right) \right) dP_1(x, y) \right), \quad (306) $$

where the function $\ell$ and the functional $G(\theta, P_2, P_1)$ are defined in (4) and in (58), respectively.

*Proof:* From [65, Corollary 4.15, Page 100], it follows that the probability measures $P_1$ and $P_2$ in $(\mathcal{X} \times \mathcal{Y}, \mathcal{F}_{\mathcal{X}\times\mathcal{Y}})$ satisfy the following equality:

$$ D(P_2\|P_1) = \sup_f \int f(x,y)dP_2(x,y) - \log \int \exp(f(x,y))dP_1(x,y), \quad (307) $$

where the supremum is over the space of all measurable functions $f$ with respect to $(\mathcal{X} \times \mathcal{Y}, \mathcal{F}_{\mathcal{X}\times\mathcal{Y}})$ and $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$, such that $\int \exp(f(x,y))dP_1(x,y) < \infty$. Hence, for all $z \in (\mathcal{X} \times \mathcal{Y})^n$ and for all $\theta \in \mathcal{M}$; and for all $t \in (0, +\infty)$, it
follows that the function $\ell$ in (4) satisfies that

$$ D(P_2 \| P_1) \geq \int t\ell(\boldsymbol{\theta}, x, y)dP_2(x, y) - \log \int \exp(t\ell(\boldsymbol{\theta}, x, y))dP_1(x, y) \quad (308) $$

$$ = \int t\ell(\boldsymbol{\theta}, x, y)dP_2(x, y) - \log \int \exp \left( t\ell(\boldsymbol{\theta}, x, y) + t \int \ell(\boldsymbol{\theta}, u, v)dP_1(u, v) - t \int \ell(\boldsymbol{\theta}, u, v)dP_1(u, v) \right) dP_1(x, y) \quad (309) $$

$$ = \int t\ell(\boldsymbol{\theta}, x, y)dP_2(x, y) - t \int \ell(\boldsymbol{\theta}, u, v)dP_1(u, v) - \log \int \exp \left( t\ell(\boldsymbol{\theta}, x, y) - t \int \ell(\boldsymbol{\theta}, u, v)dP_1(u, v) \right) dP_1(x, y) \quad (310) $$

$$ = tG(\boldsymbol{\theta}, P_2, P_1) - \log \int \exp \left( t\ell(\boldsymbol{\theta}, x, y) - t \int \ell(\boldsymbol{\theta}, u, v)dP_1(u, v) \right) dP_1(x, y), \quad (311) $$

which leads to

$$ G(\boldsymbol{\theta}, P_2, P_1) \leq \frac{D(P_2 \| P_1)}{t} + \frac{1}{t} \log \left( \int \exp \left( t \left( \ell(\boldsymbol{\theta}, x, y) - \int \ell(\boldsymbol{\theta}, u, v)dP_1(u, v) \right) \right) dP_1(x, y) \right). \quad (312) $$

Given that $t$ can be chosen arbitrarily in $(0, +\infty)$, it holds that

$$ G(\boldsymbol{\theta}, P_2, P_1) \leq \inf_{t>0} \left( \frac{D(P_2 \| P_1)}{t} + \frac{1}{t} \log \left( \int \exp \left( t \left( \ell(\boldsymbol{\theta}, x, y) - \int \ell(\boldsymbol{\theta}, x, y)dP_1(x, y) \right) \right) dP_1(x, y) \right) \right), \quad (313) $$

which completes the proof of the lemma.

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

The proof of Theorem M continues from here. From Lemma 13, it holds that the probability measure $P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}$ in (21), satisfies for all $P \in \Delta_{P_S}(\chi \times \mathcal{Y})$,

$$ G(\boldsymbol{\theta}, P, P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) \leq \inf_{t>0} \left( \frac{D(P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)})}{t} + \frac{1}{t} \log \left( \int \exp \left( t \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{\beta} \right) \right) \right) dP_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}(x, y) \right) \right), \quad (314) $$
where $J_{P_S, \theta}^{(1)}(\frac{1}{\beta})$ is in (37). Moreover, for all $t \in (0, +\infty)$,

$$ \log \left( \int \exp \left( t \left( \ell(\boldsymbol{\theta}, x, y) - J_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{\beta} \right) \right) \right) dP_{\hat{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, \beta)}(x, y) \right) = \log \left( \int \exp(t\ell(\boldsymbol{\theta}, x, y)) dP_{\hat{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, \beta)}(x, y) \right) - tJ_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{\beta} \right) \quad (315) $$

$$ = J_{P_{\hat{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, \beta)}, \boldsymbol{\theta}}(t) - tJ_{P_S, \boldsymbol{\theta}}^{(1)} \left( \frac{1}{\beta} \right) \quad (316) $$

$$ \le \frac{1}{2} t^2 \hat{\zeta}_{P_S, \theta}^2, \quad (317) $$

where the function $J_{P_{\hat{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, \beta)}, \boldsymbol{\theta}}$ in (316) is defined in (19); the inequality in (317) follows from Theorem 3; and

$$ \hat{\zeta}_{P_S, \boldsymbol{\theta}}^2 \triangleq \sup \left\{ \sqrt{J_{P_S, \boldsymbol{\theta}}^{(2)}(\xi)} : \xi \in \left(0, b - \frac{1}{\beta}\right) \right\}, \quad (318) $$

with

$$ b \triangleq \sup\{\alpha \in (0, +\infty) : J_{P_S, \boldsymbol{\theta}}(\alpha) < +\infty\}. \quad (319) $$

Plugging (317) into (314) yields

$$ G(\boldsymbol{\theta}, P, P_{\hat{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, \beta)}) \le \inf_{t>0} \left( \frac{D(P\|P_{\hat{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, \beta)})}{t} + \frac{1}{2} t^2 \hat{\zeta}_{P_S, \boldsymbol{\theta}}^2 \right). \quad (320) $$

Let $c \in \mathbb{R}$ be defined as follows:

$$ c \triangleq G(\boldsymbol{\theta}, P, P_{\hat{Z}|\Theta=\boldsymbol{\theta}}^{(P_S, \beta)}). \quad (321) $$

Hence, from (320), it follows that for all $t \in (0, +\infty)$,

$$ ct - \frac{1}{2} t^2 \hat{\zeta}_{P_S, \theta}^2 \le D(P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) $$

The rest of the proof consists in finding an explicit expression for the absolute value of $c$ in (321). To this aim, consider the function $\phi: \mathbb{R} \to \mathbb{R}$ such that

$$ \phi(\alpha) = \frac{1}{2} \alpha^2 \hat{\zeta}_{P_S, \theta}^2. \quad (322) $$

Let the Legendre-Fenchel transform of $\phi$ be the function $\phi^*: \mathbb{R} \to \mathbb{R}$, and thus for all $x \in \mathbb{R}$,

$$ \phi^*(x) = \max_{t \in (0, +\infty)} xt - \phi(t). \quad (323) $$
In particular, note that

$$ \phi^*(c) \le D \left( P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right). \quad (324) $$

Note that for all $x \in \mathbb{R}$ and for all $t \in (0, +\infty)$, the function $\phi^*$ in (323) satisfies

$$ xt - \frac{1}{2} t^2 \hat{\zeta}_{P_S, \theta}^2 \le \phi^*(x) = x\alpha^*(x) - \phi(\alpha^*(x)), \quad (325) $$

where the term $\alpha^*(x)$ represents the unique solution in $\alpha$ within the interval $(0, +\infty)$ to

$$ \frac{d}{d\alpha} (x\alpha - \phi(\alpha)) = x - \alpha\zeta^2 = 0. \quad (326) $$

That is

$$ \alpha^*(x) = \frac{x}{\hat{\zeta}_{P_S, \theta}^2}. \quad (327) $$

Plugging (327) into (325) gives

$$ \phi^*(x) = \frac{x^2}{2\hat{\zeta}_{P_S, \theta}^2}. \quad (328) $$

Hence, from (324) and (325), given $c$ in (321) for all $t \in (0, +\infty)$,

$$ ct - \frac{1}{2} t^2 \hat{\zeta}_{P_S, \theta}^2 \le \phi^*(c) \le D \left( P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right), \quad (329) $$

and thus,

$$ \frac{c^2}{2\hat{\zeta}_{P_S, \theta}^2} \le D \left( P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right). \quad (330) $$

This implies that

$$ c \le \sqrt{2\hat{\zeta}_{P_S, \theta}^2 D \left( P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right)}, \quad \text{and} \quad (331) $$

$$ c \ge -\sqrt{2\hat{\zeta}_{P_S, \theta}^2 D \left( P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right)}, \quad (332) $$

which leads to

$$ |G(\theta, P, P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)})| \le \sqrt{2\hat{\zeta}_{P_S, \theta}^2 D \left( P \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right)}. \quad (333) $$

This completes the proof.
## N Proof of Theorem 8

The proof follows from the following equalities:

$$G(\boldsymbol{\theta}, P_1, P_2) = G(\boldsymbol{\theta}, P_1, P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) - G(\boldsymbol{\theta}, P_2, P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) \quad (334)$$

$$= \beta \left( D(P_1 \| P_S) - D(P_1 \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) - D(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S) \right) \\ - \beta \left( D(P_2 \| P_S) - D(P_2 \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)}) - D(P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \| P_S) \right) \quad (335)$$

$$= \beta \left( D \left( P_2 \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) - D \left( P_1 \| P_{\hat{Z}|\Theta=\theta}^{(P_S, \beta)} \right) \right) \quad (336)$$

$$-D(P_2 \| P_S) + D(P_1 \| P_S), \quad (337)$$

where equality in (335) follows from (59). This completes the proof.

## O Proof for Lemma 7

The proof follows from Definition 3 and the following equalities:

$$L(z, \boldsymbol{\theta}) = \frac{1}{n} \sum_{t=1}^{n} \ell(\boldsymbol{\theta}, x_t, y_t) \quad (338)$$

$$= \frac{1}{n} \sum_{(x,y) \in (\mathcal{X} \times \mathcal{Y})} \ell(\boldsymbol{\theta}, x, y) \sum_{t=1}^{n} 1_{\{x=x_t, y=y_t\}} \quad (339)$$

$$= \sum_{(x,y) \in (\mathcal{X} \times \mathcal{Y})} \ell(\boldsymbol{\theta}, x, y) P_z(x, y) \quad (340)$$

$$= \int \ell(\boldsymbol{\theta}, x, y) dP_z(x, y) \quad (341)$$

$$= R_{\boldsymbol{\theta}}(P_z), \quad (342)$$

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

## P Proof of Theorem 11

*Proof:* From the equality in (103), it follows that

$$\overline{\overline{G}}(P_{\Theta|Z}, P_Z) = \int G(\boldsymbol{\theta}, P_Z, P_{Z|\Theta=\theta}) dP_{\Theta}(\boldsymbol{\theta}). \quad (343)$$

Moreover, from the assumption that for all $\boldsymbol{\theta} \in \text{supp } P_{\Theta}$, the probability measure $P_Z$ is absolutely continuous with respect to $P_{Z|\Theta=\theta}$, it follows from Corollary 2 (Equation (64)) that

$$G(\boldsymbol{\theta}, P_Z, P_{Z|\Theta=\theta}) = D\left(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}, \beta)}\right) - D\left(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}, \beta)}\right) \\ + D\left(P_Z \| P_{Z|\Theta=\theta}\right). \quad (344)$$
Finally, plugging (344) into (343) yields

$$ \frac{1}{\beta} \overline{\overline{G}}(P_{\Theta|Z}, P_Z) = \int D\left(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}, \beta)}\right) dP_{\Theta}(\theta) \\ - \int D\left(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}, \beta)}\right) dP_{\Theta}(\theta) \\ + \int D\left(P_Z \| P_{Z|\Theta=\theta} \right) dP_{\Theta}(\theta), \quad (345) $$

where $\int D(P_Z \| P_{Z|\Theta=\theta}) dP_{\Theta}(\theta) = \frac{1}{n} L(P_{\Theta|Z}; P_Z)$, which follows from (84). This completes the proof. ■

## Q Proof of Theorem 12

*Proof:* The proof follows from Theorem 11 by noticing that if for all $\theta \in$ supp $P_{\Theta}$, $\beta$ satisfies (125), then the probability measures $P_Z$ and $P_{\hat{Z}|\Theta=\theta}$ are identical. Hence, for all $\theta \in$ supp $P_{\Theta}$,

$$ D\left(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}, \beta)}\right) = 0, \quad (346) $$

and moreover, from the fact for all $\theta \in$ supp $P_{\Theta}$, the probability measures $P_{Z|\Theta=\theta}$ and $P_{\hat{Z}|\Theta=\theta}$ are mutually absolutely continuous (Lemma 3), it follows that $P_Z$ and $P_{Z|\Theta=\theta}$ are also mutually absolutely continuous. Hence,

$$ D\left(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}, \beta)}\right) = D\left(P_{Z|\Theta=\theta} \| P_Z\right). \quad (347) $$

The equalities in (346) and (347) imply that

$$ \int \left( D\left(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}, \beta)}\right) - D\left(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}, \beta)}\right) \right) dP_{\Theta}(\theta) \\ = \int D(P_{Z|\Theta=\theta} \| P_Z) dP_{\Theta}(\theta), \quad (348) $$

where $\int D(P_{Z|\Theta=\theta} \| P_Z) dP_{\Theta}(\theta) = \frac{1}{n} I(P_{\Theta|Z}; P_Z)$, which follows from (83). This completes the proof. ■

## R Proof of Lemma 11

### R.1 Preliminaries

**Lemma 14** Let $P_{\Theta|Z}^{(Q, \lambda)} \in \Delta(\mathcal{M} | (\mathcal{X} \times \mathcal{Y})^n)$ be the Gibbs algorithm in (85) and assume that for all $\theta \in \mathcal{M}$, the measure $P_Z$ in (94) is absolutely continuous
with $P_{Z|\Theta=\theta}^{(Q,\beta)}$ in (93). Then, for all $\theta \in \text{supp } P_{\Theta}^{(Q,\lambda)}$,

$$ D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) = \frac{1}{n\lambda} \left( \begin{aligned} & R_{\theta}(P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) - n\lambda D(P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)} \| P_{Z|\Theta=\theta}^{(Q,\lambda)}) \\ & \quad - \frac{1}{n\lambda} (R_{\theta}(P_Z) - n\lambda D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)})) \end{aligned} \right) \quad (349) $$

$$ = \frac{1}{n\lambda} \left( R_{\theta}(P_{Z|\Theta=\theta}^{(Q,\lambda)}) + n\lambda D(P_{Z|\Theta=\theta}^{(Q,\lambda)} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) \right) \quad (350) $$

$$ -\frac{1}{n\lambda} (R_{\theta}(P_Z) - n\lambda D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)})) \quad (351) $$

$$ = J_{P_{Z|\Theta=\theta}^{(Q,\lambda)}} \left( \frac{1}{n\lambda} \right) - \frac{1}{n\lambda} (R_{\theta}(P_Z) - n\lambda D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)})), \quad (352) $$

where the functional $R_{\theta}$ is defined in (8); the function $J_{P_{Z|\Theta=\theta}^{(Q,\lambda)}, \theta}$ is defined as in (19); the measure $P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}$ is defined as in (21); and the measures $P_Z$, $P_{\hat{Z}}$, $P_{\Theta}^{(Q,\lambda)}$ and $P_{Z|\Theta=\theta}^{(Q,\lambda)}$ jointly satisfy (91), (92), (93), and (94).

**Proof:** The proof follows from Theorem 6, which implies the following equality:

$$ R_{\theta}(P_Z) - R_{\theta}\left(P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}\right) = n\lambda \left( D\left(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)}\right) - D\left(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}\right) \right. \\ \left. - D\left(P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}\right) \| P_{Z|\Theta=\theta}^{(Q,\lambda)}\right), \quad (353) $$

which can be re-written as follows:

$$ D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) = \frac{1}{n\lambda} \left( R_{\theta}(P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) - n\lambda D(P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)} \| P_{Z|\Theta=\theta}^{(Q,\lambda)}) \right) \\ - \frac{1}{n\lambda} (R_{\theta}(P_Z) - n\lambda D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)})). \quad (354) $$

From Lemma 3 and the equality in (354), it follows that

$$ D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) = \frac{1}{n\lambda} \left( R_{\theta}(P_{Z|\Theta=\theta}^{(Q,\lambda)}) + n\lambda D(P_{Z|\Theta=\theta}^{(Q,\lambda)} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) \right) \\ - \frac{1}{n\lambda} (R_{\theta}(P_Z) - n\lambda D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)})) \quad (355) $$

$$ = J_{P_{Z|\Theta=\theta}^{(Q,\lambda)}, \theta} \left( \frac{1}{n\lambda} \right) - \frac{1}{n\lambda} (R_{\theta}(P_Z) - n\lambda D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)})), \quad (356) $$

which completes the proof. ■

<figure><img src="image_18.png" /></figure>
**Lemma 15** Let $P_{\Theta|Z}^{(Q,\lambda)} \in \Delta(M|(\mathcal{X} \times \mathcal{Y})^n)$ be the Gibbs algorithm in (85). Then, for all $\theta \in \text{supp } P_{\Theta}^{(Q,\lambda)}$,

$$ J_{P_{Z|\Theta=\theta}^{(Q,\lambda)}, \theta} \left( \frac{1}{n\lambda} \right) = \frac{1}{n} \log \left( \int \exp \left( -K_{Q,z} \left( -\frac{1}{\lambda} \right) \right) dP_Z(z) \right) + \frac{1}{n} \log \frac{dQ}{dP_{\Theta}^{(Q,\lambda)}}(\theta), \quad (357) $$

where the functions $J_{P_{Z|\Theta=\theta}^{(Q,\lambda)}, \theta}$ and $K_{Q,z}$ are respectively defined in (19) and (86); and the measures $P_Z$, $P_{\Theta}^{(Q,\lambda)}$ and $P_{Z|\Theta=\theta}^{(Q,\lambda)}$ jointly satisfy (91), (92), (93), and (94).

*Proof:* The term $J_{P_{Z|\Theta=\theta}^{(Q,\lambda)}, \theta} \left( \frac{1}{n\lambda} \right)$ in (357) satisfies

$$ J_{P_{Z|\Theta=\theta}^{(Q,\lambda)}, \theta} \left( \frac{1}{n\lambda} \right) = \log \int \exp \left( \frac{1}{n\lambda} \ell(x, y, \theta) \right) dP_{Z|\Theta=\theta}^{(Q,\lambda)}(x, y) \quad (358) $$

$$ = \frac{1}{n} \log \prod_{t=1}^{n} \left( \int \exp \left( \frac{1}{n\lambda} \ell(x_t, y_t, \theta) \right) dP_{Z|\Theta=\theta}^{(Q,\lambda)}(x_t, y_t) \right) \quad (359) $$

$$ = \frac{1}{n} \log \left( \int \prod_{t=1}^{n} \exp \left( \frac{1}{n\lambda} \ell(x_t, y_t, \theta) \right) dP_{Z|\Theta=\theta}^{(Q,\lambda)}(z) \right) \quad (360) $$

$$ = \frac{1}{n} \log \left( \int \exp \left( \frac{1}{\lambda} L(z, \theta) \right) dP_{Z|\Theta=\theta}^{(Q,\lambda)}(z) \right) \quad (361) $$

$$ = \frac{1}{n} \log \left( \int \exp \left( \frac{1}{\lambda} L(z, \theta) \right) \frac{dP_{Z|\Theta=\theta}^{(Q,\lambda)}}{dP_Z}(z) dP_Z(z) \right), \quad (362) $$

where the equality in (358) follows from (19); the equality in (359) follows from observing that

$$ \left( \int \exp \left( \frac{1}{n\lambda} \ell(x_t, y_t, \theta) \right) P_{Z|\Theta=\theta}^{(Q,\lambda)}(x_t, y_t) \right)^n = \prod_{t=1}^{n} \left( \int \exp \left( \frac{1}{n\lambda} \ell(x_t, y_t, \theta) \right) P_{Z|\Theta=\theta}^{(Q,\lambda)}(x_t, y_t) \right); \quad (363) $$

the equality in (360) follows from (81); and the equality in (361) follows from (5).

Under the assumption that the measures $P_Z$, $P_{\Theta}^{(Q,\lambda)}$ and $P_{Z|\Theta=\theta}^{(Q,\lambda)}$ jointly satisfy (91), (92), (93), and (94), it follows that for all $z \in \text{supp } P_Z$, the Radon-Nikodym derivative $\frac{dP_{Z|\Theta=\theta}^{(Q,\lambda)}}{dP_Z}$ in (362) satisfies

$$ \frac{dP_{Z|\Theta=\theta}^{(Q,\lambda)}}{dP_Z}(z) = \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta}^{(Q,\lambda)}}(\theta). \quad (364) $$
Plugging (364) in (362), it follows that

$$J_{P_{Z|\Theta=\theta}^{(Q,\lambda)}}\left(\frac{1}{n\lambda}\right) = \frac{1}{n}\log\left(\int \exp\left(\frac{1}{\lambda}\mathbf{L}(z, \theta)\right) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta}^{(Q,\lambda)}}(\theta)dP_Z(z)\right) \quad (365)$$

$$= \frac{1}{n} \log \left( \int \exp \left( \frac{1}{\lambda} \mathbf{L}(z, \theta) \right) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dP_{\Theta}^{(Q,\lambda)}}(\theta) \frac{dQ}{dQ}(\theta) dP_Z(z) \right) \quad (366)$$

$$= \frac{1}{n} \log \left( \int \exp \left( \frac{1}{\lambda} \mathbf{L}(z, \theta) \right) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \frac{dQ}{dP_{\Theta}^{(Q,\lambda)}}(\theta) dP_Z(z) \right) \quad (367)$$

$$= \frac{1}{n} \log \left( \int \exp \left( \frac{1}{\lambda} \mathbf{L}(z, \theta) \right) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dP_Z(z) \right) + \frac{1}{n} \log \frac{dQ}{dP_{\Theta}^{(Q,\lambda)}}(\theta) \quad (368)$$

$$= \frac{1}{n} \log \left( \int \exp \left( -K_{Q,z} \left( -\frac{1}{\lambda} \right) \right) dP_Z(z) \right) + \frac{1}{n} \log \frac{dQ}{dP_{\Theta}^{(Q,\lambda)}}(\theta), \quad (369)$$

where the equality in (369) follows from (85), which completes the proof. ■

The expectation of $\mathbf{L}$ in (5) with respect to a probability measure $P \in \Delta(\mathcal{M})$, for a fixed dataset $z$ is denoted using the functional $\mathbf{R}_z : \Delta(\mathcal{M}) \to [0, +\infty]$, which satisfies

$$\mathbf{R}_z(P) = \int \mathbf{L}(z, \theta) dP(\theta). \quad (370)$$

Let the functional $\mathbf{G}: (\mathcal{X} \times \mathcal{Y})^n \times \Delta(\mathcal{M}) \times \Delta(\mathcal{M}) \to \mathbb{R}$ be such that

$$\mathbf{G}(z, P_1, P_2) = \mathbf{R}_z(P_1) - \mathbf{R}_z(P_2). \quad (371)$$

The functional $\mathbf{G}$ in (58) and the functional $\mathbf{G}$ in (371) are distinguishable by their arguments. Hence, there is no notational ambiguity.

**Lemma 16** Let $P_{\Theta|Z=z}^{(Q,\lambda)} \in \Delta(\mathcal{M})$ be the probability measure in (85). Then, for all $P \in \Delta_Q(\mathcal{M})$,

$$\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) = \mathbf{R}_z(P) + \lambda D(P \| Q) - \lambda D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}), \quad (372)$$

where the functional $\mathbf{R}_z$ is defined in (370).

*Proof:* The proof follows immediately from [20, Theorem 1] by noticing that

$$\mathbf{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), \quad (373)$$

which completes the proof. ■

<figure><img src="image_19.png" /></figure>
## R.2 The Proof

*Proof:* If for all $\theta \in \text{supp } P_{\Theta}^{(Q,\lambda)}$, the equality in (127) holds, then,

$$ \int D \left( P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)} \right) dP_{\Theta}^{(Q,\lambda)}(\theta) = 0. \quad (374) $$

Note that the relative entropy of a probability measure with respect to another probability measure is nonnegative ( [21, Theorem 1]). Hence, if the equality (374) holds, then, for all $\theta \in \text{supp } P_{\Theta}^{(Q,\lambda)}$, the equality in (127) holds ( [60, Theorem 1.6.6b]).

This said, the rest of the proof focuses on proving that the equality in (374) holds if and only if the equality in (128) holds for some real $c \le 0$. Note that

$$ 0 = \int D \left( P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)} \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (375) $$

$$ = \int \mathcal{J}_{P_{Z|\Theta=\theta}^{(Q,\lambda)}, \theta} \left( \frac{1}{n\lambda} \right) dP_{\Theta}^{(Q,\lambda)}(\theta) - \frac{1}{n\lambda} \int \left( \mathbb{R}_{\theta}(P_Z) - n\lambda D \left( P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)} \right) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (376) $$

$$ = \frac{1}{n} \int \log \left( \int \exp \left( -K_{Q,z} \left( -\frac{1}{\lambda} \right) \right) dP_Z(z) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) + \frac{1}{n} \int \log \frac{dQ}{dP_{\Theta}^{(Q,\lambda)}}(\theta) dP_{\Theta}^{(Q,\lambda)}(\theta) $$

$$ -\frac{1}{n\lambda} \int \left( \mathbb{R}_{\theta}(P_Z) - n\lambda D \left( P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)} \right) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (377) $$

$$ = \frac{1}{n} \log \left( \int \exp \left( -K_{Q,z} \left( -\frac{1}{\lambda} \right) \right) dP_Z(z) \right) - \frac{1}{n} D \left( P_{\Theta}^{(Q,\lambda)} \| Q \right) $$

$$ -\frac{1}{n\lambda} \int \left( \mathbb{R}_{\theta}(P_Z) - n\lambda D \left( P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)} \right) \right) dP_{\Theta}^{(Q,\lambda)}(\theta), \quad (378) $$

where the equality in (376) follows from Lemma 14; and the equality in (377) follows from Lemma 15.
Note that

$$ \int \mathbb{R}_{\theta}(P_Z) dP_{\Theta}^{(Q,\lambda)}(\theta) = \int \int \ell(x, y, \theta) dP_Z(x, y) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (379) $$

$$ = \int \frac{1}{n} \sum_{t=1}^{n} \left( \int \ell(x_t, y_t, \theta) dP_Z(x_t, y_t) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (380) $$

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

$$ = \int \left( \int L(z, \theta) dP_Z(z) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (382) $$

$$ = \int \left( \int L(z, \theta) dP_{\Theta}^{(Q,\lambda)}(\theta) \right) dP_Z(z) \quad (383) $$

$$ = \int \mathbb{R}_z (P_{\Theta}^{(Q,\lambda)}) dP_Z(z), \quad (384) $$

where the function $L$ is defined in (5) and the functional $\mathbb{R}_z$ is defined in (370). The change in the order of the integrals in (383) follows from [60, Theorem 2.6.6].

Note also that for all $\theta \in \text{supp } P_{\Theta}^{(Q,\lambda)}$, it follows that

$$ D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)}) = \int \log \left( \frac{dP_Z}{dP_{Z|\Theta=\theta}^{(Q,\lambda)}}(x, y) \right) dP_Z(x, y) \quad (385) $$

$$ = \frac{1}{n} \sum_{t=1}^{n} \int \log \left( \frac{dP_Z}{dP_{Z|\Theta=\theta}^{(Q,\lambda)}}(x_t, y_t) \right) dP_Z(x_t, y_t) \quad (386) $$

$$ = \frac{1}{n} \int \sum_{t=1}^{n} \log \left( \frac{dP_Z}{dP_{Z|\Theta=\theta}^{(Q,\lambda)}}(x_t, y_t) \right) dP_Z(z) \quad (387) $$

$$ = \frac{1}{n} \int \log \left( \frac{dP_Z}{dP_{Z|\Theta=\theta}^{(Q,\lambda)}}(z) \right) dP_Z(z) \quad (388) $$

$$ = \frac{1}{n} D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)}), \quad (389) $$

where the equality in (387) follows from [60, Theorem 1.6.3]; and the equality in (388) follows from the fact that the measure $P_Z$ is a product measure formed by $P_Z$ and the measure $P_{Z|\Theta=\theta}^{(Q,\lambda)}$ is a product measure formed by $P_{Z|\Theta=\theta}^{(Q,\lambda)}$, as in (93).
From (389), it holds that

$$ \int D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)}) dP_{\Theta}^{(Q,\lambda)}(\theta) = \frac{1}{n} \int D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)}) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (390) $$

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

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

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

$$ = \frac{1}{n} \int D(P_{\Theta}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(z), \quad (394) $$

where the equality in (392) follows from the same arguments that justify (364).

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

Finally, using the equalities in (384) and (394), the equality in (378) can be re-written as follows:

$$ \begin{aligned} 0 &= \frac{1}{n} \log \left( \int \exp \left( -K_{Q,z} \left( -\frac{1}{\lambda} \right) \right) dP_Z(z) \right) - \frac{1}{n} D \left( P_{\Theta}^{(Q,\lambda)} \| Q \right) \\ &\quad - \frac{1}{n\lambda} \int \left( \mathbb{R}_z \left( P_{\Theta}^{(Q,\lambda)} \right) - \lambda D \left( P_{\Theta}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{(Q,\lambda)} \right) \right) dP_Z(z) \end{aligned} \quad (395) $$

$$ = \frac{1}{n} \log \left( \int \exp \left( -K_{Q,z} \left( -\frac{1}{\lambda} \right) \right) dP_Z(z) \right) - \frac{1}{n\lambda} \int \left( \mathbb{R}_z \left( P_{\Theta}^{(Q,\lambda)} \right) + \lambda D \left( P_{\Theta}^{(Q,\lambda)} \| Q \right) - \lambda D \left( P_{\Theta}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{(Q,\lambda)} \right) \right) dP_Z(z), \quad (396) $$

$$ = \frac{1}{n} \log \left( \int \exp \left( -K_{Q,z} \left( -\frac{1}{\lambda} \right) \right) dP_Z(z) \right) - \frac{1}{n\lambda} \int \left( \mathbb{R}_z \left( P_{\Theta|Z=z}^{(Q,\lambda)} \right) + \lambda D \left( P_{\Theta|Z=z}^{(Q,\lambda)} \| Q \right) \right) dP_Z(z), \quad (397) $$

$$ = \frac{1}{n} \log \left( \int \exp \left( -K_{Q,z} \left( -\frac{1}{\lambda} \right) \right) dP_Z(z) \right) + \frac{1}{n} \int K_{Q,z} \left( -\frac{1}{\lambda} \right) dP_Z(z), \quad (398) $$

$$ = \frac{1}{n} \log \left( \int \exp \left( -K_{Q,z} \left( -\frac{1}{\lambda} \right) \right) dP_Z(z) \right) - \frac{1}{n} \int \log \left( \exp \left( -K_{Q,z} \left( -\frac{1}{\lambda} \right) \right) \right) dP_Z(z), \quad (399) $$

where the equality in (397) follows from Lemma 16; and the equality in (398) follows from [20, Lemma 3].

The proof is finalized by noticing that the log function is strictly concave and the term in the right-hand side of (399) is a Jensen gap [66]. Hence, from [58, Theorem 2.6.2], the equality in (399) holds if and only if (128) holds for some real $c \le 0$. The negativity of $c$ follows from the fact that $K_{Q,z}(-\frac{1}{\lambda}) \le 0$, [20, Lemma 3].
S Proof of Lemma 12

From Lemma 14, it follows that for all $\theta \in \text{supp } P_{\Theta}^{(Q,\lambda)}$,

$$ D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) = \frac{1}{n\lambda} \left( \mathbf{R}_{\theta}(P_{Z|\Theta=\theta}^{(Q,\lambda)}) + n\lambda D(P_{Z|\Theta=\theta}^{(Q,\lambda)} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) \right) \\ - \frac{1}{n\lambda} (\mathbf{R}_{\theta}(P_Z) - n\lambda D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)})), \quad (400) $$

and thus,

$$ D(P_{Z|\Theta=\theta}^{(Q,\lambda)} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) \\ = \frac{1}{n\lambda} \left( \mathbf{R}_{\theta}(P_Z) - \mathbf{R}_{\theta}(P_{Z|\Theta=\theta}^{(Q,\lambda)}) - n\lambda D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)}) \right). \quad (401) $$

From the equality in (401), it follows that

$$ \begin{align} & \int \left( D(P_{Z|\Theta=\theta}^{(Q,\lambda)} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \nonumber \\ &= \frac{1}{n\lambda} \int \left( \mathbf{R}_{\theta}(P_Z) - \mathbf{R}_{\theta}(P_{Z|\Theta=\theta}^{(Q,\lambda)}) - n\lambda D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)}) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (402) \\ &= \frac{1}{n\lambda} \int \mathbf{R}_z(P_{\Theta}^{(Q,\lambda)}) dP_Z(z) \nonumber \\ & \quad - \frac{1}{n\lambda} \int \left( \mathbf{R}_{\theta}(P_{Z|\Theta=\theta}^{(Q,\lambda)}) + n\lambda D(P_Z \| P_{Z|\Theta=\theta}^{(Q,\lambda)}) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (403) \\ &= \frac{1}{n\lambda} \int \mathbf{R}_z(P_{\Theta}^{(Q,\lambda)}) dP_Z(z) \nonumber \\ & \quad - \frac{1}{n\lambda} \int \mathbf{R}_{\theta}(P_{Z|\Theta=\theta}^{(Q,\lambda)}) dP_{\Theta}^{(Q,\lambda)}(\theta) - \frac{1}{n} \int D(P_{\Theta}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(z) \quad (404) \\ &= \frac{1}{n\lambda} \left( \int \mathbf{R}_z(P_{\Theta}^{(Q,\lambda)}) dP_Z(z) - \int \mathbf{R}_{\theta}(P_{Z|\Theta=\theta}^{(Q,\lambda)}) dP_{\Theta}^{(Q,\lambda)}(\theta) \right) \nonumber \\ & \quad - \frac{1}{n} L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) \quad (405) \end{align} $$

where the equality in (403) follows a similar argument as in (384); the equality in (404) follows a similar argument as in (394); and the equality in (405) follows from (90).
The proof continues by observing that

$$ \int \mathbb{R}_{\theta} (P_{Z|\Theta=\theta}^{(Q,\lambda)}) dP_{\Theta}^{(Q,\lambda)}(\theta) \\ = \iint \ell(x, y, \theta) dP_{Z|\Theta=\theta}^{(Q,\lambda)}(x, y) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (406) $$

$$ = \int \left( \frac{1}{n} \sum_{t=1}^{n} \int \ell(x_t, y_t, \theta) dP_{Z|\Theta=\theta}^{(Q,\lambda)}(x_t, y_t) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (407) $$

$$ = \int \left( \int \frac{1}{n} \sum_{t=1}^{n} \ell(x_t, y_t, \theta) dP_{Z|\Theta=\theta}^{(Q,\lambda)}(z) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (408) $$

$$ = \iint L(z, \theta) dP_{Z|\Theta=\theta}^{(Q,\lambda)}(z) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (409) $$

$$ = \iint L(z, \theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) dP_Z(z) \quad (410) $$

$$ = \int \mathbb{R}_z (P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(z), \quad (411) $$

where the functions $\ell$ and $L$ are respectively defined in (4) and (5); and the functional $\mathbb{R}_z$ is defined in (370). The change of measures in (410) follows from (364). Plugging the equality in (411) into (405) yields

$$ \int \left( D(P_{Z|\Theta=\theta}^{(Q,\lambda)} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}^{(Q,\lambda)}, n\lambda)}) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \\ = \frac{1}{n\lambda} \int \left( \mathbb{R}_z (P_{\Theta}^{(Q,\lambda)}) - \mathbb{R}_z (P_{\Theta|Z=z}^{(Q,\lambda)}) \right) dP_Z(z) - \frac{1}{n} L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) \quad (412) $$

$$ = \frac{1}{n\lambda} \int G(z, P_{\Theta}^{(Q,\lambda)}, P_{\Theta|Z=z}^{(Q,\lambda)}) dP_Z(z) - \frac{1}{n} L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) \quad (413) $$

$$ = \frac{1}{n} \left( I(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) + L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) \right) - \frac{1}{n} L(P_{\Theta|Z}^{(Q,\lambda)}; P_Z) \quad (414) $$

$$ = \frac{1}{n} I(P_{\Theta|Z}^{(Q,\lambda)}; P_Z), \quad (415) $$

where the functional $G$ in (413) is defined in (371); and the equality in (414) follows from [21, Theorem 17]. This completes the proof.

# T Proof of Theorem 13

## T.1 Preliminaries

**Lemma 17** Let $P_{\Theta|Z} \in \Delta(M | (X \times Y)^n)$ be a given algorithm and assume that for all $\theta \in M$, the measure $P_Z$ in (82) is absolutely continuous with $P_{Z|\Theta=\theta}$
in (81). Then, for all $\theta \in \text{supp } P_{\Theta}$,

$$ D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_Z|\Theta=\theta,\beta)}) = \frac{1}{\beta} \left( \begin{aligned} & \mathrm{R}_{\theta}(P_{\hat{Z}|\Theta=\theta}^{(P_Z|\Theta=\theta,\beta)}) - \beta D(P_{\hat{Z}|\Theta=\theta}^{(P_Z|\Theta=\theta,\beta)} \| P_{Z|\Theta=\theta}) \\ & - \frac{1}{\beta} (\mathrm{R}_{\theta}(P_Z) - \beta D(P_Z \| P_{Z|\Theta=\theta})) \end{aligned} \right) \quad (416) $$

$$ = \frac{1}{\beta} \left( \mathrm{R}_{\theta}(P_{Z|\Theta=\theta}) + \beta D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta},\beta)}) \right) \quad (417) $$

$$ -\frac{1}{\beta} (\mathrm{R}_{\theta}(P_Z) - \beta D(P_Z \| P_{Z|\Theta=\theta})) \quad (418) $$

$$ = J_{P_{Z|\Theta=\theta}, \theta} \left( \frac{1}{\beta} \right) -\frac{1}{\beta} (\mathrm{R}_{\theta}(P_Z) - \beta D(P_Z \| P_{Z|\Theta=\theta})), \quad (419) $$

where the functional $\mathrm{R}_{\theta}$ is defined in (8); the function $J_{P_{Z|\Theta=\theta}, \theta}$ is defined as in (19); the measure $P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta},\beta)}$ is defined as in (21); and the measures $P_Z$, $P_Z$, $P_{\Theta}$ and $P_{Z|\Theta=\theta}$ jointly satisfy (91), (92), (93), and (94).

*Proof:* The proof follows along the same steps as the proof of Lemma 14. ■

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

## T.2 The Proof

*Proof:* From Lemma 17, it follows that for all $\theta \in \text{supp } P_{\Theta}^{(Q,\lambda)}$,

$$ D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_Z|\Theta=\theta,\beta)}) = \frac{1}{\beta} \left( \begin{aligned} & \mathrm{R}_{\theta}(P_{Z|\Theta=\theta}) + \beta D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta},\beta)}) \\ & - \frac{1}{\beta} (\mathrm{R}_{\theta}(P_Z) - \beta D(P_Z \| P_{Z|\Theta=\theta})) \end{aligned} \right), \quad (420) $$

and thus,

$$ \begin{aligned} & D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta},\beta)}) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta},\beta)}) \\ & = \frac{1}{\beta} \left( \mathrm{R}_{\theta}(P_Z) - \mathrm{R}_{\theta}(P_{Z|\Theta=\theta}) - \beta D(P_Z \| P_{Z|\Theta=\theta}) \right). \end{aligned} \quad (421) $$
From the equality in (421), it follows that

$$ \int \left( D(P_{Z|\Theta=\theta} P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta,\beta})}) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta,\beta})}) \right) dP_{\Theta}(\theta) \\ = \frac{1}{\beta} \int \left( R_{\theta}(P_Z) - R_{\theta}(P_{Z|\Theta=\theta}) - \beta D(P_Z \| P_{Z|\Theta=\theta}) \right) dP_{\Theta}(\theta) \quad (422) $$

$$ = \frac{1}{\beta} \int \left( R_{\theta}(P_Z) - R_{\theta}(P_{Z|\Theta=\theta}) \right) dP_{\Theta}(\theta) - \frac{1}{n} L(P_{\Theta|Z}; P_Z) \quad (423) $$

$$ = \frac{1}{\beta} \int \left( R_z(P_{\Theta}) - R_z(P_{\Theta|Z=z}) \right) dP_Z(z) - \frac{1}{n} L(P_{\Theta|Z}; P_Z), \quad (424) $$

where the equality in (423) follows from (84); and the equality (424) follows the same arguments used to prove the equalities in (384) and (411).

Let $P_{\Theta|Z}^{(Q,\lambda)} \in \Delta(M|(X \times Y)^n)$ be the Gibbs algorithm in (85). The proof continues by adding and subtracting some convenient terms to the right-hand side of (424), as follows:

$$ \beta \int \left( D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta,\beta})}) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta,\beta})}) \right) dP_{\Theta}(\theta) \\ = \int \left( R_z(P_{\Theta}) - R_z(P_{\Theta|Z=z}) \right) dP_Z(z) - \frac{\beta}{n} L(P_{\Theta|Z}; P_Z), \quad (425) $$

$$ = \int \left( R_z(P_{\Theta}) + \lambda D(P_{\Theta}\|Q) \right) dP_Z(z) \\ - \int \left( R_z(P_{\Theta|Z=z}) + \lambda D(P_{\Theta|Z=z}\|Q) \right) dP_Z(z) \\ - \lambda \int \left( D(P_{\Theta}\|Q) - D(P_{\Theta|Z=z}\|Q) \right) dP_Z(z) - \frac{\beta}{n} L(P_{\Theta|Z}; P_Z), \quad (426) $$

$$ = \int \left( R_z(P_{\Theta}) + \lambda D(P_{\Theta}\|Q) - \left( R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D(P_{\Theta|Z=z}^{(Q,\lambda)}\|Q) \right) \right) dP_Z(z) \\ - \int \left( R_z(P_{\Theta|Z=z}) + \lambda D(P_{\Theta|Z=z}\|Q) \right) dP_Z(z) \\ - \left( R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D(P_{\Theta|Z=z}^{(Q,\lambda)}\|Q) \right) dP_Z(z) \\ - \lambda \int \left( D(P_{\Theta}\|Q) - D(P_{\Theta|Z=z}\|Q) \right) dP_Z(z) - \frac{\beta}{n} L(P_{\Theta|Z}; P_Z), \quad (427) $$

where the equality in (426) follows by respectively adding and subtracting the terms $\lambda \int D(P_{\Theta}\|Q) dP_Z(z)$ and $\lambda \int D(P_{\Theta|Z=z}\|Q) dP_Z(z)$; and the equality in (427) follows by respectively adding and subtracting the term

$$ \int \left( R_z \left( P_{\Theta|Z=z}^{(Q,\lambda)} \right) + \lambda D \left( P_{\Theta|Z=z}^{(Q,\lambda)} \| Q \right) \right) dP_Z(z). $$
From [20, Theorem 1], it follows that

$$
\begin{aligned}
& \lambda D(P_{\Theta} \| P_{\Theta|Z=z}^{(Q,\lambda)}) \\
& = \int \left( \mathbb{R}_z(P_{\Theta}) + \lambda D(P_{\Theta} \| Q) - \left( \mathbb{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \right) \right) dP_Z(z) \quad (428)
\end{aligned}
$$

and

$$
\begin{aligned}
\lambda D(P_{\Theta|Z=z} \| P_{\Theta|Z=z}^{(Q,\lambda)}) = & \int \left( \mathbb{R}_z (P_{\Theta|Z=z}) + \lambda D(P_{\Theta|Z=z} \| Q) \right. \\
& \left. - \left( \mathbb{R}_z (P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \right) \right) dP_Z(z). \quad (429)
\end{aligned}
$$

Plugging (428) and (429) in (427) yields,

$$
\begin{aligned}
& \beta \int \left( D(P_{Z|\Theta=\theta} \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}, \beta)}) - D(P_Z \| P_{\hat{Z}|\Theta=\theta}^{(P_{Z|\Theta=\theta}, \beta)}) \right) dP_{\Theta}(\theta) \\
&= \lambda \int \left( D(P_{\Theta} \| P_{\Theta|Z=z}^{(Q,\lambda)}) - D(P_{\Theta|Z=z} \| P_{\Theta|Z=z}^{(Q,\lambda)}) \right) dP_Z(z) \\
&\quad - \lambda \int \left( D(P_{\Theta} \| Q) - D(P_{\Theta|Z=z} \| Q) \right) dP_Z(z) - \frac{\beta}{n} L(P_{\Theta|Z}; P_Z) \quad (430) \\
&= \lambda \int \left( D(P_{\Theta} \| P_{\Theta|Z=z}^{(Q,\lambda)}) - D(P_{\Theta|Z=z} \| P_{\Theta|Z=z}^{(Q,\lambda)}) \right) dP_Z(z) \\
&\quad + \lambda I(P_{\Theta|Z}; P_Z) - \frac{\beta}{n} L(P_{\Theta|Z}; P_Z), \quad (431)
\end{aligned}
$$

where the equality in (431) follows from observing that

$$
\begin{aligned}
& \int \left( D(P_{\Theta|Z=z} \| Q) - D(P_{\Theta} \| Q) \right) dP_Z(z) \\
&= \int D(P_{\Theta|Z=z} \| Q) dP_Z(z) - D(P_{\Theta} \| Q) \qquad (432)
\end{aligned}
$$

$$
= \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 (433)
$$

$$
= \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)
$$

$$
= \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 (434)
$$

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

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

$$
= I(P_{\Theta|Z}; P_Z), \qquad (437)
$$
where the equality in (434) follows from (79); and the equality in (435) follows
from the assumption that for all $z \in \text{supp } P_Z$, the measures $Q$ and $P_{\Theta|Z=z}$ are
mutually absolutely continuous.

The proof is finalized by Theorem 11. More specifically, the equality in (131) is
obtained by plugging the equality in (431) into (124). ■
References

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

[2] I. Csiszár, “The method of types,” *IEEE Transactions on Information Theory*, vol. 44, no. 6, pp. 2505–2523, Oct. 1998.

[3] I. N. Sanov, “On the probability of large deviations of random variables,” *Selected Translations in Mathematical Statistics and Probability*, vol. 1, pp. 213–244, 1961.

[4] H. Rahimian and S. Mehrotra, “ framworks and results in distributionally robust optimization,” *Open Journal of Mathematical Optimization*, vol. 3, pp. 1–85, 2022.

[5] E. Delage and Y. Ye, “Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems,” *Operations research*, vol. 58, no. 3, pp. 595–612, 2010.

[6] Z. Hu and L. J. Hong, “Kullback-Leibler divergence constrained distribu-
tionally robust optimization,” *Optimization Online*, vol. 1, no. 2, p. 9, 2013.

[7] J. Lee and M. Raginsky, “Minimax Statistical Learning with Wasserstein distances,” *Advances in Neural Information Processing Systems*, vol. 31, pp. 2687–2696, 2018.

[8] D. Kuhn, P. M. Esfahani, V. A. Nguyen, and S. Shafieezadeh-Abadeh, “Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning,” in *Operations research & management science in the age of analytics*. Informs, 2019, pp. 130–166.

[9] F. Daunas, I. Esnaola, S. M. Perlaza, and H. V. Poor, “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.

[10] F. Daunas, I. Esnaola, S. M. Perlaza, and H. V. Poor, “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.

[11] E. T. Jaynes, “Information theory and statistical mechanics I,” *Physical Review Journals*, vol. 106, no. 4, pp. 620–630, May 1957.

[12] —, “Information theory and statistical mechanics II,” *Physical Review Journals*, vol. 108, no. 2, pp. 171–190, Oct. 1957.

[13] S. Mazuelas, Y. Shen, and A. Pérez, “Generalized maximum entropy for supervised classification,” *IEEE Transactions on Information Theory*, vol. 68, no. 4, pp. 2530–2550, Jan. 2022.
[14] J. N. Kapur, *Maximum Entropy Models in Science and Engineering*, 1st ed. New York, NY, USA: Wiley, 1989.

[15] G. Aminian, Y. Bu, L. Toni, M. Rodrigues, and G. Wornell, "An exact characterization of the generalization error for the Gibbs algorithm," *Advances in Neural Information Processing Systems*, vol. 34, pp. 8106-8118, Dec. 2021.

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

[17] A. Xu and M. Raginsky, "Information-theoretic analysis of generalization capability of learning algorithms," *Advances in Neural Information Processing Systems*, vol. 30, pp. 1-10, Dec. 2017.

[18] Y. Chu and M. Raginsky, "A unified framework for information-theoretic generalization bounds," arXiv preprint arXiv:2305.11042, May 2023.

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

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

[21] S. M. Perlaza, G. Bisson, I. Esnaola, A. Jean-Marie, and S. Rini, "Empirical risk minimization with relative entropy regularization," *IEEE Transactions on Information Theory*, 2024.

[22] F. Hellström, G. Durisi, B. Guedj, and M. Raginsky, "Generalization bounds: Perspectives from information theory and PAC-Bayes," arXiv preprint arXiv:2309.04381, Sep. 2023.

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

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

[25] A. Asadi, E. Abbe, and S. Verdú, "Chaining mutual information and tightening generalization bounds," *Advances in Neural Information Processing Systems*, vol. 31, pp. 7245-7254, Dec. 2018.