# Empirical Risk Minimization with Relative Entropy Regularization Type-II

Francisco Daunas, Iñaki Esnaola, Samir M. Perlaza, H. Vincent Poor

► To cite this version:

Francisco Daunas, Iñaki Esnaola, Samir M. Perlaza, H. Vincent Poor. Empirical Risk Minimization with Relative Entropy Regularization Type-II. RR-9508, INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis. 2023. hal-04110899v2

HAL Id: hal-04110899

https://hal.science/hal-04110899v2

Submitted on 18 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.
informatics mathematics
Inria

# Empirical Risk Minimization with Relative Entropy Regularization Type-II

Francisco Daunas, Iñaki Esnaola, Samir M. Perlaza, and
H. Vincent Poor

RESEARCH
REPORT

Nº 9508

May 2023

Project-Team NEO
informatics mathematics
Inria

# Empirical Risk Minimization with Relative Entropy Regularization Type-II

Francisco Daunas, Iñaki Esnaola, Samir M. Perlaza, and
H. Vincent Poor

RESEARCH
REPORT

Nº 9508

May 2023

Project-Team NEO
<figure><img src="image_1.png" /></figure>
<figure><img src="image_1.png" /></figure>
# Empirical Risk Minimization with Relative Entropy Regularization Type-II

Francisco Daunas, Iñaki Esnaola, Samir M. Perlaza, and
H. Vincent Poor

Project-Team NEO

Research Report n° 9508 — version 4 — initial version May 2023 —
revised version August 2025 — 75 pages

**Abstract:** The effect of relative entropy asymmetry is analyzed in the context of empirical risk minimization (ERM) with relative entropy regularization (ERM-RER). Two regularizations are considered: (a) the relative entropy of the measure to be optimized with respect to a reference measure (Type-I ERM-RER); and (b) the relative entropy of the reference measure with respect to the measure to be optimized (Type-II ERM-RER). The main result is the characterization of the solution to the Type-II ERM-RER problem and its key properties. By comparing the well-understood Type-I ERM-RER with Type-II ERM-RER, the effects of entropy asymmetry are highlighted. The analysis shows that in both cases, regularization by relative entropy forces the support of the solution to collapse into the support of the reference measure, introducing a strong inductive bias that negates the evidence provided by the training data. Finally, it is shown that Type-II regularization is equivalent to Type-I regularization with an appropriate transformation of the empirical risk function.

**Key-words:** Supervised Learning, Empirical Risk Minimization; Relative Entropy; Regularization; Gibbs Measure; Inductive Bias; Sensitivity; and Generalization.

Francisco Daunas and Iñaki Esnaola are with the Department of Automatic Control and Systems Engineering at the University of Sheffield, Sheffield, UK. Francisco Daunas is also a member of the NEO Team at INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis. Samir M. Perlaza is with INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France and with the GAATI Laboratory of the Université de la Polynésie Française, Faaa, French Polynesia. H. Vincent Poor, Iñaki Esnaola, and Samir M. Perlaza are with the ECE Department at Princeton University, Princeton,NJ.

This work was presented in part at the IEEE International Symposium on Information Theory in 2023 [1] and appeared in the IEEE Transactions on Information Theory in 2025 [2].
# Empirical Risk Minimization with Relative Entropy Regularization Type-II

Francisco Daunas, Iñaki Esnaola, Samir M. Perlaza, and
H. Vincent Poor

Project-Team NEO

Research Report n° 9508 — version 2 — initial version May 2023 —
revised version February 2024 — 59 pages

**Abstract:** The effect of relative entropy asymmetry is analyzed in the context of empirical risk minimization with relative entropy regularization (ERM-RER). A novel regularization is introduced, termed Type-II regularization, that allows for solutions to the ERM-RER problem with a support that extends outside the support of the reference measure. The solution to the ERM-RER Type-II problem is characterized in terms of the Radon-Nikodym derivative of the reference measure with respect to the solution. Analysis of the solution unveils the following properties of relative entropy when it acts as a regularizer in the ERM-RER problem: i) relative entropy forces the support of the Type-II solution to collapse into the support of the reference measure, which introduces a strong inductive bias that dominates the evidence provided by the training data; and ii) Type-II regularization is equivalent to classical relative entropy regularization with an appropriate transformation of the empirical risk function. Closed-form expressions for the expected empirical risk as a function of the regularization parameters are provided.

**Key-words:** Supervised Learning, Empirical Risk Minimization; Relative Entropy; Regularization; Gibbs Measure; Inductive Bias; Sensitivity; and Generalization.

RESEARCH CENTRE
SOPHIA ANTIPOLIS – MÉDITERRANÉE

2004 route des Lucioles - BP 93
06902 Sophia Antipolis Cedex

<footnote>Francisco Daunas and Iñaki Esnaola are with the Department of Automatic Control and Systems Engineering at the University of Sheffield, Sheffield, UK. Francisco Daunas is also a member of the NEO Team at INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis.</footnote>

<footnote>Samir M. Perlaza is with INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France and with the GAATI Laboratory of the Université de la Polynésie Française, Faaa, French Polynesia.</footnote>

<footnote>H. Vincent Poor, Iñaki Esnaola, and Samir M. Perlaza are with the ECE Department at Princeton University, Princeton, NJ.</footnote>
# Minimisation du Risque Empirique avec Régularisation par l'Entropie Relative Type-II

**Résumé** : L'effet de l'asymétrie de l'entropie relative est analysé dans le contexte de la minimisation du risque empirique (ERM) avec régularisation par entropie relative (ERM-RER). Deux régularisations sont considérées : (a) l'entropie relative de la mesure à optimiser par rapport à une mesure de référence (Type-I ERM-RER) ; et (b) l'entropie relative de la mesure de référence par rapport à la mesure à optimiser (Type-II ERM-RER). Le résultat principal est la caractérisation de la solution du problème Type-II ERM-RER et de ses propriétés essentielles. En comparant le bien connu Type-I ERM-RER avec le Type-II ERM-RER, les effets de l'asymétrie de l'entropie sont mis en évidence. L'analyse montre que, dans les deux cas, la régularisation par entropie relative force le support de la solution à se réduire au support de la mesure de référence, introduisant ainsi un fort biais inductif qui annule les preuves fournies par les données d'apprentissage. Enfin, il est montré que la régularisation de Type-II est équivalente à la régularisation de Type-I au moyen d'une transformation appropriée de la fonction de risque empirique.

**Mots-clés** : Apprentissage Supervisé; Minimisation du Risque Empirique; Entropie Relative; Régularisation; Algorithme de Gibbs; Mesure de Gibbs; Sensitivité; et Généralisation
# Minimisation du Risque Empirique avec Régularisation par l'Entropie Relative Tapez-II

**Résumé :** L'effet de l'asymétrie de l'entropie relative est analysé dans le problème de la minimisation du risque empirique avec régularisation par entropie relative (MRE-RER). Une nouvelle régularisation est introduite, appelée régularisation de Type-II, qui permet la recherche des solutions au problème de la MRE-RER avec un support qui s'étend en dehors du support de la mesure de référence. La solution au nouveau problème de la Type-II MRE-RER est caractérisée analytiquement en termes de la dérivée de Radon-Nikodym de la mesure de référence par rapport à la solution. L'analyse de la solution dévoile certaines propriétés de l'entropie relative lorsqu'elle agit comme régularisateur du problème de la MRE-RER : (a) l'entropie relative force le support de la solution de Type-II à s'étaler sur tout le support de la mesure de référence, ce qui introduit un fort biais inductif qui domine l'évidence fournie par les données d'entraînement ; (b) La régularisation de Type-II est équivalente à la régularisation d'entropie relative classique avec une transformation appropriée de la fonction du risque empirique. Enfin, une expression sous forme explicite de la valeur espérée du risque empirique en fonction des paramètres de régularisation est présentée.

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

<table><tr><td>1</td><td>Introduction</td><td>5</td></tr><tr><td>1.1</td><td>Motivation</td><td>5</td></tr><tr><td>1.2</td><td>Contributions</td><td>6</td></tr><tr><td>2</td><td>Empirical Risk Minimization</td><td>7</td></tr><tr><td>2.1</td><td>The Type-I ERM-RER Problem</td><td>8</td></tr><tr><td>2.2</td><td>The Type-II ERM-RER Problem</td><td>9</td></tr><tr><td>3</td><td>The Solution to the Type-II ERM-RER Problem</td><td>10</td></tr><tr><td>4</td><td>The Normalization Function</td><td>12</td></tr><tr><td>5</td><td>Properties of the Solution</td><td>14</td></tr><tr><td>5.1</td><td>Bounds on the Radon-Nikodym Derivative</td><td>14</td></tr><tr><td>5.2</td><td>Asymptotes of the Radon-Nikodym Derivative</td><td>15</td></tr><tr><td>6</td><td>The Expected Empirical Risk</td><td>17</td></tr><tr><td>6.1</td><td>Bounds on the Expected Empirical Risk</td><td>18</td></tr><tr><td>6.2</td><td>(δ, ε)-Optimality</td><td>19</td></tr><tr><td>7</td><td>Interplay Between the Relative Entropy Asymmetry and the Empirical Risk</td><td>20</td></tr><tr><td>7.1</td><td>Sensitivity of the Log-Empirical Risk</td><td>22</td></tr><tr><td>7.2</td><td>Type-I and Type-II Optimal Measures</td><td>24</td></tr><tr><td>7.3</td><td>Numerical Comparison of Type-I and Type-II Regularization</td><td>25</td></tr><tr><td>8</td><td>Final Remarks</td><td>29</td></tr><tr><td colspan="2">Appendices</td><td>29</td></tr><tr><td>A</td><td>Preliminary</td><td>29</td></tr><tr><td>B</td><td>Proof of Lemma 3.1</td><td>31</td></tr><tr><td>C</td><td>Proof of Lemma 3.2</td><td>33</td></tr><tr><td>D</td><td>Proof of Lemma 4.1</td><td>35</td></tr><tr><td>E</td><td>Proof of Lemma 4.2</td><td>37</td></tr><tr><td>F</td><td>Proof of Lemma 4.6</td><td>40</td></tr><tr><td>G</td><td>Proof of Lemma 5.1</td><td>40</td></tr><tr><td>H</td><td>Proof of Lemma 5.2</td><td>41</td></tr><tr><td>I</td><td>Proof of Lemma 5.3</td><td>42</td></tr></table>
# Contents

<table><tr><td>1</td><td>Introduction</td><td>5</td></tr><tr><td>2</td><td>Empirical Risk Minimization</td><td>6</td></tr><tr><td>3</td><td>The Type-I ERM-RER Problem</td><td>7</td></tr><tr><td>4</td><td>The Type-II ERM-RER Problem</td><td>8</td></tr><tr><td>4.1</td><td>The Solution to the Type-II ERM-RER Problem</td><td>9</td></tr><tr><td>4.2</td><td>Properties of the Solution</td><td>11</td></tr><tr><td>4.2.1</td><td>The Normalization Function</td><td>11</td></tr><tr><td>4.2.2</td><td>Bounds on the Radon-Nikodym Derivative</td><td>16</td></tr><tr><td>4.2.3</td><td>Asymptotes of the Radon-Nikodym Derivative</td><td>17</td></tr><tr><td>5</td><td>The Expected Empirical Risk</td><td>18</td></tr><tr><td>6</td><td>(δ, ε)-Optimality</td><td>20</td></tr><tr><td>7</td><td>Interplay Between the Relative Entropy Asymmetry and the Empirical Risk</td><td>20</td></tr><tr><td>7.1</td><td>The Connection between Type-I and Type-II</td><td>21</td></tr><tr><td>7.2</td><td>Sensitivity of the Log-Empirical Risk</td><td>22</td></tr><tr><td>7.3</td><td>Type-I and Type-II Optimal Measures</td><td>24</td></tr><tr><td>8</td><td>Final Remarks</td><td>25</td></tr><tr><td>A</td><td>Proof of Lemma 4.1</td><td>26</td></tr><tr><td>B</td><td>Proof of Lemma 4.2</td><td>30</td></tr><tr><td>C</td><td>Proof of Lemma 4.4</td><td>31</td></tr><tr><td>D</td><td>Proof of Lemma 4.5</td><td>33</td></tr><tr><td>E</td><td>Proof of Lemma 4.8</td><td>34</td></tr><tr><td>F</td><td>Proof of Lemma 4.9</td><td>35</td></tr><tr><td>G</td><td>Proof of Lemma 4.10</td><td>36</td></tr><tr><td>H</td><td>Proof of Lemma 4.11</td><td>37</td></tr><tr><td>I</td><td>Proof of Lemma 4.12</td><td>37</td></tr><tr><td>J</td><td>Proof of Lemma 4.13</td><td>41</td></tr><tr><td>K</td><td>Proof of Lemma 5.1</td><td>42</td></tr></table>
<table><tbody><tr><td><b>J</b></td><td><b>Proof of Lemma 5.4</b></td><td><b>43</b></td></tr><tr><td></td><td>J.1 Case 1</td><td>44</td></tr><tr><td></td><td>J.1.1 Part 1</td><td>44</td></tr><tr><td></td><td>J.1.2 Part 2</td><td>45</td></tr><tr><td></td><td>J.1.3 Part 3</td><td>48</td></tr><tr><td></td><td>J.2 Case 2</td><td>48</td></tr><tr><td></td><td>J.2.1 Part 1</td><td>49</td></tr><tr><td></td><td>J.2.2 Part 2</td><td>49</td></tr><tr><td></td><td>J.2.3 Part 3</td><td>49</td></tr><tr><td><b>K</b></td><td><b>Proof of Lemma 5.5</b></td><td><b>50</b></td></tr><tr><td></td><td>K.1 Case 1</td><td>50</td></tr><tr><td></td><td>K.2 Case 2</td><td>51</td></tr><tr><td><b>L</b></td><td><b>Proof of Lemma 6.1</b></td><td><b>51</b></td></tr><tr><td><b>M</b></td><td><b>Proof of Lemma 6.2</b></td><td><b>52</b></td></tr><tr><td><b>N</b></td><td><b>Proof of Lemma 6.3</b></td><td><b>54</b></td></tr><tr><td><b>O</b></td><td><b>Proof of Lemma 6.5</b></td><td><b>55</b></td></tr><tr><td><b>P</b></td><td><b>Proof of Theorem 6.1</b></td><td><b>56</b></td></tr><tr><td><b>Q</b></td><td><b>Proof of Lemma 7.1</b></td><td><b>56</b></td></tr><tr><td><b>R</b></td><td><b>Proof of Lemma 7.2</b></td><td><b>57</b></td></tr><tr><td><b>S</b></td><td><b>Proof of Lemma 7.4</b></td><td><b>58</b></td></tr><tr><td><b>T</b></td><td><b>Examples</b></td><td><b>60</b></td></tr><tr><td></td><td>T.1 Example 1</td><td>60</td></tr><tr><td></td><td>T.2 Example 2</td><td>61</td></tr><tr><td></td><td>T.3 Example 3</td><td>63</td></tr><tr><td><b>U</b></td><td><b>Numerical Simulation</b></td><td><b>66</b></td></tr><tr><td></td><td>U.1 Feature Extraction of the Histogram of Oriented Gradients</td><td>66</td></tr><tr><td></td><td>U.2 Principal Component Analysis</td><td>69</td></tr><tr><td></td><td>U.3 Simulation Dataset</td><td>70</td></tr><tr><td><b>References</b></td><td></td><td><b>70</b></td></tr></tbody></table>
<table><tr><td>L</td><td>Proof of Lemma 5.2</td><td>43</td></tr><tr><td>M</td><td>Proof of Lemma 5.3</td><td>45</td></tr><tr><td>N</td><td>Proof of Lemma 5.5</td><td>46</td></tr><tr><td>O</td><td>Proof of Theorem 6.1</td><td>47</td></tr><tr><td>P</td><td>Proof of Lemma 7.1</td><td>48</td></tr><tr><td>Q</td><td>Proof of Lemma 7.2</td><td>49</td></tr><tr><td>R</td><td>Proof of Lemma 7.4</td><td>50</td></tr><tr><td>S</td><td>Example 4.3</td><td>52</td></tr><tr><td>T</td><td>Example 4.2</td><td>53</td></tr></table>
# 1 Introduction

EMPIRICAL risk minimization (ERM) is a central tool in supervised machine learning. Among other uses, it enables the characterization of sample complexity and probably approximately correct (PAC) learning in a wide range of settings [3]. The application of ERM in the study of theoretical guarantees spans related disciplines such as machine learning [4], information theory [5, 6] and statistics [7, 8]. Classical problems such as classification [9, 10], pattern recognition [11, 12], regression [13, 14], and density estimation [11, 15] can be posed as special cases of the ERM problem [15, 16]. Unfortunately, ERM is prone to training data memorization, a phenomenon also known as overfitting [17–19]. For that reason, ERM is often regularized in order to provide generalization guarantees [20–23]. Regularization establishes a preference over the models by encoding features of interest that conform to prior knowledge. In different statistical learning frameworks, such as Bayesian learning [24, 25] and PAC learning [26–28], the prior knowledge over the set of models can be described by a reference probability measure. More general references can be adopted as proved in [29, 30] for the case of σ-finite measures. In either case, the solution to the regularized ERM problem can be cast as a probability distribution over the set of models. Prior knowledge of the set of datasets can also be represented by probability measures, e.g., the worst-case data-generating probability measure introduced in [31].

## 1.1 Motivation

A common regularizer of the ERM problem is the relative entropy of the optimization probability measure with respect to a given reference measure over the set of models [15, 32–34]. The resulting problem formulation, termed ERM with relative entropy regularization (ERM-RER) has been extensively studied for both the case in which the reference measure is a probability measure [32–35] and the case in which it is a σ-finite measure [29, 30, 36]. While in both cases the solution is unique and corresponds to a Gibbs probability measure, the existence of the solution is guaranteed only in the case in which the reference measure is a probability measure [30]. Despite the many merits of the ERM-RER formulation, it has some significant limitations. Firstly, the absolute continuity of the optimization measure with respect to the reference measure is required for the existence of the corresponding Radon-Nikodym derivative, which is used by the relative entropy regularization. This absolute continuity sets an insurmountable barrier to the exploration of models outside the support of the reference measure. More specifically, models outside the support of the reference measure exhibit zero probability with respect to the Gibbs probability measure solution to ERM-RER, regardless of the evidence provided by the training dataset. Furthermore, selecting priors with full support often leads to computationally expensive partition functions [30, 32, 33] in high-dimensional spaces. While priors with large supports ensure the inclusion of high-performing models, they also assign non-zero probability to models with poor empirical risk. Secondly, the
# 1 Introduction

Empirical risk minimization (ERM) is a central tool in supervised machine learn-
ing. Among other uses, it enables the characterization of sample complexity and
probably approximately correct (PAC) learning in a wide range of settings [1].
The application of ERM in the study of theoretical guarantees spans related dis-
ciplines such as machine learning [2], information theory [3,4] and statistics [5,6].
Classical problems such as classification [7,8], pattern recognition [9,10], regres-
sion [11,12], and density estimation [9,13] can be posed as special cases of the
ERM problem [13,14]. Unfortunately, ERM is prone to training data memoriza-
tion, a phenomenon also known as overfitting [15-17]. For that reason, ERM is
often regularized in order to provide generalization guarantees [18-21]. Regular-
ization establishes a preference over the models by encoding features of interest
that conform to prior knowledge. In different statistical learning frameworks,
such as Bayesian learning [22,23] and PAC learning [24-26], the prior knowledge
over the set of models can be described by a reference probability measure. More
general references can be adapted as proved in [27, 28] for the case of $\sigma$-finite
measures. Prior knowledge on the set of datasets can also be represented by
probability measures, e.g., the worst-case data-generating probability measure
introduced in [29]. In either case, the solution to the regularized ERM problem
can be cast as a probability distribution over the set of models.

A common regularizer of the ERM problem is the relative entropy of the opt-
imization probability measure with respect to a given reference measure over
the set of models [13, 30-32]. The resulting problem formulation, termed ERM
with relative entropy regularization (ERM-RER) has been extensively studied
for both the case in which the reference measure is a probability measure [30-33]
and the case in which it is a σ-finite measure [27, 28, 34]. While in both cases
the solution is unique and corresponds to a Gibbs probability measure, the exis-
tence of the solution is ensured only in the case in which the reference measure
is a probability measure [28]. Despite the many merits of the ERM-RER for-
mulation, it has some significant limitations. Firstly, absolute continuity of the
optimization measure with respect to the reference measure is required for the
existence of the corresponding Radon-Nikodym derivative, which is used by the
relative entropy regularization. This absolute continuity sets an insurmount-
able barrier to the exploration of models outside the support of the reference
measure. More specifically, models outside the support of the reference measure
exhibit zero probability with respect to the Gibbs probability measure solution
to ERM-RER. More importantly, this holds regardless of the evidence provided
by the training dataset. Secondly, the choice of relative entropy over alterna-
tive divergences often follows arguments based on the simplicity of obtaining
generalization guarantees in the form of bounds [18]. Nonetheless, such bounds
are often hard to calculate and are not always informative when evaluated in
practical settings [35-37].

From all the above, exploring the asymmetry of the relative entropy is of par-
ticular interest to advancing the understanding of entropy regularization and
choice of relative entropy over alternative divergences often follows arguments based on the simplicity of obtaining generalization guarantees in the form of bounds [20] or even closed form expressions, see [30] and [37]. Nonetheless, such bounds and closed form expressions are often hard to calculate and are not always informative when evaluated in practical settings [1, 30, 31, 38–42]. The problem of ERM with a general $f$-divergence regularization has been explored in [43] and [44] in the case of a finite countable set of models, and recently extended to uncountable sets of models in [45] and [46]. The authors in [43–46] constrain the optimization domains to sets of measures that are mutually absolutely continuous with respect to the reference probability measure. In view of these, exploring the asymmetry of relative entropy is of particular interest to advancing the understanding of entropy regularization in the context of ERM and its role in generalization. Additionally, examining the asymmetry opens novel pathways to overcome some of the constraints imposed by relative entropy regularization, such as, the ability to select models outside the support of the prior.

The use of the relative entropy of the optimization measure with respect to the reference measure as a regularizer in the ERM-RER is termed Type-I ERM-RER. Alternatively, the use of the relative entropy of the reference measure with respect to the optimization measure is termed Type-II ERM-RER. Interestingly, the results in [43–45], which lead to special cases of the Type-I and Type-II ERM-RER problems by assuming that $f(x) = -x \log(x)$ and $f(x) = -\log(x)$, respectively, do not study the impact of the asymmetry of relative entropy. Another observation that motivates studying the asymmetry of relative entropy in ERM-RER is that numerical analyses of the Type-II ERM-RER, presented in Section 7, suggest that Type-II regularization exhibits a markedly different relationship between test error and training error when compared to that of Type-I regularization. While, the generalization capabilities of Type-I are better in the simulations carried out for this work, the performance of the Type-II regularization is comparable and displays promising properties that warrant further research.

## 1.2 Contributions

This paper presents the solution to Type-II ERM-RER optimization problem using a new method of proof. In particular, mutual absolute continuity between the measures involved is not imposed. Surprisingly, mutual absolute continuity is exhibited by the solution as a consequence of the structure of the problem. The key properties of the solution are highlighted, and an equivalence between the Type-I and Type-II ERM-RER problems is presented. This equivalence is achieved by replacing the empirical risk in the Type-I ERM-RER problem with another function, which can be interpreted as a tunable loss function, as described in [47–49]. The remainder of the paper is organized as follows. Section 2 presents the ERM-RER problem and its two variations: Type-I and Type-II. The main contribution of this paper, which is the solution to the
its role in generalization. The problem of ERM with a general f-divergence regularization has been explored in [38] and [39] in the case of a finite countable set of models, and recently extended to uncountable sets of models in [40]. Nonetheless, the authors in [38–40] constrain the optimization domains to sets of measures that are mutually absolutely continuous with respect to the reference probability. The use of the relative entropy of the optimization measure with respect to the reference in ERM-RER is termed Type-I ERM-RER. Alternatively, the use of the relative entropy of the reference measure with respect to the optimization measure, introduced here, is termed Type-II ERM-RER. Interestingly, the existing results in [38–40], which lead to special cases of the Type-I and Type-II ERM-RER problems by assuming that $f(x) = -x \log(x)$ and $f(x) = -\log(x)$, respectively, do not study the impact of the asymmetry of relative entropy in the context of ERM regularization.

This paper presents the solution to Type-II ERM-RER optimization problem using a new method of proof. In particular, mutual absolute continuity of the measures in the optimization domain with respect to the reference measure is not imposed. Nonetheless, such a mutual absolute continuity is exhibited by the solution as a consequence of the structure of the problem. The main properties of the solution are highlighted and an equivalence between Type-I and a Type-II ERM-RER problems is presented by replacing the empirical risk in the Type-I problem by another function, which can be cast as a tunable loss function as in [41–43].

The remainder of the paper is organized as follows. Section 2 presents the standard ERM problem. Section 3 describes the Type-I regularization. The main contribution of this paper, which is the solution to the Type-II ERM-RER problem, is presented in Section 4. Section 7 studies the equivalence between Type-I and Type-II regularization. The conclusions are summarized in Section 8.

## 2 Empirical Risk Minimization

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$.
Type-II ERM-RER problem, is presented in Section 3. This section also presents key properties of the solution. Section 6 uses these properties to characterize the expected empirical risk. Section 7 studies the equivalence between Type-I and Type-II ERM-RER problems. This work is concluded by Section 8, with some final remarks.

## 2 Empirical Risk Minimization

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

$$ \mathbf{z} \triangleq ((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 non-negative and for all $y \in \mathcal{Y}$, $\ell(y, y) = 0$.

The empirical risk induced by the model $\theta$, with respect to the dataset $\mathbf{z}$ in (1) is determined by the function $\mathbf{L}_z: \mathcal{M} \to [0, \infty)$, which satisfies

$$ \mathbf{L}_z(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(\theta, x_i), y_i). \quad (3) $$

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

$$ \min_{\theta \in \mathcal{M}} \mathbf{L}_z(\theta). \quad (4) $$

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

$$ \mathcal{T}(\mathbf{z}) \triangleq \arg \min_{\theta \in \mathcal{M}} \mathbf{L}_z(\theta). \quad (5) $$

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

The PAC and Bayesian frameworks, as discussed in [25] and [27], address the problem in (4) by constructing probability measures, conditioned on the dataset $\mathbf{z}$, from which models are randomly sampled. In this context, the focus is on probability measures that assign high probability to minimizers of the ERM problem in (4). Such probability measures are defined on the measurable
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). \quad (3)$$

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

$$\min_{\theta \in \mathcal{M}} L_z(\theta). \quad (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). \quad (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 does not necessarily possess a solution, i.e., it might happen that $|\mathcal{T}(z)| = 0$.

The PAC and Bayesian frameworks, c.f. in [23] and [25], solve the problem in (4) by constructing probability measures conditioned on the dataset $z$, from which models are randomly sampled. In this context, finding probability measures that are minimizers of the ERM problem in (4) over the set of all probability measures that can be defined on the measurable space $(\mathcal{M}, \mathcal{F})$, which is denoted by $\Delta(\mathcal{M})$, requires a metric that enables assessing the goodness of the probability measure. From this perspective, the underlying assumption in the remainder of this work is that the functions $f$ and $\ell$ in (3) are such that for all $(x, y) \in \mathcal{X} \times \mathcal{Y}$, the function $g_{x,y}: \mathcal{M} \to [0, \infty]$, such that $g_{x,y}(\theta) = \ell(f_{\theta}(x), y)$, is measurable with respect to the Borel measurable spaces $(\mathcal{M}, \mathcal{F})$ and $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$, where $\mathcal{F}$ and $\mathcal{B}(\mathbb{R})$ are respectively the Borel $\sigma$-fields on $\mathcal{M}$ and $\mathbb{R}$. Under these assumptions, a common metric is the notion of expected empirical risk.

**Definition 2.1** (Expected Empirical Risk). Given the dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$ in (1), for all probability measures $P \in \Delta(\mathcal{M})$ let the functional $R_z: \Delta(\mathcal{M}) \to [0, \infty)$ be such that

$$R_z(P) \triangleq \int L_z(\theta) dP(\theta), \quad (6)$$

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

In the following section, the Type-I relative entropy regularization is reviewed as it serves as the basis for the analysis of the regularization asymmetry.

# 3 The Type-I ERM-RER Problem

The Type-I ERM-RER problem is parametrized by a probability measure $Q \in \Delta(\mathcal{M})$ and a real $\lambda \in (0, \infty)$. The measure $Q$ is referred to as the reference
space $(\mathcal{M}, \mathcal{F})$, which is denoted by $\Delta(\mathcal{M})$. From this perspective, the underlying assumption in the remainder of this work is that the functions $f$ and $\ell$ in (3) are such that for all $(x, y) \in \mathcal{X} \times \mathcal{Y}$, the function $g_{x,y}: \mathcal{M} \to [0, \infty)$, such that $g_{x,y}(\theta) = \ell(f(\theta, x), y)$, is measurable with respect to the Borel measurable spaces $(\mathcal{M}, \mathcal{F})$ and $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$, where $\mathcal{F}$ and $\mathcal{B}(\mathbb{R})$ are, respectively, Borel $\sigma$-fields on $\mathcal{M}$ and $\mathbb{R}$. Under these assumptions, a common metric is the expected empirical risk.

**Definition 2.1** (Expected Empirical Risk). Given the dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$ in (1), let the functional $\mathbb{R}_z: \Delta(\mathcal{M}) \to [0, \infty)$ be such that

$$ \mathbb{R}_z(P) = \int \mathbb{L}_z(\theta) dP(\theta), \qquad (6) $$

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

In the following section, the Type-I relative entropy regularization is reviewed as it serves as the basis for the analysis of the regularization asymmetry.

## 2.1 The Type-I ERM-RER Problem

The Type-I ERM-RER problem is parameterized by a probability measure $Q \in \Delta(\mathcal{M})$ and a real $\lambda \in (0, \infty)$. The measure $Q$ is referred to as the reference measure and $\lambda$ as the regularization factor. The Type-I ERM-RER problem, with parameters $Q$ and $\lambda$, is given by the following optimization problem:

$$ \min_{P \in \Delta_Q(\mathcal{M})} \mathbb{R}_z(P) + \lambda \mathrm{D}(P \| Q), \qquad (7) $$

where the functional $\mathbb{R}_z$ is defined in (6), and the optimization domain is

$$ \Delta_Q(\mathcal{M}) \triangleq \{P \in \Delta(\mathcal{M}) : P \ll Q\}, \qquad (8) $$

with the notation $P \ll Q$ standing for $P$ being absolutely continuous with respect to $Q$.

The solution to the Type-I ERM-RER problem in (7) is the Gibbs probability measure reported in [29, 32] and [33]. In order to introduce such a measure, consider the function $K_{Q,z}: \mathbb{R} \to \mathbb{R}$ that satisfies for all $t \in \mathbb{R}$,

$$ K_{Q,z}(t) = \log \left( \int \exp(t\mathbb{L}_z(\theta)) dQ(\theta) \right), \qquad (9) $$

with $\mathbb{L}_z$ in (3). Using this notation, the solution to the Type-I ERM-RER problem in (7) is presented by the following lemma.

**Lemma 2.1** ([30, Theorem 3]). The solution to the optimization problem in (7) is a unique probability measure, denoted by $P_{\Theta|Z=z}^{(Q,\lambda)}$, which satisfies for all $\theta \in \mathrm{supp} Q$,

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

where the function $\mathbb{L}_z$ is defined in (3) and the function $K_{Q,z}$ is defined in (9).
measure and $\lambda$ as the regularization factor. The Type-I ERM-RER problem, with parameters $Q$ and $\lambda$, is given by the following optimization problem:

$$ \min_{P \in \Delta_Q(\mathcal{M})} \mathbf{R}_z(P) + \lambda D(P \| Q), \qquad (7) $$

where the functional $\mathbf{R}_z$ is defined in (6), and the optimization domain is

$$ \Delta_Q(\mathcal{M}) \triangleq \{P \in \Delta(\mathcal{M}) : P \ll Q\}. \qquad (8) $$

The notation $P \ll Q$ stands for $P$ being absolutely continuous with respect to $Q$.

The solution to the Type-I ERM-RER problem in (7) is the Gibbs probability measure [27, 30, 31], which is presented in the following lemma.

**Lemma 3.1** ([28, Theorem 3.1]). *The solution of the Type-I ERM-RER problem in (7), denoted by $P_{\Theta|Z=z}^{(Q,\lambda)} \in \Delta(\mathcal{M})$, is unique, always exists, and satisfies for all $\theta \in \text{supp } Q$*

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

where the function $K_{Q,z}: \mathbb{R} \to \mathbb{R}$ is such that

$$ K_{Q,z}(t) = \log\left(\int \exp(t\mathbf{L}_z(\theta)) \mathrm{d}Q(\theta)\right). \qquad (10) $$

# 4 The Type-II ERM-RER Problem

The Type-II ERM-RER problem is parametrized by a probability measure $Q \in \Delta(\mathcal{M})$ and a real $\lambda \in (0, \infty)$. As in Type-I ERM-RER problem, the measure $Q$ is referred to as the reference measure and $\lambda$ as the regularization factor. Given the dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$ in (1), the Type-II ERM-RER problem, with parameters $Q$ and $\lambda$, consists of the following optimization problem:

$$ \min_{P \in \nabla_Q(\mathcal{M})} \mathbf{R}_z(P) + \lambda D(Q \| P), \qquad (11) $$

where the functional $\mathbf{R}_z$ is defined in (6), and the optimization domain is

$$ \nabla_Q(\mathcal{M}) \triangleq \{P \in \Delta(\mathcal{M}) : Q \ll P\}. \qquad (12) $$

The difference between Type-I and Type-II ERM-RER problems lies on the regularization. While the former uses the relative entropy $D(P \| Q)$, the latter uses $D(Q \| P)$. This translates into different optimization domains due to the asymmetry of the relative entropy. More specifically, in the Type-I ERM-RER problem, the optimization domain is the set of probability measures on the Borel measurable space $(\mathcal{M}, \mathcal{F})$ that are absolutely continuous with the reference
## 2.2 The Type-II ERM-RER Problem

The Type-II ERM-RER problem is parameterized by a probability measure $Q \in \Delta(\mathcal{M})$ and a real $\lambda \in (0, \infty)$. As in the Type-I ERM-RER problem, the measure $Q$ is referred to as the reference measure and $\lambda$ as the regularization factor. Given the dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$ in (1), the Type-II ERM-RER problem, with parameters $Q$ and $\lambda$, consists of the following optimization problem:

$$ \min_{P \in \nabla_Q(\mathcal{M})} \mathrm{R}_z(P) + \lambda \mathrm{D}(Q \| P), \qquad (11) $$

where the functional $\mathrm{R}_z$ is defined in (6), and the optimization domain is

$$ \nabla_Q(\mathcal{M}) \triangleq \{P \in \Delta(\mathcal{M}) : Q \ll P\}. \qquad (12) $$

The difference between Type-I and Type-II ERM-RER problems lies on the regularization. While the former uses the relative entropy $\mathrm{D}(P \| Q)$, the latter uses $\mathrm{D}(Q \| P)$. This translates into different optimization domains due to the asymmetry of the relative entropy. More specifically, in the Type-I ERM-RER problem, the optimization domain is the set of probability measures on the Borel measurable space $(\mathcal{M}, \mathcal{F})$ that are absolutely continuous with the reference measure $Q$. That is, the set $\Delta_Q(\mathcal{M})$ in (8). Alternatively, in the Type-II ERM-RER problem, the optimization domain consists of probability measures defined on the Borel measurable space $(\mathcal{M}, \mathcal{F})$, with the additional condition that the reference measure $Q$ must be absolutely continuous with respect to them. This corresponds to the set denoted as $\nabla_Q(\mathcal{M})$ in (12). From this perspective, the techniques used in [30] for solving the Type-I ERM-RER no longer hold. In the next section, a new technique is developed for solving the Type-II ERM-RER.

The problems in (7) and (11) exhibit trivial solutions when the functional $\mathrm{R}_z$ is such that for all $P \in \Delta_Q(\mathcal{M})$ or $P \in \nabla_Q(\mathcal{M})$, respectively, it holds that $\mathrm{R}_z(P) = c$, for some $c \in [0, \infty)$. In such a case, the solution is unique and equal to the probability measure $Q$, independently of the parameter $\lambda$. In order to avoid this trivial case, the notion of separability of the empirical risk function with respect to the measure $Q$ is borrowed from [30]. A separable empirical risk function with respect to a given probability measure $P$ is defined as follows.

**Definition 2.2** (Definition 5 in [30]). The empirical risk function $\mathrm{L}_z$ in (3) is said to be separable with respect to the probability measure $P \in \Delta(\mathcal{M})$, if 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$, and for all $(\theta_1, \theta_2) \in \mathcal{A} \times \mathcal{B}$,

$$ \mathrm{L}_z(\theta_1) < c < \mathrm{L}_z(\theta_2) < \infty. \qquad (13) $$

A nonseparable empirical risk function $\mathrm{L}_z$ in (3) with respect to a measure $P$ is a constant almost surely with respect to the measure $P$. More specifically, there exists a real $a \ge 0$, such that

$$ P(\{\theta \in \mathcal{M} : \mathrm{L}_z(\theta) = a\}) = 1. \qquad (14) $$
measure $Q$. That is, the set $\Delta_Q(\mathcal{M})$ in (8). Alternatively, in the Type-II ERM-RER problem, the optimization domain consists of probability measures defined on the Borel measurable space $(\mathcal{M}, \mathcal{F})$, with the additional condition that the reference measure $Q$ must be absolutely continuous with respect to them. This corresponds to the set denoted as $\nabla_Q(\mathcal{M})$ in Equation (12). From this perspective, the techniques used in [28] for solving the Type-I ERM-RER no longer hold. As shown in the next section, a new technique is used for solving the Type-II ERM-RER.

The problem in (11) exhibits a trivial solution when the functional $\mathbb{R}_z$ is such that for all $P \in \nabla_Q(\mathcal{M})$, it holds that $\mathbb{R}_z(P) = c$, for some $c \in [0, \infty)$. In such a case, the solution is unique and equal to the probability measure $Q$, independently of the parameter $\lambda$. In order to avoid this trivial case, which arises under particular conditions over the empirical risk function $\mathbb{L}_z$ in (3) and the probability measure $Q$, the notion of separability of the empirical risk function with respect to the measure $Q$ is borrowed from [28]. A separable empirical risk function with respect to a given probability measure $P$ is defined as follows.

**Definition 4.1** (Definition 4.1 in [28]). The empirical risk function $\mathbb{L}_z$ in (3) is said to be separable with respect to the probability measure $P \in \Delta(\mathcal{M})$, if there exist a positive real $c > 0$ and two subsets $A$ and $B$ of $\mathcal{M}$ that are nonnegligible with respect to $P$, and for all $(\theta_1, \theta_2) \in A \times B$,

$$ \mathbb{L}_z(\theta_1) < c < \mathbb{L}_z(\theta_2) < \infty. \quad (13) $$

A nonseparable empirical risk function $\mathbb{L}_z$ in (3) with respect to a measure $P$ is a constant almost surely with respect to the measure $P$. More specifically, there exists a real $a \ge 0$, such that

$$ P(\{\theta \in \mathcal{M} : \mathbb{L}_z(\theta) = a\}) = 1. \quad (14) $$

When the empirical risk function $\mathbb{L}_z$ in (3) is nonseparable with respect to all measures in $P \in \nabla_Q(\mathcal{M})$, the trivial case described above is observed. The notion of separable empirical risk functions would play a central role in the study of the optimization problem in (11).

## 4.1 The Solution to the Type-II ERM-RER Problem

The solution of the Type-II ERM-RER problem in (11) is presented in the following theorem, where the measure $Q$ is a parameter of the optimization problem in (11) and the function $\mathbb{L}_z$ is defined in (3).

**Theorem 4.1.** If there exists a real $\beta$ such that

$$ \beta \in \{t \in \mathbb{R} : \forall \theta \in \text{supp} Q, 0 < t + \mathbb{L}_z(\theta)\}, \quad (15a) $$

and

$$ \int \frac{\lambda}{\beta + \mathbb{L}_z(\theta)} dQ(\theta) = 1, \quad (15b) $$
When the empirical risk function $L_z$ in (3) is nonseparable with respect to all measures in $P \in \nabla_Q(\mathcal{M})$, the trivial case described above is observed. The notion of separable empirical risk functions would play a central role in the study of the optimization problem in (11).

## 3 The Solution to the Type-II ERM-RER Problem

The solution to the Type-II ERM-RER problem in (11) is presented in the following theorem.

**Theorem 3.1.** If there exists a real $\beta$ such that

$$ \beta \in \{t \in \mathbb{R} : \forall \theta \in \text{supp } Q, 0 < t + L_z(\theta)\}, \quad (15a) $$

and

$$ \int \frac{\lambda}{\beta + L_z(\theta)} dQ(\theta) = 1, \quad (15b) $$

with the function $L_z$ defined in (3), and $\lambda$ and $Q$ the parameters of the optimization problem in (11), then, the solution to such a problem, denoted by $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \in \Delta(\mathcal{M})$, is unique and for all $\theta \in \text{supp } Q$, it satisfies

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda}{\beta + L_z(\theta)}. \quad (16) $$

Before introducing the proof of Theorem 3.1, two important results are presented. The first result provides the solution to the optimization problem in (11) when the optimization domain is restricted to

$$ \mathcal{O}_Q(\mathcal{M}) \triangleq \nabla_Q(\mathcal{M}) \cap \Delta_Q(\mathcal{M}), \quad (17) $$

where the sets $\Delta_Q(\mathcal{M})$ and $\nabla_Q(\mathcal{M})$ are defined in (8) and (12), respectively. This ancillary problem can be formulated as follows:

$$ \min_{P \in \mathcal{O}_Q(\mathcal{M})} R_z(P) + \lambda D(Q \| P), \quad (18) $$

where the functional $R_z$ is defined in (6). The solution to the problem in (18) is described by the following lemma.

**Lemma 3.1.** The solution to the optimization problem in (18) is unique and identical to the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16).

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

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

The second result consists of comparing the optimal values resulting from the optimization problems in (11) and (18), as shown hereunder.
then the solution to the optimization problem in (11), denoted by $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \in \Delta(\mathcal{M})$, is unique and for all $\theta \in \text{supp } Q$, it satisfies

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda}{\beta + L_z(\theta)}. \qquad (16) $$

Before introducing the proof of Theorem 4.1, two important results are presented. The first result consists in the solution to the optimization problem in (11) when the optimization domain is restricted to

$$ \mathcal{O}_Q(\mathcal{M}) \triangleq \nabla_Q(\mathcal{M}) \cap \Delta_Q(\mathcal{M}), \qquad (17) $$

where the sets $\Delta_Q(\mathcal{M})$ and $\nabla_Q(\mathcal{M})$ are defined in (8) and (12), respectively. Such an ancillary problem can be formulated as follows:

$$ \min_{P \in \mathcal{O}_Q(\mathcal{M})} \mathbf{R}_z(P) + \lambda \mathbf{D}(Q \| P). \qquad (18) $$

The solution to such an ancillary problem is described by the following lemma.

**Lemma 4.1.** *The solution to the optimization problem in (18) is unique and identical to the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16).*

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

The second result consists of comparing the optimal values resulting from the optimizations in (11) and (18). The following lemma formalizes this result.

**Lemma 4.2.** *The optimization problems in (11) and (18) satisfy*

$$ \min_{P \in \nabla_Q} \mathbf{R}_z(P) + \lambda \mathbf{D}(Q \| P) \geq \min_{P \in \mathcal{O}_Q} \mathbf{R}_z(P) + \lambda \mathbf{D}(Q \| P). \qquad (19) $$

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

Lemma 4.2 unveils the fact that the objective function in (11) when evaluated at measures whose support extends beyond the support of $Q$ is larger than such an objective function evaluated at measures whose support is identical to the reference measure. This includes the case in which the set $\mathcal{T}(z)$ in (5) lies outside the support of $Q$.

Using these results, the proof of Theorem 4.1 is as follows.

*Proof of Theorem 4.1:* The proof follows by observing that from (17), it holds that

$$ \mathcal{O}_Q(\mathcal{M}) \subseteq \nabla_Q(\mathcal{M}). \qquad (20) $$

Hence, from (20), it follows that

$$ \min_{P \in \nabla_Q} \mathbf{R}_z(P) + \lambda \mathbf{D}(Q \| P) \leq \min_{P \in \mathcal{O}_Q} \mathbf{R}_z(P) + \lambda \mathbf{D}(Q \| P). \qquad (21) $$
**Lemma 3.2.** The optimization problems in (11) and (18) satisfy

$$ \min_{P \in \nabla_Q} \mathrm{R}_z(P) + \lambda \mathrm{D}(Q \| P) \geq \min_{P \in \mathcal{O}_Q} \mathrm{R}_z(P) + \lambda \mathrm{D}(Q \| P). \quad (19) $$

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

Lemma 3.2 unveils the fact that the objective function in (11) when evaluated at measures whose support extends beyond the support of $Q$ is larger than such an objective function evaluated at measures whose support is identical to the reference measure. This includes the case in which the set $\mathcal{T}(z)$ in (5) lies outside the support of $Q$. Using these results, the proof of Theorem 3.1 is as follows.

*Proof of Theorem 3.1:* The proof follows by observing that from (17), it holds that

$$ \mathcal{O}_Q(\mathcal{M}) \subseteq \nabla_Q(\mathcal{M}). \quad (20) $$

Hence, from (20), it follows that

$$ \min_{P \in \nabla_Q} \mathrm{R}_z(P) + \lambda \mathrm{D}(Q \| P) \leq \min_{P \in \mathcal{O}_Q} \mathrm{R}_z(P) + \lambda \mathrm{D}(Q \| P). \quad (21) $$

From the inequalities in (19) and (21), it also follows that

$$ \min_{P \in \nabla_Q} \mathrm{R}_z(P) + \lambda \mathrm{D}(Q \| P) = \min_{P \in \mathcal{O}_Q} \mathrm{R}_z(P) + \lambda \mathrm{D}(Q \| P). \quad (22) $$

Thus, the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) is the solution of the optimization problem in (11), which completes the proof of Theorem 3.1. ■

Lemma 3.2 implies that the solution to the optimization problem in (11) is in the set $\mathcal{O}_Q(\mathcal{M})$ in (16). A consequence of this observation is the following corollary.

**Corollary 3.3.** The probability measures $Q$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) are mutually absolutely continuous.

Corollary 3.3 also follows from Theorem 3.1 by observing that the solution to the Type-II ERM-RER problem in (11) is expressed in terms of its Radon-Nikodym derivative with respect to $Q$, which implies the absolute continuity of $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ with respect to $Q$. The absolute continuity of the measure $Q$ with respect to $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ follows from the optimization domain of the Type-II ERM-RER problem. From this perspective, Corollary 3.3 conveys the fact that there does not exist a dataset that can overcome the inductive bias induced by the reference measure $Q$. That is, sets of models outside the support of $Q$ exhibit zero probability measure with respect to the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$.

This observation is important as, at first glance, the Type-II relative entropy regularization for the ERM problem in (11) does not restrict the solution to be absolutely continuous with respect to the reference measure $Q$. However,
From the inequalities in (19) and (21), it follows that

$$ \min_{P \in \nabla_Q} \mathrm{R}_z(P) + \lambda \mathrm{D}(Q \| P) = \min_{P \in \mathcal{O}_Q} \mathrm{R}_z(P) + \lambda \mathrm{D}(Q \| P). \quad (22) $$

Thus, the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) is the solution of the optimization problem in (11), which completes the proof of Theorem 4.1. ■

Lemma 4.2 implies that the solution to the optimization problem in (11) is in the set $\mathcal{O}_Q(M)$ in (16). A consequence of this observation is the following corollary.

**Corollary 4.3.** The probability measures $Q$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) are mutually absolutely continuous.

Corollary 4.3 also follows from Theorem 4.1 by observing that the solution to the Type-II ERM-RER problem in (11) is expressed in terms of its Radon-Nikodym with respect to $Q$, which implies the absolute continuity of $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ with respect to $Q$. The absolute continuity of the measure $Q$ with respect to $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ follows from the optimization domain of the Type-II ERM-RER problem. From this perspective, Corollary 4.3 conveys the fact that there does not exist a dataset that can overcome the inductive bias induced by the reference measure $Q$. That is, set of models outside the support of $Q$ exhibit zero probability measure with respect to the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$.

This observation is important as at a first glance, the Type-II relative entropy regularization for the ERM problem in (11) does not restrict the solution to be absolutely continuous with respect to the reference measure $Q$. However, Theorem 4.1 shows that the support of the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) collapses into the support of the reference. A parallel can be established between Type-I and Type-II cases, as in both cases the support of the solution is the support of the reference measure. In a nutshell, the use of relative entropy regularization inadvertently forces the solution to coincide with the support of the reference regardless of the training data.

## 4.2 Properties of the Solution

This section introduces a function referred to as the normalization function and its properties. This function as well as its properties are central for studying the solution to the ERM-RER problem in (11).

### 4.2.1 The Normalization Function

Let the function

$$ \bar{K}_{Q,z} : (0, \infty) \to \mathcal{A}, \quad (23a) $$

with $\mathcal{A} \subseteq \mathbb{R}$, and $Q$ and $z$ in (11), be such that for all $t \in (0, \infty)$

$$ \bar{K}_{Q,z}(t) = \alpha, \quad (23b) $$
Theorem 3.1 shows that the support of the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) collapses into the support of the reference. A parallel can be established between Type-I and Type-II cases, as in both cases, the support of the solution is the support of the reference measure. In a nutshell, the use of relative entropy regularization inadvertently forces the solution to coincide with the support of the reference regardless of the training data.

# 4 The Normalization Function

Let the set $A_{Q,z} \subseteq (0, \infty)$ and $C_{Q,z} \subset \mathbb{R}$, with $Q$ and $z$ in (11), be such that if $\lambda \in A_{Q,z}$, then there exists a $\beta \in C_{Q,z}$ that satisfies the inclusion in (15a) and (15b). From Theorem 3.1, specifically from the uniqueness of the solution to (11), it follows that for all $(\lambda, \beta) \in A_{Q,z} \times C_{Q,z}$ and for all $\alpha \in \mathbb{R}$, with $\alpha \neq \beta$, it holds that $(\lambda, \alpha) \notin A_{Q,z} \times C_{Q,z}$. This observation allows establishing a bijection between these two sets. Let such a bijection be represented by the function

$$ \bar{K}_{Q,z} : A_{Q,z} \to C_{Q,z}, \qquad (23a) $$

which satisfies

$$ \bar{K}_{Q,z}(\lambda) = \beta, \qquad (23b) $$

with $\lambda$ and $\beta$ satisfying (15). The function $\bar{K}_{Q,z}$ in (23) is referred to as the normalization function. This is due to the observation that the Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) can be re-written for all $\theta \in \text{supp } Q$, as

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda}{\bar{K}_{Q,z}(\lambda) + L_z(\theta)}, \qquad (24) $$

which together with (15b), implies that the function $\bar{K}_{Q,z}$ ensures that $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) is a probability measure.

The analysis of the normalization function $\bar{K}_{Q,z}$ in (23) relies on the analysis of its functional inverse, denoted by $\bar{K}_{Q,z}^{-1} : C_{Q,z} \to A_{Q,z}$, which can be defined by noticing that

$$ 1 = \int \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \qquad (25a) $$

$$ = \int \frac{\lambda}{L_z(\theta) + \beta} dQ(\theta), \qquad (25b) $$

with the function $L_z$ defined in (3), and $\lambda$ and $Q$ the parameters of the optimization problem in (11). More specifically, from (23b), it follows that $\lambda = \bar{K}_{Q,z}^{-1}(\beta)$; and from (25b), it follows that

$$ \bar{K}_{Q,z}^{-1}(\beta) = \frac{1}{\int \frac{1}{L_z(\theta) + \beta} dQ(\theta)}. \qquad (26) $$
where $\alpha$ satisfies

$$ \int \frac{t}{\alpha + \mathbf{L}_z(\boldsymbol{\theta})} \mathrm{d}Q(\boldsymbol{\theta}) = 1, \qquad (24) $$

and the function $\mathbf{L}_z$ is defined in (3). The function $\bar{K}_{Q,z}$ is referred to as the normalization function. This is essentially due to the observation that $\beta$ and $\lambda$ in (16) satisfy

$$ \bar{K}_{Q,z}(\lambda) = \beta, \qquad (25) $$

which guarantees that the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \in \Delta(\mathcal{M})$ in (16) is a probability measure. Hence, the Radon-Nikodym derivative in (16) satisfies for all $\boldsymbol{\theta} \in \mathrm{supp} Q$

$$ \frac{\mathrm{d}\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) = \frac{\lambda}{\bar{K}_{Q,z}(\lambda) + \mathbf{L}_z(\boldsymbol{\theta})}. \qquad (26) $$

The properties of the function $\bar{K}_{Q,z}$ in (23b) are studied using the notion of Rashamon sets [44]. Given a real $\delta \in [0, \infty)$, consider the Rashamon set

$$ \mathcal{L}_z(\delta) \triangleq \{\boldsymbol{\theta} \in \mathcal{M} : \mathbf{L}_z(\boldsymbol{\theta}) \leq \delta\}. \qquad (27) $$

Consider also the nonnegative real number

$$ \delta_{Q,z}^* \triangleq \inf\{\delta \in [0, \infty) : Q(\mathcal{L}_z(\delta)) > 0\}. \qquad (28) $$

Let also $\mathcal{L}_{Q,z}^*$ be the following level set of the empirical risk function $\mathbf{L}_z$ in (3):

$$ \mathcal{L}_{Q,z}^* \triangleq \{\boldsymbol{\theta} \in \mathcal{M} : \mathbf{L}_z(\boldsymbol{\theta}) = \delta_{Q,z}^*\}. \qquad (29) $$

Using the objects defined above, the following lemma introduces one of the main properties of the function $\bar{K}_{Q,z}$ in (23).

**Lemma 4.4.** The function $\bar{K}_{Q,z}$ in (23) is strictly increasing and continuous.

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

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

As a consequence of Lemma 4.4, the continuity of function $\bar{K}_{Q,z}$ in (23) and equality (24), it follows that for all $\alpha \in \mathcal{A}$, with $\mathcal{A}$ in (23a), the functional inverse $\bar{K}_{Q,z}^{-1} : \mathcal{A} \to (0, \infty)$ is given by

$$ \bar{K}_{Q,z}^{-1}(\alpha) = \frac{1}{\int_{\mathbf{L}_z(\boldsymbol{\theta})+\alpha}^{\mathbf{L}_z(\boldsymbol{\theta})} \mathrm{d}Q(\boldsymbol{\theta})}. \qquad (30) $$

Note that the function $\bar{K}_{Q,z}^{-1}$ in (30) allows defining the codomain of the function $\bar{K}_{Q,z}$ in (23b), which is formalized by the following lemma.
Note that while the function $\bar{K}_{Q,z}$ in (23) is defined implicitly, its functional inverse $\bar{K}_{Q,z}^{-1}$ is defined explicitly in (26). The existence of the function and inverse follows from the fact that $\bar{K}_{Q,z}$ is a bijection.

The purpose of the remaining of this section is to provide a characterization of the sets $\mathcal{A}_{Q,z}$ and $\mathcal{C}_{Q,z}$. To do so, some mathematical objects are introduced. Given a real $\delta \in [0, \infty)$, consider the Rashomon set $[50]$, $\mathcal{L}_z(\delta)$, defined as follows

$$ \mathcal{L}_z(\delta) \triangleq \{\theta \in \mathcal{M} : \mathcal{L}_z(\theta) \leq \delta\}. \qquad (27) $$

Consider also the real numbers $\delta_{Q,z}^*$ and $\lambda_{Q,z}^*$ defined as follow:

$$ \delta_{Q,z}^* \triangleq \inf\{\delta \in [0, \infty) : Q(\mathcal{L}_z(\delta)) > 0\}, \qquad (28) $$

and

$$ \lambda_{Q,z}^* \triangleq \inf \mathcal{A}_{Q,z}. \qquad (29) $$

Let also $\mathcal{L}_{Q,z}^*$ be the level set of the empirical risk function $\mathcal{L}_z$ in (3) for the value $\delta_{Q,z}^*$. That is,

$$ \mathcal{L}_{Q,z}^* \triangleq \{\theta \in \mathcal{M} : \mathcal{L}_z(\theta) = \delta_{Q,z}^*\}. \qquad (30) $$

Using the objects defined above, the following lemma introduces one of the main properties of the function $\bar{K}_{Q,z}$ in (23).

**Lemma 4.1.** The function $K_{Q,z}$ in (23) is strictly increasing and continuous.

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

The following lemma characterizes the sets $\mathcal{A}_{Q,z}$ and $\mathcal{C}_{Q,z}$ in (23a), which are the domain and codomain of the function $\bar{K}_{Q,z}$ in (23b).

**Lemma 4.2.** The set $\mathcal{A}_{Q,z}$ in (23a) is either empty or an interval of the form

$$ \mathcal{A}_{Q,z} = \begin{cases} [\lambda_{Q,z}, \infty) & \text{if } \int \frac{1}{\mathcal{L}_z(\theta) - \delta_{Q,z}^*} dQ(\theta) < \infty \\ (0, \infty) & \text{otherwise,} \end{cases} \qquad (31) $$

where

$$ \lambda_{Q,z} = \bar{K}_{Q,z}^{-1}(-\delta_{Q,z}^*), \qquad (32) $$

with $\bar{K}_{Q,z}^{-1}$ in (26), the function $\mathcal{L}_z$ is defined in (3), and $\delta_{Q,z}^*$ is defined in (28). Moreover, the set $\mathcal{C}_{Q,z}$ in (23a) is either empty or an interval of the form

$$ \mathcal{C}_{Q,z} = \begin{cases} [-\delta_{Q,z}^*, \infty) & \text{if } \int \frac{1}{\mathcal{L}_z(\theta) - \delta_{Q,z}^*} dQ(\theta) < \infty. \\ (-\delta_{Q,z}^*, \infty) & \text{otherwise.} \end{cases} \qquad (33) $$

*Proof:* The proof is presented in Appendix E. ■
**Lemma 4.5.** The set $\mathcal{A}$ in (23a) satisfies

$$(-\delta_{Q,z}^*, \infty) \subseteq \mathcal{A} \subseteq [-\delta_{Q,z}^*, \infty). \qquad (31)$$

Moreover, the set $\mathcal{A}$ is identical to $[-\delta_{Q,z}^*, \infty)$ if and only if

$$\int \frac{1}{\mathcal{L}_z(\theta) - \delta_{Q,z}^*} dQ(\theta) < \infty, \qquad (32)$$

with $\delta_{Q,z}^*$ defined in (28).

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

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

Observe that for all finite sets of models $\mathcal{M}$, the subset $\mathcal{L}_{Q,z}^*$ as defined in (29) satisfies $Q(\mathcal{L}_{Q,z}^*) > 0$. This implies that the integral in (32) is not finite. The formalization of this observation is presented in the following corollary.

**Corollary 4.6.** If the set $\mathcal{M}$ is finite, then the set $\mathcal{A}$ in (23a) is identical to $(-\delta_{Q,z}^*, \infty)$.

An additional remark, is that from Lemma 4.4 and Lemma 4.5, if the set $\mathcal{A}$ in (23a) is equal to the closed set $[\delta_{Q,z}^*, \infty)$ in (31), there exists a minimum regularization factor $\lambda^* > 0$, where $\lambda^* = \bar{K}_{Q,z}^{-1}(-\delta_{Q,z}^*)$, with $\bar{K}_{Q,z}^{-1}$ defined in (30). This implies that the mapping of the function $\bar{K}_{Q,z}$ in (23) is such that $\bar{K}_{Q,z} : [\lambda^*, \infty) \to [-\delta_{Q,z}^*, \infty)$. This minimum regularization implies that the existence of a solution to the optimization problem in (11) only exists for regularization factors $\lambda \ge \lambda^*$.

Based on Lemma 4.5, the existence of the minimum regularization factor depends on whether the integral in (32) is finite. The finiteness of the integral is conditioned by the reference measure $Q$; the functions $\ell$ and $f$ in (3); and the dataset $z$ in (1). The subsequent examples illustrate situations where the set $\mathcal{A}$ is the open set $(\delta_{Q,z}^*, \infty)$ and closed set $[\delta_{Q,z}^*, \infty)$ in (31).

**Example 4.1.** Consider the Type-II ERM-RER problem in (11) and assume that: (a) $\mathcal{M} = \mathcal{X} = \mathcal{Y} = [0, \infty)$; (b) $z = (1, 0)$ and (c) $Q \ll \mu$, with $\mu$ the Lebesgue measure, such that for all $\theta \in \text{supp } Q$,

$$\frac{dQ}{d\mu}(\theta) = 4\theta^2 \exp(-2\theta). \qquad (33)$$

Let also the function $f: \mathcal{M} \times \mathcal{X} \to \mathcal{Y}$ be

$$f(\theta, x) = x\theta, \qquad (34)$$

and the loss function $\ell$ in (2) be

$$\ell(f(\theta, x), y) = (x\theta - y)^2, \qquad (35)$$

which implies

$$\mathcal{L}_z(\theta) = (x\theta - y)^2, \qquad (36)$$
Lemma 4.2 shows that the sets $A_{Q,z}$ and $C_{Q,z}$ in (23a) are convex sets (intervals). Appendix T introduces some examples to illustrate particular cases in which the set $A_{Q,z}$ is open or semi-open. The convexity of $A_{Q,z}$ and $C_{Q,z}$ is crucial for analyzing how the choice of $\lambda$ influences whether the Type-II ERM-RER problem in (11) has a solution. For instance, if $\lambda \in A_{Q,z}$, then the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ is the unique solution to the problem in (11) (Theorem 3.1). Moreover, as $\lambda$ increases, the resulting Type-II ERM-RER problem still possesses a solution, which is formalized by the following corollary.

**Corollary 4.3.** If the Type-II ERM-RER problem in (11) possesses a solution, then, the following problem

$$ \min_{P \in \nabla_Q(\mathcal{M})} \mathbf{R}_z(P) + \alpha \mathbf{D}(Q \| P), \quad (34) $$

with $\alpha \ge \lambda$, also possesses a solution.

Additionally, Lemma 4.2 allows identifying how small $\lambda$ in (11) can be, such that the Type-II ERM-RER problem in (11) still possesses a solution. The regularization factor $\lambda$ can be made arbitrarily close to zero in some cases, as shown hereunder.

**Corollary 4.4.** If the set $\mathcal{M}$ is finite, then the set $A_{Q,z}$ in (23a) is $(0, \infty)$.

Corollary 4.4 follows by noticing that if the set $\mathcal{M}$ is finite, the subset $\mathcal{L}_{Q,z}^*$ in (30) satisfies $Q(\mathcal{L}_{Q,z}^*) > 0$. Thus, the integral in (33) is not finite, which follows from the fact that for all $\theta \in \mathcal{L}_{Q,z}^*$, $\mathbf{L}_z(\theta) - \delta_{Q,z}^* = 0$. Another immediate consequence of Lemma 4.1 and Lemma 4.2 is the following corollary.

**Corollary 4.5.** If the real value $\delta_{Q,z}^* = 0$, with $\delta_{Q,z}^*$ in (28), then the function $\bar{K}_{Q,z}$ in (23b) is strictly positive.

This section is closed by leveraging Lemma 4.2 for presenting a key property of the function $\bar{K}_{Q,z}$ in (23b).

**Lemma 4.6.** The function $\bar{K}_{Q,z}$ in (23) satisfies

$$ \lim_{\lambda \to \lambda_{Q,z}^* +} \bar{K}_{Q,z}(\lambda) = -\delta_{Q,z}^*, \quad (35) $$

where $\delta_{Q,z}^*$ and $\lambda_{Q,z}^*$ are defined in (28) and (29), respectively.

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

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

The limit in (35) is determined by the set of models in the support of the prior with the lowest empirical risk determined by the choice of the loss function $\ell$ and the function $f$ in (3).

# 5 Properties of the Solution

## 5.1 Bounds on the Radon-Nikodym Derivative

Note that from Theorem 3.1, models resulting in lower empirical risks correspond to greater values of the Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16). The
with the function $L_z$ defined in (3). Under the current assumptions the objective of this example is to show that $\mathcal{A} = [\delta_{Q,z}^*, \infty)$. For this purpose, it is sufficient to show that the inequality in (32) holds. From Theorem 4.1, it follows that $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies for all $\theta \in \text{supp } Q$,

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{d\mu}(\theta) = \frac{\lambda}{L_z(\theta) + \beta} 4\theta^2 \exp(-2\theta), \quad (37) $$

with $\beta$ satisfying (15). Thus,

$$ \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) = \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} 4\theta^2 \exp(-2\theta) d\mu(\theta) \quad (38a) $$

$$ = \int_{0}^{\infty} \frac{4\theta^2 \exp(-2\theta)}{(x\theta - y)^2 - \delta_{Q,z}^*} d\theta \quad (38b) $$

$$ = \int_{0}^{\infty} \frac{4\theta^2 \exp(-2\theta)}{\theta^2 - \delta_{Q,z}^*} d\theta \quad (38c) $$

$$ = \int_{0}^{\infty} \frac{4\theta^2 \exp(-2\theta)}{\theta^2} d\theta \quad (38d) $$

$$ = \int_{0}^{\infty} 4\exp(-2\theta) d\theta \quad (38e) $$

$$ = 2, \quad (38f) $$

where equality (38a) follows from equality (33); equality (38c) follows from the assumption that $(x, y) = (1, 0)$; and equality (38d) follows from the fact that $\delta_{Q,z}^* = 0$. Finally, the function $\bar{K}_{Q,z}$ in (23) satisfies $\bar{K}_{Q,z}(\frac{1}{2}) = 0$, which implies $\delta_{Q,z}^* = 0 \in \mathcal{A}$.

**Example 4.2.** Consider Example 4.1 with $z = (1, 1)$. Under the current assumptions, the objective of this example is to show that $\mathcal{A} = (\delta_{Q,z}^*, \infty)$. For this purpose, it is sufficient to show that the inequality in (32) does not hold:

$$ \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) = \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} 4\theta^2 \exp(-2\theta) d\mu(\theta) \quad (39a) $$

$$ = \int_{0}^{\infty} \frac{4\theta^2 \exp(-2\theta)}{(x\theta - y)^2 - \delta_{Q,z}^*} d\theta \quad (39b) $$

$$ = \int_{0}^{\infty} \frac{4\theta^2 \exp(-2\theta)}{(\theta - 1)^2} d\theta \quad (39c) $$

$$ = \infty. \quad (39d) $$

where equality (39a) follows from equality (33); equality (39b) follows from the assumption that $(x, y) = (1, 0)$; equality (39c) follows from the fact that $\delta_{Q,z}^* = 0$; and the equality (39d) follows from an algebraic development shown in Appendix T. Finally, the function $\bar{K}_{Q,z}$ in (23) is undefined at zero, which implies $\delta_{Q,z}^* = 0 \notin \mathcal{A}$.
following corollary formalizes this observation.

**Lemma 5.1.** For all $(\theta_1, \theta_2) \in (\text{supp } Q)^2$, such that $L_z(\theta_1) \le L_z(\theta_2)$, with $L_z$ in (3), the Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) satisfies

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta_2) \le \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta_1), \qquad (36) $$

with equality if and only if $L_z(\theta_1) = L_z(\theta_2)$.

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

The intuition that follows from Lemma 5.1 is that, under the assumption that the ERM problem in (4) possesses a solution in the support of the reference measure, the maximum of the function $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) is achieved by the models in $\mathcal{T}(z) \cap \text{supp } Q$, provided that it is not empty, with $\mathcal{T}(z)$ in (5). Furthermore, the Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ is monotonic with respect to the empirical risk $L_z$ in (3). This property is similar to that of the solution to the Type-I ERM-RER problem in (10), as established in [30, Corollary 1].

The Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) is always finite and strictly positive. This observation is formalized in the following lemma.

**Lemma 5.2.** The Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) satisfies for all $\theta \in \text{supp } Q$,

$$ 0 < \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \le \frac{\lambda}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} < \infty, \qquad (37) $$

where the function $\bar{K}_{Q,z}$ and the real $\delta_{Q,z}^*$ are defined in (23a) and (28), respectively. The equality holds if and only if $\theta \in \mathcal{L}_{Q,z}^* \cap \text{supp } Q$, with $\mathcal{L}_{Q,z}^*$ in (30).

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

## 5.2 Asymptotes of the Radon-Nikodym Derivative

In the asymptotic regime, when the regularization factor $\lambda$ in (11) grows to infinity, i.e., $\lambda \to \infty$, the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ becomes identical to the reference measure $Q$, up to sets of measure zero, as described in the following lemma.

**Lemma 5.3.** The Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) satisfies for all $\theta \in \text{supp } Q$,

$$ \lim_{\lambda \to \infty} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 1. \qquad (38) $$

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

Lemma 5.3 unveils a similarity between Type-I and Type-II regularization as the Type-I measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (10), also exhibits a similar behavior [30, Lemma 7].
The aforementioned examples demonstrate that even if the reference measure $Q$ and functions $\ell$ and $f$ in (3) are fixed, the set $\mathcal{A}$ might be either $[\delta_{Q,z}^*, \infty)$ or $(\delta_{Q,z}^*, \infty)$ depending on the dataset $z$. This observation underscores that the existence of the minimum regularization factor $\lambda^*$ is coupled on the specific choices of $Q$, $\ell$, $f$, and $z$. Finally, from Lemma 4.5 it is implied that if the set $\mathcal{M}$ is finite, then the set $\mathcal{A}$ is the open set $(-\delta_{Q,z}^*, \infty)$ in (31), as shown by the following example.

**Example 4.3.** Consider the Type-II ERM-RER problem in (11) and assume that: (a) $\mathcal{B}$ is a proper subset of $\mathcal{M}$, and (b) the probability measure $Q$ satisfies

$$Q(\mathcal{B}) = \epsilon, \quad \text{and} \tag{40a}$$

$$Q(\mathcal{M} \setminus \mathcal{B}) = 1 - \epsilon, \tag{40b}$$

with $\epsilon > 0$. Let the empirical risk function $\mathcal{L}_z$ in (3) be

$$\mathcal{L}_z(\theta) = \begin{cases} 0 & \text{if } \theta \in \mathcal{B} \\ c & \text{if } \theta \in \mathcal{M} \setminus \mathcal{B}, \end{cases} \tag{41}$$

with $c > 0$.

Under the current assumptions, the objective of this example is to show that for all $z \in (\mathcal{X} \times \mathcal{Y})^n$, it holds that $\mathcal{A} = (\delta_{Q,z}^*, \infty)$. For this purpose, it is sufficient to show that for all $c \in (0, \infty)$, the function $\bar{K}_{Q,z}$ in (23b) is strictly greater than $-\delta_{Q,z}^*$. From the current assumptions it follows that $\delta_{Q,z}^* = 0$ and that for all $\lambda \in (0, +\infty)$ the function $\bar{K}_{Q,z}$ in (23b) satisfies

$$\bar{K}_{Q,z}(\lambda) = -\frac{(c-\lambda)}{2} + \sqrt{\left(\frac{c-\lambda}{2}\right)^2 + \lambda c Q(\mathcal{B})}. \tag{42}$$

The proof of equality (42) is presented in appendix S. From equality (42), it holds that

$$\bar{K}_{Q,z}(\lambda) = -\frac{(c-\lambda)}{2} + \sqrt{\left(\frac{c-\lambda}{2}\right)^2 + \lambda c Q(\mathcal{B})} \tag{43a}$$

$$> -\frac{(c-\lambda)}{2} + \sqrt{\left(\frac{c-\lambda}{2}\right)^2} \tag{43b}$$

$$= -\frac{(c-\lambda)}{2} + \left|\frac{c-\lambda}{2}\right| \tag{43c}$$

$$\ge 0 \tag{43d}$$

$$= -\delta_{Q,z}^*, \tag{43e}$$

which proves that for all $c \in (0, \infty)$, $\mathcal{A} = (-\delta_{Q,z}^*, \infty)$.

Another immediate consequence of Lemma 4.4 is the following corollary.

**Corollary 4.7.** If the real value $\delta_{Q,z}^* = 0$, with $\delta_{Q,z}^*$ in (28), then the function $\bar{K}_{Q,z}$ in (23b) is strictly positive.
Alternatively, when the regularization factor decreases to zero from the right, i.e., $\lambda \to 0^+$, the Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) exhibits the following behavior.

**Lemma 5.4.** If $Q(\mathcal{L}_{Q,z}^*) > 0$, with the set $\mathcal{L}_{Q,z}^*$ in (30), then the Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) satisfies for all $\theta \in \text{supp } Q$,

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

On the other hand, if $Q(\mathcal{L}_{Q,z}^*) = 0$ and $\lambda_{Q,z}^*$ in (29) satisfies $\lambda_{Q,z}^* = 0$, then for all $\theta \in \text{supp } Q$, it holds that

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

Conversely, if $Q(\mathcal{L}_{Q,z}^*) = 0$ and $\lambda_{Q,z}^* > 0$, then for all $\theta \in \text{supp } Q$, it holds that

$$ \lim_{\lambda \to \lambda_{Q,z}^* +} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda_{Q,z}^*}{L_z(\theta) - \delta_{Q,z}^*}. \quad (41) $$

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

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

Lemma 5.4 highlights that in the asymptotic regime when the regularization factor decreases to zero from the right, i.e., $\lambda \to 0^+$, the value $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta)$ does not depend on the exact model $\theta$ but rather on whether $\theta \in \text{supp } Q \cap \mathcal{L}_{Q,z}^*$. In the case in which $\theta \in \text{supp } Q \cap \mathcal{L}_{Q,z}^*$, it holds that $\lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) > 0$. Otherwise, $\lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 0$. In the special case in which $\delta_{Q,z}^* = 0$, with $\delta_{Q,z}^*$ in (28), the set $\mathcal{L}_{Q,z}^*$ satisfies $\mathcal{L}_{Q,z}^* = \mathcal{T}(z)$, where $\mathcal{T}(z)$ is defined in (5). This implies a concentration of probability over $\mathcal{T}(z) \cap \text{supp } Q$, which establishes a connection with the ERM problem without regularization in (4).

Furthermore, in the asymptotic regime, when the regularization factor decreases to zero from the right, the solutions to the Type-I and Type-II ERM-RER problems exhibit the same asymptotic behavior, as shown in [30, Lemma 6]. This aligns with the observation that as $\lambda$ decreases, the optimization problems in (7) and (11) exhibit a weaker relative entropy constraint. A stronger result that follows from Lemma 5.4 is presented in the following lemma.

**Lemma 5.5.** If $\lambda_{Q,z}^*$ in (29) satisfies $\lambda_{Q,z}^* = 0$, then the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) and the set $\mathcal{L}_{Q,z}^*$ in (30) satisfy

$$ \lim_{\lambda \to 0^+} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) = 1. \quad (42) $$
The following lemma characterizes the limit of $\bar{K}_{Q,z}$ as $\lambda$ approaches zero from the right, under the assumption that the set $\mathcal{A}$ is $(-\delta_{Q,z}^*, \infty)$.

**Lemma 4.8.** If the set $\mathcal{A}$ is $(-\delta_{Q,z}^*, \infty)$, the function $\bar{K}_{Q,z}$ in (23b) satisfies

$$ \lim_{\lambda \to 0^+} \bar{K}_{Q,z}(\lambda) = -\delta_{Q,z}^*, \qquad (44) $$

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

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

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

Studying cases in which the choice of the reference measure $Q$, empirical risk function $L_z$ and dataset $z$ induce the set $\mathcal{A}$ to be equal $(-\delta_{Q,z}^*, \infty)$ is relevant in the context of learning algorithm, from the fact that if $\mathcal{M}$ is countable the set $\mathcal{A}$ is equal $(-\delta_{Q,z}^*, \infty)$. Furthermore, as the number of data points in datasets increases, choosing a prior $Q$ such that (32) is satisfied becomes less likely. Hence, in the paper, it will be assumed that $Q$, $L_z$ and $z$ induce $\mathcal{A} = (-\delta_{Q,z}^*, \infty)$ unless otherwise stated.

### 4.2.2 Bounds on the Radon-Nikodym Derivative

Note that from Theorem 4.1 models resulting in lower empirical risks correspond to greater values of the Radon-Nikodym derivative. The following corollary formalizes this observation.

**Lemma 4.9.** For all $(\theta_1, \theta_2) \in (\text{supp } Q)^2$, such that $L_z(\theta_1) \le L_z(\theta_2)$, with $L_z$ in (3), the Radon-Nikodym derivative in (16) satisfies

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta_2) \le \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta_1), \qquad (45) $$

with equality if and only if $L_z(\theta_1) = L_z(\theta_2)$.

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

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

The Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) is always finite and strictly positive. This observation is formalized in the following lemma.

**Lemma 4.10.** The Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) satisfies for all $\theta \in \text{supp } Q$

$$ 0 < \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \le \frac{\lambda}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} < \infty, \qquad (46) $$

where the equality holds if and only if $\theta \in \mathcal{L}_{Q,z}^* \cap \text{supp } Q$.

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

<figure><img src="image_6.png" /></figure>
Alternatively, if $\lambda_{Q,z}^* > 0$, then the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) and the set $\mathcal{L}_{Q,z}^*$ in (30) satisfy

$$ \lim_{\lambda \to \lambda_{Q,z}^*} + \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) = 0. \qquad (43) $$

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

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

Lemma 5.5 shows that indeed, if $\lambda_{Q,z}^* = 0$ and the regularization factor $\lambda$ approaches zero from the right, the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) concentrates on a set of models that induce minimum empirical risk, i.e., the set $\mathcal{L}_{Q,z}^*$ in (30).

# 6 The Expected Empirical Risk

This section focuses on the expected empirical risk induced by the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16). That is, the value $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$, with the functional $R_z$ defined in (6).

The following lemma establishes a relation between $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$, $\lambda$, and the function $\bar{K}_{Q,z}$ in (23b).

**Lemma 6.1.** The probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies

$$ R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = \lambda - \bar{K}_{Q,z}(\lambda), \qquad (44) $$

where the functional $R_z$ and the function $\bar{K}_{Q,z}$ are defined in (6) and (23b), respectively.

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

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

Lemma 6.1 characterizes the expected empirical risk of the Type-II ERM-RER solution and establishes a direct connection to the regularization factor $\lambda$. For example, from Lemma 4.6 if there exists a model $\theta^* \in \text{supp} Q$, such that its empirical risk is zero, the function $\bar{K}_{Q,z}$ is nonnegative, which implies that $\lambda$ serves as an explicit upper bound to the expected empirical risk. This provides a clear interpretation: the choice of $\lambda$ directly controls and bounds the average expected empirical risk. This property gives Type-II ERM-RER a distinct risk management strategy over that of Type-I ERM-RER, mainly lowering the expected empirical risk by appropriately choosing the value of $\lambda$. Additionally, Lemma 6.1 highlights that the expected empirical risk $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$, with $Q$ and $z$ fixed, inherits all properties of the function $\bar{K}_{Q,z}$ in (23b). The following lemma formalizes this observation.

**Lemma 6.2.** The expected empirical risk $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$, with the functional $R_z$ in (6) and the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16), is continuous and nondecreasing with
### 4.2.3 Asymptotes of the Radon-Nikodym Derivative

In the asymptotic regime, when the regularization factor grows to infinity, i.e., $\lambda \to \infty$, the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ becomes identical to the reference measure $Q$, as described in the following lemma.

**Lemma 4.11.** The Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) satisfies for all $\theta \in \text{supp } Q$,

$$ \lim_{\lambda \to \infty} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 1. \qquad (47) $$

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

Lemma 4.11 unveils a similarity between Type-I and Type-II regularization as the Type-I measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (9) exhibits a similar behavior [28].

In the asymptotic regime, when the regularization factor decreases to zero from the right, i.e., $\lambda \to 0^+$, the Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) exhibits the following behavior.

**Lemma 4.12.** If $Q(\mathcal{L}_{Q,z}^*) > 0$, with the set $\mathcal{L}_{Q,z}^*$ in (29), then the Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) satisfies for all $\theta \in \text{supp } Q$,

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

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

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

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

Lemma 4.12 highlights that in the asymptotic regime, when the regularization factor decreases to zero from the right, i.e., $\lambda \to 0^+$, the value $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta)$ does not depend on the exact model $\theta$ but rather on whether $\theta \in \text{supp } Q \cap \mathcal{L}_{Q,z}^*$. In the case in which $\theta \in \text{supp } Q \cap \mathcal{L}_{Q,z}^*$, it holds that $\lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) > 0$. Otherwise, $\lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 0$. In the special case in which $\delta_{Q,z}^* = 0$, with $\delta_{Q,z}^*$ in (28), the set $\mathcal{L}_{Q,z}^*$ satisfies $\mathcal{L}_{Q,z}^* = \mathcal{T}(z)$, where $\mathcal{T}(z)$ is defined in (5). This implies a concentration of probability over $\mathcal{T}(z) \cap \text{supp } Q$, which establishes a connection with the ERM problem without regularization in (4).

Furthermore, in the asymptotic regime, when the regularization factor decreases to zero from the right, the solutions to the Type-I and Type-II ERM-RER problems exhibit the same asymptotic behavior, as shown in [28]. This aligns with
respect to $\lambda$. Moreover, it is strictly increasing if and only if the empirical risk function $L_z$ in (3) is separable with respect to the probability measure $Q$.

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

## 6.1 Bounds on the Expected Empirical Risk

This section builds on the characterization of the expected empirical risk and its monotonicity with respect to the regularization factor $\lambda$ in (11) to establish a range of bounds on the expected empirical risk. The following lemma highlights a connection existing between the expected empirical risks $R_z(Q)$ and $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$; and the relative entropy $D(Q\|\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$.

**Lemma 6.3.** The functional $R_z$ defined in (6) and the measures $Q$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfy

$$R_z(Q) - R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \geq \lambda(\exp(D(Q\|\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})) - 1). \quad (45)$$

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

Note that $D(Q\|\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \geq 0$ in (45), which leads to the observation that

$$(\exp(D(Q\|\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})) - 1) \geq 0. \quad (46)$$

Hence, from Lemma 6.3, it follows that the solution to the Type-II ERM-RER problem induces an expected empirical risk that is smaller than the one induced by reference measure $Q$. This is formalized by the following corollary.

**Corollary 6.4.** The probability measures $Q$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfy

$$R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \leq R_z(Q), \quad (47)$$

where the functional $R_z$ is defined in (6) and equality holds if and only if the empirical risk function $L_z$ in (3) is nonseparable.

The following lemma presents a lower bound and an upper bound on the expected empirical risk $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ in which the regularization parameter plays a central role.

**Lemma 6.5.** The probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies

$$\delta_{Q,z}^* \leq R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) < \lambda + \delta_{Q,z}^*, \quad (48)$$

where the functional $R_z$ is defined in (6) and $\delta_{Q,z}^*$ is defined in (28). Moreover, the inequality on the left-hand side holds with equality if and only if the empirical risk function $L_z$ in (3) is nonseparable.
the observation that as $\lambda$ decreases, the optimization problems in (7) and (11) exhibit a weaker relative entropy constraint. A stronger result follows from Lemma 4.12 and is presented in the following lemma.

**Lemma 4.13.** The measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) and the set $\mathcal{L}_{Q,z}^*$ in (29) satisfy

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

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

Lemma 4.13 shows that indeed when the regularization factor approaches zero from the right, the probability of the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16), in the asymptotic regime, concentrates in the set of models that induce the minimum empirical risk in supp $Q$.

# 5 The Expected Empirical Risk

This section focuses on the expected empirical risk induced by the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16). Some important properties of the functional $R_z$ in (6) and the value $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ are introduced.

The expected empirical risk can be calculated in terms of the regularization parameter $\lambda$ and the function $\bar{K}_{Q,z}$ defined in (23b), as shown by the following lemma.

**Lemma 5.1.** The probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies

$$ R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = \lambda - \bar{K}_{Q,z}(\lambda), \qquad (51) $$

where the functional $R_z$, the function $\bar{K}_{Q,z}$ and the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ are defined in (6), (23b), and (26), respectively.

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

Lemma 5.1 highlights that the function $r: (0, \infty) \to [0, \infty)$ such that $r(\lambda) = R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$, with $Q$ and $z$ fixed, inherits all properties of the function $\bar{K}_{Q,z}$ in (23b). The following lemma formalizes this observation.

**Lemma 5.2.** The expected empirical risk $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$, with the functional $R_z$ in (6) and the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16), is nondecreasing with respect to $\lambda$. Moreover, it is strictly increasing if and only if the empirical risk function $L_z$ in (3) is separable with respect to the probability measure $Q$.

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

The following lemma highlights a connection existing between the expected empirical risks $R_z(Q)$ and $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$; and the relative entropy $D(Q||\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$.
Proof: The proof is presented in Appendix O.

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

The bounds presented in Lemma 6.5 highlight that the regularization parameter $\lambda$ in (11) governs the increase of the expected empirical risk $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ with respect to its minimum, i.e, $\delta_{Q,z}^*$ in (28). Moreover, the lower bound is tight for the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) in the asymptotic regime when $\lambda$ decreases to $\lambda_{Q,z}^*$ from right, as shown hereunder.

**Lemma 6.6.** The probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies

$$ \lim_{\lambda \to \lambda_{Q,z}^*} R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = \lambda_{Q,z}^* + \delta_{Q,z}^*, \quad (49) $$

where $\delta_{Q,z}^*$ is defined in (28) and the functional $R_z$ is defined in (6).

Proof: From Lemma 6.1, it holds that

$$ \lim_{\lambda \to \lambda_{Q,z}^*} R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = \lim_{\lambda \to \lambda_{Q,z}^*} \lambda - \lim_{\lambda \to \lambda_{Q,z}^*} \bar{K}_{Q,z}(\lambda) \quad (50) $$

$$ = \lambda_{Q,z}^* - \lim_{\lambda \to \lambda_{Q,z}^*} \bar{K}_{Q,z}(\lambda) \quad (51) $$

$$ = \lambda_{Q,z}^* + \delta_{Q,z}^*, \quad (52) $$

where equality (52) follows from Lemma 4.6. This completes the proof.

Finally, note that the functional $R_z$ in (6) is nonnegative. This observation together with Lemma 6.1 lead to a new property for the function $\bar{K}_{Q,z}$ in (23b), which is stated by the following corollary

**Corollary 6.7.** The function $\bar{K}_{Q,z}$ in (23b) satisfies, for all $t > \lambda_{Q,z}^*$, with $\lambda_{Q,z}^*$ in (29),

$$ \bar{K}_{Q,z}(t) \le t. \quad (53) $$

## 6.2 $(\delta, \epsilon)$-Optimality

This section presents a PAC guarantee for models sampled from the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16), with respect to the Type-II ERM-RER problem in (11). Such guarantee is presented using the notion of $(\delta, \epsilon)$-optimality introduced in [30, Definition 6].

**Definition 6.1** ([30, Definition 6]). Given a pair of positive reals $(\delta, \epsilon)$, with $\epsilon < 1$, the probability measure $P \in \Delta(\mathcal{M})$ is said to be $(\delta, \epsilon)$-optimal if the set $\mathcal{L}_z(\delta)$ in (27) satisfies

$$ P(\mathcal{L}_z(\delta)) > 1 - \epsilon. \quad (54) $$

The following theorem presents a $(\delta, \epsilon)$-optimality guarantee for the solution to the Type-II ERM-RER problem in (11).

**Theorem 6.1.** Assume that $\lambda_{Q,z}^* = 0$, then for all $(\delta, \epsilon) \in (\delta_{Q,z}^*, \infty) \times (0, 1)$, with $\delta_{Q,z}^*$ in (28), there always exists a $\lambda \in (0, \infty)$, such that the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) is $(\delta, \epsilon)$-optimal.
**Lemma 5.3.** The functional $R_z$ defined in (6) and the measures $Q$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfy

$$R_z(Q) - R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \geq \lambda(\exp(D(Q\|\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})) - 1). \quad (52)$$

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

Note that $D(Q\|\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \geq 0$, which leads to the observation that

$$(\exp(D(Q\|\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})) - 1) \geq 0, \quad (53)$$

in (52). Hence, from Lemma 5.3, it follows that the solution to the Type-II ERM-RER problem induces an expected empirical risk that is smaller than the one induced by reference measure $Q$. This is formalized by the following corollary.

**Corollary 5.4.** The probability measures $Q$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfy

$$R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \leq R_z(Q), \quad (54)$$

where the functional $R_z$ is defined in (6) and equality holds if and only if the empirical risk function $L_z$ in (3) is nonseparable.

The following lemma presents a lower bound and an upper bound on the expected empirical risk $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ in which the regularization parameter plays a central role.

**Lemma 5.5.** The probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies

$$\delta_{Q,z}^* \leq R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) < \lambda + \delta_{Q,z}^*, \quad (55)$$

where the functional $R_z$ is defined in (6) and $\delta_{Q,z}^*$ is defined in (28). Moreover, equality holds if and only if the empirical risk function $L_z$ in (3) is nonseparable.

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

The bounds presented in Lemma 5.5 highlight that the regularization parameter $\lambda$ in (11) governs the increase of the expected empirical risk $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ with respect to its minimum, i.e, $\delta_{Q,z}^*$ in (28). Moreover, the lower bound is tight for the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) in the asymptotic regime when $\lambda$ decreases to zero from right, as shown hereunder.

**Lemma 5.6.** The probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies

$$\lim_{\lambda \to 0^+} R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = \delta_{Q,z}^*, \quad (56)$$

where $\delta_{Q,z}^*$ is defined in (28) and the functional $R_z$ is defined in (6).
*Proof:* The proof is presented in Appendix P.

■

# 7 Interplay Between the Relative Entropy Asymmetry and the Empirical Risk

This section presents a connection between the Type-I ERM-RER in (7) and Type-II ERM-RER in (11) established via a transformation of the empirical risk function. The connection is established by proving the existence of two functions $W_{Q,z,\lambda}: \mathcal{M} \to \mathbb{R}$ and $V_{Q,z,\lambda}: \mathcal{M} \to \mathbb{R}$, such that the solution to the optimization problem in (7) is identical to the solution of the following problem:

$$ \min_{P \in \nabla_Q(\mathcal{M})} \int W_{Q,z,\lambda}(\theta) \, dP(\theta) + D(Q \| P), \quad (55) $$

with $\lambda$ and $Q$ in (7); and the solution to the optimization problem in (11) is identical to the solution of the following problem:

$$ \min_{P \in \Delta_Q(\mathcal{M})} \int V_{Q,z,\lambda}(\theta) \, dP(\theta) + D(P \| Q), \quad (56) $$

with $\lambda$ and $Q$ in (11). The main result of this section is presented in the following theorem.

**Theorem 7.1.** If the problems in (7) and in (11) have solutions, then

$$ \begin{aligned} & \min_{P \in \nabla_Q(\mathcal{M})} \int L_z(\theta) \, dP(\theta) + \lambda D(Q \| P) \\ & = \min_{P \in \Delta_Q(\mathcal{M})} \int V_{Q,z,\lambda}(\theta) \, dP(\theta) + D(P \| Q), \end{aligned} \quad (57a) $$

where the function $V_{Q,z,\lambda}: \mathcal{M} \to \mathbb{R}$ is defined as

$$ V_{Q,z,\lambda}(\theta) = \log(\bar{K}_{Q,z}(\lambda) + L_z(\theta)), \quad (57b) $$

and

$$ \begin{aligned} & \min_{P \in \Delta_Q(\mathcal{M})} \int L_z(\theta) \, dP(\theta) + \lambda D(P \| Q) \\ & = \min_{P \in \nabla_Q(\mathcal{M})} \int W_{Q,z,\lambda}(\theta) \, dP(\theta) + D(Q \| P), \end{aligned} \quad (58a) $$

where the function $W_{Q,z,\lambda}: \mathcal{M} \to \mathbb{R}$ is such that

$$ W_{Q,z,\lambda}(\theta) = \frac{\lambda}{\exp\left(-\frac{L_z(\theta)}{\lambda} - K_{Q,z}\left(-\frac{1}{\lambda}\right)\right)} - \bar{K}_{Q,z}(\lambda), \quad (58b) $$

where the functions $K_{Q,z}$ and $\bar{K}_{Q,z}$ are defined in (9) and (23), respectively.
*Proof:* From Lemma 5.1, it holds that

$$ \lim_{\lambda \to 0^+} \mathrm{R}_z \left( \bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \right) = \lim_{\lambda \to 0^+} \lambda - \lim_{\lambda \to 0^+} \bar{K}_{Q,z}(\lambda) \quad (57a) $$

$$ = - \lim_{\lambda \to 0^+} \bar{K}_{Q,z}(\lambda) \quad (57b) $$

$$ = \delta_{Q,z}^*, \quad (57c) $$

where equality (57c) follows from Lemma 4.8. This completes the proof. ■

Finally, note that the functional $\mathrm{R}_z$ in (6) is nonnegative. This observation together with Lemma 5.1 lead to a new property for the function $\bar{K}_{Q,z}$ in (23b), which is stated by the following corollary

**Corollary 5.7.** The function $\bar{K}_{Q,z}$ in (23b) satisfies, for all $t \in (0, \infty)$,

$$ \bar{K}_{Q,z}(t) \le t. \quad (58) $$

# 6 $(\delta, \epsilon)$-Optimality

This section presents a PAC guarantee of optimality for models sampled from the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) within the setting of the Type-II ERM-RER problem in (11). Such guarantee is presented using the notion of $(\delta, \epsilon)$-optimality introduced in [28].

**Definition 6.1** (($\delta, \epsilon$)-Optimality). Given a pair of positive reals $(\delta, \epsilon)$, with $\epsilon < 1$, the probability measure $P \in \Delta(\mathcal{M})$ is said to be $(\delta, \epsilon)$-optimal if the set $\mathcal{L}_z(\delta)$ in (27) satisfies

$$ P(\mathcal{L}_z(\delta)) > 1 - \epsilon. \quad (59) $$

The $(\delta, \epsilon)$-optimality guarantee ensures that with probability at least $1 - \epsilon$, sampling models from $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) yields models that induce empirical risks not greater than $\delta$. The following theorem presents an $(\delta, \epsilon)$-optimality guarantee for the Type-II ERM-RER solution.

**Theorem 6.1.** For all $(\delta, \epsilon) \in (\delta_{Q,z}^*, \infty) \times (0, 1)$, with $\delta_{Q,z}^*$ in (28), there always exists a $\lambda \in (0, \infty)$, such that the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) is $(\delta, \epsilon)$-optimal.

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

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

# 7 Interplay Between the Relative Entropy Asymmetry and the Empirical Risk

This section presents a connection between the Type-I ERM-RER in (7) and Type-II ERM-RER problems in (11) established via a transformation of the
Proof: Denote by $\hat{P}_{\Theta|Z=z}^{(Q,\lambda)}$ the solution to the optimization problem in (56). From Lemma 2.1, for all $\theta \in \text{supp } Q$, it follows that

$$ \frac{d\hat{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\exp(-V_{Q,z,\lambda}(\theta))}{\int \exp(-V_{Q,z,\lambda}(\nu)) dQ(\nu)} \quad (59) $$

$$ = \frac{\exp\left(\log\left(\frac{1}{L_z(\theta) + \bar{K}_{Q,z}(\lambda)}\right)\right)}{\int \exp\left(\log\left(\frac{1}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)}\right)\right) dQ(\nu)} \quad (60) $$

$$ = \frac{\left( \int \frac{1}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1}}{L_z(\theta) + \bar{K}_{Q,z}(\lambda)} \quad (61) $$

$$ = \frac{\bar{K}_{Q,z}^{-1}(\beta)}{L_z(\theta) + \bar{K}_{Q,z}(\lambda)} \quad (62) $$

$$ = \frac{\lambda}{L_z(\theta) + \bar{K}_{Q,z}(\lambda)} \quad (63) $$

$$ = \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta), \quad (64) $$

where (60) follows from (57b); (62) follows from (26); (63) follows from (23b); and (64) follows from Theorem 3.1. This completes the proof of (58a).

Similarly, denote by $\tilde{P}_{\Theta|Z=z}^{(Q,\lambda)}$ the solution to the optimization problem in (55). From Theorem 3.1, for all $\theta \in \text{supp } Q$, it follows that

$$ \frac{d\tilde{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda}{W_{Q,z,\lambda}(\theta) + \bar{K}_{Q,z}(\lambda)} \quad (65) $$

$$ = \frac{\lambda}{\exp\left(-\frac{\lambda}{L_z(\theta)} - K_{Q,z}(\frac{1}{\lambda})\right) - \bar{K}_{Q,z}(\lambda) + \bar{K}_{Q,z}(\lambda)} \quad (66) $$

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

$$ = \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta), \quad (68) $$

where (65) follows from (24); (66) follows from (58b); and (68) follows from Lemma 2.1. This completes the proof of (57a). ■

Theorem 7.1 establishes an equivalence between the regularization of Type-I and Type-II. More specifically, Theorem 7.1 highlights that by modifying the empirical risk function $L_z$ in (57b) using the function $V_{Q,z,\lambda}$ in (57b), the Type-II ERM-RER problem in (11) can be solved by solving the Type-I ERM-RER problem in (56). It is noteworthy that Type-I regularization imposes the support of the solution to be contained within the support of the reference measure, i.e., $\text{supp } P_{\Theta|Z=z}^{(Q,\lambda)} \subseteq \text{supp } Q$. Similarly, Type-II regularization imposes the support
empirical risk function. The transformation used is termed log-empirical risk and is defined hereunder.

**Definition 7.1** (Log-Empirical Risk). Consider the empirical risk function Lz in (3) and let the function Vz,λ: M → R, with Q and λ in (11), be such that

$$V_{z,\lambda}(\theta) \triangleq \log(\bar{K}_{Q,z}(\lambda) + L_z(\theta)), \quad (60)$$

with the function $\bar{K}_{Q,z}$ defined in (23b). The value $V_{z,\lambda}(\theta)$ is said to be the log-empirical risk induced by the model $\theta \in M$.

The notion of log-empirical risk in (60) leads to the expected log-empirical risk, which is denoted as follows.

**Definition 7.2** (Expected Log-Empirical Risk). Consider the log-empirical risk function $V_{z,\lambda}$ in (60) and let the functional $\bar{R}_{z,Q,\lambda}: \Delta(M) \to \mathbb{R}$ be such that for all probability measures $P \in \Delta(M)$, it holds that

$$\bar{R}_{z,Q,\lambda}(P) \triangleq \int V_{z,\lambda}(\theta) dP(\theta). \quad (61)$$

The value $\bar{R}_{z,Q,\lambda}(P)$ is the expected log-empirical risk induced by the measure P.

## 7.1 The Connection between Type-I and Type-II

Using the objects defined above, a new Type-I ERM-RER problem is presented:

$$\min_{P \in \Delta_Q(M)} \bar{R}_{z,Q,\lambda}(P) + D(P \| Q), \quad (62)$$

with $\lambda$ and $Q$ being problems of the Type-I and Type-II ERM-RER problems in (7) and (11). The main result of this section is presented in the following theorem.

**Theorem 7.1.** The solution to the optimization problem in (62) is unique and identical to the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16).

*Proof:* Denote by $\hat{P}_{\Theta|Z=z}^{(Q,\lambda)}$ the solution to the optimization problem in (62). From Lemma 3.1, for all $\theta \in \text{supp} Q$, it follows that

$$\frac{d\hat{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\exp(-V_{z,\lambda}(\theta))}{\int \exp(-V_{z,\lambda}(\nu)) dQ(\nu)} \quad (63a)$$

$$= \frac{\exp\left(\log\left(\frac{1}{L_z(\theta) + \bar{K}_{Q,z}(\lambda)}\right)\right)}{\int \exp\left(\log\left(\frac{1}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)}\right)\right) dQ(\nu)} \quad (63b)$$

$$= \frac{\left( \int \frac{1}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1}}{L_z(\theta) + \bar{K}_{Q,z}(\lambda)} \quad (63c)$$
of the solution to contain the support of the reference measure, i.e., supp $Q \subseteq$ supp $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$. Interestingly, these inclusions can be shown to be equalities from Theorem 3.1 and Lemma 2.1. That is,

$$ \mathrm{supp} P_{\Theta|Z=z}^{(Q,\lambda)} = \mathrm{supp} Q = \mathrm{supp} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}. \quad (69) $$

The remainder of the section focuses on the transformation from Type-I to Type-II. The function $V_{Q,z,\lambda}$ in (57b) is referred to as the *log-empirical risk* function. The *expected log-empirical risk* is defined as follows.

**Definition 7.1** (Expected Log-Empirical Risk). Given the dataset $z \in (\mathcal{X} \times \mathcal{Y})^n$ in (1) and the log-empirical risk function $V_{Q,z,\lambda}$ in (57b), let the functional $\bar{R}_{Q,z,\lambda} : \Delta(\mathcal{M}) \to \mathbb{R}$ be such that

$$ \bar{R}_{Q,z,\lambda}(P) = \int V_{Q,z,\lambda}(\boldsymbol{\theta}) \, dP(\boldsymbol{\theta}). \quad (70) $$

The value $\bar{R}_{Q,z,\lambda}(P)$ is the *expected log-empirical risk* induced by the measure $P$.

Using the *expected log-empirical risk* defined above, the optimization problem in (55) can be rewritten as follows

$$ \min_{P \in \Delta_Q(\mathcal{M})} \bar{R}_{Q,z,\lambda}(P) + D(P \| Q), \quad (71) $$

with $\lambda$ and $Q$ being parameters of the Type-I and Type-II ERM-RER problems in (7) and (11). The Type-I - Type-II relation in Theorem 7.1 can be used to establish an equality involving the relative entropies $D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ and $D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q)$; and the expected log-empirical risks $\bar{R}_{Q,z,\lambda}(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ and $\bar{R}_{Q,z,\lambda}(Q)$, as shown hereunder.

**Lemma 7.1.** The functional $\bar{R}_{Q,z,\lambda}$ in (70) and the probability measures $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ in (16) satisfy

$$ \log(\lambda) = \bar{R}_{Q,z,\lambda}(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) + D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \quad (72) $$

$$ = \bar{R}_{Q,z,\lambda}(Q) - D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}). \quad (73) $$

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

## 7.1 Sensitivity of the Log-Empirical Risk

The sensitivity of the expected empirical risk, as presented in [30, Definition 7], is defined as follows.

**Definition 7.2** (Sensitivity of the Expected Empirical Risk). Consider the functional $\mathbb{R}_z$ in (6) and let $S_{Q,\lambda} : (\mathcal{X} \times \mathcal{Y})^n \times \Delta_Q(\mathcal{M}) \to \mathbb{R}$ be a functional such that

$$ S_{Q,\lambda}(z, P) = \mathbb{R}_z(P) - \mathbb{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)}), \quad (74) $$
$$ = \frac{\lambda}{\mathbf{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)} \qquad (63d) $$

$$ = \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}), \qquad (63e) $$

where the equality in (63b) follows from the definition of log-empirical risk in (60); the equality in (63d) follows from (23b) and (15b); and the equality in (63e) follows from Theorem 4.1, which completes the proof. ■

Theorem 7.1 establishes an equivalence between the regularization of Type-I and Type-II. More specifically, Theorem 7.1 highlights that by transforming the empirical risk function $L_z$ in (60) into the log-empirical risk $V_{z,\lambda}$ in (60), the Type-II ERM-RER problem in (11) can be solved by solving the Type-I ERM-RER problem in (62). In view of this, it is interesting to note that Type-I regularization forces the support of the solution to be included into the support of the reference measure as a consequence of the optimization domain $\Delta_Q(\mathcal{M})$. Hence, $\mathrm{supp} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \subseteq \mathrm{supp} Q$. Moreover, as a consequence of the solution, all the models in the support of the reference measure are in the support of the solution. That is, $\mathrm{supp} Q \subseteq \mathrm{supp} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$. Alternatively, Type-II regularization forces the support of the solution to be included into the support of the reference measure as a consequence of the optimization domain $\nabla_Q(\mathcal{M})$. Hence, $\mathrm{supp} Q \subseteq \mathrm{supp} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$. Moreover, as a consequence of the solution, all the models in the support of the solution are in the support of the reference measure. That is, $\mathrm{supp} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \subseteq \mathrm{supp} Q$. Hence, $\mathrm{supp} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)} = \mathrm{supp} Q$, regardless of whether the regularization is of Type-I or Type-II.

Finally, the Type-I - Type-II relation can be used to establish an equality involving the relative entropies $D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ and $D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q)$; and the expected log-empirical risks $\bar{R}_{z,Q,\lambda}(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ and $\bar{R}_{z,Q,\lambda}(Q)$, as shown hereunder.

**Lemma 7.1.** The functional $\bar{R}_{z,Q,\lambda}$ in (61) and the probability measures $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ in (16) satisfy

$$ \bar{R}_{z,Q,\lambda}(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) + D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q) = \log(\lambda), \qquad (64) $$

and

$$ \bar{R}_{z,Q,\lambda}(Q) - D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = \log(\lambda). \qquad (65) $$

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

## 7.2 Sensitivity of the Log-Empirical Risk

The sensitivity of the expected empirical risk, as presented in [28, Definition 10.1], is defined as follows.
where the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is defined in (10). The sensitivity of the expected empirical risk $\mathbb{R}_z$ due to a deviation from $P_{\Theta|Z=z}^{(Q,\lambda)}$ to $P$ is $S_{Q,z}(z, P)$.

Similarly, the sensitivity of the expected log-empirical risk $V_{Q,z,\lambda}$ in (57b) is defined as follows.

**Definition 7.3** (Sensitivity of the Expected Log-Empirical Risk). Consider the functional $\bar{\mathbb{R}}_{Q,z,\lambda}$ in (70) and let $\bar{S}_{Q,\lambda} : (\mathcal{X} \times \mathcal{Y})^n \times \bigtriangledown_Q(\mathcal{M}) \to \mathbb{R}$ be a functional such that

$$ \bar{S}_{Q,\lambda}(z, P) = \bar{\mathbb{R}}_{Q,z,\lambda}(P) - \bar{\mathbb{R}}_{Q,z,\lambda} \left( \bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)} \right), \quad (75) $$

where the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ is in (16). The sensitivity of the expected log-empirical risk due to a deviation from $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ to $P$ is $\bar{S}_{Q,\lambda}(z, P)$.

The sensitivity of the expected log-empirical risk due to a deviation from $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ to $P$ is described by the following closed-form expression.

**Lemma 7.2.** The sensitivity $\bar{S}_{Q,\lambda}$ in (75) satisfies for all probability measures $P \in \mathcal{O}_Q(\mathcal{M})$ that

$$ \bar{S}_{Q,\lambda}(z, P) = D(P \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) - D(P \| Q) + D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q), \quad (76) $$

where the probability measures $Q$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ are defined in (16).

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

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

An interesting interpretation of Lemma 7.2 follows from rewriting (76) using the objective function of the Type-I ERM-RER problem in (56) as follows:

$$ \begin{aligned} & D(P \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \\ & = \bar{\mathbb{R}}_{Q,z,\lambda}(P) - \bar{\mathbb{R}}_{Q,z,\lambda} \left( \bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)} \right) + D(P \| Q) - D(\bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)} \| Q). \end{aligned} \quad (77) $$

That is, the relative entropy $D(P \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ represents the variation of the objective function of the Type-I ERM-RER problem in (56) due to a deviation from the solution $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ to an alternative probability measure $P$.

In Lemma 7.2, when $P$ is chosen to be identical to the reference measure $Q$, it follows that

$$ \bar{S}_{Q,\lambda}(z, Q) = D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) + D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q), \quad (78) $$

where the right-hand side is a Jeffreys divergence [51], also known as the symmetrized Kullback-Leibler divergence between the measures $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$. Furthermore, by observing that $D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \ge 0$, and $D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \ge 0$ [30, Theorem 1], Lemma 7.2 leads to the following corollary.
**Definition 7.3** (Sensitivity of the Expected Empirical Risk). Consider the functional $\mathbb{R}_z$ defined in (6) and let $S_{Q,\lambda} : (\mathcal{X} \times \mathcal{Y})^n \times \bigtriangleup_Q(\mathcal{M}) \to \mathbb{R}$ be a functional such that

$$S_{Q,\lambda}(z, P) = \mathbb{R}_z(P) - \mathbb{R}_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right), \quad (66)$$

where the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is in (9). The sensitivity of the expected empirical risk due to a deviation from $P_{\Theta|Z=z}^{(Q,\lambda)}$ to $P$ is $S_{Q,\lambda}(z, P)$.

Following the same idea, the sensitivity of the expected log-empirical risk is defined as follows.

**Definition 7.4** (Sensitivity of the Expected Log-Empirical Risk). Consider the functional $\bar{\mathbb{R}}_{z,Q,\lambda}$ in (61) and let $\bar{S}_{Q,\lambda} : (\mathcal{X} \times \mathcal{Y})^n \times \bigtriangleup_Q(\mathcal{M}) \to \mathbb{R}$ be a functional such that

$$\bar{S}_{Q,\lambda}(z, P) = \bar{\mathbb{R}}_{z,Q,\lambda}(P) - \bar{\mathbb{R}}_{z,Q,\lambda}\left(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}\right), \quad (67)$$

where the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ is in (16). The sensitivity of the expected log-empirical risk due to a deviation from $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ to $P$ is $\bar{S}_{Q,\lambda}(z, P)$.

The sensitivity of the expected log-empirical risk due to a deviation from $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ to $P$ exhibits the following closed-form expression.

**Lemma 7.2.** The sensitivity $\bar{S}_{Q,\lambda}$ in (67) satisfies for all probability measures $P \in \mathcal{O}_Q(\mathcal{M})$ that

$$\bar{S}_{Q,\lambda}(z, P) = \mathrm{D}\left(P \Vert \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}\right) - \mathrm{D}\left(P \Vert Q\right) + \mathrm{D}\left(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \Vert Q\right), \quad (68)$$

where the probability measures $Q$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ are defined in (16).

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

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

An interesting interpretation of Lemma 7.2 follows from rewriting (68) using the objective function of the Type-I ERM-RER problem in (62) as follows:

$$\mathrm{D}\left(P \Vert \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}\right) = \bar{\mathbb{R}}_{z,Q,\lambda}(P) + \mathrm{D}\left(P \Vert Q\right) - \bar{\mathbb{R}}_{z,Q,\lambda}\left(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}\right) \\ - \mathrm{D}\left(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \Vert Q\right). \quad (69)$$

That is, the relative entropy $\mathrm{D}\left(P \Vert \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}\right)$ represents the variation of the objective function of the Type-I ERM-RER problem in (62) due to a deviation from the solution $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ to an alternative probability measure $P$.

In Lemma 7.2, when $P$ is chosen to be identical to the reference measure $Q$, it follows that

$$\bar{S}_{Q,\lambda}(z, Q) = \mathrm{D}\left(Q \Vert \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}\right) + \mathrm{D}\left(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \Vert Q\right), \quad (70)$$
**Corollary 7.3.** The probability measures $Q$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfy

$$ \bar{R}_{Q,z,\lambda}(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \leq \bar{R}_{Q,z,\lambda}(Q), \qquad (79) $$

where the functional $\bar{R}_{Q,z,\lambda}$ is defined in (70).

## 7.2 Type-I and Type-II Optimal Measures

The solutions to the optimization problems (7) and (11), with regularization factors $\lambda$ and $\alpha$, respectively, are $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $\bar{P}_{\Theta|Z=z}^{(Q,\alpha)}$ in (10) and in (16). These measures exhibit the following property.

**Lemma 7.4.** The probability measures $P_{\Theta|Z=z}^{(Q,\lambda)}$ and $\bar{P}_{\Theta|Z=z}^{(Q,\alpha)}$ in (10) and in (16), respectively, satisfy

$$ D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) - D(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)} \| Q) = \log(\alpha) + K_{Q,z} \left(-\frac{1}{\lambda}\right), \qquad (80) $$

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

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

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

Lemma 7.4 characterizes the relative entropy difference of Type-I and Type-II ERM-RER solution with respect to the prior $Q$. In doing so, it provides an alternative way to evaluate this difference without directly computing the corresponding relative entropies.

Finally, two important properties of the Type-I and Type-II optimal measures are presented by the following corollary of Lemma 7.4.

**Corollary 7.5.** The probability measures $P_{\Theta|Z=z}^{(Q,\alpha)}$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (10) and in (16), respectively, satisfy

$$ \bar{S}_{Q,\alpha}(z, P_{\Theta|Z=z}^{(Q,\lambda)}) = D(P_{\Theta|Z=z}^{(Q,\alpha)} \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) - \left(\log(\alpha) + K_{Q,z}\left(-\frac{1}{\lambda}\right)\right) \quad (81) $$

and

$$ \frac{1}{\lambda} S_{Q,\lambda}(z, \bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) = D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{(Q,\alpha)}) + \log(\alpha) + K_{Q,z} \left(-\frac{1}{\lambda}\right), \quad (82) $$

where the functionals $S_{Q,\lambda}$ and $\bar{S}_{Q,\alpha}$ are respectively defined in (74) and in (75); and the function $K_{Q,z}$ is defined in (9).

The equality in (81) quantifies the variation of the expected log-empirical risk due to a deviation from the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (10) to the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\alpha)}$ in (16) via the sensitivity $\bar{S}_{Q,\alpha}(z, P_{\Theta|Z=z}^{(Q,\lambda)})$. The equality in (82) quantifies the variation of the expected empirical risk due to a deviation from the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (10) via the sensitivity $S_{Q,\lambda}(z, \bar{P}_{\Theta|Z=z}^{(Q,\alpha)})$.
where the right-hand side is a Jeffrey's divergence, also known as the symmetrized Kullback-Liebler divergence, between the measures $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$. Furthermore, by observing that $D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}||Q) \ge 0$, and $D(Q||\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \ge 0$, Lemma 7.2 leads to the following corollary.

**Corollary 7.3.** The probability measures $Q$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfy

$$ \bar{R}_{z,Q,\lambda}(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \le \bar{R}_{z,Q,\lambda}(Q), \quad (71) $$

where the functional $\bar{R}_{z,Q,\lambda}$ is defined in (61).

## 7.3 Type-I and Type-II Optimal Measures

The probability measures $P_{\Theta|Z=z}^{(Q,\alpha)}$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (9) and in (16), respectively, exhibit the following property.

**Lemma 7.4.** The probability measures $P_{\Theta|Z=z}^{(Q,\alpha)}$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (9) and in (16), respectively, satisfy

$$ D(P_{\Theta|Z=z}^{(Q,\lambda)}||Q) - D(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)}||Q) = \log(\alpha) + K_{Q,z}\left(-\frac{1}{\lambda}\right), \quad (72) $$

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

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

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

Finally, two important properties of the Type-I and Type-II optimal measures are presented. The first one quantifies the variation of the expected log-empirical risk due to a deviation from the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (9) to the probability measure $P_{\Theta|Z=z}^{(Q,\alpha)}$ in (16) via the sensitivity $\bar{S}_{Q,\alpha}(z, P_{\Theta|Z=z}^{(Q,\lambda)})$. The second result quantifies the variation of the expected empirical risk due to a deviation from the probability measure $P_{\Theta|Z=z}^{(Q,\alpha)}$ in (16) to the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (9) via the sensitivity $S_{Q,\alpha}(z, \bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$.

**Corollary 7.5.** The probability measures $P_{\Theta|Z=z}^{(Q,\alpha)}$ and $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (9) and in (16), respectively, satisfy

$$ \bar{S}_{Q,\alpha}(z, P_{\Theta|Z=z}^{(Q,\lambda)}) = D(P_{\Theta|Z=z}^{(Q,\alpha)}||\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) - \left(\log(\alpha) + K_{Q,z}\left(-\frac{1}{\lambda}\right)\right) \quad (73) $$

and

$$ \frac{1}{\lambda}S_{Q,\lambda}(z, \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}||P_{\Theta|Z=z}^{(Q,\alpha)}) + \log(\alpha) + K_{Q,z}\left(-\frac{1}{\lambda}\right), \quad (74) $$

where the functionals $S_{Q,\lambda}$ and $\bar{S}_{Q,\alpha}$ are respectively defined in (66) and in (67); and the function $K_{Q,z}$ is defined in (10).
## 7.3 Numerical Comparison of Type-I and Type-II Regularization

In machine learning, the generalization error describes the capacity of a learning algorithm to select models based on training data that performs well with unseen test data. The sensitivity (Definition 7.2) of the optimization problem in (7) is closely related to the generalization error [30, Theorem 16]. See also [31, 52]. A probability measure $P \in \Delta_Q(M)$, e.g., a machine learning algorithm, that yields larger sensitivity indicates that the learning overfits with respect to the training data, leading to an increase in the generalization error [52]. In this context, algorithms arising from the Type-I and Type-II ERM-RER are used for the classification of two handwritten numbers from the MNIST dataset [53]. The MNIST example is simplified to accommodate a parameterized model in $\mathbb{R}^2$ such that the numerical approximations of the generalization error for different regularization factors are meaningful [37].

The MNIST dataset consists of 60,000 images for training and 10,000 images for testing. Out of the 60,000 training images, 12,183 are labeled as the digits six and seven, while 1,986 out of the 10,000 test images correspond to these digits. Each image is a 28 x 28 grayscale picture and is represented by a matrix in $[0, 1]^{28 \times 28}$. To reduce the computational complexity, the pictures are processed following the procedure described in Appendix U. Consider the Type-I ERM-RER problem in (7) and the Type-II ERM-RER problem in (11) and assume that: (i) the set of models is $M = [-50, 50]^2$; (ii) the set of patterns $\mathcal{X}$ is formed by computing the histogram of gradients (HOG) of the pictures such that $\mathcal{X} \subset \mathbb{R}^{1296}$ of the handwritten six and seven in the MNIST dataset; (iii) the set of labels is $\mathcal{Y} = \{6, 7\}$; (iv) the reference measure $Q$ is chosen to be a uniform probability measure over the set of models; (v) the function $f$ in (3) is defined as

$$f(\theta, x) = \begin{cases} 6 & \text{if } 0 < (xW)\theta, \\ 7 & \text{if } 0 > (xW)\theta, \end{cases} \qquad (83)$$

where the matrix $W$ is defined in (354) in Appendix U; and (vi) the loss function $\ell$ in (2) satisfies

$$\ell(f(\theta, x), y) = 1_{\{f(\theta, x) \neq y\}}. \qquad (84)$$

For the simulation, 8,100 data points are uniformly sampled from the 12,183 available training images, forming the dataset $z_1$, referred to as the training dataset. Similarly, 1,300 data points are uniformly sampled from the 1,986 available test images, forming the dataset $z_2$, referred to as the test dataset. Not all images are used because the simulation is repeated only 100 times, and at each iteration, the datasets $z_1$ and $z_2$ are uniformly resampled. Figure 5 displays the average (over 100 repetitions) generalization gap for Type-I and Type-II algorithms. The average generalization gap of Type-II suggests it is less prone to overfitting. In contrast, Figure 3 and Figure 4 show that Type-I
# 8 Final Remarks

This work has introduced the Type-II ERM-RER problem and has presented its solution through Theorem 4.1. The solution highlights that regardless of the direction in which relative entropy is used as a regularizer, the models that are considered by the solution are necessarily in the support of the reference measure. In that sense, the restriction over the models introduced by the reference measure cannot be bypassed by the training data when relative entropy is used as the regularizer. This limitation has been shown to be a consequence of the equivalence that can be established between Type-I and Type-II regularization. Remarkably, the direction of the relative entropy regularizer can be switched by a logarithmic transformation of the risk. The mutual absolute continuity of both Type-I and Type-II ERM-RER solutions relative to the reference measure can be understood in light of the equivalence between both types of regularization. The analytical results have also enabled us to provide an operationally meaningful characterization of the expected empirical risk induced by the Type-II solution in terms of the regularization parameters. This, in turn, reduces the computational burden of bounding the expected empirical risk. Moreover, the insight provided by the bounds on the expected empirical risk can be distilled into guidelines for selecting the regularization parameter.
<figure><img src="image_10.png" /><figcaption>Figure 1: 28 × 28 Image of a handwritten 6
from MNIST dataset.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 2: 28 × 28 Image of a handwritten 7
from MNIST dataset.</figcaption></figure>

achieves a lower average training error, which results on a lower average test error. These observations imply that Type-II promotes a more positive conservative learning, reducing the generalization gap by keeping average training and testing error closer, while Type-I achieves lower training error at the cost of a higher average generalization gap, indicating greater reliance on the training data.

Another key observation is that, for certain ranges of the regularization factor (e.g.,$\lambda \in (0.002, 0.09)$) and $\lambda \in (0.3, 0.8)$ for Type-II), where the average test error are comparable, Type-II exhibits lower average generalization gap. This suggests that Type-II can achieve both small test error and generalization error for certain regularization factor, a highly desirable outcome. However, selecting such regularization ranges remains an open question for future research under the theoretical framework presented in this paper.
A Proof of Lemma 4.1

*Proof:* The optimization problem in (11) can be re-written in terms of the Radon-Nikodym derivative of the optimization measure *P* with respect to the measure *Q*, which yields:

$$
\begin{equation}
\begin{split}
\min_{P \in \mathcal{O}_Q(\mathcal{M})} & \int \mathbf{L}_z(\boldsymbol{\theta}) \frac{dP}{d\mathcal{Q}}(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) \\
& + \lambda \int \frac{dQ}{dP}(\boldsymbol{\theta}) \log \left( \frac{dQ}{dP}(\boldsymbol{\theta}) \right) \, dP(\boldsymbol{\theta}),
\end{split}
\tag{75a}
\end{equation}
$$

$$
\text{s.t.} \quad \int \frac{dP}{dQ}(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}) = 1. \tag{75b}
$$

The remainder of the proof focuses on the problem in which the optimization
is over the function $\frac{dP}{dQ} : \mathcal{M} \to \mathbb{R}$, instead of optimizing the measure $P$. This
is due to the fact that for all $P \in \mathcal{O}_Q(\mathcal{M})$, the Radon-Nikodym derivate $\frac{dP}{dQ}$
is unique up to sets of zero measure with respect to $Q$. Let $\mathcal{M}$ be the set of
measurable functions $\mathcal{M} \to \mathbb{R}$ with respect to the measurable spaces $(\mathcal{M}, \mathcal{F})$
and $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$ that are absolutely integrable with respect to $Q$. That is, for all
$\hat{g} \in \mathcal{M}$, it holds that

$$
\int |\hat{g}(\theta)| \, dQ(\theta) < \infty. \tag{76}
$$

Hence, the optimization problem of interest is:

$$
\min_{g \in \mathcal{M}} \int \mathbf{L}_z(\boldsymbol{\theta}) g(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) - \lambda \int \log(g(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \quad (77\text{a})
$$

$$
\text{s.t.} \quad \int g(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) = 1. \tag{77b}
$$

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

$$
\begin{align}
L(g, \beta) &= \int \mathbf{L}_z(\boldsymbol{\theta}) g(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) - \lambda \int \log(g(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \nonumber \\
&\quad + \beta \left( \int g(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) - 1 \right) \tag{78}
\end{align}
$$

$$
= \int (g(\boldsymbol{\theta})(\mathbf{L}_z(\boldsymbol{\theta}) + \beta) - \lambda \log(g(\boldsymbol{\theta}))) \, dQ(\boldsymbol{\theta}) - \beta, \quad (79)
$$

where $\beta$ is a real that acts as a Lagrange multiplier due to the constraint (77b).
Let $\hat{g}: \mathcal{M} \to \mathbb{R}$ be a function in $\mathcal{M}$. The Gateaux differential of the functional
$L$ in (78) at $(g, \beta) \in \mathcal{M} \times \mathbb{R}$ in the direction of $\hat{g}$, if it exists, is

$$
\partial L(g, \beta; \hat{g}) \triangleq \frac{d}{d\gamma} L(g + \gamma \hat{g}, \beta) \Big|_{\gamma=0} . \quad (80)
$$

The proof continues under the assumption that the function *g* and *ĝ* are such
that the Gateaux differential in (80) exists. Under such an assumption, let
<figure><img src="image_12.png" /><figcaption>Figure 3: Average Training Error: average of the expected empirical risks $R_{z_1}(P_{\Theta|Z=z_1}^{(Q,\lambda)})$ and $R_{z_1}(\bar{P}_{\Theta|Z=z_1}^{(Q,\lambda)})$, with the measures $P_{\Theta|Z=z_1}^{(Q,\lambda)}$ and $\bar{P}_{\Theta|Z=z_1}^{(Q,\lambda)}$ in (10) and (16), respectively, computed over one hundred different $z_1$ (training dataset) random selections.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 4: Average Test Error: average of the expected empirical risks $R_{z_2}(P_{\Theta|Z=z_1}^{(Q,\lambda)})$ and $R_{z_2}(\bar{P}_{\Theta|Z=z_1}^{(Q,\lambda)})$, with the measures $P_{\Theta|Z=z_1}^{(Q,\lambda)}$ and $\bar{P}_{\Theta|Z=z_1}^{(Q,\lambda)}$ in (10) and (16), respectively, computed over one hundred different $z_1$ (training dataset) and $z_2$ (test dataset) random selections.</figcaption></figure>
the function $r: \mathbb{R} \to \mathbb{R}$ satisfy for all $\gamma \in (-\epsilon, \epsilon)$, with $\epsilon$ arbitrarily small, that

$$r(\gamma) = L(g + \gamma \hat{g}, \beta) \qquad (81)$$

$$= \int \mathbf{L}_z(\boldsymbol{\theta})(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) - \lambda \int \log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \\ + \beta \left( \int (g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) - 1 \right) \qquad (82)$$

$$=-\beta + \int g(\boldsymbol{\theta})(\mathbf{L}_z(\boldsymbol{\theta}) + \beta) \, dQ(\boldsymbol{\theta}) + \gamma \int \hat{g}(\boldsymbol{\theta})(\mathbf{L}_z(\boldsymbol{\theta}) + \beta) \, dQ(\boldsymbol{\theta}) \\ + \lambda \int \log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}), \qquad (83)$$

where the last equality is simply an algebraic re-arrangement of terms. From the assumption that the function $g$ and $\hat{g}$ are such that the Gateauz differential in (80) exists, it follows that the function $r$ in (81) is differentiable at zero. Note that the first two terms in (83) are independent of $\gamma$; the third term is linear with $\gamma$; and the fourth term can be written using the function $\hat{r}: \mathbb{R} \to \mathbb{R}$ such that for all $\gamma \in (-\epsilon, \epsilon)$, with $\epsilon$ arbitrarily small, satisfies

$$\hat{r}(\gamma) = -\lambda \int \log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}). \qquad (84)$$

Under the same assumption, it follows that the function $\hat{r}$ in (84) is differentiable at zero. That is, the limit

$$\lim_{\delta \to 0} \frac{1}{\delta}(\hat{r}(\gamma + \delta) - \hat{r}(\gamma)) \qquad (85)$$

exists for all $\gamma \in (-\epsilon, \epsilon)$, with $\epsilon$ arbitrarily small. The proof of the existence of such a limit relies on the fact that $\log$ is strictly concave and continuous. This implies that $-\log$ is also Lipschitz continuous, which implies that for all $\boldsymbol{\theta} \in \mathcal{M}$ and for all $\gamma \in (-\epsilon, \epsilon)$, with $\epsilon > 0$ arbitrarily small, it holds that

$$|\log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) - \log(g(\boldsymbol{\theta}) + (\gamma + \delta)\hat{g}(\boldsymbol{\theta}))| \le c |\hat{g}(\boldsymbol{\theta})\delta|, \qquad (86)$$

with $\delta > 0$, for some constant $c$ positive and finite, which implies that

$$\left| \frac{\log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) - \log(g(\boldsymbol{\theta}) + (\gamma + \delta) \hat{g}(\boldsymbol{\theta}))}{\delta} \right| \le c |\hat{g}(\boldsymbol{\theta})|. \qquad (87)$$

Using these arguments, the limit in (85) satisfies for all $\gamma \in (-\epsilon, \epsilon)$, with $\epsilon > 0$ arbitrarily small, that

$$\lim_{\delta \to 0} \frac{1}{\delta}(\hat{r}(\gamma + \delta) - \hat{r}(\gamma)) = \lambda \lim_{\delta \to 0} \frac{1}{\delta} \left( \int \log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) - \int \log(g(\boldsymbol{\theta}) + (\gamma + \delta) \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \right) \qquad (88)$$
<figure><img src="image_14.png" /><figcaption>Figure 5: Average of the differences (generalization gaps) $R_{z_2}(P_{\Theta|Z=z_1}^{(Q,\lambda)}) - R_{z_1}(P_{\Theta|Z=z_1}^{(Q,\lambda)})$ and $R_{z_2}(\bar{P}_{\Theta|Z=z_1}^{(Q,\lambda)}) - R_{z_1}(\bar{P}_{\Theta|Z=z_1}^{(Q,\lambda)})$, with the measures $P_{\Theta|Z=z_1}^{(Q,\lambda)}$ and $\bar{P}_{\Theta|Z=z_1}^{(Q,\lambda)}$ in (10) and (16), respectively, computed over one hundred different $z_1$ (training dataset) and $z_2$ (test dataset) random selections.</figcaption></figure>
$$ =\lambda \lim_{\delta \to 0} \int \frac{\log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta}))}{\delta} - \frac{\log(g(\boldsymbol{\theta}) + (\gamma + \delta)\hat{g}(\boldsymbol{\theta}))}{\delta} \, dQ(\boldsymbol{\theta}) \quad (89) $$

$$ =\lambda \int \frac{d}{d\gamma} \log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \quad (90) $$

$$ <\infty, \quad (91) $$

where both the equality in (90) and the inequality in (91) follow from noticing that the conditions for the dominated convergence theorem hold [45, Theorem 1.6.9], namely:

* For all $\gamma \in (-\epsilon, \epsilon)$, with $\epsilon > 0$, the inequality in (87) holds;

* The function $\hat{g}$ in (87) satisfies the inequality in (76); and

* For all $\boldsymbol{\theta} \in \mathcal{M}$ and for all $\gamma \in (-\epsilon, \epsilon)$, with $\epsilon > 0$ arbitrarily small, it holds that

$$ \lim_{\delta \to 0} \frac{\log(g(\boldsymbol{\theta}) + (\gamma + \delta)\hat{g}(\boldsymbol{\theta})) - \log(g(\boldsymbol{\theta}) + \gamma\hat{g}(\boldsymbol{\theta}))}{\delta} = \frac{d}{d\gamma} \log(g(\boldsymbol{\theta}) + \gamma\hat{g}(\boldsymbol{\theta})) \quad (92) $$

$$ = \frac{\hat{g}(\boldsymbol{\theta})}{(g(\boldsymbol{\theta}) + \gamma\hat{g}(\boldsymbol{\theta}))}, \quad (93) $$

which follows from the fact that $\log$ is differentiable.

Hence, the derivative of the real function $r$ in (83) is

$$ \frac{d}{d\gamma} r(\gamma) = \int \hat{g}(\boldsymbol{\theta}) (\mathbf{L}_z(\boldsymbol{\theta}) + \beta) dQ(\boldsymbol{\theta}) - \lambda \int \frac{\hat{g}(\boldsymbol{\theta})}{(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta}))} dQ(\boldsymbol{\theta}) \quad (94) $$

$$ = \int \hat{g}(\boldsymbol{\theta}) \left( \mathbf{L}_z(\boldsymbol{\theta}) + \beta - \frac{\lambda}{(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta}))} \right) dQ(\boldsymbol{\theta}). \quad (95) $$

From (80) and (95), it follows that

$$ \partial L(g, \beta; \hat{g}) = \int \hat{g}(\boldsymbol{\theta}) \left( \mathbf{L}_z(\boldsymbol{\theta}) + \beta - \frac{\lambda}{g(\boldsymbol{\theta})} \right) dQ(\boldsymbol{\theta}). \quad (96) $$

The relevance of the Gateaux differential in (96) stems from [46, Theorem 1, page 178], which unveils the fact that a necessary condition for the functional $L$ in (78) to have a stationary point at $\left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}, \beta \right) \in \mathcal{M} \times [0, \infty)$ is that for all functions $\hat{g} \in \mathcal{M}$,

$$ \partial L \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}, \beta; \hat{g} \right) = 0. \quad (97) $$
# 8 Final Remarks

This work has introduced the Type-II ERM-RER problem and has presented its solution through Theorem 3.1. The solution highlights that regardless of whether Type-I or Type-II regularization is used in ERM problems, the models that are considered by the resulting solution are necessarily in the support of the reference measure. In this sense, the restriction over the models introduced by the reference measure cannot be bypassed by the training data when relative entropy is used as the regularizer. This limitation has been shown to be a consequence of the equivalence that can be established between Type-I and Type-II regularization. These analytical results lead to an operationally meaningful characterization of the expected empirical risk induced by the Type-II solution in terms of the regularization parameters. The closed-form expressions for the expected empirical risk induced by Type-I and Type-II errors are used to characterize the sensitivity of the expected empirical risk and the sensitivity of the expected log-empirical risk, in terms of the cumulant generating function and Kullback-Leibler divergence. The analysis of the solution to the optimization problem (11) shows that, under mild assumptions, there always exists a positive real value $\lambda$ such, with probability $1 - \epsilon$, the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ concentrates on the set of models that minimize the empirical risk.

# Appendices

## A Preliminary

This appendix introduces a preliminary result, which is central in the proof of Lemma 3.1.

**Lemma A.1.** Let $\mathcal{M}$ be the set of measurable functions $h: \mathcal{M} \to \mathbb{R}$, with respect to the measurable space $(\mathcal{M}, \mathcal{F})$ and $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$. Let $\mathcal{S}$ be the subset of $\mathcal{M}$ including all nonnegative functions that are absolutely integrable with respect to a probability measure $Q$. That is, for all $h \in \mathcal{S}$, it holds that

$$ \int |h(\boldsymbol{\theta})| \mathrm{d}Q(\boldsymbol{\theta}) < \infty. \qquad (85) $$

Let the function $\hat{r}: \mathbb{R} \to \mathbb{R}$ be such that

$$ \hat{r}(\alpha) = \int -\log(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta})) \mathrm{d}Q(\boldsymbol{\theta}), \qquad (86) $$

for some functions $g$ and $h$ in $\mathcal{S}$. The function $\hat{r}$ in (86) is differentiable at zero.

*Proof:* The objective is to prove that the function $\hat{r}$ in (86) is differentiable at
From (96) and (97), it follows that $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ must satisfy for all functions $\hat{g}$ in $\mathcal{M}$ that

$$ \int \hat{g}(\theta) \left( \mathbf{L}_z(\theta) + \beta - \lambda \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right)^{-1} \right) dQ(\theta) = 0. \quad (98) $$

This implies that for all $\theta \in \text{supp } Q$,

$$ \mathbf{L}_z(\theta) + \beta - \lambda \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right)^{-1} = 0, \quad (99) $$

and thus,

$$ \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda}{\beta + \mathbf{L}_z(\theta)}, \quad (100) $$

where $\beta$ is chosen to satisfy (77b) and guarantee that for all $\theta \in \text{supp } Q$, it holds that $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \in (0, \infty)$. That is,

$$ \beta \in \left\{ t \in \mathbb{R} : \forall \theta \in \text{supp } Q, 0 < \frac{\lambda}{t + \mathbf{L}_z(\theta)} \right\}, \quad \text{and} \quad (101) $$

$$ 1 = \int \frac{\lambda}{\mathbf{L}_z(\theta) + \beta} dQ(\theta). \quad (102) $$

which is an assumption of the theorem.

The proof continues by verifying that the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ that satisfies (100) is the unique solution to the optimization problem in (75). Such verification is done by showing that the objective function in (75) is strictly convex with the optimization variable. Let $P_1$ and $P_2$ be two different probability measures in $(\mathcal{M}, \mathcal{F})$ and let $\alpha$ be in $(0, 1)$. Hence,

$$ \mathbf{R}_z(\alpha P_1 + (1 - \alpha) P_2) + \lambda \mathbf{D}(\alpha P_1 + (1 - \alpha) P_2 \| Q) \quad (103) $$

$$ = \mathbf{R}_z(\alpha P_1) + \mathbf{R}_z((1 - \alpha) P_2) + \lambda \mathbf{D}(\alpha P_1 + (1 - \alpha) P_2 \| Q) \quad (104) $$

$$ > \mathbf{R}_z(\alpha P_1) + \mathbf{R}_z((1 - \alpha) P_2) + \lambda \mathbf{D}(\alpha P_1 \| Q) + \lambda \mathbf{D}((1 - \alpha) P_2 \| Q) \quad (105) $$

$$ (106) $$

where the functional $\mathbf{R}_z$ is defined in (6). The equality above follows from the properties of the Lebesgue integral, while the inequality follows from [28, Theorem 2.2., page 1]. This proves that the solution is unique due to the strict concavity of the objective function, which completes the proof. ■
zero, which reduces to proving that the limit

$$ \lim_{\delta \to 0} \frac{1}{\delta}(\hat{r}(\alpha + \delta) - \hat{r}(\alpha)) \qquad (87) $$

exists for all $\alpha \in (-\epsilon, \epsilon)$, with $\epsilon > 0$ arbitrarily small. Let the function $f: (0, \infty) \to \mathbb{R}$ be a function such that

$$ f(x) = -\log(x). \qquad (88) $$

Note that the function $\hat{r}$ can be written in terms of $f$ as follows:

$$ \hat{r}(\alpha) = \int f(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}). \qquad (89) $$

The proof of the existence of such limit in (87) relies on the fact that the function $f$ in (88) is strictly convex and differentiable, which implies that $f$ is also Lipschitz continuous. Hence, it follows that for all $\boldsymbol{\theta} \in \text{supp } Q$,

$$ |f(g(\boldsymbol{\theta}) + (\alpha + \delta)h(\boldsymbol{\theta})) - f(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta}))| \le c|h(\boldsymbol{\theta})| |\delta|, \qquad (90) $$

for some positive and finite constant $c$, which implies that

$$ \frac{|f(g(\boldsymbol{\theta}) + (\alpha + \delta)h(\boldsymbol{\theta})) - f(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta}))|}{|\delta|} \le c|h(\boldsymbol{\theta})|, \qquad (91) $$

and thus, given that $h \in \mathcal{S}$, it holds that

$$ \int \frac{|f(g(\boldsymbol{\theta}) + (\alpha + \delta)h(\boldsymbol{\theta})) - f(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta}))|}{|\delta|} dQ(\boldsymbol{\theta}) \le \infty. \qquad (92) $$

This facilitates using the dominated convergence theorem as follows. From the fact that the function $f$ is differentiable, the limit in (87) satisfies for $\alpha \in (-\epsilon, \epsilon)$, with $\epsilon > 0$ arbitrarily small,

$$ \begin{align} & \lim_{\delta \to 0} \frac{1}{\delta}(\hat{r}(\alpha + \delta) - \hat{r}(\alpha)) \notag \\ &= \lim_{\delta \to 0} \frac{1}{\delta} \left( \int f(g(\boldsymbol{\theta}) + (\alpha + \delta)h(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) - \int f(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) \right) \tag{93a} \\ &= \lim_{\delta \to 0} \int \frac{1}{\delta} (f(g(\boldsymbol{\theta}) + (\alpha + \delta)h(\boldsymbol{\theta})) - f(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta}))) dQ(\boldsymbol{\theta}) \tag{93b} \\ &\le \lim_{\delta \to 0} \int \frac{1}{|\delta|} |f(g(\boldsymbol{\theta}) + (\alpha + \delta)h(\boldsymbol{\theta})) - f(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta}))| dQ(\boldsymbol{\theta}) \tag{93c} \\ &= \int \lim_{\delta \to 0} \frac{1}{|\delta|} |f(g(\boldsymbol{\theta}) + (\alpha + \delta)h(\boldsymbol{\theta})) - f(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta}))| dQ(\boldsymbol{\theta}) \tag{93d} \\ &= c \int h(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}) \tag{93e} \\ &< \infty, \tag{93f} \end{align} $$

where (93c) follows from [54, Theorem 1.5.9(c)]; (93d) follows from the dominated convergence theorem [54, Theorem 1.6.9]; (93e) follows from (91); and (93f) follows from (85). Finally, from (93f), it follows that the function $\hat{r}$ in (86) is differentiable at zero, which completes the proof. ■
## B Proof of Lemma 4.2

*Proof:* Given a probability measure $V \in \nabla_Q(\mathcal{M})$, with $\nabla_Q(\mathcal{M})$ in (12), let $V_0$ and $V_1$ be two probability measures on the measurable space $(\mathcal{M}, \mathcal{F})$ such that for all $A \in \mathcal{F}$, it holds that

$$V_0(A) = \frac{V(A \setminus \text{supp } Q)}{V(M \setminus \text{supp } Q)}, \qquad (107a)$$

and

$$V_1(A) = \frac{V(A \cap \text{supp } Q)}{V(M \cap \text{supp } Q)}. \qquad (107b)$$

Let the real value $\alpha$ be

$$\alpha = V(M \cap \text{supp } Q). \qquad (108)$$

Hence, for all $A \in \mathcal{F}$ the measure $V$ satisfies that

$$V(A) = (1 - \alpha)V_0(A) + \alpha V_1(A). \qquad (109)$$

Moreover, from (109) it holds that: i) If $V(A) = 0$, then $V_0(A) = 0$, which implies that $V_0$ is absolutely continuous with respect to $V$; ii) If $V(A) = 0$, then $V_1(A) = 0$, which implies that $V_1$ is absolutely continuous with respect to $V$. Furthermore, from the definition of $\nabla_Q(\mathcal{M})$ in (12) the probability measure $V$ is absolutely continuous with respect to $Q$. Hence, for all $A \in \mathcal{F}$, it follows that

$$Q(A) = \int_A dQ(\theta) \qquad (110)$$

$$= \int_A \frac{dQ}{dV}(\theta) dV(\theta) \qquad (111)$$

$$= \int_A \frac{dQ}{dV}(\theta) d((1 - \alpha)V_0 + \alpha V_1)(\theta) \qquad (112)$$

$$= (1 - \alpha) \int_A \frac{dQ}{dV}(\theta) dV_0(\theta) + \alpha \int_A \frac{dQ}{dV}(\theta) dV_1(\theta) \qquad (113)$$

$$= \int_A \alpha \frac{dQ}{dV}(\theta) dV_1(\theta). \qquad (114)$$

Hence, from (114) and the Radon-Nikodym Theorem in [45, Theorem 2.2.1, page 65] the probability measure $Q$ is absolutely continuous with respect to $V_1$. This implies that for all $A \in \mathcal{F}$, it holds that

$$Q(A) = \int \frac{dQ}{dV_1}(\theta) dV_1(\theta), \qquad (115)$$

where, for all $\theta \in \text{supp } V$,

$$\frac{dQ}{dV_1}(\theta) = \alpha \frac{dQ}{dV}(\theta). \qquad (116)$$
B Proof of Lemma 3.1

The optimization problem in (18) can be re-written in terms of the Radon-
Nikodym derivative of the optimization measure P with respect to the measure
Q, which yields:

$$
\min_{P \in \mathcal{O}_Q(\mathcal{M})} \int \mathbf{L}_z(\boldsymbol{\theta}) \frac{\mathrm{d}P}{\mathrm{d}Q}(\boldsymbol{\theta}) \, \mathrm{d}Q(\boldsymbol{\theta}) - \lambda \int \log\left(\frac{\mathrm{d}P}{\mathrm{d}Q}(\boldsymbol{\theta})\right) \, \mathrm{d}Q(\boldsymbol{\theta}), \quad (94\text{a})
$$

$$
\text{s.t.} \quad \int \frac{dP}{dQ}(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) = 1. \tag{94b}
$$

The remainder of the proof focuses on the problem in which the optimization
is over the function $\frac{dP}{dQ} : \mathcal{M} \to \mathbb{R}$, instead of the measure $P$. This is due to
the fact that for all $P \in \mathcal{O}_Q(\mathcal{M})$, the Radon-Nikodym derivate $\frac{dP}{dQ}$ is unique
up to sets of zero measure with respect to $Q$ [54, Theorem 2.2.1]. Let $\mathcal{S}$ be
the set defined in Lemma A.1. Using this notation, the optimization problem
of interest is:

$$
\min_{g \in \mathcal{S}} \int \mathbf{L}_z(\boldsymbol{\theta}) g(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) - \lambda \int \log(g(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \quad (95\text{a})
$$

$$
\text{s.t.} \quad \int g(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) = 1. \tag{95b}
$$

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

$$
\begin{align}
L(g, \beta) &= \int \mathbf{L}_z(\boldsymbol{\theta}) g(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) - \lambda \int \log(g(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \nonumber \\
&\quad + \beta \left( \int g(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) - 1 \right) \tag{96}
\end{align}
$$

$$
= \int (g(\boldsymbol{\theta})(\mathbf{L}_z(\boldsymbol{\theta}) + \beta) - \lambda \log(g(\boldsymbol{\theta}))) dQ(\boldsymbol{\theta}) - \beta, \quad (97)
$$

where $\beta$ is a real that acts as a Lagrange multiplier due to the constraint (95b).
Let $\hat{g}: \mathcal{M} \to \mathbb{R}$ be a function in $\mathcal{S}$. The Gateaux differential of the functional
$L$ in (96) at $(g, \beta) \in \mathcal{S} \times \mathbb{R}$ in the direction of $\hat{g}$ is

$$
\partial L(g, \beta; \hat{g}) \triangleq \frac{d}{d\gamma} L(g + \gamma \hat{g}, \beta) \Big|_{\gamma=0}. \quad (98)
$$

Let the function $r: \mathbb{R} \to \mathbb{R}$ be defined for some fixed functions $g$ and $\hat{g}$ and some fixed $\beta$ such that for all $\gamma \in (-\epsilon, \epsilon)$, with $\epsilon$ arbitrarily small,

$$
r(\gamma) = L(g + \gamma \hat{g}, \beta). \tag{99}
$$

The proof follows by showing that the function $r$ in (99) is differentiable at
zero, in order to prove the existence of the Gateaux differential in (98) for those
functions $g$ and $\hat{g}$ and real $\beta$. For doing so, note that

$$
r(\gamma) = \int \mathbf{L}_z(\boldsymbol{\theta})(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) - \lambda \int \log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta})
$$
From (116), the following holds:

$$D(Q||V) = \int \log\left(\frac{dQ}{dV}(\boldsymbol{\theta})\right) dQ(\boldsymbol{\theta}) \qquad (117a)$$

$$= \int \log\left(\frac{1}{\alpha} \frac{dQ}{dV_1}(\boldsymbol{\theta})\right) dQ(\boldsymbol{\theta}) \qquad (117b)$$

$$= \int \log\left(\frac{dQ}{dV_1}(\boldsymbol{\theta})\right) dQ(\boldsymbol{\theta}) - \int \log(\alpha) dQ(\boldsymbol{\theta}) \qquad (117c)$$

$$= D(Q||V_1) - \log(\alpha). \qquad (117d)$$

From (117) it follows that

$$R_z(V) + \lambda D(Q||V) = R_z((1-\alpha)V_0 + \alpha V_1) + \lambda D(Q||V_1) - \lambda \log(\alpha) \qquad (118a)$$

$$= (1-\alpha)R_z(V_0) + \alpha R_z(V_1) + \lambda D(Q||V_1) \qquad (118b)$$

$$\geq \alpha R_z(V_1) + \lambda D(Q||V_1) - \lambda \log(\alpha), \qquad (118c)$$

with equality if and only if $\alpha = 1$, which implies that for all $A \in \mathcal{F}$, it holds that

$$V(A) = V_1(A) \qquad (119a)$$

$$= V(A \cap \text{supp } Q), \qquad (119b)$$

where the equality in (119b) follows from (107b). This implies that the equality in (118c) holds if and only if

$$\text{supp } Q = \text{supp } V, \qquad (120)$$

which implies that the equality in (118c) holds if and only if the measure $V$ is mutually absolutely continuous with respect to the reference measure $Q$. Finally, the above leads to

$$\min_{P \in \nabla_Q(M) \setminus \bigcup_Q(M)} R_z(P) + \lambda D(Q||P) > \min_{P \in \nabla_Q(M)} R_z(P) + \lambda D(Q||P), \qquad (121)$$

which completes the proof.

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

## C Proof of Lemma 4.4

*Proof:* The properties of the function $\bar{K}_{Q,z}$ in (23b), for which an explicit expression is unknown, are proven by studying the functional inverse and the continuous inverse theorem [47, Theorem 5.6]. Hence, the proof is divided into two parts. The first part introduces the functional inverse of the function $\bar{K}_{Q,z}$ in (23b) and properties. The second part proves the continuity of the function
$$ 
\begin{aligned}
&+ \beta \left( \int (g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) - 1 \right) && (100a) \\
&= \gamma \int \hat{g}(\boldsymbol{\theta}) (\mathbf{L}_z(\boldsymbol{\theta}) + \beta) \, dQ(\boldsymbol{\theta}) - \lambda \int \log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \\
&+ \int g(\boldsymbol{\theta}) (\mathbf{L}_z(\boldsymbol{\theta}) + \beta) \, dQ(\boldsymbol{\theta}) - \beta, && (100b)
\end{aligned}
$$

where the first term in (100b) is linear with respect to $\gamma$ and the third term is independent of $\gamma$. The second term can be written using the function $\hat{r}: \mathbb{R} \to \mathbb{R}$, which is defined for fixed functions $g$ and $\hat{g}$ as follows

$$ \hat{r}(\gamma) = - \int \log(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}), \quad (101) $$

and is verified to be differentiable at zero in Lemma A.1. This implies that

$$ r(\gamma) = \gamma \int \hat{g}(\boldsymbol{\theta}) (\mathbf{L}_z(\boldsymbol{\theta}) + \beta) \, dQ(\boldsymbol{\theta}) + \lambda \hat{r}(\gamma) + \int g(\boldsymbol{\theta}) (\mathbf{L}_z(\boldsymbol{\theta}) + \beta) \, dQ(\boldsymbol{\theta}) - (\mathbf{I}\mathbf{I}\mathbf{I}\mathbf{I}\mathbf{I}\mathbf{I}\mathbf{I}\mathbf{I}) $$

which verifies that the function $r$ in (99) is differentiable at zero and more importantly, verifies that the Gateaux differential $\partial L(g, \beta; \hat{g})$ in (98) exists.

The proof proceeds by calculating the Gateaux differential $\partial L(g, \beta; \hat{g})$ in (98), which requires calculating the derivative of the real function $r$ in (99). That is,

$$ \frac{d}{d\gamma} r(\gamma) = \int \hat{g}(\boldsymbol{\theta}) (\mathbf{L}_z(\boldsymbol{\theta}) + \beta) \, dQ(\boldsymbol{\theta}) - \lambda \int \frac{\hat{g}(\boldsymbol{\theta})}{(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta}))} \, dQ(\boldsymbol{\theta}) \quad (103) $$

$$ = \int \hat{g}(\boldsymbol{\theta}) \left( \mathbf{L}_z(\boldsymbol{\theta}) + \beta - \frac{\lambda}{(g(\boldsymbol{\theta}) + \gamma \hat{g}(\boldsymbol{\theta}))} \right) dQ(\boldsymbol{\theta}). \quad (104) $$

From (98) and (104), it follows that

$$ \partial L(g, \beta; \hat{g}) = \int \hat{g}(\boldsymbol{\theta}) \left( \mathbf{L}_z(\boldsymbol{\theta}) + \beta - \frac{\lambda}{g(\boldsymbol{\theta})} \right) dQ(\boldsymbol{\theta}). \quad (105) $$

The relevance of the Gateaux differential in (105) stems from [55, Theorem 1, page 178], which unveils the fact that a necessary condition for the functional $L$ in (96) to have a stationary point at $\left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}, \beta \right) \in \mathcal{M} \times [0, \infty)$ is that for all functions $\hat{g} \in \mathcal{S}$,

$$ \partial L \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}, \beta; \hat{g} \right) = 0. \quad (106) $$

From (105) and (106), it follows that $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ must satisfy for all functions $\hat{g}$ in $\mathcal{S}$ that

$$ \int \hat{g}(\boldsymbol{\theta}) \left( \mathbf{L}_z(\boldsymbol{\theta}) + \beta - \lambda \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) \right)^{-1} \right) dQ(\boldsymbol{\theta}) = 0. \quad (107) $$

Inria
$\bar{K}_{Q,z}$ in (23b) is proved using its functional inverse via the continuous inverse theorem [47, Theorem 5.6]

The first part is as follows. For $\bar{K}_{Q,z}$ defined in (23), assume that $t \in (0, \infty)$ and $\gamma \in \mathcal{A}$, with $\mathcal{A}$ defined in (23a) satisfy that

$$ \bar{K}_{Q,z}(t) = \gamma, \qquad (122) $$

which implies that

$$ 1 = \int \frac{d\bar{P}^{(Q,t)}_{\Theta|Z=z}(\theta)}{dQ} dQ(\theta) \qquad (123a) $$

$$ = \int \frac{t}{L_z(\theta) + \gamma} dQ(\theta). \qquad (123b) $$

Let the function $\bar{K}_{Q,z}^{-1}: \mathcal{A} \to (0, \infty)$ be the functional inverse of $\bar{K}_{Q,z}$ in (23b) given by

$$ \bar{K}_{Q,z}^{-1}(\gamma) = \frac{1}{\int \frac{1}{L_z(\theta) + \gamma} dQ(\theta)}, \qquad (124) $$

which follows from the constraint in (123) and the equality in (122).

From (123) and the fact that $t \in (0, \infty)$, it holds that

$$ 0 < \int \frac{1}{L_z(\theta) + \gamma} dQ(\theta) < \infty, \qquad (125) $$

which implies that for all $\gamma \in \mathcal{A}$, with $\mathcal{A}$ in (23a), the function $\bar{K}_{Q,z}^{-1}$ in (124) satisfies

$$ \infty > \bar{K}_{Q,z}^{-1}(\gamma) > 0. \qquad (126) $$

Note that from (125), for all $(\gamma_1, \gamma_2) \in \mathcal{A}^2$, such that $\gamma_1 < \gamma_2$, for all $\theta \in \text{supp } Q$ it holds that

$$ \frac{1}{L_z(\theta) + \gamma_1} > \frac{1}{L_z(\theta) + \gamma_2}, \qquad (127) $$

which implies that

$$ \int \frac{1}{L_z(\theta) + \gamma_1} dQ(\theta) > \int \frac{1}{L_z(\theta) + \gamma_2} dQ(\theta). \qquad (128) $$

Therefore, from equality (124) and inequality (128) for all $(\gamma_1, \gamma_2) \in \mathcal{A}^2$, such that $\gamma_1 < \gamma_2$, the function $\bar{K}_{Q,z}^{-1}$ in (124) satisfies

$$ \bar{K}_{Q,z}^{-1}(\gamma_1) < \bar{K}_{Q,z}^{-1}(\gamma_2), \qquad (129) $$
This implies that for all $\theta \in \text{supp } Q$,

$$L_z(\theta) + \beta - \lambda \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right)^{-1} = 0, \quad (108)$$

and thus,

$$\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda}{\beta + L_z(\theta)}, \quad (109)$$

where $\beta$ is chosen to satisfy (95b) and guarantee that for all $\theta \in \text{supp } Q$, it holds that $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \in (0, \infty)$. That is,

$$\beta \in \left\{ t \in \mathbb{R} : \forall \theta \in \text{supp } Q, 0 < \frac{\lambda}{t + L_z(\theta)} \right\}, \quad \text{and} \quad (110)$$

$$1 = \int \frac{\lambda}{L_z(\theta) + \beta} dQ(\theta), \quad (111)$$

which is an assumption of the theorem.

The proof continues by verifying that the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ that satisfies (109) is the unique solution to the optimization problem in (94). Such verification is done by showing that the objective function in (94) is strictly convex with the optimization variable. Let $P_1$ and $P_2$ be two different probability measures in $(\mathcal{M}, \mathcal{F})$ and let $\alpha$ be in $(0, 1)$. Hence,

$$\begin{aligned} & R_z(\alpha P_1 + (1-\alpha)P_2) + \lambda \mathrm{D}(\alpha P_1 + (1-\alpha)P_2 \| Q) \\ &= R_z(\alpha P_1) + R_z((1-\alpha)P_2) + \lambda \mathrm{D}(\alpha P_1 + (1-\alpha)P_2 \| Q) \end{aligned} \quad (112)$$

$$> \alpha R_z(P_1) + (1-\alpha)R_z(P_2) + \lambda(\alpha \mathrm{D}(P_1 \| Q) + (1-\alpha)\mathrm{D}(P_2 \| Q)), \quad (113)$$

where the functional $R_z$ is defined in (6). The equality above follows from the properties of the Lebesgue integral, while the inequality follows from [30, Theorem 2]. This proves that the solution is unique due to the strict concavity of the objective function, which completes the proof. ■

## C Proof of Lemma 3.2

Given a probability measure $V \in \nabla_Q(\mathcal{M})$, with $\nabla_Q(\mathcal{M})$ in (12), it follows that

$$\text{supp } Q \subseteq \text{supp } V. \quad (114)$$

Using this observation, let $V_0$ and $V_1$ be two probability measures on the measurable space $(\mathcal{M}, \mathcal{F})$ such that for all $A \in \mathcal{F}$, it holds that

$$V_0(A) = \frac{V(A \setminus \text{supp } Q)}{V(M \setminus \text{supp } Q)}, \quad (115a)$$
which implies that the function $\bar{K}_{Q,z}^{-1}$ in (124) is strictly increasing. Furthermore, from inequality (129) and the fact that $\bar{P}_{\Theta|Z=z}^{(Q,t)}$ is unique (see Theorem 4.1), it follows that $\bar{K}_{Q,z}^{-1}$ is bijective, which completes the proof of the first part.

The second part is as follows. The continuity of the function $\bar{K}_{Q,z}^{-1}$ in (124) is shown by considering an arbitrary $\epsilon > 0$ and a pair $(\gamma_1, \gamma_2) \in \mathcal{A}^2$ under the condition

$$ \epsilon > |\bar{K}_{Q,z}^{-1}(\gamma_2) - \bar{K}_{Q,z}^{-1}(\gamma_1)|. \quad (130) $$

From the fact that $\bar{K}_{Q,z}^{-1}$ is bijective and strictly increasing, let the pair $\gamma_1$, and $\gamma_2$ satisfy $\gamma_1 < \gamma_2$, without loss of generality. Thus, it holds that

$$ |\bar{K}_{Q,z}^{-1}(\gamma_2) - \bar{K}_{Q,z}^{-1}(\gamma_1)| = \bar{K}_{Q,z}^{-1}(\gamma_2) - \bar{K}_{Q,z}^{-1}(\gamma_1). \quad (131) $$

Substituting equality (131) into (130) yields

$$ \bar{K}_{Q,z}^{-1}(\gamma_1) + \epsilon > \bar{K}_{Q,z}^{-1}(\gamma_2). \quad (132) $$

From the fact that $\bar{K}_{Q,z}^{-1}$ is bijective, evaluating inequality (132) with $\bar{K}_{Q,z}$ in (23a) leads to

$$ \bar{K}_{Q,z} \left( \bar{K}_{Q,z}^{-1}(\gamma_1) + \epsilon \right) > \bar{K}_{Q,z} \left( \bar{K}_{Q,z}^{-1}(\gamma_2) \right) \quad (133a) $$

$$ = \gamma_2. \quad (133b) $$

Subtracting $\gamma_1$ from both sides in (133), results in

$$ \bar{K}_{Q,z} \left( \bar{K}_{Q,z}^{-1}(\gamma_1) + \epsilon \right) - \gamma_1 > \gamma_2 - \gamma_1 \quad (134a) $$

$$ = |\gamma_2 - \gamma_1|, \quad (134b) $$

where equality (134b) follows from the condition that $\gamma_2 > \gamma_1$. Thus, from (134) it follows that for all $\epsilon > 0$, there exist a $\delta > 0$ that satisfies

$$ \delta = \bar{K}_{Q,z} \left( \bar{K}_{Q,z}^{-1}(\gamma_1) + \epsilon \right) - \gamma_1, \quad (135) $$

which implies the function $\bar{K}_{Q,z}^{-1}$ in (124) is continuous for all $\gamma \in \mathcal{A}$. From (135) the function $\bar{K}_{Q,z}^{-1}$ is continuous and strictly increasing. Hence, from the continuous inverse theorem in [47, Theorem 5.6], the inverse of the function $\bar{K}_{Q,z}^{-1}$ in (124), which is given by $\bar{K}_{Q,z}$ in (23) is continuous and strictly increasing, which completes the proof. ■

## D Proof of Lemma 4.5

*Proof:* The proof shows by exhaustion that the codomain of the function $\bar{K}_{Q,z}$ in (23) is an interval of $\mathbb{R}$ by evaluating $\beta$ in (25). Three cases are considered: i) $\beta < -\delta_{Q,z}^*$; ii) $\beta > -\delta_{Q,z}^*$; and iii) $\beta = -\delta_{Q,z}^*$, with $\delta_{Q,z}^*$ in (28).
and

$$V_1(\mathcal{A}) = \frac{V(\mathcal{A} \cap \text{supp } Q)}{V(\mathcal{M} \cap \text{supp } Q)}. \qquad (115b)$$

Let the real value $\alpha$ be

$$\alpha \triangleq V(\mathcal{M} \cap \text{supp } Q) \in (0, 1], \qquad (116)$$

which implies that

$$1 - \alpha \triangleq V(\mathcal{M} \setminus \text{supp } Q) \in [0, 1). \qquad (117)$$

Hence, for all $\mathcal{A} \in \mathcal{F}$, the measure $V$ satisfies that

$$V(\mathcal{A}) = (1 - \alpha)V_0(\mathcal{A}) + \alpha V_1(\mathcal{A}). \qquad (118)$$

Moreover, from the definition of $\nabla_Q(\mathcal{M})$ in (12), it follows that the probability measure $Q$ is absolutely continuous with respect to $V$. Hence, for all measurable sets $\mathcal{A}$, it follows that

$$Q(\mathcal{A}) = \int_{\mathcal{A}} dQ(\boldsymbol{\theta}) \qquad (119a)$$

$$= \int_{\mathcal{A}} \frac{dQ}{dV}(\boldsymbol{\theta}) dV(\boldsymbol{\theta}) \qquad (119b)$$

$$= \int_{\mathcal{A}} \frac{dQ}{dV}(\boldsymbol{\theta}) d((1 - \alpha)V_0 + \alpha V_1)(\boldsymbol{\theta}) \qquad (119c)$$

$$= (1 - \alpha) \int_{\mathcal{A}} \frac{dQ}{dV}(\boldsymbol{\theta}) dV_0(\boldsymbol{\theta}) \\ + \alpha \int_{\mathcal{A}} \frac{dQ}{dV}(\boldsymbol{\theta}) dV_1(\boldsymbol{\theta}). \qquad (119d)$$

Note that if $\mathcal{A} \subseteq \text{supp } Q$, it follows that

$$0 < Q(\mathcal{A}) = \int_{\mathcal{A}} \alpha \frac{dQ}{dV}(\boldsymbol{\theta}) dV_1(\boldsymbol{\theta}), \qquad (120)$$

which follows from the fact that $V_0(\mathcal{A}) = 0$ under the assumption that $\mathcal{A} \subseteq \text{supp } Q$. Moreover, noting that the measures $Q$ and $V_1$ are mutually absolutely continuous, it follows from the Radon-Nikodym Theorem [54, Theorem 2.2.1], that the Radon-Nikodym derivative of $Q$ with respect to $V_1$ exists. Moreover, from (120), it follows that for all $\boldsymbol{\theta} \in \text{supp } Q$, it holds that

$$\frac{dQ}{dV_1}(\boldsymbol{\theta}) = \alpha \frac{dQ}{dV}(\boldsymbol{\theta}). \qquad (121)$$

Alternatively, for all measurable sets $\mathcal{A}$, with $\mathcal{A} \subseteq \mathcal{M} \setminus \text{supp } Q$, it follows that

$$0 = Q(\mathcal{A}) = \int_{\mathcal{A}} (1 - \alpha) \frac{dQ}{dV}(\boldsymbol{\theta}) dV_0(\boldsymbol{\theta}), \qquad (122)$$
In the first case, from the definition of $\delta_{Q,z}^*$ in (28), it follows from (15b) that if $\beta < -\delta_{Q,z}^*$, then for all $\theta \in \{\theta \in \text{supp } Q: L_z(\theta) < -\beta\}$, it holds that

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,t)}}{dQ}(\theta) = \frac{\lambda}{L_z(\theta) + \beta} \qquad (136a) $$

$$ < 0, \qquad (136b) $$

which contradicts the fact that the function $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,t)}}{dQ}$ in (16) is nonnegative [45, Corollary 2.2.2]. The above implies that for all $t \in (0, \infty)$, the function $\bar{K}_{Q,z}$ in (23) satisfies that $\bar{K}_{Q,z}(t) \notin (-\infty, -\delta_{Q,z}^*)$.

In the second case, if $\beta > -\delta_{Q,z}^*$, it holds that

$$ \int \frac{1}{L_z(\theta) + \beta} dQ(\theta) \le \int \frac{1}{\delta_{Q,z}^* + \beta} dQ(\theta) \qquad (137a) $$

$$ = \frac{1}{\delta_{Q,z}^* + \beta}. \qquad (137b) $$

Moreover, from (137) for all $\beta > -\delta_{Q,z}^*$, there exists a $\lambda \in (0, \infty)$ such that the constraint in (24) holds, which implies $\bar{K}_{Q,z}^{-1}(\beta) \in (0, \infty)$.

Finally, under the assumption that $\beta = -\delta_{Q,z}^*$ and $\mathcal{L}_{Q,z}^*$ defined in (29), two cases are considered: (a) $Q(\mathcal{L}_{Q,z}^*) > 0$; and (b) $Q(\mathcal{L}_{Q,z}^*) = 0$. In case (a), if $\beta = -\delta_{Q,z}^*$ and $Q(\mathcal{L}_{Q,z}^*) > 0$, then the integral in the denominator of (30) is undefined, contradicting (24). In the alternative case (b), if $\beta = -\delta_{Q,z}^*$ and $Q(\mathcal{L}_{Q,z}^*) = 0$, then the integral in (30) is either

$$ \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) < \infty, \qquad (138a) $$

which implies that $-\delta_{Q,z}^* \in \mathcal{A}$, with $\mathcal{A}$ defined in (23a), or the integral is

$$ \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) = \infty, \qquad (138b) $$

which implies that, $-\delta_{Q,z}^* \notin \mathcal{A}$. Note that the integral is always positive from the fact that for all $\theta \in \text{supp } Q$, it holds that $L_z(\theta) > \delta_{Q,z}^*$. Moreover, the integral in (138) is never zero as it would be a contradiction with (2). Hence, from (136), (137) and (138) the set $\mathcal{A}$ in (23a) is either the open set $(-\delta_{Q,z}^*, \infty)$ or the closed set $[-\delta_{Q,z}^*, \infty)$, which completes the proof.

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

## E Proof of Lemma 4.8

*Proof:* From (15b), for all $\lambda \in (0, \infty)$, it follows that

$$ \lambda = \frac{1}{\int \frac{1}{L_z(\nu) + \beta} dQ(\nu)} \qquad (139a) $$
which follows from the fact that $V_1(\mathcal{A}) = 0$ under the assumption that $\mathcal{A} \subseteq \mathcal{M} \setminus \text{supp } Q$. Hence, it holds that for all $\theta \in \mathcal{M} \setminus \text{supp } Q$, $\frac{dQ}{dV}(\theta) = 0$. In a nutshell, for all $\theta \in \text{supp } V$,

$$ \frac{dQ}{dV}(\theta) = \begin{cases} \frac{1}{\alpha} \frac{dQ}{dV_1}(\theta) & \text{if } \theta \in \text{supp } Q \\ 0 & \text{otherwise.} \end{cases} \qquad (123) $$

From (123), the following holds:

$$ D(Q \| V) = \int \log \left( \frac{dQ}{dV}(\theta) \right) dQ(\theta) \qquad (124a) $$

$$ = \int \log \left( \frac{1}{\alpha} \frac{dQ}{dV_1}(\theta) \right) dQ(\theta) \qquad (124b) $$

$$ = \int \log \left( \frac{dQ}{dV_1}(\theta) \right) dQ(\theta) - \int \log(\alpha) dQ(\theta) \qquad (124c) $$

$$ = D(Q \| V_1) - \log(\alpha). \qquad (124d) $$

From (124), it follows that

$$ \mathbb{R}_z(V) + \lambda D(Q \| V) = \mathbb{R}_z((1 - \alpha)V_0 + \alpha V_1) + \lambda D(Q \| V_1) - \lambda \log(\alpha) \qquad (125a) $$

$$ = (1 - \alpha)\mathbb{R}_z(V_0) + \alpha\mathbb{R}_z(V_1) + \lambda D(Q \| V_1) - \lambda \log(\alpha) \qquad (125b) $$

$$ \geq \alpha \mathbb{R}_z(V_1) + \lambda D(Q \| V_1), \qquad (125c) $$

with equality if and only if $\alpha = 1$, which implies that for all

$$ P^* \in \arg \min_{V \in \nabla_Q(\mathcal{M})} \mathbb{R}_z(V) + \lambda D(Q \| V), \qquad (126) $$

it holds that $P^* \in \mathcal{O}_Q(\mathcal{M})$, which follows from observing that

$$ \text{supp } Q = \text{supp } P^*, \qquad (127) $$

which implies (19) and completes the proof

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

# D Proof of Lemma 4.1

The proof is divided into two parts. The first part proves the monotonicity of the function $\bar{K}_{Q,z}^{-1}$ in (26); while the second part proves the continuity of the function $\bar{K}_{Q,z}^{-1}$. The proof is finalized by using the continuous inverse theorem [56, Theorem 5.6.5] to show both the monotonicity and continuity of the function $\bar{K}_{Q,z}$ in (23).

The first part is as follows. Let $\lambda$ and $\beta$ be two reals that satisfy (23b). Hence, $0 < \lambda < \infty$ and from (25b), it holds that

$$ 0 < \int \frac{1}{L_z(\theta) + \beta} dQ(\theta) < \infty, \qquad (128) $$
$$ = \frac{1}{\int \frac{1}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu)}, \qquad (139b) $$

where equality (139a) follows from (15b), and equality (139b) follows from the nominal function in (23b). From the definition of $\delta_{Q,z}^*$ in (28), for all $\nu \in \text{supp } Q$, the empirical risk satisfies

$$ L_z(\nu) \geq \delta_{Q,z}^*. \qquad (140) $$

Taking the limit of (139) as $\lambda$ approaches zero from the right satisfies

$$ \lim_{\lambda \to 0^+} \lambda = \lim_{\lambda \to 0^+} \frac{1}{\int \frac{1}{L_z(\nu) + \bar{K}(\lambda)} dQ(\nu)} \qquad (141a) $$

$$ \geq \lim_{\lambda \to 0^+} \frac{1}{\int \frac{1}{\delta_{Q,z}^* + \bar{K}(\lambda)} dQ(\nu)} \qquad (141b) $$

$$ = \lim_{\lambda \to 0^+} \frac{1}{\delta_{Q,z}^* + \bar{K}(\lambda)} \qquad (141c) $$

$$ = \lim_{\lambda \to 0^+} (\delta_{Q,z}^* + \bar{K}(\lambda)) \qquad (141d) $$

$$ = \delta_{Q,z}^* + \lim_{\lambda \to 0^+} \bar{K}(\lambda), \qquad (141e) $$

where inequality (141b) follows from (140). Hence, from (141) it holds that

$$ 0 \geq \delta_{Q,z}^* + \lim_{\lambda \to 0^+} \bar{K}(\lambda). \qquad (142) $$

From (15a) and Lemma 4.4, for all $\lambda \in (0, \infty)$, it holds that

$$ 0 \leq \delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda). \qquad (143) $$

Taking the limit when $\lambda$ approaches zero from the right in (143) yields

$$ 0 \leq \delta_{Q,z}^* + \lim_{\lambda \to 0^+} \bar{K}_{Q,z}(\lambda). \qquad (144) $$

Then, from (142) and (144) it follows that

$$ \lim_{\lambda \to 0^+} \bar{K}_{Q,z}(\lambda) = -\delta_{Q,z}^*, \qquad (145) $$

which completes the proof. ■

## F Proof of Lemma 4.9

*Proof:* For all $\theta_1 \in \text{supp } Q$ and for all $\theta_2 \in \mathcal{L}_{Q,z}^*$, it follows that

$$ L_z(\theta_1) \geq L_z(\theta_2), \qquad (146) $$

and thus, for all $\lambda \in (0, \infty)$, it holds that

$$ \frac{1}{\bar{K}_{Q,z}(\lambda) + L_z(\theta_1)} \leq \frac{1}{\bar{K}_{Q,z}(\lambda) + L_z(\theta_2)}, \qquad (147a) $$
which, together with (26), imply

$$ \infty > \bar{K}_{Q,z}^{-1}(\beta) > 0. \qquad (129) $$

That is, the function $\bar{K}_{Q,z}^{-1}$ in (26) is positive and finite. Using this observation, let the reals $\gamma_1$ and $\gamma_2$ be elements of the set $C_{Q,z}$, with $C_{Q,z}$ in (23a) and $\gamma_1 < \gamma_2$. Hence, for all $\theta \in \text{supp } Q$, it holds that

$$ \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \gamma_1} > \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \gamma_2}, \qquad (130) $$

which implies that

$$ \int \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \gamma_1} dQ(\boldsymbol{\theta}) > \int \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \gamma_2} dQ(\boldsymbol{\theta}), \qquad (131) $$

and thus, from (26), it holds that

$$ \bar{K}_{Q,z}^{-1}(\gamma_1) < \bar{K}_{Q,z}^{-1}(\gamma_2). \qquad (132) $$

This proves that the function $\bar{K}_{Q,z}^{-1}$ in (26) is strictly increasing, and completes the first part of the proof.

In the second part, the objective is to prove the continuity of the function $\bar{K}_{Q,z}^{-1}$. To do so, two auxiliary functions are introduced and proven to be continuous. Then, the fact that $\bar{K}_{Q,z}^{-1}$ in (26) is the composition of the two auxiliary functions is leveraged to prove its continuity. Let the function $h : (0, \infty) \to (0, \infty)$ be

$$ h(x) = \frac{1}{x}. \qquad (133) $$

Let also the function $k : C_{Q,z} \to (0, \infty)$, be such that

$$ k(\gamma) = \int h(\gamma + \mathbf{L}_z(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}). \qquad (134) $$

The first step is to prove that the function $k$ in (134) is continuous in $C_{Q,z}$. This is proved by showing that $k$ always exhibits a limit in $C_{Q,z}$. Note that if $\gamma \in C_{Q,z}$, with $C_{Q,z}$ in (23), then from (15a), it follows that for all $\theta \in \text{supp } Q$, the inequality $\mathbf{L}_z(\boldsymbol{\theta}) + \gamma > 0$ holds, which implies that $\gamma > -\delta_{Q,z}^*$, with $\delta_{Q,z}^*$ in (28). Hence, the proof of continuity of the function $k$ in (134) is restricted to $(-\delta_{Q,z}^*, \infty)$.

For two models $\theta_1$ and $\theta_2$ in $\text{supp } Q$, such that $\mathbf{L}_z(\theta_1) < \mathbf{L}_z(\theta_2)$, the function $h$ satisfies

$$ h(\gamma + \mathbf{L}_z(\boldsymbol{\theta}_1)) > h(\gamma + \mathbf{L}_z(\boldsymbol{\theta}_2)). \qquad (135) $$

Then, for all $\gamma \in (-\delta_{Q,z}^*, \infty)$ and for all $\theta \in \text{supp } Q$, it holds that

$$ h(\gamma + \delta_{Q,z}^*) \geq h(\gamma + \mathbf{L}_z(\boldsymbol{\theta})), \qquad (136) $$
which implies

$$ \frac{(\bar{K}_{Q,z}(\lambda) + L_z(\theta_1))^{-1}}{\int (\bar{K}_{Q,z}(\lambda) + L_z(\nu))^{-1} dQ(\nu)} \le \frac{(\bar{K}_{Q,z}(\lambda) + L_z(\theta_2))^{-1}}{\int (\bar{K}_{Q,z}(\lambda) + L_z(\nu))^{-1} dQ(\nu)}. \quad (148) $$

Hence, under the assumption that $\mathcal{L}_{Q,z}^* \cap \text{supp } Q \neq \emptyset$, for all $\theta_1 \in \text{supp } Q$ and for all $\theta_2 \in \mathcal{L}_{Q,z}^* \cap \text{supp } Q$, it holds that

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta_1) \le \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta_2), \quad (149) $$

with equality if and only if $\theta_1 \in \mathcal{L}_{Q,z}^* \cap \text{supp } Q$, which completes the proof. ■

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

## G Proof of Lemma 4.10

*Proof:* From Lemma 4.9, it follows that for all $\lambda \in (0, \infty)$, for all $\theta \in \text{supp } Q$, and for all $\phi \in \mathcal{L}_{Q,z}^* \cap \text{supp } Q$, it holds that

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \le \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\phi) \quad (150a) $$

$$ = \frac{\lambda}{L_z(\phi) + \bar{K}_{Q,z}(\lambda)} \quad (150b) $$

$$ = \frac{\lambda}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} \quad (150c) $$

$$ < \infty, \quad (150d) $$

where equality (150a) follows from (16); equality (150b) follows from the fact that $L_z(\phi) \ge \delta_{Q,z}^*$; and the equality in (150d) follows from the fact that for all $\lambda > 0$, the function $\bar{K}_{Q,z}(\lambda) < \infty$. From the definition of $\delta_{Q,z}^*$ in (28) and $\mathcal{L}_{Q,z}^*$ in (29) equality in (150a) holds if and only if $\theta \in \mathcal{L}_{Q,z}^* \cap \text{supp } Q$. This completes the proof of finiteness.

For the proof of positivity, observe that from Lemma 4.4 for all $\lambda \in (0, \infty)$, it holds that

$$ - \delta_{Q,z}^* < \bar{K}_{Q,z}(\lambda) < \infty, \quad (151) $$

which implies

$$ 0 < \delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda). \quad (152) $$

From (151), it follows that

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda}{\bar{K}_{Q,z}(\lambda) + L_z(\theta)} \quad (153a) $$
where equality holds if and only if $L_z(\theta) = \delta_{Q,z}^*$. The function $h$ is continuous, and thus, for all $\theta \in \text{supp } Q$ and for all $a \in (-\delta_{Q,z}^*, \infty)$, it holds that

$$ \lim_{\gamma \to a} h(\gamma + L_z(\theta)) = h(a + L_z(\theta)). \quad (137) $$

Hence, from the dominated convergence theorem [54, Theorem 1.6.9], the following limit exists and satisfies

$$ \lim_{\gamma \to a} k(b) = \lim_{\gamma \to a} \int h(\gamma + L_z(\theta)) \, dQ(\theta) \quad (138a) $$

$$ = \int \left( \lim_{\gamma \to a} h(\gamma + L_z(\theta)) \right) dQ(\theta) \quad (138b) $$

$$ = \int h(a + L_z(\theta)) \, dQ(\theta) \quad (138c) $$

$$ = k(a), \quad (138d) $$

where (138c) follows from (137). The equality in (138d) proves that the function $k$ in (134) is continuous in the interval $(-\delta_{Q,z}^*, \infty)$. Note that from (26) and (134), it holds that

$$ \bar{K}_{Q,z}^{-1}(\gamma) = \frac{1}{k(\gamma)}. \quad (139) $$

Using (139), for all $a \in (-\delta_{Q,z}^*, \infty)$, it holds that

$$ \lim_{\gamma \to a} \bar{K}_{Q,z}^{-1}(\gamma) = \lim_{\gamma \to a} \frac{1}{k(\gamma)} \quad (140) $$

$$ = \frac{1}{\lim_{\gamma \to a} k(\gamma)} \quad (141) $$

$$ = \frac{1}{\int h(a + L_z(\theta)) dQ(\theta)} \quad (142) $$

$$ = \frac{1}{\int \frac{1}{a + L_z(\theta)} dQ(\theta)} \quad (143) $$

$$ = \bar{K}_{Q,z}^{-1}(a), \quad (144) $$

where (141) follows from the continuity of the function $h$ in (133) over the interval $(0, \infty)$; (142) follows from (138d); and (143) follows from (26). Thus, the existence of the limit in (140) implies that the function $\bar{K}_{Q,z}^{-1}$ is continuous in $C_{Q,z}$. This completes the second part of the proof.

The proof ends by using the continuous inverse theorem [56, Theorem 5.6.5]. That is, given that the function $\bar{K}_{Q,z}^{-1}$ is both continuous and strictly increasing, then, so is the function $\bar{K}_{Q,z}$ in (23). This concludes the proof. ■

## E Proof of Lemma 4.2

The proof is divided into two parts. In the first part, it is shown that the set $C_{Q,z}$ is an interval of $\mathbb{R}$. In the second part, the set $A_{Q,z}$ is shown to be also
$$= \frac{\int_{\bar{K}_{Q,z}(\lambda)+L_z(\nu)} \frac{1}{\bar{K}_{Q,z}(\lambda)+L_z(\nu)} dQ(\nu)}{\bar{K}_{Q,z}(\lambda)+L_z(\theta)} \quad (153b)$$

$$> 0, \qquad (153c)$$

which completes the proof.

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

## H Proof of Lemma 4.11

*Proof:* From Theorem 4.1, the Radon-Nikodym derivative of the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ with respect to $Q$, for all $\theta \in \text{supp } Q$, satisfies that

$$\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda}{\bar{K}_{Q,z}(\lambda) + L_z(\theta)} \quad (154a)$$

$$= \frac{\int_{\bar{K}_{Q,z}(\lambda)+L_z(\nu)} \frac{1}{\bar{K}_{Q,z}(\lambda)+L_z(\nu)} dQ(\nu)}{\bar{K}_{Q,z}(\lambda)+L_z(\theta)} \quad (154b)$$

$$= \left( \frac{\bar{K}_{Q,z}(\lambda) + L_z(\theta)}{\int (\bar{K}_{Q,z}(\lambda) + L_z(\nu))^{-1} dQ(\nu)} \right)^{-1} \quad (154c)$$

$$= \frac{\exp(-\log(\bar{K}_{Q,z}(\lambda) + L_z(\theta)))}{\int \exp\left(\log\left(\frac{1}{\bar{K}_{Q,z}(\lambda)+L_z(\nu)}\right)\right) dQ(\nu)} \quad (154d)$$

From Lemma 4.4, the case in which $\lambda \to \infty$ implies $\bar{K}_{Q,z}(\lambda) \to \infty$, and from (154), it follows that

$$\lim_{\lambda \to \infty} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \lim_{\lambda \to \infty} \frac{\exp(-\log(\bar{K}_{Q,z}(\lambda) + L_z(\theta)))}{\int \exp\left(\log\left(\frac{1}{\bar{K}_{Q,z}(\lambda)+L_z(\nu)}\right)\right) dQ(\nu)} \quad (155)$$

$$= \frac{1}{\int dQ(\nu)} \quad (156)$$

$$= 1, \quad (157)$$

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

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

## I Proof of Lemma 4.12

*Proof:* Assume that $t \in (0, \infty)$ and $\gamma \in \mathbb{R}$ satisfy that

$$1 = \int \frac{t}{L_z(\theta) + \gamma} dQ(\theta), \quad (158)$$

which implies

$$\bar{K}_{Q,z}(t) = \gamma. \quad (159)$$
an interval. The first part uses a partition of $\mathbb{R}$ formed by the following sets: $(-\infty, -\delta_{Q,z}^*)$; $(-\delta_{Q,z}^*, \infty)$; and $\{\delta_{Q,z}^*\}$, with $\delta_{Q,z}^*$ in (28). Each of these intervals is studied separately.

Let $\beta$ be such that $\bar{K}_{Q,z}(\lambda) = \beta$, with $\lambda$ in (11) and assume that $\beta \in (-\infty, -\delta_{Q,z}^*)$. Under this assumption, the inclusion in (15a) does not hold. This follows from the fact that, if $\beta < -\delta_{Q,z}^*$, for all $\theta \in \{\nu \in \text{supp } Q : \delta_{Q,z}^* \le L_z(\nu) < -\beta\}$, it holds that $L_z(\theta) + \beta < 0$, which contradicts (15a). This implies that

$$(-\infty, -\delta_{Q,z}^*) \cap C_{Q,z} = \emptyset. \qquad (145)$$

Assume now that $\beta \in (-\delta_{Q,z}^*, \infty)$. Then, from (28), it can be verified that the constraint in (15a) is satisfied. More specifically, for all $\theta \in \text{supp } Q$, it holds that $L_z(\theta) + \beta > 0$. The proof continuous by showing that (15b) is also verified. For this purpose, note that

$$\int \frac{1}{L_z(\theta) + \beta} dQ(\theta) \le \int \frac{1}{\delta_{Q,z}^* + \beta} dQ(\theta) \qquad (146a)$$

$$= \frac{1}{\delta_{Q,z}^* + \beta} \qquad (146b)$$

$$< \infty. \qquad (146c)$$

The finiteness of the integral in the left-hand side of (146a) implies that

$$0 < \lambda \qquad (147a)$$

$$= \bar{K}_{Q,z}^{-1}(\beta) \qquad (147b)$$

$$= \frac{1}{\int \frac{1}{L_z(\theta) + \beta} dQ(\theta)} \qquad (147c)$$

$$< \infty, \qquad (147d)$$

where (147a) follows from the assumption that $\lambda \in A_{Q,z} \subseteq (0, \infty)$; (147b) follows from the fact that $\bar{K}_{Q,z}(\lambda) = \beta$; (147c) follows from (26); and (147d) follows from the inequality in (146c). In a nutshell,

$$\int \frac{1}{L_z(\theta) + \beta} dQ(\theta) < \infty, \text{ and} \qquad (148)$$

$$\lambda < \infty, \qquad (149)$$

which, implies that the product

$$\lambda \int \frac{1}{L_z(\theta) + \beta} dQ(\theta) = \int \frac{\lambda}{L_z(\theta) + \beta} dQ(\theta) \qquad (150a)$$

$$= \int \frac{\frac{1}{\int \frac{1}{L_z(\nu) + \beta} dQ(\nu)}}{L_z(\theta) + \beta} dQ(\theta) \qquad (150b)$$

$$= 1, \qquad (150c)$$
Let the function $\bar{K}_{Q,z}^{-1}: \mathbb{R} \to (0, \infty)$ be the functional inverse of $\bar{K}_{Q,z}$ in (159). Thus,

$$ \bar{K}_{Q,z}^{-1}(\gamma) = t, \qquad (160) $$

with $\gamma$ and $t$ in (158). From (158), the function $\bar{K}_{Q,z}^{-1}$ in (160) satisfies

$$ \bar{K}_{Q,z}^{-1}(\gamma) = \frac{1}{\int_{\mathbb{L}_z(\boldsymbol{\theta})+\gamma}^{\mathbb{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta})}. \qquad (161) $$

From Theorem 4.1, for all $\lambda \in (0, \infty)$ and for all $\boldsymbol{\theta} \in \text{supp } Q$, it follows that

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) = \frac{\lambda}{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)} \qquad (162\text{a}) $$

$$ = \frac{\bar{K}_{Q,z}^{-1}(\bar{K}_{Q,z}(\lambda))}{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)} \qquad (162\text{b}) $$

$$ = \frac{\int_{\mathbb{L}_z(\boldsymbol{\nu})+\bar{K}_{Q,z}(\lambda)}^{\frac{1}{\mathbb{L}_z(\boldsymbol{\nu})+\bar{K}_{Q,z}(\lambda)}} dQ(\boldsymbol{\nu})}{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)} \qquad (162\text{c}) $$

$$ = \left( \int \frac{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbb{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right)^{-1}. \qquad (162\text{d}) $$

Given $\boldsymbol{\theta} \in \text{supp } Q$, consider the partition of the set $\mathcal{M}$ formed by the sets $\mathcal{A}_0$, $\mathcal{A}_1$, and $\mathcal{A}_2$, which satisfy the following:

$$ \mathcal{A}_0 = \{ \boldsymbol{\nu} \in \mathcal{M} : \mathbb{L}_z(\boldsymbol{\nu}) = \delta_{Q,z}^* \}, \qquad (163\text{a}) $$

$$ \mathcal{A}_1 = \{ \boldsymbol{\nu} \in \mathcal{M} : \mathbb{L}_z(\boldsymbol{\nu}) > \delta_{Q,z}^* \}, \qquad (163\text{b}) $$

$$ \mathcal{A}_2 = \{ \boldsymbol{\nu} \in \mathcal{M} : \mathbb{L}_z(\boldsymbol{\nu}) < \delta_{Q,z}^* \}, \qquad (163\text{c}) $$

with $\delta_{Q,z}^*$ defined in (28). Using the sets $\mathcal{A}_0$, $\mathcal{A}_1$, and $\mathcal{A}_2$ in (162), for all $\lambda \in (0, \infty)$ and for all $\boldsymbol{\theta} \in \text{supp } Q$ the following holds

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) = \left( \int_{\mathcal{A}_0} \frac{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbb{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) + \int_{\mathcal{A}_1} \frac{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbb{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) + \int_{\mathcal{A}_2} \frac{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbb{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right)^{-1} \qquad (164\text{a}) $$

$$ = \left( \int_{\mathcal{L}_{Q,z}^*} \frac{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbb{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) + \int_{\mathcal{A}_1} \frac{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbb{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right)^{-1} \qquad (164\text{b}) $$

$$ = \left( \int_{\mathcal{L}_{Q,z}^*} \frac{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) + \int_{\mathcal{A}_1} \frac{\mathbb{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbb{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right)^{-1} \qquad (164\text{c}) $$

where equality (164b) follows from the fact that the $\mathcal{A}_2$ has measure zero with respect to $Q$ and that the set $\mathcal{A}_0 = \mathcal{L}_{Q,z}^*$, with $\mathcal{L}_{Q,z}^*$ in (29); and equality
where (150b) follows from (147c). This verifies (15b), which implies that

$$(-\delta_{Q,z}^*, \infty) \subseteq C_{Q,z}. \qquad (151)$$

Finally, under the assumption that $\beta = -\delta_{Q,z}^*$, two cases are considered: (a) $Q(\mathcal{L}_{Q,z}^*) > 0$; and (b) $Q(\mathcal{L}_{Q,z}^*) = 0$, with $\mathcal{L}_{Q,z}^*$ defined in (30). In case (a), if $\beta = -\delta_{Q,z}^*$ and $Q(\mathcal{L}_{Q,z}^*) > 0$, then for all $\theta \in \mathcal{L}_{Q,z}^*$, it follows that

$$\frac{1}{\mathcal{L}_z(\theta) - \delta_{Q,z}^*} Q(\mathcal{L}_{Q,z}^*) = \infty, \qquad (152)$$

which implies that,

$$\int \frac{1}{\mathcal{L}_z(\theta) + \beta} dQ(\theta) = \infty. \qquad (153)$$

The equality in (153) implies that the constraint (15b) is not satisfied. Therefore, for case (a) it follows that,

$$-\delta_{Q,z}^* \notin C_{Q,z}. \qquad (154)$$

In the alternative case (b), if $\beta = -\delta_{Q,z}^*$ and $Q(\mathcal{L}_{Q,z}^*) = 0$, then, the integral in (26) is either

$$\int \frac{1}{\mathcal{L}_z(\theta) - \delta_{Q,z}^*} dQ(\theta) < \infty, \qquad (155)$$

which implies that $-\delta_{Q,z}^* \in C_{Q,z}$, with $C_{Q,z}$ defined in (23a), or the integral is

$$\int \frac{1}{\mathcal{L}_z(\theta) - \delta_{Q,z}^*} dQ(\theta) = \infty, \qquad (156)$$

which implies that $-\delta_{Q,z}^* \notin C_{Q,z}$. Hence, from (145), (151), (154), (155), and (156) the set $C_{Q,z}$ in (23a) is either the open set $(-\delta_{Q,z}^*, \infty)$ or the closed set $(-\delta_{Q,z}^*, \infty)$. Note that the equality $C_{Q,z} = (-\delta_{Q,z}^*, \infty)$ is observed, if and only if,

$$\int \frac{1}{\mathcal{L}_z(\theta) - \delta_{Q,z}^*} dQ(\theta) < \infty, \qquad (157)$$

which completes the first part of the proof.

The second part of the proof is as follows. Two cases are considered: i) $C_{Q,z} = (-\delta_{Q,z}^*, \infty)$; and ii) $C_{Q,z} = (-\delta_{Q,z}^*, \infty)$. In case i), the value $-\delta_{Q,z}^*$ is in the domain of the function $\bar{K}_{Q,z}^{-1}$ in (26), that is, the set $C_{Q,z}$. Given that the function $\bar{K}_{Q,z}^{-1}$ is strictly increasing, then, $-\delta_{Q,z}^*$ should be mapped to the smallest value in the range of $\bar{K}_{Q,z}^{-1}$, denoted by $\lambda_{Q,z}$. Hence,

$$\bar{K}_{Q,z}^{-1}(-\delta_{Q,z}^*) = \lambda_{Q,z} \qquad (158)$$
(164b) follows from the definition of $\delta_{Q,z}^*$ in (28). Following this observation, the rest of the proof is divided into three parts. The first part evaluates $\lim_{\lambda \to \infty} \frac{d\bar{P}^{(Q,\lambda)}}{dQ}(\theta)$, with $\theta \in \{\nu \in \mathcal{M} : \mathcal{L}_z(\nu) = \delta_{Q,z}^*\}$. The second part considers the case in which $\theta \in \{\nu \in \mathcal{M} : \mathcal{L}_z(\nu) > \delta_{Q,z}^*\}$. The third part considers the remaining case.

The first part is as follows. Consider that $\theta \in \{\nu \in \mathcal{M} : \mathcal{L}_z(\nu) = \delta_{Q,z}^*\}$ and note that $A_0 = \mathcal{L}_{Q,z}^*$. From (164), for all $\theta \in \{\nu \in \mathcal{M} : \mathcal{L}_z(\nu) = \delta_{Q,z}^*\}$ it holds that

$$ \frac{d\bar{P}^{(Q,\lambda)}(\theta)}{dQ} = \left( \int_{\mathcal{L}_{Q,z}^*} \frac{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} dQ(\nu) + \int_{A_1} \frac{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)}{\mathcal{L}_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1} \quad (165a) $$

$$ = \left( Q(\mathcal{L}_{Q,z}^*) + \int_{A_1} \frac{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)}{\mathcal{L}_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1} \quad (165b) $$

The equality in (165) implies that for all $\theta \in \{\nu \in \mathcal{M} : \mathcal{L}_z(\nu) = \delta_{Q,z}^*\}$ the limit satisfies

$$ \lim_{\lambda \to 0^+} \frac{d\bar{P}^{(Q,\lambda)}(\theta)}{dQ} = \left( Q(\mathcal{L}_{Q,z}^*) + \lim_{\lambda \to 0^+} \int_{A_1} \frac{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)}{\mathcal{L}_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1} \quad (166a) $$

$$ = \left( Q(\mathcal{L}_{Q,z}^*) + \lim_{\lambda \to 0^+} (\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)) \right) \lim_{\lambda \to 0^+} \int_{A_1} \frac{1}{\mathcal{L}_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \quad (166b) $$

$$ = \left( Q(\mathcal{L}_{Q,z}^*) + \lim_{\lambda \to 0^+} \left( \delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda) \right) \right) \lim_{\lambda \to 0^+} \int_{A_1} \frac{1}{\mathcal{L}_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \quad (166c) $$

$$ = \left( Q(\mathcal{L}_{Q,z}^*) + 0 \int_{A_1} \frac{1}{\mathcal{L}_z(\nu) - \delta_{Q,z}^*} dQ(\nu) \right)^{-1} \quad (166d) $$

$$ = (Q(\mathcal{L}_{Q,z}^*))^{-1}, \quad (166e) $$

where equality (166d) follows from Lemma 4.8.

The second part is as follows. Consider that $\theta \in \{\nu \in \mathcal{M} : \mathcal{L}_z(\nu) > \delta_{Q,z}^*\}$. Hence, for all $\theta \in \{\nu \in \mathcal{M} : \mathcal{L}_z(\nu) > \delta_{Q,z}^*\}$, there exists a real value $\epsilon > 0$ such
$$> 0, \qquad (159)$$

where (159) follows from the fact that zero is not in the domain of the function $\bar{K}_{Q,z}$, that is, the set $A_{Q,z}$. Using these elements, it is concluded that the set $A_{Q,z}$ is the interval $[\lambda_{Q,z}, \infty)$, which ends the analysis of case i.).

In case ii), from Lemma 4.1, the continuity and strict monotonicity of the function $\bar{K}_{Q,z}$ in (23) imply that $A_{Q,z} = (\lambda_{Q,z}^*, \infty)$, with $\lambda_{Q,z}^*$ in (29). The remaining of the proof focuses on showing that $\lambda_{Q,z}^* = 0$ in this case, and thus, $A_{Q,z} = (0, \infty)$. From Lemma 4.1 and the continuous inverse theorem [56, Theorem 5.6.5], it follows that function $\bar{K}_{Q,z}^{-1}$ is strictly increasing and continuous. Hence, using (26), it holds that

$$\lim_{\gamma \to -\delta_{Q,z}^*+} \bar{K}_{Q,z}^{-1}(\gamma) = \lim_{\gamma \to -\delta_{Q,z}^*+} \frac{1}{\int_{L_z(\theta)+\gamma}^{\frac{1}{L_z(\theta)+\gamma}} dQ(\theta)} \quad (160)$$

$$= \frac{1}{\lim_{\gamma \to -\delta_{Q,z}^*+} \int_{L_z(\theta)+\gamma}^{\frac{1}{L_z(\theta)+\gamma}} dQ(\theta)} \quad (161)$$

$$= \frac{1}{\int_{L_z(\theta)-\delta_{Q,z}^*}^{\frac{1}{L_z(\theta)-\delta_{Q,z}^*}} dQ(\theta)} \quad (162)$$

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

where (161) follows from [57, Theorem 4.4], that permits the change of the limit to the reciprocal; and (162) follows from (138); and (163) follows from (156). From Lemma 4.1 and (163), it follows that in this second case, in which $C_{Q,z} = (-\delta_{Q,z}^*, \infty)$, it holds that $A_{Q,z} = (0, \infty)$. This completes the proof. ■

## F Proof of Lemma 4.6

From Lemma 4.1, the function $\bar{K}_{Q,z}$ in (23) is strictly increasing and continuous. Additionally, from Lemma 4.2, the domain and range of the function $\bar{K}_{Q,z}$, defined by the sets $A_{Q,z}$ and $C_{Q,z}$, respectively, are convex intervals. Consequently, combining Lemma 4.1 and Lemma 4.2, it follows that

$$\lim_{\lambda \to \lambda_{Q,z}^*+} \bar{K}_{Q,z}(\lambda) = -\delta_{Q,z}^*, \qquad (164)$$

with $\delta_{Q,z}^*$ defined in (28) and $\lambda_{Q,z}^*$ defined in (29). ■

## G Proof of Lemma 5.1

For all $(\theta_1, \theta_2) \in (\text{supp } Q)^2$, such that

$$L_z(\theta_1) \le L_z(\theta_2), \qquad (165)$$
that the function $L_z$ satisfies

$$L_z(\theta) - \delta_{Q,z}^* = \epsilon. \qquad (167)$$

From (164), for all $\theta \in \{\nu \in \mathcal{M} : L_z(\nu) > \delta_{Q,z}^*\}$ it holds that

$$\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \left( \int_{\mathcal{L}_{Q,z}^*} \frac{\delta_{Q,z}^* + \epsilon + \bar{K}_{Q,z}(\lambda)}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} dQ(\nu) + \int_{A_1} \frac{\delta_{Q,z}^* + \epsilon + \bar{K}_{Q,z}(\lambda)}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1} \qquad (168a)$$

$$= \left( \frac{\delta_{Q,z}^* + \epsilon + \bar{K}_{Q,z}(\lambda)}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} Q(\mathcal{L}_{Q,z}^*) + \int_{A_1} \frac{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1}. \qquad (168b)$$

The equality in (168) implies that for all $\theta \in \{\nu \in \mathcal{M} : L_z(\nu) = \delta_{Q,z}^*\}$, the limit satisfies

$$\lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \left( \lim_{\lambda \to 0^+} \frac{\delta_{Q,z}^* + \epsilon + \bar{K}_{Q,z}(\lambda)}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} Q(\mathcal{L}_{Q,z}^*) + \lim_{\lambda \to 0^+} \int_{A_1} \frac{\delta_{Q,z}^* + \epsilon + \bar{K}_{Q,z}(\lambda)}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1} \qquad (169a)$$

$$= \left( \frac{\delta_{Q,z}^* + \epsilon + \lim_{\lambda \to 0^+} \bar{K}_{Q,z}(\lambda)}{\delta_{Q,z}^* + \lim_{\lambda \to 0^+} \bar{K}_{Q,z}(\lambda)} Q(\mathcal{L}_{Q,z}^*) + \lim_{\lambda \to 0^+} (\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)) \right)$$

$$\lim_{\lambda \to 0^+} \int_{A_1} \frac{1}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1} \qquad (169b)$$

$$= \left( \infty Q(\mathcal{L}_{Q,z}^*) + \epsilon \int_{A_1} \frac{1}{L_z(\nu) - \delta_{Q,z}^*} dQ(\nu) \right)^{-1} \qquad (169c)$$

The proof continuous by considering the cases in which $Q(\mathcal{A}_0) > 0$ and $Q(\mathcal{A}_0) = 0$ for the limit in (169). Under the assumption that $Q(\mathcal{A}_0) > 0$, from (169b) the limit satisfies

$$\lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 0. \qquad (170a)$$

Under the assumption that $Q(\mathcal{A}_0) = 0$, from the definition of $\delta_{Q,z}^*$ in (28), if $Q(\mathcal{A}_0) = 0$, then it is implied that there is at least an infinite countable sequence of models $\nu_1, \nu_2, \dots$ in supp $Q$ that satisfies

$$L_z(\nu_1) > L_z(\nu_2) > \dots, \qquad (171)$$