# Empirical Risk Minimization with f-Divergence Regularization

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

► To cite this version:

Francisco Daunas, Samir M. Perlaza, Iñaki Esnaola, H. Vincent Poor. Empirical Risk Minimization with f-Divergence Regularization. 2026. hal-05474394

HAL Id: hal-05474394

https://inria.hal.science/hal-05474394v1

Preprint submitted on 23 Jan 2026

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

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Empirical Risk Minimization with *f*-Divergence Regularization

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

***Abstract***—In this paper, the solution to the empirical risk minimization problem with *f*-divergence regularization (ERM-*f*DR) is presented and conditions under which the solution also serves as the solution to the minimization of the expected empirical risk subject to an *f*-divergence constraint are established. The proposed approach extends applicability to a broader class of *f*-divergences than previously reported and yields theoretical results that recover previously known results. Additionally, the difference between the expected empirical risk of the ERM-*f*DR solution and that of its reference measure is characterized, providing insights into previously studied cases of *f*-divergences. A central contribution is the introduction of the normalization function, a mathematical object that is critical in both the dual formulation and practical computation of the ERM-*f*DR solution. This work presents an implicit characterization of the normalization function as a nonlinear ordinary differential equation (ODE), establishes its key properties, and subsequently leverages them to construct a numerical algorithm for approximating the normalization factor under mild assumptions. Further analysis demonstrates structural equivalences between ERM-*f*DR problems with different *f*-divergences via transformations of the empirical risk. Finally, the proposed algorithm is used to compute the training and test risks of ERM-*f*DR solutions under different *f*-divergence regularizers. This numerical example highlights the practical implications of choosing different functions *f* in ERM-*f*DR problems.

## I. INTRODUCTION

Empirical risk minimization (ERM) [3]–[7] is an underlying principle of statistical learning [8]–[12], which serves as the basis for the fundamental analysis of many modern supervised and unsupervised learning algorithms [13]–[15]. In statistical learning, several frameworks, such as Bayesian inference, PAC-Bayesian learning, and information-theoretic learning, adopt a probabilistic perspective by characterizing

This work was presented in part at the International Symposium on Information Theory (ISIT) 2024 in [1] and at the Information Theory Workshop (ITW) 2025 in [2]. This work is supported in part by a University of Sheffield ACSE PGR scholarship and Sheffield Publication scholarship. Special thanks to Maxime Nicaise for helpful feedback and discussions that enhanced clarity over the results here presented.

F. Daunas is with the School of Electrical and Electronic Engineering, University of Sheffield, Sheffield S1 3JD, U.K.; (e-mail: j.daunastorres@sheffield.ac.uk).

I. Esnaola is with the School of Electrical and Electronic Engineering, University of Sheffield, Sheffield S1 3JD, U.K.; and also with the Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: esnaola@sheffield.ac.uk).

Samir M. Perlaza is with INRIA, Centre Inria d'Université Côte d'Azur, 06902 Sophia Antipolis, France; also with the Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544 USA; and also with the GAATI Mathematics Laboratory, University of French Polynesia, 98702 Faaà, French Polynesia (e-mail: samir.perlaza@inria.fr).

H. Vincent Poor is with the Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: poor@princeton.edu).

algorithms as probability distributions over the hypothesis class conditioned on the available training data [16]–[20]. This perspective facilitates both uncertainty quantification and generalization analysis [21]–[24]. Under the statistical perspective, ERM is often posed as an optimization problem regularized by an information-theoretic metric, as a measure of dissimilarity between two distributions. These metrics include the family of *f*-divergences, Rényi divergence, Wasserstein distance, and maximum mean discrepancy [25]–[31]. Among these, the *f*-divergences, first introduced in [32]–[34] and later expanded in [35]–[37], have received particular attention, with one of the most extensively studied cases involving ERM with relative entropy regularization, also known as ERM-RER [38]–[43]. The importance of the ERM-RER problem is a consequence of its solution being a Gibbs probability distribution, highlighting its analytical tractability and deep connections to Bayesian learning [44]–[47], as well as to the Boltzmann distribution in statistical physics [48]–[50]. Remarkably, this holds regardless of whether the reference measure is a probability measure or a *σ*-finite measure, as established in [41]. Other works address the general case of *f*-divergences, known as ERM with *f*-divergence regularization (ERM-*f*DR). The case of discrete sets of models in the ERM-*f*DR problem is explored in [51] and [52], while more general settings are covered in [53] and [1].

Recent works have shown that *f*-divergence regularization can improve the robustness of learning algorithms in the context of distributionally robust optimization (DRO) [54]–[56]. Beyond robustness, the ERM-*f*DR formulation has been applied to analyze the generalization behavior of learning algorithms under specific *f*-divergence regularization [57]–[61]. More recently, this line of research has been extended to general *f*-divergence regularization. It offers insights into how different divergence choices affect learning stability and complexity, via bounds that describe the transition from weak to strong generalization [62]. In deep learning, ERM-*f*DR has been formulated as an *f*-divergence-based maximum a posteriori (MAP) estimation problem [63]–[65], enabling a probabilistic interpretation of regularization that connects with variational inference and stochastic optimization techniques. In these analyses, the dependence between the learning algorithms and the training data is studied through the mutual *f*-information [66]–[68] in order to provide generalization bounds.

### A. Motivation

Together, the developments mentioned above underscore the relevance of the ERM-*f*DR framework in both machine
learning practice and theoretical analysis. ERM-fDR flexibility and close relation to information-theoretic metrics make it a strong candidate for addressing challenges in learning, such as generalization, robustness, and uncertainty quantification. A central focus in existing literature is the ERM-fDR using the relative entropy, also known as the Kullback-Leibler (KL) divergence, as the regularizer. This choice is due to its analytical tractability and strong connections to Bayesian learning [38]–[41]. However, concentrating solely on KL divergence leaves a gap in the literature over the choice of regularizer. For instance, some divergences emphasize tail behavior, others improve robustness to outliers or enhance sensitivity to model misspecification [69]. Hence, extending ERM-fDR theory can enable the principled selection of divergence functions based on desired performance criteria or domain-specific constraints, ultimately offering more control over the trade-off between fit and generalization [70].

A critical bottleneck in both the theoretical analysis and practical implementation of the ERM-fDR solution is that it is generally known only up to a normalization factor [51]–[53]. This poses serious challenges, as for many f-divergences, explicit expressions for such a normalization factor are unknown. In practice, this limitation affects the feasibility of sampling methods from algorithms such as Markov Chain Monte Carlo (MCMC) and rejection sampling. In MCMC, the normalization factor appears in the likelihood ratio, which is required for constructing valid transition probabilities. In rejection sampling, the absence of a normalization constant prevents the definition of an efficient proposal distribution, making sampling impractical. Additionally, the comparison of concentration sets arising from different f-divergence regularizations cannot be meaningfully established without knowing the normalization factor. Even in cases in which a closed-form expression exists, such as with relative entropy (or KL divergence), the normalization factor corresponds to the log-partition function [71]–[73], whose computation is especially difficult. This is because it requires evaluating the empirical risk across the entire support of the reference measure, a task that is known to be #P-hard [74]–[76].

## B. Contributions

This work presents the solution to the ERM-fDR problem under mild conditions on $f$, that is, strict convexity and differentiability. Under these assumptions, the solution to the ERM-fDR problem also solves the minimization of the expected empirical risk subject to an $f$-divergence constraint with respect to a reference probability distribution. The proposed approach broadens the scope of ERM-fDR to encompass a wider range of $f$-divergences beyond those previously treated in the literature, including divergences such as Jensen-Shannon and Hellinger. This work establishes a link between the ERM-fDR solution and its dual optimization counterpart via the Legendre-Fenchel transform. This relationship is significant for two key reasons: First, it demonstrates that the duality gap between the ERM-fDR problem and its dual is zero. This strong duality implies that the optimal value of the ERM-fDR problem evaluated at its solution can be characterized by the value of the corresponding dual problem at its

solution. Second, by exploiting properties of the Legendre-Fenchel transform and applying the implicit function theorem, a nonlinear ordinary differential equation (ODE) is derived for the normalization function. Unlike prior work, which often treats this normalization as an arbitrary real value satisfying certain constraints, this approach yields a tractable expression for it. It is important to note that solving such an ODE depends directly on the choice of $f$, and leaves open the problem for an explicit solution in terms of general $f$-divergences. Then, the properties of the normalization function are analyzed and subsequently used to develop a numerical algorithm capable of approximating the normalization factor under the assumption of an integrable prior $Q$. The properties of the ERM-fDR solution are studied, and general expressions for its expected empirical risk are provided, which recover existing results of specific divergences as well as new results. Furthermore, the analysis establishes a general equivalence principle: under suitable transformations of the empirical risk, distinct ERM-fDR problems associated with different $f$-divergences may yield equivalent learning algorithms. This insight reveals a structural relationship among divergence-based regularization schemes and the formulation of the risk in the learning problem. Numerical examples support the theoretical findings and demonstrate how the choice of $f$-divergence impacts training and test performance. The observed performance of different regularizers indicates that Jensen-Shannon and Hellinger divergences outperform those obtained using relative entropy and reverse relative entropy. Notably, the generalization gap remains small for a wide range of $\lambda$ values, suggesting that appropriate tuning of the regularization parameter can control overfitting while maintaining test accuracy. Overall, this work advances the theoretical foundations of ERM with divergence-based regularization and offers concrete tools for analyzing and implementing robust learning algorithms across a broad spectrum of divergence measures.

## II. PRELIMINARIES

### A. Notation

Let $\Omega$ be an arbitrary subset of $\mathbb{R}^d$, with $d \in \mathbb{N}$, and let $\mathcal{B}(\Omega)$ denote the Borel $\sigma$-field on $\Omega$. The set of probability measures that can be defined upon the measurable space $(\Omega, \mathcal{B}(\Omega))$ is denoted by $\Delta(\Omega)$. Given a probability measure $Q \in \Delta(\Omega)$, the set exclusively containing the probability measures in $\Delta(\Omega)$ that are absolutely continuous with respect to $Q$ is denoted by $\Delta_Q(\Omega)$. That is,

$$ \Delta_Q(\Omega) \triangleq \{P \in \Delta(\Omega) : P \ll Q\}, \quad (1) $$

where the notation $P \ll Q$ stands for the measure $P$ being absolutely continuous with respect to the measure $Q$. The Radon-Nikodym derivative of the measure $P$ with respect to $Q$ is denoted by $\frac{dP}{dQ} : \Omega \to [0, \infty)$. Using this notation, an $f$-divergence is defined as follows

**Definition 1 (f-divergence [32]):** Let $f : [0, \infty) \to \mathbb{R}$ be a convex function with $f(1) = \dot{f}(1) = 0$ and $f(0) \triangleq \lim_{u \to 0^+} f(u)$. Let $P$ and $Q$ be two probability measures on the same measurable space, with $P$ absolutely continuous with
Q. The f-divergence of P with respect to Q, denoted by $D_f(P||Q)$, is

$$D_f(P||Q) \triangleq \int f\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) dQ(\boldsymbol{\theta}). \quad (2)$$

In the case in which the function f in (2) is continuous and differentiable, the derivative of the function f is denoted by

$$\dot{f} : (0, \infty) \to \mathbb{R}. \quad (3)$$

If the inverse of the function $\dot{f}$ exists, it is denoted by

$$\dot{f}^{-1} : \mathbb{R} \to (0, \infty). \quad (4)$$

Note that the function f in (1) can, without loss of generality, be chosen to satisfy

$$\dot{f}(1) = 0. \quad (5)$$

This condition can always be imposed since the f-divergence is invariant under affine transformations of f. Although such a normalization does not affect the value of the divergence, it is essential when comparing solutions associated with different f-divergences, as these are characterized through their derivatives; see Appendix A, Lemma 11. Furthermore, the function $\frac{dP}{dQ}$ in (2) is the Radon-Nikodym derivative of P with respect to Q [77], whose properties are well described in [78] and [72]. The Kullback-Leibler divergence (or relative entropy) of P with respect to Q under the assumption in (5), denoted by $D(P||Q)$, is obtained from (2) when the function f satisfies $f(u) = u \log(u) - u + 1$ (see [79]). More specifically,

$$D(P||Q) = \int \left( \frac{dP}{dQ}(\boldsymbol{\theta}) \log \left( \frac{dP}{dQ}(\boldsymbol{\theta}) \right) - \frac{dP}{dQ}(\boldsymbol{\theta}) \right) dQ(\boldsymbol{\theta}) + 1. \quad (6)$$

## B. The Learning Problem

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 data point, and a dataset is represented by the tuple $((x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)) \in (\mathcal{X} \times \mathcal{Y})^n$. Let the function $h: \mathcal{M} \times \mathcal{X} \to \mathcal{Y}$ be such that the label assigned to a pattern $x \in \mathcal{X}$ according to the model $\boldsymbol{\theta} \in \mathcal{M}$ is $h(\boldsymbol{\theta}, x)$. Then, given a dataset

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

the objective is to obtain a model $\boldsymbol{\theta} \in \mathcal{M}$, such that, for all $i \in \{1, 2, \dots, n\}$, the label assigned to the pattern $x_i$, which is $h(\boldsymbol{\theta}, x_i)$, is “close” to the label $y_i$. This notion of “closeness” is formalized by the function

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

such that the loss or risk induced by choosing the model $\boldsymbol{\theta} \in \mathcal{M}$ with respect to the labeled pattern $(x_i, y_i)$, with $i \in \{1, 2, \dots, n\}$, is $\ell(h(\boldsymbol{\theta}, x_i), y_i)$. The risk function $\ell$ is assumed to be nonnegative and to satisfy $\ell(y, y) = 0$, for all $y \in \mathcal{Y}$.

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

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

The expectation of the empirical risk $\mathbf{L}_z(\boldsymbol{\theta})$ in (9) when $\boldsymbol{\theta}$ is sampled from a probability measure $P \in \Delta(\mathcal{M})$ is determined by the functional $\mathbf{R}_z: \Delta(\mathcal{M}) \to [0, \infty)$, such that

$$\mathbf{R}_z(P) = \int \mathbf{L}_z(\boldsymbol{\theta}) dP(\boldsymbol{\theta}). \quad (10)$$

## III. THE ERM-fDR PRIMAL AND DUAL PROBLEMS

### A. The ERM-fDR Primal Problem

The ERM-fDR problem is parametrized by a probability measure $Q \in \Delta(\mathcal{M})$, a positive real $\lambda$, and a function $f: [0, \infty) \to \mathbb{R}$ that satisfies the conditions in Definition 1. The measure $Q$ is referred to as the reference measure and $\lambda$ as the regularization factor. Given the dataset $\boldsymbol{z} \in (\mathcal{X} \times \mathcal{Y})^n$ in (7), the ERM-fDR problem, with parameters $Q$, $\lambda$ and $f$, consists of the following optimization problem:

$$\min_{P \in \Delta_Q(\mathcal{M})} \mathbf{R}_z(P) + \lambda D_f(P||Q), \quad (11)$$

where the functional $\mathbf{R}_z$ is defined in (10) and the f-divergence $D_f$ is defined in (2). The optimization problem in (11) is closely related to the following optimization problem:

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

$$\text{s.t.} \quad D_f(P||Q) \le \eta, \quad (12b)$$

with $\eta \in [0, \infty)$. The optimization problems in (11) and (12) do not share the same solutions when for all $\boldsymbol{\theta} \in \text{supp } Q$, $\mathbf{L}_z(\boldsymbol{\theta}) = c$ for some $c > 0$ and $\mathbf{L}_z$ in (9). More specifically, the set of solutions to the problem in (12) is $\{P \in \Delta_Q(\mathcal{M}) : D_f(P||Q) \le \eta\}$, while the set of solutions to (11) is the singleton $\{Q\}$. This distinction is mathematically significant but can be ignored in practice, as it arises only when the function $\mathbf{L}_z$ is a constant almost surely with respect to $Q$. In order to avoid the above case, the notion of separable empirical risk functions [41, Definition 5] is adopted.

**Definition 2 (Separable Empirical Risk Function [41]):** The empirical risk function $\mathbf{L}_z$ in (9) is said to be separable with respect to a $\sigma$-finite measure $P \in \Delta(\mathcal{M})$, if there exists a positive real $c > 0$ and two subsets $\mathcal{M}_1$ and $\mathcal{M}_2$ of $\mathcal{M}$ that are nonnegligible with respect to $P$, such that for all $(\boldsymbol{\theta}_1, \boldsymbol{\theta}_2) \in \mathcal{M}_1 \times \mathcal{M}_2$,

$$\mathbf{L}_z(\boldsymbol{\theta}_1) < c < \mathbf{L}_z(\boldsymbol{\theta}_2) < \infty. \quad (13)$$

Essentially, a nonseparable empirical risk function with respect to the measure $Q$ in (11) satisfies

$$Q(\{\boldsymbol{\theta} \in \mathcal{M} : \mathbf{L}_z(\boldsymbol{\theta}) = a\}) = 1, \quad (14)$$

for some $a > 0$. The solutions to the ERM-fDR problems in (11) and (12) are presented under the following assumptions:

(a) The function $f$ is strictly convex and differentiable;

(b) There exists a $\beta$ such that

$$\beta \in \left\{ t \in \mathbb{R} : \forall \boldsymbol{\theta} \in \text{supp } Q, 0 < \dot{f}^{-1}\left(-\frac{t + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) \right\}, \quad (15a)$$

and

$$\int \dot{f}^{-1}\left(-\frac{\beta + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) dQ(\boldsymbol{\theta}) = 1, \quad (15b)$$
where the function $L_z$ is defined in (9); and

(c) The function $L_z$ is separable with respect to the probability measure $Q$.

Under Assumptions (a), (b) and (c), the following theorem shows that the problems in (11) and (12) share the same unique solution subject to a condition on the parameters $\lambda$ in (11) and $\eta$ in (12).

**Theorem 1:** Under Assumptions (a) and (b), the solution to the optimization problem in (11), denoted $P_{\Theta|Z=z}^{(Q,\lambda)} \in \Delta_Q(\mathcal{M})$, is unique, and for all $\theta \in \text{supp } Q$,

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

where the functions $\dot{f}^{-1}$ and $L_z$ are respectively defined in (4) and (9). Moreover, under Assumptions (a), (b), and (c), if $\lambda$ in (11) and $\eta$ in (12) satisfy

$$ D_f(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) = \eta, \quad (17) $$

then, the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) is also the unique solution to the optimization problem in (12).

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

Assumption (b) in Theorem 1, leads to observing that for all $\theta \in \text{supp } Q$,

$$ \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) > 0. \quad (18) $$

This observation leads to the following lemma.

**Lemma 1:** Under Assumptions (a) and (b) in Theorem 1, the probability measures $Q$ and $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) are mutually absolutely continuous.

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

Lemma 1 reveals that the support of the reference measure $Q$ establishes an inductive bias that cannot be overcome, regardless of the choice of $f$-divergence. That is, the support of the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) is identical to the support of the reference measure $Q$. In summary, the use of any $f$-divergence regularization, under Assumptions (a) and (b) in Theorem 1, inadvertently forces the solution to the optimization problem in (11) to coincide with the support of the reference measure $Q$, independently of the training data. This observation has already been pointed out for particular cases. For instance, when the function $f$ is such that $f(u) = u \log(u)$ in [41, Lemma 3]; and $f(u) = -\log(u)$ in [71, Lemma 3]. In general, this observation is particularly important for choosing the reference measure $Q$.

## B. Examples

This section presents the solutions to the optimization problem in (11) for specific choices of the function $f$.

1) **Relative Entropy:** Let the function $f: [0, \infty) \to \mathbb{R}$ be such that $f(u) = u \log(u) - u + 1$. In this case, the resulting $f$-divergence $D_f(P\|Q)$ is the relative entropy of $P$ with respect to $Q$. That is,

$$ D_f(P\|Q) = D(P\|Q), \quad (19) $$

where $D$ is defined in (6). From Theorem 1, it holds that for all $\theta \in \text{supp } Q$,

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

where $\beta$ can be explicitly obtained using (15b), which yields

$$ 1 = \int \exp\left(-\frac{\beta + L_z(\theta)}{\lambda}\right) dQ(\theta) \quad (21) $$

$$ = \exp\left(-\frac{\beta}{\lambda}\right) \int \exp\left(-\frac{L_z(\theta)}{\lambda}\right) dQ(\theta), \quad (22) $$

and thus,

$$ \beta = \lambda \log \left( \int \exp\left(-\frac{L_z(\theta)}{\lambda}\right) dQ(\theta) \right). \quad (23) $$

Substituting (23) into (20) yields

$$ \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\exp\left(-\frac{1}{\lambda}L_z(\theta)\right)}{\int \exp\left(-\frac{1}{\lambda}L_z(\nu)\right) dQ(\nu)}. \quad (24) $$

This result has been independently reported by several authors in [7], [38], [41], [42], [80], and proved via a large variety of methods.

2) **Reverse Relative Entropy:** Let the function $f: [0, \infty) \to \mathbb{R}$ be such that $f(u) = -\log(u) + u - 1$. In this case, the resulting $f$-divergence $D_f(P\|Q)$ is the relative entropy of $Q$ with respect to $P$. That is,

$$ D_f(P\|Q) = D(Q\|P), \quad (25) $$

where $D$ is defined in (6). This result, in contrast to the previous example, justifies referring to $D_f(P\|Q)$ as the *reverse relative entropy*. From Theorem 1, it holds that for all $\theta \in \text{supp } Q$,

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

Note that if the assumption $\dot{f}(1) = 0$ is relaxed and the function $f: [0, \infty) \to \mathbb{R}$ is chosen as $f(u) = -\log(u)$, then the solutions to the optimization problem in (11) satisfy, for all $\theta \in \text{supp } Q$,

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

where, $\tilde{\beta} = \beta + \lambda$. The relaxation of the affine shift is advantageous because, although no closed-form expression for $\beta$ in (26) is available under $\dot{f}(1) = 0$, the regularization parameter $\lambda$ admits a closed-form expression in terms of the modified constant $\tilde{\beta}$. Specifically,

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

which follows from (15b). Note that (28) establishes a one-to-one relation between $\lambda$ and $\beta$. This observation leads to the following

$$ \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{(L_z(\theta) + \tilde{\beta})^{-1}}{\int (L_z(\nu) + \tilde{\beta})^{-1} dQ(\nu)}, \quad (29) $$
which follows from substituting (28) into (27). This result has been previously reported in [71]. Additionally, from (29), the expression in (28) suggests that, for other choices of $f$-divergences, an appropriate selection of the affine shift applied to $f$ may likewise allow $\beta$ to be solved explicitly, while preserving the solution of the underlying optimization problem.

3) **Jeffreys Divergence:** Let the function $f: [0, \infty) \to \mathbb{R}$ be such that $f(u) = u \log(u) - \log(u)$. In this case, the resulting $f$-divergence $D_f(P\|Q)$ is the Jeffreys divergence between $P$ and $Q$, also known as symmetrized relative entropy or symmetrized Kullback-Leibler divergence, which follows from observing that

$$D_f(P\|Q) = D(P\|Q) + D(Q\|P), \quad (30)$$

where $D$ is defined in (6). From Theorem 1, it holds that for all $\theta \in \text{supp } Q$,

$$\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) = \exp\left(W_0\left(\exp\left(\frac{\beta+\lambda+L_z(\theta)}{\lambda}\right)\right) - \frac{\beta+\lambda+L_z(\theta)}{\lambda}\right), (31)$$

where the function $W_0: [0, \infty) \to [0, \infty)$ is the Lambert function, which for a function $g: \mathbb{R} \to \mathbb{R}$ such that $g(u) = u \exp(u)$ satisfies $W_0(g(x)) = x$. The coupling induced by the Lambert function in (31) between the parameters $\beta$ and $\lambda$ prevents the characterization of $\beta$ in closed-form. Hence, $\beta$ must be obtained via numerical methods using

$$1 = \int \exp\left(W_0\left(\exp\left(\frac{\beta+\lambda+L_z(\theta)}{\lambda}\right)\right) - \frac{\beta+\lambda+L_z(\theta)}{\lambda}\right) dQ(\theta), \quad (32)$$

which follows from (15b).

4) **Jensen-Shannon Divergence:** Let the function $f: [0, \infty) \to \mathbb{R}$ be such that $f(u) = u \log(\frac{2u}{u+1}) + \log(\frac{2}{u+1})$. In this case, the resulting $f$-divergence $D_f(P\|Q)$ is the Jensen-Shannon's divergence between $P$ and $Q$, and similarly to the Jeffreys divergence, it is also symmetric, which follows from observing that

$$D_f(P\|Q) = D\left(P\left\|\frac{P+Q}{2}\right\right) + D\left(Q\left\|\frac{P+Q}{2}\right\right), \quad (33)$$

where $D$ is defined in (6). From Theorem 1, it holds that for all $\theta \in \text{supp } Q$,

$$\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) = \frac{1}{2\exp\left(\frac{\beta+L_z(\theta)}{\lambda}\right) - 1}, \quad (34)$$

where $\beta = -\lambda \log(2c)$ and $c > 0$ satisfies the following fixed point equation:

$$c = \frac{1}{\int \frac{1}{\exp\left(\frac{1}{\lambda}L_z(\theta)\right) - c} dQ(\theta)}, \quad (35)$$

which follows from (15b).

5) **Hellinger Divergence:** Let the function $f: [0, \infty) \to \mathbb{R}$ be such that $f(x) = (1 - \sqrt{x})^2$. In this case, the resulting $f$-divergence $D_f(P\|Q)$ is the Hellinger's divergence of $P$ with respect to $Q$, which satisfies

$$D_f(P\|Q) = \int \left(1 - \sqrt{\frac{\mathrm{d}P}{\mathrm{d}Q}(\theta)}\right)^2 dQ(\theta). \quad (36)$$

From Theorem 1, it holds that for all $\theta \in \text{supp } Q$,

$$\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) = \left( \frac{\lambda}{\beta + \lambda + L_z(\theta)} \right)^2, \quad (37)$$

where $\beta$ is chosen to satisfy

$$\int \left( \frac{\lambda}{\beta + \lambda + L_z(\theta)} \right)^2 dQ(\theta) = 1, \quad (38)$$

which follows from (15b).

6) **$\chi^2$ Divergence:** Let the function $f: [0, \infty) \to \mathbb{R}$ be such that $f(x) = x^2 - 1$. In this case, the resulting $f$-divergence $D_f(P\|Q)$ is the Pearson-divergence, also known as the $\chi^2$-divergence between $P$ and $Q$. From Theorem 1, it holds that for all $\theta \in \text{supp } Q$,

$$\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) = -\frac{\beta + L_z(\theta)}{2\lambda}, \quad (39)$$

where $\beta$ satisfies (15b), which implies

$$1 = - \int \left( \frac{\beta}{2\lambda} + \frac{L_z(\theta)}{2\lambda} \right) dQ(\theta), \quad (40)$$

and thus,

$$\beta = -(\lambda + R_z(Q)). \quad (41)$$

Substituting (41) into (39) yields

$$\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) = \frac{\lambda + R_z(Q) - L_z(\theta)}{2\lambda}. \quad (42)$$

From (42), it is easy to see that there exist cases in which Assumption (b) is not met. For instance, if there exists a model $\theta \in \text{supp } Q$ for which $\lambda + R_z(Q) < L_z(\theta)$, then, for such a model $\theta$, it holds that $\dot{f}^{-1}\left(-\frac{\beta+L_z(\theta)}{\lambda}\right) = \frac{\lambda+R_z(Q)-L_z(\theta)}{2\lambda} < 0$, which implies condition (15a) does not hold.

When Assumptions (a) and (b) in Theorem 1 are not met, the solution to the optimization problems in (11) and (12) cannot be obtained from Theorem 1. Moreover, in such a case, nothing can be asserted on whether solutions to these optimization problems exist. In summary, the existence of the solution to the optimization problems in (11) and (12) when Assumptions (a) and (b) in Theorem 1 are not met is still an open problem. Some interesting $f$-divergences do not meet both Assumptions (a) and (b) in Theorem 1, which is the case of the total variation divergence.

7) **Total Variation Divergence:** Let the function $f: [0, \infty) \to \mathbb{R}$ be such that $f(x) = |x - 1|$. The resulting $f$-divergence $D_f(P\|Q)$ is the total variation between $P$ and $Q$. Nonetheless, the function $f$ is not strictly convex and nondifferentiable at 1. Hence, the solution to the optimization problems in (11) and (12) cannot be obtained from Theorem 1.
### C. The ERM-fDR Dual Problem

The duality principle [81, Chapter 5] enables the analysis of the optimization problem in (11) by studying an alternative form, known as the dual problem. In this section, this dual problem is derived using the Legendre-Fenchel transform [81], which is defined below.

**Definition 3 (Legendre-Fenchel transform [81]):** Consider a function $f: \mathcal{I}_1 \to \mathcal{I}_2$, with $\mathcal{I}_i \subseteq \mathbb{R}$, with $i \in \{1, 2\}$. The Legendre-Fenchel transform of the function $f$, denoted by $f^* : \mathcal{J} \to \mathbb{R}$, is

$$f^*(v) = \sup_{u \in \mathcal{I}_1} (vu - f(u)) \quad (43)$$

with

$$\mathcal{J} = \{v \in \mathbb{R} : f^*(v) < \infty\}. \quad (44)$$

Using this notation, consider the following problem:

$$\min_{\beta \in \mathbb{R}} \quad \lambda \int f^* \left( - \frac{\beta + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right) dQ(\boldsymbol{\theta}) + \beta, \quad (45)$$

where the real $\lambda$, the measure $Q$ and the function $f$ are those in (11); and the functions $\mathbf{L}_z$ and $f^*$ are defined in (9) and (43), respectively. An important observation for the analysis of the problem in (45) is that the equality in (16) can be written in terms of the normalization function, introduced in [1] and defined hereunder.

**Definition 4 (Normalization Function):** Let the set $A_{Q,z} \subseteq (0, \infty)$, be the set that contains all regularization factors $\lambda$ for which Assumption (b) in Theorem 1 holds. The normalization function of the problems in (11) and (12), denoted by

$$N_{Q,z} : A_{Q,z} \to B_{Q,z}, \quad (46a)$$

with $B_{Q,z} \subseteq \mathbb{R}$, is such that for all $\lambda \in A_{Q,z}$,

$$\int \dot{f}^{-1} \left( - \frac{N_{Q,z}(\lambda) + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right) dQ(\boldsymbol{\theta}) = 1, \quad (46b)$$

where the functions $\dot{f}^{-1}$ and $\mathbf{L}_z$ are defined in (4) and (9). More specifically, the set $A_{Q,z}$ in (46a) contains the regularization factors $\lambda$ for which the problem in (11) has a solution. The equality in (46b) justifies referring to the function $N_{Q,z}$ as the normalization function, as it ensures that the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) is a probability measure, such that for all $\boldsymbol{\theta} \in \text{supp } Q$,

$$\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) = \dot{f}^{-1} \left( - \frac{N_{Q,z}(\lambda) + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right). \quad (47)$$

The following theorem introduces the solution to the problem in (45).

**Theorem 2:** Under Assumptions (a) and (b) in Theorem 1, the solution to the optimization problem in (45) is $N_{Q,z}(\lambda)$, where the function $N_{Q,z}$ is defined in (46).

*Proof:* Let $G: \mathbb{R} \to \mathbb{R}$ be a function such that

$$G(\beta) = \lambda \int f^* \left( - \frac{\beta + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right) dQ(\boldsymbol{\theta}) + \beta, \quad (48)$$

which is the objective function of the optimization problem in (45). Note that from Assumption (a) in Theorem 1 and

Definition 3, the function $G$ in (48) is a strictly convex function, which satisfies

$$\frac{d}{d\beta} G(\beta) = \frac{d}{d\beta} \left( \lambda \int f^* \left( - \frac{\beta + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right) dQ(\boldsymbol{\theta}) + \beta \right) \quad (49)$$

$$= \lambda \int \frac{d}{d\beta} f^* \left( - \frac{\beta + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right) dQ(\boldsymbol{\theta}) + 1 \quad (50)$$

$$= - \int \dot{f}^* \left( - \frac{\beta + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right) dQ(\boldsymbol{\theta}) + 1, \quad (51)$$

where $\dot{f}^*$ is the derivative of the function $f^*$ in (45); and (50) follows from the dominated convergence theorem [82, Theorem 1.6.9]. Let the solution to the optimization problem in (48) be denoted by $\hat{\beta} \in \mathbb{R}$ and note that the derivative of the function $G$ evaluated at $\hat{\beta}$ is equal to zero, that is

$$\int \dot{f}^* \left( - \frac{\hat{\beta} + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right) dQ(\boldsymbol{\theta}) = 1. \quad (52)$$

From [83, Corollary 23.5.1] and Assumption (a) in Theorem 1, the following equality holds for all $v \in \mathcal{J}$, with $\mathcal{J}$ in (44),

$$\frac{d}{dv} f^*(v) = \dot{f}^*(v) = \dot{f}^{-1}(v), \quad (53)$$

where the functions $\dot{f}^{-1}$ and $\dot{f}^*$ are defined in (4) and (51), respectively. From (52) and (53), it follows that

$$\int \dot{f}^{-1} \left( - \frac{\hat{\beta} + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right) dQ(\boldsymbol{\theta}) = 1, \quad (54)$$

which combined with (46b) and Assumption (b) in Theorem 1 yields

$$N_{Q,z}(\lambda) = \hat{\beta}. \quad (55)$$

Note that $\hat{\beta}$ is unique as it is the minimum of a strictly convex function. This observation completes the proof. ■

The following lemma establishes that the problem in (45) is the dual problem to the ERM-fDR problem in (11) and characterizes the difference between their optimal values, which is often referred to as duality gap [84, Section 8.3].

**Lemma 2:** Under Assumptions (a) and (b) in Theorem 1, the optimization problem in (45) is the dual problem to the ERM-fDR problem in (11). Moreover, the duality gap is zero.

*Proof:* Under Assumption (a) in Theorem 1 and [81, Section 3.3.2], it can be verified that for all $v \in \mathcal{J}$, with $\mathcal{J}$ in (44), the function $f^*$ in (43) satisfies

$$f^*(v) = v \dot{f}^*(v) - f(\dot{f}^*(v)), \quad (56)$$

where the function $\dot{f}^*$ is the same as in (53). From Assumption (a) in Theorem 1 and (53), the Radon-Nikodym derivative

$\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) satisfies for all $\boldsymbol{\theta} \in \text{supp } Q$,

$$\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) = \dot{f}^* \left( - \frac{N_{Q,z}(\lambda) + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right), \quad (57)$$
where the functions $L_z$ and $N_{Q,z}$ are defined in (9) and (46), respectively. Then, from (56) and (57), it holds that for all $\theta \in \text{supp } Q$,

$$ 
\begin{aligned}
& f^*\left(-\frac{N_{Q,z}(\lambda)+L_z(\theta)}{\lambda}\right) \\
& =-\frac{N_{Q,z}(\lambda)+L_z(\theta)}{\lambda} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) - f\left(\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta)\right). \quad (58)
\end{aligned}
$$

Rearranging (58) yields

$$ 
\begin{aligned}
& L_z(\theta) + \lambda f\left(\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta)\right) \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \\
& = -\lambda f^*\left(-\frac{N_{Q,z}(\lambda)+L_z(\theta)}{\lambda}\right) \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) - N_{Q,z}(\lambda). \quad (59)
\end{aligned}
$$

Taking the expectation of both sides of (59) with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) yields

$$ 
\begin{aligned}
& R_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) + \lambda D_f\left(P_{\Theta|Z=z}^{(Q,\lambda)}\|Q\right) \\
& = -\lambda \int f^*\left(-\frac{N_{Q,z}(\lambda)+L_z(\theta)}{\lambda}\right) dQ(\theta) - N_{Q,z}(\lambda). \quad (60)
\end{aligned}
$$

Using Theorem 1 and Theorem 2 in the left-hand and right-hand sides of (60), respectively, yields

$$ 
\begin{aligned}
& \min_{P \in \Delta_Q(\mathcal{M})} R_z(P) + \lambda D_f(P \| Q) \\
& = \max_{\beta \in \mathbb{R}} -\lambda \int f^*\left(-\frac{\beta + L_z(\theta)}{\lambda}\right) dQ(\theta) - \beta. \quad (61)
\end{aligned}
$$

The proof that the optimization problem in (45) is the dual to the ERM-fDR problem in (11) follows from (61) and [85, Theorem 1, Section 8.4]. The zero duality gap is established by the equality in (61), which completes the proof. ■

Lemma 2 builds on [83, Theorem 29.1] and is applied throughout the paper. The zero duality gap ensures strong duality, meaning the optimal value of the dual variables can be used to recover the primal optimal measure. However, solving the dual problem in (45) remains equally challenging, as the solution must satisfy the constraints of Assumption (b) in Theorem 1.

# IV. ANALYSIS OF THE NORMALIZATION FUNCTION

## A. Implicit Characterization via Functional Properties

The purpose of this section is to characterize the function $N_{Q,z}$ and the sets $\mathcal{A}_{Q,z}$ and $\mathcal{B}_{Q,z}$ in (46). Given a real $\delta \in [0, \infty)$, consider the Rashomon set $\mathcal{L}_z(\delta)$, which is defined as follows

$$ \mathcal{L}_z(\delta) \triangleq \{\theta \in \mathcal{M} : L_z(\theta) \leq \delta\}, \quad (62) $$

where the function $L_z$ is defined in (9). Consider also the real numbers $\delta_{Q,z}^*$ and $\lambda_{Q,z}^*$ defined as follows

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

and

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

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

$$ \mathcal{L}_{Q,z}^* \triangleq \{\theta \in \mathcal{M} : L_z(\theta) = \delta_{Q,z}^*\}. \quad (65) $$

Using this notation, the following theorem introduces one of the main properties of the function $N_{Q,z}$.

**Theorem 3:** The normalization function $N_{Q,z}$ in (46), under the assumption that the function $f$ is twice differentiable, is continuous within the interior of $\mathcal{A}_{Q,z}$ in (46a) and for all $\lambda \in \mathcal{A}_{Q,z}$, the value $N_{Q,z}$ is unique.

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

Theorem 3 allows obtaining an implicit expression for the normalization function in the form of a nonlinear ordinary differential equation, which is formalized by the following theorem.

**Theorem 4:** The function $N_{Q,z}$ in (46), under the assumption that the function $f$ in (46) is twice differentiable, satisfies for all $\lambda \in \mathcal{A}_{Q,z}$,

$$ N_{Q,z}(\lambda) = \lambda \frac{d}{d\lambda} N_{Q,z}(\lambda) - R_z(P), \quad (66) $$

where the functional $R_z$ is defined in (10) and the probability measure $P \in \Delta_Q(\mathcal{M})$ satisfies for all $\theta \in \text{supp } Q$,

$$ \frac{dP}{dQ}(\theta) = \frac{\left( \ddot{f}\left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) \right)^{-1}}{\int \left( \ddot{f}\left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\nu) \right) \right)^{-1} dQ(\nu)}; \quad (67) $$

the function $\ddot{f}$ is the second derivative of the function $f$, and the measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is that in (16).

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

The results of Theorem 3 and Theorem 4 do not yield an explicit expression that can be directly computed for the normalization function (46). Instead, these theorems establish key properties of the normalization function, which can be used to characterize further aspects of the function and to motivate approximation methods for the normalization parameter required in order to obtain the solution to the optimization problem (11).

**Lemma 3:** Under the assumption that the function $f$ is twice differentiable, and the function $\dot{f}^{-1}$ is log convex (see [81, Definition 3.5.1]). Then, the normalization function $N_{Q,z}$ in (46) is monotonically decreasing.

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

The continuity and monotonicity exhibited by the function $N_{Q,z}$ allow the following characterization of the set $\mathcal{A}_{Q,z}$.

**Lemma 4:** The set $\mathcal{A}_{Q,z}$ in (46a) is either empty or a convex subset of $(0, \infty)$, that satisfies

$$ (\lambda_{Q,z}^*, \infty) \subseteq \mathcal{A}_{Q,z} \subseteq [\lambda_{Q,z}^*, \infty), \quad (68) $$

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

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

Lemma 4 highlights two facts. First, the set $\mathcal{A}_{Q,z}$ is a convex subset of positive reals. Second, if there exists a solution to the optimization problems in (11) and (12) for
some $\lambda > 0$, then there exists a solution to such problems when $\lambda$ is replaced by $\bar{\lambda} \in (\lambda, \infty)$.

The following lemma presents a case in which the set $\mathcal{A}_{Q,z}$ in (46a) can be fully characterized.

**Lemma 5:** If the function $\dot{f}^{-1}$ in (16) is strictly positive, then the set $\mathcal{A}_{Q,z}$ is identical to $(0, \infty)$.

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

The condition of Lemma 5 is satisfied by the *Kullback-Leibler Divergence* (Section III-B1), *Jeffreys Divergence* (Section III-B3), and *Hellinger Divergence* (Section III-B5). For those cases, it holds that $\mathcal{A}_{Q,z} = (0, \infty)$. Alternatively, the *Reverse Relative Entropy Divergence* (Section III-B2), *Jensen-Shannon Divergence* (Section III-B4), and $\chi^2$ Divergence (Section III-B6) do not satisfy the condition of Lemma 5.

## B. Efficient Approximation via Root-finding

A major bottleneck in statistical learning is formed by the computational challenges associated with: (i) Evaluating expectations with respect to the prior $Q$ (see, for example, (15b)), and (ii) Determining the normalization factor $\beta$ in (16) for implementing the resulting algorithms. This subsection discusses the significance of the continuity and monotonicity properties of the normalization function $N_{Q,z}$ in (46) and their practical implications towards the challenges in (ii), under the assumption that expectations with respect to the prior $Q$ are computationally tractable. For certain choices of $f$, an explicit expression for the normalization function cannot be obtained solely in terms of the regularization factor $\lambda$ as shown in [43]. However, the bijection property of $N_{Q,z}$ resulting from Theorem 3 implies that finding the inverse of the normalization function is enough for calculations. For example, if $f(x) = -\log x$, the inverse normalization function $N_{Q,z}^{-1}$ satisfies

$$N_{Q,z}^{-1}(\beta) = \left( \int \frac{1}{L_z(\theta) + \beta} dQ(\theta) \right)^{-1}, \quad (69)$$

as shown in [43, Theorem 1], which suffices to solve the optimization problem in (11). Nevertheless, for certain $f$-divergences, neither the normalization function nor its inverse can be explicitly obtained. An example of such a case is the Hellinger divergence (see Example III-B5). An alternative approach is a numerical approximation of the function $N_{Q,z}$ leveraging the properties from Theorem 3 and Lemma 4. The following algorithm captures this intuition.

### Algorithm 1 Root-finding for $N_{Q,z}(\lambda)$

**Input:** $L_z: \mathcal{M} \to [0, \infty)$, $Q, f: [0, \infty) \to \mathbb{R}$, $\lambda > 0$, $\delta_{Q,z}^*$, tolerance $\epsilon > 0$, max iterations $N_{\max}$

**Output:** $\beta$ satisfying $\left| \int \dot{f}^{-1} \left( -\frac{L_z(\theta) + \beta}{\lambda} \right) dQ(\theta) - 1 \right| \le \epsilon$
**Initialization:**

1: $b_{\text{low}} \leftarrow \delta_{Q,z}^* - \lambda \dot{f}(0)$, $b_{\text{high}} \leftarrow \lambda$

2: $n \leftarrow 0$, $b \leftarrow \frac{1}{2}(b_{\text{low}} + b_{\text{high}})$

3: $I \leftarrow \int \dot{f}^{-1} \left( -\frac{L_z(\theta) + b}{\lambda} \right) dQ(\theta)$

**Root-Finding Process:**

4: **while** $|I - 1| > \epsilon$ **and** $n < N_{\max}$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $I > 1$ **then**

6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$b_{\text{high}} \leftarrow b$

7: &nbsp;&nbsp;&nbsp;&nbsp;**else**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$b_{\text{low}} \leftarrow b$

9: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$b \leftarrow \frac{1}{2}(b_{\text{low}} + b_{\text{high}})$

11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$I \leftarrow \int \dot{f}^{-1} \left( -\frac{L_z(\theta) + b}{\lambda} \right) dQ(\theta)$, $n \leftarrow n + 1$

12: **end while**

13: **return** $\beta = b$

The algorithm leverages the strict monotonicity of $N_{Q,z}$, established in Theorem 3, along with the uniqueness of the ERM-$f$DR solution shown in Theorem 1. Together, these properties imply that the integral in (15b) is strictly monotonic in $\beta$, with a unique root that determines whether $\beta$ should increase or decrease. In Section VII, this Algorithm 1 is used to compute, for each $\lambda$, the corresponding $\beta$ for different $f$-divergence regularizers.

## V. PROPERTIES OF THE ERM-$f$DR SOLUTION

This section studies the properties of the solution to the ERM-$f$DR problem in (11) and (12). First, note that from Theorem 1 models resulting in lower empirical risks correspond to greater values of the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16). The following lemma formalizes this observation.

**Lemma 6:** 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 (9), the Radon-Nikodym derivative in (16) satisfies

$$\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta_2) \le \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta_1), \quad (70)$$

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

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

Lemma 6 aligns with the intuition of assigning greater probability mass to models that achieve lower risk on the dataset $z$. Second, the Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) is always finite and strictly positive. This observation is formalized by the following lemma.

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

$$0 < \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \le \dot{f}^{-1}\left(-\frac{\delta_{Q,z}^* + \beta}{\lambda}\right) < \infty, \quad (71)$$

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 J. ■
The next lemma shows that the expected empirical risk induced by the solution to the optimization problems in (11) and (12), $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (16), monotonically decreases with respect to the regularization factor $\lambda$. This observation is formalized by the following lemma.

**Lemma 8:** For all $(\lambda_1, \lambda_2) \in (0, \infty)^2$, such that $\lambda_1 < \lambda_2$, the probability measures $P_{\Theta|Z=z}^{(Q,\lambda_1)}$ and $P_{\Theta|Z=z}^{(Q,\lambda_2)}$ in (16) satisfy

$$ \delta_{Q,z}^* \le R_z(P_{\Theta|Z=z}^{(Q,\lambda_1)}) \le R_z(P_{\Theta|Z=z}^{(Q,\lambda_2)}) \le R_z(Q), \quad (72) $$

where $\delta_{Q,z}^*$ is defined in (63), the functional $R_z$ is defined in (10) and the equalities simultaneously hold if and only if $L_z$ in (9) is nonseparable with respect to the probability measure $Q$.

**Proof:** The proof follows from the preliminary results in Lemma 17 and Lemma 18, presented in Appendix A. ■

From [83, Corollary 23.5.1], given a convex function $f$, the derivative of the Legendre-Fenchel transform of $f^*$ in Definition 3, denoted by $f^* : \mathcal{J} \to \mathcal{I}_1$, with the sets $\mathcal{I}_1$ and $\mathcal{J}$ in Definition 3, satisfies for all $v \in \mathcal{J}$,

$$ \frac{d}{dv} f^*(v) = \dot{f}^*(v) = \dot{f}^{-1}(v), \quad (73) $$

with the function $\dot{f}^{-1}$ defined in (4). This observation leads to the following corollary.

**Corollary 9:** The Radon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ in (16) satisfies for all $\theta \in \text{supp } Q$,

$$ \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \dot{f}^*\left(-\frac{L_z(\theta) + N_{Q,z}(\lambda)}{\lambda}\right), \quad (74) $$

where the functions $L_z$, $N_{Q,z}$ and $\dot{f}^*$ are defined in (9), (46) and (73), respectively.

Furthermore, from [83, Corollary 23.5.1] and (73), it follows that for all $u \in \mathcal{I}_1$,

$$ f^*(\dot{f}(u)) = \dot{f}(u)u - f(u). \quad (75) $$

The following theorem specifies the value of the objective function in the optimization problem defined in (11), evaluated at the solution $P_{\Theta|Z=z}^{(Q,\lambda)}$ given in (16).

**Theorem 5:** Let the function $g: [0, \infty) \to \mathbb{R}$ be $g(u) = \frac{1}{u}f(u)$, with $f$ in (11). The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies

$$ \begin{aligned} & R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D_f(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \\ &= -\lambda \int f^*\left(-\frac{L_z(\theta) + N_{Q,z}(\lambda)}{\lambda}\right) dQ(\theta) - N_{Q,z}(\lambda), \end{aligned} \quad (76) $$

and

$$ \begin{aligned} & R_z(Q) + \lambda \int g\left(\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta)\right) dQ(\theta) \\ &= -\lambda \int f^*\left(-\frac{L_z(\theta) + N_{Q,z}(\lambda)}{\lambda}\right) \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) dQ(\theta) \\ & \quad - N_{Q,z}(\lambda), \end{aligned} \quad (77) $$

where $f^*$ is the Legendre-Fenchel transform of $f$ (see Definition 3); the functions $L_z$ and $N_{Q,z}$ are defined in (9) and (46), respectively; and the functional $R_z$ is defined in (10).

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

Note that the function $g$ in (77) is not necessarily a convex function and thus it may not induce an $f$-divergence as in Definition 1. Additionally, Theorem 5 provides an upper bound for the expected empirical risk in terms of the normalization function. This is formalized by the following lemma.

**Lemma 10:** The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies

$$ \begin{aligned} & R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D_f(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \\ & \le -\lambda f^*\left(-\frac{1}{\lambda} R_z(Q) - \frac{N_{Q,z}(\lambda)}{\lambda}\right) - N_{Q,z}(\lambda), \end{aligned} \quad (78) $$

where the functions $R_z$ and $N_{Q,z}$ are defined in (10) and (46), respectively. The equality holds if and only if the Legendre-Fenchel transform of $f$ is a linear function.

**Proof:** The proof follows from the fact that $f^*$ is strictly convex and using Jensen inequality in (76). ■

The following examples show Theorem 5 and Lemma 10 for specific choices of $f$-divergence regularization, recovering existing results as well as yielding new insights.

### Relative Entropy

Let the function $f: [0, \infty) \to \mathbb{R}$ be such that $f(u) = u \log(u) - u + 1$, and note that the Legendre-Fenchel transform of the function $f$ satisfies

$$ f^*(v) = \exp(v) - 1. \quad (79) $$

Furthermore, under relative entropy regularization, the normalization function is directly related to the cumulant generating function $K_{Q,z}: (0, \infty) \to \mathbb{R}$,

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

introduced in [41, Eq. (22)]. The relation of the normalization and cumulant generating function is such that for all $\lambda \in A_{Q,z}$, with $A_{Q,z}$ in (46a), the function $N_{Q,z}$ satisfies that

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

where (81) follows from (23), and (81) follows from the definition of $K_{Q,z}$ in (80). Substituting (79) and (81) into (76) yields

$$ \begin{aligned} & R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D_f(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \\ &= -\lambda \int \left( \exp\left(-\frac{N_{Q,z}(\lambda) + L_z(\theta)}{\lambda}\right) - 1 \right) dQ(\theta) - N_{Q,z}(\lambda) \end{aligned} \quad (82) $$

$$ = \lambda - \lambda \int \frac{\exp\left(-\frac{1}{\lambda}L_z(\theta)\right)}{\int \exp\left(-\frac{1}{\lambda}L_z(\nu)\right) dQ(\nu)} dQ(\theta) - N_{Q,z}(\lambda) \quad (83) $$

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

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

This result has been previously reported by other authors in [80, Lemma 3] and [41, Lemma 20] for the case of relative entropy regularization. From (77) and (79), the expected
empirical risk induced by the reference measure $Q$ in (11) satisfies that

$$
\begin{align}
R_z(Q) &= -\lambda \int \left( g \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) - \dot{g} \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) \right) dP_{\Theta|Z=z}^{(Q,\lambda)} - N_{Q,z}(\lambda) \tag{86} \\
&= -\lambda \int \left( \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) f \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) - \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) f^* \left( -\frac{L_z(\theta) + N_{Q,z}(\lambda)}{\lambda} \right) \right) dQ(\theta) \nonumber \\
&\quad - N_{Q,z}(\lambda) \tag{87}
\end{align}
$$

$$
\begin{align}
&= -\lambda \int \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \exp\left(-\frac{L_z(\theta) + N_{Q,z}(\lambda)}{\lambda} - 1\right) dQ(\theta) \nonumber \\
&\quad -\lambda \int \log\left(\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta)\right) dQ(\theta) - N_{Q,z}(\lambda) \tag{88}
\end{align}
$$

$$
\begin{align}
&= \lambda \int \log \left( \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta)} \right) dQ(\theta) + \lambda - \lambda K_{Q,z} \left( -\frac{1}{\lambda} \right) \nonumber \\
&\quad - \lambda \int \frac{\exp\left(-\frac{L_z(\theta)}{\lambda} - K_{Q,z}\left(-\frac{1}{\lambda}\right)\right)}{\exp\left(-\frac{L_z(\theta)}{\lambda} - K_{Q,z}\left(-\frac{1}{\lambda}\right)\right)} dQ(\theta) \tag{89}
\end{align}
$$

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

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

where the function $g$ in (86) is defined in Theorem 5, (87) follows from (73); (88) follows from (79); and (89) follows from (81). Rearranging the terms in (91) yields

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

where the function $K_{Q,z}$ is defined in (80). This result has also been reported in [41, Lemma 20]. Furthermore, the difference of (85) and (91) yields,

$$
\begin{align}
R_z(Q) - R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) & \nonumber \\
&= \lambda \left( D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) + D(Q \| P_{\Theta|Z=z}^{(Q,\lambda)}) \right), \tag{93}
\end{align}
$$

which appeared first in [41, Corollary 3]. Then, substituting (79) and (81) into Lemma 10 yields

$$
\begin{align}
& R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) + \lambda D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \nonumber \\
& < -\lambda \exp\left(-\frac{R_z(Q) + N_{Q,z}(\lambda)}{\lambda}\right) - N_{Q,z}(\lambda) \tag{94}
\end{align}
$$

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

where the function $K_{Q,z}$ is defined in (80). This result has been previously reported by several authors in [41, Lemma 20] and [80, Lemma 3].

Reverse Relative Entropy

Let the function $f : [0, \infty) \to \mathbb{R}$ be such that $f(u) = -\log(u) + u - 1$, and note that the Legendre-Fenchel transform of the function $f$ satisfies

$$
f^*(t) = -\log(1-t). \tag{96}
$$

Substituting (96) into (76) yields

$$
\begin{align}
R_z \left( P_{\Theta|Z=z}^{(Q,\lambda)} \right) & = \lambda \mathrm{D} \left( Q \| P_{\Theta|Z=z}^{(Q,\lambda)} \right) - N_{Q,z}(\lambda) \nonumber \\
& \quad - \lambda \int \left( -\log \left( \frac{N_{Q,z}(\lambda) + L_z(\theta)}{\lambda} \right) - 1 \right) dQ(\theta) \tag{97}
\end{align}
$$

$$
\begin{align}
&= \lambda \mathrm{D} \left( Q \| P_{\Theta|Z=z}^{(Q,\lambda)} \right) + \lambda - N_{Q,z}(\lambda) \nonumber \\
&\quad - \lambda \int \log \left( \frac{\lambda}{N_{Q,z}(\lambda) + L_z(\theta)} \right) dQ(\theta) \tag{98}
\end{align}
$$

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

$$
\begin{align}
&= \lambda \mathrm{D} \left( Q \| P_{\Theta|Z=z}^{(Q,\lambda)} \right) - \lambda \mathrm{D} \left( Q \| P_{\Theta|Z=z}^{(Q,\lambda)} \right) + \lambda - N_{Q,z}(\lambda) \tag{100} \\
&= \lambda - N_{Q,z}(\lambda). \tag{101}
\end{align}
$$

This result has been previously reported in [71, Lemma 3], and characterizes the expected empirical risk with only the regularization factor and normalization function. As in the previous example, from (77) and the assumption that the Legendre-Fenchel transform of $f$ leads to (96), the expected empirical risk induced by the reference measure $Q$ in (11) satisfies that

$$
\begin{align}
R_z(Q) &= -\lambda \int g \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) - N_{Q,z}(\lambda) \nonumber \\
&\quad -\lambda \int \dot{g} \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \tag{102}
\end{align}
$$

$$
\begin{align}
&= -\lambda \int \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) f \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) dQ(\theta) - N_{Q,z}(\lambda) \nonumber \\
&\quad - \lambda \int \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) f^* \left( -\frac{L_z(\theta) + N_{Q,z}(\lambda)}{\lambda} \right) dQ(\theta) \tag{103}
\end{align}
$$

$$
\begin{align}
&= -\lambda \int \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \log \left( \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \right) dQ(\theta) - N_{Q,z}(\lambda) \nonumber \\
&\quad - \lambda \int \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \left( -\log\left(\frac{L_z(\theta) + \lambda + N_{Q,z}(\lambda)}{\lambda}\right) \right) \nonumber
\end{align}
$$
$$
\begin{align}
& -1) \, dQ(\boldsymbol{\theta}) \tag{104} \\
&= -\lambda \int \frac{dQ}{dP_{\boldsymbol{\Theta}|\boldsymbol{Z}=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) \log \left( \frac{dQ}{dP_{\boldsymbol{\Theta}|\boldsymbol{Z}=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) \right) dQ(\boldsymbol{\theta}) \nonumber \\
&\quad +\lambda \int \frac{dQ}{dP_{\boldsymbol{\Theta}|\boldsymbol{Z}=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}) \nonumber \\
&\quad +\lambda \int \frac{dQ}{dP_{\boldsymbol{\Theta}|\boldsymbol{Z}=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) \log \left( \frac{dQ}{dP_{\boldsymbol{\Theta}|\boldsymbol{Z}=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) \right) dQ(\boldsymbol{\theta}) \nonumber \\
&\quad -N_{Q,z}(\lambda) \tag{105}
\end{align}
$$

$$
= \lambda \int \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) dQ(\theta) - N_{Q,z}(\lambda), \quad (106)
$$

where (103) follows from (75); and (104) follows from (96).
The importance of (106) is that it complements the previous
work in [71] by providing a new expression to compute
the difference between the empirical risk introduced by the
measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) and the reference measure $Q$ in terms
of the Radon-Nikodym derivative as follows:

$$
R_z(Q) - R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) = \lambda \int \left( \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) - 1 \right) dQ(\theta), (107)
$$

which follows from taking the difference between (101)
and (106). Note that (107) complements the work in [43],
where only (101) was known, and thus highlighting the value
of Theorem 5 to the existing body of work.

Then, substituting (96) into Lemma 10 yields

$$
\begin{align}
& R_z \left( P_{\Theta|Z=z}^{(Q,\lambda)} \right) + \lambda D \left( Q \| P_{\Theta|Z=z}^{(Q,\lambda)} \right) \nonumber \\
& < \lambda \log \left( \frac{\lambda}{R_z(Q) + N_{Q,z}(\lambda)} \right) + \lambda - N_{Q,z}(\lambda). \tag{108}
\end{align}
$$

The upper bound derived in (108), in conjunction with (101),
can be equivalently expressed as a lower bound on the dif-
ference between the expected empirical risks of the reference
measure $Q$ and the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$. More specif-
ically,

$$
\begin{align}
& R_z(Q) - R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) \nonumber \\
& > \lambda \left( \exp\left(\mathrm{D}\left(Q \| P_{\Theta|Z=z}^{(Q,\lambda)}\right)\right) - 1 \right), \tag{109}
\end{align}
$$

where $R_z$ is defined in (10). This lower bound has been
previously established in [43, Lemma 18] for the specific
setting of reverse relative entropy regularization.

VI. EQUIVALENCE OF THE *f*-REGULARIZATION VIA
TRANSFORMATION OF THE EMPIRICAL RISK

This section shows that given two strictly convex and
differentiable functions *f* and *g* that satisfy the conditions in
Definition 1, there exists a function *r* : [0, ∞) → R, such that
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 r(\mathbf{L}_z(\boldsymbol{\theta})) dP(\boldsymbol{\theta}) + \lambda D_g(P \| Q), \quad (110)
$$

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

*Theorem 6:* Let *f* and *g* be two strictly convex and differ-
entiable functions satisfying the conditions in Definition 1. If
the problem in (11) possesses a solution, then

$$
\begin{align*}
& \arg \min_{P \in \Delta_Q(\mathcal{M})} \int \mathbf{L}_z(\boldsymbol{\theta}) \, dP(\boldsymbol{\theta}) + \lambda D_f(P \| Q) \\
& = \arg \min_{P \in \Delta_Q(\mathcal{M})} \int r(\mathbf{L}_z(\boldsymbol{\theta})) \, dP(\boldsymbol{\theta}) + \lambda D_g(P \| Q), \quad (111)
\end{align*}
$$

where the function $r: [0, \infty) \to \mathbb{R}$ is such that

$$
r(t) = -\lambda \dot{g} \left( \dot{f}^{-1} \left( -\frac{N_{Q,z}(\lambda) + t}{\lambda} \right) \right) - c, \quad (112)
$$

with $N_{Q,z}$ being the normalization function defined in (46)
for the optimization problem in (11), and $c \in \mathbb{R}$ is a constant.

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

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

Theorem 6 establishes an equivalence between two ERM problems, each subject to a different *f*-divergence regularization. This equivalence holds whenever the divergences are defined by strictly convex and differentiable functions. Theorem 6 extends the earlier result in [43, Theorem 3] in two key aspects. First, it generalizes the result to all strictly convex and differentiable *f*-divergences. Second, and more importantly, it establishes the equivalence in both directions, whereas the previous result only proved the direction from reverse relative entropy to relative entropy.

The following examples illustrate the equivalence between
two *f*-divergence regularizations.

*Example 1:* Consider the optimization problems in (11) and (110) with $f(u) = -\log(u) + u - 1$ and $g(u) = u \log(u) - u + 1$, respectively. Under the current assumptions, the objective of this example is to demonstrate the equivalence of the solutions to the optimization problems in (11) and (110). Denote by $\hat{P}_{\Theta|Z=z}^{(Q,\lambda)}$ the solution to the optimization problem in (110). From Theorem 1, it follows that for all $\theta \in \text{supp } Q$,

$$
\frac{d\hat{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda}{r(\mathbf{L}_z(\theta)) + \lambda + \beta}, \quad (113)
$$

where the function *r* is defined in (112) and under the
assumptions of this example satisfies for all *θ* ∈ *supp* *Q*,

$$
\begin{align}
& r(\mathbf{L}_z(\boldsymbol{\theta})) \nonumber \\
&= \frac{\lambda}{\exp\left(-\frac{\mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) - \log\left(\int \exp\left(-\frac{\mathbf{L}_z(\boldsymbol{\nu})}{\lambda}\right) dQ(\boldsymbol{\nu})\right)} - \lambda - \beta. \tag{114}
\end{align}
$$

Substituting (114) into (113) yields

$$
\frac{d\hat{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\exp(-\frac{1}{\lambda}\mathbf{L}_z(\theta))}{\int \exp(-\frac{1}{\lambda}\mathbf{L}_z(\nu)) dQ(\nu)}, \quad (115)
$$

which is the solution to the optimization problem in (11)
presented in Section III-B1.

*Example 2:* Consider the optimization problems in (11) and (110) with $f(u) = u \log(u) - u + 1$ and $g(u) = - \log(u) + u - 1$, respectively. Under the current assumptions, the objective of this example is to demonstrate the converse equivalence for the optimization problems in (11) and (110).
<figure><img src="image_3.png" /><figcaption>Fig. 1. Representation of the empirical risk transformation from the f-divergence induced by $f(u) = -\log(u)+u-1$ and the g-divergence induced by $g(u) = u \log(u) - u + 1$.</figcaption></figure>

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

$$ \frac{\mathrm{d}\hat{P}_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) = \frac{\exp\left(-\frac{r(L_z(\theta))}{\lambda}\right)}{\int \exp\left(-\frac{r(L_z(\nu))}{\lambda}\right) dQ(\nu)}, \quad (116) $$

where the function $r$ is defined in (112) and under the assumptions of this example satisfies for all $\theta \in \text{supp } Q$,

$$ r(L_z(\theta)) = \lambda \log(N_{Q,z}(\lambda) + \lambda + L_z(\theta)). \quad (117) $$

Substituting (117) into (116) yields

$$ \frac{\mathrm{d}\hat{P}_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) = \frac{\lambda}{\beta + \lambda + L_z(\theta)}, \quad (118) $$

which is the solution to the optimization problem in (11) presented in Section III-B2.

An important distinction exists between the equivalence result established in Example 1 and the log expected empirical risk in [43]. While the latter demonstrated equivalence specifically between relative entropy regularization and reverse relative entropy regularization, Theorem 6 extends this result to the class of f-divergences satisfying Assumptions (a) and (b) in Theorem 1. Moreover, the present equivalence holds bidirectionally, representing a significant generalization beyond previous work.

## VII. NUMERICAL EXAMPLES

In machine learning, the generalization error quantifies how well a learning algorithm performs on unseen data [21]. More specifically, it reflects how effectively a probability measure (an algorithm) concentrates on models that correctly label test data points. Recent work has shown that the sensitivity of the optimization problem in (11) is closely tied to generalization performance [41, Theorem 16]; see also [21], [60], [86], and [58]. Thus, the remaining of this section focuses on the sensitivity of algorithms arising from ERM-fDR problems. A probability measure $P \in \Delta_Q(\mathcal{M})$, which may represent a learning algorithm, exhibits higher generalization error when

it is more sensitive to perturbations in the training data. This increased sensitivity suggests overfitting to the training set. See [18] and [60].

To illustrate the impact of different f-divergence regularizations in ERM-fDR, the problem of classifying two handwritten digits from the MNIST dataset of handwritten digits from 0 to 9 [87] is studied. The dataset consists of 60,000 training images and 10,000 test images. Among these, 12,183 training images and 1,986 test images correspond to the digits six and seven, which form the focus of our binary classification task. Each image is a 28 × 28 grayscale matrix with pixel values in [0, 1]$^{28×28}$. To reduce computational complexity, images are preprocessed following the procedure described in Appendix M. The ERM-fDR problem defined in (11) is evaluated, using the following regularization choices: relative entropy (ERM-RER Type-I), reverse relative entropy (ERM-RER Type-II), Jensen-Shannon, and Hellinger divergences, as specified in (24), (29), (34), and (37). The experimental setup assumes the following:

(i) The model space is defined as $\mathcal{M} = [-50, 50]^2$;

(ii) The input space $\mathcal{X}$ consists of HOG (Histogram of Oriented Gradients) feature vectors extracted from the images of digits six and seven, so that $\mathcal{X} \subset \mathbb{R}^{1296}$;

(iii) The label space is $\mathcal{Y} = \{6, 7\}$;

(iv) The reference measure $Q$ is a uniform probability measure on $\mathcal{M}$;

(v) The loss function $h$ in (9) is defined as

$$ h(\theta, x) = \begin{cases} 6 & \text{if } 0 < (xW)\theta, \\ 7 & \text{if } 0 > (xW)\theta, \end{cases} \quad (119) $$

where the matrix $W$ is defined in (448) in Appendix M;

(vi) The loss function $\ell$ in (8) satisfies

$$ \ell(h(\theta, x), y) = \mathbb{1}_{\{h(\theta, x) \neq y\}}, \quad (120) $$

For the training of each ERM-fDR algorithm, 8,100 samples are drawn uniformly at random from the training images to construct the training dataset $z_1$. Likewise, 1,300 samples are drawn from the test images to form the test dataset $z_2$. This sampling procedure is repeated independently over 100 iterations.

<figure><img src="image_4.png" /><figcaption>Fig. 2. 28 × 28 Image of a handwritten 6 from MNIST dataset.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 3. 28 × 28 Image of a handwritten 7 from MNIST dataset.</figcaption></figure>

Figure 4 illustrates the training expected risk $R_{z_1}(P_{\Theta|Z=z_1}^{(Q,\lambda)})$ for different choices of f-divergence in the ERM-fDR framework, computed over 100 independent iterations. Among the f-divergences compared, the solution obtained using the reverse relative entropy (ERM-RER Type-II) yields the highest training expected risk. This behavior is expected, as reverse KL divergence is known to have heavier tails, based on the work in [43], which results in a broader
<figure><img src="image_6.png" /><figcaption>Fig. 4. Average Training Error: average of the expected empirical risks $R_{z_1}(P^{(Q,\lambda)}_{\Theta|Z=z_1})$, computed for four different f-divergences: relative entropy, reverse relative entropy, Jensen-Shannon divergence, and Hellinger divergence defined in (19), (25), (33), and (36), respectively. The results are the average of 100 random partitions of the training datasets.</figcaption></figure>

allocation of probability mass over supp $Q$ compared to the classical relative entropy (ERM-RER Type-I) solutions. In contrast, the Hellinger and Jensen-Shannon divergences result in significantly lower training risks, even outperforming the ERM-RER Type-I. This suggests that both Hellinger and Jensen-Shannon divergences induce more concentrated posteriors around empirical risk minimizers, which leads to tighter fits on the training set. An interesting observation is the narrow shaded regions representing the empirical standard deviations across the 100 trials. Their small width across all methods implies that the training expected risk is largely invariant to randomness in the dataset. This highlights the dominant role played by the regularization parameter $\lambda$ and the prior $Q$ in the selection of a desired training expected risk for the solution of ERM-fDR based algorithms.

<figure><img src="image_7.png" /><figcaption>Fig. 5. Average Test Error: average of the expected empirical risks $R_{z_2}(P^{(Q,\lambda)}_{\Theta|Z=z_1})$, computed for four different f-divergences: relative entropy, reverse relative entropy, Jensen-Shannon divergence, and Hellinger divergence defined in (19), (25), (33), and (36), respectively. The results are the average of 100 random partitions of the training and test datasets.</figcaption></figure>

Figure 5 displays the expected test risk $R_{z_2}(P^{(Q,\lambda)}_{\Theta|Z=z_1})$ for various ERM-fDR solutions, computed across 100 independent trials. Each curve corresponds to a different f-divergence used in the regularization: reverse relative entropy (Type-II ERM-RER), classical relative entropy (Type-I ERM-RER), Jensen-Shannon, and Hellinger. ERM-RER Type-II (Reverse KL) continues to yield the highest test risk across nearly all

values of $\lambda$, consistent with its high training expected risk. Similarly, the Jensen-Shannon and Hellinger divergences yield the lowest test risks for most values of $\lambda$. This example indicates that the training expected risk is indeed a good descriptor of the performance of an ERM-fDR algorithm in the test expected empirical risk. This is particularly interesting as it points to the possibility of guaranteeing generalization performance based on training performance. However, it is important to point out that for smaller regularization factors, the empirical variance increases, which may indicate that guarantees are also dependent on the choice of regularization factor $\lambda$.

<figure><img src="image_8.png" /><figcaption>Fig. 6. Average of the differences $R_{z_2}(P^{(Q,\lambda)}_{\Theta|Z=z_1}) - R_{z_1}(P^{(Q,\lambda)}_{\Theta|Z=z_1})$, computed for four different f-divergences: relative entropy, reverse relative entropy, Jensen-Shannon divergence, and Hellinger divergence defined in (19), (25), (33), and (36), respectively. The results are the average of 100 random partitions of the training and test datasets.</figcaption></figure>

Figure 6 depicts the difference between the expected test risk and the expected training risk $R_{z_2}(P^{(Q,\lambda)}_{\Theta|Z=z_1}) - R_{z_1}(P^{(Q,\lambda)}_{\Theta|Z=z_1})$ for various ERM-fDR solutions across 100 iterations. For most of the range of the regularization parameter $\lambda$, the ERM-RER Type-I exhibits a larger sensitivity than ERM-RER Type-II, Jensen-Shannon, and Hellinger. Notably, the Type-I ERM-RER largest gap is at $\lambda$ around one, indicating a tendency to overfit the training data more significantly compared to the other methods. This behavior contrasts with the other divergences in this example. Remarkably, for small values of the regularization factor $\lambda$, the generalization gap of relative entropy is significantly smaller on average than that of reverse relative entropy, Jensen-Shannon, and Hellinger. It is worth noting that while the test and training expected risks are monotonically decreasing, the generalization gap can take the same value for different regularization factors $\lambda$. Hence, Figure 6 indicates that in this numerical analysis, there exist cases in which an appropriate choice of the regularization factor can keep the generalization error small while maintaining good test performance. Additionally, the three plots indicate that for this particular example, using a uniform reference measure over the set of models for classification is suboptimal; as a result, small values of $\lambda$ are favored, as they rely more on the training data than on the prior.

VIII. CONCLUSIONS

This work has presented the solution to the ERM-fDR problem in (11) and established conditions under which this
solution also solves the optimization problem in (12). Additionally, the dual problem in (45) has been introduced, along with its solution, which is characterized by the normalization function and exhibits a zero duality gap. By proving a zero duality gap, it has been established that the ERM-fDR solution depends directly on the Legendre-Fenchel transform. This connection enables the derivation of an implicit expression for the normalization function in the form of a nonlinear ODE, as well as the properties of the function. These properties facilitated the design of Algorithm 1, which numerically approximates the normalization function for a given regularization factor. The algorithm addresses a critical bottleneck in practical applications of the ERM-fDR solution: the intractability of analytically solving for the normalization function under general f-divergences. Without knowing the value of the normalization function, sampling methods such as rejection sampling or Markov Chain Monte Carlo (MCMC) cannot be applied due to the coupling of the log-likelihood ratio (for MCMC) and the need for scaling for suitable proposal distributions (for rejection sampling). Furthermore, the Legendre-Fenchel transform has been used to characterize the difference between the expected empirical risk of the ERM-fDR solution and its reference measure.

These results pave the way for future exploration of non-convex or nondifferentiable divergences (e.g., Wasserstein or total variation), where the dual optimization remains convex and thus provides lower bounds for the ERM-fDR problem. Another possible direction for future work involves extending these expressions to characterize the difference between the ERM-fDR solution and an arbitrary probability measure (beyond the reference). Such an extension could enable explicit generalization bounds for ERM-fDR solutions using methods analogous to those in [21], as suggested by the equivalence result in Section VI. The equivalence result shows that the solution of an f-divergence regularizer can be equal to the solution of a different f-divergence regularizer via an appropriate transformation of the empirical risk (see (112)). Additionally, this equivalence between regularizations clarifies the mutual absolute continuity between ERM-fDR solutions and the reference measure. Finally, despite the equivalence, simulations indicate that there are advantages to choosing different f-divergence regularizers, though the conditions favoring one choice over another remain an open question.

## REFERENCES

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

[2] F. Daunas, I. Esnaola, and S. M. Perlaza, "A dual optimization view to empirical risk minimization with f-divergence regularization," in *Proceedings of the IEEE Information Theory Workshop (ITW)*, Sydney, Australia, Oct. 2025, pp. 740-745.

[3] V. Vapnik and A. Y. Chervonenkis, "On a perceptron class," *Avtomatika i Telemekhanika*, vol. 25, no. 1, pp. 112-120, Feb. 1964.

[4] V. Vapnik, "Principles of risk minimization for learning theory," in *Advances in Neural Information Processing Systems*, vol. 4, Denver, CO, USA, Dec. 1991, pp. 831-838.

[5] V. Vapnik and L. Bottou, "Local algorithms for pattern recognition and dependencies estimation," *Neural Computation*, vol. 5, no. 6, pp. 893-909, Nov. 1993.

[6] A. Krzyzak, T. Linder, and C. Lugosi, "Nonparametric estimation and classification using radial basis function nets and empirical risk minimization," *IEEE Transactions on Neural Networks*, vol. 7, no. 2, pp. 475-487, Mar. 1996.

[7] B. Zou, L. Li, and Z. Xu, "The generalization performance of ERM algorithm with strongly mixing observations," *Machine Learning*, vol. 75, no. 3, pp. 275-295, Feb. 2009.

[8] L. G. Valiant, "A theory of the learnable," *Communications of the ACM*, vol. 27, no. 11, pp. 1134-1142, Nov. 1984.

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

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

[11] D. Cullina, A. N. Bhagoji, and P. Mittal, "PAC-learning in the presence of adversaries," in *Advances in Neural Information Processing Systems*, vol. 31, Montréal, Canada, Dec. 2018, pp. 1-12.

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

[13] B. E. Boser, I. M. Guyon, and V. N. Vapnik, "A training algorithm for optimal margin classifiers," in *Proceedings of the Fifth Annual Workshop on Computational Learning Theory (COLT)*, Pittsburgh, PA, USA, Jul. 1992, pp. 144-152.

[14] T. G. Dietterich, "Approximate statistical tests for comparing supervised classification learning algorithms," *Neural Computation*, vol. 10, no. 7, pp. 1895-1923, Sep. 1998.

[15] P. Xu, J. Chen, D. Zou, and Q. Gu, "Global convergence of Langevin dynamics based algorithms for nonconvex optimization," *arXiv preprint arXiv:1707.06618*, Feb. 2017.

[16] S. Geman and D. Geman, "Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 11, no. 6, pp. 721-741, Nov. 1984.

[17] X. Cheng and P. Bartlett, "Convergence of Langevin MCMC in KL-divergence," in *Proceedings of Algorithmic Learning Theory (ALT)*, vol. 83, Lanzarote, Spain, Apr. 2018, pp. 186-211.

[18] G. Aminian, Y. Bu, L. Toni, M. Rodrigues, and G. Wornell, "An exact characterization of the generalization error for the Gibbs algorithm," in *Advances in Neural Information Processing Systems*, vol. 34, Virtual, Dec. 2021, pp. 8106-8118.

[19] J. Wishart, "The generalised product moment distribution in samples from a normal multivariate population," *Biometrika*, vol. 20, no. 1/2, pp. 32-52, Jul. 1928.

[20] S. Kolouri, Y. Zou, and G. K. Rohde, "Sliced Wasserstein kernels for probability distributions," in *Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition*, Las Vegas, NV, USA, Jun. 2016, pp. 5258-5267.

[21] S. M. Perlaza and X. Zou, "The generalization error of machine learning algorithms," *arXiv preprint 2411.12030*, Nov. 2024.

[22] H. Hafez-Kolahi, Z. Golgooni, S. Kasaei, and M. Soleymani, "Conditioning and processing: Techniques to improve information-theoretic generalization bounds," in *Advances in Neural Information Processing Systems*, vol. 33, Vancouver, Canada, Dec. 2020, pp. 16457-16467.

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

[24] A. Asadi, E. Abbe, and S. Verdú, "Chaining mutual information and tightening generalization bounds," in *Advances in Neural Information Processing Systems*, vol. 31, Montréal, Canada, Dec. 2018, pp. 7245-7254.

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

[26] H. Wang, M. Diaz, J. C. S. Santos Filho, and F. P. Calmon, "An information-theoretic view of generalization via Wasserstein distance," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Paris, France, Jul. 2019, pp. 577-581.

[27] A. S. Dalalyan and A. G. Karagulyan, "User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient," *arXiv preprint arXiv:1710.00095*, Feb. 2024.

[28] W. Li, N. Klein, B. Gifford, E. Sklute, C. Legett, and S. Clegg, "Regularization via f-divergence: An application to multi-oxide spectroscopic analysis," *arXiv preprint arXiv:2502.03755*, Feb. 2025.

[29] F. Peng, M. Zhang, and M. Tang, "An information-theoretic analysis for federated learning under concept drift," *arXiv preprint arXiv:2506.21036*, Jun. 2025.
[30] F. Futami and T. Iwata, "Information-theoretic analysis of test data sensitivity in uncertainty," arXiv preprint arXiv:2307.12456, Jul. 2023.

[31] Z. Huang and S. Becker, "Stochastic gradient Langevin dynamics with variance reduction," arXiv preprint arXiv:2102.06759, Jul. 2021.

[32] I. Csiszár, "Information-type measures of difference of probability distributions and indirect observation," *Studia Scientiarum Mathematicarum Hungarica*, vol. 2, no. 1, pp. 299-318, Jun. 1967.

[33] —, "Maxent, mathematics, and information theory," in *Proceedings of the International Workshop on Maximum Entropy and Bayesian Methods*, Santa Fe, NM, USA, Jul. 1996, pp. 35-50.

[34] S. M. Ali and S. D. Silvey, "A general class of coefficients of divergence of one distribution from another," *Journal of the Royal Statistical Society: Series B (Methodological)*, vol. 28, no. 1, pp. 131-142, Apr. 1966.

[35] I. Csiszár, "I-divergence geometry of probability distributions and minimization problems," *The Annals of Probability*, vol. 3, no. 1, pp. 146-158, Feb. 1975.

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

[37] I. Sason and S. Verdú, "f-divergence inequalities," *IEEE Transactions on Information Theory*, vol. 62, no. 11, pp. 5973-6006, Jun. 2016.

[38] M. Raginsky, A. Rakhlin, M. Tsao, Y. Wu, and A. Xu, "Information-theoretic analysis of stability and bias of learning algorithms," in *Proceedings of the IEEE Information Theory Workshop (ITW)*, Cambridge, UK, Sep. 2016, pp. 26-30.

[39] A. Xu and M. Raginsky, "Information-theoretic analysis of generalization capability of learning algorithms," in *Advances in Neural Information Processing Systems*, vol. 30, Long Beach, CA, USA, Dec. 2017, pp. 1-10.

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

[41] S. M. Perlaza, G. Bisson, I. Esnaola, A. Jean-Marie, and S. Rini, "Empirical risk minimization with relative entropy regularization," *IEEE Transactions on Information Theory*, vol. 70, no. 7, pp. 5122-5161, Jul. 2024.

[42] —, "Empirical risk minimization with relative entropy regularization: Optimality and sensitivity," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Espoo, Finland, Jul. 2022, pp. 684-689.

[43] F. Daunas, I. Esnaola, S. M. Perlaza, and H. V. Poor, "Asymmetry of the relative entropy in the regularization of empirical risk minimization," *To appear in the IEEE Transactions on Information Theory*, Oct. 2025.

[44] J. W. Gibbs, *Elementary principles in statistical mechanics*, 1st ed. New Haven, NJ, USA: Yale University Press, 1902.

[45] W. Jiang and M. A. Tanner, "Gibbs posterior for variable selection in high-dimensional classification and data mining," *Annals of Statistics*, vol. 36, no. 5, pp. 2207-2231, Oct. 2008.

[46] L. Martino, V. Elvira, and G. Camps-Valls, "The recycling Gibbs sampler for efficient learning," *Digital Signal Processing*, vol. 74, no. 1, pp. 1-13, Aug. 2018.

[47] I. Kuzborskij, N. Cesa-Bianchi, and C. Szepesvári, "Distribution-dependent analysis of Gibbs-ERM principle," in *Proceedings of the Conference on Learning Theory (COLT)*, Phoenix, AZ, USA, Jun. 2019, pp. 2028-2054.

[48] L. Boltzmann, *Leçons Sur la Théorie des Gaz (première partie)*, réédition Jacques Gabay ed. Paris, France: Gauthier-Villars, 1902.

[49] —, *Leçons Sur la Théorie des Gaz (deuxième partie)*, réédition Jacques Gabay ed. Paris, France: Gauthier-Villars, 1905.

[50] D. H. Ackley, G. E. Hinton, and T. J. Sejnowski, "A learning algorithm for Boltzmann machines," *Cognitive Science*, vol. 9, no. 1, pp. 147-169, Jan. 1985.

[51] M. Teboulle, "Entropic proximal mappings with applications to nonlinear programming," *Mathematics of Operations Research*, vol. 17, no. 3, pp. 670-690, Aug. 1992.

[52] A. Beck and M. Teboulle, "Mirror descent and nonlinear projected subgradient methods for convex optimization," *Operations Research Letters*, vol. 31, no. 3, pp. 167-175, Jan. 2003.

[53] P. Alquier, "Non-exponentially weighted aggregation: Regret bounds for unbounded loss functions," in *Proceedings of the 38th International Conference on Machine Learning (ICML)*, vol. 139, Bilbao, Spain, Jul. 2021, pp. 207-218.

[54] J. Wei and Y. Liu, "When optimizing f-divergence is robust with label noise," arXiv preprint arXiv:2011.03687, Aug. 2021.

[55] Z. Liu, B. P. Van Parys, and H. Lam, "Smoothed f-divergence distributionally robust optimization," arXiv preprint arXiv:2306.14041, Oct. 2023.

[56] H. Namkoong and J. C. Duchi, "Stochastic gradient methods for distributionally robust optimization with f-divergences," in *Advances in Neural Information Processing Systems*, vol. 26, Barcelona, Spain, Dec. 2016, pp. 1476-1485.

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

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

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

[60] X. Zou, S. M. Perlaza, I. Esnaola, and E. Altman, "Generalization analysis of machine learning algorithms via the worst-case data-generating probability measure," in *Proceedings of the AAAI Conference on Artificial Intelligence*, Vancouver, Canada, Feb. 2024, pp. 17271-17279.

[61] X. Wu, J. H. Manton, U. Aickelin, and J. Zhu, "On the generalization for transfer learning: An information-theoretic analysis," *IEEE Transactions on Information Theory*, vol. 70, no. 10, pp. 7089-7124, Aug. 2024.

[62] W. Yao, G. Xu, H. Tang, W. Yang, D. Di, Z. Wang, and Y. Liu, "On weak-to-strong generalization and f-divergence," arXiv preprint arXiv:2506.03109, Jun. 2025.

[63] N. Novello and A. M. Tonello, "f-divergence based classification: Beyond the use of cross-entropy," in *Proceedings of the 41st International Conference on Machine Learning (ICML)*, Vienna, Austria, Jul. 2024, pp. 1273-1282.

[64] N. A. Letizia, N. Novello, and A. M. Tonello, "Mutual information estimation via f-divergence and data derangements," in *Advances in Neural Information Processing Systems*, vol. 37, Vancouver, Canada, Dec. 2024, pp. 105114-105150.

[65] N. Novello and A. M. Tonello, "Robust classification with noisy labels based on posterior maximization," arXiv preprint arXiv:2504.06805, Apr. 2025.

[66] S. Masiha, A. Gohari, and M. H. Yassaee, "f-divergences and their applications in lossy compression and bounding generalization error," *IEEE Transactions on Information Theory*, vol. 69, no. 12, pp. 7538-7564, Apr. 2023.

[67] A. R. Esposito, M. Gastpar, and I. Issa, "Robust generalization via f-mutual information," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Los Angeles, CA, USA, Jun. 2020, pp. 2723-2728.

[68] A. Van Biesbroeck, "Generalized mutual information and their reference priors under Csizar f-divergence," arXiv preprint arXiv:2310.10530, Apr. 2024.

[69] M. Zhang, T. Bird, R. Habib, T. Xu, and D. Barber, "Variational f-divergence minimization," arXiv preprint arXiv:1907.11891v2, Oct. 2024.

[70] A. Picard-Weibel, E. Clerico, R. Moscoviz, and B. Guedj, "How good is PAC-Bayes at explaining generalization?" arXiv preprint arXiv:2503.08231, May 2025.

[71] F. Daunas, I. Esnaola, S. M. Perlaza, and H. V. Poor, "Analysis of the relative entropy asymmetry in the regularization of empirical risk minimization," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Taipei, Taiwan, Jun. 2023.

[72] Y. Bermudez, S. M. Perlaza, G. Bisson, and I. Esnaola, "Proofs for folklore theorems on the radon-nikodym derivative," INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France, Tech. Rep. RR-9591, Jul. 2025.

[73] Z. Hu and L. J. Hong, "Kullback-Leibler divergence constrained distributionally robust optimization," *Available at Optimization Online*, vol. 1, no. 2, Nov. 2013.

[74] A. Bulatov and M. Grohe, "The complexity of partition functions," *Theoretical Computer Science*, vol. 348, no. 2-3, pp. 148-186, Sep. 2005.

[75] A. A. Bulatov, "The complexity of the counting constraint satisfaction problem," *Journal of the ACM (JACM)*, vol. 60, no. 5, pp. 1-41, Sep. 2014.

[76] C. McQuillan, "The computational complexity of approximation of partition functions," PhD thesis, University of Liverpool, Liverpool, UK, Jun. 2013.

[77] J. Radon, "Theorie und anwendungen der absolut additiven mengenfunktionen," *Sitzungsberichte der Kaiserlichen Akademie der Wissenschaften, Wien, Mathematisch-Naturwissenschaftliche Klasse*, vol. 122, no. 1, pp. 1296-1438, Jun. 1913.
[78] P. R. Halmos and L. J. Savage, "Application of the Radon-Nikodym theorem to the theory of sufficient statistics," *The Annals of Mathematical Statistics*, vol. 20, no. 2, pp. 225-241, Apr. 1949.

[79] S. Kullback and R. A. Leibler, "On information and sufficiency," *Annals of Mathematical Statistics*, vol. 22, no. 1, pp. 79-86, Mar. 1951.

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

[81] S. Boyd and L. Vandenberghe, *Convex Optimization*, 1st ed. Cambridge, UK: Cambridge University Press, 2004.

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

[83] R. T. Rockafellar, *Conjugate Convex Functions in Optimal Control and the Calculus of Variations*, 2nd ed. Princeton, NJ, USA: Princeton University Press, 1970.

[84] D. G. Luenberger, "Observing the state of a linear system," *IEEE Transactions on Military Electronics*, vol. 8, no. 2, pp. 74-80, Apr. 1964.

[85] ——, *Optimization by Vector Space Methods*, 1st ed. New York, NY, USA: Wiley, 1997.

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

[87] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, "Gradient-based learning applied to document recognition," *Proceedings of the IEEE*, vol. 86, no. 11, pp. 2278-2324, Aug. 1998.

[88] R. G. Bartle and D. R. Sherbert, *Introduction to Real Analysis*, 3rd ed. New York, NY, USA: Wiley New York, 2000.

[89] J. Douchet, *Analyse : Recueil d'Exercices et Aide-Mémoire*, 3rd ed. Lausanne, Switzerland: PPUR, 2010, vol. 1.

[90] O. de Oliveira, "The Implicit and Inverse Function Theorems: Easy Proofs," *Real Analysis Exchange*, vol. 39, no. 1, pp. 207-218, Jul. 2014.

[91] W. Rudin, *Principles of Mathematical Analysis*, 1st ed. New York, NY, USA: McGraw-Hill Book Company, Inc., 1953.

[92] N. Dalal and B. Triggs, "Histograms of oriented gradients for human detection," in *Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)*, San Diego, CA, USA, Apr. 2005, pp. 886-893.
APPENDIX A
PRELIMINARIES

Lemma 11: Let $f: [0, \infty) \to \mathbb{R}$ be a differentiable function inducing an $f$-divergence and satisfying $\dot{f}(1) \neq 0$. Then there exists a function $\tilde{f}: [0, \infty) \to \mathbb{R}$ such that $\dot{f}(1) = 0$ and, for all probability measures $P$ and $Q$, it holds that

$$D_f(P\|Q) = D_{\tilde{f}}(P\|Q). \qquad (121)$$

*Proof:* Let the function $f: [0, \infty) \to \mathbb{R}$ be differentiable and the function $\tilde{f}: [0, \infty) \to \mathbb{R}$ be defined as

$$\tilde{f}(u) = f(u) - \dot{f}(1)(u-1). \qquad (122)$$

Note that, from (122) it follows that

$$\tilde{f}(1) = f(1) - \dot{f}(1)(0) \qquad (123)$$

$$= 0. \qquad (124)$$

Similarly, the derivative of (122) yields,

$$\dot{\tilde{f}}(u) = \dot{f}(u) - \dot{f}(1), \qquad (125)$$

which implies that

$$\dot{\tilde{f}}(1) = 0. \qquad (126)$$

The proof continues by showing that the equality in (121) holds. From the definition of $f$-divergences, it follows that

$$D_{\tilde{f}}(P\|Q) = \int \tilde{f}\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) dQ(\boldsymbol{\theta}) \qquad (127)$$

$$= \int f\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) - \dot{f}(1)\left(\frac{dP}{dQ}(\boldsymbol{\theta}) - 1\right) dQ(\boldsymbol{\theta}) \qquad (128)$$

$$= \int f\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) dQ(\boldsymbol{\theta}) - \dot{f}(1) \int \left(\frac{dP}{dQ}(\boldsymbol{\theta}) - 1\right) dQ(\boldsymbol{\theta}) \qquad (129)$$

$$= D_f(P\|Q) - \dot{f}(1) \left( \int dP(\boldsymbol{\theta}) - \int dQ(\boldsymbol{\theta}) \right) \qquad (130)$$

$$= D_f(P\|Q), \qquad (131)$$

where (128) follows from (122); (129) follows from the change of measure; and (130) follows from the fact that both $P$ and $Q$ are probability measures. This completes the proof of (121). ■

Lemma 12: Let $P$ and $Q$ be two probability measures on the measurable space $(\mathcal{M}, \mathcal{F})$. Let $f: [0, \infty) \to \mathbb{R}$ be a twice differentiable and strictly convex function that induces a finite $f$-divergence and satisfies $\dot{f}(1) = 0$. Then,

$$\int \dot{f}\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) dP(\boldsymbol{\theta}) \geq 0. \qquad (132)$$

*Proof:* From the $f$-divergence definition, $P$ is absolutely continuous with respect to $Q$. Consequently, the Radon-Nikodym derivative $u: \mathcal{M} \to [0, \infty)$ exists, is $Q$-measurable and satisfies $\int u(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}) = 1$. Moreover, by the assumptions that $f$ is twice differentiable and strictly convex, it follows that $\dot{f} \geq 0$ on $(0, \infty)$. Finally, from the assumption that $D_f(P\|Q) < \infty$, the composition $f \circ u$ is $Q$-integrable.

The first step is as follows. From the strict convexity of $f$ and the condition $f(1) = 0$, for all $t > 0$, the convexity and differentiability of $f$ yield the tangent-line inequality such that, for all $s > 0$

$$f(s) \geq f(t) + \dot{f}(t)(s-t), \qquad (133)$$

with strict inequality for $s \neq t$. Let $s = 1$ and use the fact that $f(1) = 0$ to obtain, for all $t > 0$,

$$\dot{f}(t)(t-1) \geq f(t). \qquad (134)$$

Replacing $t$ by $u(\boldsymbol{\theta})$ and integrating with respect to $Q$ yields

$$\int \dot{f}(u(\boldsymbol{\theta}))(u(\boldsymbol{\theta}) - 1) dQ(\boldsymbol{\theta}) \geq \int f(u(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) = D_f(P\|Q). \qquad (135)$$

The second step is as follows. Consider the partition of the set $[0, \infty)$ formed by the sets $A_0$ and $A_1$, which satisfy the following:

$$A_0 \triangleq [0, 1), \qquad (136)$$

$$A_1 \triangleq [1, \infty). \qquad (137)$$
For $t \in A_1$ the Fundamental Theorem of Calculus together with $f(1) = \dot{f}(1) = 0$ give

$$ \dot{f}(t) = \int_{1}^{t} \ddot{f}(s) \, ds, \qquad (138) $$

$$ f(t) = \int_{1}^{t} (t-s) \ddot{f}(s) \, ds. \qquad (139) $$

For $t \in A_0$ the same conditions give

$$ \dot{f}(t) = - \int_{t}^{1} \ddot{f}(s) \, ds, \qquad (140) $$

$$ f(t) = \int_{t}^{1} (s-t) \ddot{f}(s) \, ds. \qquad (141) $$

Adding (138) and (139), and (140) and (141) for each set $A_0$ and $A_1$ yields the representation

$$ f(t) + \dot{f}(t) = \begin{cases} \int_{1}^{t} (t-s+1) \ddot{f}(s) \, ds, & t \in A_1, \\ \int_{t}^{1} (t-s+1) \ddot{f}(s) \, ds, & t \in A_0. \end{cases} \qquad (142) $$

Observe that for all $t \in [0, \infty)$, the integrand term $(t-s+1)\ddot{f}(s)$ is nonnegative. Indeed, since $\ddot{f}(s) \ge 0$, it suffices to verify that $t-s+1 \ge 0$. If $t \ge 1$ and $s \in [1, t]$, then $t-s+1 \ge 0$. If $t < 1$ and $s \in [t, 1]$, then $t-s+1 \ge t > 0$. Therefore, $t-s+1 \ge 0$ holds throughout the interval $[0, \infty)$. Using this, and the fact that $t \ge 0$, (142) can be expressed as follows,

$$ f(t) + \dot{f}(t) = \int_{0}^{\infty} \mathbb{1}_{\{s:(s-1)(t-1)>0\}} (t-s+1) \ddot{f}(s) \, ds \qquad (143) $$

The third step is as follows. The right-hand side of (143) can be written as an integral over the product space $M \times [0, \infty)$ of the nonnegative measurable function

$$ \int (f(u(\boldsymbol{\theta}))) + \dot{f}(u(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) = \int \left( \int (u(\boldsymbol{\theta}) - s + 1) \ddot{f}(s) \mathbb{1}_{\{(s-1)(u(\boldsymbol{\theta})-1)>0\}} \, ds \right) dQ(\boldsymbol{\theta}) \qquad (144) $$

$$ = \int \left( \int (u(\boldsymbol{\theta}) - s + 1) \mathbb{1}_{\{\boldsymbol{\theta} \in \mathcal{M}: (s-1)(u(\boldsymbol{\theta})-1)>0\}} dQ(\boldsymbol{\theta}) \right) \ddot{f}(s) \, ds. \qquad (145) $$

where (145) follows from Tonelli's theorem [82, Theorem 2.5.3], which follows by observing that the set $\{\boldsymbol{\theta} \in \mathcal{M}: (s-1)(u(\boldsymbol{\theta})-1)>0\}$ is measurable as a result of $u$ being measurable. For fixed $s > 0$, define the measurable subset

$$ \mathcal{A}_s \triangleq \{\boldsymbol{\theta} \in \mathcal{M}: (s-1)(u(\boldsymbol{\theta})-1) > 0\}. \qquad (146) $$

Then

$$ \int_{A_s} (u(\boldsymbol{\theta}) - s + 1) dQ(\boldsymbol{\theta}) = \int_{A_s} (u(\boldsymbol{\theta}) - s) dQ(\boldsymbol{\theta}) + Q(\mathcal{A}_s) \geq 0. \qquad (147) $$

From the strict convexity of $f$, it follows that $\ddot{f}(s) \ge 0$ for all $s$. Together with (147), this implies that the integral in (145) is nonnegative for all $s \ge 0$. This yields

$$ \int (f(u(\boldsymbol{\theta}))) + \dot{f}(u(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \ge 0, \qquad (148) $$

or equivalently

$$ \int \dot{f}(u(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) \ge - \int f(u(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) \qquad (149) $$

$$ = -D_f(P \| Q). \qquad (150) $$

The proof continues by using the algebraic identity

$$ u(\boldsymbol{\theta}) \dot{f}(u(\boldsymbol{\theta})) = \dot{f}(u(\boldsymbol{\theta})) + \dot{f}(u(\boldsymbol{\theta}))(u(\boldsymbol{\theta}) - 1), \qquad (151) $$

which together with (135) and (149) imply that

$$ \int u(\boldsymbol{\theta}) \dot{f}(u(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) = \int \dot{f}(u(\boldsymbol{\theta}))(u(\boldsymbol{\theta}) - 1) dQ(\boldsymbol{\theta}) + \int \dot{f}(u(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) \qquad (152) $$

$$ \geq D_f(P \| Q) + \int \dot{f}(u(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) \qquad (153) $$

$$ \geq D_f(P \| Q) - D_f(P \| Q) \qquad (154) $$

$$ = 0. \qquad (155) $$
It follows from (155), that

$$ \int \hat{f}\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) dP(\boldsymbol{\theta}) \geq 0, \qquad (156) $$

which completes the proof.

**Theorem 7:** Given a probability measure space $(\mathcal{M}, \mathcal{F}_{\mathcal{M}}, P)$ and an open subset $A \subseteq \mathbb{R}$, let the function $f: A \times \mathcal{M} \to \mathbb{R}$ be measurable with respect to $(A \times \mathcal{M}, \mathcal{F})$ and $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$. If for all $\boldsymbol{\nu} \in \mathcal{M}$, the function $f(\cdot, \boldsymbol{\nu}) : A \to \mathbb{R}$ is Lipschitz continuous and for some $s \in A$, $\int f(s, \boldsymbol{\nu}) dP(\boldsymbol{\nu}) < \infty$, then

$$ \left. \frac{d}{dt} \int f(t, \boldsymbol{\nu}) dP(\boldsymbol{\nu}) \right|_{t=s} = \left. \int \frac{d}{dt} f(t, \boldsymbol{\nu}) \right|_{t=s} dP(\boldsymbol{\nu}), \qquad (157) $$

*Proof:* Note that

$$ \left. \frac{d}{dt} \int f(t, \boldsymbol{\nu}) dP(\boldsymbol{\nu}) \right|_{t=s} = \lim_{\delta \to 0} \frac{\int f(s + \delta, \boldsymbol{\nu}) dP(\boldsymbol{\nu}) - \int f(s, \boldsymbol{\nu}) dP(\boldsymbol{\nu})}{\delta} \qquad (158) $$

$$ = \lim_{\delta \to 0} \int \frac{f(s + \delta, \boldsymbol{\nu}) - f(s, \boldsymbol{\nu})}{\delta} dP(\boldsymbol{\nu}), \qquad (159) $$

where (159) follows from [82, Theorem 1.6.3]. The assumption that for all $\boldsymbol{\nu} \in \mathcal{M}$, the function $f(\cdot, \boldsymbol{\nu})$ is Lipschitz continuous implies that for all $s \in A$ and some $\delta \in \mathbb{R}$ and $L \in \mathbb{R}$,

$$ |f(s + \delta, \boldsymbol{\nu}) - f(s, \boldsymbol{\nu})| < L |\delta|. \qquad (160) $$

And thus, dividing the right hand side and left hand side of (160) by $|\delta|$ yields

$$ \left| \frac{f(s + \delta, \boldsymbol{\nu}) - f(s, \boldsymbol{\nu})}{\delta} \right| < L, \qquad (161) $$

(162)

which implies that

$$ \int \left| \frac{f(s + \delta, \boldsymbol{\nu}) - f(s, \boldsymbol{\nu})}{\delta} \right| dP(\boldsymbol{\nu}) < \infty. \qquad (163) $$

(164)

This allows using the dominated convergence theorem [82, Theorem 1.6.9] as follows. From (159), the following holds

$$ \left. \frac{d}{dt} \int f(t, \boldsymbol{\nu}) dP(\boldsymbol{\nu}) \right|_{t=s} = \lim_{\delta \to 0} \int \frac{f(s + \delta, \boldsymbol{\nu}) - f(s, \boldsymbol{\nu})}{\delta} dP(\boldsymbol{\nu}) \qquad (165) $$

$$ = \int \lim_{\delta \to 0} \frac{f(s + \delta, \boldsymbol{\nu}) - f(s, \boldsymbol{\nu})}{\delta} dP(\boldsymbol{\nu}) \qquad (166) $$

$$ = \int \left. \frac{d}{dt} f(t, \boldsymbol{\nu}) \right|_{t=s} dP(\boldsymbol{\nu}), \qquad (167) $$

where (166) follows from the dominated convergence theorem [82, Theorem 1.6.9]. This completes the proof.

**Lemma 13:** Let $\mathcal{M}$ be the set of measurable functions that maps $\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})| dQ(\boldsymbol{\theta}) < \infty. \qquad (168) $$

Given a strictly convex function $f: \mathbb{R} \to \mathbb{R}$, let the function $\hat{r}: \mathbb{R} \to \mathbb{R}$ be such that

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

for some function $g$ and $h$ in $\mathcal{S}$ and $\alpha \in (-\epsilon, \epsilon)$, with $\epsilon > 0$ arbitrarily small. Then, the function $\hat{r}$ in (169) is differentiable at zero.

*Proof:* The objective is to prove that the function $\hat{r}$ in (169) is differentiable at zero, which boils down to proving that the limit

$$ \lim_{\delta \to 0} \frac{1}{\delta} (\hat{r}(\alpha + \delta) - \hat{r}(\alpha)) \qquad (170) $$
exists for $\alpha \in (-\epsilon, \epsilon)$, with $\epsilon > 0$ arbitrarily small. The proof of the existence of the limit in (170) relies on the fact that the function $f$ in (169) is strictly convex and differentiable, which implies that $f$ is also Lipschitz continuous. Hence, it follows that

$$|f(g(\boldsymbol{\theta}) + (\alpha + \delta)h(\boldsymbol{\theta})) - f(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta}))| \leq c|h(\boldsymbol{\theta})| |\delta|, \quad (171)$$

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|} \leq c|h(\boldsymbol{\theta})|, \quad (172)$$

and thus, given that $g \in \mathcal{S}$, integrating both sides of (172) with respect to $Q$ yields,

$$\int \frac{|f(g(\boldsymbol{\theta}) + (\alpha + \delta)h(\boldsymbol{\theta})) - f(g(\boldsymbol{\theta}) + \alpha h(\boldsymbol{\theta}))|}{|\delta|} dQ(\boldsymbol{\theta}) \leq \infty. \quad (173)$$

This allows using the dominated convergence theorem as follows. From the fact that the function $f$ is differentiable, let $\dot{f} : (0, \infty) \to \mathbb{R}$ be the first derivative of $f$. The limit in (170) satisfies for all $\alpha \in (-\epsilon, \epsilon)$, with $\epsilon > 0$ arbitrarily small,

$$\lim_{\delta \to 0} \frac{1}{\delta}(\hat{r}(\alpha + \delta) - \hat{r}(\alpha)) = \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) \quad (174)$$

$$= \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}) \quad (175)$$

$$= \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}) \quad (176)$$

$$= \int \dot{f}(g(\boldsymbol{\theta}) + (\alpha + \delta)h(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) \quad (177)$$

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

where the equalities in (176) and (178) follow from the dominated convergence theorem [82, Theorem 1.6.9]. From (178), it follows that the function $\hat{r}$ in (169) is differentiable at zero. This completes the proof. ■

**Lemma 14:** Given a strictly convex and differentiable function $f: \mathcal{I} \to \mathbb{R}$, the inverse of the derivative of $f$, denoted by the function $\dot{f}^{-1}: \mathcal{J} \to \mathcal{I}$, exists and is strictly increasing.

*Proof:* Under the assumption that the function $f: \mathcal{I} \to \mathbb{R}$ is strictly convex and differentiable, it follows from the definition of strict convexity (see [85, Definition 7.8]) that its derivative $\dot{f}: \mathcal{I} \to \mathcal{J}$ is strictly increasing and continuous. By the continuous inverse theorem (see [88, Theorem 5.6]), the inverse function $\dot{f}^{-1}: \mathcal{J} \to \mathcal{I}$ exists and is also strictly increasing and continuous. This completes the proof. ■

**Lemma 15:** Given a strictly convex and twice differentiable function $f: \mathcal{I} \to \mathbb{R}$, and a differentiable function $h: \mathcal{I} \to \mathcal{J}$, for all $u \in \mathcal{I}$ it holds that

$$\frac{d}{du} \dot{f}^{-1}(h(u)) = \frac{\dot{h}(u)}{\ddot{f}(\dot{f}^{-1}(h(u)))}. \quad (179)$$

*Proof:* Let the function $g: \mathcal{I} \to \mathcal{J}$ be defined for all $u \in \mathcal{I}$ by

$$g(u) = \dot{f}^{-1}(h(u)) \quad (180)$$

By the definition of the inverse function, it follows that

$$\dot{f}(g(u)) = h(u). \quad (181)$$

Differentiating (181) with respect to $u$ yields

$$\frac{d}{du} \dot{f}(g(u)) = \ddot{f}(g(u)) \dot{g}(u) \quad (182)$$

$$= \dot{h}(u). \quad (183)$$

From (182), the derivative of the function $g$ in (181) is given by

$$\dot{g}(u) = \frac{\dot{h}(u)}{\ddot{f}(g(u))} \quad (184)$$

$$= \frac{\dot{h}(u)}{\ddot{f}(\dot{f}^{-1}(h(u)))}, \quad (185)$$
where (185) follows from (180). Hence, (180) and (185) imply that

$$ \frac{d}{du} \dot{f}^{-1}(h(u)) = \frac{\dot{h}(u)}{\ddot{f}(\dot{f}^{-1}(h(u)))}. \qquad (186) $$

This completes the proof.

*Lemma 16:* The Legendre-Fenchel transform of a strictly convex and differentiable function $f$, satisfies for all $v \in \mathcal{J}$, with $\mathcal{J}$ in (44),

$$ f^*(v) = v \dot{f}^*(v) - f(\dot{f}^*(v)). \qquad (187) $$

*Proof:* From the Legendre-Fenchel transform in Definition 3, it holds that for all $v \in \mathcal{J}$, with $\mathcal{J}$ in (44),

$$ f^*(v) = \sup_{u \in \mathcal{I}} (vu - f(u)), \qquad (188) $$

which implies that, for all $u \in \mathcal{I}$,

$$ f^*(v) \geq vu - f(u). \qquad (189) $$

Note that (189) holds with equality if $u$ achieves the supremum in (188), which will be denoted by $u_v$. In other words, $u_v$ is the maximizing argument

$$ u_v = \arg \max_{u \in \mathcal{I}} uv - f(u), \qquad (190) $$

such that

$$ f^*(v) = vu_v - f(u_v). \qquad (191) $$

Note that under Assumption (a) in Theorem 1, the maximization problem

$$ \max_{u \in \mathcal{I}} uv - f(u), \qquad (192) $$

is concave and possesses a unique solution that satisfies

$$ \left. \frac{d}{du}(uv - f(u)) \right|_{u=u_v} = v - \dot{f}(u_v) = 0, \qquad (193) $$

and thus,

$$ u_v = \dot{f}^{-1}(v) \qquad (194) $$

$$ = \dot{f}^*(v), \qquad (195) $$

where (195) follows from [83, Corollary 23.5.1]. Hence, substituting (195) into (191) yields that for all $v \in \mathcal{J}$,

$$ f^*(v) = v \dot{f}^*(v) - f(\dot{f}^*(v)), \qquad (196) $$

which completes the proof.

*Lemma 17:* Let $P$ and $Q$ be probability measures on the measurable space $(\mathcal{M}, \mathcal{F})$, such that $P$ and $Q$ are mutually absolutely continuous. Under the assumption that the Radon-Nikodym derivative $\frac{dP}{dQ}$ is strictly monotonic with respect to the empirical risk $L_z$ defined in (9). Then the corresponding expected empirical risks satisfy

$$ R_z(Q) < R_z(P), \qquad (197) $$

in the case in which $\frac{dP}{dQ}$ is strictly monotonically decreasing with respect to $L_z$, and

$$ R_z(Q) > R_z(P), \qquad (198) $$

in the case in which $\frac{dP}{dQ}$ is strictly monotonically increasing with respect to $L_z$.

*Proof:* The proof treats the case in which $\frac{dP}{dQ}$ is strictly increasing; the case of strict decrease follows by the same argument with the inequalities reversed. Denote the Radon-Nikodym derivative $\frac{dP}{dQ}$ by the function $g: [0, \infty) \to [0, \infty)$, such that for all $\theta \in \text{supp } Q$,

$$ \frac{dP}{dQ}(\theta) = g(L_z(\theta)), \qquad (199) $$

Let the real value $k \in \mathbb{R}$ be defined as

$$ k = g^{-1}(1), \qquad (200) $$
and consider the partition of the set $\mathcal{M}$ formed by the sets $\mathcal{M}_0$ and $\mathcal{M}_1$, which satisfy the following:

$$ \mathcal{M}_0 = \{\boldsymbol{\theta} \in \mathcal{M} : \mathbf{L}_z(\boldsymbol{\theta}) < k\}, \qquad (201) $$

$$ \mathcal{M}_1 = \{\boldsymbol{\theta} \in \mathcal{M} : \mathbf{L}_z(\boldsymbol{\theta}) \geq k\}. \qquad (202) $$

Note that from (200) for all $\boldsymbol{\theta} \in \mathcal{M}$, such that $\mathbf{L}_z(\boldsymbol{\theta}) = k$, it follows

$$ g(\mathbf{L}_z(\boldsymbol{\theta})) = 1. \qquad (203) $$

The monotonicity of $g$ and (203) imply that for all $\boldsymbol{\theta} \in \mathcal{M}_0$,

$$ g(\mathbf{L}_z(\boldsymbol{\theta})) < 1, \qquad (204) $$

and for all $\boldsymbol{\theta} \in \mathcal{M}_1$,

$$ g(\mathbf{L}_z(\boldsymbol{\theta})) \geq 1, \qquad (205) $$

Let $P$ denote the probability measure defined by the function $g$ in (199), such that

$$ P(\mathcal{M}) = \int_{\mathcal{M}_0} g(\mathbf{L}_z(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) + \int_{\mathcal{M}_1} g(\mathbf{L}_z(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}). \qquad (206) $$

Under the assumption that $g$ is increasing with respect to $\mathbf{L}_z$, the measure $P$ over the set $\mathcal{M}_0$ in (201) satisfies

$$ P(\mathcal{M}_0) = \int_{\mathcal{M}_0} g(\mathbf{L}_z(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \qquad (207a) $$

$$ < \int_{\mathcal{M}_0} dQ(\boldsymbol{\theta}) \qquad (207b) $$

$$ = Q(\mathcal{M}_0), \qquad (207c) $$

where (207b) follows from (204). Hence, from (204) and (207) it follows that

$$ \int_{\mathcal{M}_0} \mathbf{L}_z(\boldsymbol{\theta}) g(\mathbf{L}_z(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) < \int_{\mathcal{M}_0} \mathbf{L}_z(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}). \qquad (208) $$

Similarly, under the assumption $g$ is increasing with respect to $\mathbf{L}_z$, the measure $P$ over the set $\mathcal{M}_1$ in (202) satisfies

$$ P(\mathcal{M}_1) = \int_{\mathcal{M}_1} g(\mathbf{L}_z(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \qquad (209a) $$

$$ \geq \int_{\mathcal{M}_1} dQ(\boldsymbol{\theta}) \qquad (209b) $$

$$ = Q(\mathcal{M}_1). \qquad (209c) $$

where (209b) follows from (205). Hence, from (205) and (209) it follows that

$$ \int_{\mathcal{M}_1} \mathbf{L}_z(\boldsymbol{\theta}) g(\mathbf{L}_z(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \geq \int_{\mathcal{M}_1} \mathbf{L}_z(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}). \qquad (210) $$

Note that from (201) and (208), it holds that

$$ 0 < \int_{\mathcal{M}_0} \mathbf{L}_z(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) - \int_{\mathcal{M}_0} \mathbf{L}_z(\boldsymbol{\theta}) \, dP(\boldsymbol{\theta}) \qquad (211a) $$

$$ < k(Q(\mathcal{M}_0) - P(\mathcal{M}_0)). \qquad (211b) $$

Similarly, from (202) and (210), it holds that

$$ \int_{\mathcal{M}_1} \mathbf{L}_z(\boldsymbol{\theta}) \, dP(\boldsymbol{\theta}) - \int_{\mathcal{M}_1} \mathbf{L}_z(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) > k(P(\mathcal{M}_1) - Q(\mathcal{M}_1)) \qquad (212a) $$

$$ = k((1 - P(\mathcal{M}_0)) - (1 - Q(\mathcal{M}_0))) \qquad (212b) $$

$$ = k(Q(\mathcal{M}_0) - P(\mathcal{M}_0)) \qquad (212c) $$

Substituting, (211) into (212) yields

$$ \int_{\mathcal{M}_0} \mathbf{L}_z(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) - \int_{\mathcal{M}_0} \mathbf{L}_z(\boldsymbol{\theta}) \, dP(\boldsymbol{\theta}) < \int_{\mathcal{M}_1} \mathbf{L}_z(\boldsymbol{\theta}) \, dP(\boldsymbol{\theta}) - \int_{\mathcal{M}_1} \mathbf{L}_z(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}), \qquad (213) $$

which can be rearranged into,

$$ \int_{\mathcal{M}_0} \mathbf{L}_z(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) + \int_{\mathcal{M}_1} \mathbf{L}_z(\boldsymbol{\theta}) \, dQ(\boldsymbol{\theta}) < \int_{\mathcal{M}_1} \mathbf{L}_z(\boldsymbol{\theta}) \, dP(\boldsymbol{\theta}) + \int_{\mathcal{M}_0} \mathbf{L}_z(\boldsymbol{\theta}) \, dP(\boldsymbol{\theta}). \qquad (214) $$
Thus, the expected empirical risk of the measures $P$ under the assumption $g$ is increasing with respect to $L_z$ implies that

$$R_z(Q) < R_z(P), \qquad (215)$$

which completes the proof.

Lemma 18: Let $Q$ be a probability measure on $(\mathcal{M}, \mathcal{F})$, and let $P_1$ and $P_2$ be two probability measures on $(\mathcal{M}, \mathcal{F})$ that are absolutely continuous with respect to $Q$, with Radon-Nikodym derivatives that satisfy, for all $\theta \in \text{supp } Q$,

$$\frac{dP_i}{dQ}(\theta) = g\left(-\frac{L_z(\theta) + \beta_i}{\lambda_i}\right), \qquad (216)$$

where the function $g$ is a strictly increasing function, the function $L_z$ is the empirical risk in (9) and the real values satisfy $0 < \lambda_1 < \lambda_2$, and $\beta_i \in \mathbb{R}$, with $i \in \{1, 2\}$. Then, the expected empirical risk satisfies

$$R_z(P_1) < R_z(P_2). \qquad (217)$$

*Proof:* From the strict monotonicity of the function $g$ in (216), the empirical risk induces

$$\frac{dP_1}{dQ}(\theta) \ge \frac{dP_2}{dQ}(\theta) \iff -\frac{L_z(\theta) + \beta_1}{\lambda_1} \ge -\frac{L_z(\theta) + \beta_2}{\lambda_2}. \qquad (218)$$

Using the fact that $0 < \lambda_1 < \lambda_2$, let the real value $c \in \mathbb{R}$ be

$$c = \frac{\beta_1 \lambda_2 - \beta_2 \lambda_1}{\lambda_1 - \lambda_2}, \qquad (219)$$

and consider the partition of the set $\mathcal{M}$ formed by the sets $A_0, A_1$ and $A_2$, which satisfy the following:

$$A_0 \triangleq \{\theta \in \mathcal{M} : L_z(\theta) = c\}, \qquad (220)$$

$$A_1 \triangleq \{\theta \in \mathcal{M} : L_z(\theta) < c\}, \qquad (221)$$

$$A_2 \triangleq \{\theta \in \mathcal{M} : L_z(\theta) > c\}. \qquad (222)$$

Note that for all $\theta \in A_0$, the pair $(\lambda_2, \beta_2)$ satisfies

$$-\frac{1}{\lambda_2}(L_z(\theta) + \beta_2) = -\frac{1}{\lambda_2}(c + \beta_2) \qquad (223)$$

$$= -\frac{1}{\lambda_2} \left( \frac{\beta_1 \lambda_2 - \beta_2 \lambda_1}{\lambda_1 - \lambda_2} + \frac{\beta_2 (\lambda_1 - \lambda_2)}{\lambda_1 - \lambda_2} \right) \qquad (224)$$

$$= -\frac{1}{\lambda_2} \left( \frac{\beta_1 \lambda_2 - \beta_2 \lambda_1}{\lambda_1 - \lambda_2} \right) \qquad (225)$$

$$= -\left( \frac{\beta_1 - \beta_2}{\lambda_1 - \lambda_2} \right). \qquad (226)$$

Similarly, for all $\theta \in A_0$, the pair $(\lambda_1, \beta_1)$ satisfies

$$-\frac{1}{\lambda_1}(L_z(\theta) + \beta_1) = -\frac{1}{\lambda_1}(c + \beta_1) \qquad (227)$$

$$= -\frac{1}{\lambda_1} \left( \frac{\beta_1 \lambda_2 - \beta_2 \lambda_1}{\lambda_1 - \lambda_2} + \frac{\beta_1 (\lambda_1 - \lambda_2)}{\lambda_1 - \lambda_2} \right) \qquad (228)$$

$$= -\frac{1}{\lambda_1} \left( \frac{\beta_1 \lambda_1 - \beta_2 \lambda_1}{\lambda_1 - \lambda_2} \right) \qquad (229)$$

$$= -\left( \frac{\beta_1 - \beta_2}{\lambda_1 - \lambda_2} \right). \qquad (230)$$

Hence, from (226) and (230) for all $\theta \in A_0$, it holds that

$$-\frac{L_z(\theta) + \beta_2}{\lambda_2} = -\frac{L_z(\theta) + \beta_1}{\lambda_1}. \qquad (231)$$

Then, from (216) and (231), it follows that for all $\theta \in A_0$,

$$\frac{dP_1}{dQ}(\theta) = g\left(-\frac{L_z(\theta) + \beta_1}{\lambda_1}\right) \qquad (232a)$$

$$= g\left(-\frac{L_z(\theta) + \beta_2}{\lambda_2}\right) \qquad (232b)$$

$$= \frac{dP_2}{dQ}(\theta). \qquad (232c)$$
Furthermore, from the fact that $g$ is strictly increasing, for all $\theta \in A_1$, it holds that

$$ \frac{dP_1}{dQ}(\theta) > \frac{dP_2}{dQ}(\theta), \qquad (233) $$

and for all $\theta \in A_2$, it holds that

$$ \frac{dP_1}{dQ}(\theta) < \frac{dP_2}{dQ}(\theta). \qquad (234) $$

Let $P_1$ and $P_2$ denote the probability measures defined by the pairs $(\lambda_1, \beta_1)$ and $(\lambda_2, \beta_2)$, respectively. From (216), it follows that

$$ P_1(A_1) = \int_{A_1} \frac{dP_1}{dQ}(\theta) dQ(\theta), \qquad (235) $$

and

$$ P_2(A_1) = \int_{A_1} \frac{dP_2}{dQ}(\theta) dQ(\theta). \qquad (236) $$

From (235) and (236), the measures $P_1$ and $P_2$ over the set $A_1$ in (221) satisfy

$$ P_1(A_1) = \int_{A_1} \frac{dP_1}{dQ}(\theta) dQ(\theta) \qquad (237a) $$

$$ > \int_{A_1} \frac{dP_2}{dQ}(\theta) dQ(\theta) \qquad (237b) $$

$$ = P_2(A_1), \qquad (237c) $$

where (237b) follows from (233). Hence, from (237) it follows that

$$ \int_{A_1} \mathbf{L}_z(\theta) \frac{dP_1}{dQ}(\theta) dQ(\theta) > \int_{A_1} \mathbf{L}_z(\theta) \frac{dP_2}{dQ}(\theta) dQ(\theta). \qquad (238) $$

Similarly, from (235) and (236), the measures $P_1$ and $P_2$ over the set $A_2$ in (222) satisfy

$$ P_1(A_2) = \int_{A_2} \frac{dP_1}{dQ}(\theta) dQ(\theta) \qquad (239a) $$

$$ < \int_{A_2} \frac{dP_2}{dQ}(\theta) dQ(\theta) \qquad (239b) $$

$$ = P_2(A_2). \qquad (239c) $$

where (239b) follows from (234). Hence, from (239) it follows that

$$ \int_{A_2} \mathbf{L}_z(\theta) \frac{dP_1}{dQ}(\theta) dQ(\theta) < \int_{A_2} \mathbf{L}_z(\theta) \frac{dP_2}{dQ}(\theta) dQ(\theta). \qquad (240) $$

Note that from (221) and (238), it holds that

$$ 0 < \int_{A_1} \mathbf{L}_z(\theta) dP_1(\theta) - \int_{A_1} \mathbf{L}_z(\theta) dP_2(\theta) \qquad (241a) $$

$$ < c(P_1(A_1) - P_2(A_1)). \qquad (241b) $$

Similarly, from (222) and (240), it holds that

$$ \int_{A_2} \mathbf{L}_z(\theta) dP_2(\theta) - \int_{A_2} \mathbf{L}_z(\theta) dP_1(\theta) > c(P_2(A_2) - P_1(A_2)) \qquad (242a) $$

$$ = c((1 - P_2(A_1)) - (1 - P_1(A_1))) \qquad (242b) $$

$$ = c(P_1(A_1) - P_2(A_1)) \qquad (242c) $$

Substituting, (241) into (242) yields

$$ \int_{A_1} \mathbf{L}_z(\theta) dP_1(\theta) - \int_{A_1} \mathbf{L}_z(\theta) dP_2(\theta) < \int_{A_2} \mathbf{L}_z(\theta) dP_2(\theta) - \int_{A_2} \mathbf{L}_z(\theta) dP_1(\theta), \qquad (243) $$

which can be rearranged into,

$$ \int_{A_1} \mathbf{L}_z(\theta) dP_1(\theta) + \int_{A_2} \mathbf{L}_z(\theta) dP_1(\theta) < \int_{A_2} \mathbf{L}_z(\theta) dP_2(\theta) + \int_{A_1} \mathbf{L}_z(\theta) dP_2(\theta). \qquad (244) $$
Thus, the expected empirical risk of the measures $P_1$ and $P_2$ satisfies

$$R_z(P_1) < R_z(P_2). \qquad (245)$$

This completes the proof.

Lemma 19: Let $Q$ be a probability measure on a measurable space $(\mathcal{M}, \mathcal{F})$. Consider the pair $(a_1, b_1) \in (0, \infty) \times \mathbb{R}$ and let $g: \mathbb{R} \to (0, \infty)$ be a strictly increasing function such that

$$\int g\left(-\frac{L_z(\theta) + b_1}{a_1}\right) dQ(\theta) < \infty, \qquad (246)$$

where $L_z$ is defined in (9). Then the following monotonicity properties hold: For all $b_2 \in \mathbb{R}$ with $b_1 < b_2$:

$$\int g\left(-\frac{L_z(\theta) + b_1}{a_1}\right) dQ(\theta) > \int g\left(-\frac{L_z(\theta) + b_2}{a_1}\right) dQ(\theta). \qquad (247)$$

*Proof:* For all $(b_1, b_2) \in \mathbb{R}^2$, such that $b_1 < b_2$, it holds that for all $\theta \in \text{supp } Q$,

$$-\frac{L_z(\theta) + b_1}{a_1} > -\frac{L_z(\theta) + b_2}{a_1}. \qquad (248)$$

Then, from the assumption that $g$ is monotonically increasing it follows that for all $\theta \in \text{supp } Q$,

$$g\left(-\frac{L_z(\theta)+b_1}{a_1}\right) > g\left(-\frac{L_z(\theta)+b_2}{a_1}\right). \qquad (249)$$

Thus, integrating (249) with respect to $Q$ yields

$$\int g\left(-\frac{L_z(\theta)+b_1}{a}\right) dQ(\theta) > \int g\left(-\frac{L_z(\theta)+b_2}{a}\right) dQ(\theta), \qquad (250)$$

which completes the proof.

# APPENDIX B

## PROOF OF THEOREM 1

*Proof:* The optimization problems in (11) and (12) can be re-written in terms of the Radon-Nikodym derivative of the optimization measure $P$ with respect to the reference measure $Q$, denoted by $\frac{dP}{dQ}: \mathcal{M} \to [0, \infty)$, which yields:

$$\min_{P \in \Delta_Q(\mathcal{M})} \int L_z(\theta) \frac{dP}{dQ}(\theta) dQ(\theta) \qquad (251a)$$

$$\text{s.t.} \quad \int f\left(\frac{dP}{dQ}(\theta)\right) dQ(\theta) \leq \eta \qquad (251b)$$

$$\int \frac{dP}{dQ}(\theta) dQ(\theta) = 1. \qquad (251c)$$

The remainder of the proof focuses on the problem in which the optimization is over the Radon-Nikodym derivative $\frac{dP}{dQ}$ instead of the measures $P$. This is due to the fact that for all $P \in \Delta_Q(\mathcal{M})$, the Radon-Nikodym derivative $\frac{dP}{dQ}$ is unique up to sets of measure zero with respect to $Q$. The first part is as follows. Let $\mathcal{M}$ be the set of measurable functions $\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 $Q$. That is, for all $\hat{g} \in \mathcal{S}$, it holds that

$$\int |\hat{g}(\theta)| dQ(\theta) < \infty. \qquad (252)$$

Note that the set $\mathcal{M}$ forms a real vector space and the set $\mathcal{S}$ is a convex subset of $\mathcal{M}$. Note also that the constraints (251b) and (251c) are satisfied by the probability measure $Q$, which also satisfies $Q \in \Delta_Q(\mathcal{M})$. Hence, the constraints do not induce an empty feasible set. Finally, note that without loss of generality the minimization in (251) can be written as a minimization problem of the form:

$$\min_{g \in \mathcal{S}} \int L_z(\theta) g(\theta) dQ(\theta) \qquad (253a)$$

$$\text{s.t.} \quad \frac{1}{\eta} \int f(g(\theta)) dQ(\theta) \leq 1 \qquad (253b)$$

$$\int g(\theta) dQ(\theta) = 1, \qquad (253c)$$
where the expressions $\int L_z(\theta)g(\theta) dQ(\theta)$ and $\int g(\theta) dQ(\theta)$ are linear with $g$; the expression $\frac{1}{\eta} \int f(g(\theta)) dQ(\theta)$ is convex with $g$. The proof continues by assuming that the problem in (253) possesses a solution, which is denoted by $g^* \in \mathcal{S}$. Let $\mu_0 \in [0, \infty)$ be

$$ \mu_0 \triangleq \min_{g \in \mathcal{S}} \int L_z(\theta) g(\theta) dQ(\theta) \quad (254a) $$

$$ \text{s.t.} \quad \frac{1}{\eta} \int f(g(\theta)) dQ(\theta) \le 1 \quad (254b) $$

$$ \int g(\theta) dQ(\theta) = 1 \quad (254c) $$

$$ = \int L_z(\theta) g^*(\theta) dQ(\theta). \quad (254d) $$

From [85, Theorem 1, Section 8.3], it holds that there exists two tuples $(a_1, b_1)$ and $(a_2, b_2)$ in $\mathbb{R}^2$ such that

$$ \mu_0 = \min_{g \in \mathcal{S}} \left\{ \int L_z(\theta) g(\theta) dQ(\theta) + \frac{a_1}{\eta} \int f(g(\theta)) dQ(\theta) + b_1 + a_2 \int g(\theta) dQ(\theta) + b_2 \right\}, \quad (255a) $$

and moreover,

$$ 0 = \frac{a_1}{\eta} \int f(g^*(\theta)) dQ(\theta) + b_1, \quad \text{and} \quad (255b) $$

$$ 0 = a_2 \int g^*(\theta) dQ(\theta) + b_2. \quad (255c) $$

Hence, the proof continues by solving the ancillary optimization problem in (255), which allows the reformulation of the optimization problem in an unconstrained dual problem. This reformulation is possible as the tuples $(a_1, b_1)$ and $(a_2, b_2)$ are such that equalities (255b) and (255c) are satisfied, by definition.

Let the function $L: \mathcal{S} \to \mathbb{R}$ be such that

$$ L(g) = \int L_z(\theta) g(\theta) dQ(\theta) + \frac{a_1}{\eta} \int f(g(\theta)) dQ(\theta) + b_1 + a_2 \int g(\theta) dQ(\theta) + b_2. \quad (256) $$

Let $\hat{g}: \mathcal{M} \to \mathbb{R}$ be a function in $\mathcal{S}$. The Gateaux differential of the functional $L$ in (256) at $(g, \beta) \in \mathcal{S} \times \mathbb{R}$ in the direction of $\hat{g}$ is

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

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

$$ r(\alpha) = L(g + \alpha \hat{g}). \quad (258) $$

The proof follows by showing that the function $r$ in (258) is differentiable at zero, in order to prove the existence of the Gateaux differential in (257) for the functions $g$ and $\hat{g}$ and real values $a_1, b_1, a_2$ and $b_2$. To this end, note that

$$ r(\alpha) = \int L_z(\theta)(g(\theta) + \alpha \hat{g}(\theta)) dQ(\theta) + \frac{a_1}{\eta} \int f(g(\theta) + \alpha \hat{g}(\theta)) dQ(\theta) + b_1 + a_2 \int (g(\theta) + \alpha \hat{g}(\theta)) dQ(\theta) + b_2 \quad (259) $$

which can be rewritten as follows,

$$ r(\alpha) = \alpha \int \hat{g}(\theta)(a_2 + L_z(\theta)) dQ(\theta) + \frac{a_1}{\eta} \int f(g(\theta) + \alpha \hat{g}(\theta)) dQ(\theta) + \int g(\theta)(a_2 + L_z(\theta)) dQ(\theta) + b_1 + b_2. \quad (260) $$

Note that the first term in (260) is linear with $\alpha$; the second term can be written using the function $\hat{r}: \mathbb{R} \to \mathbb{R}$ such that for all $\alpha \in (-\epsilon, \epsilon)$, with $\epsilon$ arbitrarily small, it holds that

$$ \hat{r}(\alpha) = \lambda \int f(g(\theta) + \alpha \hat{g}(\theta)) dQ(\theta); \quad (261) $$

and the remaining terms are independent of $\alpha$. Hence, based on the fact that the function $\hat{r}$ in (261) is differentiable at zero (see Lemma 13 in Appendix A), so is the function $r$ in (260), which implies that the Gâteaux differential of $\partial L(g, \hat{g})$ in (257) exists.
The proof proceeds by calculating the Gateaux differential $\partial L(g, \hat{g})$ in (257), which requires calculating the derivative of the real function $r$ in (260). That is,

$$ \frac{d}{d\alpha} r(\alpha) = \frac{d}{d\alpha} \left( \alpha \int \hat{g}(\boldsymbol{\theta}) (a_2 + \mathbf{L}_z(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) + \frac{a_1}{\eta} \int f(g(\boldsymbol{\theta}) + \alpha \hat{g}(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) \right. \\ \left. + \int g(\boldsymbol{\theta}) (a_2 + \mathbf{L}_z(\boldsymbol{\theta})) \, dQ(\boldsymbol{\theta}) + b_1 + b_2 \right) \qquad (262) $$

$$ = \int \hat{g}(\boldsymbol{\theta}) (a_2 + \mathbf{L}_z(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) + \frac{a_1}{\eta} \int \frac{d}{d\alpha} f(g(\boldsymbol{\theta}) + \alpha \hat{g}(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) \qquad (263) $$

$$ = \int \hat{g}(\boldsymbol{\theta}) (a_2 + \mathbf{L}_z(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) + \frac{a_1}{\eta} \int \hat{g}(\boldsymbol{\theta}) \dot{f}(g(\boldsymbol{\theta}) + \alpha \hat{g}(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) \qquad (264) $$

where (263) follows from Theorem 7. From equations (257) and (264), it follows that

$$ \partial L(g; \hat{g}) = \int \hat{g}(\boldsymbol{\theta}) (a_2 + \mathbf{L}_z(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) + \frac{a_1}{\eta} \int \hat{g}(\boldsymbol{\theta}) \dot{f}(g(\boldsymbol{\theta})) dQ(\boldsymbol{\theta}) \qquad (265a) $$

$$ = \int \hat{g}(\boldsymbol{\theta}) \left( a_2 + \mathbf{L}_z(\boldsymbol{\theta}) + \frac{a_1}{\eta} \dot{f}(g(\boldsymbol{\theta})) \right) dQ(\boldsymbol{\theta}). \qquad (265b) $$

From [85, Theorem 1, Chapter 7], a necessary condition to use for the functional $L$ in (256) to have a minimum at $g^*$ is that for all functions $\hat{g} \in \mathcal{S}$,

$$ \partial L(g^*; \hat{g}) = 0. \qquad (266) $$

From (265b) and (266), it follows that $g^*$ must satisfy for all $\boldsymbol{\theta} \in \text{supp } Q$, that

$$ \mathbf{L}_z(\boldsymbol{\theta}) + \frac{a_1}{\eta} \dot{f}(g^*(\boldsymbol{\theta})) + a_2 = 0. \qquad (267) $$

Assuming that

$$ a_1 \neq 0, \qquad (268) $$

it follows from (267) that

$$ g^*(\boldsymbol{\theta}) = \dot{f}^{-1} \left( -\frac{\eta}{a_1} (\mathbf{L}_z(\boldsymbol{\theta}) + a_2) \right), \qquad (269) $$

where the values $a_1$ and $a_2$ satisfy (255b) and (255c) and (268).

The remainder of the proof focuses on determining the values of $a_1$, $a_2$, $b_1$, and $b_2$, which must also be such that $g^*$ in (269) satisfies the constraints (253b) and (253c) under the assumption that $\mathbf{L}_z$ in (9) is separable. For instance, from constraints (253b) and (255c), it follows that

$$ a_2 = -b_2. \qquad (270) $$

From (270), the constraint in (255c) implies that the choice of $a_2$ satisfies

$$ 1 = \int g^*(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}). \qquad (271) $$

Similarly, the function $g^*$ in (269) is the Radon-Nikodym derivative with respect to $Q$ of the solution $P^* \in \Delta(\mathcal{M})$ to the problem in (251). Hence, (255b) can be written as follows

$$ \frac{a_1}{\eta} \mathrm{D}_f(P^* \| Q) + b_1 = 0, \qquad (272) $$

which implies

$$ b_1 = -\frac{a_1}{\eta} \mathrm{D}_f(P^* \| Q). \qquad (273) $$

Note that if $a_1 < 0$, then the function $g^*$ in (269) is strictly increasing with respect to the empirical risk $\mathbf{L}_z$ in (9). Then, from Lemma 17 in Appendix A, it follows that

$$ \mathbf{R}_z(P^*) > \mathbf{R}_z(Q). \qquad (274) $$

Note that from Definition 1, for all $P \in \Delta_Q(\mathcal{M})$, it follows that

$$ \mathrm{D}_f(Q \| Q) \le \mathrm{D}_f(P \| Q), \qquad (275) $$
with equality, if and only if $P = Q$. Hence, (274) and (275) imply

$$R_z(Q) + \lambda D_f(Q \| Q) < R_z(P^*) + \lambda D_f(P^* \| Q), \quad (276)$$

which is a contradiction. Thus, the focus in the remainder of the proof is on the case in which

$$a_1 > 0, \quad (277)$$

which implies that for models $\theta_1$ and $\theta_2$ in supp $Q$ satisfying $L_z(\theta_1) < L_z(\theta_2)$, it holds that

$$g^*(\theta_1) > g^*(\theta_2). \quad (278)$$

Given the pairs $(a_1, a_2)$ and $(\hat{a}_1, \hat{a}_2)$ in $\mathbb{R}^2$ such that each pair satisfies the constraints in (255b) and (255c), from (269) there exists a solution for each pair given by

$$g^*(\theta) = \dot{f}^{-1}\left(-\frac{\eta}{a_1}(L_z(\theta) + a_2)\right), \quad (279)$$

and

$$\hat{g}^*(\theta) = \dot{f}^{-1}\left(-\frac{\eta}{\hat{a}_1}(L_z(\theta) + \hat{a}_2)\right), \quad (280)$$

where the functions $g^*$ and $\hat{g}^*$ are the Radon-Nikodym derivative of the solutions $P^*$ and $\hat{P}^*$ with respect to $Q$ for each pair $(a_1, a_2)$ and $(\hat{a}_1, \hat{a}_2)$, respectively. Since $f$ is strictly convex, Lemma 14 in Appendix A implies that $\dot{f}^{-1}$ is strictly increasing. Moreover, by Lemma 18 in Appendix A it follows that

$$R_z(P^*) < R_z(\hat{P}^*). \quad (281)$$

From (281) and the assumption of $a_1 < \hat{a}_1$, it follows that

$$\frac{d}{da_1} R_z(P^*) = \frac{d}{da_1} \int L_z(\theta) dP^*(\theta) \quad (282a)$$

$$= \lim_{\hat{a}_1 \to a_1} \frac{\int L_z(\theta) d\hat{P}^*(\theta) - \int L_z(\theta) dP^*(\theta)}{\hat{a}_1 - a_1} \quad (282b)$$

$$> 0, \quad (282c)$$

where (282c) follows from (281). The proof continues by showing the induced $f$-divergence by the function $f$ is increasing with respect to $a_1$, which is equivalent to showing that the derivative of $D_f$ with respect to $a_1$ is always positive. To do so, note that from Assumption (a) in Theorem 1 specifically, the strict convexity, it follows from Jensen inequality that

$$D_f(P^* \| Q) - D_f(\hat{P}^* \| Q) = \int f(g^*(\theta)) dQ(\theta) - \int f(\hat{g}^*(\theta)) dQ(\theta) \quad (283a)$$

$$= \int f(g^*(\theta)) - f(\hat{g}^*(\theta)) dQ(\theta) \quad (283b)$$

$$> \int \dot{f}(\hat{g}^*(\theta))(g^*(\theta) - \hat{g}^*(\theta)) dQ(\theta) \quad (283c)$$

$$= \int \dot{f}\left(\dot{f}^{-1}\left(-\frac{\eta}{\hat{a}_1}(L_z(\theta) + \hat{a}_2)\right)\right)(g^*(\theta) - \hat{g}^*(\theta)) dQ(\theta) \quad (283d)$$

$$= \int -\frac{\eta}{\hat{a}_1}(L_z(\theta) + \hat{a}_2)(g^*(\theta) - \hat{g}^*(\theta)) dQ(\theta) \quad (283e)$$

$$= \int \frac{\eta}{\hat{a}_1}(L_z(\theta) + \hat{a}_2)\hat{g}^*(\theta) - \frac{\eta}{\hat{a}_1}(L_z(\theta) + \hat{a}_2)g^*(\theta) dQ(\theta) \quad (283f)$$

$$= \int \frac{\eta}{\hat{a}_1}(L_z(\theta) + \hat{a}_2)\hat{g}^*(\theta) dQ(\theta) - \int \frac{\eta}{\hat{a}_1}(L_z(\theta) + \hat{a}_2)g^*(\theta) dQ(\theta) \quad (283g)$$

$$= \int \frac{\eta}{\hat{a}_1}(L_z(\theta) + \hat{a}_2) d\hat{P}^*(\theta) - \int \frac{\eta}{\hat{a}_1}(L_z(\theta) + \hat{a}_2) dP^*(\theta) \quad (283h)$$

$$= \frac{\eta}{\hat{a}_1} \left( \int L_z(\theta) d\hat{P}^*(\theta) + \hat{a}_2 - \int L_z(\theta) dP^*(\theta) - \hat{a}_2 \right) \quad (283i)$$

$$= \frac{\eta}{\hat{a}_1} \left( \int L_z(\theta) d\hat{P}^*(\theta) - \int L_z(\theta) dP^*(\theta) \right) \quad (283j)$$

$$= \frac{\eta}{\hat{a}_1}(R_z(\hat{P}^*) - R_z(P^*)) \quad (283k)$$

$$> 0, \quad (283l)$$
where (283c) follows from first-order condition (see [81, Section 3.1.3]); (283d) follows from (280); (283h) follows from (235) and (236); and (283l) follows from (281) and the facts that $0 < \eta, \hat{a}_1$. Observe that from (283) and the assumption of $a_1 < \hat{a}_1$, it follows that

$$ \frac{d}{da_1} D_f(P^*\|Q) = \frac{d}{da_1} \int f(g^*(\theta)) dQ(\theta) \qquad (284) $$

$$ = \lim_{\hat{a}_1 \to a_1} \frac{D_f(P^*\|Q) - D_f(\hat{P}^*\|Q)}{a_1 - \hat{a}_1} \qquad (285) $$

$$ < 0, \qquad (286) $$

where (286) follows from (283l) and that $a_1 - \hat{a}_1 < 0$. Hence, from (282) the term $\int g^*(\theta)L_z(\theta)dQ(\theta)$ in (251b) is strictly increasing with $a_1$ and from (286) the term $\int f(g^*(\theta))dQ(\theta)$ in (251c) is strictly decreasing with $a_1$. This implies that $a_1 > 0$ shall be chosen such that

$$ D_f(P^*\|Q) = \eta, \qquad (287) $$

and justify the uniqueness of the solution.

For the case in which the empirical risk function $L_z$ in (9) is nonseparable (see Definition 2), the objective function in (12) is a constant. Hence, the optimization problems in (11) and (12) do not share the same solutions when for all $\theta \in \text{supp } Q$, $L_z(\theta) = c$, for some $c > 0$ and $L_z$ in (9). More specifically, the set of solutions to (11) is the singleton $\{Q\}$, while the set of solutions to the problem in (12) is $\{P \in \Delta_Q(\mathcal{M}) : D_f(P\|Q) \le \eta\}$. Thus, the problem is ill-posted and justifies the need for Assumption (c) in Theorem 1.

Essentially, choosing a real value $\lambda = \frac{a_1}{\eta}$, the real $a_2$ to satisfy

$$ a_2 \in \left\{ t \in \mathbb{R} : \forall \theta \in \text{supp } Q, 0 < \hat{j}^{-1}\left(-\frac{t + L_z(\theta)}{\lambda}\right) \right\}, \qquad (288) $$

and denoting the solution $P^*$ as $P_{\Theta|Z=z}^{(Q,\lambda)}$, it holds that $g^*$ in (269) can be written as $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$, and thus, for all $(\theta) \in \text{supp } Q$,

$$ \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \hat{j}^{-1}\left(-\frac{L_z(\theta) + a_2}{\lambda}\right), \qquad (289) $$

where $\lambda$ is such that $D_f(P_{\Theta|Z=z}^{(Q,\lambda)}\|Q) = \eta$. This completes the proof. ■

# APPENDIX C

## PROOF OF LEMMA 1

*Proof:* The probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is absolutely continuous with respect to $Q$ from the fact that $P_{\Theta|Z=z}^{(Q,\lambda)} \in \Delta_Q(\mathcal{M})$. Additionally, for all sets $A \in \mathcal{F}$, such that $P_{\Theta|Z=z}^{(Q,\lambda)}(A) = 0$, it holds that

$$ 0 = \int_A dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \qquad (290) $$

$$ = \int_A \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta), \qquad (291) $$

which implies, from the fact that $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ} > 0$ for all $\theta \in \text{supp } Q$, that $Q(A) = 0$. Thus, the probability measures $Q$ and $P_{\Theta|Z=z}^{(Q,\lambda)}$ are mutually absolutely continuous. This completes the proof. ■

# APPENDIX D

## PROOF OF THEOREM 3

*Proof:* The proof is divided into two parts. The first part uses the properties of the $f$-divergence regularization to prove the properties of an ancillary function. The second part proves that the normalization function $N_{Q,z} : A_{Q,z} \to B_{Q,z}$, with $N_{Q,z}$ implicitly defined in (46), has a unique solution and is continuous by using the implicit function theorem on the ancillary function properties.

Under the assumptions (a), (b) and (c) from Theorem 1, the sets $A_{Q,z}$ and $B_{Q,z}$ in (46) are non-empty such that

$$ \bar{a} = \sup A_{Q,z}, \qquad (292) $$

$$ \underline{a} = \inf A_{Q,z}, \qquad (293) $$

$$ \bar{b} = \sup B_{Q,z}, \text{ and} \qquad (294) $$

$$ \underline{b} = \inf B_{Q,z}, \qquad (295) $$
such that

$$
\mathcal{A} = (a, \bar{a}) \subseteq (0, \infty), \text{ and} \tag{296a}
$$

$$
\mathcal{B} = (\underline{b}, \bar{b}) \subseteq \mathbb{R}. \tag{296b}
$$

Let the function $F : \mathcal{A} \times \mathcal{B} \rightarrow \mathbb{R}$ be

$$
F(a, b) = \int \dot{f}^{-1} \left( - \frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}) - 1. \quad (297)
$$

The first part is as follows. Given the function $F$ in (297), the continuity of $F$ over the sets $\mathcal{A}$ and $\mathcal{B}$, defined in (296), is established by showing that $F$ exhibits a limit at every point in $\mathcal{A}$ and $\mathcal{B}$, respectively. Note that due to the strict convexity and differentiability of $f$, satisfying the normalization constraint (15b) requires the argument of $\dot{f}^{-1}$ (equivalently $\dot{f}^*$) to lie strictly within the interior of the conjugate's domain. This guarantees the density remains finite. In other words, for all $(a, b) \in \mathcal{A} \times \mathcal{B}$ and $\boldsymbol{\theta} \in \text{supp } \mathcal{Q}$, it holds that

$$
\dot{f}^{-1} \left( \frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) \le \dot{f}^{-1} \left( - \frac{b + \delta_{Q,z}^*}{a} \right) < \infty, \quad (298)
$$

where equality holds if and only if $\mathbf{L}_z(\boldsymbol{\theta}) = \delta_{Q,z}^*$. Now, from [83, Corollary 24.5.1] the function $\dot{f}^{-1}$ is continuous, such that for all $b \in \mathcal{B}$, it holds that

$$
\lim_{b \to \beta} \dot{f}^{-1} \left( \frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) = \dot{f}^{-1} \left( \frac{-\beta - \mathbf{L}_z(\boldsymbol{\theta})}{a} \right). \quad (299)
$$

Hence, from the dominated convergence theorem [82, Theorem 1.6.9], the following limit exists and satisfies

$$
\lim_{b \to \beta} F(a, b) = \lim_{b \to \beta} \int \dot{f}^{-1} \left( - \frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}) - 1 \quad (300)
$$

$$
= \int \left( \lim_{b \to \beta} \dot{f}^{-1} \left( - \frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) \right) dQ(\boldsymbol{\theta}) - 1 \quad (301)
$$

$$
= \int \dot{f}^{-1} \left( - \frac{\beta + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}) - 1 \quad (302)
$$

$$
= F(a, \beta), \tag{303}
$$

which proves that the function $F$ in (297) is continuous in $\mathcal{B}$. Similarly, from [83, Corollary 24.5.1] the function $\dot{f}^{-1}$ is
continuous, such that for all $a \in \mathcal{A}$, it holds that

$$
\lim_{a \to \lambda} \dot{f}^{-1} \left( \frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) = \dot{f}^{-1} \left( \frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right). \quad (304)
$$

Hence, from the dominated convergence theorem [82, Theorem 1.6.9], the following limit exists and satisfies

$$
\lim_{a \to \lambda} F(a, b) = \lim_{a \to \lambda} \int \dot{f}^{-1} \left( \frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}) - 1 \quad (305)
$$

$$
= \int \left( \lim_{a \to \lambda} \dot{f}^{-1} \left( \frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) \right) dQ(\boldsymbol{\theta}) - 1 \quad (306)
$$

$$
= \int \dot{f}^{-1} \left( \frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{\lambda} \right) dQ(\boldsymbol{\theta}) - 1 \quad (307)
$$

$$
= F(\lambda, b), \tag{308}
$$

which proves that the function $F$ in (297) is continuous in $\mathcal{A}$. Given a pair $(a, b) \in \mathcal{A}_{Q,z} \times \mathcal{B}_{Q,z}$, with $\mathcal{A}_{Q,z}$ in (46), assume that

$$
N_{Q,z}(a) = b. \tag{309}
$$

This implies that

$$
0 = \int \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,b)}}{\mathrm{d}Q}(\boldsymbol{\theta}) \mathrm{d}Q(\boldsymbol{\theta}) - 1 \quad (310)
$$

$$
= \int \dot{f}^{-1} \left( - \frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}). \quad (311)
$$

$$
= F(a, b). \tag{312}
$$

Note that the inverse $\dot{f}^{-1}$ exists from the fact that $f$ is strictly convex, which implies that $\dot{f}$ is a strictly increasing function.
Hence, $\dot{f}^{-1}$ is also a strictly increasing function in $\mathcal{B}_{Q,z}$ [88, Theorem 5.6.9]. Moreover, from the assumption that $f$ is
strictly convex and differentiable, it holds that $\dot{f}$ is continuous [89, Proposition 5.44]. This implies that $\dot{f}^{-1}$ is continuous.
From Lemma 14 the function $\dot{f}^{-1}$ is strictly increasing such that for all $b \in \mathcal{B}_{Q,z}$ and for all $\theta \in \text{supp } Q$, it holds that

$$ \dot{f}^{-1}\left(-\frac{b+\mathbf{L}_z(\boldsymbol{\theta})}{a}\right) \le \dot{f}^{-1}\left(-\frac{b+\delta_{Q,z}^*}{a}\right), \quad (313) $$

with $\delta_{Q,z}^*$ defined in (63). Then, from (313) it follows that

$$ \int \dot{f}^{-1}\left(-\frac{b+\mathbf{L}_z(\boldsymbol{\theta})}{a}\right) dQ(\boldsymbol{\theta}) < \int \dot{f}^{-1}\left(-\frac{b+\delta_{Q,z}^*}{a}\right) dQ(\boldsymbol{\theta}) \quad (314) $$

$$ = \dot{f}^{-1}\left(-\frac{b+\delta_{Q,z}^*}{a}\right) \quad (315) $$

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

where (316) follows from $\mathcal{A}_{Q,z} \subseteq (0, \infty)$, which implies $a > 0$. For all $(b_1, b_2) \in \mathcal{B}_{Q,z}^2$, such that $b_1 < b < b_2$, it holds that for all $\theta \in \text{supp } Q$,

$$ -\frac{1}{a}(\mathbf{L}_z(\boldsymbol{\theta}) + b_1) > -\frac{1}{a}(\mathbf{L}_z(\boldsymbol{\theta}) + b) > -\frac{1}{a}(\mathbf{L}_z(\boldsymbol{\theta}) + b_2), \quad (317) $$

which from Lemma 14 implies that

$$ \dot{f}^{-1}\left(-\frac{1}{a}(\mathbf{L}_z(\boldsymbol{\theta}) + b_1)\right) > \dot{f}^{-1}\left(-\frac{1}{a}(\mathbf{L}_z(\boldsymbol{\theta}) + b)\right) > \dot{f}^{-1}\left(-\frac{1}{a}(\mathbf{L}_z(\boldsymbol{\theta}) + b_2)\right). \quad (318) $$

From (318), it holds that

$$ F(a, b_1) > 0 > F(a, b_2), \quad (319) $$

which implies that the function $F$ in (297) is strictly monotonic with respect to $b$.

The second part is as follows. From the definition of $\mathcal{A}$ and $\mathcal{B}$ in (296) there exists at least one point $(\lambda, \beta) \in \mathcal{A} \times \mathcal{B}$, such that

$$ (\lambda, \beta) \in \mathcal{A}_{Q,z} \times \mathcal{B}_{Q,z}, \quad (320) $$

which implies that

$$ F(\lambda, \beta) = \int \dot{f}^{-1}\left(-\frac{\beta + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) dQ(\boldsymbol{\theta}) - 1 \quad (321) $$

$$ = \int \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}) - 1 \quad (322) $$

$$ = \int dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) - 1 \quad (323) $$

$$ = 0. \quad (324) $$

Note that from (300) and (305) the function $F$ is continuous and thus the partial derivative of $F$ satisfy

$$ \frac{\partial}{\partial a} F(a, b) = \frac{\partial}{\partial a} \left( \int \dot{f}^{-1} \left( -\frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}) - 1 \right) \quad (325) $$

$$ = \int \frac{\partial}{\partial a} \dot{f}^{-1} \left( -\frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}) \quad (326) $$

$$ = \int \frac{d}{da} \dot{f}^{-1} \left( -\frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}) \quad (327) $$

$$ = \int \frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a^2} \frac{1}{\ddot{f}\left(\dot{f}^{-1}\left(-\frac{b+\mathbf{L}_z(\boldsymbol{\theta})}{a}\right)\right)} dQ(\boldsymbol{\theta}), \quad (328) $$

where (328) follows from Lemma 15; and

$$ \frac{\partial}{\partial b} F(a, b) = \frac{\partial}{\partial b} \left( \int \dot{f}^{-1} \left( -\frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}) - 1 \right) \quad (329) $$

$$ = \int \frac{\partial}{\partial b} \dot{f}^{-1} \left( -\frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}) \quad (330) $$

$$ = \int \frac{d}{db} \dot{f}^{-1} \left( -\frac{b + \mathbf{L}_z(\boldsymbol{\theta})}{a} \right) dQ(\boldsymbol{\theta}) \quad (331) $$

$$ = \int -\frac{1}{a} \frac{1}{\ddot{f}\left(\dot{f}^{-1}\left(-\frac{b+\mathbf{L}_z(\boldsymbol{\theta})}{a}\right)\right)} dQ(\boldsymbol{\theta}), \quad (332) $$
where (332) follows from Lemma 15. Note that, for all $(a, b) \times A \times B$, the partial derivative $\frac{\partial}{\partial b}F$, satisfies,

$$ \frac{\partial}{\partial b} F(a, b) < 0, \qquad (333) $$

The fact that $a > 0$, together with the strict convexity and twice differentiability of $f$, implies that for all $u \in \mathbb{R}$, the function $\dot{f}$ satisfies, $\dot{f}(u) > 0$. Then, from *The Implicit Function Theorem* in [90, Theorem 4] the function $N_{Q,z}$ exists and is unique in the open interval $A$ with $A$ in (296) and for all $a \in A$ satisfies

$$ N_{Q,z}(a)=b, \qquad (334) $$

such that

$$ F(a, N_{Q,z}(a))=0, \qquad (335) $$

which completes the proof of continuity and uniqueness for the normalization function $N_{Q,z}$.

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

# APPENDIX E

## PROOF OF THEOREM 4

*Proof:* Recall the function $F$ defined in (297), together with its partial derivatives $\frac{\partial F}{\partial a}$ and $\frac{\partial F}{\partial b}$, introduced in (325) and (329), respectively. Then, from Theorem 3 and [90, Theorem 4], the derivative of the normalization function $N_{Q,z}$ satisfies

$$ \frac{d}{da} N_{Q,z}(a) = - \left( \frac{\partial}{\partial b} F(a, b) \right)^{-1} \frac{\partial}{\partial a} F(a, b), \qquad (336) $$

$$ = - \frac{\int \frac{b + L_z(\boldsymbol{\theta})}{a^2} \frac{1}{\ddot{f}\left(\dot{f}^{-1}\left(-\frac{b+L_z(\boldsymbol{\theta})}{a}\right)\right)} dQ(\boldsymbol{\theta})}{\int -\frac{1}{a} \frac{1}{\ddot{f}\left(\dot{f}^{-1}\left(-\frac{b+L_z(\boldsymbol{\nu})}{a}\right)\right)} dQ(\boldsymbol{\nu})} \qquad (337) $$

$$ = \frac{\int \frac{b + L_z(\boldsymbol{\theta})}{a} \frac{1}{\ddot{f}\left(\dot{f}^{-1}\left(-\frac{b+L_z(\boldsymbol{\theta})}{a}\right)\right)} dQ(\boldsymbol{\theta})}{\int \frac{1}{\ddot{f}\left(\dot{f}^{-1}\left(-\frac{b+L_z(\boldsymbol{\nu})}{a}\right)\right)} dQ(\boldsymbol{\nu})} \qquad (338) $$

$$ = \frac{\int \frac{b + L_z(\boldsymbol{\theta})}{a} \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,a)}}{dQ}(\boldsymbol{\theta}) \right) \right)^{-1} dQ(\boldsymbol{\theta})}{\int \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,a)}}{dQ}(\boldsymbol{\nu}) \right) \right)^{-1} dQ(\boldsymbol{\nu})} \qquad (339) $$

$$ = \frac{b}{a} + \frac{1}{a} \frac{\int L_z(\boldsymbol{\theta}) \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,a)}}{dQ}(\boldsymbol{\theta}) \right) \right)^{-1} dQ(\boldsymbol{\theta})}{\int \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,a)}}{dQ}(\boldsymbol{\nu}) \right) \right)^{-1} dQ(\boldsymbol{\nu})} \qquad (340) $$

$$ = \frac{b}{a} + \frac{1}{a} \frac{\int L_z(\boldsymbol{\theta}) \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,a)}}{dQ}(\boldsymbol{\theta}) \right) \right)^{-1} dQ(\boldsymbol{\theta})}{\int \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,a)}}{dQ}(\boldsymbol{\nu}) \right) \right)^{-1} dQ(\boldsymbol{\nu})} \qquad (341) $$

$$ = \frac{b}{a} + \int \frac{L_z(\boldsymbol{\theta})}{a} g_a(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}), \qquad (342) $$

$$ = \frac{N_{Q,z}(a)}{a} + \int \frac{L_z(\boldsymbol{\theta})}{a} g_a(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}), \qquad (343) $$
with the function $g_a : \mathcal{M} \to \mathbb{R}$, such that for all $\theta \in \text{supp } Q$

$$ g_a(\theta) = \frac{\left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,a)}}{dQ}(\theta) \right) \right)^{-1}}{\int \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,a)}}{dQ}(\nu) \right) \right)^{-1} dQ(\nu)}. \quad (344) $$

Note that from the assumption that $f$ is strictly convex and twice differentiable, the derivative $\dot{f}$ is increasing, and the second derivative $\ddot{f}$ is positive for all $\theta \in \text{supp } Q$. The denominator is the integral of the numerator with respect to $Q$, and thus, it serves as a normalization constant. This ensures that $g_a$ constitutes a valid Radon-Nikodym derivative with respect to $Q$ that satisfies

$$ \int g_a(\theta) \, dQ(\theta) = 1. \quad (345) $$

Therefore, the function $g_a$ in (344) can be interpreted as the Radon-Nikodym derivative of a new probability measure $P^{(a)}$, parameterized by the regularization factor $a$ with respect to $Q$. Specifically, if the measure $P^{(a)}$ is defined such that for any set $A \in \mathcal{F}_M$,

$$ P^{(a)}(A) = \int_A g_a(\theta) \, dQ(\theta). \quad (346) $$

From (343) and (346), it follows that

$$ N_{Q,z}(a) = a \frac{d}{da} N_{Q,z}(a) - \int L_z(\theta) \frac{dP^{(a)}}{dQ}(\theta) dQ(\theta) \quad (347) $$

$$ = a \frac{d}{da} N_{Q,z}(a) - R_z(P^{(a)}), \quad (348) $$

with $R_z$ defined in (10). This completes the proof. ■

# APPENDIX F

## PROOF OF LEMMA 3

*Proof:* From the implicit function theorem the derivative of the normalization function satisfies

$$ \frac{d}{d\lambda} N_{Q,z}(\lambda) = - \left( \frac{\partial}{\partial \beta} F(\lambda, \beta) \right)^{-1} \frac{\partial}{\partial \lambda} F(\lambda, \beta), \quad (349) $$

$$ = \frac{\int \frac{\beta + L_z(\theta)}{\lambda} \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) \right)^{-1} dQ(\theta)}{\int \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\nu) \right) \right)^{-1} dQ(\nu)} \quad (350) $$

$$ = \frac{\int -\dot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) \right)^{-1} dQ(\theta)}{\int \left( \ddot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\nu) \right) \right)^{-1} dQ(\nu)} \quad (351) $$

$$ = \frac{\int -\dot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) \ddot{f}^* \left( \dot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) \right) dQ(\theta)}{\int \ddot{f}^* \left( \dot{f} \left( \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\nu) \right) \right) dQ(\nu)} \quad (352) $$

Let the function $\psi : \mathbb{R} \to \mathbb{R}$ be

$$ \psi(y) = \frac{\ddot{f}^*(y)}{\dot{f}^*(y)} = \frac{d}{dy} \log(\dot{f}^*(y)). \quad (353) $$
Then, from (352) and (353),

$$ \frac{d}{d\lambda} N_{Q,z}(\lambda) = \frac{\int \frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta})}{\int \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta})}. \quad (354) $$

Note that under Assumptions (a), it holds that for all $v \in \mathcal{J}$, the functions $\dot{f}^{-1}$ and $\dot{f}^*$ satisfy $\dot{f}^{-1}(t) = \dot{f}^*(t)$. Hence, together with the assumption that $\dot{f}^{-1}$ is log convex, it implies that the function $\psi$ is increasing. Therefore, the map $\mathrm{L}_z(\boldsymbol{\theta}) \mapsto \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta})+\beta}{\lambda}\right)$ is decreasing with respect to the empirical risk $\mathrm{L}_z(\boldsymbol{\theta})$. Now consider the integral

$$ \int \frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}). \quad (355) $$

This quantity can be analyzed and upper-bounded by evaluating the covariance between the functions $\frac{\mathrm{L}_z(\boldsymbol{\theta})+\beta}{\lambda}$ and $\psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta})+\beta}{\lambda}\right)$ under the measure $P_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}$. Since models $\boldsymbol{\theta} \in \mathcal{M}$ are sampled independently and identically according to the probability measure $P_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}$, it follows that

$$ \frac{1}{2} \iint \left( \frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} - \frac{\mathrm{L}_z(\boldsymbol{\nu}) + \beta}{\lambda} \right) \left( \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) - \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\nu}) + \beta}{\lambda}\right) \right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\nu}) = \frac{1}{2} \left( \int \frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right. \\ = \left. \int \frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) $$

Observe that for all $(\boldsymbol{\theta}, \boldsymbol{\nu}) \in \text{supp } Q$ satisfying $\mathrm{L}_z(\boldsymbol{\nu}) \ge \mathrm{L}_z(\boldsymbol{\theta})$, it follows that

$$ \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) \le \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\nu}) + \beta}{\lambda}\right), \quad (358) $$

which implies

$$ \left( \frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} - \frac{\mathrm{L}_z(\boldsymbol{\nu}) + \beta}{\lambda} \right) \left( \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) - \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\nu}) + \beta}{\lambda}\right) \right) \le 0. \quad (359) $$

Similarly, for all $(\boldsymbol{\theta}, \boldsymbol{\nu}) \in \text{supp } Q$ such that $\mathrm{L}_z(\boldsymbol{\theta}) < \mathrm{L}_z(\boldsymbol{\nu})$, it holds that

$$ \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) > \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\nu}) + \beta}{\lambda}\right), \quad (360) $$

which implies

$$ \left( \frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} - \frac{\mathrm{L}_z(\boldsymbol{\nu}) + \beta}{\lambda} \right) \left( \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) - \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\nu}) + \beta}{\lambda}\right) \right) < 0. \quad (361) $$

Using (357), (359) and (361)

$$ \int \frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \le \int \frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \int \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) P_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}). \quad (362) $$

From (354) and (362) it follows that

$$ \frac{d}{d\lambda} N_{Q,z}(\lambda) \le \frac{\int \frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \int \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta})}{\int \psi\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda}\right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta})} \quad (363) $$

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

$$ = \int -\dot{f} \left( \frac{dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) \right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \quad (365) $$

$$ = - \int \frac{dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) \dot{f} \left( \frac{dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) \right) dQ(\boldsymbol{\theta}). \quad (366) $$

From Lemma 12 in Appendix A and (366), it follows that

$$ \frac{d}{d\lambda} N_{Q,z}(\lambda) \le 0. \quad (367) $$

which completes the proof.

<figure><img src="image_10.png" /></figure>
## APPENDIX G
### PROOF OF LEMMA 4

*Proof:* The proof is divided into two parts. In the first part, the strictly increasing property of the Radon-Nikodym derivative, obtained from the connection established with the Legendre-Fenchel transform of $f$, is used to evaluate the real values of $\lambda$ under which assumption (15a) holds. In the second part, the strictly increasing property is used to evaluate the real values of $\lambda$ under which assumption (15b) holds.

The first part is as follows. Lemma 16 in Appendix A, together with [83, Corollary 23.5.1], implies that for all $\theta \in \text{supp } Q$,

$$ \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) = \dot{f}^* \left( -\frac{\mathrm{L}_z(\theta) + \beta}{\lambda} \right) \qquad (368) $$

$$ = \dot{f}^{-1} \left( -\frac{\mathrm{L}_z(\theta) + \beta}{\lambda} \right). \qquad (369) $$

Evaluating the real values of $\lambda$ under which assumption in (15a) holds requires to show that the function $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ belongs to the set of nonnegative measurable functions. From the $f$-divergence in Definition 1 and the fact that $\dot{f}^{-1}$ strictly increasing and bijective, the proof follows by showing that the limit

$$ \lim_{u \to 0^+} \dot{f}(u) = v_0, \qquad (370) $$

satisfies for all $\theta \in \text{supp } Q$,

$$ -\frac{\mathrm{L}_z(\theta) + \beta}{\lambda} > v_0. \qquad (371) $$

Note that (371) is sufficient from the fact that the monotonicity of $\dot{f}^{-1}$ implies that for all $v > v_0$,

$$ \dot{f}^{-1}(v) > 0. \qquad (372) $$

To evaluate the real values of $\lambda$ under which assumption in (15a) holds, two cases must be considered for the limit in (370). **Case 1:** Assume that

$$ \lim_{u \to 0^+} \dot{f}(u) = a, \qquad (373) $$

where $a \in \mathbb{R}$. Under the above assumption, consider the set

$$ \mathcal{D} = \{ \theta \in \text{supp } Q : -\mathrm{L}_z(\theta) < a\lambda + \beta \}. \qquad (374) $$

On one hand, note that if the function $\mathrm{L}_z$ in (9) is unbounded in $\text{supp } Q$, from (373) the set $\mathcal{D}$ in (374) is noneworthy and measurable, such that for all $\theta \in \mathcal{D}$,

$$ -\frac{\mathrm{L}_z(\theta) + \beta}{\lambda} < a, \qquad (375) $$

which implies that

$$ \dot{f}^{-1} \left( -\frac{\mathrm{L}_z(\theta) + \beta}{\lambda} \right) < 0. \qquad (376) $$

Hence, Assumption (b) of Theorem 1 is not satisfied and nothing can be stated about the solution. On the other hand, if the function $\mathrm{L}_z$ in (9) is bounded in $\text{supp } Q$, such that

$$ M = \sup_{\theta \in \text{supp } Q} \mathrm{L}_z(\theta). \qquad (377) $$

Then, there exists a $\lambda_{Q,z} \in (0, \infty)$ such that

$$ -M = a\lambda_{Q,z} + \beta. \qquad (378) $$

From (378) for all $\lambda > \lambda_{Q,z}$, it holds that for all $\theta \in \text{supp } Q$,

$$ \dot{f}^{-1} \left( -\frac{\mathrm{L}_z(\theta) + \beta}{\lambda} \right) > 0. \qquad (379) $$

From (379), consider the following conditions: If there exists a model $\bar{\theta} \in \text{supp } Q$ such that $\mathrm{L}_z(\bar{\theta}) = M$, where $M$ is defined in (377), then the set of regularization factors $\lambda$ for which the function $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ is nonnegative is $(\lambda_{Q,z}, \infty)$. Alternatively, if for all models $\theta \in \text{supp } Q$, it holds that $\mathrm{L}_z(\theta) < M$, where $M$ is defined in (377), then the set of regularization factors $\lambda$ for which the function $\frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}$ is nonnegative is $[\lambda_{Q,z}, \infty)$.
**Case 2:** Assume that

$$ \lim_{u \to 0^+} \dot{f}(u) = -\infty. \qquad (380) $$

Under the above assumption, for all $\theta \in \text{supp } Q$,

$$ -\frac{\mathbf{L}_z(\theta) + \beta}{\lambda} > -\infty, \qquad (381) $$

which implies that

$$ \dot{f}^{-1}\left(-\frac{\mathbf{L}_z(\theta) + \beta}{\lambda}\right) > 0. \qquad (382) $$

Hence, for all $\lambda \in (0, \infty)$, Assumption (b) of Theorem 1 is satisfied, guaranteeing the nonnegativity of the function $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$. This completes the first part of the proof.

The second part is as follows. Evaluating the values $\lambda$ under which assumption (15b) holds requires to show there exists a real value $\beta \in \mathbb{R}$ such that the integral of $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ with respect to $Q$ is one. From Lemma 3 the monotonicity of the normalization function $N_{Q,z}$ in (46) there is a minimum regularization factor $\lambda_{Q,z}^*$ defined in (64). Furthermore, from Lemma 3 the continuity of the function $N_{Q,z}$ implies that for all $\lambda \in (\lambda_{Q,z}^*, \infty)$, there exists a unique $\beta \in \mathcal{B}_{Q,z}$ such that Assumption (b) of Theorem 1 is satisfied. From Lemma 3, it holds that

$$ \lim_{\lambda \to \lambda_{Q,z}^*} N_{Q,z}(\lambda) = N_{Q,z}(\lambda_{Q,z}^*), \qquad (383) $$

with the function $N_{Q,z}$ defined in (46) and the limit from the right is well defined from the fact that the set $\mathcal{A}_{Q,z}$ is convex. To determine whether the infimum in (64) belongs to the set $\mathcal{A}_{Q,z}$ two cases are considered.

**Case 1:** Assume that $\beta > N_{Q,z}(\lambda_{Q,z}^*)$, such that

$$ \int \dot{f}^{-1}\left(-\frac{\beta + \mathbf{L}_z(\theta)}{\lambda_{Q,z}^*}\right) dQ(\theta) = \infty. \qquad (384) $$

Notice that from (384) for all $\beta_1 \in [N_{Q,z}(\lambda_{Q,z}^*), \beta)$ and for all $\theta \in \text{supp } Q$, it holds that

$$ \dot{f}^{-1}\left(-\frac{\beta_1 + \mathbf{L}_z(\theta)}{\lambda_{Q,z}^*}\right) > \dot{f}^{-1}\left(-\frac{\beta + \mathbf{L}_z(\theta)}{\lambda_{Q,z}^*}\right). \qquad (385) $$

Hence, under this assumption, $N_{Q,z}(\lambda_{Q,z}^*) \notin \mathcal{B}_{Q,z}$. This implies that the set $\mathcal{A}_{Q,z}$ of regularization parameters that satisfy (15b) is given by $\mathcal{A}_{Q,z} = (\lambda_{Q,z}^*, \infty)$.

**Case 2:** Assume that $\beta > N_{Q,z}(\lambda_{Q,z}^*)$, such that

$$ \int \dot{f}^{-1}\left(-\frac{\beta + \mathbf{L}_z(\theta)}{\lambda_{Q,z}^*}\right) dQ(\theta) < \infty. \qquad (386) $$

From the monotonicity of the solution in part one and continuity of the function $N_{Q,z}$ in (46) from Lemma 3, there exists a $\beta_{Q,z}^* \in \mathcal{B}_{Q,z}$ such that $N_{Q,z}(\lambda_{Q,z}^*) = \beta_{Q,z}^*$, which implies that the set of all regularization factors $\mathcal{A}_{Q,z} = [\lambda_{Q,z}^*, \infty)$.

Finally, from parts two and three of the proof the set $\mathcal{A}_{Q,z}$ is a convex set such that the regularization factors for which the assumptions of Theorem 1 hold and are given by

$$ (\lambda_{Q,z}^*, \infty) \subseteq \mathcal{A}_{Q,z} \subseteq [\lambda_{Q,z}^*, \infty), \qquad (387) $$

which completes the proof.

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

# APPENDIX H

## PROOF OF LEMMA 5

*Proof:* The following proof is divided into two parts. In the first part, an auxiliary function is introduced and proven to be continuous. In the second part, relying on the assumption that $\dot{f}^{-1}$ is nonnegative and the previously established continuity of the auxiliary function, the intermediate value theorem is applied to prove the existence of a unique solution for any given regularization factor. Consequently, it is shown that the set of admissible regularization factors comprises the positive reals. The first part is as follows. Let the function $k: \mathbb{R} \to (0, \infty)$, be such that

$$ k(b) = \int \dot{f}^{-1}\left(-\frac{-b - \mathbf{L}_z(\theta)}{\lambda}\right) dQ(\theta). \qquad (388) $$
The first step is to prove that the function $k$ in (388) is continuous in $\mathbb{R}$. This is proved by showing that $k$ always exhibits a limit. Note that from Lemma 14 in Appendix A, the function $\dot{f}^{-1}$ is strictly increasing; thus, it holds that for all $b \in \mathcal{B}_{Q,z}$ with $\mathcal{B}_{Q,z}$ defined in (46) and for all $\theta \in \text{supp } Q$, it holds that

$$ \dot{f}^{-1}\left(\frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) \le \dot{f}^{-1}\left(-\frac{b}{\lambda}\right), \qquad (389) $$

where equality holds if and only if $\mathbf{L}_z(\boldsymbol{\theta}) = 0$. Now, from the [83, Corollary 24.5.1] the function $\dot{f}^{-1}$ is continuous, such that for all $\beta \in \mathcal{B}$, it holds that

$$ \lim_{b \to \beta} \dot{f}^{-1}\left(\frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) = \dot{f}^{-1}\left(\frac{-\beta - \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right). \qquad (390) $$

Hence, from the dominated convergence theorem [82, Theorem 1.6.9], the following limit exists and satisfies

$$ \lim_{b \to \beta} k(b) = \lim_{b \to \beta} \int \dot{f}^{-1}\left(\frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) dQ(\boldsymbol{\theta}) \qquad (391) $$

$$ = \int \left( \lim_{b \to \beta} \dot{f}^{-1}\left(\frac{-b - \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) \right) dQ(\boldsymbol{\theta}) \qquad (392) $$

$$ = \int \dot{f}^{-1}\left(\frac{-\beta - \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) dQ(\boldsymbol{\theta}) \qquad (393) $$

$$ = k(\beta), \qquad (394) $$

which proves that the function $k$ in (388) is continuous.

The second part proceeds as follows. Consider an arbitrary $\lambda \in (0, \infty)$. From [83, Corollary 24.5.1] and Lemma 14 in Appendix A, the function $\dot{f}^{-1}$ is continuous and strictly increasing. Consequently, the function $k(b)$ defined in (388) is strictly decreasing with respect to $b$. Given the range of $\dot{f}^{-1}$, there exist values $b_1 \in (b_{Q,z}^*, b)$ and $b_2 \in (b, \infty)$ such that the integral is bounded above and below unity

$$ \int \dot{f}^{-1}\left(\frac{-b_1 + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) dQ(\boldsymbol{\theta}) > 1 > \int \dot{f}^{-1}\left(\frac{-b_2 + \mathbf{L}_z(\boldsymbol{\theta})}{\lambda}\right) dQ(\boldsymbol{\theta}). \qquad (395) $$

Since $k(b)$ is continuous (as proven in the first part) and satisfies the bounds in (395), the intermediate-value theorem [91, Theorem 4.23] guarantees the existence of a real $b \in \mathcal{B}_{Q,z}$ such that $k(b) = 1$. Furthermore, the strict monotonicity of $k(b)$ ensures that this solution $b$ is unique for the chosen $\lambda$. Finally, since this result holds for any arbitrary $\lambda \in (0, \infty)$, it follows that the set of admissible regularization factors $\mathcal{A}_{Q,z}$ in (46a) is identical to $(0, \infty)$, which completes the proof. ■

# APPENDIX I

## PROOF OF LEMMA 6

*Proof:* For all $(\boldsymbol{\theta}_1, \boldsymbol{\theta}_2) \in (\text{supp } Q)^2$, such that

$$ \mathbf{L}_z(\boldsymbol{\theta}_1) \le \mathbf{L}_z(\boldsymbol{\theta}_2), \qquad (396) $$

it follows that

$$ -\frac{\mathbf{L}_z(\boldsymbol{\theta}_1) + N_{Q,z}(\lambda)}{\lambda} \le -\frac{\mathbf{L}_z(\boldsymbol{\theta}_2) + N_{Q,z}(\lambda)}{\lambda}, \qquad (397) $$

where the function $N_{Q,z}$ is defined in (46); and equality holds if and only if (397) holds with equality. From Lemma 14 in Appendix A, the function $\dot{f}^{-1}$ is strictly increasing. Then, the monotonicity of $\dot{f}^{-1}$ and (397) imply that

$$ \dot{f}^{-1}\left(-\frac{\mathbf{L}_z(\boldsymbol{\theta}_1) + \beta}{\lambda}\right) \ge \dot{f}^{-1}\left(-\frac{\mathbf{L}_z(\boldsymbol{\theta}_2) + \beta}{\lambda}\right). \qquad (398) $$

The proof is completed by noticing that from (398), the inequality above can be rewritten as

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

which completes the proof. ■
APPENDIX J

PROOF OF LEMMA 7

*Proof:* From Lemma 6, it follows that for all $\lambda > 0$ such that $\beta \in \mathcal{B}$, with $\mathcal{B}$ defined in (15a), it holds that for all $\theta \in \text{supp } Q$, and for all $\phi \in \mathcal{L}_{Q,z}^* \cap \text{supp } Q$,

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

$$ = j^{-1} \left( - \frac{L_z(\phi) + N_{Q,z}(\lambda)}{\lambda} \right) \quad (401) $$

$$ = j^{-1} \left( - \frac{\delta_{Q,z}^* + N_{Q,z}(\lambda)}{\lambda} \right) \quad (402) $$

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

where (400) follows from (16); (401) follows from the fact that $L_z(\phi) \ge \delta_{Q,z}^*$; and (403) follows from the fact that for all $\lambda > 0$, the function $N_{Q,z}(\lambda) < \infty$. From the definition of $\delta_{Q,z}^*$ in (63) and $\mathcal{L}_{Q,z}^*$ in (65) equality in (400) 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 1, it holds that for all $\theta \in \text{supp } Q$,

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

which completes the proof.

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

APPENDIX K

PROOF OF THEOREM 5

*Proof:* The Legendre-Fenchel transform of a strictly convex function $f: \mathcal{I} \to \mathbb{R}$ satisfies

$$ f^*(t) \triangleq \sup_{s \in \mathcal{I}} (ts - f(s)). \quad (405) $$

From [83, Theorem 23.5] if $f$ is strictly convex then maximizing argument of the convex conjugate $f^*$ satisfies

$$ f^*(t) = t \frac{d}{dt} f^*(t) - f\left(\frac{d}{dt} f^*(t)\right). \quad (406) $$

Furthermore, from [83, Corollary 23.5.1] the function $\dot{f}^{-1}$ is the derivative of the convex conjugate of $f$ in (406), which implies that Differential Equations

$$ f^*(t) = t \dot{f}^{-1}(t) - f(\dot{f}^{-1}(t)). \quad (407) $$

From Theorem 1, let $t = -\frac{L_z(\theta) + \beta}{\lambda}$ in (407), then it holds that for all $\theta \in \text{supp } Q$,

$$ f^*\left(-\frac{L_z(\theta) + \beta}{\lambda}\right) = -\frac{L_z(\theta) + \beta}{\lambda} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) - f\left(\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta)\right). \quad (408) $$

Taking the integral of (408) with respect to the reference measure $Q$, yields

$$ \int f^* \left( -\frac{L_z(\theta) + \beta}{\lambda} \right) dQ(\theta) = \int \left( -\frac{L_z(\theta) + \beta}{\lambda} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) - f\left(\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta)\right) \right) dQ(\theta) \quad (409) $$

$$ = -\frac{1}{\lambda} \left( \mathbb{R}_z \left( P_{\Theta|Z=z}^{(Q,\lambda)} \right) + \beta \right) - \mathbb{D}_f \left( P_{\Theta|Z=z}^{(Q,\lambda)} \| Q \right). \quad (410) $$

Arranging (410) results in

$$ \mathbb{R}_z \left( P_{\Theta|Z=z}^{(Q,\lambda)} \right) + \lambda \mathbb{D}_f \left( P_{\Theta|Z=z}^{(Q,\lambda)} \| Q \right) = -\lambda \int f^* \left( -\frac{L_z(\theta) + \beta}{\lambda} \right) dQ(\theta) - \beta, \quad (411) $$

which completes the proof.

The second part of the proof is as follows. From Lemma 1, equality (408) can be rewritten as

$$ \frac{L_z(\theta) + \beta}{\lambda} = -f^*\left(-\frac{L_z(\theta) + \beta}{\lambda}\right) \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) - \frac{dQ}{dP_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) f\left(\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta)\right). \quad (412) $$
Taking the integral of (412) with respect to the reference measure $Q$, yields

$$ \frac{1}{\lambda} \mathrm{R}_z(Q) + \frac{\beta}{\lambda} = - \int f^* \left( -\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} \right) \frac{\mathrm{d}Q}{\mathrm{d}P_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) \mathrm{d}Q(\boldsymbol{\theta}) - \int \frac{\mathrm{d}Q}{\mathrm{d}P_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) f \left( \frac{\mathrm{d}P_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) \right) \mathrm{d}Q(\boldsymbol{\theta}). \quad (413) $$

Arranging (413) results in

$$ \mathrm{R}_z(Q) + \lambda \int \frac{\mathrm{d}Q}{\mathrm{d}P_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) f \left( \frac{\mathrm{d}P_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) \right) \mathrm{d}Q(\boldsymbol{\theta}) = -\lambda \int f^* \left( -\frac{\mathrm{L}_z(\boldsymbol{\theta}) + \beta}{\lambda} \right) \frac{\mathrm{d}Q}{\mathrm{d}P_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) \mathrm{d}Q(\boldsymbol{\theta}) - \beta, \quad (414) $$

which completes the proof.

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

# APPENDIX L

## PROOF OF THEOREM 6

*Proof:* Note that from Theorem 1, the functions $f$ and $g$ are differentiable and strictly convex. Hence, the functional inverse of the derivative is well-defined from the fact that $\dot{f}$ and $\dot{g}$ are strictly increasing and bijective. Denote by $\hat{P}_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}$ the solution to the optimization problem in (110). Then, from Theorem 1, for all $\boldsymbol{\theta} \in \mathrm{supp} Q$, it follows that

$$ \frac{\mathrm{d}\hat{P}_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) = \dot{g}^{-1}\left(-\frac{\hat{N}_{Q,z}(\lambda) + v(\mathrm{L}_z(\boldsymbol{\theta}))}{\lambda}\right) \quad (415) $$

$$ = \dot{g}^{-1}\left(\dot{g}\left(\dot{f}^{-1}\left(-\frac{N_{Q,z}(\lambda) + \mathrm{L}_z(\boldsymbol{\theta})}{\lambda}\right)\right) + \frac{c - \hat{N}_{Q,z}(\lambda)}{\lambda}\right), \quad (416) $$

where $\hat{N}_{Q,z}$ is the normalization function of the optimization problem in (110). Then, under the assumption that $\hat{N}_{Q,z}$ satisfies $\hat{N}_{Q,z}(\lambda) > c$, from the monotonicity of $\dot{g}^{-1}$, for all $\boldsymbol{\theta} \in \mathrm{supp} Q$,

$$ \begin{aligned} \dot{g}^{-1}\left(\dot{g}\left(\dot{f}^{-1}\left(-\frac{N_{Q,z}(\lambda) + \mathrm{L}_z(\boldsymbol{\theta})}{\lambda}\right)\right) - \frac{\hat{N}_{Q,z}(\lambda) + c}{\lambda}\right) &< \dot{f}^{-1}\left(-\frac{N_{Q,z}(\lambda) + \mathrm{L}_z(\boldsymbol{\theta})}{\lambda}\right). \end{aligned} \quad (417) $$

Similarly, under the assumption that $\hat{N}_{Q,z}$ satisfies $\hat{N}_{Q,z}(\lambda) < c$, from the monotonicity of $\dot{g}^{-1}$, for all $\boldsymbol{\theta} \in \mathrm{supp} Q$,

$$ \begin{aligned} & \dot{g}^{-1}\left(\dot{g}\left(\dot{f}^{-1}\left(-\frac{N_{Q,z}(\lambda) + \mathrm{L}_z(\boldsymbol{\theta})}{\lambda}\right)\right) - \frac{\hat{N}_{Q,z}(\lambda) + c}{\lambda}\right) \\ & > \dot{f}^{-1}\left(-\frac{N_{Q,z}(\lambda) + \mathrm{L}_z(\boldsymbol{\theta})}{\lambda}\right). \end{aligned} \quad (418) $$

Note that $\hat{N}_{Q,z}$ needs to be such that,

$$ 1 = \int \frac{\mathrm{d}\hat{P}_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) \mathrm{d}Q(\boldsymbol{\theta}). \quad (419) $$

Under the assumption that $\hat{N}_{Q,z}(\lambda) > c$, from (417), it follows that

$$ \int \frac{\mathrm{d}\hat{P}_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) \mathrm{d}Q(\boldsymbol{\theta}) < \int \dot{f}^{-1}\left(-\frac{N_{Q,z}(\lambda) + \mathrm{L}_z(\boldsymbol{\theta})}{\lambda}\right) \mathrm{d}Q(\boldsymbol{\theta}) \quad (420) $$

$$ = 1. \quad (421) $$

Similarly, under the assumption that $\hat{N}_{Q,z}(\lambda) < c$, from (418), it follows that

$$ \int \frac{\mathrm{d}\hat{P}_{\boldsymbol{\theta}|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) \mathrm{d}Q(\boldsymbol{\theta}) > \int \dot{f}^{-1}\left(-\frac{N_{Q,z}(\lambda) + \mathrm{L}_z(\boldsymbol{\theta})}{\lambda}\right) \mathrm{d}Q(\boldsymbol{\theta}) \quad (422) $$

$$ = 1. \quad (423) $$

Therefore, the normalization function $\hat{N}_{Q,z}$ satisfies

$$ \hat{N}_{Q,z}(\lambda) = c. \quad (424) $$
Thus, from (416) and (424), for all $\theta \in \text{supp} Q$ that

$$ \frac{d\hat{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = j^{-1}\left(-\frac{N_{Q,z}(\lambda) + L_z(\theta)}{\lambda}\right) \qquad (425) $$

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

where (425) follows from (112), which completes the proof. ■

# APPENDIX M
## NUMERICAL SIMULATION

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 or seven, while 1,986 out of the 10,000 test images correspond to these digits. Each image is a 28 × 28 grayscale picture and is represented by the matrix $I \in [0, 1]^{28 \times 28}$.

### A. Feature Extraction of the Histogram of Oriented Gradients

The grayscale images are processed by calculating their corresponding histogram of oriented gradients (HOG) [92]. The HOG for each image is computed through the following steps:

1.) For each pixel location $(i, j) \in \{1, 2, ..., 28\}^2$ in the image, the gradients in the w- and h-directions (width, height) are computed using finite differences given by the functions $G_w : \{1, 2, ..., 28\}^2 \to \mathbb{R}$ and $G_h : \{1, 2, ..., 28\}^2 \to \mathbb{R}$, which are defined as

$$ G_w(i, j) = \begin{cases} I(i + 1, j) - I(i - 1, j) & \text{if } i \in \{2, \dots, 27\} \\ I(i + 1, j) - I(i, j) & \text{if } i = 1 \\ I(i, j) - I(i - 1, j) & \text{if } i = 28 \end{cases}, \qquad (427) $$

and

$$ G_h(i, j) = \begin{cases} I(i, j + 1) - I(i, j - 1) & \text{if } j \in \{2, \dots, 27\} \\ I(i, j + 1) - I(i, j) & \text{if } j = 1 \\ I(i, j) - I(i, j - 1) & \text{if } j = 28 \end{cases}, \qquad (428) $$

where $I(i, j) \in [0, 1]$ represents the pixel intensity at location $(i, j)$.

2.) Given a pixel location $(i, j) \in \{1, 2, ..., 28\}^2$, the magnitude and orientation of a pixel at location $(i, j)$ is given by the functions $M : \{1, 2, ..., 28\}^2 \to \mathbb{R}$ and $\phi : \{1, 2, ..., 28\}^2 \to \mathbb{R}$, such that

$$ M(i, j) = \sqrt{G_w(i, j)^2 + G_h(i, j)^2}, \quad \text{and} \qquad (429) $$

$$ \phi(i, j) = \arctan \left( \frac{G_h(i, j)}{G_w(i, j)} \right). \qquad (430) $$

3.) The matrix $I$ is divided into sub-matrices of size 4 × 4, such that the number of sub-matrices is 7. These sub-matrices are referred to as cells and are denoted, for all $(w, h) \in \{1, \dots, 7\}^2$, by

$$ C_{w,h} = \begin{bmatrix} I(a_w, b_h) & \cdots & I(a_w + 3, b_h) \\ \vdots & \ddots & \vdots \\ I(a_w, b_h + 3) & \cdots & I(a_w + 3, b_h + 3) \end{bmatrix}, \qquad (431) $$

where the real values $a_w$ and $b_h$ are

$$ a_w = 4(w - 1) + 1 \qquad (432) $$

$$ b_h = 4(h - 1) + 1. \qquad (433) $$

This implies that the matrix $I$ can be represented as

$$ I = \begin{bmatrix} C_{1,1} & \cdots & C_{7,1} \\ \vdots & \ddots & \vdots \\ C_{1,7} & \cdots & C_{7,7} \end{bmatrix}. \qquad (434) $$

From (431), the set of all pairs $(i, j)$ of pixel coordinates in $I$ that lie within the cell $C_{w,h}$ is given by:

$$ A_{w,h} = \{a_w, a_w + 3\} \times \{b_h, b_h + 3\}, \qquad (435) $$
with $a_w$ in (432) and $b_h$ in (433).

4.) For each cell $C_{w,h}$ in (431) the orientations $\phi(i, j)$ in (430) are divided into 9 bins. That is, the $n^{th}$ bin, with $1 \le n \le 9$, satisfies that

$$ B_{w,h}^{(n)} = \left\{ \phi(i,j) \in \mathbb{R} : 180 \left( \frac{n-1}{9} \right) \le \phi(i,j) < 180 \left( \frac{n}{9} \right) : (i,j) \in A_{w,h} \right\}. \quad (436) $$

The contribution of each pixel to its corresponding bin is based on its gradient magnitude. That is, the value of the $n$-th bin from the $(w, h)$-th cell $C_{w,h}$ in (431) is given by the function $H_{w,h}(n) : \{1, 2, \dots, 9\} \to \mathbb{R}$, such that

$$ H_{w,h}(n) = \sum_{(i,j) \in A_{w,h}} \mathrm{M}(i,j) \mathbf{1}_{\{\phi(i,j) \in B_{w,h}^{(n)}\}}, \quad (437) $$

with $\mathrm{M}$ in (429); and $B_{w,h}^{(n)}$ in (436). Thus, the histogram of gradient orientations of the cell $C_{w,h}$ is represented by the vector $\mathbf{H}_{w,h} \in \mathbb{R}^9$, such that

$$ \mathbf{H}_{w,h} = [H_{w,h}(1), H_{w,h}(2), \dots, H_{w,h}(9)], \quad (438) $$

with the function $H_{w,h}$ in (437).

5.) To account for illumination and contrast variations, the histogram $\mathbf{H}_{w,h}$ in (438) is normalized. To normalize the histograms for all cells $C_{w,h}$ in (431), the cells are grouped into sub-matrices formed by $2 \times 2$ cells with a cell overlap set to 1 pixel, such that the number of sub-matrices is:

$$ (7-1) \times (7-1) = 36. \quad (439) $$

These sub-matrices of the matrix $I$ in (434), with $(m, s) \in \{1, \dots, \sqrt{36}\}^2$ are referred to as blocks, and denoted by

$$ B_{m,s} = \begin{bmatrix} C_{m,s} & C_{m+1,s} \\ C_{m,s+1} & C_{m+1,s+1} \end{bmatrix}, \quad (440) $$

with the matrix $C_{m,s}$ in (431). From (434) and (440), a block $B_{m,s}$ is a sub-matrix of size $8 \times 8$, i.e., $B_{m,s} \in \mathbb{R}^{8 \times 8}$. The size of a block is given by the ratio of the total number of pixels in a block to the number of pixels in a cell:

$$ \frac{8 \times 8}{4 \times 4} = 4, \quad (441a) $$

The normalized histogram of a cell $C_{w,h}$ in a block $B_{m,s}$ is denoted by the vector $\hat{\mathbf{H}}_{w,h}^{(m,s)} \in \mathbb{R}^9$. This normalization of is typically done using the $l_2$-norm, such that

$$ \hat{\mathbf{H}}_{w,h}^{(m,s)} = \frac{\mathbf{H}_{w,h}}{\sqrt{\sum_{(i,j) \in \{m,m+1\} \times \{s,s+1\}} \mathbf{H}_{i,j}^2 + \epsilon^2}}, \quad (442) $$

where $\mathbf{H}_{w,h}$ in (438) is the unnormalized histogram, and $\epsilon = 10^{-4}$ to avoid division by zero.

6.) For an image with 36 blocks (see (439)), 9 orientation bins, and a block size of 4 (see (441)), the dimension of the HOG feature vector $\hat{\mathbf{x}}$ is:

$$ 36 \times 4 \times 9 = 1296. \quad (443) $$

The HOG feature vector $\hat{\mathbf{x}} \in \mathbb{R}^{1296}$ is formed by concatenating all the normalized histograms $\hat{\mathbf{H}}_{w,h}^{(m,s)}$ such that

$$ \hat{\mathbf{x}} = \begin{bmatrix} \hat{\mathbf{H}}_{1,1}^{(1,1)}, \hat{\mathbf{H}}_{1,2}^{(1,1)}, \hat{\mathbf{H}}_{2,1}^{(1,1)}, \hat{\mathbf{H}}_{2,2}^{(1,1)}, \\ \hat{\mathbf{H}}_{2,1}^{(2,1)}, \hat{\mathbf{H}}_{2,2}^{(2,1)}, \hat{\mathbf{H}}_{3,1}^{(2,1)}, \hat{\mathbf{H}}_{3,2}^{(2,1)}, \dots, \\ \hat{\mathbf{H}}_{6,6}^{(6,6)}, \hat{\mathbf{H}}_{6,7}^{(6,6)}, \hat{\mathbf{H}}_{7,6}^{(6,6)}, \hat{\mathbf{H}}_{7,7}^{(6,6)} \end{bmatrix}^{\top}. \quad (444) $$
## B. Principal Component Analysis

The final step in the data processing is to reduce the dimensionality of the pattern $\hat{x}$ in (444) from $\mathbb{R}^{1296}$ to $\mathbb{R}^2$, while ensuring that the important structure of the pattern is preserved. In this simulation, principal component analysis (PCA) is used to project the high-dimensional data onto a lower-dimensional subspace. From 60,000 images for training in the MNIST, the HOG of two handwritten numbers (in this simulation 6 and 7) are computed, as mentioned in Appendix M-A. The resulting 12,183 HOG vectors $\hat{x} \in \mathbb{R}^{1296}$ are reduced to $\mathbb{R}^2$ using PCA as follows:

1.) To reduce the dimensionality, the first step in PCA is to compute the covariance matrix of the data. This matrix captures the relationships between the different features (or dimensions) of the data. The covariance matrix is calculated as follows:

$$ C = \frac{1}{n-1} \sum_{i=1}^{n} (\hat{x}_i - \mu)(\hat{x}_i - \mu)^{\top}, \qquad (445) $$

where $n = 12,183$, $C \in \mathbb{R}^{1296 \times 1296}$, and $\mu$ is the mean of all the training patterns given by

$$ \mu = \frac{1}{n} \sum_{i=1}^{n} \hat{x}_{i}. \qquad (446) $$

2.) The next step in PCA is to perform an eigenvalue decomposition of the covariance matrix $C$ in (445). The decomposition can be written as:

$$ C = V\Lambda V^{\top}, \qquad (447) $$

where $V \in \mathbb{R}^{1296 \times 1296}$ is a matrix whose columns are the eigenvectors of $C$ and $\Lambda \in \mathbb{R}^{1296 \times 1296}$ is a diagonal matrix containing the corresponding eigenvalues.

3.) Following the computation of the eigenvectors, the dimensionality is reduced from $\mathbb{R}^{1296}$ to $\mathbb{R}^2$ by selecting the two eigenvectors associated with the largest eigenvalues. Denote these top two eigenvectors as $w_1$ and $w_2$. These eigenvectors constitute the columns of the projection matrix $W \in \mathbb{R}^{1296 \times 2}$, defined as

$$ W = [w_1 \ w_2]. \qquad (448) $$

4.) Once the projection matrix $W$ is computed, each high-dimensional pattern $\hat{x} \in \mathbb{R}^{1296}$ can be projected onto the new $\mathbb{R}^2$ subspace. The projection is performed as follows:

$$ x = W^{\top} \hat{x}, \qquad (449) $$

with $\hat{x}$ in (444), $W$ in (448) and $x \in \mathbb{R}^2$ represents the 2-dimensional coordinates of the original pattern $\hat{x}$ in the reduced-dimensional space.

## C. Simulation Dataset

In this simulation, a datapoint is a tuple $(\hat{x}, y) \in \mathbb{R}^{1296} \times \{6, 7\}$, with $\hat{x}$ in (444) and $y$ being the label assigned by MNIST to the image $I$ in (434). The label $y$ corresponds to the digit in the image $I$. Such an image produces the vector $\hat{x}$, when its HOG features are computed.