# Empirical Risk Minimization with Relative Entropy Regularization

Samir M. Perlaza, Gaetan Bisson, Iñaki Esnaola, Alain Jean-Marie, Stefano Rini

► To cite this version:

Samir M. Perlaza, Gaetan Bisson, Iñaki Esnaola, Alain Jean-Marie, Stefano Rini. Empirical Risk Minimization with Relative Entropy Regularization. [Research Report] RR-9454, Inria. 2022. hal-03560072v7

HAL Id: hal-03560072

https://hal.science/hal-03560072v7

Submitted on 27 Feb 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Empirical Risk Minimization with Relative Entropy Regularization

Samir M. Perlaza, Gaetan Bisson, Iñaki Esnaola, Alain Jean-Marie, Stefano Rini

► To cite this version:

Samir M. Perlaza, Gaetan Bisson, Iñaki Esnaola, Alain Jean-Marie, Stefano Rini. Empirical Risk Minimization with Relative Entropy Regularization. [Research Report] RR-9454, Inria. 2022. hal-03560072v7

HAL Id: hal-03560072

https://hal.science/hal-03560072v7

Submitted on 27 Feb 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
informatics mathematics
Inria

# Empirical Risk Minimization with Relative Entropy Regularization

Samir M. Perlaza, Gaetan Bisson, Iñaki Esnaola, Alain Jean-Marie, and Stefano Rini

## RESEARCH REPORT

Nº 9454

February 2022

Project-Team NEO

ISSN 0249-6399 ISRN INRIA/RR-9454-FR+ENG
informatics mathematics
Inria

Empirical Risk
Minimization with
Relative Entropy
Regularization

Samir M. Perlaza, Gaetan Bisson, Iñaki Esnaola, Alain Jean-Marie,
and Stefano Rini

RESEARCH

REPORT

Nº 9454

February 2022

Project-Team NEO
<figure><img src="image_2.png" /></figure>
<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /></figure>

# Empirical Risk Minimization with Relative Entropy Regularization

Samir M. Perlaza, Gaetan Bisson, Iñaki Esnaola, Alain Jean-Marie, and Stefano Rini

Project-Team NEO

Research Report n° 9454 — version 7 — initial version February 2022 — revised version February 2024 — 97 pages

**Abstract:** The empirical risk minimization (ERM) problem with relative entropy regularization (ERM-RER) is investigated under the assumption that the reference measure is a σ-finite measure, and not necessarily a probability measure. Under this assumption, which leads to a generalization of the ERM-RER problem allowing a larger degree of flexibility for incorporating prior knowledge, numerous relevant properties are stated. Among these properties, the solution to this problem, if it exists, is shown to be a unique probability measure, mutually absolutely continuous with the reference measure. Such a solution exhibits a probably-approximately-correct guarantee for the ERM problem independently of whether the latter possesses a solution. For a fixed dataset and under a specific condition, the empirical risk is shown to be a sub-Gaussian random variable when the models are sampled from the solution to the ERM-RER problem. The generalization capabilities of the solution to the ERM-RER problem (the Gibbs algorithm) are studied via the sensitivity of the expected empirical risk to deviations from such a solution towards alternative probability measures. Finally, an interesting connection between sensitivity, generalization error, and lautum information is established.

**Key-words:** Supervised Learning, PAC-Learning, Gibbs Algorithm, and Generalization.

RESEARCH CENTRE
SOPHIA ANTIPOLIS – MÉDITERRANÉE

2004 route des Lucioles - BP 93
06902 Sophia Antipolis Cedex

<footnote>Samir M. Perlaza and Alain Jean-Marie are with INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis 06902, France. Gaetan Bisson and Samir M. Perlaza are with the GAATI Laboratory at the Université de la Polynésie Française, Faaa 98702, French Polynesia. Iñaki Esnaola is with the ACSE Dept. at The University of Sheffield, Sheffield S1 3JD, UK. Stefano Rini is with the ECE Dept. at the National Yang Ming Chiao Tung University (NYCU), Hsinchu, Taiwan 30010, ROC. Samir M. Perlaza and Iñaki Esnaola are also with the ECE Dept. at Princeton University, Princeton N.J. 08544, USA. This work has been presented in part at the IEEE International Symposium on Information Theory (ISIT) in [1].</footnote>
# Empirical Risk Minimization with Relative Entropy Regularization

Samir M. Perlaza, Gaetan Bisson, Iñaki Esnaola, Alain Jean-Marie, and Stefano Rini

Project-Team NEO

Research Report n° 9454 — version 7 — initial version February 2022 — revised version February 2024 — 97 pages

**Abstract:** The empirical risk minimization (ERM) problem with relative entropy regularization (ERM-RER) is investigated under the assumption that the reference measure is a σ-finite measure, and not necessarily a probability measure. Under this assumption, which leads to a generalization of the ERM-RER problem allowing a larger degree of flexibility for incorporating prior knowledge, numerous relevant properties are stated. Among these properties, the solution to this problem, if it exists, is shown to be a unique probability measure, mutually absolutely continuous with the reference measure. Such a solution exhibits a probably-approximately-correct guarantee for the ERM problem independently of whether the latter possesses a solution. For a fixed dataset and under a specific condition, the empirical risk is shown to be a sub-Gaussian random variable when the models are sampled from the solution to the ERM-RER problem. The generalization capabilities of the solution to the ERM-RER problem (the Gibbs algorithm) are studied via the sensitivity of the expected empirical risk to deviations from such a solution towards alternative probability measures. Finally, an interesting connection between sensitivity, generalization error, and lautum information is established.

**Key-words:** Supervised Learning, PAC-Learning, Gibbs Algorithm, and Generalization.

RESEARCH CENTRE
SOPHIA ANTIPOLIS – MÉDITERRANÉE

2004 route des Lucioles - BP 93
06902 Sophia Antipolis Cedex

<footnote>Samir M. Perlaza and Alain Jean-Marie are with INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis 06902, France. Gaetan Bisson and Samir M. Perlaza are with the GAATI Laboratory at the Université de la Polynésie Française, Faaa 98702, French Polynesia. Iñaki Esnaola is with the ACSE Dept. at The University of Sheffield, Sheffield S1 3JD, UK. Stefano Rini is with the ECE Dept. at the National Yang Ming Chiao Tung University (NYCU), Hsinchu, Taiwan 30010, ROC. Samir M. Perlaza and Iñaki Esnaola are also with the ECE Dept. at Princeton University, Princeton N.J. 08544, USA. This work has been presented in part at the IEEE International Symposium on Information Theory (ISIT) in [1].</footnote>
Minimisation du Risque Empirique avec
Régularisation par l'Entropie Relative

**Résumé** : Le problème de minimisation du risque empirique (ERM) avec régularisation d'entropie relative (ERM-RER) est étudié sous l'hypothèse que la mesure de référence est une mesure σ-finie, et pas nécessairement une mesure de probabilité. Sous cette hypothèse, qui conduit à une généralisation du problème ERM-RER permettant une plus grande flexibilité pour l'incorporation des connaissances antérieures, de nombreuses propriétés pertinentes sont énoncées. Parmi ces propriétés, la solution à ce problème, si elle existe, se révèle être une mesure de probabilité unique, mutuellement absolument continue avec la mesure de référence. Une telle solution présente une garantie probablement-approximativement-correcte pour le problème ERM indépendamment du fait que ce dernier possède ou non une solution. Pour un ensemble de données fixe, et sous une condition particulière, le risque empirique s'avère être une variable aléatoire sous-gaussienne lorsque les modèles sont échantillonnés à partir de la solution au problème ERM-RER. Les capacités de généralisation de la solution au problème ERM-RER (l'algorithme de Gibbs) sont étudiées via la sensibilité de la valeur espérée du risque empirique aux déviations d'une telle solution vers des mesures de probabilité alternatives. Enfin, un lien intéressant entre la sensibilité, l'erreur de généralisation et l'information lautum est établi.

**Mots-clés** : Apprentissage Supervisé, Apprentissage PAC, Régularisation, Entropie Relative, Minimisation du Risque Empirique, Mesure de Gibbs, Algorithmique de Gibbs, Généralisation, et Sensitivité.
# Minimisation du Risque Empirique avec Régularisation par l'Entropie Relative

**Résumé** : Le problème de minimisation du risque empirique (ERM) avec régularisation d'entropie relative (ERM-RER) est étudié sous l'hypothèse que la mesure de référence est une mesure σ-finie, et pas nécessairement une mesure de probabilité. Sous cette hypothèse, qui conduit à une généralisation du problème ERM-RER permettant une plus grande flexibilité pour l'incorporation des connaissances antérieures, de nombreuses propriétés pertinentes sont énoncées. Parmi ces propriétés, la solution à ce problème, si elle existe, se révèle être une mesure de probabilité unique, mutuellement absolument continue avec la mesure de référence. Une telle solution présente une garantie probablement-approximativement-correcte pour le problème ERM indépendamment du fait que ce dernier possède ou non une solution. Pour un ensemble de données fixe, et sous une condition particulière, le risque empirique s'avère être une variable aléatoire sous-gaussienne lorsque les modèles sont échantillonnés à partir de la solution au problème ERM-RER. Les capacités de généralisation de la solution au problème ERM-RER (l'algorithme de Gibbs) sont étudiées via la sensibilité de la valeur espérée du risque empirique aux déviations d'une telle solution vers des mesures de probabilité alternatives. Enfin, un lien intéressant entre la sensibilité, l'erreur de généralisation et l'information lautum est établi.

**Mots-clés** : Apprentissage Supervisé, Apprentissage PAC, Régularisation, Entropie Relative, Minimisation du Risque Empirique, Mesure de Gibbs, Algorithmique de Gibbs, Généralisation, et Sensitivité.
# Contents

<table><tr><td>1</td><td>Introduction</td><td>5</td></tr><tr><td>2</td><td>Empirical Risk Minimization (ERM)</td><td>7</td></tr><tr><td>2.1</td><td>Notation and Main Assumptions</td><td>8</td></tr><tr><td>2.2</td><td>Relative Entropy Extended to σ-Finite Measures</td><td>8</td></tr><tr><td>2.3</td><td>ERM with Relative Entropy Regularization</td><td>10</td></tr><tr><td>2.4</td><td>Type-I and Type-II Relative Entropy Regularization</td><td>10</td></tr><tr><td>3</td><td>The Solution to the ERM-RER Problem</td><td>11</td></tr><tr><td>3.1</td><td>Examples</td><td>13</td></tr><tr><td>3.1.1</td><td>ERM with Discrete Entropy Regularization</td><td>13</td></tr><tr><td>3.1.2</td><td>ERM with Differential Entropy Regularization</td><td>13</td></tr><tr><td>3.1.3</td><td>Information-Risk Minimization</td><td>14</td></tr><tr><td>3.2</td><td>Bounds on the Radon-Nikodym Derivative</td><td>14</td></tr><tr><td>3.3</td><td>Asymptotes of the Radon-Nikodym Derivative</td><td>15</td></tr><tr><td>4</td><td>Reference Measures</td><td>17</td></tr><tr><td>4.1</td><td>Coherent and Consistent Reference Measures</td><td>18</td></tr><tr><td>4.2</td><td>Gibbs Reference Measures</td><td>20</td></tr><tr><td>5</td><td>The Log-Partition Function</td><td>25</td></tr><tr><td>5.1</td><td>Separable Empirical Risk Functions</td><td>25</td></tr><tr><td>5.2</td><td>Properties of the Log-Partition Function</td><td>26</td></tr><tr><td>6</td><td>Expectation of the Empirical Risk</td><td>28</td></tr><tr><td>7</td><td>Variance of the Empirical Risk</td><td>31</td></tr><tr><td>8</td><td>Cumulant Generating Function of the Empirical Risk</td><td>34</td></tr><tr><td>9</td><td>Concentration of Probability</td><td>41</td></tr><tr><td>9.1</td><td>The Limit Set</td><td>41</td></tr><tr><td>9.2</td><td>The Nonnegligible Limit Set</td><td>42</td></tr><tr><td>10</td><td>(δ, ε)-Optimality</td><td>44</td></tr><tr><td>11</td><td>Sensitivity and Generalization</td><td>46</td></tr><tr><td>11.1</td><td>Sensitivity</td><td>46</td></tr><tr><td>11.2</td><td>Generalization Error</td><td>47</td></tr><tr><td>12</td><td>Conclusions and Final Remarks</td><td>52</td></tr><tr><td colspan="2">Appendices</td><td>53</td></tr><tr><td colspan="2">A Proof of Theorem 2.2</td><td>53</td></tr></table>
# Contents

<table><tr><td>1</td><td>Introduction</td><td>5</td></tr><tr><td>2</td><td>Empirical Risk Minimization (ERM)</td><td>7</td></tr><tr><td>2.1</td><td>Notation and Main Assumptions</td><td>8</td></tr><tr><td>2.2</td><td>Relative Entropy Extended to σ-Finite Measures</td><td>8</td></tr><tr><td>2.3</td><td>ERM with Relative Entropy Regularization</td><td>10</td></tr><tr><td>2.4</td><td>Type-I and Type-II Relative Entropy Regularization</td><td>10</td></tr><tr><td>3</td><td>The Solution to the ERM-RER Problem</td><td>11</td></tr><tr><td>3.1</td><td>Examples</td><td>13</td></tr><tr><td>3.1.1</td><td>ERM with Discrete Entropy Regularization</td><td>13</td></tr><tr><td>3.1.2</td><td>ERM with Differential Entropy Regularization</td><td>13</td></tr><tr><td>3.1.3</td><td>Information-Risk Minimization</td><td>14</td></tr><tr><td>3.2</td><td>Bounds on the Radon-Nikodym Derivative</td><td>14</td></tr><tr><td>3.3</td><td>Asymptotes of the Radon-Nikodym Derivative</td><td>15</td></tr><tr><td>4</td><td>Reference Measures</td><td>17</td></tr><tr><td>4.1</td><td>Coherent and Consistent Reference Measures</td><td>18</td></tr><tr><td>4.2</td><td>Gibbs Reference Measures</td><td>20</td></tr><tr><td>5</td><td>The Log-Partition Function</td><td>25</td></tr><tr><td>5.1</td><td>Separable Empirical Risk Functions</td><td>25</td></tr><tr><td>5.2</td><td>Properties of the Log-Partition Function</td><td>26</td></tr><tr><td>6</td><td>Expectation of the Empirical Risk</td><td>28</td></tr><tr><td>7</td><td>Variance of the Empirical Risk</td><td>31</td></tr><tr><td>8</td><td>Cumulant Generating Function of the Empirical Risk</td><td>34</td></tr><tr><td>9</td><td>Concentration of Probability</td><td>41</td></tr><tr><td>9.1</td><td>The Limit Set</td><td>41</td></tr><tr><td>9.2</td><td>The Nonnegligible Limit Set</td><td>42</td></tr><tr><td>10</td><td>(δ, ε)-Optimality</td><td>44</td></tr><tr><td>11</td><td>Sensitivity and Generalization</td><td>46</td></tr><tr><td>11.1</td><td>Sensitivity</td><td>46</td></tr><tr><td>11.2</td><td>Generalization Error</td><td>47</td></tr><tr><td>12</td><td>Conclusions and Final Remarks</td><td>52</td></tr><tr><td colspan="2">Appendices</td><td>53</td></tr><tr><td colspan="2">A Proof of Theorem 2.2</td><td>53</td></tr></table>
<table><tr><td>B</td><td>Proof of Lemma 3.1</td><td>54</td></tr><tr><td>C</td><td>Proof of Theorem 3.1</td><td>55</td></tr><tr><td>D</td><td>Proof of Lemma 3.2</td><td>59</td></tr><tr><td>E</td><td>Proof of Lemma 3.3</td><td>60</td></tr><tr><td>F</td><td>Proof of Lemma 3.4</td><td>61</td></tr><tr><td>G</td><td>Proof of Lemma 3.6</td><td>62</td></tr><tr><td>H</td><td>Proof of Lemma 3.7</td><td>65</td></tr><tr><td>I</td><td>Proof of Lemma 4.1</td><td>66</td></tr><tr><td>J</td><td>Proof of Theorem 4.1</td><td>66</td></tr><tr><td>K</td><td>Proof of Lemma 5.2</td><td>70</td></tr><tr><td>L</td><td>Proof of Lemma 5.3</td><td>71</td></tr><tr><td>M</td><td>Proof of Lemma 5.4</td><td>72</td></tr><tr><td>N</td><td>Proof of Theorem 6.1</td><td>74</td></tr><tr><td>N.1</td><td>Preliminaries</td><td>75</td></tr><tr><td>N.2</td><td>The proof</td><td>77</td></tr><tr><td>O</td><td>Proof of Lemma 6.1</td><td>79</td></tr><tr><td>P</td><td>Proof of Theorem 6.2</td><td>80</td></tr><tr><td>Q</td><td>Proof of Theorem 9.1</td><td>80</td></tr><tr><td>R</td><td>Proof of Theorem 9.2</td><td>82</td></tr><tr><td>S</td><td>Proof of Lemma 9.2</td><td>87</td></tr><tr><td>T</td><td>Proof of Theorem 11.2</td><td>87</td></tr><tr><td>U</td><td>Proof of Theorem 11.4</td><td>90</td></tr><tr><td>References</td><td></td><td>97</td></tr></table>
<table><tr><td>B</td><td>Proof of Lemma 3.1</td><td>54</td></tr><tr><td>C</td><td>Proof of Theorem 3.1</td><td>55</td></tr><tr><td>D</td><td>Proof of Lemma 3.2</td><td>59</td></tr><tr><td>E</td><td>Proof of Lemma 3.3</td><td>60</td></tr><tr><td>F</td><td>Proof of Lemma 3.4</td><td>61</td></tr><tr><td>G</td><td>Proof of Lemma 3.6</td><td>62</td></tr><tr><td>H</td><td>Proof of Lemma 3.7</td><td>65</td></tr><tr><td>I</td><td>Proof of Lemma 4.1</td><td>66</td></tr><tr><td>J</td><td>Proof of Theorem 4.1</td><td>66</td></tr><tr><td>K</td><td>Proof of Lemma 5.2</td><td>70</td></tr><tr><td>L</td><td>Proof of Lemma 5.3</td><td>71</td></tr><tr><td>M</td><td>Proof of Lemma 5.4</td><td>72</td></tr><tr><td>N</td><td>Proof of Theorem 6.1</td><td>74</td></tr><tr><td>N.1</td><td>Preliminaries</td><td>75</td></tr><tr><td>N.2</td><td>The proof</td><td>77</td></tr><tr><td>O</td><td>Proof of Lemma 6.1</td><td>79</td></tr><tr><td>P</td><td>Proof of Theorem 6.2</td><td>80</td></tr><tr><td>Q</td><td>Proof of Theorem 9.1</td><td>80</td></tr><tr><td>R</td><td>Proof of Theorem 9.2</td><td>82</td></tr><tr><td>S</td><td>Proof of Lemma 9.2</td><td>87</td></tr><tr><td>T</td><td>Proof of Theorem 11.2</td><td>87</td></tr><tr><td>U</td><td>Proof of Theorem 11.4</td><td>90</td></tr><tr><td colspan="2">References</td><td>97</td></tr></table>
# 1 Introduction

In statistical machine learning, the problem of empirical risk minimization (ERM) with relative entropy regularization (ERM-RER) has been the workhorse for building probability measures on the set of models, without any additional assumption on the statistical description of the datasets. See for instance [2–4] and [5]. Instead of additional statistical assumptions on the datasets, which are typical in Bayesian methods [6], relative entropy regularization requires a reference probability measure on the set of models, which is external to the ERM problem. Often, such a reference measure represents prior knowledge or side information and is chosen for guiding the search of models towards those inducing low empirical risks with high probability over seen and unseen datasets. From this perspective, the reference measure can be seen as an additional degree of freedom to improve the generalization capabilities of machine learning algorithms based on ERM-RER, e.g., Gibbs algorithms [4, 7–16] and [17]. This new degree of freedom is one of the main motivations for regularizing the ERM problem using relative entropy, or more generally, any f-divergence regularization, as discussed in [18, 19] and [20]. Beyond probability measures, as shown in this paper, the reference measure can be any σ-finite measure with arbitrary support. The flexibility introduced by this generalization becomes particularly relevant for the case in which priors are available in the form of probability distributions that can be evaluated up to some normalizing factor, cf. [21], or cannot be represented by probability distributions, e.g., equal preferences among elements of infinite countable sets. For some specific choices of σ-finite reference measures, the ERM-RER boils down to particular cases of special interest: (i) the information-risk minimization problem presented in [22]; (ii) the ERM with differential entropy regularization (ERM-Differ); and (iii) the ERM with discrete entropy regularization (ERM-DisER). See for instance [23, 24] and references therein. From this perspective, the proposed ERM-RER formulation yields a unified mathematical framework that comprises a large class of problems.

When the reference measure is a probability measure, the solution to the ERM-RER problem is known to be unique and correspond to a Gibbs probability measure. Such a Gibbs probability measure has been studied using measure theoretic and information theoretic notions in [8, 22, 25–32]; statistical physics in [2]; PAC (Probably Approximately Correct)-Bayesian learning theory in [33–36]; and proved to be of particular interest in classification problems in [4, 11, 19, 23, 37, 38] and [39]. In the general case in which the reference is a σ-finite measure, a solution to the ERM-RER problem does not always exist. Nonetheless, if it exists, it is shown to be a unique Gibbs probability despite the fact that its partition function is defined with respect to a σ-finite measure. The condition for the existence is mild and is always satisfied when the reference measure is a probability measure, as highlighted above. Interestingly, such a solution is mutually absolutely continuous with the reference measure and most of the properties known for the classical ERM-RER problem are shown to hold
# 1 Introduction

In statistical machine learning, the problem of empirical risk minimization (ERM) with relative entropy regularization (ERM-RER) has been the workhorse for building probability measures on the set of models, without any additional assumption on the statistical description of the datasets. See for instance [2–4] and [5]. Instead of additional statistical assumptions on the datasets, which are typical in Bayesian methods [6], relative entropy regularization requires a reference probability measure on the set of models, which is external to the ERM problem. Often, such a reference measure represents prior knowledge or side information and is chosen for guiding the search of models towards those inducing low empirical risks with high probability over seen and unseen datasets. From this perspective, the reference measure can be seen as an additional degree of freedom to improve the generalization capabilities of machine learning algorithms based on ERM-RER, e.g., Gibbs algorithms [4, 7–16] and [17]. This new degree of freedom is one of the main motivations for regularizing the ERM problem using relative entropy, or more generally, any $f$-divergence regularization, as discussed in [18, 19] and [20]. Beyond probability measures, as shown in this paper, the reference measure can be any $\sigma$-finite measure with arbitrary support. The flexibility introduced by this generalization becomes particularly relevant for the case in which priors are available in the form of probability distributions that can be evaluated up to some normalizing factor, cf. [21], or cannot be represented by probability distributions, e.g., equal preferences among elements of infinite countable sets. For some specific choices of $\sigma$-finite reference measures, the ERM-RER boils down to particular cases of special interest: (i) the information-risk minimization problem presented in [22]; (ii) the ERM with differential entropy regularization (ERM-Differ); and (iii) the ERM with discrete entropy regularization (ERM-DisER). See for instance [23, 24] and references therein. From this perspective, the proposed ERM-RER formulation yields a unified mathematical framework that comprises a large class of problems.

When the reference measure is a probability measure, the solution to the ERM-RER problem is known to be unique and correspond to a Gibbs probability measure. Such a Gibbs probability measure has been studied using measure theoretic and information theoretic notions in [8, 22, 25–32]; statistical physics in [2]; PAC (Probably Approximately Correct)-Bayesian learning theory in [33–36]; and proved to be of particular interest in classification problems in [4, 11, 19, 23, 37, 38] and [39]. In the general case in which the reference is a $\sigma$-finite measure, a solution to the ERM-RER problem does not always exist. Nonetheless, if it exists, it is shown to be a unique Gibbs probability despite the fact that its partition function is defined with respect to a $\sigma$-finite measure. The condition for the existence is mild and is always satisfied when the reference measure is a probability measure, as highlighted above. Interestingly, such a solution is mutually absolutely continuous with the reference measure and most of the properties known for the classical ERM-RER problem are shown to hold
in the most general case. For instance, under certain conditions, the empirical
risk observed when models are sampled from the ERM-RER-optimal probability
measure is a sub-Gaussian random variable that exhibits a PAC guarantee for
the ERM problem without regularization.

When the solution to the ERM-RER problem is used to sample models to
label unseen patterns, the process is known as the Gibbs algorithm. One of
the traditional performance metrics to evaluate the generalization capabilities
of machine learning algorithms is the generalization error, for which closed-
form expressions in terms of information measures are presented in [14]. When
the reference measure is a probability measure, a closed-form expression for
the generalization error of the Gibbs algorithm is presented in [8], while upper
bounds have been derived in [17, 22, 30–36, 40–54], and references therein. In
this work, a new performance metric coined sensitivity, which quantifies the
variations of the expected empirical risk due to deviations from the solution of
the ERM-RER problem is introduced. The sensitivity is defined as the difference
between two quantities: (a) The expectation of the empirical risk with respect to
the solution to the ERM-RER problem; and (b) the expectation of the empirical
risk with respect to an alternative measure. The absolute value of the sensitivity
is shown to be upper bounded by a term that is proportional to the squared-
root of the relative entropy of the alternative measure with respect to the ERM-
RER-optimal measure. Such bound allows providing lower and upper bounds
on the expected empirical risk after a deviation from the ERM-RER-optimal
measure towards an alternative probability measure. More interestingly, the
expectation (with respect to the probability distribution of the datasets) of
the sensitivity to deviations to a specific measure is shown to be equal to the
generalization error of the Gibbs algorithm. Using this result, the closed-form
expression for the generalization error of the Gibbs algorithm presented in [8]
is shown to hold even in the case in which the reference measure is a σ-finite
measure. Moreover, the generalization error is shown to be upper bounded
by a term that is proportional to the squared-root of the lautum information
between the models and the datasets, cf. [55]. This bound is reminiscent of the
result in [32, Theorem 1] in which a similar bound is presented using the mutual
information instead of the lautum information. While [32, Theorem 1] follows
immediately from the variational representation of relative entropy, c.f., [56,
Lemma 4.18 (Transportation Lemma)], the new result follows from the fact
that the empirical risk when models are sampled from the ERM-RER-optimal
probability measure is a sub-Gaussian random variable. Interestingly, the new
upper-bound does not require any of the conditions in [32, Theorem 1].

The remainder of this work is organized as follows. Section 2 introduces two
optimization problems: the ERM and the ERM-RER. The asymmetry of the
relative entropy is analyzed in the context of the ERM-RER and two variants,
coined Type-I and Type-II, are distinguished. The former considers the case in
which the regularization is the relative entropy of the optimization measure with
respect to the reference measure. The latter considers a regularization by the
relative entropy of the reference measure with respect to the optimization mea-
in the most general case. For instance, under certain conditions, the empirical
risk observed when models are sampled from the ERM-RER-optimal probability
measure is a sub-Gaussian random variable that exhibits a PAC guarantee for
the ERM problem without regularization.

When the solution to the ERM-RER problem is used to sample models to
label unseen patterns, the process is known as the Gibbs algorithm. One of
the traditional performance metrics to evaluate the generalization capabilities
of machine learning algorithms is the generalization error, for which closed-
form expressions in terms of information measures are presented in [14]. When
the reference measure is a probability measure, a closed-form expression for
the generalization error of the Gibbs algorithm is presented in [8], while upper
bounds have been derived in [17, 22, 30–36, 40–54], and references therein. In
this work, a new performance metric coined sensitivity, which quantifies the
variations of the expected empirical risk due to deviations from the solution of
the ERM-RER problem is introduced. The sensitivity is defined as the difference
between two quantities: (a) The expectation of the empirical risk with respect to
the solution to the ERM-RER problem; and (b) the expectation of the empirical
risk with respect to an alternative measure. The absolute value of the sensitivity
is shown to be upper bounded by a term that is proportional to the squared-
root of the relative entropy of the alternative measure with respect to the ERM-
RER-optimal measure. Such bound allows providing lower and upper bounds
on the expected empirical risk after a deviation from the ERM-RER-optimal
measure towards an alternative probability measure. More interestingly, the
expectation (with respect to the probability distribution of the datasets) of
the sensitivity to deviations to a specific measure is shown to be equal to the
generalization error of the Gibbs algorithm. Using this result, the closed-form
expression for the generalization error of the Gibbs algorithm presented in [8]
is shown to hold even in the case in which the reference measure is a σ-finite
measure. Moreover, the generalization error is shown to be upper bounded
by a term that is proportional to the squared-root of the lautum information
between the models and the datasets, cf. [55]. This bound is reminiscent of the
result in [32, Theorem 1] in which a similar bound is presented using the mutual
information instead of the lautum information. While [32, Theorem 1] follows
immediately from the variational representation of relative entropy, c.f., [56,
Lemma 4.18 (Transportation Lemma)], the new result follows from the fact
that the empirical risk when models are sampled from the ERM-RER-optimal
probability measure is a sub-Gaussian random variable. Interestingly, the new
upper-bound does not require any of the conditions in [32, Theorem 1].

The remainder of this work is organized as follows. Section 2 introduces two
optimization problems: the ERM and the ERM-RER. The asymmetry of the
relative entropy is analyzed in the context of the ERM-RER and two variants,
coined Type-I and Type-II, are distinguished. The former considers the case in
which the regularization is the relative entropy of the optimization measure with
respect to the reference measure. The latter considers a regularization by the
relative entropy of the reference measure with respect to the optimization mea-
sure. Section 3 presents the solution to the ERM-RER problem in the general case and introduces its main properties. Section 4 introduces two new classes of reference measures and the solution of the ERM-RER problem is shown to exhibit different properties for each class. This section ends by studying the ERM-RER problem in the special case in which the reference measure is a Gibbs probability measure. This special case exhibits a solution that is identical to the solution to an ERM-RER problem whose reference measure is the same used to build the above mentioned Gibbs measure. Section 5 studies the properties of the log-partition function of the ERM-RER-optimal probability measure. The first, second, and third cumulants of the empirical risk when the models are sampled from the ERM-RER-optimal measure and the reference measure are respectively characterized. Section 6 and Section 7 study the properties of the expectation and variance of the empirical risk when the models are sampled from the ERM-RER-optimal probability measure. This mean and variance are compared with the mean and variance of the empirical risk when models are sampled from the reference measure. Section 8 introduces several explicit expressions for the cumulant generating function of the empirical risk when the models are sampled from the ERM-RER-optimal measure. Using these equivalent expressions, under a specific condition, it is shown that the empirical risk is a sub-Gaussian random variable when models are sampled from the ERM-RER-optimal measure. Section 9 describes the monotonic concentration of the ERM-RER-optimal probability measure when the regularization factor tends to zero. Section 10 show that the empirical risk when the models are sampled from the ERM-RER-optimal probability measure exhibits a PAC-type guarantee with respect to the ERM problem without regularization. Finally, Section 11 studies the sensitivity of the expected empirical risk with respect to deviations from the ERM-RER-optimal measure to alternative measures and shows connections with the generalization error and the lautum information. Section 12 ends this work with conclusions and a discussion on the results.

## 2 Empirical Risk Minimization (ERM)

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. Given $n$ data points, with $n \in \mathbb{N}$, denoted by $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$, the corresponding 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. \quad (1)$$

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

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

be such that given a data point $(x, y) \in \mathcal{X} \times \mathcal{Y}$, the risk induced by a model $\theta \in \mathcal{M}$ is $\ell(f(\theta, x), y)$. In the following, the risk function $\ell$ is assumed to be nonnegative and for all $y \in \mathcal{Y}$, $\ell(y, y) = 0$.
sure. Section 3 presents the solution to the ERM-RER problem in the general case and introduces its main properties. Section 4 introduces two new classes of reference measures and the solution of the ERM-RER problem is shown to exhibit different properties for each class. This section ends by studying the ERM-RER problem in the special case in which the reference measure is a Gibbs probability measure. This special case exhibits a solution that is identical to the solution to an ERM-RER problem whose reference measure is the same used to build the above mentioned Gibbs measure. Section 5 studies the properties of the log-partition function of the ERM-RER-optimal probability measure. The first, second, and third cumulants of the empirical risk when the models are sampled from the ERM-RER-optimal measure and the reference measure are respectively characterized. Section 6 and Section 7 study the properties of the expectation and variance of the empirical risk when the models are sampled from the ERM-RER-optimal probability measure. This mean and variance are compared with the mean and variance of the empirical risk when models are sampled from the reference measure. Section 8 introduces several explicit expressions for the cumulant generating function of the empirical risk when the models are sampled from the ERM-RER-optimal measure. Using these equivalent expressions, under a specific condition, it is shown that the empirical risk is a sub-Gaussian random variable when models are sampled from the ERM-RER-optimal measure. Section 9 describes the monotonic concentration of the ERM-RER-optimal probability measure when the regularization factor tends to zero. Section 10 show that the empirical risk when the models are sampled from the ERM-RER-optimal probability measure exhibits a PAC-type guarantee with respect to the ERM problem without regularization. Finally, Section 11 studies the sensitivity of the expected empirical risk with respect to deviations from the ERM-RER-optimal measure to alternative measures and shows connections with the generalization error and the lautum information. Section 12 ends this work with conclusions and a discussion on the results.

## 2 Empirical Risk Minimization (ERM)

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. Given $n$ data points, with $n \in \mathbb{N}$, denoted by $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$, the corresponding 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 (1)$$

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

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

be such that given a data point $(x, y) \in \mathcal{X} \times \mathcal{Y}$, the risk induced by a model $\theta \in \mathcal{M}$ is $\ell(f(\theta, x), y)$. In the following, the risk function $\ell$ is assumed to be nonnegative and for all $y \in \mathcal{Y}$, $\ell(y, y) = 0$.
The empirical risk induced by the model $\theta$, with respect to the dataset $z$ in (1) is determined by the function $L_z: \mathcal{M} \to [0, +\infty]$, which satisfies

$$L_z(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(\theta, x_i), y_i). \qquad (3)$$

Using this notation, the ERM consists of the following optimization problem:

$$\min_{\theta \in \mathcal{M}} L_z(\theta). \qquad (4)$$

Let the set of solutions to the ERM problem in (4) be denoted by

$$\mathcal{T}(z) \triangleq \arg \min_{\theta \in \mathcal{M}} L_z(\theta). \qquad (5)$$

Note that if the set $\mathcal{M}$ is finite, the ERM problem in (4) always possesses a solution, and thus, $|\mathcal{T}(z)| > 0$. Nonetheless, in general, the ERM problem might not necessarily possess a solution, i.e., $|\mathcal{T}(z)| = 0$.

## 2.1 Notation and Main Assumptions

In the following, given a measurable space $(\Omega, \mathcal{F})$, the notation $\triangleq (\Omega, \mathcal{F})$ is used to represent the set of $\sigma$-finite measures that can be defined over $(\Omega, \mathcal{F})$. Given a measure $Q \in \triangleq (\Omega, \mathcal{F})$, the subset $\triangleq_Q (\Omega, \mathcal{F})$ of $\triangleq (\Omega, \mathcal{F})$ contains all $\sigma$-finite measures that are absolutely continuous with respect to the measure $Q$. Alternatively, the subset $\nabla_Q (\Omega, \mathcal{F})$ of $\triangleq (\Omega, \mathcal{F})$ contains all probability measures $P$ such that $Q$ is absolutely continuous with respect to $P$. Given a set $\mathcal{A} \subset \mathbb{R}^d$, the Borel $\sigma$-field over $\mathcal{A}$ is denoted by $\mathcal{B}(\mathcal{A})$.

The main assumption adopted in this work is that the function $L_z$ in (3) is measurable with respect to the Borel measurable spaces $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ and $([0, +\infty], \mathcal{B}([0, +\infty]))$.

## 2.2 Relative Entropy Extended to $\sigma$-Finite Measures

In this work, the relative entropy, which is usually defined for probability measures, is extended to $\sigma$-finite measures.

**Definition 2.1** (Generalized Relative Entropy). Given two $\sigma$-finite 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), \qquad (6)$$

where the function $\frac{dP}{dQ}$ is the Radon-Nikodym derivative of $P$ with respect to $Q$.

The relative entropy exhibits a property often referred to as the information inequality [57, Theorem 2.6.3] in the case of probability measures on $(\Omega, \mathcal{F})$, with $\Omega$ a countable set. The following theorem explores this property in a more general scenario.
The empirical risk induced by the model $\theta$, with respect to the dataset $z$ in (1) is determined by the function $L_z: \mathcal{M} \to [0, +\infty]$, which satisfies

$$L_z(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(\theta, x_i), y_i). \qquad (3)$$

Using this notation, the ERM consists of the following optimization problem:

$$\min_{\theta \in \mathcal{M}} L_z(\theta). \qquad (4)$$

Let the set of solutions to the ERM problem in (4) be denoted by

$$\mathcal{T}(z) \triangleq \arg \min_{\theta \in \mathcal{M}} L_z(\theta). \qquad (5)$$

Note that if the set $\mathcal{M}$ is finite, the ERM problem in (4) always possesses a solution, and thus, $|\mathcal{T}(z)| > 0$. Nonetheless, in general, the ERM problem might not necessarily possess a solution, i.e., $|\mathcal{T}(z)| = 0$.

## 2.1 Notation and Main Assumptions

In the following, given a measurable space $(\Omega, \mathcal{F})$, the notation $\triangle (\Omega, \mathcal{F})$ is used to represent the set of $\sigma$-finite measures that can be defined over $(\Omega, \mathcal{F})$. Given a measure $Q \in \triangle (\Omega, \mathcal{F})$, the subset $\triangle_Q (\Omega, \mathcal{F})$ of $\triangle (\Omega, \mathcal{F})$ contains all $\sigma$-finite measures that are absolutely continuous with respect to the measure $Q$. Alternatively, the subset $\triangledown_Q (\Omega, \mathcal{F})$ of $\triangle (\Omega, \mathcal{F})$ contains all probability measures $P$ such that $Q$ is absolutely continuous with respect to $P$. Given a set $A \subset \mathbb{R}^d$, the Borel $\sigma$-field over $A$ is denoted by $\mathcal{B}(A)$.

The main assumption adopted in this work is that the function $L_z$ in (3) is measurable with respect to the Borel measurable spaces $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ and $([0, +\infty], \mathcal{B}([0, +\infty]))$.

## 2.2 Relative Entropy Extended to $\sigma$-Finite Measures

In this work, the relative entropy, which is usually defined for probability measures, is extended to $\sigma$-finite measures.

**Definition 2.1 (Generalized Relative Entropy).** Given two $\sigma$-finite 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), \qquad (6)$$

where the function $\frac{dP}{dQ}$ is the Radon-Nikodym derivative of $P$ with respect to $Q$.

The relative entropy exhibits a property often referred to as the information inequality [57, Theorem 2.6.3] in the case of probability measures on $(\Omega, \mathcal{F})$, with $\Omega$ a countable set. The following theorem explores this property in a more general scenario.
**Theorem 2.1.** If P and Q are both probability measures on a general measurable space $(\Omega, \mathcal{F})$, with P absolutely continuous with respect to Q, then,

$$D(P||Q) \ge 0, \qquad (7)$$

with equality if and only if P and Q are identical.

*Proof:* Consider the function $f: [0, \infty) \to \mathbb{R}$ such that for all $x \in (0, +\infty)$, $f(x) = x \log(x)$ and $f(0) = 0$. Note that $f$ is strictly convex. If P and Q are both probability measures on the measurable space $(\Omega, \mathcal{F})$, the following holds:

$$D(P||Q) = \int \frac{dP}{dQ}(x) \log \left( \frac{dP}{dQ}(x) \right) dQ(x) \qquad (8)$$

$$= \int f \left( \frac{dP}{dQ}(x) \right) dQ(x) \qquad (9)$$

$$\ge f \left( \int \frac{dP}{dQ}(x) dQ(x) \right) \qquad (10)$$

$$=f(1) \qquad (11)$$

$$=0, \qquad (12)$$

where the inequality (11) follows from Jensen's inequality [58, Section 6.3.5]. Equality in (11) holds if and only if for all $x \in \text{supp} Q$, $\frac{dP}{dQ}(x) = 1$, which implies that both P and Q are identical. This completes proof. ■

If Q is not a probability measure, then it might be observed that $D(P||Q) < 0$. Consider for instance the case in which P is a zero-mean Gaussian probability measure with variance $\sigma^2$ and Q is the Lebesgue measure on $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$. Hence, the Radon-Nikodym derivative $\frac{dP}{dQ}$ is the Gaussian probability density function such that for all $x \in \mathbb{R}$,

$$\frac{dP}{dQ}(x) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp \left( -\frac{x^2}{2\sigma^2} \right). \qquad (13)$$

Under this assumption, the relative entropy of P with respect to Q is the negative of the differential entropy of P. That is,

$$D(P||Q) = -\frac{1}{2} \log (2\pi\epsilon\sigma^2), \qquad (14)$$

with $\epsilon$ being Néper's constant. See for instance [57, Example 8.1.2]. Hence, $D(P||Q)$ is negative for all $\sigma^2 \in (\frac{1}{2\pi\epsilon}, +\infty)$ and nonnegative for all $\sigma^2 \in (0, \frac{1}{2\pi\epsilon}]$. Finally, note also that

$$\lim_{\sigma^2 \to 0} D(P||Q) = +\infty, \text{ and} \qquad (15)$$

$$\lim_{\sigma^2 \to +\infty} D(P||Q) = -\infty. \qquad (16)$$

A central observation from (14) is that the equality $D(P||Q) = 0$ does not necessarily imply that P and Q are identical measures. For instance, when
**Theorem 2.1.** If P and Q are both probability measures on a general measurable space $(\Omega, \mathcal{F})$, with P absolutely continuous with respect to Q, then,

$$D(P||Q) \ge 0, \qquad (7)$$

with equality if and only if P and Q are identical.

*Proof:* Consider the function $f: [0, \infty) \to \mathbb{R}$ such that for all $x \in (0, +\infty)$, $f(x) = x \log(x)$ and $f(0) = 0$. Note that $f$ is strictly convex. If P and Q are both probability measures on the measurable space $(\Omega, \mathcal{F})$, the following holds:

$$D(P||Q) = \int \frac{dP}{dQ}(x) \log \left( \frac{dP}{dQ}(x) \right) dQ(x) \qquad (8)$$

$$= \int f \left( \frac{dP}{dQ}(x) \right) dQ(x) \qquad (9)$$

$$\ge f \left( \int \frac{dP}{dQ}(x) dQ(x) \right) \qquad (10)$$

$$=f(1) \qquad (11)$$

$$=0, \qquad (12)$$

where the inequality (11) follows from Jensen's inequality [58, Section 6.3.5]. Equality in (11) holds if and only if for all $x \in \text{supp } Q$, $\frac{dP}{dQ}(x) = 1$, which implies that both P and Q are identical. This completes proof. ■

If Q is not a probability measure, then it might be observed that $D(P||Q) < 0$. Consider for instance the case in which P is a zero-mean Gaussian probability measure with variance $\sigma^2$ and Q is the Lebesgue measure on $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$. Hence, the Radon-Nikodym derivative $\frac{dP}{dQ}$ is the Gaussian probability density function such that for all $x \in \mathbb{R}$,

$$\frac{dP}{dQ}(x) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{x^2}{2\sigma^2}\right). \qquad (13)$$

Under this assumption, the relative entropy of P with respect to Q is the negative of the differential entropy of P. That is,

$$D(P||Q) = -\frac{1}{2} \log (2\pi\epsilon\sigma^2), \qquad (14)$$

with $\epsilon$ being Néper's constant. See for instance [57, Example 8.1.2]. Hence, $D(P||Q)$ is negative for all $\sigma^2 \in (\frac{1}{2\pi\epsilon}, +\infty)$ and nonnegative for all $\sigma^2 \in (0, \frac{1}{2\pi\epsilon}]$. Finally, note also that

$$\lim_{\sigma^2 \to 0} D(P||Q) = +\infty, \text{ and} \qquad (15)$$

$$\lim_{\sigma^2 \to +\infty} D(P||Q) = -\infty. \qquad (16)$$

A central observation from (14) is that the equality $D(P||Q) = 0$ does not necessarily imply that P and Q are identical measures. For instance, when
$\sigma^2 = \frac{1}{2\pi\epsilon}$ in (15), it holds that $D(P\|Q) = 0$, while $P$ is a Gaussian probability measure and $Q$ is the Lebesgue measure.

The following property, known for the case of probability measures as the joint-convexity of the relative entropy, is extended by the following theorem.

**Theorem 2.2.** Let $P_1$ and $P_2$ be two probability measures and $Q_1$ and $Q_2$ be two $\sigma$-finite measures, all on the same measurable space. For all $i \in \{1, 2\}$, let $P_i$ be absolutely continuous with respect to $Q_i$. Then, for all $\lambda \in [0, 1]$,

$$D(\lambda P_1 + (1-\lambda)P_2 \| \lambda Q_1 + (1-\lambda)Q_2) \le \lambda D(P_1 \| Q_1) + (1-\lambda)D(P_2 \| Q_2). \quad (17)$$

Equality in (17) holds if and only if $P_1 = P_2$ and $Q_1 = Q_2$.

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

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

## 2.3 ERM with Relative Entropy Regularization

Given a dataset, the *expected empirical risk* induced by a probability measure $P \in \Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ is defined as follows.

**Definition 2.2 (Expected Empirical Risk).** Let $P$ be a probability measure in $\Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$. The *expected empirical risk* with respect to the dataset $z$ in (1) induced by the measure $P$ is

$$R_z(P) = \int L_z(\theta) dP(\theta), \quad (18)$$

where the function $L_z$ is defined in (3).

The ERM-RER problem is parametrized by a $\sigma$-finite measure in $\Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ and a positive real, which are referred to as the *reference measure* and the *regularization factor*, respectively. Let $Q \in \Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ be a $\sigma$-finite measure and let $\lambda$ be a positive real. The ERM-RER problem, with parameters $Q$ and $\lambda$, consists of the following optimization problem:

$$\min_{P \in \Delta_Q(\mathcal{M}, \mathcal{B}(\mathcal{M}))} R_z(P) + \lambda D(P \| Q), \quad (19a)$$

$$\text{s. t.} \quad \int dP(\theta) = 1, \quad (19b)$$

where the dataset $z$ is in (1), and the functional $R_z$ is defined in (18).

## 2.4 Type-I and Type-II Relative Entropy Regularization

The optimization problem in (19) is coined Type-I ERM-RER in [59] in the aim of distinguishing it from the optimization problem

$$\min_{P \in \nabla_Q(\mathcal{M}, \mathcal{B}(\mathcal{M}))} R_z(P) + \lambda D(Q \| P), \quad (20a)$$

$$\text{s. t.} \quad \int dP(\theta) = 1, \quad (20b)$$
$\sigma^2 = \frac{1}{2\pi\epsilon}$ in (15), it holds that $D(P\|Q) = 0$, while $P$ is a Gaussian probability measure and $Q$ is the Lebesgue measure.

The following property, known for the case of probability measures as the joint-convexity of the relative entropy, is extended by the following theorem.

**Theorem 2.2.** Let $P_1$ and $P_2$ be two probability measures and $Q_1$ and $Q_2$ be two $\sigma$-finite measures, all on the same measurable space. For all $i \in \{1, 2\}$, let $P_i$ be absolutely continuous with respect to $Q_i$. Then, for all $\lambda \in [0, 1]$,

$$D(\lambda P_1 + (1-\lambda)P_2 \| \lambda Q_1 + (1-\lambda)Q_2) \le \lambda D(P_1 \| Q_1) + (1-\lambda)D(P_2 \| Q_2). \quad (17)$$

Equality in (17) holds if and only if $P_1 = P_2$ and $Q_1 = Q_2$.

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

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

## 2.3 ERM with Relative Entropy Regularization

Given a dataset, the *expected empirical risk* induced by a probability measure $P \in \Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ is defined as follows.

**Definition 2.2** (Expected Empirical Risk). Let $P$ be a probability measure in $\Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$. The *expected empirical risk* with respect to the dataset $z$ in (1) induced by the measure $P$ is

$$R_z(P) = \int L_z(\theta) dP(\theta), \quad (18)$$

where the function $L_z$ is defined in (3).

The ERM-RER problem is parametrized by a $\sigma$-finite measure in $\Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ and a positive real, which are referred to as the *reference measure* and the *regularization factor*, respectively. Let $Q \in \Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ be a $\sigma$-finite measure and let $\lambda$ be a positive real. The ERM-RER problem, with parameters $Q$ and $\lambda$, consists of the following optimization problem:

$$\min_{P \in \Delta_Q(\mathcal{M}, \mathcal{B}(\mathcal{M}))} R_z(P) + \lambda D(P \| Q), \quad (19a)$$

$$\text{s. t.} \quad \int dP(\theta) = 1, \quad (19b)$$

where the dataset $z$ is in (1), and the functional $R_z$ is defined in (18).

## 2.4 Type-I and Type-II Relative Entropy Regularization

The optimization problem in (19) is coined Type-I ERM-RER in [59] in the aim of distinguishing it from the optimization problem

$$\min_{P \in \nabla_Q(\mathcal{M}, \mathcal{B}(\mathcal{M}))} R_z(P) + \lambda D(Q \| P), \quad (20a)$$

$$\text{s. t.} \quad \int dP(\theta) = 1, \quad (20b)$$
which is coined Type-II ERM-RER.

The Type-II ERM-RER problem in (20), when $Q$ is a probability measure, exhibits a solution that is identical to the solution to the following Type-I ERM-RER problem [59, Theorem 1]:

$$ \min_{P \in \Delta_Q(M, \mathcal{B}(M))} \int \log(\beta + \mathbf{L}_z(\boldsymbol{\nu})) dP(\boldsymbol{\nu}) + D(P \| Q), \quad (21a) $$

$$ \text{s. t.} \quad \int dP(\boldsymbol{\theta}) = 1, \qquad (21b) $$

where $\beta$ is a constant chosen to satisfy

$$ \int \frac{\lambda}{\beta + \mathbf{L}_z(\boldsymbol{\nu})} dQ(\boldsymbol{\nu}) = 1. \qquad (21c) $$

Essentially, by appropriately transforming the objective function, an equivalence can be established between Type-I and Type-II ERM-RER problems. Hence, without loss of generality, the remainder of this work focuses exclusively on Type-I ERM-RER, which is simply referred to as ERM-RER.

## 3 The Solution to the ERM-RER Problem

The solution to the ERM-RER problem in (19) is presented in terms of two objects. First, the function $K_{Q,z}: \mathbb{R} \to \mathbb{R} \cup \{+\infty\}$ such that for all $t \in \mathbb{R}$,

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

with $\mathbf{L}_z$ in (3). Second, the set $K_{Q,z} \subset (0, +\infty)$, which is defined by

$$ K_{Q,z} \triangleq \{s \in (0, +\infty) : K_{Q,z} \left(-\frac{1}{s}\right) < +\infty\}. \qquad (23) $$

The notation for the function $K_{Q,z}$ and the set $K_{Q,z}$ are chosen such that their parametrization by (or dependence on) the dataset $z$ in (1) and the $\sigma$-finite measure $Q$ in (19) are highlighted.

The following lemma describes the set $K_{Q,z}$.

**Lemma 3.1.** The set $K_{Q,z}$ in (23) is a convex subset of $\mathbb{R}$. If the measure $Q$ in (19) is a probability measure, then, the set $K_{Q,z}$ in (23) satisfies

$$ K_{Q,z} = (0, +\infty). \qquad (24) $$

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

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

Using this notation, the solution to the ERM-RER problem in (19) is presented by the following theorem.
which is coined Type-II ERM-RER.

The Type-II ERM-RER problem in (20), when $Q$ is a probability measure, exhibits a solution that is identical to the solution to the following Type-I ERM-RER problem [59, Theorem 1]:

$$ \min_{P \in \Delta_Q(M, \mathcal{B}(M))} \int \log(\beta + \mathbf{L}_z(\boldsymbol{\nu})) dP(\boldsymbol{\nu}) + D(P \| Q), \quad (21a) $$

$$ \text{s. t.} \quad \int dP(\boldsymbol{\theta}) = 1, \qquad (21b) $$

where $\beta$ is a constant chosen to satisfy

$$ \int \frac{\lambda}{\beta + \mathbf{L}_z(\boldsymbol{\nu})} dQ(\boldsymbol{\nu}) = 1. \qquad (21c) $$

Essentially, by appropriately transforming the objective function, an equivalence can be established between Type-I and Type-II ERM-RER problems. Hence, without loss of generality, the remainder of this work focuses exclusively on Type-I ERM-RER, which is simply referred to as ERM-RER.

# 3 The Solution to the ERM-RER Problem

The solution to the ERM-RER problem in (19) is presented in terms of two objects. First, the function $K_{Q,z}: \mathbb{R} \to \mathbb{R} \cup \{+\infty\}$ such that for all $t \in \mathbb{R}$,

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

with $\mathbf{L}_z$ in (3). Second, the set $K_{Q,z} \subset (0, +\infty)$, which is defined by

$$ K_{Q,z} \triangleq \{s \in (0, +\infty) : K_{Q,z} \left(-\frac{1}{s}\right) < +\infty\}. \qquad (23) $$

The notation for the function $K_{Q,z}$ and the set $K_{Q,z}$ are chosen such that their parametrization by (or dependence on) the dataset $z$ in (1) and the $\sigma$-finite measure $Q$ in (19) are highlighted.

The following lemma describes the set $K_{Q,z}$.

**Lemma 3.1.** The set $K_{Q,z}$ in (23) is a convex subset of $\mathbb{R}$. If the measure $Q$ in (19) is a probability measure, then, the set $K_{Q,z}$ in (23) satisfies

$$ K_{Q,z} = (0, +\infty). \qquad (24) $$

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

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

Using this notation, the solution to the ERM-RER problem in (19) is presented by the following theorem.
**Theorem 3.1.** If $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23), the solution to the optimization problem in (19) is a unique probability measure, denoted by $P_{\Theta|Z=z}^{(Q,\lambda)}$, which satisfies for all $\theta \in \text{supp } Q$,

$$ \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 (25) $$

where the function $L_z$ is defined in (3) and the function $K_{Q,z}$ is defined in (22).

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

Contrary to the ERM problem in (4), which does not necessarily possess a solution, the ERM-RER problem in (19) always possess a solution when $Q$ is a probability measure. This is essentially because the set $K_{Q,z}$ is the set of all positive reals (Lemma 3.1), and thus, the condition $\lambda \in K_{Q,z}$ is always verified. On the contrary, when $Q$ is a $\sigma$-finite measure, the solution to the ERM-RER problem in (19) depends on whether $\lambda \in K_{Q,z}$. If a solution exists, it is $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25), which is unique and corresponds to a Gibbs probability measure [60]. The function $K_{Q,z}$ is often referred to as the log-partition function, see for instance, [61, Section 7.3.1].

The following lemma shows that the Radon-Nikodym derivative in (25) is both nonnegative and finite.

**Lemma 3.2.** The Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25) satisfies for all $\theta \in \text{supp } Q$ that

$$ \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) < +\infty. \quad (26) $$

Moreover, it is strictly positive almost surely with respect to $Q$.

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

Theorem 3.1 has shown that the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is absolutely continuous with respect to the measure $Q$. The following lemma shows that the converse is also true.

**Lemma 3.3.** The $\sigma$-finite measure $Q$ and the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) are mutually absolutely continuous.

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

The relevance of Lemma 3.3 is that it shows that if $\lambda \in K_{Q,z}$, the corresponding collections of negligible sets with respect to the measures $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ are identical. The following lemma shows that the negligible sets with respect to the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) are invariant with respect to $\lambda$.

**Lemma 3.4.** For all $(\alpha, \beta) \in K_{Q,z} \times K_{Q,z}$, with $K_{Q,z}$ in (23), assume that the probability measures $P_{\Theta|Z=z}^{(Q,\alpha)}$ and $P_{\Theta|Z=z}^{(Q,\beta)}$ satisfy (25) with $\lambda = \alpha$ and $\lambda = \beta$, respectively. Then, $P_{\Theta|Z=z}^{(Q,\alpha)}$ and $P_{\Theta|Z=z}^{(Q,\beta)}$ are mutually absolutely continuous.
**Theorem 3.1.** If $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23), the solution to the optimization problem in (19) is a unique probability measure, denoted by $P_{\Theta|Z=z}^{(Q,\lambda)}$, which satisfies for all $\theta \in \text{supp } Q$,

$$ \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 (25) $$

where the function $L_z$ is defined in (3) and the function $K_{Q,z}$ is defined in (22).

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

Contrary to the ERM problem in (4), which does not necessarily possess a solution, the ERM-RER problem in (19) always possess a solution when $Q$ is a probability measure. This is essentially because the set $K_{Q,z}$ is the set of all positive reals (Lemma 3.1), and thus, the condition $\lambda \in K_{Q,z}$ is always verified. On the contrary, when $Q$ is a $\sigma$-finite measure, the solution to the ERM-RER problem in (19) depends on whether $\lambda \in K_{Q,z}$. If a solution exists, it is $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25), which is unique and corresponds to a Gibbs probability measure [60]. The function $K_{Q,z}$ is often referred to as the *log-partition function*, see for instance, [61, Section 7.3.1].

The following lemma shows that the Radon-Nikodym derivative in (25) is both nonnegative and finite.

**Lemma 3.2.** *The Radon-Nikodym derivative* $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ *in (25) satisfies for all* $\theta \in \text{supp } Q$ *that*

$$ \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) < +\infty. \quad (26) $$

Moreover, it is strictly positive almost surely with respect to $Q$.

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

Theorem 3.1 has shown that the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is absolutely continuous with respect to the measure $Q$. The following lemma shows that the converse is also true.

**Lemma 3.3.** *The $\sigma$-finite measure $Q$ and the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) are mutually absolutely continuous.*

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

The relevance of Lemma 3.3 is that it shows that if $\lambda \in K_{Q,z}$, the corresponding collections of negligible sets with respect to the measures $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ are identical. The following lemma shows that the negligible sets with respect to the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) are invariant with respect to $\lambda$.

**Lemma 3.4.** For all $(\alpha, \beta) \in K_{Q,z} \times K_{Q,z}$, with $K_{Q,z}$ in (23), assume that the probability measures $P_{\Theta|Z=z}^{(Q,\alpha)}$ and $P_{\Theta|Z=z}^{(Q,\beta)}$ satisfy (25) with $\lambda = \alpha$ and $\lambda = \beta$, respectively. Then, $P_{\Theta|Z=z}^{(Q,\alpha)}$ and $P_{\Theta|Z=z}^{(Q,\beta)}$ are mutually absolutely continuous.
Proof: The proof is presented in Appendix F.

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

Particular assumptions on the set $\mathcal{M}$ and the reference measure $Q$ lead to well-known instances of the ERM-RER problem in (19), as discussed hereunder.

## 3.1 Examples

Three examples are of particular interest: (a) The set $\mathcal{M} \subset \mathbb{R}^d$ is countable and the measure $Q$ is the counting measure in $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, which leads to the ERM-DisER problem; (b) The set $\mathcal{M}$ is an uncountable subset of $\mathbb{R}^d$, and $Q$ is the Lebesgue measure on $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, which leads to the ERM-DiffER problem; and (c) The set $\mathcal{M}$ and the measure $Q$ form a Borel probability measure space $(\mathcal{M}, \mathcal{B}(\mathcal{M}), Q)$, which leads to the information-risk minimization problem.

### 3.1.1 ERM with Discrete Entropy Regularization

When the set $\mathcal{M} \subset \mathbb{R}^d$ is countable and the $\sigma$-finite measure $Q$ in (19) is the counting measure in $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, given a probability measure $P \in \Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, the Radon-Nikodym derivative $\frac{dP}{dQ}$ is a probability mass function, denoted by $p$. Thus, the relative entropy $D(P||Q)$ is equivalent to the negative of the discrete entropy induced by $p$ [57, Chapter 2], denoted by $H(p)$. In this case, the ERM-RER in (19) can be re-written as the following ERM-DisER problem:

$$ \min_{p} \sum_{\theta \in \mathcal{M}} \mathbb{L}_{z}(\theta) p(\theta) - \lambda H(p), \qquad (27) $$

where the optimization domain in (27) is the set of probability mass functions that can be defined over the measure space $\Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$. In this special case, the probability measure $P_{\Theta|Z=z}^{(Q, \lambda)}$ in (25) whose probability mass function is the solution to the ERM-DisER problem in (27) satisfies

$$ \frac{dP_{\Theta|Z=z}^{(Q, \lambda)}}{dQ}(\theta) = \frac{\exp\left(-\frac{\mathbb{L}_z(\theta)}{\lambda}\right)}{\sum_{\nu \in \mathcal{M}} \exp\left(-\frac{\mathbb{L}_z(\nu)}{\lambda}\right)}, \qquad (28) $$

which describes the discrete Gibbs probability measure on $\Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, with temperature parameter $\lambda$, and energy function $\mathbb{L}_z$ in (3).

### 3.1.2 ERM with Differential Entropy Regularization

When $\mathcal{M} \subset \mathbb{R}^d$ is uncountable and the $\sigma$-finite measure $Q$ in (19) is the Lebesgue measure in $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, for all probability measures $P \in \Delta_Q(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, the Radon-Nikodym derivative $\frac{dP}{dQ}$ is a probability density function, denoted by $g$. Thus, the relative entropy $D(P||Q)$ is equivalent to the negative of the differential entropy induced by $g$ [57, Chapter 8], denoted by $h(g)$. In this
Proof: The proof is presented in Appendix F.

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

Particular assumptions on the set $\mathcal{M}$ and the reference measure $Q$ lead to well-known instances of the ERM-RER problem in (19), as discussed hereunder.

## 3.1 Examples

Three examples are of particular interest: (a) The set $\mathcal{M} \subset \mathbb{R}^d$ is countable and the measure $Q$ is the counting measure in $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, which leads to the ERM-DisER problem; (b) The set $\mathcal{M}$ is an uncountable subset of $\mathbb{R}^d$, and $Q$ is the Lebesgue measure on $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, which leads to the ERM-DiffER problem; and (c) The set $\mathcal{M}$ and the measure $Q$ form a Borel probability measure space $(\mathcal{M}, \mathcal{B}(\mathcal{M}), Q)$, which leads to the information-risk minimization problem.

### 3.1.1 ERM with Discrete Entropy Regularization

When the set $\mathcal{M} \subset \mathbb{R}^d$ is countable and the $\sigma$-finite measure $Q$ in (19) is the counting measure in $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, given a probability measure $P \in \Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, the Radon-Nikodym derivative $\frac{dP}{dQ}$ is a probability mass function, denoted by $p$. Thus, the relative entropy $D(P||Q)$ is equivalent to the negative of the discrete entropy induced by $p$ [57, Chapter 2], denoted by $H(p)$. In this case, the ERM-RER in (19) can be re-written as the following ERM-DisER problem:

$$ \min_{p} \sum_{\theta \in \mathcal{M}} \mathbb{L}_{z}(\theta) p(\theta) - \lambda H(p), \qquad (27) $$

where the optimization domain in (27) is the set of probability mass functions that can be defined over the measure space $\Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$. In this special case, the probability measure $P_{\Theta|Z=z}^{(Q, \lambda)}$ in (25) whose probability mass function is the solution to the ERM-DisER problem in (27) satisfies

$$ \frac{dP_{\Theta|Z=z}^{(Q, \lambda)}}{dQ}(\theta) = \frac{\exp\left(-\frac{\mathbb{L}_z(\theta)}{\lambda}\right)}{\sum_{\nu \in \mathcal{M}} \exp\left(-\frac{\mathbb{L}_z(\nu)}{\lambda}\right)}, \qquad (28) $$

which describes the discrete Gibbs probability measure on $\Delta(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, with temperature parameter $\lambda$, and energy function $\mathbb{L}_z$ in (3).

### 3.1.2 ERM with Differential Entropy Regularization

When $\mathcal{M} \subset \mathbb{R}^d$ is uncountable and the $\sigma$-finite measure $Q$ in (19) is the Lebesgue measure in $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, for all probability measures $P \in \Delta_Q(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, the Radon-Nikodym derivative $\frac{dP}{dQ}$ is a probability density function, denoted by $g$. Thus, the relative entropy $D(P||Q)$ is equivalent to the negative of the differential entropy induced by $g$ [57, Chapter 8], denoted by $h(g)$. In this
special case, the ERM-RER in (19) can be re-written as the following ERM-DiffER problem:

$$ \min_{g} \int_{\mathcal{M}} \mathbf{L}_z(\boldsymbol{\theta}) g(\boldsymbol{\theta}) \, d\boldsymbol{\theta} - \lambda h(g), \qquad (29) $$

where the optimization domain in (29) is the set of probability density functions that can be defined over the measure space $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$. The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) whose probability density function is the solution to the ERM-RER problem in (29) satisfies

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) = \frac{\exp\left(-\frac{\mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right)}{\int_{\mathcal{M}} \exp\left(-\frac{\mathbf{L}_z(\boldsymbol{\nu})}{\lambda}\right) \mathrm{d}\boldsymbol{\nu}}, \qquad (30) $$

which describes the absolutely continuous Gibbs probability measure with temperature parameter $\lambda$ and energy function $\mathbf{L}_z$ in (3).

Both, the ERM-DiffER and ERM-DisER problems are closely related to those typically arising while using Jayne's maximum entropy principle [62, 63] for classification problems such as those in [23, 37, 38], and [64].

### 3.1.3 Information-Risk Minimization

When $Q$ is a probability measure, the ERM-RER in (19) is equivalent to the information-risk minimization (IRM) problem in [22]. The IRM problem in (19) is known to possess a unique solution equal to the Gibbs probability measure in (25), as independently shown in [22, 32, 60, 65, 66] and [67].

## 3.2 Bounds on the Radon-Nikodym Derivative

The Radon-Nikodym derivative $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ in (25) is greater for models inducing smaller empirical risks, as shown by the following corollary of Theorem 3.1.

**Corollary 3.1.** The Radon-Nikodym derivative $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ in (25) satisfies for all $(\boldsymbol{\theta}_1, \boldsymbol{\theta}_2) \in \mathrm{supp} Q \times \mathrm{supp} Q$, with $\mathbf{L}_z(\boldsymbol{\theta}_2) \le \mathbf{L}_z(\boldsymbol{\theta}_1)$, that

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}_1) \le \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}_2), \qquad (31) $$

with equality if and only if $\mathbf{L}_z(\boldsymbol{\theta}_1) = \mathbf{L}_z(\boldsymbol{\theta}_2)$.

The intuition that follows from corollary 3.1 is that under the assumption that the ERM problem in (4) possesses a solution in the support of the reference measure, i.e., $\mathcal{T}(z) \cap \mathrm{supp} Q$ is not empty, with $\mathcal{T}(z)$ in (5), the maximum of the function $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ in (25) is achieved by the models in $\mathcal{T}(z) \cap \mathrm{supp} Q$. When the Radon-Nikodym derivative $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ in (25) is either the probability mass
special case, the ERM-RER in (19) can be re-written as the following ERM-DiffER problem:

$$ \min_{g} \int_{\mathcal{M}} \mathbf{L}_z(\boldsymbol{\theta}) g(\boldsymbol{\theta}) \mathrm{d}\boldsymbol{\theta} - \lambda h(g), \qquad (29) $$

where the optimization domain in (29) is the set of probability density functions that can be defined over the measure space $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$. The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) whose probability density function is the solution to the ERM-RER problem in (29) satisfies

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) = \frac{\exp\left(-\frac{\mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right)}{\int_{\mathcal{M}} \exp\left(-\frac{\mathbf{L}_z(\boldsymbol{\nu})}{\lambda}\right) \mathrm{d}\boldsymbol{\nu}}, \qquad (30) $$

which describes the absolutely continuous Gibbs probability measure with temperature parameter $\lambda$ and energy function $\mathbf{L}_z$ in (3).

Both, the ERM-DiffER and ERM-DisER problems are closely related to those typically arising while using Jayne's maximum entropy principle [62, 63] for classification problems such as those in [23, 37, 38], and [64].

### 3.1.3 Information-Risk Minimization

When $Q$ is a probability measure, the ERM-RER in (19) is equivalent to the information-risk minimization (IRM) problem in [22]. The IRM problem in (19) is known to possess a unique solution equal to the Gibbs probability measure in (25), as independently shown in [22, 32, 60, 65, 66] and [67].

## 3.2 Bounds on the Radon-Nikodym Derivative

The Radon-Nikodym derivative $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ in (25) is greater for models inducing smaller empirical risks, as shown by the following corollary of Theorem 3.1.

**Corollary 3.1.** The Radon-Nikodym derivative $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ in (25) satisfies for all $(\theta_1, \theta_2) \in \mathrm{supp} Q \times \mathrm{supp} Q$, with $\mathbf{L}_z(\theta_2) \le \mathbf{L}_z(\theta_1)$, that

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}_1) \le \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}_2), \qquad (31) $$

with equality if and only if $\mathbf{L}_z(\theta_1) = \mathbf{L}_z(\theta_2)$.

The intuition that follows from corollary 3.1 is that under the assumption that the ERM problem in (4) possesses a solution in the support of the reference measure, i.e., $\mathcal{T}(z) \cap \mathrm{supp} Q$ is not empty, with $\mathcal{T}(z)$ in (5), the maximum of the function $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ in (25) is achieved by the models in $\mathcal{T}(z) \cap \mathrm{supp} Q$. When the Radon-Nikodym derivative $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ in (25) is either the probability mass
function in (28) or the probability density function in (30), Corollary 3.1 shows that the elements of the set $\mathcal{T}(z) \cap \text{supp} Q$ are the modes of the corresponding probability density function or probability mass function.

## 3.3 Asymptotes of the Radon-Nikodym Derivative

The following lemma describes the asymptotic behavior of the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25) when the regularization factor increases, i.e., $\lambda \to +\infty$ and the reference measure $Q$ is a probability measure.

**Lemma 3.5.** Let the measure $Q$ in (19) be a probability measure. Then, for all $\theta \in \text{supp} Q$, the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25) satisfies

$$ \lim_{\lambda \to +\infty} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 1. \qquad (32) $$

*Proof:* From Theorem 3.1, it follows that for all $\theta \in \text{supp} Q$,

$$ \lim_{\lambda \to +\infty} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \lim_{\lambda \to +\infty} \frac{\exp\left(-\frac{L_z(\theta)}{\lambda}\right)}{\int \exp\left(-\frac{L_z(\nu)}{\lambda}\right) dQ(\nu)} \qquad (33) $$

$$ = \frac{1}{\int dQ(\nu)} \qquad (34) $$

$$ =1, \qquad (35) $$

where the function $L_z$ is defined in (3). This completes the proof. ■

Lemma 3.5 unveils the fact that, when $Q$ is a probability measure, in the limit when $\lambda \to +\infty$, both probability measures $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ are identical. This is consistent with the fact that when $\lambda$ tends to infinity, the optimization problem in (19) boils down to exclusively minimizing the relative entropy. Such minimum is zero and is observed when both probability measures $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ are identical (Theorem 2.1). Such intuition breaks when the reference measure is a $\sigma$-finite measure, but not a probability measure. In such a case, the relative entropy term in (19) might be negative and a minimum might not exist. See for instance, the case of the relative entropy between a Gaussian measure and the Lebesgue measure in (14), which satisfies (16).

The limit of the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25), when $\lambda$ tends to zero from the right, can be studied using the following set

$$ \mathcal{L}_z(\delta) \triangleq \{\theta \in \mathcal{M} : L_z(\theta) \le \delta\}, \qquad (36) $$

where the function $L_z$ is defined in (3) and $\delta \in [0, +\infty)$. In particular consider the nonnegative real

$$ \delta_{Q,z}^{*} \triangleq \inf \{\delta \in [0, +\infty) : Q(\mathcal{L}_z(\delta)) > 0\}. \qquad (37) $$
function in (28) or the probability density function in (30), Corollary 3.1 shows that the elements of the set $\mathcal{T}(z) \cap \text{supp} Q$ are the modes of the corresponding probability density function or probability mass function.

## 3.3 Asymptotes of the Radon-Nikodym Derivative

The following lemma describes the asymptotic behavior of the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25) when the regularization factor increases, i.e., $\lambda \to +\infty$ and the reference measure $Q$ is a probability measure.

**Lemma 3.5.** Let the measure $Q$ in (19) be a probability measure. Then, for all $\theta \in \text{supp} Q$, the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25) satisfies

$$ \lim_{\lambda \to +\infty} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 1. \qquad (32) $$

*Proof:* From Theorem 3.1, it follows that for all $\theta \in \text{supp} Q$,

$$ \lim_{\lambda \to +\infty} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \lim_{\lambda \to +\infty} \frac{\exp\left(-\frac{L_z(\theta)}{\lambda}\right)}{\int \exp\left(-\frac{L_z(\nu)}{\lambda}\right) dQ(\nu)} \qquad (33) $$

$$ = \frac{1}{\int dQ(\nu)} \qquad (34) $$

$$ =1, \qquad (35) $$

where the function $L_z$ is defined in (3). This completes the proof. ■

Lemma 3.5 unveils the fact that, when $Q$ is a probability measure, in the limit when $\lambda \to +\infty$, both probability measures $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ are identical. This is consistent with the fact that when $\lambda$ tends to infinity, the optimization problem in (19) boils down to exclusively minimizing the relative entropy. Such minimum is zero and is observed when both probability measures $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ are identical (Theorem 2.1). Such intuition breaks when the reference measure is a $\sigma$-finite measure, but not a probability measure. In such a case, the relative entropy term in (19) might be negative and a minimum might not exist. See for instance, the case of the relative entropy between a Gaussian measure and the Lebesgue measure in (14), which satisfies (16).

The limit of the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25), when $\lambda$ tends to zero from the right, can be studied using the following set

$$ \mathcal{L}_z(\delta) \triangleq \{\theta \in \mathcal{M} : L_z(\theta) \le \delta\}, \qquad (36) $$

where the function $L_z$ is defined in (3) and $\delta \in [0, +\infty)$. In particular consider the nonnegative real

$$ \delta_{Q,z}^{*} \triangleq \inf \{\delta \in [0, +\infty) : Q(\mathcal{L}_z(\delta)) > 0\}. \qquad (37) $$
Let also $\mathcal{L}_{Q,z}^*$ be the following level set of the empirical risk function $L_z$ in (3):

$$ \mathcal{L}_{Q,z}^* \triangleq \{ \theta \in \text{supp } Q : L_z(\theta) = \delta_{Q,z}^* \}. \qquad (38) $$

Using this notation, the limit of the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25), when $\lambda$ tends to zero from the right, is described by the following lemma.

**Lemma 3.6.** If $Q(\mathcal{L}_{Q,z}^*) > 0$, with the set $\mathcal{L}_{Q,z}^*$ in (38) and $Q$ the $\sigma$-finite measure in (19), then for all $\theta \in \text{supp } Q$, the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25) satisfies

$$ \lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{1}{Q(\mathcal{L}_{Q,z}^*)} \mathbb{1}_{\{\theta \in \mathcal{L}_{Q,z}^*\}}. \qquad (39) $$

Alternatively, if $Q(\mathcal{L}_{Q,z}^*) = 0$. Then, for all $\theta \in \text{supp } Q$,

$$ \lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \begin{cases} +\infty & \text{if } \theta \in \mathcal{L}_{Q,z}^* \\ 0 & \text{otherwise.} \end{cases} \qquad (40) $$

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

Consider that $Q(\mathcal{L}_{Q,z}^*) > 0$, with $\mathcal{L}_{Q,z}^*$ in (38). Under this assumption, from Lemma 3.6, it holds that the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ asymptotically concentrates on the set $\mathcal{L}_{Q,z}^*$ when $\lambda$ tends to zero from the right. More specifically, note that for all measurable sets $A \subseteq \mathcal{L}_{Q,z}^* \cap \text{supp } Q$, it holds that

$$ \lim_{\lambda \to 0^+} P_{\Theta|Z=z}^{(Q,\lambda)}(A) = \lim_{\lambda \to 0^+} \int_A \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \qquad (41) $$

$$ = \int \lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \mathbb{1}_{\{\theta \in A\}} dQ(\theta) \qquad (42) $$

$$ = \int \frac{1}{Q(\mathcal{L}_{Q,z}^*)} \mathbb{1}_{\{\theta \in \mathcal{L}_{Q,z}^*\}} \mathbb{1}_{\{\theta \in A\}} dQ(\theta) \qquad (43) $$

$$ = \frac{1}{Q(\mathcal{L}_{Q,z}^*)} \int \mathbb{1}_{\{\theta \in A\}} dQ(\theta) \qquad (44) $$

$$ = \frac{Q(A)}{Q(\mathcal{L}_{Q,z}^*)}, \qquad (45) $$

where the equality in (42) follows from Lemma 3.2 and the dominated convergence theorem [58, Theorem 2.6.9]. The equality in (43) follows from Lemma 3.6.

In the particular case in which $A = \mathcal{L}_{Q,z}^*$ in (45), it holds that $\lim_{\lambda \to 0^+} P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) = 1$, which verifies the asymptotic concentration of the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ on the set $\mathcal{L}_{Q,z}^*$.
Let also $\mathcal{L}_{Q,z}^*$ be the following level set of the empirical risk function $L_z$ in (3):

$$ \mathcal{L}_{Q,z}^* \triangleq \{ \theta \in \text{supp } Q : L_z(\theta) = \delta_{Q,z}^* \}. \qquad (38) $$

Using this notation, the limit of the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25), when $\lambda$ tends to zero from the right, is described by the following lemma.

**Lemma 3.6.** If $Q(\mathcal{L}_{Q,z}^*) > 0$, with the set $\mathcal{L}_{Q,z}^*$ in (38) and $Q$ the $\sigma$-finite measure in (19), then for all $\theta \in \text{supp } Q$, the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25) satisfies

$$ \lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{1}{Q(\mathcal{L}_{Q,z}^*)} \mathbb{1}_{\{\theta \in \mathcal{L}_{Q,z}^*\}}. \qquad (39) $$

Alternatively, if $Q(\mathcal{L}_{Q,z}^*) = 0$. Then, for all $\theta \in \text{supp } Q$,

$$ \lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \begin{cases} +\infty & \text{if } \theta \in \mathcal{L}_{Q,z}^* \\ 0 & \text{otherwise.} \end{cases} \qquad (40) $$

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

Consider that $Q(\mathcal{L}_{Q,z}^*) > 0$, with $\mathcal{L}_{Q,z}^*$ in (38). Under this assumption, from Lemma 3.6, it holds that the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ asymptotically concentrates on the set $\mathcal{L}_{Q,z}^*$ when $\lambda$ tends to zero from the right. More specifically, note that for all measurable sets $A \subseteq \mathcal{L}_{Q,z}^* \cap \text{supp } Q$, it holds that

$$ \lim_{\lambda \to 0^+} P_{\Theta|Z=z}^{(Q,\lambda)}(A) = \lim_{\lambda \to 0^+} \int_A \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \qquad (41) $$

$$ = \int \lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \mathbb{1}_{\{\theta \in A\}} dQ(\theta) \qquad (42) $$

$$ = \int \frac{1}{Q(\mathcal{L}_{Q,z}^*)} \mathbb{1}_{\{\theta \in \mathcal{L}_{Q,z}^*\}} \mathbb{1}_{\{\theta \in A\}} dQ(\theta) \qquad (43) $$

$$ = \frac{1}{Q(\mathcal{L}_{Q,z}^*)} \int \mathbb{1}_{\{\theta \in A\}} dQ(\theta) \qquad (44) $$

$$ = \frac{Q(A)}{Q(\mathcal{L}_{Q,z}^*)}, \qquad (45) $$

where the equality in (42) follows from Lemma 3.2 and the dominated convergence theorem [58, Theorem 2.6.9]. The equality in (43) follows from Lemma 3.6.

In the particular case in which $A = \mathcal{L}_{Q,z}^*$ in (45), it holds that $\lim_{\lambda \to 0^+} P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) = 1$, which verifies the asymptotic concentration of the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ on the set $\mathcal{L}_{Q,z}^*$.
Another interesting observation is that the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25) is a constant among the elements of the set $\mathcal{L}_{Q,z}^*$. This can be assimilated to a uniform distribution of the probability among the elements of the set $\mathcal{L}_{Q,z}^*$ in the limit when $\lambda$ tends to zero from the right, as previously highlighted in [25-27] and [28]. This becomes more evident in the case in which the set $\mathcal{M}$ is finite and $Q$ is the counting measure. In such a case, the asymptotic probability of each of the elements in $\mathcal{L}_{Q,z}^*$ when $\lambda$ tends to zero from the right is $\frac{1}{|\mathcal{L}_{Q,z}^*|}$.

Consider now that $Q(\mathcal{L}_{Q,z}^*) = 0$, with $\mathcal{L}_{Q,z}^*$ in (38). Under this assumption, in the asymptotic regime when $\lambda \to 0$, the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is not a probability measure but either the trivial measure or the infinite measure. This is typically the case in which $\mathcal{M} = \mathbb{R}^d$, the measure $Q$ is absolutely continuous with respect to the Lebesgue measure, and the solution to the ERM problem in (4) has a unique solution on the support of $Q$, i.e., $\mathcal{L}_{Q,z}^* = \mathcal{T}(z)$ and $|\mathcal{T}(z)| = 1$, which implies $Q(\mathcal{L}_{Q,z}^*) = 0$.

An interesting question, which is left out of the scope of this paper, is the rate at which $P_{\Theta|Z=z}^{(Q,\lambda)}$ converges to such limiting measure. The interested reader is referred to [25, 28], and references therein.

The following lemma shows that independently of whether the set $\mathcal{L}_{Q,z}^*$ is negligible with respect to the measure $Q$, the limit when $\lambda$ tends to zero from the right of $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*)$ is equal to one.

**Lemma 3.7.** The measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) and the set $\mathcal{L}_{Q,z}^*$ in (38) satisfy,

$$ \lim_{\lambda \to 0^+} P_{\Theta|Z=z}^{(Q,\lambda)} (\mathcal{L}_{Q,z}^*) = 1. \qquad (46) $$

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

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

Note that if the ERM problem in (4) possesses at least one solution and such solution is within the support of the measure $Q$, i.e., $\mathcal{T}(z) \cap \text{supp} Q \neq \emptyset$, then, when $\lambda$ tends to zero from the right, the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ asymptotically concentrates on the solution (or the set of solutions within the support of $Q$) to the ERM problem in (4). Alternatively, in the case in which $\mathcal{L}_{Q,z}^* \cap \mathcal{T}(z) = \emptyset$, when $\lambda$ tends to zero from the right, the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ asymptotically concentrates on a set that does not contain the set of solutions to the ERM problem in (4). This observation leads to the introduction to two new classes of reference measures, namely, *coherent* and *consistent* measures, in the following section.

# 4 Reference Measures

This section introduces two classes of reference measures, namely *coherent* and *consistent* measures, and discusses the special case of Gibbs reference measures.
Another interesting observation is that the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (25) is a constant among the elements of the set $\mathcal{L}_{Q,z}^*$. This can be assimilated to a uniform distribution of the probability among the elements of the set $\mathcal{L}_{Q,z}^*$ in the limit when $\lambda$ tends to zero from the right, as previously highlighted in [25-27] and [28]. This becomes more evident in the case in which the set $M$ is finite and $Q$ is the counting measure. In such a case, the asymptotic probability of each of the elements in $\mathcal{L}_{Q,z}^*$ when $\lambda$ tends to zero from the right is $\frac{1}{|\mathcal{L}_{Q,z}^*|}$.

Consider now that $Q(\mathcal{L}_{Q,z}^*) = 0$, with $\mathcal{L}_{Q,z}^*$ in (38). Under this assumption, in the asymptotic regime when $\lambda \to 0$, the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is not a probability measure but either the trivial measure or the infinite measure. This is typically the case in which $M = \mathbb{R}^d$, the measure $Q$ is absolutely continuous with respect to the Lebesgue measure, and the solution to the ERM problem in (4) has a unique solution on the support of $Q$, i.e., $\mathcal{L}_{Q,z}^* = \mathcal{T}(z)$ and $|\mathcal{T}(z)| = 1$, which implies $Q(\mathcal{L}_{Q,z}^*) = 0$.

An interesting question, which is left out of the scope of this paper, is the rate at which $P_{\Theta|Z=z}^{(Q,\lambda)}$ converges to such limiting measure. The interested reader is referred to [25, 28], and references therein.

The following lemma shows that independently of whether the set $\mathcal{L}_{Q,z}^*$ is negligible with respect to the measure $Q$, the limit when $\lambda$ tends to zero from the right of $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*)$ is equal to one.

**Lemma 3.7.** The measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) and the set $\mathcal{L}_{Q,z}^*$ in (38) satisfy,

$$ \lim_{\lambda \to 0^+} P_{\Theta|Z=z}^{(Q,\lambda)} (\mathcal{L}_{Q,z}^*) = 1. \quad (46) $$

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

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

Note that if the ERM problem in (4) possesses at least one solution and such solution is within the support of the measure $Q$, i.e., $\mathcal{T}(z) \cap \text{supp} Q \neq \emptyset$, then, when $\lambda$ tends to zero from the right, the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ asymptotically concentrates on the solution (or the set of solutions within the support of $Q$) to the ERM problem in (4). Alternatively, in the case in which $\mathcal{L}_{Q,z}^* \cap \mathcal{T}(z) = \emptyset$, when $\lambda$ tends to zero from the right, the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ asymptotically concentrates on a set that does not contain the set of solutions to the ERM problem in (4). This observation leads to the introduction to two new classes of reference measures, namely, *coherent* and *consistent* measures, in the following section.

# 4 Reference Measures

This section introduces two classes of reference measures, namely *coherent* and *consistent* measures, and discusses the special case of Gibbs reference measures.
sures.

## 4.1 Coherent and Consistent Reference Measures

A class of reference measures of particular importance to establish connections between the set of solutions to the ERM problem in (4) and the solution to the ERM-RER problem in (19) is that of coherent measures. Let $\rho^* \ge 0$ be the infimum of the empirical risk $L_z$ in (3). That is,

$$ \rho^* \triangleq \inf\{L_z(\theta) : \theta \in \mathcal{M}\}. \qquad (47) $$

Using this notation, coherent measures are defined as follows.

**Definition 4.1 (Coherent Measures).** The $\sigma$-finite measure $Q$ in (19) is said to be coherent if, for all $\delta \in (\rho^*, +\infty)$, with $\rho^*$ in (47), it holds that

$$ Q(\mathcal{L}_z(\delta)) > 0, \qquad (48) $$

where the set $\mathcal{L}_z(\delta)$ is defined in (36).

When the reference measure $Q$ in the EMR-RER problem in (19) is a coherent measure, it holds that for all $\delta > \rho^*$, the set $\mathcal{L}_z(\delta)$ in (36) exhibits positive probability with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25). The following lemma highlights this observation.

**Lemma 4.1.** The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) satisfies for all $\delta \in (\rho^*, +\infty)$, with $\rho^*$ in (47), that

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_z(\delta))>0, \qquad (49) $$

with $\mathcal{L}_z(\delta)$ in (36), if and only if the $\sigma$-finite measure $Q$ in (19) is coherent.

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

Under the assumption that the ERM problem in (4) possesses a solution, it holds that

$$ \min_{\theta \in \mathcal{M}} L_z(\theta) = \inf\{L_z(\theta) : \theta \in \mathcal{M}\}. \qquad (50) $$

Hence, when the $\sigma$-finite measure $Q$ in (19) is coherent, then

$$ \delta_{Q,z}^* = \rho^*, \qquad (51) $$

with $\delta_{Q,z}^*$ in (37) and $\rho^*$ in (47), which implies that

$$ \mathcal{L}_{Q,z}^* \subseteq \mathcal{T}(z), \qquad (52) $$

with $\mathcal{T}(z)$ in (5) and $\mathcal{L}_{Q,z}^*$ in (38). This observation, together with Lemma 3.7, leads to the following result.
sures.

## 4.1 Coherent and Consistent Reference Measures

A class of reference measures of particular importance to establish connections between the set of solutions to the ERM problem in (4) and the solution to the ERM-RER problem in (19) is that of coherent measures. Let $\rho^* \ge 0$ be the infimum of the empirical risk $L_z$ in (3). That is,

$$ \rho^* \triangleq \inf\{L_z(\theta) : \theta \in \mathcal{M}\}. \quad (47) $$

Using this notation, coherent measures are defined as follows.

**Definition 4.1 (Coherent Measures).** The $\sigma$-finite measure $Q$ in (19) is said to be coherent if, for all $\delta \in (\rho^*, +\infty)$, with $\rho^*$ in (47), it holds that

$$ Q(\mathcal{L}_z(\delta)) > 0, \quad (48) $$

where the set $\mathcal{L}_z(\delta)$ is defined in (36).

When the reference measure $Q$ in the EMR-RER problem in (19) is a coherent measure, it holds that for all $\delta > \rho^*$, the set $\mathcal{L}_z(\delta)$ in (36) exhibits positive probability with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25). The following lemma highlights this observation.

**Lemma 4.1.** The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) satisfies for all $\delta \in (\rho^*, +\infty)$, with $\rho^*$ in (47), that

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_z(\delta))>0, \quad (49) $$

with $\mathcal{L}_z(\delta)$ in (36), if and only if the $\sigma$-finite measure $Q$ in (19) is coherent.

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

Under the assumption that the ERM problem in (4) possesses a solution, it holds that

$$ \min_{\theta \in \mathcal{M}} L_z(\theta) = \inf\{L_z(\theta) : \theta \in \mathcal{M}\}. \quad (50) $$

Hence, when the $\sigma$-finite measure $Q$ in (19) is coherent, then

$$ \delta_{Q,z}^* = \rho^*, \quad (51) $$

with $\delta_{Q,z}^*$ in (37) and $\rho^*$ in (47), which implies that

$$ \mathcal{L}_{Q,z}^* \subseteq \mathcal{T}(z), \quad (52) $$

with $\mathcal{T}(z)$ in (5) and $\mathcal{L}_{Q,z}^*$ in (38). This observation, together with Lemma 3.7, leads to the following result.
**Lemma 4.2.** Assume that the ERM problem in (4) possesses a solution. Then, the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) and the sets $\mathcal{T}(z)$ in (5) and $\mathcal{L}_{Q,z}^*$ in (38) satisfy

$$ \lim_{\lambda \to 0^+} P_{\Theta|Z=z}^{(Q,\lambda)} (\mathcal{L}_{Q,z}^* \cap \mathcal{T}(z)) = 1, \quad (53) $$

if and only if the $\sigma$-finite measure $Q$ in (19) is coherent.

*Proof:* The proof follows by observing that if $Q$ is a coherent measure and the ERM problem in (4) possesses a solution, the inclusion in (52) holds. Thus, from Lemma 3.7, the equality in (53) holds. Alternatively, when the measure $Q$ in (19) is noncoherent, then $\delta_{Q,z}^* > \rho^*$, which implies that $\mathcal{L}_{Q,z}^* \cap \mathcal{T}(z) = \emptyset$. Hence, from Lemma 3.7, it follows that

$$ \lim_{\lambda \to 0^+} P_{\Theta|Z=z}^{(Q,\lambda)} (\mathcal{L}_{Q,z}^* \cap \mathcal{T}(z)) = 0, \quad (54) $$

and completes the proof.

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

The relevance of coherent measures in ERM-RER problems is well highlighted by Lemma 4.2. Essentially, when the ERM problem in (4) possesses at least one solution, the concentration of the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) on the set (or a subset) of solutions to the ERM problem in (4) occurs asymptotically when $\lambda$ tends to zero from the right, if only if the reference measure $Q$ in (19) is coherent. Nonetheless, such asymptotic concentration is not a guarantee that for strictly positive values of $\lambda$ in (19), the set $\mathcal{T}(z)$ in (5) and the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) satisfy $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{T}(z)) > 0$. In order to ensure this, another class of reference measures, known as *consistent measures*, is introduced.

**Definition 4.2 (Consistent Measure).** The $\sigma$-finite measure $Q$ in (19) is said to be consistent if $Q(\mathcal{L}_{Q,z}^*) > 0$, with $\mathcal{L}_{Q,z}^*$ in (38).

Note that every consistent measure is not necessarily coherent. For instance, if $Q$ is consistent but $\delta_{Q,z}^* > \rho^*$, with $\rho^*$ in (47) and $\delta_{Q,z}^*$ in (37), then, for all $\delta \in (\rho^*, \delta_{Q,z}^*)$, it follows that $Q(\mathcal{L}_z(\delta)) = 0$, and thus, $Q$ is not coherent. Alternatively, every coherent measure is not necessarily consistent. For instance, if $|\mathcal{L}_{Q,z}^*| = 1$ and $Q$ is coherent and absolutely continuous with respect to the Lebesgue measure, it follows that $Q(\mathcal{L}_{Q,z}^*) = 0$, and thus, $Q$ is not consistent.

The relevance of consistent measures is highlighted by the following lemma.

**Lemma 4.3.** The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) and the set $\mathcal{L}_{Q,z}^*$ in (38) satisfy

$$ P_{\Theta|Z=z}^{(Q,\lambda)} (\mathcal{L}_{Q,z}^*) > 0, \quad (55) $$

if and only if the $\sigma$-finite measure $Q$ in (19) is consistent.
**Lemma 4.2.** Assume that the ERM problem in (4) possesses a solution. Then, the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) and the sets $\mathcal{T}(z)$ in (5) and $\mathcal{L}_{Q,z}^*$ in (38) satisfy

$$ \lim_{\lambda \to 0^+} P_{\Theta|Z=z}^{(Q,\lambda)} (\mathcal{L}_{Q,z}^* \cap \mathcal{T}(z)) = 1, \quad (53) $$

if and only if the $\sigma$-finite measure $Q$ in (19) is coherent.

*Proof:* The proof follows by observing that if $Q$ is a coherent measure and the ERM problem in (4) possesses a solution, the inclusion in (52) holds. Thus, from Lemma 3.7, the equality in (53) holds. Alternatively, when the measure $Q$ in (19) is noncoherent, then $\delta_{Q,z}^* > \rho^*$, which implies that $\mathcal{L}_{Q,z}^* \cap \mathcal{T}(z) = \emptyset$. Hence, from Lemma 3.7, it follows that

$$ \lim_{\lambda \to 0^+} P_{\Theta|Z=z}^{(Q,\lambda)} (\mathcal{L}_{Q,z}^* \cap \mathcal{T}(z)) = 0, \quad (54) $$

and completes the proof.

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

The relevance of coherent measures in ERM-RER problems is well highlighted by Lemma 4.2. Essentially, when the ERM problem in (4) possesses at least one solution, the concentration of the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) on the set (or a subset) of solutions to the ERM problem in (4) occurs asymptotically when $\lambda$ tends to zero from the right, if only if the reference measure $Q$ in (19) is coherent. Nonetheless, such asymptotic concentration is not a guarantee that for strictly positive values of $\lambda$ in (19), the set $\mathcal{T}(z)$ in (5) and the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) satisfy $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{T}(z)) > 0$. In order to ensure this, another class of reference measures, known as *consistent measures*, is introduced.

**Definition 4.2 (Consistent Measure).** The $\sigma$-finite measure $Q$ in (19) is said to be consistent if $Q(\mathcal{L}_{Q,z}^*) > 0$, with $\mathcal{L}_{Q,z}^*$ in (38).

Note that every consistent measure is not necessarily coherent. For instance, if $Q$ is consistent but $\delta_{Q,z}^* > \rho^*$, with $\rho^*$ in (47) and $\delta_{Q,z}^*$ in (37), then, for all $\delta \in (\rho^*, \delta_{Q,z}^*)$, it follows that $Q(\mathcal{L}_z(\delta)) = 0$, and thus, $Q$ is not coherent. Alternatively, every coherent measure is not necessarily consistent. For instance, if $|\mathcal{L}_{Q,z}^*| = 1$ and $Q$ is coherent and absolutely continuous with respect to the Lebesgue measure, it follows that $Q(\mathcal{L}_{Q,z}^*) = 0$, and thus, $Q$ is not consistent.

The relevance of consistent measures is highlighted by the following lemma.

**Lemma 4.3.** The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) and the set $\mathcal{L}_{Q,z}^*$ in (38) satisfy

$$ P_{\Theta|Z=z}^{(Q,\lambda)} (\mathcal{L}_{Q,z}^*) > 0, \quad (55) $$

if and only if the $\sigma$-finite measure $Q$ in (19) is consistent.
*Proof:* When $Q$ is nonconsistent, it holds that $Q(\mathcal{L}_{Q,z}^*) = 0$ and thus, from the fact that the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) is absolutely continuous with respect to $Q$, it holds that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) = 0$. When $Q$ is consistent, it holds that $Q(\mathcal{L}_{Q,z}^*) > 0$. Moreover, for all $\theta \in \mathcal{L}_{Q,z}^*$, it holds that $L_z(\theta) < +\infty$ and thus, from Lemma 3.2, it follows that $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) > 0$. Hence,

$$P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) = \int_{\mathcal{L}_{Q,z}^*} dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (56)$$

$$= \int_{\mathcal{L}_{Q,z}^*} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) > 0, \quad (57)$$

which completes the proof. ■

The following lemma highlights a central property of consistent measures when the ERM problem in (4) possesses a solution.

**Lemma 4.4.** Assume that the ERM problem in (4) possesses a solution in the support of $Q$. The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) and the sets $\mathcal{T}(z)$ in (5) and $\mathcal{L}_{Q,z}^*$ in (38) satisfy

$$P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^* \cap \mathcal{T}(z)) > 0, \quad (58)$$

if and only if the $\sigma$-finite measure $Q$ in (19) is consistent.

*Proof:* The proof follows from Lemma 4.3 by noticing that when the ERM problem in (4) possesses a solution in the support of $Q$, the inclusion in (52) holds. ■

The distinction between coherent and consistent measures becomes more evident under certain conditions. Consider the case in which $\mathcal{M}$ is finite. In this case, if the solution to the ERM problem in (4) is in the support of the $\sigma$-finite measure $Q$, then $Q$ is both coherent and consistent. This is essentially because all measurable singletons (models) in $\text{supp} Q$ exhibit positive measure with respect to $Q$. Alternatively, if the solution to the ERM problem in (4) is not in the support of $Q$, then $Q$ is consistent but not coherent. Consider the case in which $\mathcal{M}$ is the set $\mathbb{R}^d$; the loss function $\ell$ in (2) is continuous; and the ERM problem in (4) admits a unique solution. In this case, any probability measure $Q$ absolutely continuous with respect to the Lebesgue measure is a coherent measure, but it is not a consistent measure. Alternatively, if the set of solutions to the ERM problem in (4) exhibits positive Lebesgue measure, then, the measure $Q$ is both coherent and consistent.

## 4.2 Gibbs Reference Measures

In model selection, a natural idea is to proceed by successive approximations in the seek of lower computation complexity. From this perspective, one might
*Proof:* When $Q$ is nonconsistent, it holds that $Q(\mathcal{L}_{Q,z}^*) = 0$ and thus, from the fact that the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) is absolutely continuous with respect to $Q$, it holds that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) = 0$. When $Q$ is consistent, it holds that $Q(\mathcal{L}_{Q,z}^*) > 0$. Moreover, for all $\theta \in \mathcal{L}_{Q,z}^*$, it holds that $L_z(\theta) < +\infty$ and thus, from Lemma 3.2, it follows that $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) > 0$. Hence,

$$P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) = \int_{\mathcal{L}_{Q,z}^*} dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (56)$$

$$= \int_{\mathcal{L}_{Q,z}^*} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) > 0, \quad (57)$$

which completes the proof. ■

The following lemma highlights a central property of consistent measures when the ERM problem in (4) possesses a solution.

**Lemma 4.4.** Assume that the ERM problem in (4) possesses a solution in the support of $Q$. The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) and the sets $\mathcal{T}(z)$ in (5) and $\mathcal{L}_{Q,z}^*$ in (38) satisfy

$$P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^* \cap \mathcal{T}(z)) > 0, \quad (58)$$

if and only if the $\sigma$-finite measure $Q$ in (19) is consistent.

*Proof:* The proof follows from Lemma 4.3 by noticing that when the ERM problem in (4) possesses a solution in the support of $Q$, the inclusion in (52) holds. ■

The distinction between coherent and consistent measures becomes more evident under certain conditions. Consider the case in which $\mathcal{M}$ is finite. In this case, if the solution to the ERM problem in (4) is in the support of the $\sigma$-finite measure $Q$, then $Q$ is both coherent and consistent. This is essentially because all measurable singletons (models) in $\text{supp} Q$ exhibit positive measure with respect to $Q$. Alternatively, if the solution to the ERM problem in (4) is not in the support of $Q$, then $Q$ is consistent but not coherent. Consider the case in which $\mathcal{M}$ is the set $\mathbb{R}^d$; the loss function $\ell$ in (2) is continuous; and the ERM problem in (4) admits a unique solution. In this case, any probability measure $Q$ absolutely continuous with respect to the Lebesgue measure is a coherent measure, but it is not a consistent measure. Alternatively, if the set of solutions to the ERM problem in (4) exhibits positive Lebesgue measure, then, the measure $Q$ is both coherent and consistent.

## 4.2 Gibbs Reference Measures

In model selection, a natural idea is to proceed by successive approximations in the seek of lower computation complexity. From this perspective, one might
wonder whether the solution to a current instance of an ERM-RER problem might serve as reference measure for the next instance. In this section, it is shown that this yields no benefit. Composing two successive ERM-REM problems boils down to a unique ERM-RER problem with the initial reference measure and a particular regularization factor. Under the assumption that $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23), the problem of interest is:

$$ \min_{P \in \Delta_Q(M, \mathcal{B}(M))} \mathbf{R}_z(P) + \alpha D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}), \quad (59a) $$

$$ \text{s. t.} \quad \int dP(\theta) = 1, \quad (59b) $$

where $\alpha > 0$; the reference measure $P_{\Theta|Z=z}^{(Q,\lambda)}$, which satisfies (25), is the solution of the ERM-RER problem in (19); and the functional $\mathbf{R}_z$ is defined in (18). From Theorem 3.1, the solution to the ERM-RER problem in (59), which is denoted by $P_{\Theta|Z=z}^{(P_{\Theta|Z=z,\alpha}^{(Q,\lambda)})}$, satisfies for all $\theta \in \text{supp} Q$ that

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(P_{\Theta|Z=z,\alpha}^{(Q,\lambda)})}}{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) = \exp\left(-K_{P_{\Theta|Z=z,\alpha}^{(Q,\lambda)}}\left(-\frac{1}{\alpha}\right) - \frac{1}{\alpha}\mathbf{L}_z(\theta)\right). \quad (60) $$

The log-partition functions $K_{Q,z}$ in (22) and $K_{P_{\Theta|Z=z,\alpha}^{(Q,\lambda)}}$ in (60) are strongly related, as shown by the following lemma.

**Lemma 4.5.** The functions $K_{Q,z}$ in (22) and $K_{P_{\Theta|Z=z,\alpha}^{(Q,\lambda)}}$ in (60) satisfy for all $t \in \mathbb{R}$,

$$ K_{P_{\Theta|Z=z,\alpha}^{(Q,\lambda)}}(t) = K_{Q,z}\left(t - \frac{1}{\lambda}\right) - K_{Q,z}\left(-\frac{1}{\lambda}\right). \quad (61) $$

Moreover, for all $t \le 0$,

$$ K_{P_{\Theta|Z=z,\alpha}^{(Q,\lambda)}}(t) \le 0. \quad (62) $$

*Proof:* The proof of (61) relies on the fact that the function $K_{P_{\Theta|Z=z,\alpha}^{(Q,\lambda)}}$ in (60)
wonder whether the solution to a current instance of an ERM-RER problem might serve as reference measure for the next instance. In this section, it is shown that this yields no benefit. Composing two successive ERM-REM problems boils down to a unique ERM-RER problem with the initial reference measure and a particular regularization factor. Under the assumption that $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23), the problem of interest is:

$$ \min_{P \in \Delta_Q(M, \mathcal{B}(M))} \mathrm{R}_z(P) + \alpha D(P \| P_{\Theta|Z=z}^{(Q, \lambda)}), \quad (59a) $$

$$ \text{s. t.} \quad \int dP(\theta) = 1, \qquad (59b) $$

where $\alpha > 0$; the reference measure $P_{\Theta|Z=z}^{(Q, \lambda)}$, which satisfies (25), is the solution of the ERM-RER problem in (19); and the functional $\mathrm{R}_z$ is defined in (18). From Theorem 3.1, the solution to the ERM-RER problem in (59), which is denoted by $P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q, \lambda)}, \alpha)}$, satisfies for all $\theta \in \text{supp} Q$ that

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q, \lambda)}, \alpha)}}{\mathrm{d}P_{\Theta|Z=z}^{(Q, \lambda)}}(\theta) = \exp\left(-K_{P_{\Theta|Z=z},z}^{(Q, \lambda)}\left(-\frac{1}{\alpha}\right) - \frac{1}{\alpha}\mathrm{L}_z(\theta)\right). \quad (60) $$

The log-partition functions $K_{Q,z}$ in (22) and $K_{P_{\Theta|Z=z}^{(Q, \lambda)},z}$ in (60) are strongly related, as shown by the following lemma.

**Lemma 4.5.** The functions $K_{Q,z}$ in (22) and $K_{P_{\Theta|Z=z}^{(Q, \lambda)},z}$ in (60) satisfy for all $t \in \mathbb{R}$,

$$ K_{P_{\Theta|Z=z}^{(Q, \lambda)},z}(t) = K_{Q,z}\left(t - \frac{1}{\lambda}\right) - K_{Q,z}\left(-\frac{1}{\lambda}\right). \quad (61) $$

Moreover, for all $t \le 0$,

$$ K_{P_{\Theta|Z=z}^{(Q, \lambda)},z}(t) \le 0. \quad (62) $$

*Proof:* The proof of (61) relies on the fact that the function $K_{P_{\Theta|Z=z}^{(Q, \lambda)},z}$ in (60)
satisfies for all $t \in \{\nu \in \mathbb{R} : K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(\nu) < \infty\}$,

$$K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(t) = \log \left( \int \exp(t \mathbf{L}_z(\boldsymbol{\theta})) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) \quad (63)$$

$$= \log \left( \int \exp(t \mathbf{L}_z(\boldsymbol{\theta})) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}) \right) \quad (64)$$

$$= \log \left( \int \exp\left(\left(t - \frac{1}{\lambda}\right) \mathbf{L}_z(\boldsymbol{\theta}) - K_{Q,z}\left(-\frac{1}{\lambda}\right)\right) dQ(\boldsymbol{\theta}) \right) \quad (65)$$

$$= \log \left( \int \exp\left(\left(t - \frac{1}{\lambda}\right) \mathbf{L}_z(\boldsymbol{\theta})\right) dQ(\boldsymbol{\theta}) - K_{Q,z}\left(-\frac{1}{\lambda}\right) \right) \quad (66)$$

$$= K_{Q,z}\left(t - \frac{1}{\lambda}\right) - K_{Q,z}\left(-\frac{1}{\lambda}\right), \quad (67)$$

where the equality in (65) follows from (25). Moreover, from Lemma 5.2, it follows that the function $K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}$ is continuous and nondecreasing. Let $s^* \in \mathbb{R} \cup \{+\infty\}$ be defined by

$$s^* \triangleq \sup \left\{ \nu \in \mathbb{R} : K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(\nu) < \infty \right\}. \quad (68)$$

If $s^* = +\infty$, then for all $t \in \mathbb{R}$, $K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(t) < +\infty$, and the proof of (61) is completed.

Alternatively, if $s^* < +\infty$, it follows that for all $t > s^*$, $K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(t) = +\infty$, which implies that $K_{Q,z}(t - \frac{1}{\lambda}) = +\infty$, as the function $K_{Q,z}$ is also continuous (Lemma 5.2) and $K_{Q,z}(-\frac{1}{\lambda}) < \infty$ (due to the choice of $\lambda$). Hence, in this case, the equality in (61) is of the form $+\infty = +\infty$. This completes the proof of (61).

The proof of (62) follows by noticing that for all $t \le 0$ and for all $\theta \in \text{supp } Q$, it holds that $\exp(t \mathbf{L}_z(\boldsymbol{\theta})) \le 1$. Hence,

$$K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(t) = \log \left( \int \exp(t \mathbf{L}_z(\boldsymbol{\theta})) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) \quad (69)$$

$$\le \log \left( \int dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) \quad (70)$$

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

which completes the proof.

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

The following lemma establishes that the solution to the ERM-RER problem in (59) is identical to the solution to another ERM-RER problem of the form
satisfies for all $t \in \{\nu \in \mathbb{R} : K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(\nu) < \infty\}$,

$$K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(t) = \log \left( \int \exp(t \mathbf{L}_z(\boldsymbol{\theta})) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) \quad (63)$$

$$= \log \left( \int \exp(t \mathbf{L}_z(\boldsymbol{\theta})) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}) \right) \quad (64)$$

$$= \log \left( \int \exp\left(\left(t - \frac{1}{\lambda}\right) \mathbf{L}_z(\boldsymbol{\theta}) - K_{Q,z}\left(-\frac{1}{\lambda}\right)\right) dQ(\boldsymbol{\theta}) \right) \quad (65)$$

$$= \log \left( \int \exp\left(\left(t - \frac{1}{\lambda}\right) \mathbf{L}_z(\boldsymbol{\theta})\right) dQ(\boldsymbol{\theta}) - K_{Q,z}\left(-\frac{1}{\lambda}\right) \right) \quad (66)$$

$$= K_{Q,z}\left(t - \frac{1}{\lambda}\right) - K_{Q,z}\left(-\frac{1}{\lambda}\right), \quad (67)$$

where the equality in (65) follows from (25). Moreover, from Lemma 5.2, it follows that the function $K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}$ is continuous and nondecreasing. Let $s^* \in \mathbb{R} \cup \{+\infty\}$ be defined by

$$s^* \triangleq \sup \left\{ \nu \in \mathbb{R} : K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(\nu) < \infty \right\}. \quad (68)$$

If $s^* = +\infty$, then for all $t \in \mathbb{R}$, $K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(t) < +\infty$, and the proof of (61) is completed.

Alternatively, if $s^* < +\infty$, it follows that for all $t > s^*$, $K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(t) = +\infty$, which implies that $K_{Q,z}(t - \frac{1}{\lambda}) = +\infty$, as the function $K_{Q,z}$ is also continuous (Lemma 5.2) and $K_{Q,z}(-\frac{1}{\lambda}) < \infty$ (due to the choice of $\lambda$). Hence, in this case, the equality in (61) is of the form $+\infty = +\infty$. This completes the proof of (61).

The proof of (62) follows by noticing that for all $t \le 0$ and for all $\theta \in \text{supp } Q$, it holds that $\exp(t \mathbf{L}_z(\boldsymbol{\theta})) \le 1$. Hence,

$$K_{P_{\Theta|Z=z},z}^{(Q,\lambda)}(t) = \log \left( \int \exp(t \mathbf{L}_z(\boldsymbol{\theta})) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) \quad (69)$$

$$\le \log \left( \int dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) \quad (70)$$

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

which completes the proof.

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

The following lemma establishes that the solution to the ERM-RER problem in (59) is identical to the solution to another ERM-RER problem of the form
$$ \min_{P \in \Delta_Q(M, \mathcal{B}(M))} \mathrm{R}_z(P) + \left( \frac{1}{\frac{1}{\alpha} + \frac{1}{\lambda}} \right) D(P \| Q), \qquad (72a) $$

$$ \text{s. t.} \qquad \int dP(\theta) = 1, \qquad (72b) $$

with $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23), and whose solution, denoted by $P_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\frac{1}{\alpha}})}$, satisfies for all $\theta \in \text{supp } Q$,

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\frac{1}{\alpha}})}}{\mathrm{d}Q}(\theta) = \exp \left( -K_{Q,z} \left(-\frac{1}{\lambda} - \frac{1}{\alpha}\right) - \left(\frac{1}{\lambda} + \frac{1}{\alpha}\right) \mathrm{L}_z(\theta) \right). \quad (73) $$

The formal statement is as follows.

**Lemma 4.6.** Let $\alpha \in (0, +\infty)$ and $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23). Then, the probability measures $P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)}, \alpha)}$ in (60) and $P_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\frac{1}{\alpha}})}$ in (73) are identical.

*Proof:* For all $\theta \in \text{supp } Q$,

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)}, \alpha)}}{\mathrm{d}Q}(\theta) = \frac{\mathrm{d}P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)}, \alpha)}}{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) \quad (74) $$

$$ = \exp \left( - K_{P_{\Theta|Z=z},z}^{(Q,\lambda)} \left( -\frac{1}{\alpha} \right) - K_{Q,z} \left( -\frac{1}{\lambda} \right) - \left( \frac{1}{\alpha} + \frac{1}{\lambda} \right) \mathrm{L}_z(\theta) \right) \quad (75) $$

$$ = \exp \left( -K_{Q,z} \left( -\frac{1}{\alpha} - \frac{1}{\lambda} \right) - \left( \frac{1}{\alpha} + \frac{1}{\lambda} \right) \mathrm{L}_z(\theta) \right) \quad (76) $$

$$ = \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\frac{1}{\alpha}})}}{\mathrm{d}Q}(\theta), \qquad (77) $$

where the equality in (74) follows from the fact that the measure $P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)}, \alpha)}$ is absolutely continuous with respect to $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $P_{\Theta|Z=z}^{(Q,\lambda)}$ is absolutely continuous with respect to the measure $Q$; the equality in (75) follows from Lemma 4.5; and the equality in (77) follows from Theorem 3.1.
$$ \min_{P \in \Delta_Q(M, \mathcal{B}(M))} \mathrm{R}_z(P) + \left( \frac{1}{\frac{1}{\alpha} + \frac{1}{\lambda}} \right) D(P \| Q), \qquad (72a) $$

$$ \text{s. t.} \qquad \int dP(\theta) = 1, \qquad (72b) $$

with $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23), and whose solution, denoted by $P_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\frac{1}{\alpha}})}$, satisfies for all $\theta \in \text{supp } Q$,

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\frac{1}{\alpha}})}}{\mathrm{d}Q}(\theta) = \exp \left( -K_{Q,z} \left(-\frac{1}{\lambda} - \frac{1}{\alpha}\right) - \left(\frac{1}{\lambda} + \frac{1}{\alpha}\right) \mathrm{L}_z(\theta) \right). \quad (73) $$

The formal statement is as follows.

**Lemma 4.6.** Let $\alpha \in (0, +\infty)$ and $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23). Then, the probability measures $P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)}, \alpha)}$ in (60) and $P_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\frac{1}{\alpha}})}$ in (73) are identical.

*Proof:* For all $\theta \in \text{supp } Q$,

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)}, \alpha)}}{\mathrm{d}Q}(\theta) = \frac{\mathrm{d}P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)}, \alpha)}}{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) \quad (74) $$

$$ = \exp \left( - K_{P_{\Theta|Z=z},z}^{(Q,\lambda)} \left( -\frac{1}{\alpha} \right) - K_{Q,z} \left( -\frac{1}{\lambda} \right) - \left( \frac{1}{\alpha} + \frac{1}{\lambda} \right) \mathrm{L}_z(\theta) \right) \quad (75) $$

$$ = \exp \left( -K_{Q,z} \left( -\frac{1}{\alpha} - \frac{1}{\lambda} \right) - \left( \frac{1}{\alpha} + \frac{1}{\lambda} \right) \mathrm{L}_z(\theta) \right) \quad (76) $$

$$ = \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\frac{1}{\alpha}})}}{\mathrm{d}Q}(\theta), \qquad (77) $$

where the equality in (74) follows from the fact that the measure $P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)}, \alpha)}$ is absolutely continuous with respect to $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $P_{\Theta|Z=z}^{(Q,\lambda)}$ is absolutely continuous with respect to the measure $Q$; the equality in (75) follows from Lemma 4.5; and the equality in (77) follows from Theorem 3.1.
For all measurable subsets $\mathcal{A}$ of $\mathcal{M}$, the following holds:

$$P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)},\alpha)}(\mathcal{A}) = \int_{\mathcal{A}} \frac{dP_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)},\alpha)}}{dQ}(\boldsymbol{\theta})dQ(\boldsymbol{\theta}) \quad (78)$$

$$= \int_{\mathcal{A}} \frac{dP_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\alpha})}}{dQ} dQ(\boldsymbol{\theta}) \quad (79)$$

$$= \int_{\mathcal{A}} dP_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\alpha})}(\boldsymbol{\theta}) \quad (80)$$

$$= P_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\alpha})}(\mathcal{A}), \quad (81)$$

where the equality in (79) follows from (77). This completes the proof. ■

The following theorem establishes a relation between the solutions to the following optimization problems

$$\min_{P \in \Delta_Q(\mathcal{M}, \mathcal{B}(\mathcal{M}))} \mathbf{R}_z(P), \quad (82a)$$

$$\text{s. t.} \quad D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}) \le c, \text{ and} \quad (82b)$$

$$\int dP(\boldsymbol{\theta}) = 1, \quad (82c)$$

and

$$\min_{P \in \Delta_Q(\mathcal{M}, \mathcal{B}(\mathcal{M}))} \mathbf{R}_z(P) + \omega D(P \| Q), \quad (83a)$$

$$\text{s. t.} \quad \int dP(\boldsymbol{\theta}) = 1, \quad (83b)$$

with $c > 0$ and $\omega \in \mathcal{K}_{Q,z}$, with $\mathcal{K}_{Q,z}$ in (23), two constants; $P_{\Theta|Z=z}^{(Q,\lambda)}$ the probability measure in (25); and $\mathbf{R}_z$ the functional in (18).

From Theorem 3.1, the solution to the ERM-RER problem in (83), which is denoted by $P_{\Theta|Z=z}^{(Q,\omega)}$, satisfies for all $\theta \in \text{supp} Q$ that

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

where the function $K_{Q,z}$ is in (22).

The following theorem formalizes the relation between both optimization problems.

**Theorem 4.1.** Assume that $c$ and $\omega$ in (82) and (83) satisfy

$$D(P_{\Theta|Z=z}^{(Q,\omega)} \| P_{\Theta|Z=z}^{(Q,\lambda)}) = c, \quad (85)$$
For all measurable subsets $\mathcal{A}$ of $\mathcal{M}$, the following holds:

$$ P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)},\alpha)}(\mathcal{A}) = \int_{\mathcal{A}} \frac{dP_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)},\alpha)}}{dQ}(\boldsymbol{\theta})dQ(\boldsymbol{\theta}) \quad (78) $$

$$ = \int_{\mathcal{A}} \frac{dP_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\alpha})}}{dQ} dQ(\boldsymbol{\theta}) \quad (79) $$

$$ = \int_{\mathcal{A}} dP_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\alpha})}(\boldsymbol{\theta}) \quad (80) $$

$$ = P_{\Theta|Z=z}^{(Q, \frac{1}{\lambda+\alpha})}(\mathcal{A}), \quad (81) $$

where the equality in (79) follows from (77). This completes the proof. ■

The following theorem establishes a relation between the solutions to the following optimization problems

$$ \min_{P \in \Delta_Q(\mathcal{M}, \mathcal{B}(\mathcal{M}))} \mathbf{R}_z(P), \quad (82a) $$

$$ \text{s. t.} \quad D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}) \le c, \quad \text{and} \quad (82b) $$

$$ \int dP(\boldsymbol{\theta}) = 1, \quad (82c) $$

and

$$ \min_{P \in \Delta_Q(\mathcal{M}, \mathcal{B}(\mathcal{M}))} \mathbf{R}_z(P) + \omega D(P \| Q), \quad (83a) $$

$$ \text{s. t.} \quad \int dP(\boldsymbol{\theta}) = 1, \quad (83b) $$

with $c > 0$ and $\omega \in \mathcal{K}_{Q,z}$, with $\mathcal{K}_{Q,z}$ in (23), two constants; $P_{\Theta|Z=z}^{(Q,\lambda)}$ the probability measure in (25); and $\mathbf{R}_z$ the functional in (18).

From Theorem 3.1, the solution to the ERM-RER problem in (83), which is denoted by $P_{\Theta|Z=z}^{(Q,\omega)}$, satisfies for all $\theta \in \text{supp } Q$ that

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

where the function $K_{Q,z}$ is in (22).

The following theorem formalizes the relation between both optimization problems.

**Theorem 4.1.** Assume that $c$ and $\omega$ in (82) and (83) satisfy

$$ D(P_{\Theta|Z=z}^{(Q,\omega)} \| P_{\Theta|Z=z}^{(Q,\lambda)}) = c, \quad (85) $$
with $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $P_{\Theta|Z=z}^{(Q,\omega)}$ being the probability measures in (25) and (84), respectively. Then, the solution to the optimization problem in (82) is the probability measure $P_{\Theta|Z=z}^{(Q,\omega)}$.

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

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

# 5 The Log-Partition Function

This section introduces some properties of the log-partition function $K_{Q,z}$ in (22) using the notion of separable empirical risk functions.

## 5.1 Separable Empirical Risk Functions

Separable empirical risk functions are defined with respect to a measure $P \in \Delta(M)$.

**Definition 5.1** (Separable Empirical Risk Function). The empirical risk function $L_z$ in (3) is said to be separable with respect to a $\sigma$-finite measure $P \in \Delta(M)$, if there exist a positive real $c > 0$ and two subsets $A$ and $B$ of $M$ that are nonnegligible with respect to $P$, and for all $(\theta_1, \theta_2) \in A \times B$,

$$L_z(\theta_1) < c < L_z(\theta_2) < +\infty. \qquad (86)$$

In a nutshell, a nonseparable empirical risk function with respect to the measure $Q$ is a constant almost surely. More specifically, there exists a real $a \ge 0$, such that

$$Q(\{\theta \in \mathcal{M} : L_z(\theta) = a\}) = 1. \qquad (87)$$

From this perspective, nonseparable empirical risk functions exhibit little practical interest for model selection.

The definition of separability in Definition 5.1 and Lemma 3.3 lead to the following lemma.

**Lemma 5.1.** The empirical risk function $L_z$ in (3) is separable with respect to the $\sigma$-finite measure $Q$ in (19) if and only if it is separable with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25).

*Proof:* Consider first that the function $L_z$ is separable with respect to the $\sigma$-finite measure $Q$. Hence, there exist a positive real $c > 0$ and two subsets $A$ and $B$ of $M$ that are nonnegligible with respect to $Q$, such that for all $(\theta_1, \theta_2) \in A \times B$ the inequality in (86) holds. Hence, from (86) the following inequalities hold:

$$-\frac{1}{\lambda}L_z(\theta_1) > -\frac{c}{\lambda} > -\frac{1}{\lambda}L_z(\theta_2) > -\infty, \text{ and} \qquad (88)$$

$$\exp\left(-\frac{1}{\lambda}L_z(\theta_1)\right) > \exp\left(-\frac{c}{\lambda}\right) > \exp\left(-\frac{1}{\lambda}L_z(\theta_2)\right) > 0. \qquad (89)$$
with $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $P_{\Theta|Z=z}^{(Q,\omega)}$ being the probability measures in (25) and (84), respectively. Then, the solution to the optimization problem in (82) is the probability measure $P_{\Theta|Z=z}^{(Q,\omega)}$.

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

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

# 5 The Log-Partition Function

This section introduces some properties of the log-partition function $K_{Q,z}$ in (22) using the notion of separable empirical risk functions.

## 5.1 Separable Empirical Risk Functions

Separable empirical risk functions are defined with respect to a measure $P \in \Delta(M)$.

**Definition 5.1** (Separable Empirical Risk Function). The empirical risk function $L_z$ in (3) is said to be separable with respect to a $\sigma$-finite measure $P \in \Delta(M)$, if there exist a positive real $c > 0$ and two subsets $A$ and $B$ of $M$ that are nonnegligible with respect to $P$, and for all $(\theta_1, \theta_2) \in A \times B$,

$$L_z(\theta_1) < c < L_z(\theta_2) < +\infty. \qquad (86)$$

In a nutshell, a nonseparable empirical risk function with respect to the measure $Q$ is a constant almost surely. More specifically, there exists a real $a \ge 0$, such that

$$Q(\{\theta \in \mathcal{M} : L_z(\theta) = a\}) = 1. \qquad (87)$$

From this perspective, nonseparable empirical risk functions exhibit little practical interest for model selection.

The definition of separability in Definition 5.1 and Lemma 3.3 lead to the following lemma.

**Lemma 5.1.** The empirical risk function $L_z$ in (3) is separable with respect to the $\sigma$-finite measure $Q$ in (19) if and only if it is separable with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25).

*Proof:* Consider first that the function $L_z$ is separable with respect to the $\sigma$-finite measure $Q$. Hence, there exist a positive real $c > 0$ and two subsets $A$ and $B$ of $M$ that are nonnegligible with respect to $Q$, such that for all $(\theta_1, \theta_2) \in A \times B$ the inequality in (86) holds. Hence, from (86) the following inequalities hold:

$$-\frac{1}{\lambda}L_z(\theta_1) > -\frac{c}{\lambda} > -\frac{1}{\lambda}L_z(\theta_2) > -\infty, \text{ and} \qquad (88)$$

$$\exp\left(-\frac{1}{\lambda}L_z(\theta_1)\right) > \exp\left(-\frac{c}{\lambda}\right) > \exp\left(-\frac{1}{\lambda}L_z(\theta_2)\right) > 0. \qquad (89)$$
This implies that

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta_1) > \exp\left(-K_{Q,z}\left(-\frac{1}{\lambda}\right) - \frac{c}{\lambda}\right) \quad (90) $$

$$ > \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta_2) \quad (91) $$

$$ > 0. \quad (92) $$

Using the inequality in (90) and the facts that $Q(\mathcal{A}) > 0$ and $Q(\mathcal{B}) > 0$, the following holds

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}) = \int_{\mathcal{A}} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) \mathrm{d}Q(\theta) > 0, \quad (93) $$

and

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{B}) = \int_{\mathcal{B}} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) \mathrm{d}Q(\theta) > 0. \quad (94) $$

which implies that the function $L_z$ is separable with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$.

Consider now that the function $L_z$ is separable with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$. Hence, there exist a positive real $c > 0$ and two subsets $\mathcal{A}$ and $\mathcal{B}$ of $\mathcal{M}$ that are nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\lambda)}$, such that for all $(\theta_1, \theta_2) \in \mathcal{A} \times \mathcal{B}$ the inequality in (86) holds. More specifically, $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}) > 0$ and $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{B}) > 0$. From Lemma 3.2 and the inequality in (86), it follows that for all pairs $(\theta_1, \theta_2) \in \mathcal{A} \times \mathcal{B}$, $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta_1) > 0$ and $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta_2) > 0$. Hence, from the fact that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}) > 0$ and $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{B}) > 0$, it follows that $Q(\mathcal{A}) > 0$ and $Q(\mathcal{B}) > 0$, which implies that the function $L_z$ is separable with respect to the $\sigma$-finite measure $Q$. This completes the proof. ■

Lemma 5.1 shows that separable empirical risk functions, and only these functions, lead to ERM-RER-optimal probability measures from which models are sampled with different probabilities. For the case of nonseparable empirical risk functions, all models are sampled from the ERM-RER-optimal probability measure with the same probability.

## 5.2 Properties of the Log-Partition Function

The log-partition function $K_{Q,z}$ in (22) is a nondecreasing continuous convex function as shown by the following lemmas.

**Lemma 5.2.** The function $K_{Q,z}$ in (22) is nondecreasing and differentiable infinitely many times in the interior of $\{t \in \mathbb{R} : K_{Q,z}(t) < +\infty\}$.
This implies that

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta_1) > \exp\left(-K_{Q,z}\left(-\frac{1}{\lambda}\right) - \frac{c}{\lambda}\right) \quad (90) $$

$$ > \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta_2) \quad (91) $$

$$ > 0. \quad (92) $$

Using the inequality in (90) and the facts that $Q(\mathcal{A}) > 0$ and $Q(\mathcal{B}) > 0$, the following holds

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}) = \int_{\mathcal{A}} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) \mathrm{d}Q(\theta) > 0, \quad (93) $$

and

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{B}) = \int_{\mathcal{B}} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) \mathrm{d}Q(\theta) > 0. \quad (94) $$

which implies that the function $L_z$ is separable with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$.

Consider now that the function $L_z$ is separable with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$. Hence, there exist a positive real $c > 0$ and two subsets $\mathcal{A}$ and $\mathcal{B}$ of $\mathcal{M}$ that are nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\lambda)}$, such that for all $(\theta_1, \theta_2) \in \mathcal{A} \times \mathcal{B}$ the inequality in (86) holds. More specifically, $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}) > 0$ and $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{B}) > 0$. From Lemma 3.2 and the inequality in (86), it follows that for all pairs $(\theta_1, \theta_2) \in \mathcal{A} \times \mathcal{B}$, $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta_1) > 0$ and $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta_2) > 0$. Hence, from the fact that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}) > 0$ and $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{B}) > 0$, it follows that $Q(\mathcal{A}) > 0$ and $Q(\mathcal{B}) > 0$, which implies that the function $L_z$ is separable with respect to the $\sigma$-finite measure $Q$. This completes the proof. ■

Lemma 5.1 shows that separable empirical risk functions, and only these functions, lead to ERM-RER-optimal probability measures from which models are sampled with different probabilities. For the case of nonseparable empirical risk functions, all models are sampled from the ERM-RER-optimal probability measure with the same probability.

## 5.2 Properties of the Log-Partition Function

The log-partition function $K_{Q,z}$ in (22) is a nondecreasing continuous convex function as shown by the following lemmas.

**Lemma 5.2.** The function $K_{Q,z}$ in (22) is nondecreasing and differentiable infinitely many times in the interior of $\{t \in \mathbb{R} : K_{Q,z}(t) < +\infty\}$.
*Proof:* The proof is presented in Appendix K.

**Lemma 5.3.** The function $K_{Q,z}$ in (22) is convex in $\{t \in \mathbb{R} : K_{Q,z}(t) < +\infty\}$. Moreover, it is strictly convex if and only if the empirical risk function $\mathbb{L}_z$ in (3) is separable with respect to the $\sigma$-finite measure $Q$ in (19).

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

In Lemma 5.2, it has been established that the log-partition function $K_{Q,z}$ in (22) is differentiable infinitely many times in the interval $\{t \in \mathbb{R} : K_{Q,z}(t) < +\infty\}$. Let the $m$-th derivative of the function $K_{Q,z}$ in (22) be denoted by $K_{Q,z}^{(m)} : \mathbb{R} \to \mathbb{R}$, with $m \in \mathbb{N}$. Hence, for all $s \in K_{Q,z}$,

$$K_{Q,z}^{(m)}\left(-\frac{1}{s}\right) \triangleq \frac{d^m}{dt^m} K_{Q,z}(t)\bigg|_{t=-\frac{1}{s}}. \qquad (95)$$

The following lemma provides explicit expressions for the first, second and third derivatives of the function $K_{Q,z}$ in (22).

**Lemma 5.4.** The first, second and third derivatives of the function $K_{Q,z}$ in (22), denoted respectively by $K_{Q,z}^{(1)}$, $K_{Q,z}^{(2)}$, and $K_{Q,z}^{(3)}$, satisfy for all $\lambda \in \text{int}K_{Q,z}$, with $K_{Q,z}$ in (23),

$$K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) = \int \mathbb{L}_z(\boldsymbol{\theta}) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}), \qquad (96)$$

$$K_{Q,z}^{(2)}\left(-\frac{1}{\lambda}\right) = \int \left(\mathbb{L}_z(\boldsymbol{\theta}) - K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right)\right)^2 dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}), \qquad (97)$$

$$K_{Q,z}^{(3)}\left(-\frac{1}{\lambda}\right) = \int \left(\mathbb{L}_z(\boldsymbol{\theta}) - K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right)\right)^3 dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}), \qquad (98)$$

where the function $\mathbb{L}_z$ is defined in (3) and the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ satisfies (25).

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

From Lemma 5.4, it follows that if $\Theta \sim P_{\Theta|Z=z}^{(Q,\lambda)}$, with $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25), the random variable

$$W \triangleq \mathbb{L}_z(\Theta), \qquad (99)$$

with the function $\mathbb{L}_z$ in (3), possesses a mean, variance, and third cumulant that are equivalent to $K_{Q,z}^{(1)}(-\frac{1}{\lambda})$ in (96), $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$ in (97), and $K_{Q,z}^{(3)}(-\frac{1}{\lambda})$ in (98), respectively.

Note that if there exists a $\delta > 0$ such that the log-partition function $K_{Q,z}$ is differentiable within the open interval $(-\delta, \delta)$ and $Q$ in (19) is a probability measure, the function $K_{Q,z}$ is the cumulant generating function of the random variable

$$V \triangleq \mathbb{L}_z(\Theta), \text{ with } \Theta \sim Q. \qquad (100)$$

The following lemma leverages this observation.
*Proof:* The proof is presented in Appendix K.

**Lemma 5.3.** The function $K_{Q,z}$ in (22) is convex in $\{t \in \mathbb{R} : K_{Q,z}(t) < +\infty\}$. Moreover, it is strictly convex if and only if the empirical risk function $L_z$ in (3) is separable with respect to the $\sigma$-finite measure $Q$ in (19).

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

In Lemma 5.2, it has been established that the log-partition function $K_{Q,z}$ in (22) is differentiable infinitely many times in the interval $\{t \in \mathbb{R} : K_{Q,z}(t) < +\infty\}$. Let the $m$-th derivative of the function $K_{Q,z}$ in (22) be denoted by $K_{Q,z}^{(m)} : \mathbb{R} \to \mathbb{R}$, with $m \in \mathbb{N}$. Hence, for all $s \in K_{Q,z}$,

$$K_{Q,z}^{(m)}\left(-\frac{1}{s}\right) \triangleq \frac{d^m}{dt^m} K_{Q,z}(t) \Big|_{t=-\frac{1}{s}}. \qquad (95)$$

The following lemma provides explicit expressions for the first, second and third derivatives of the function $K_{Q,z}$ in (22).

**Lemma 5.4.** The first, second and third derivatives of the function $K_{Q,z}$ in (22), denoted respectively by $K_{Q,z}^{(1)}$, $K_{Q,z}^{(2)}$, and $K_{Q,z}^{(3)}$, satisfy for all $\lambda \in \text{int} K_{Q,z}$, with $K_{Q,z}$ in (23),

$$K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) = \int L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta), \qquad (96)$$

$$K_{Q,z}^{(2)}\left(-\frac{1}{\lambda}\right) = \int \left(L_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right)\right)^2 dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta), \qquad (97)$$

$$K_{Q,z}^{(3)}\left(-\frac{1}{\lambda}\right) = \int \left(L_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right)\right)^3 dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta), \qquad (98)$$

where the function $L_z$ is defined in (3) and the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ satisfies (25).

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

From Lemma 5.4, it follows that if $\Theta \sim P_{\Theta|Z=z}^{(Q,\lambda)}$, with $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25), the random variable

$$W \triangleq L_z(\Theta), \qquad (99)$$

with the function $L_z$ in (3), possesses a mean, variance, and third cumulant that are equivalent to $K_{Q,z}^{(1)}(-\frac{1}{\lambda})$ in (96), $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$ in (97), and $K_{Q,z}^{(3)}(-\frac{1}{\lambda})$ in (98), respectively.

Note that if there exists a $\delta > 0$ such that the log-partition function $K_{Q,z}$ is differentiable within the open interval $(-\delta, \delta)$ and $Q$ in (19) is a probability measure, the function $K_{Q,z}$ is the cumulant generating function of the random variable

$$V \triangleq L_z(\Theta), \text{ with } \Theta \sim Q. \qquad (100)$$

The following lemma leverages this observation.
**Lemma 5.5.** Assume that $Q$ in (19) is a probability measure and that there exists real $\delta > 0$ such that the log-partition function $K_{Q,z}$ in (22) is differentiable within $(-\delta, \delta)$. Then, the first, second and third derivatives of $K_{Q,z}$, denoted respectively by $K_{Q,z}^{(1)}$, $K_{Q,z}^{(2)}$, and $K_{Q,z}^{(3)}$, satisfy

$$K_{Q,z}^{(1)}(0) = \int \mathbf{L}_z(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}), \qquad (101)$$

$$K_{Q,z}^{(2)}(0) = \int (\mathbf{L}_z(\boldsymbol{\theta}) - K_{Q,z}^{(1)}(0))^2 dQ(\boldsymbol{\theta}), \qquad (102)$$

$$K_{Q,z}^{(3)}(0) = \int (\mathbf{L}_z(\boldsymbol{\theta}) - K_{Q,z}^{(1)}(0))^3 dQ(\boldsymbol{\theta}), \qquad (103)$$

where the function $\mathbf{L}_z$ is defined in (3).

*Proof:* The proof follows along the same arguments of the proof of Lemma 5.4.

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

The mean, variance, and third cumulant of the random variable $V$ in (100) are $K_{Q,z}^{(1)}(0)$ in (101), $K_{Q,z}^{(2)}(0)$ in (102), and $K_{Q,z}^{(3)}(0)$ in (103), respectively.

# 6 Expectation of the Empirical Risk

The mean of the random variable $W$ in (99) is equivalent to the expectation of the empirical risk function $\mathbf{L}_z$ with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25), which is equal to $\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)})$, with the functional $\mathbf{R}_z$ in (18). Often, $\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ is referred to as the ERM-RER-optimal expected empirical risk to emphasize that this is the expected value of the empirical risk when models are sampled from the solution of the ERM-RER problem in (19). The following corollary of Lemma 5.4 formalizes this observation.

**Corollary 6.1.** The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) verifies that

$$\mathbf{R}_z (P_{\Theta|Z=z}^{(Q,\lambda)}) = K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right), \qquad (104)$$

where the functional $\mathbf{R}_z$ and the function $K_{Q,z}^{(1)}$ are defined in (18) and (96), respectively.

The expected empirical risk $\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) exhibits the following property.

**Theorem 6.1.** The expected empirical risk $\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) is nondecreasing with $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23). Moreover, $\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ is strictly increasing with $\lambda \in K_{Q,z}$ if and only if the function $\mathbf{L}_z$ in (3) is separable with respect to the measure $Q$.
**Lemma 5.5.** Assume that $Q$ in (19) is a probability measure and that there exists real $\delta > 0$ such that the log-partition function $K_{Q,z}$ in (22) is differentiable within $(-\delta, \delta)$. Then, the first, second and third derivatives of $K_{Q,z}$, denoted respectively by $K_{Q,z}^{(1)}$, $K_{Q,z}^{(2)}$, and $K_{Q,z}^{(3)}$, satisfy

$$ K_{Q,z}^{(1)}(0) = \int \mathbf{L}_z(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}), \qquad (101) $$

$$ K_{Q,z}^{(2)}(0) = \int (\mathbf{L}_z(\boldsymbol{\theta}) - K_{Q,z}^{(1)}(0))^2 dQ(\boldsymbol{\theta}), \qquad (102) $$

$$ K_{Q,z}^{(3)}(0) = \int (\mathbf{L}_z(\boldsymbol{\theta}) - K_{Q,z}^{(1)}(0))^3 dQ(\boldsymbol{\theta}), \qquad (103) $$

where the function $\mathbf{L}_z$ is defined in (3).

*Proof:* The proof follows along the same arguments of the proof of Lemma 5.4.

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

The mean, variance, and third cumulant of the random variable $V$ in (100) are $K_{Q,z}^{(1)}(0)$ in (101), $K_{Q,z}^{(2)}(0)$ in (102), and $K_{Q,z}^{(3)}(0)$ in (103), respectively.

# 6 Expectation of the Empirical Risk

The mean of the random variable $W$ in (99) is equivalent to the expectation of the empirical risk function $\mathbf{L}_z$ with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25), which is equal to $\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)})$, with the functional $\mathbf{R}_z$ in (18). Often, $\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ is referred to as the ERM-RER-optimal expected empirical risk to emphasize that this is the expected value of the empirical risk when models are sampled from the solution of the ERM-RER problem in (19). The following corollary of Lemma 5.4 formalizes this observation.

**Corollary 6.1.** The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) verifies that

$$ \mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)}) = K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right), \qquad (104) $$

where the functional $\mathbf{R}_z$ and the function $K_{Q,z}^{(1)}$ are defined in (18) and (96), respectively.

The expected empirical risk $\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) exhibits the following property.

**Theorem 6.1.** The expected empirical risk $\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) is nondecreasing with $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23). Moreover, $\mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ is strictly increasing with $\lambda \in K_{Q,z}$ if and only if the function $\mathbf{L}_z$ in (3) is separable with respect to the measure $Q$.
*Proof:* The proof is presented in Appendix N.

The expected empirical risk $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) has been shown to be non-decreasing with $\lambda$ in [8, Appendix E.4] for the special case in which $Q$ is a probability measure.

A question that arises from Theorem 6.1 is whether the value $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) can be made arbitrarily close to $\delta_{Q,z}^*$, with $\delta_{Q,z}^*$ in (37), by making $\lambda$ arbitrarily small. The following lemma shows that the value $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ is often bounded away from $\delta_{Q,z}^*$, even for arbitrarily small values of $\lambda$.

**Lemma 6.1.** The expected empirical risk $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) satisfies,

$$R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) \geq \delta_{Q,z}^*, \qquad (105)$$

where $\delta_{Q,z}^*$ is defined in (37). Moreover, the inequality in (105) is strict if and only if the function $L_z$ in (3) is separable with respect to the measure $Q$ in (19).

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

In the asymptotic regime when $\lambda$ tends to zero, the expected empirical risk $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) is equal to $\delta_{Q,z}^*$, as shown by the following lemma.

**Theorem 6.2.** The expected empirical risk $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) satisfies,

$$\lim_{\lambda \to 0^+} R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) = \delta_{Q,z}^*, \qquad (106)$$

where $\delta_{Q,z}^*$ is defined in (37).

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

The following lemma determines the value of the objective function of the ERM-RER problem in (19) when it is evaluated at its solution. This result appeared first in [10, Lemma 3].

**Lemma 6.2 (Lemma 3 in [10]).** The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) and the $\sigma$-finite measure $Q$ in (19) satisfy

$$-\lambda K_{Q,z} \left(-\frac{1}{\lambda}\right) = R_z \left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) + \lambda D \left(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q \right) \qquad (107)$$

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

where the functional $R_z$ is defined in (18); and the function $K_{Q,z}$ is defined in (22).

*Proof:* From Theorem 3.1, it follows that for all $\theta \in \text{supp } Q$,

$$\log \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) = -K_{Q,z} \left(-\frac{1}{\lambda}\right) - \frac{1}{\lambda} L_z(\theta), \qquad (109)$$
*Proof:* The proof is presented in Appendix N.

The expected empirical risk $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) has been shown to be non-decreasing with $\lambda$ in [8, Appendix E.4] for the special case in which $Q$ is a probability measure.

A question that arises from Theorem 6.1 is whether the value $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) can be made arbitrarily close to $\delta_{Q,z}^*$, with $\delta_{Q,z}^*$ in (37), by making $\lambda$ arbitrarily small. The following lemma shows that the value $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ is often bounded away from $\delta_{Q,z}^*$, even for arbitrarily small values of $\lambda$.

**Lemma 6.1.** The expected empirical risk $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) satisfies,

$$R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) \geq \delta_{Q,z}^*, \qquad (105)$$

where $\delta_{Q,z}^*$ is defined in (37). Moreover, the inequality in (105) is strict if and only if the function $L_z$ in (3) is separable with respect to the measure $Q$ in (19).

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

In the asymptotic regime when $\lambda$ tends to zero, the expected empirical risk $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) is equal to $\delta_{Q,z}^*$, as shown by the following lemma.

**Theorem 6.2.** The expected empirical risk $R_z(P_{\Theta|Z=z}^{(Q,\lambda)})$ in (104) satisfies,

$$\lim_{\lambda \to 0^+} R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) = \delta_{Q,z}^*, \qquad (106)$$

where $\delta_{Q,z}^*$ is defined in (37).

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

The following lemma determines the value of the objective function of the ERM-RER problem in (19) when it is evaluated at its solution. This result appeared first in [10, Lemma 3].

**Lemma 6.2 (Lemma 3 in [10]).** The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) and the $\sigma$-finite measure $Q$ in (19) satisfy

$$-\lambda K_{Q,z} \left(-\frac{1}{\lambda}\right) = R_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) + \lambda D\left(P_{\Theta|Z=z}^{(Q,\lambda)}\|Q\right) \qquad (107)$$

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

where the functional $R_z$ is defined in (18); and the function $K_{Q,z}$ is defined in (22).

*Proof:* From Theorem 3.1, it follows that for all $\theta \in \text{supp } Q$,

$$\log \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) = -K_{Q,z} \left(-\frac{1}{\lambda}\right) - \frac{1}{\lambda} L_z(\theta), \qquad (109)$$
where the function $L_z$ is defined in (3). Thus,

$$D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) = \int \log \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} (\theta) \right) dP_{\Theta|Z=z}^{(Q,\lambda)} (\theta) \quad (110)$$

$$=-K_{Q,z} \left(-\frac{1}{\lambda}\right) - \frac{1}{\lambda} \int L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (111)$$

$$=-K_{Q,z} \left(-\frac{1}{\lambda}\right) - \frac{1}{\lambda} R_z \left(P_{\Theta|Z=z}^{(Q,\lambda)}\right), \quad (112)$$

where the functional $R_z$ is defined in (18). This completes the proof of (107).

From Lemma 3.3 and (109), it follows that

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

$$=K_{Q,z} \left(-\frac{1}{\lambda}\right) + \frac{1}{\lambda} \int L_z(\theta) dQ(\theta) \quad (114)$$

$$=K_{Q,z} \left(-\frac{1}{\lambda}\right) + \frac{1}{\lambda} R_z(Q), \quad (115)$$

which completes the proof of (108).

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

The following corollary of Lemma 6.2 characterizes the difference between the expected values of the random variables $W$ and $V$ in (99) and (100), respectively.

**Corollary 6.2.** If measures $Q$ and $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) are both probability measures, then,

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

The right-hand side of (116) is a symmetrized Kullback-Liebler divergence, also known as Jeffrey's divergence [68], between the measures $Q$ and $P_{\Theta|Z=z}^{(Q,\lambda)}$. More importantly, when $Q$ is a probability measure, it follows that $D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \ge 0$ and $D(Q \| P_{\Theta|Z=z}^{(Q,\lambda)}) \ge 0$, which leads to the following corollary from Lemma 6.2.

**Corollary 6.3.** If the $\sigma$-finite measure $Q$ in (19) is a probability measure, then, the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) satisfies

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

where, the functional $R_z$ is defined in (18).
where the function $L_z$ is defined in (3). Thus,

$$D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) = \int \log \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} (\theta) \right) dP_{\Theta|Z=z}^{(Q,\lambda)} (\theta) \quad (110)$$

$$=-K_{Q,z} \left(-\frac{1}{\lambda}\right) - \frac{1}{\lambda} \int L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (111)$$

$$=-K_{Q,z} \left(-\frac{1}{\lambda}\right) - \frac{1}{\lambda} R_z \left(P_{\Theta|Z=z}^{(Q,\lambda)}\right), \quad (112)$$

where the functional $R_z$ is defined in (18). This completes the proof of (107).

From Lemma 3.3 and (109), it follows that

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

$$=K_{Q,z} \left(-\frac{1}{\lambda}\right) + \frac{1}{\lambda} \int L_z(\theta) dQ(\theta) \quad (114)$$

$$=K_{Q,z} \left(-\frac{1}{\lambda}\right) + \frac{1}{\lambda} R_z(Q), \quad (115)$$

which completes the proof of (108).

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

The following corollary of Lemma 6.2 characterizes the difference between the expected values of the random variables $W$ and $V$ in (99) and (100), respectively.

**Corollary 6.2.** If measures $Q$ and $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) are both probability measures, then,

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

The right-hand side of (116) is a symmetrized Kullback-Liebler divergence, also known as Jeffrey's divergence [68], between the measures $Q$ and $P_{\Theta|Z=z}^{(Q,\lambda)}$. More importantly, when $Q$ is a probability measure, it follows that $D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \ge 0$ and $D(Q \| P_{\Theta|Z=z}^{(Q,\lambda)}) \ge 0$, which leads to the following corollary from Lemma 6.2.

**Corollary 6.3.** If the $\sigma$-finite measure $Q$ in (19) is a probability measure, then, the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) satisfies

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

where, the functional $R_z$ is defined in (18).
# 7 Variance of the Empirical Risk

In Lemma 5.2, it has been established that if there exists a $\delta > 0$ such that the log-partition function $K_{Q,z}$ in (22) is finite within the open interval $(-\delta, \delta)$, the log-partition function $K_{Q,z}$ is differentiable infinitely many times within the interval $(-\infty, \delta)$. This together with the mean value theorem [69, Theorem 5.10] lead to the following characterization of the differences of the values $K_{Q,z}^{(2)}(-\frac{1}{t})$ and $K_{Q,z}^{(2)}(0)$, with $t > 0$.

**Lemma 7.1.** If the measure $Q$ in (19) is a probability measure and there exists a $\delta > 0$ such that the function $K_{Q,z}$ in (22) is differentiable within the open interval $(-\delta, \delta)$, then for all $t > 0$,

$$K_{Q,z}^{(2)}\left(-\frac{1}{t}\right) - K_{Q,z}^{(2)}(0) = -\frac{1}{t}K_{Q,z}^{(3)}\left(-\frac{1}{\beta}\right) < +\infty, \quad (118)$$

for some $\beta \in (t, +\infty)$, where the functions $K_{Q,z}^{(2)}$ and $K_{Q,z}^{(3)}$ are defined in (95).

*Proof:* The proof is an immediate consequence of Lemma 5.2 and the mean value theorem [69, Theorem 5.10]. ■

The relevance of Lemma 7.1 lies on the fact that $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$ and $K_{Q,z}^{(2)}(0)$ are the variances of the random variables $W$ in (99) and $V$ in (100). See Lemma 5.4 and Lemma 5.5. Under the assumptions of Lemma 7.1, it follows that the function $K_{Q,z}^{(3)}$ is continuous in $(-\infty, \delta)$, where $\delta > 0$. Hence, for all $t > 0$, the function $K_{Q,z}^{(3)}$ achieves a maximum and a minimum within the interval $[-\frac{1}{t}, 0]$. Such extrema allow providing lower and upper bounds on the variance $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$ of the random variable $W$ in terms of the variance $K_{Q,z}^{(2)}(0)$ of the random variable $V$, as shown hereunder.

**Corollary 7.1.** If the measure $Q$ in (19) is a probability measure and there exists a $\delta > 0$ such that the function $K_{Q,z}$ in (22) is differentiable within the open interval $(-\delta, \delta)$, then for all $t > 0$,

$$K_{Q,z}^{(2)}(0) - \frac{1}{t}c_2 \le K_{Q,z}^{(2)}\left(-\frac{1}{t}\right) \le K_{Q,z}^{(2)}(0) - \frac{1}{t}c_1, \quad (119)$$

where,

$$c_1 = \min_{s \in [-\frac{1}{t}, 0]} K_{Q,z}^{(3)}(s) \quad \text{and} \quad (120)$$

$$c_2 = \max_{s \in [-\frac{1}{t}, 0]} K_{Q,z}^{(3)}(s), \quad (121)$$

and the functions $K_{Q,z}^{(2)}$ and $K_{Q,z}^{(3)}$ are defined in (95).

The inequality in (119) reveals that under the assumptions of Corollary 7.1, in the asymptotic regime when $t \to +\infty$, the variances of the random variables $W$
# 7 Variance of the Empirical Risk

In Lemma 5.2, it has been established that if there exists a $\delta > 0$ such that the log-partition function $K_{Q,z}$ in (22) is finite within the open interval $(-\delta, \delta)$, the log-partition function $K_{Q,z}$ is differentiable infinitely many times within the interval $(-\infty, \delta)$. This together with the mean value theorem [69, Theorem 5.10] lead to the following characterization of the differences of the values $K_{Q,z}^{(2)}(-\frac{1}{t})$ and $K_{Q,z}^{(2)}(0)$, with $t > 0$.

**Lemma 7.1.** If the measure $Q$ in (19) is a probability measure and there exists a $\delta > 0$ such that the function $K_{Q,z}$ in (22) is differentiable within the open interval $(-\delta, \delta)$, then for all $t > 0$,

$$K_{Q,z}^{(2)}\left(-\frac{1}{t}\right) - K_{Q,z}^{(2)}(0) = -\frac{1}{t}K_{Q,z}^{(3)}\left(-\frac{1}{\beta}\right) < +\infty, \quad (118)$$

for some $\beta \in (t, +\infty)$, where the functions $K_{Q,z}^{(2)}$ and $K_{Q,z}^{(3)}$ are defined in (95).

*Proof:* The proof is an immediate consequence of Lemma 5.2 and the mean value theorem [69, Theorem 5.10]. ■

The relevance of Lemma 7.1 lies on the fact that $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$ and $K_{Q,z}^{(2)}(0)$ are the variances of the random variables $W$ in (99) and $V$ in (100). See Lemma 5.4 and Lemma 5.5. Under the assumptions of Lemma 7.1, it follows that the function $K_{Q,z}^{(3)}$ is continuous in $(-\infty, \delta)$, where $\delta > 0$. Hence, for all $t > 0$, the function $K_{Q,z}^{(3)}$ achieves a maximum and a minimum within the interval $[-\frac{1}{t}, 0]$. Such extrema allow providing lower and upper bounds on the variance $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$ of the random variable $W$ in terms of the variance $K_{Q,z}^{(2)}(0)$ of the random variable $V$, as shown hereunder.

**Corollary 7.1.** If the measure $Q$ in (19) is a probability measure and there exists a $\delta > 0$ such that the function $K_{Q,z}$ in (22) is differentiable within the open interval $(-\delta, \delta)$, then for all $t > 0$,

$$K_{Q,z}^{(2)}(0) - \frac{1}{t}c_2 \le K_{Q,z}^{(2)}\left(-\frac{1}{t}\right) \le K_{Q,z}^{(2)}(0) - \frac{1}{t}c_1, \quad (119)$$

where,

$$c_1 = \min_{s \in [-\frac{1}{t}, 0]} K_{Q,z}^{(3)}(s) \quad \text{and} \quad (120)$$

$$c_2 = \max_{s \in [-\frac{1}{t}, 0]} K_{Q,z}^{(3)}(s), \quad (121)$$

and the functions $K_{Q,z}^{(2)}$ and $K_{Q,z}^{(3)}$ are defined in (95).

The inequality in (119) reveals that under the assumptions of Corollary 7.1, in the asymptotic regime when $t \to +\infty$, the variances of the random variables $W$
in (99) and V in (100) are identical. Additionally, unlike the means $K_{Q,z}^{(1)}(-\frac{1}{\lambda})$ and $K_{Q,z}^{(1)}(0)$ of the random variables W and V, which satisfy $K_{Q,z}^{(1)}(-\frac{1}{\lambda}) \le K_{Q,z}^{(1)}(0)$ (Corollary 6.3), their variances $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$ and $K_{Q,z}^{(2)}(0)$ might satisfy $K_{Q,z}^{(2)}(-\frac{1}{\lambda}) < K_{Q,z}^{(2)}(0)$ or $K_{Q,z}^{(2)}(-\frac{1}{\lambda}) \ge K_{Q,z}^{(2)}(0)$ depending on whether the function $K_{Q,z}^{(3)}$ is positive or negative within the interval $[-\frac{1}{\lambda}, 0]$.

Lemma 7.1 shows that the monotonicity of the expectation of the random variable W in (99) with respect to $\lambda$, stated by Theorem 6.1, is not a property exhibited by the variance nor the third cumulant. The following example highlights this observation.

**Example 7.1.** Consider the ERM-RER problem in (19), under the assumption that $Q$ is a probability measure and the empirical risk function $L_z$ in (3) is such that for all $\theta \in \mathcal{M}$,

$$L_z(\theta) = \begin{cases} 0 & \text{if } \theta \in \mathcal{A} \\ 1 & \text{if } \theta \in \mathcal{M} \setminus \mathcal{A}, \end{cases} \qquad (122)$$

where the sets $\mathcal{A} \subset \mathcal{M}$ and $\mathcal{M} \setminus \mathcal{A}$ are nonnegligible with respect to the reference probability measure $Q$. In this case, the function $K_{Q,z}$ in (22) satisfies for all $\lambda > 0$,

$$K_{Q,z}\left(-\frac{1}{\lambda}\right) = \log\left(Q(\mathcal{A}) + \exp\left(-\frac{1}{\lambda}\right)(1-Q(\mathcal{A}))\right). \qquad (123)$$

The derivatives $K_{Q,z}^{(1)}$, $K_{Q,z}^{(2)}$, and $K_{Q,z}^{(3)}$ in (95) of the function $K_{Q,z}$ in (123) satisfy for all $\lambda > 0$,

$$K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) = \frac{\exp\left(-\frac{1}{\lambda}\right)(1-Q(\mathcal{A}))}{Q(\mathcal{A}) + \exp\left(-\frac{1}{\lambda}\right)(1-Q(\mathcal{A}))}; \qquad (124)$$

$$K_{Q,z}^{(2)}\left(-\frac{1}{\lambda}\right) = \frac{Q(\mathcal{A})(1-Q(\mathcal{A}))\exp\left(-\frac{1}{\lambda}\right)}{(Q(\mathcal{A}) + \exp\left(-\frac{1}{\lambda}\right)(1-Q(\mathcal{A})))^2}; \quad \text{and} \qquad (125)$$

$$K_{Q,z}^{(3)}\left(-\frac{1}{\lambda}\right) = K_{Q,z}^{(2)}\left(-\frac{1}{\lambda}\right) \left( \frac{Q(\mathcal{A}) - (1 - Q(\mathcal{A}))\exp\left(-\frac{1}{\lambda}\right)}{Q(\mathcal{A}) + \exp\left(-\frac{1}{\lambda}\right)(1 - Q(\mathcal{A}))} \right). \qquad (126)$$

Note that $K_{Q,z}^{(3)}(-\frac{1}{\lambda}) > 0$ if and only if

$$Q(\mathcal{A}) - (1 - Q(\mathcal{A})) \exp\left(-\frac{1}{\lambda}\right) > 0. \qquad (127)$$

Assume that $Q(\mathcal{A}) \ge \frac{1}{2}$. Thus, it holds that for all $\lambda > 0$, the inequality in (127) is always satisfied. This follows from observing that for all $\lambda > 0$,

$$\exp\left(-\frac{1}{\lambda}\right) < 1 \le \frac{Q(\mathcal{A})}{1 - Q(\mathcal{A})}. \qquad (128)$$
in (99) and V in (100) are identical. Additionally, unlike the means $K_{Q,z}^{(1)}(-\frac{1}{\lambda})$ and $K_{Q,z}^{(1)}(0)$ of the random variables W and V, which satisfy $K_{Q,z}^{(1)}(-\frac{1}{\lambda}) \le K_{Q,z}^{(1)}(0)$ (Corollary 6.3), their variances $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$ and $K_{Q,z}^{(2)}(0)$ might satisfy $K_{Q,z}^{(2)}(-\frac{1}{\lambda}) < K_{Q,z}^{(2)}(0)$ or $K_{Q,z}^{(2)}(-\frac{1}{\lambda}) \ge K_{Q,z}^{(2)}(0)$ depending on whether the function $K_{Q,z}^{(3)}$ is positive or negative within the interval $[-\frac{1}{\lambda}, 0]$.

Lemma 7.1 shows that the monotonicity of the expectation of the random variable W in (99) with respect to $\lambda$, stated by Theorem 6.1, is not a property exhibited by the variance nor the third cumulant. The following example highlights this observation.

**Example 7.1.** Consider the ERM-RER problem in (19), under the assumption that $Q$ is a probability measure and the empirical risk function $L_z$ in (3) is such that for all $\theta \in \mathcal{M}$,

$$L_z(\theta) = \begin{cases} 0 & \text{if } \theta \in \mathcal{A} \\ 1 & \text{if } \theta \in \mathcal{M} \setminus \mathcal{A}, \end{cases} \qquad (122)$$

where the sets $\mathcal{A} \subset \mathcal{M}$ and $\mathcal{M} \setminus \mathcal{A}$ are nonnegligible with respect to the reference probability measure $Q$. In this case, the function $K_{Q,z}$ in (22) satisfies for all $\lambda > 0$,

$$K_{Q,z}\left(-\frac{1}{\lambda}\right) = \log\left(Q(\mathcal{A}) + \exp\left(-\frac{1}{\lambda}\right)(1-Q(\mathcal{A}))\right). \qquad (123)$$

The derivatives $K_{Q,z}^{(1)}$, $K_{Q,z}^{(2)}$, and $K_{Q,z}^{(3)}$ in (95) of the function $K_{Q,z}$ in (123) satisfy for all $\lambda > 0$,

$$K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) = \frac{\exp\left(-\frac{1}{\lambda}\right)(1-Q(\mathcal{A}))}{Q(\mathcal{A}) + \exp\left(-\frac{1}{\lambda}\right)(1-Q(\mathcal{A}))}; \qquad (124)$$

$$K_{Q,z}^{(2)}\left(-\frac{1}{\lambda}\right) = \frac{Q(\mathcal{A})(1-Q(\mathcal{A}))\exp\left(-\frac{1}{\lambda}\right)}{(Q(\mathcal{A}) + \exp\left(-\frac{1}{\lambda}\right)(1-Q(\mathcal{A})))^2}; \quad \text{and} \qquad (125)$$

$$K_{Q,z}^{(3)}\left(-\frac{1}{\lambda}\right) = K_{Q,z}^{(2)}\left(-\frac{1}{\lambda}\right) \left( \frac{Q(\mathcal{A}) - (1 - Q(\mathcal{A}))\exp\left(-\frac{1}{\lambda}\right)}{Q(\mathcal{A}) + \exp\left(-\frac{1}{\lambda}\right)(1 - Q(\mathcal{A}))} \right). \qquad (126)$$

Note that $K_{Q,z}^{(3)}(-\frac{1}{\lambda}) > 0$ if and only if

$$Q(\mathcal{A}) - (1 - Q(\mathcal{A})) \exp\left(-\frac{1}{\lambda}\right) > 0. \qquad (127)$$

Assume that $Q(\mathcal{A}) \ge \frac{1}{2}$. Thus, it holds that for all $\lambda > 0$, the inequality in (127) is always satisfied. This follows from observing that for all $\lambda > 0$,

$$\exp\left(-\frac{1}{\lambda}\right) < 1 \le \frac{Q(\mathcal{A})}{1 - Q(\mathcal{A})}. \qquad (128)$$
Hence, if $Q(\mathcal{A}) \ge \frac{1}{2}$, for all decreasing sequences of positive reals $\lambda_1 > \lambda_2 > \dots > 0$, it holds that

$$ \frac{1}{4} \ge K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_1}\right) > K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_2}\right) > \dots > 0. \quad (129) $$

Alternatively, assume that $Q(\mathcal{A}) < \frac{1}{2}$. In this case, the inequality in (127) is satisfied if and only if

$$ \lambda < \left( \log \left( \frac{1 - Q(\mathcal{A})}{Q(\mathcal{A})} \right) \right)^{-1}. \quad (130) $$

Hence, if $Q(\mathcal{A}) < \frac{1}{2}$, then for all decreasing sequences of positive reals

$$ \left( \log \left( \frac{1 - Q(\mathcal{A})}{Q(\mathcal{A})} \right) \right)^{-1} > \lambda_1 > \lambda_2 > \dots > 0, $$

it holds that

$$ \frac{1}{4} > K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_1}\right) > K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_2}\right) > \dots > 0. \quad (131) $$

Moreover, for all decreasing sequences of positive reals

$$ \lambda_1 > \lambda_2 > \dots > \left( \log \left( \frac{1 - Q(\mathcal{A})}{Q(\mathcal{A})} \right) \right)^{-1}, $$

it holds that

$$ K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_1}\right) < K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_2}\right) < \dots < \frac{1}{4}. \quad (132) $$

The upperbound by $\frac{1}{4}$ in (129), (131) and (132) follows by noticing that the value $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$ is maximized when $\lambda = \left(\log\left(\frac{1-Q(\mathcal{A})}{Q(\mathcal{A})}\right)\right)^{-1}$ and $K_{Q,z}^{(2)}(-\frac{1}{\lambda}) = \frac{1}{4}$.

Example 7.1 provides important insights on the choice of the reference measure $Q$. Note for instance that when the reference measure assigns a probability to the set of models $\mathcal{T}(z)$ in (5) that is greater than or equal to the probability of suboptimal models $\mathcal{M} \setminus \mathcal{T}(z)$, i.e., $Q(\mathcal{T}(z)) \ge \frac{1}{2}$, the variance is strictly decreasing to zero when $\lambda$ decreases. See for instance, Figure 1 and Figure 2. That is, when the reference measure assigns higher probability to the set of solutions to the ERM problem in (4), the variance is monotone with respect to the parameter $\lambda$.

Alternatively, when the reference measure assigns a probability to the set $\mathcal{T}(z)$ that is smaller than the probability of the set $\mathcal{M} \setminus \mathcal{T}(z)$, i.e., $Q(\mathcal{T}(z)) < \frac{1}{2}$, there exists a critical point for $\lambda$ at $\left(\log\left(\frac{1-Q(\mathcal{A})}{Q(\mathcal{A})}\right)\right)^{-1}$. See for instance, Figure 3. More importantly, such a critical point can be arbitrarily close to zero depending on the value $Q(\mathcal{A})$. The variance strictly decreases when $\lambda$
Hence, if $Q(\mathcal{A}) \ge \frac{1}{2}$, for all decreasing sequences of positive reals $\lambda_1 > \lambda_2 > \dots > 0$, it holds that

$$ \frac{1}{4} \ge K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_1}\right) > K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_2}\right) > \dots > 0. \quad (129) $$

Alternatively, assume that $Q(\mathcal{A}) < \frac{1}{2}$. In this case, the inequality in (127) is satisfied if and only if

$$ \lambda < \left( \log \left( \frac{1 - Q(\mathcal{A})}{Q(\mathcal{A})} \right) \right)^{-1}. \quad (130) $$

Hence, if $Q(\mathcal{A}) < \frac{1}{2}$, then for all decreasing sequences of positive reals

$$ \left( \log \left( \frac{1 - Q(\mathcal{A})}{Q(\mathcal{A})} \right) \right)^{-1} > \lambda_1 > \lambda_2 > \dots > 0, $$

it holds that

$$ \frac{1}{4} > K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_1}\right) > K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_2}\right) > \dots > 0. \quad (131) $$

Moreover, for all decreasing sequences of positive reals

$$ \lambda_1 > \lambda_2 > \dots > \left( \log \left( \frac{1 - Q(\mathcal{A})}{Q(\mathcal{A})} \right) \right)^{-1}, $$

it holds that

$$ K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_1}\right) < K_{Q,z}^{(2)} \left(-\frac{1}{\lambda_2}\right) < \dots < \frac{1}{4}. \quad (132) $$

The upperbound by $\frac{1}{4}$ in (129), (131) and (132) follows by noticing that the value $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$ is maximized when $\lambda = \left(\log\left(\frac{1-Q(\mathcal{A})}{Q(\mathcal{A})}\right)\right)^{-1}$ and $K_{Q,z}^{(2)}(-\frac{1}{\lambda}) = \frac{1}{4}$.

Example 7.1 provides important insights on the choice of the reference measure $Q$. Note for instance that when the reference measure assigns a probability to the set of models $\mathcal{T}(z)$ in (5) that is greater than or equal to the probability of suboptimal models $\mathcal{M} \setminus \mathcal{T}(z)$, i.e., $Q(\mathcal{T}(z)) \ge \frac{1}{2}$, the variance is strictly decreasing to zero when $\lambda$ decreases. See for instance, Figure 1 and Figure 2. That is, when the reference measure assigns higher probability to the set of solutions to the ERM problem in (4), the variance is monotone with respect to the parameter $\lambda$.

Alternatively, when the reference measure assigns a probability to the set $\mathcal{T}(z)$ that is smaller than the probability of the set $\mathcal{M} \setminus \mathcal{T}(z)$, i.e., $Q(\mathcal{T}(z)) < \frac{1}{2}$, there exists a critical point for $\lambda$ at $\left(\log\left(\frac{1-Q(\mathcal{A})}{Q(\mathcal{A})}\right)\right)^{-1}$. See for instance, Figure 3. More importantly, such a critical point can be arbitrarily close to zero depending on the value $Q(\mathcal{A})$. The variance strictly decreases when $\lambda$
decreases beyond the value $(\log (\frac{1-Q(A)}{Q(A)}))^{-1}$. Otherwise, reducing $\lambda$ above the
value $(\log (\frac{1-Q(A)}{Q(A)}))^{-1}$ increases the variance.

In general, these observations suggest that reference measures $Q$ that allocate
small measures to the sets containing the set $\mathcal{T}(z)$ might require reducing the
value $\lambda$ beyond a small threshold in order to observe small values of $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$,
which is the variance of the random variable $W$, in (99). These observations are
central to understanding the concentration of probability that occurs when $\lambda$
decreases to zero, as discussed in Section 9.

<figure><img src="image_13.png" /><figcaption>Figure 1: Mean $K_{Q,z}^{(1)}(-\frac{1}{\lambda})$, variance $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$, and third central moment $K_{Q,z}^{(3)}(-\frac{1}{\lambda})$ of the empirical risk in Example 7.1, with $Q(A) = \frac{3}{4}$</figcaption></figure>

# 8 Cumulant Generating Function of the Empirical Risk

Consider the transport of the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) from $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ to $([0, +\infty], \mathcal{B}([0, +\infty]))$ through the function $L_z$ in (3). Denote the resulting probability measure in $([0, +\infty], \mathcal{B}([0, +\infty]))$
decreases beyond the value $(\log(\frac{1-Q(A)}{Q(A)}))^{-1}$. Otherwise, reducing $\lambda$ above the
value $(\log(\frac{1-Q(A)}{Q(A)}))^{-1}$ increases the variance.

In general, these observations suggest that reference measures $Q$ that allocate
small measures to the sets containing the set $\mathcal{T}(z)$ might require reducing the
value $\lambda$ beyond a small threshold in order to observe small values of $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$,
which is the variance of the random variable $W$, in (99). These observations are
central to understanding the concentration of probability that occurs when $\lambda$
decreases to zero, as discussed in Section 9.

<figure><img src="image_12.png" /><figcaption>Figure 1: Mean $K_{Q,z}^{(1)}(-\frac{1}{\lambda})$, variance $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$, and third central moment $K_{Q,z}^{(3)}(-\frac{1}{\lambda})$ of the empirical risk in Example 7.1, with $Q(A) = \frac{3}{4}$</figcaption></figure>

# 8 Cumulant Generating Function of the Empirical Risk

Consider the transport of the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25) from $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ to $([0, +\infty], \mathcal{B}([0, +\infty]))$ through the function $L_z$ in (3). Denote the resulting probability measure in $([0, +\infty], \mathcal{B}([0, +\infty]))$
<figure><img src="image_14.png" /><figcaption>Figure 2: Mean $K_{Q,z}^{(1)}(-\frac{1}{\lambda})$, variance $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$, and third central moment $K_{Q,z}^{(3)}(-\frac{1}{\lambda})$ of the empirical risk in Example 7.1, with $Q(\mathcal{A}) = \frac{1}{2}$</figcaption></figure>

by $P_{W|Z=z}^{(Q,\lambda)}$. That is, for all $\mathcal{A} \in \mathcal{B}([0, +\infty])$,

$$P_{W|Z=z}^{(Q,\lambda)}(\mathcal{A}) = P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_z^{-1}(\mathcal{A})), \quad (133)$$

where the term $\mathcal{L}_z^{-1}(\mathcal{A})$ represents the set

$$\mathcal{L}_z^{-1}(\mathcal{A}) \triangleq \{\nu \in \mathcal{M} : \mathcal{L}_z(\nu) \in \mathcal{A}\}. \quad (134)$$

Note that the random variable $W$ in (99) induces the probability measure $P_{W|Z=z}^{(Q,\lambda)}$ in $([0, +\infty], \mathcal{B}([0, +\infty]))$. The objective of this section is to study the properties of the cumulant generating function of the probability measure $P_{W|Z=z}^{(Q,\lambda)}$, denoted by $J_{z,Q,\lambda}: \mathbb{R} \to \mathbb{R} \cup \{+\infty\}$, which satisfies for all $t \in \mathbb{R}$,

$$J_{z,Q,\lambda}(t) = \log \left( \int \exp(tw) dP_{W|Z=z}^{(Q,\lambda)}(w) \right) \quad (135)$$

$$= \log \left( \int \exp(t \mathcal{L}_z(\theta)) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \right), \quad (136)$$
<figure><img src="image_13.png" /><figcaption>Figure 2: Mean $K_{Q,z}^{(1)}(-\frac{1}{\lambda})$, variance $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$, and third central moment $K_{Q,z}^{(3)}(-\frac{1}{\lambda})$ of the empirical risk in Example 7.1, with $Q(\mathcal{A}) = \frac{1}{2}$</figcaption></figure>

by $P_{W|Z=z}^{(Q,\lambda)}$. That is, for all $\mathcal{A} \in \mathcal{B}([0, +\infty])$,

$$P_{W|Z=z}^{(Q,\lambda)}(\mathcal{A}) = P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_z^{-1}(\mathcal{A})), \qquad (133)$$

where the term $\mathcal{L}_z^{-1}(\mathcal{A})$ represents the set

$$\mathcal{L}_z^{-1}(\mathcal{A}) \triangleq \{\nu \in \mathcal{M} : \mathcal{L}_z(\nu) \in \mathcal{A}\}. \qquad (134)$$

Note that the random variable $W$ in (99) induces the probability measure $P_{W|Z=z}^{(Q,\lambda)}$ in $([0, +\infty], \mathcal{B}([0, +\infty]))$. The objective of this section is to study the properties of the cumulant generating function of the probability measure $P_{W|Z=z}^{(Q,\lambda)}$, denoted by $J_{z,Q,\lambda}: \mathbb{R} \to \mathbb{R} \cup \{+\infty\}$, which satisfies for all $t \in \mathbb{R}$,

$$J_{z,Q,\lambda}(t) = \log \left( \int \exp(tw) dP_{W|Z=z}^{(Q,\lambda)}(w) \right) \qquad (135)$$

$$= \log \left( \int \exp(t \mathcal{L}_z(\theta)) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \right), \qquad (136)$$
<figure><img src="image_15.png" /><figcaption>Figure 3: Mean $K_{Q,z}^{(1)}(-\frac{1}{\lambda})$, variance $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$, and third central moment $K_{Q,z}^{(3)}(-\frac{1}{\lambda})$ of the empirical risk in Example 7.1, with $Q(\mathcal{A}) = \frac{1}{4}$</figcaption></figure>

where the equality in (136) follows from [58, Theorem 1.6.12].

The following lemma provides an expression for $J_{z,Q,\lambda}$ in terms of the log-partition function $K_{Q,z}$ in (22).

**Lemma 8.1.** If $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23), then, the function $J_{z,Q,\lambda}$ in (135), verifies for all $t \in \mathbb{R}$,

$$J_{z,Q,\lambda}(t) = K_{P|_{\Theta=\mathbb{Z}=\mathbb{Z}, \lambda}}^{(Q,\lambda)}(t) \quad (137)$$

$$= K_{Q,z} \left( t - \frac{1}{\lambda} \right) - K_{Q,z} \left( -\frac{1}{\lambda} \right) \quad (138)$$

$$= \sum_{m=1}^{+\infty} \frac{t^m}{m!} K_{Q,z}^{(m)} \left( -\frac{1}{\lambda} \right), \quad (139)$$

with the function $K_{Q,z}$ in (22) and the function $K_{Q,z}^{(m)}$ in (95).

*Proof:* The proof of (137) follows immediately from (22) and (136). The proof of (138) follows from Lemma 4.5. Finally, the proof of (139) follows by observing
<figure><img src="image_14.png" /><figcaption>Figure 3: Mean $K_{Q,z}^{(1)}(-\frac{1}{\lambda})$, variance $K_{Q,z}^{(2)}(-\frac{1}{\lambda})$, and third central moment $K_{Q,z}^{(3)}(-\frac{1}{\lambda})$ of the empirical risk in Example 7.1, with $Q(\mathcal{A}) = \frac{1}{4}$</figcaption></figure>

where the equality in (136) follows from [58, Theorem 1.6.12].

The following lemma provides an expression for $J_{z,Q,\lambda}$ in terms of the log-partition function $K_{Q,z}$ in (22).

**Lemma 8.1.** If $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23), then, the function $J_{z,Q,\lambda}$ in (135), verifies for all $t \in \mathbb{R}$,

$$J_{z,Q,\lambda}(t) = K_{P|_{\Theta=\mathbb{Z}=\mathbb{Z},z}}^{(Q,\lambda)}(t) \qquad (137)$$

$$= K_{Q,z} \left( t - \frac{1}{\lambda} \right) - K_{Q,z} \left( -\frac{1}{\lambda} \right) \qquad (138)$$

$$= \sum_{m=1}^{+\infty} \frac{t^m}{m!} K_{Q,z}^{(m)} \left( -\frac{1}{\lambda} \right), \qquad (139)$$

with the function $K_{Q,z}$ in (22) and the function $K_{Q,z}^{(m)}$ in (95).

*Proof:* The proof of (137) follows immediately from (22) and (136). The proof of (138) follows from Lemma 4.5. Finally, the proof of (139) follows by observing
that a Taylor expansion of the function $K_{Q,z}$ in (22) at the point $-\frac{1}{\lambda}$, yields for all $t \in \{\nu \in \mathbb{R} : K_{Q,z}(\nu) < +\infty\}$,

$$K_{Q,z}(t) = K_{Q,z}\left(-\frac{1}{\lambda}\right) + \sum_{s=1}^{+\infty} \frac{K_{Q,z}^{(s)}\left(-\frac{1}{\lambda}\right)}{s!} \left(t + \frac{1}{\lambda}\right)^s. \quad (140)$$

Choosing $\alpha \in \{\nu \in \mathbb{R} : K_{Q,z}(\nu - \frac{1}{\lambda}) < +\infty\}$ such that $t = \alpha - \frac{1}{\lambda}$ in (140) yields

$$K_{Q,z}\left(\alpha - \frac{1}{\lambda}\right) = K_{Q,z}\left(-\frac{1}{\lambda}\right) + \sum_{s=1}^{+\infty} \frac{\alpha^s}{s!} K_{Q,z}^{(s)}\left(-\frac{1}{\lambda}\right), \quad (141)$$

which implies that for all $t \in \{\nu \in \mathbb{R} : K_{Q,z}(\nu - \frac{1}{\lambda}) < +\infty\}$,

$$K_{Q,z}\left(t - \frac{1}{\lambda}\right) - K_{Q,z}\left(-\frac{1}{\lambda}\right) = \sum_{s=1}^{+\infty} \frac{t^s}{s!} K_{Q,z}^{(s)}\left(-\frac{1}{\lambda}\right). \quad (142)$$

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

$$s^* \triangleq \sup \left\{ \nu \in \mathbb{R} : K_{Q,z}\left(\nu - \frac{1}{\lambda}\right) < \infty \right\}. \quad (143)$$

If $s^* = +\infty$, then for all $t \in \mathbb{R}$, $K_{Q,z}(t - \frac{1}{\lambda}) - K_{Q,z}(-\frac{1}{\lambda}) < +\infty$, and thus,

$$+\infty > J_{z,Q,\lambda}(t) = K_{P^{(Q,\lambda)}|Z=z,z}(t) \quad (144)$$

$$= K_{Q,z}\left(t - \frac{1}{\lambda}\right) - K_{Q,z}\left(-\frac{1}{\lambda}\right) \quad (145)$$

$$= \sum_{m=1}^{+\infty} \frac{t^m}{m!} K_{Q,z}^{(m)}\left(-\frac{1}{\lambda}\right). \quad (146)$$

Alternatively, if $s^* < +\infty$, it follows that for all $t > s^*$, $K_{Q,z}(t - \frac{1}{\lambda}) = +\infty$. From the fact that the function $K_{Q,z}$ is continuous (Lemma 5.2) and $K_{Q,z}(-\frac{1}{\lambda}) < \infty$ (due to the fact that $\lambda \in K_{Q,z}$ in (23)), it follows that

$$+\infty = J_{z,Q,\lambda}(t) = K_{Q,z}\left(t - \frac{1}{\lambda}\right) - K_{Q,z}\left(-\frac{1}{\lambda}\right) \quad (147)$$

$$= \sum_{m=1}^{+\infty} \frac{t^m}{m!} K_{Q,z}^{(m)}\left(-\frac{1}{\lambda}\right), \quad (148)$$

which implies that $\sum_{m=1}^{+\infty} \frac{t^m}{m!} K_{Q,z}^{(m)}(-\frac{1}{\lambda}) = +\infty$. Hence, in this case, the equality in (139) is of the form $+\infty = +\infty$. This completes the proof. ■

Alternative expressions for $J_{z,Q,\lambda}$ in (135) are provided hereunder.
that a Taylor expansion of the function $K_{Q,z}$ in (22) at the point $-\frac{1}{\lambda}$, yields for all $t \in \{\nu \in \mathbb{R} : K_{Q,z}(\nu) < +\infty\}$,

$$K_{Q,z}(t) = K_{Q,z}\left(-\frac{1}{\lambda}\right) + \sum_{s=1}^{+\infty} \frac{K_{Q,z}^{(s)}\left(-\frac{1}{\lambda}\right)}{s!} \left(t + \frac{1}{\lambda}\right)^s. \quad (140)$$

Choosing $\alpha \in \{\nu \in \mathbb{R} : K_{Q,z}(\nu - \frac{1}{\lambda}) < +\infty\}$ such that $t = \alpha - \frac{1}{\lambda}$ in (140) yields

$$K_{Q,z}\left(\alpha - \frac{1}{\lambda}\right) = K_{Q,z}\left(-\frac{1}{\lambda}\right) + \sum_{s=1}^{+\infty} \frac{\alpha^s}{s!} K_{Q,z}^{(s)}\left(-\frac{1}{\lambda}\right), \quad (141)$$

which implies that for all $t \in \{\nu \in \mathbb{R} : K_{Q,z}(\nu - \frac{1}{\lambda}) < +\infty\}$,

$$K_{Q,z}\left(t - \frac{1}{\lambda}\right) - K_{Q,z}\left(-\frac{1}{\lambda}\right) = \sum_{s=1}^{+\infty} \frac{t^s}{s!} K_{Q,z}^{(s)}\left(-\frac{1}{\lambda}\right). \quad (142)$$

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

$$s^* \triangleq \sup \left\{ \nu \in \mathbb{R} : K_{Q,z}\left(\nu - \frac{1}{\lambda}\right) < \infty \right\}. \quad (143)$$

If $s^* = +\infty$, then for all $t \in \mathbb{R}$, $K_{Q,z}(t - \frac{1}{\lambda}) - K_{Q,z}(-\frac{1}{\lambda}) < +\infty$, and thus,

$$+\infty > J_{z,Q,\lambda}(t) = K_{P^{(Q,\lambda)}|Z=z,z}(t) \quad (144)$$

$$= K_{Q,z}\left(t - \frac{1}{\lambda}\right) - K_{Q,z}\left(-\frac{1}{\lambda}\right) \quad (145)$$

$$= \sum_{m=1}^{+\infty} \frac{t^m}{m!} K_{Q,z}^{(m)}\left(-\frac{1}{\lambda}\right). \quad (146)$$

Alternatively, if $s^* < +\infty$, it follows that for all $t > s^*$, $K_{Q,z}(t - \frac{1}{\lambda}) = +\infty$. From the fact that the function $K_{Q,z}$ is continuous (Lemma 5.2) and $K_{Q,z}(-\frac{1}{\lambda}) < \infty$ (due to the fact that $\lambda \in \mathcal{K}_{Q,z}$ in (23)), it follows that

$$+\infty = J_{z,Q,\lambda}(t) = K_{Q,z}\left(t - \frac{1}{\lambda}\right) - K_{Q,z}\left(-\frac{1}{\lambda}\right) \quad (147)$$

$$= \sum_{m=1}^{+\infty} \frac{t^m}{m!} K_{Q,z}^{(m)}\left(-\frac{1}{\lambda}\right), \quad (148)$$

which implies that $\sum_{m=1}^{+\infty} \frac{t^m}{m!} K_{Q,z}^{(m)}(-\frac{1}{\lambda}) = +\infty$. Hence, in this case, the equality in (139) is of the form $+\infty = +\infty$. This completes the proof. ■

Alternative expressions for $J_{z,Q,\lambda}$ in (135) are provided hereunder.
**Lemma 8.2.** If $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23), then, the function $J_{z,Q,\lambda}$ in (135), verifies for all $t \in (0, +\infty)$,

$$J_{z,Q,\lambda}\left(-\frac{1}{t}\right) = -\frac{1}{t}\mathrm{R}_z\left(P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)}\right) - D\left(P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)} \| P_{\Theta|Z=z}^{(Q,\lambda)}\right) \quad (149)$$

$$= -\frac{1}{t}\mathrm{R}_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) + D\left(P_{\Theta|Z=z}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)}\right) \quad (150)$$

$$\le 0, \quad (151)$$

where the functional $\mathrm{R}_z$ is in (18); the function $K_{P_{\Theta|Z=z}^{(Q,\lambda),z}}$ is in (60); and the probability measures $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)}$ are respectively in (25) and (73).

*Proof:* The proof of (149) follows from (107) in Lemma 6.2 by observing that for all $t \in (0, +\infty)$,

$$-tK_{P_{\Theta|Z=z}^{(Q,\lambda),z}}\left(-\frac{1}{t}\right) = \mathrm{R}_z\left(P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)},t)}\right) + tD\left(P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)},t)}\|P_{\Theta|Z=z}^{(Q,\lambda)}\right) \quad (152)$$

$$= \mathrm{R}_z\left(P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)}\right) + tD\left(P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)} \| P_{\Theta|Z=z}^{(Q,\lambda)}\right), \quad (153)$$

where the equality in (153) follows from Lemma 4.6. The proof of (150) follows from (108) in Lemma 6.2 by observing that for all $t \in (0, +\infty)$,

$$-tK_{P_{\Theta|Z=z}^{(Q,\lambda),z}}\left(-\frac{1}{t}\right) = \mathrm{R}_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) - tD\left(P_{\Theta|Z=z}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)},t)}\right) \quad (154)$$

$$= \mathrm{R}_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) - tD\left(P_{\Theta|Z=z}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)}\right), \quad (155)$$

where the equality in (155) follows from Lemma 4.6, which completes the proof.

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

From Lemma 5.2 and Lemma 8.1, it follows that the function $J_{z,Q,\lambda}$ in (135) is increasing and differentiable infinitely many times in the interior of the interval $\{t \in \mathbb{R} : K_{Q,z}(t - \frac{1}{\lambda}) < +\infty\}$. Moreover, note that

$$\left(-\infty, \frac{1}{\lambda}\right] \subset \left\{t \in \mathbb{R} : K_{Q,z}\left(t - \frac{1}{\lambda}\right) < +\infty\right\}.$$

Denote by $J_{z,Q,\lambda}^{(m)} : \mathbb{R} \to \mathbb{R} \cup \{+\infty\}$, with $m \in \mathbb{N}$, the m-th derivative of the function $J_{z,Q,\lambda}$ in (135). That is, for all $s \in \mathbb{R}$,

$$J_{z,Q,\lambda}^{(m)}(s) = \left. \frac{d^m}{dt^m} J_{z,Q,\lambda}(t) \right|_{t=s}. \quad (156)$$
**Lemma 8.2.** If $\lambda \in K_{Q,z}$, with $K_{Q,z}$ in (23), then, the function $J_{z,Q,\lambda}$ in (135), verifies for all $t \in (0, +\infty)$,

$$J_{z,Q,\lambda}\left(-\frac{1}{t}\right) = -\frac{1}{t}\mathrm{R}_z\left(P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)}\right) - D\left(P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)} \| P_{\Theta|Z=z}^{(Q,\lambda)}\right) \quad (149)$$

$$= -\frac{1}{t}\mathrm{R}_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) + D\left(P_{\Theta|Z=z}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)}\right) \quad (150)$$

$$\le 0, \quad (151)$$

where the functional $\mathrm{R}_z$ is in (18); the function $K_{P_{\Theta|Z=z}^{(Q,\lambda),z}}$ is in (60); and the probability measures $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)}$ are respectively in (25) and (73).

*Proof:* The proof of (149) follows from (107) in Lemma 6.2 by observing that for all $t \in (0, +\infty)$,

$$-tK_{P_{\Theta|Z=z}^{(Q,\lambda),z}}\left(-\frac{1}{t}\right) = \mathrm{R}_z\left(P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)},t)}\right) + tD\left(P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)},t)}\|P_{\Theta|Z=z}^{(Q,\lambda)}\right) \quad (152)$$

$$= \mathrm{R}_z\left(P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)}\right) + tD\left(P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)} \| P_{\Theta|Z=z}^{(Q,\lambda)}\right), \quad (153)$$

where the equality in (153) follows from Lemma 4.6. The proof of (150) follows from (108) in Lemma 6.2 by observing that for all $t \in (0, +\infty)$,

$$-tK_{P_{\Theta|Z=z}^{(Q,\lambda),z}}\left(-\frac{1}{t}\right) = \mathrm{R}_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) - tD\left(P_{\Theta|Z=z}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{(P_{\Theta|Z=z}^{(Q,\lambda)},t)}\right) \quad (154)$$

$$= \mathrm{R}_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) - tD\left(P_{\Theta|Z=z}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{\left(Q, \frac{1}{\lambda+1} \right)}\right), \quad (155)$$

where the equality in (155) follows from Lemma 4.6, which completes the proof.

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

From Lemma 5.2 and Lemma 8.1, it follows that the function $J_{z,Q,\lambda}$ in (135) is increasing and differentiable infinitely many times in the interior of the interval $\{t \in \mathbb{R} : K_{Q,z}(t - \frac{1}{\lambda}) < +\infty\}$. Moreover, note that

$$\left(-\infty, \frac{1}{\lambda}\right] \subset \left\{t \in \mathbb{R} : K_{Q,z}\left(t - \frac{1}{\lambda}\right) < +\infty\right\}.$$

Denote by $J_{z,Q,\lambda}^{(m)}: \mathbb{R} \to \mathbb{R} \cup \{+\infty\}$, with $m \in \mathbb{N}$, the m-th derivative of the function $J_{z,Q,\lambda}$ in (135). That is, for all $s \in \mathbb{R}$,

$$J_{z,Q,\lambda}^{(m)}(s) = \left. \frac{d^m}{dt^m} J_{z,Q,\lambda}(t) \right|_{t=s}. \quad (156)$$
From Lemma 8.1, it follows that for all $m \in \mathbb{N}$, and for all $\alpha \in \mathbb{R}$, the following holds,

$$J_{z,Q,\lambda}^{(m)}(\alpha) = K_{Q,z}^{(m)}\left(\alpha - \frac{1}{\lambda}\right), \qquad (157)$$

where the function $K_{Q,z}^{(m)}$ denotes the m-th derivative of the function $K_{Q,z}$ in (22). See for instance, Lemma 5.4. The equality in (157) establishes a relation between the cumulant generating function $J_{z,Q,\lambda}$ and the function $K_{Q,z}$. This observation becomes an alternative proof to Lemma 5.4.

The following theorem presents the relation between the cumulant generating function $J_{z,Q,\lambda}$ and the functions $K_{Q,z}^{(1)}$ and $K_{Q,z}^{(2)}$ in (96) and (97).

**Theorem 8.1.** For all $\alpha \in \mathbb{R}$, the function $J_{z,Q,\lambda}$ in (135) verifies the following equality

$$J_{z,Q,\lambda}(\alpha) = \alpha K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) + \frac{1}{2}\alpha^2 K_{Q,z}^{(2)}(\xi_{\alpha}) \qquad (158)$$

with

$$\xi_{\alpha} \in \left( \min \left\{ -\frac{1}{\lambda}, \alpha - \frac{1}{\lambda} \right\}, \max \left\{ -\frac{1}{\lambda}, \alpha - \frac{1}{\lambda} \right\} \right), \qquad (159)$$

where the functions $K_{Q,z}^{(1)}$ and $K_{Q,z}^{(2)}$ are defined in (96) and (97), respectively.

*Proof:* From Lemma 5.2, it follows that the function $K_{Q,z}$ is differentiable infinitely many times in the interior of $\{t \in \mathbb{R} : K_{Q,z}(t) < +\infty\}$. Then, a Taylor expansion of the function $K_{Q,z}$ in (22) at the point $-\frac{1}{\lambda}$ yields for all $t \in \{\nu \in \mathbb{R} : K_{Q,z}(\nu) < +\infty\}$,

$$K_{Q,z}(t) = K_{Q,z}\left(-\frac{1}{\lambda}\right) + \sum_{s=1}^{+\infty} \frac{1}{s!} \left(t + \frac{1}{\lambda}\right)^s K_{Q,z}^{(s)}\left(-\frac{1}{\lambda}\right). \qquad (160)$$

Choosing $t = \alpha - \frac{1}{\lambda}$, with $\alpha \in \{\nu \in \mathbb{R} : K_{Q,z}(\nu - \frac{1}{\lambda}) < +\infty\}$ in (160), it holds from the Taylor-Lagrange theorem [70, Theorem 2.5.4] that

$$K_{Q,z}\left(\alpha - \frac{1}{\lambda}\right) = K_{Q,z}\left(-\frac{1}{\lambda}\right) + \alpha K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) + \frac{1}{2}\alpha^2 K_{Q,z}^{(2)}(\xi), \qquad (161)$$

where $\xi \in (\min\{-\frac{1}{\lambda}, \alpha - \frac{1}{\lambda}\}, \max\{-\frac{1}{\lambda}, \alpha - \frac{1}{\lambda}\})$. The proof is completed by noticing that from Lemma 8.1, it holds that $J_{z,Q,\lambda}(\alpha) = K_{Q,z}(\alpha - \frac{1}{\lambda}) - K_{Q,z}(-\frac{1}{\lambda})$.

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

In (158), the term $\xi_{\alpha}$ depends on $\alpha$ via (159). The focus is now on the term $K_{Q,z}^{(2)}(\xi_{\alpha})$, when $\alpha \in \{t \in \mathbb{R} : J_{z,Q,\lambda}(t) < +\infty\}$.

**Theorem 8.2.** The function $J_{z,Q,\lambda}$ in (135) verifies the following inequality for all $\alpha \in \{t \in \mathbb{R} : J_{z,Q,\lambda}(t) < +\infty\}$,

$$J_{z,Q,\lambda}(\alpha) \le \alpha K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) + \frac{1}{2}\alpha^2 \beta_{Q,z}^2 \qquad (162)$$
From Lemma 8.1, it follows that for all $m \in \mathbb{N}$, and for all $\alpha \in \mathbb{R}$, the following holds,

$$J_{z,Q,\lambda}^{(m)}(\alpha) = K_{Q,z}^{(m)}\left(\alpha - \frac{1}{\lambda}\right), \qquad (157)$$

where the function $K_{Q,z}^{(m)}$ denotes the m-th derivative of the function $K_{Q,z}$ in (22). See for instance, Lemma 5.4. The equality in (157) establishes a relation between the cumulant generating function $J_{z,Q,\lambda}$ and the function $K_{Q,z}$. This observation becomes an alternative proof to Lemma 5.4.

The following theorem presents the relation between the cumulant generating function $J_{z,Q,\lambda}$ and the functions $K_{Q,z}^{(1)}$ and $K_{Q,z}^{(2)}$ in (96) and (97).

**Theorem 8.1.** For all $\alpha \in \mathbb{R}$, the function $J_{z,Q,\lambda}$ in (135) verifies the following equality

$$J_{z,Q,\lambda}(\alpha) = \alpha K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) + \frac{1}{2}\alpha^2 K_{Q,z}^{(2)}(\xi_{\alpha}) \qquad (158)$$

with

$$\xi_{\alpha} \in \left( \min \left\{ -\frac{1}{\lambda}, \alpha - \frac{1}{\lambda} \right\}, \max \left\{ -\frac{1}{\lambda}, \alpha - \frac{1}{\lambda} \right\} \right), \qquad (159)$$

where the functions $K_{Q,z}^{(1)}$ and $K_{Q,z}^{(2)}$ are defined in (96) and (97), respectively.

*Proof:* From Lemma 5.2, it follows that the function $K_{Q,z}$ is differentiable infinitely many times in the interior of $\{t \in \mathbb{R} : K_{Q,z}(t) < +\infty\}$. Then, a Taylor expansion of the function $K_{Q,z}$ in (22) at the point $-\frac{1}{\lambda}$ yields for all $t \in \{\nu \in \mathbb{R} : K_{Q,z}(\nu) < +\infty\}$,

$$K_{Q,z}(t) = K_{Q,z}\left(-\frac{1}{\lambda}\right) + \sum_{s=1}^{+\infty} \frac{1}{s!} \left(t + \frac{1}{\lambda}\right)^s K_{Q,z}^{(s)}\left(-\frac{1}{\lambda}\right). \qquad (160)$$

Choosing $t = \alpha - \frac{1}{\lambda}$, with $\alpha \in \{\nu \in \mathbb{R} : K_{Q,z}(\nu - \frac{1}{\lambda}) < +\infty\}$ in (160), it holds from the Taylor-Lagrange theorem [70, Theorem 2.5.4] that

$$K_{Q,z}\left(\alpha - \frac{1}{\lambda}\right) = K_{Q,z}\left(-\frac{1}{\lambda}\right) + \alpha K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) + \frac{1}{2}\alpha^2 K_{Q,z}^{(2)}(\xi), \qquad (161)$$

where $\xi \in (\min\{-\frac{1}{\lambda}, \alpha - \frac{1}{\lambda}\}, \max\{-\frac{1}{\lambda}, \alpha - \frac{1}{\lambda}\})$. The proof is completed by noticing that from Lemma 8.1, it holds that $J_{z,Q,\lambda}(\alpha) = K_{Q,z}(\alpha - \frac{1}{\lambda}) - K_{Q,z}(-\frac{1}{\lambda})$.

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

In (158), the term $\xi_{\alpha}$ depends on $\alpha$ via (159). The focus is now on the term $K_{Q,z}^{(2)}(\xi_{\alpha})$, when $\alpha \in \{t \in \mathbb{R} : J_{z,Q,\lambda}(t) < +\infty\}$.

**Theorem 8.2.** The function $J_{z,Q,\lambda}$ in (135) verifies the following inequality for all $\alpha \in \{t \in \mathbb{R} : J_{z,Q,\lambda}(t) < +\infty\}$,

$$J_{z,Q,\lambda}(\alpha) \le \alpha K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) + \frac{1}{2}\alpha^2 \beta_{Q,z}^2 \qquad (162)$$
where $\beta_{Q,z}$ satisfies

$$ \beta_{Q,z} = \sup \left\{ \sqrt{K_{Q,z}^{(2)}(\alpha)} : \alpha \in \left(-\infty, b - \frac{1}{\lambda}\right) \right\}, \quad (163) $$

with

$$ b \triangleq \sup \{t \in \mathbb{R} : J_{z,Q,\lambda}(t) < +\infty\}, \quad (164) $$

and the functions $K_{Q,z}^{(1)}$ and $K_{Q,z}^{(2)}$ are defined in (96) and (97), respectively.

*Proof:* From Lemma 8.1, it holds that

$$ \{t \in \mathbb{R} : J_{z,Q,\lambda}(t) < +\infty\} = \{t \in \mathbb{R} : K_{Q,z}\left(t - \frac{1}{\lambda}\right) < +\infty\}, $$

which implies that the set $\{t \in \mathbb{R} : J_{z,Q,\lambda}(t) < +\infty\}$ contains an interval of the form $(-\infty, b)$ and is contained within an interval of the form $(-\infty, b]$, with $b$ in (164). This follows from the fact that the function $K_{Q,z}$ is continuous and nondecreasing (Lemma 5.2). Note also that $K_{Q,z}(0) = 0$, and thus, $\frac{1}{\lambda} \in \{t \in \mathbb{R} : J_{z,Q,\lambda}(t) < +\infty\}$, which implies that $b > \frac{1}{\lambda}$.

From Theorem 8.1, it follows that for all $\alpha \in (-\infty, b)$,

$$ J_{z,Q,\lambda}(\alpha) \le \alpha K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) + \frac{1}{2} \alpha^2 \sigma_{\alpha}^2, \quad (165) $$

where $\sigma_{\alpha}$ is

$$ \sigma_{\alpha} \triangleq \sup \left\{ \sqrt{K_{Q,z}^{(2)}(\xi)} : \xi \in \left( \min \left\{ -\frac{1}{\lambda}, \alpha - \frac{1}{\lambda} \right\}, \max \left\{ -\frac{1}{\lambda}, \alpha - \frac{1}{\lambda} \right\} \right) \right\}. $$

In the asymptotic regime, when $\alpha \to -\infty$, it holds that

$$ \lim_{\alpha \to -\infty} \sigma_{\alpha} \triangleq \sup \left\{ \sqrt{K_{Q,z}^{(2)}(\xi)} : \xi \in \left(-\infty, -\frac{1}{\lambda}\right) \right\}, $$

and when $\alpha \to b$, it holds that

$$ \lim_{\alpha \to b} \sigma_{\alpha} \triangleq \sup \left\{ \sqrt{K_{Q,z}^{(2)}(\xi)} : \xi \in \left(-\frac{1}{\lambda}, b - \frac{1}{\lambda}\right) \right\}. $$

Thus, for all $\alpha \in (-\infty, b)$,

$$ \sigma_{\alpha} \le \beta_{Q,z}, $$

with $\beta_{Q,z}$ defined in (163), which completes the proof. ■

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

The main implication of Theorem 8.2 is that if $\beta_{Q,z}$ in (163) is finite, the random variable $W$ in (99) is a sub-Gaussian random variable with sub-Gaussianity parameter $\beta_{Q,z}$ [56, Section 2.3]. This follows by noticing that the function $J_{z,Q,\lambda}$ in (136) is the cumulant generating function of the random variable $W$. Hence, whenever $\beta_{Q,z}$ is finite, when the models are sampled from the ERM-RER optimal measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (25), the empirical risk with respect to the dataset $z$ is a sub-Gaussian random variable with sub-Gaussianity parameter $\beta_{Q,z}$. The following corollary of Theorem 8.2 highlights this observation.