Hence, under the assumption that the empirical risk function $L_z$ in (3) is separable, it holds that for all $\gamma \in \mathcal{K}_{Q,z}$, $K_{Q,z}^{(2)}(-\frac{1}{\gamma}) > 0$. This completes the proof.

## APPENDIX O
PROOF OF LEMMA 19

Consider the partition of the set $\mathcal{M}$ formed by the sets $\mathcal{A}_0$, $\mathcal{A}_1$, and $\mathcal{A}_2$ in (308). From (96), for all $\lambda \in \mathcal{K}_{Q,z}$, with $\mathcal{K}_{Q,z}$ in (23), it holds that,

$$ K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) = \int_{\mathcal{A}_0} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) + \int_{\mathcal{A}_1} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (416) $$

$$ + \int_{\mathcal{A}_2} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (417) $$

$$ = \int_{\mathcal{A}_0} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) + \int_{\mathcal{A}_2} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (418) $$

$$ = \delta_{Q,z}^* P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) + \int_{\mathcal{A}_2} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (419) $$

$$ \begin{aligned} & \ge \delta_{Q,z}^* P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) + \delta_{Q,z}^* P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}_2) \quad (420) \\ & = \delta_{Q,z}^*, \quad (421) \end{aligned} $$

where the equality in (418) follows by noticing that $Q(\mathcal{A}_1) = 0$, which implies that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}_1) = 0$ (Lemma 3); the equality in (419) follows from noticing that $\mathcal{A}_0 = \mathcal{L}_{Q,z}^*$, with $\mathcal{L}_{Q,z}^*$ in (38); and the equality in (420) follows from (308c). This completes the proof.

## APPENDIX P
PROOF OF THEOREM 6

From (419) in the proof of Lemma 19, it holds that

$$ \lim_{\lambda \to 0^+} K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) = \lim_{\lambda \to 0^+} \delta_{Q,z}^* P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) + \lim_{\lambda \to 0^+} \int_{\mathcal{A}_2} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (422) $$

$$ = \lim_{\lambda \to 0^+} \delta_{Q,z}^* P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) + \lim_{\lambda \to 0^+} \int_{\mathcal{A}_2} L_z(\theta) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \quad (423) $$

$$ = \lim_{\lambda \to 0^+} \delta_{Q,z}^* P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) + \int_{\mathcal{A}_2} L_z(\theta) \lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \quad (424) $$

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

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

where, the equality in (424) follows from noticing two facts: (a) For all $\lambda \in \mathcal{K}_{Q,z}$, the Randon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ is positive and finite (Lemma 2); and (b)

For all $\theta \in \mathcal{A}_2$, it holds that $\lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 0$ (Lemma 6). Hence, the dominated convergence theorem [59, Theorem 1.6.9] holds. The inequality in (425) follows from Lemma 7. This completes the proof.

## APPENDIX Q
PROOF OF THEOREM 9

From Theorem 5, it follows that for all $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$ with $\lambda_1 > \lambda_2$,

$$ \int L_z(\alpha) \frac{dP_{\Theta|Z=z}^{(Q,\lambda_1)}}{dQ}(\alpha) dQ(\alpha) \ge \int L_z(\alpha) \frac{dP_{\Theta|Z=z}^{(Q,\lambda_2)}}{dQ}(\alpha) dQ(\alpha), $$

which implies the following inclusions:

$$ \mathcal{R}_1(\lambda_2) \subseteq \mathcal{R}_1(\lambda_1), \text{ and} \quad (427a) $$

$$ \mathcal{R}_2(\lambda_1) \subseteq \mathcal{R}_2(\lambda_2), \quad (427b) $$

with the sets $\mathcal{R}_1(\cdot)$ and $\mathcal{R}_2(\cdot)$ in (382). From (166), it holds that for all $i \in \{1, 2\}$,

$$ \mathcal{N}_{Q,z}(\lambda_i) = \mathcal{R}_2(\lambda_i)^c, \quad (428) $$

where the complement is with respect to $\mathcal{M}$. Thus, the inclusion in (427b) and the equality in (428) yields,

$$ \mathcal{N}_{Q,z}(\lambda_1) \supseteq \mathcal{N}_{Q,z}(\lambda_2). \quad (429) $$

The inclusion $\mathcal{M} \supseteq \mathcal{N}_{Q,z}(\lambda_1)$ follows from (166). Alternatively, the inclusion $\mathcal{N}_{Q,z}(\lambda_2) \supseteq \mathcal{N}_{Q,z}^*$, follows from Lemma 19 and from observing that for all $\nu \in \mathcal{N}_{Q,z}^*$,

$$ \mathcal{R}_z(P_{\Theta|Z=z}^{(Q,\lambda_2)}) \ge \delta_{Q,z}^* = L_z(\nu), \quad (430) $$

which implies that $\nu \in \mathcal{N}_{Q,z}(\lambda_2)$. This completes the proof of (170).

The proof of (171) is as follows. From the intermediate value theorem [70, Theorem 4.23] and the assumption that the empirical risk function $L_z$ in (3) is continuous on $\mathcal{M}$, it follows that for all $\lambda \in \mathcal{K}_{Q,z}$, there always exists a model $\theta \in \mathcal{M}$, such that

$$ L_z(\theta) = \int L_z(\alpha) dP_{\Theta|Z=z}^{(Q,\lambda)}(\alpha), \quad (431) $$

which implies that $\mathcal{R}_0(\lambda)$ is not empty, and as a consequence, $\mathcal{N}_{Q,z}(\lambda) = \mathcal{R}_0(\lambda) \cup \mathcal{R}_1(\lambda)$ is not empty. Hence, for all $\theta \in \mathcal{R}_0(\lambda_1)$ it holds that $\theta \notin \mathcal{N}_{Q,z}(\lambda_2)$. This proves that the elements of $\mathcal{R}_0(\lambda_1)$ are in $\mathcal{N}_{Q,z}(\lambda_1)$ but not in $\mathcal{N}_{Q,z}(\lambda_2)$. This, together with (429), verifies that

$$ \mathcal{N}_{Q,z}(\lambda_1) \supseteq \mathcal{N}_{Q,z}(\lambda_2). \quad (432) $$

The strict inclusion $\mathcal{M} \supseteq \mathcal{N}_{Q,z}(\lambda_1)$ is proved by contradiction. Assume that there exists a $\lambda \in \mathcal{K}_{Q,z}$ such that $\mathcal{M} = \mathcal{N}_{Q,z}(\lambda)$. Then, $\mathcal{R}_2(\lambda) = \emptyset$ and thus, $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_2(\lambda)) = 0$, which together with Lemma 26, implies that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_1(\lambda)) = 0$ and consequently,

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_0(\lambda)) = 1. \quad (433) $$

This contradicts the assumption that the function $L_z$ is separable (Definition 5). Hence, $\mathcal{M} \supseteq \mathcal{N}_{Q,z}(\lambda_1)$.
Hence, under the assumption that the empirical risk function $L_z$ in (3) is separable, it holds that for all $\gamma \in \mathcal{K}_{Q,z}$, $K_{Q,z}^{(2)}(-\frac{1}{\gamma}) > 0$. This completes the proof.

# APPENDIX O
PROOF OF LEMMA 19

Consider the partition of the set $\mathcal{M}$ formed by the sets $\mathcal{A}_0$, $\mathcal{A}_1$, and $\mathcal{A}_2$ in (308). From (96), for all $\lambda \in \mathcal{K}_{Q,z}$, with $\mathcal{K}_{Q,z}$ in (23), it holds that,

$$K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) = \int_{\mathcal{A}_0} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) + \int_{\mathcal{A}_1} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (416)$$

$$+ \int_{\mathcal{A}_2} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (417)$$

$$= \int_{\mathcal{A}_0} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) + \int_{\mathcal{A}_2} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (418)$$

$$= \delta_{Q,z}^{*} P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^{*}) + \int_{\mathcal{A}_2} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (419)$$

$$\begin{aligned} & \ge \delta_{Q,z}^{*} P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^{*}) + \delta_{Q,z}^{*} P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}_2) \quad (420) \\ & = \delta_{Q,z}^{*}, \quad (421) \end{aligned}$$

where the equality in (418) follows by noticing that $Q(\mathcal{A}_1) = 0$, which implies that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}_1) = 0$ (Lemma 3); the equality in (419) follows from noticing that $\mathcal{A}_0 = \mathcal{L}_{Q,z}^*$, with $\mathcal{L}_{Q,z}^*$ in (38); and the equality in (420) follows from (308c). This completes the proof.

# APPENDIX P
PROOF OF THEOREM 6

From (419) in the proof of Lemma 19, it holds that

$$\lim_{\lambda \to 0^+} K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) = \lim_{\lambda \to 0^+} \delta_{Q,z}^{*} P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^{*}) + \lim_{\lambda \to 0^+} \int_{\mathcal{A}_2} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (422)$$

$$= \lim_{\lambda \to 0^+} \delta_{Q,z}^{*} P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^{*}) + \lim_{\lambda \to 0^+} \int_{\mathcal{A}_2} L_z(\theta) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \quad (423)$$

$$= \lim_{\lambda \to 0^+} \delta_{Q,z}^{*} P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^{*}) + \int_{\mathcal{A}_2} L_z(\theta) \lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \quad (424)$$

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

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

where, the equality in (424) follows from noticing two facts: (a) For all $\lambda \in \mathcal{K}_{Q,z}$, the Randon-Nikodym derivative $\frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ is positive and finite (Lemma 2); and (b)

For all $\theta \in \mathcal{A}_2$, it holds that $\lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 0$ (Lemma 6). Hence, the dominated convergence theorem [59, Theorem 1.6.9] holds. The inequality in (425) follows from Lemma 7. This completes the proof.

# APPENDIX Q
PROOF OF THEOREM 9

From Theorem 5, it follows that for all $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$ with $\lambda_1 > \lambda_2$,

$$\int L_z(\alpha) \frac{dP_{\Theta|Z=z}^{(Q,\lambda_1)}}{dQ}(\alpha) dQ(\alpha) \ge \int L_z(\alpha) \frac{dP_{\Theta|Z=z}^{(Q,\lambda_2)}}{dQ}(\alpha) dQ(\alpha),$$

which implies the following inclusions:

$$\mathcal{R}_1(\lambda_2) \subseteq \mathcal{R}_1(\lambda_1), \text{ and} \quad (427a)$$

$$\mathcal{R}_2(\lambda_1) \subseteq \mathcal{R}_2(\lambda_2), \quad (427b)$$

with the sets $\mathcal{R}_1(\cdot)$ and $\mathcal{R}_2(\cdot)$ in (382). From (166), it holds that for all $i \in \{1, 2\}$,

$$\mathcal{N}_{Q,z}(\lambda_i) = \mathcal{R}_2(\lambda_i)^c, \quad (428)$$

where the complement is with respect to $\mathcal{M}$. Thus, the inclusion in (427b) and the equality in (428) yields,

$$\mathcal{N}_{Q,z}(\lambda_1) \supseteq \mathcal{N}_{Q,z}(\lambda_2). \quad (429)$$

The inclusion $\mathcal{M} \supseteq \mathcal{N}_{Q,z}(\lambda_1)$ follows from (166). Alternatively, the inclusion $\mathcal{N}_{Q,z}(\lambda_2) \supseteq \mathcal{N}_{Q,z}^*$, follows from Lemma 19 and from observing that for all $\nu \in \mathcal{N}_{Q,z}^*$,

$$\mathcal{R}_z(P_{\Theta|Z=z}^{(Q,\lambda_2)}) \ge \delta_{Q,z}^{*} = L_z(\nu), \quad (430)$$

which implies that $\nu \in \mathcal{N}_{Q,z}(\lambda_2)$. This completes the proof of (170).

The proof of (171) is as follows. From the intermediate value theorem [70, Theorem 4.23] and the assumption that the empirical risk function $L_z$ in (3) is continuous on $\mathcal{M}$, it follows that for all $\lambda \in \mathcal{K}_{Q,z}$, there always exists a model $\theta \in \mathcal{M}$, such that

$$L_z(\theta) = \int L_z(\alpha) dP_{\Theta|Z=z}^{(Q,\lambda)}(\alpha), \quad (431)$$

which implies that $\mathcal{R}_0(\lambda)$ is not empty, and as a consequence, $\mathcal{N}_{Q,z}(\lambda) = \mathcal{R}_0(\lambda) \cup \mathcal{R}_1(\lambda)$ is not empty. Hence, for all $\theta \in \mathcal{R}_0(\lambda_1)$ it holds that $\theta \notin \mathcal{N}_{Q,z}(\lambda_2)$. This proves that the elements of $\mathcal{R}_0(\lambda_1)$ are in $\mathcal{N}_{Q,z}(\lambda_1)$ but not in $\mathcal{N}_{Q,z}(\lambda_2)$. This, together with (429), verifies that

$$\mathcal{N}_{Q,z}(\lambda_1) \supseteq \mathcal{N}_{Q,z}(\lambda_2). \quad (432)$$

The strict inclusion $\mathcal{M} \supseteq \mathcal{N}_{Q,z}(\lambda_1)$ is proved by contradiction. Assume that there exists a $\lambda \in \mathcal{K}_{Q,z}$ such that $\mathcal{M} = \mathcal{N}_{Q,z}(\lambda)$. Then, $\mathcal{R}_2(\lambda) = \emptyset$ and thus, $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_2(\lambda)) = 0$, which together with Lemma 26, implies that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_1(\lambda)) = 0$ and consequently,

$$P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_0(\lambda)) = 1. \quad (433)$$

This contradicts the assumption that the function $L_z$ is separable (Definition 5). Hence, $\mathcal{M} \supseteq \mathcal{N}_{Q,z}(\lambda_1)$.
Finally, the strict inclusion $\mathcal{N}_{Q,z}(\lambda_2) \supset \mathcal{N}_{Q,z}^*$ is proved by contradiction. Assume that there exists a $\lambda \in \mathcal{K}_{Q,z}$ such that $\mathcal{N}_{Q,z}^* = \mathcal{N}_{Q,z}(\lambda)$. That is,

$$ \begin{aligned} & \{\theta \in \mathcal{M} : \mathrm{L}_z(\theta) \le \delta_{Q,z}^*\} \\ &= \mathcal{N}_{Q,z}^* \end{aligned} \quad (434) $$

$$ = \mathcal{N}_{Q,z}(\lambda) \quad (435) $$

$$ = \left\{ \theta \in \mathcal{M} : \mathrm{L}_z(\theta) \le K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \right\}. \quad (436) $$

Hence, three cases might arise:

(a) there exists a $\lambda \in \mathcal{K}_{Q,z}$, such that $\delta_{Q,z}^* < K_{Q,z}^{(1)}(-\frac{1}{\lambda})$ and it holds that

$$ \{\nu \in \mathcal{M} : \delta_{Q,z}^* < \mathrm{L}_z(\nu) \le K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right)\} = \emptyset; $$

(b) there exists a $\lambda \in \mathcal{K}_{Q,z}$, such that $\delta_{Q,z}^* > K_{Q,z}^{(1)}(-\frac{1}{\lambda})$ and it holds that

$$ \{\nu \in \mathcal{M} : K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) < \mathrm{L}_z(\nu) \le \delta_{Q,z}^*\} = \emptyset; $$

or (c) there exists a $\lambda \in \mathcal{K}_{Q,z}$, such that $\delta_{Q,z}^* = K_{Q,z}^{(1)}(-\frac{1}{\lambda})$.

The cases (a) and (b) are absurd. Hence, the proof is complete only by considering the case (c). In the case (c), it holds that,

$$ \mathcal{R}_1(\lambda) = \{\nu \in \mathcal{M} : \mathrm{L}_z(\nu) < \delta_{Q,z}^*\}, \quad (437) $$

and from the definition of $\delta_{Q,z}^*$ in (37), it holds that

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_1(\lambda)) = 0. \quad (438) $$

From Lemma 26 and (438), it follows that,

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_2(\lambda)) = 0. \quad (439) $$

Finally, by noticing that

$$ \begin{aligned} 1 &= P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_0(\lambda)) + P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_1(\lambda)) \\ &+ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_2(\lambda)) \end{aligned} \quad (440) $$

$$ = P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_0(\lambda)), \quad (441) $$

reveals a contradiction to the assumption that the function $\mathrm{L}_z$ is separable with respect to $P_{\Theta|Z=z}^{(Q,\lambda)}$ (and thus, separable with respect to $Q$ by Lemma 14). This completes the proof of (171).

# APPENDIX R

## PROOF OF THEOREM 10

The proof of (172) is based on the analysis of the derivative of $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A})$ with respect to $\lambda$, for some fixed set $\mathcal{A} \subseteq \mathcal{B}(\mathcal{M})$. More specifically, given a $\gamma \in \mathcal{K}_{Q,z}$, it holds that

$$ P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{A}) = \int_{\mathcal{A}} \frac{dP_{\Theta|Z=z}^{(Q,\gamma)}}{dQ}(\alpha) dQ(\alpha), \quad (442) $$

and from the fundamental theorem of calculus [70, Theorem 6.21], it follows that for all $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$ with $\lambda_1 > \lambda_2$,

$$ P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{A}) - P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{A}) $$

$$ = \int_{\lambda_2}^{\lambda_1} \frac{d}{d\gamma} P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{A}) d\gamma \quad (443) $$

$$ = \int_{\lambda_2}^{\lambda_1} \frac{d}{d\gamma} \int_{\mathcal{A}} \frac{dP_{\Theta|Z=z}^{(Q,\gamma)}}{dQ}(\alpha) dQ(\alpha) d\gamma \quad (444) $$

$$ = \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{A}} \frac{d}{d\gamma} \frac{dP_{\Theta|Z=z}^{(Q,\gamma)}}{dQ}(\alpha) dQ(\alpha) d\gamma, \quad (445) $$

where the equality in (444) follows from (442); and the equality in (445) holds from Lemma 2 and the dominated convergence theorem [59, Theorem 1.6.9].

For all $\theta \in \text{supp } \mathcal{Q}$, the following holds,

$$ \begin{aligned} & \frac{d}{d\lambda} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \\ &= \frac{d}{d\lambda} \left( \exp\left(-\frac{\mathrm{L}_z(\theta)}{\lambda}\right) \int \exp\left(-\frac{\mathrm{L}_z(\nu)}{\lambda}\right) dQ(\nu) \right) \end{aligned} \quad (446) $$

$$ \begin{aligned} &= \frac{\frac{1}{\lambda^2} \mathrm{L}_z(\theta) \exp\left(-\frac{\mathrm{L}_z(\theta)}{\lambda}\right)}{\int \exp\left(-\frac{\mathrm{L}_z(\nu)}{\lambda}\right) dQ(\nu)} \\ &= \frac{\frac{1}{\lambda^2} \exp\left(-\frac{\mathrm{L}_z(\theta)}{\lambda}\right) \int \mathrm{L}_z(\alpha) \exp\left(-\frac{\mathrm{L}_z(\alpha)}{\lambda}\right) dQ(\alpha)}{\left(\int \exp\left(-\frac{\mathrm{L}_z(\nu)}{\lambda}\right) dQ(\nu)\right)^2} \end{aligned} \quad (447) $$

$$ \begin{aligned} &= \frac{1}{\lambda^2} \mathrm{L}_z(\theta) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \\ &- \frac{1}{\lambda^2} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \int \mathrm{L}_z(\nu) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\nu) dQ(\nu) \end{aligned} \quad (448) $$

$$ = \frac{1}{\lambda^2} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \left( \mathrm{L}_z(\theta) - \int \mathrm{L}_z(\nu) dP_{\Theta|Z=z}^{(Q,\lambda)}(\nu) \right). \quad (449) $$

Plugging (449) into (445) yields,

$$ \begin{aligned} & P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{A}) - P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{A}) \\ &= \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{A}} \frac{1}{\gamma^2} \frac{dP_{\Theta|Z=z}^{(Q,\gamma)}}{dQ}(\alpha) \left( \mathrm{L}_z(\alpha) - \int \mathrm{L}_z(\nu) dP_{\Theta|Z=z}^{(Q,\gamma)}(\nu) \right) dQ(\alpha) d\gamma \end{aligned} \quad (450) $$

$$ = \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{A}} \frac{1}{\gamma^2} \left( \mathrm{L}_z(\alpha) - \int \mathrm{L}_z(\nu) dP_{\Theta|Z=z}^{(Q,\gamma)}(\nu) \right) dP_{\Theta|Z=z}^{(Q,\gamma)}(\alpha) d\gamma. \quad (451) $$

Note that for all $\alpha \in \mathcal{N}_{Q,z}(\lambda_2)$, it holds that for all $\gamma \in (\lambda_2, \lambda_1)$,

$$ \mathrm{L}_z(\alpha) - \int \mathrm{L}_z(\nu) dP_{\Theta|Z=z}^{(Q,\gamma)}(\nu) \le 0, \quad (452) $$
Finally, the strict inclusion $\mathcal{N}_{Q,z}(\lambda_2) \supset \mathcal{N}_{Q,z}^*$ is proved by contradiction. Assume that there exists a $\lambda \in \mathcal{K}_{Q,z}$ such that $\mathcal{N}_{Q,z}^* = \mathcal{N}_{Q,z}(\lambda)$. That is,

$$ \begin{aligned} & \{\boldsymbol{\theta} \in \mathcal{M} : \mathrm{L}_z(\boldsymbol{\theta}) \le \delta_{Q,z}^*\} \\ &= \mathcal{N}_{Q,z}^* \end{aligned} \quad (434) $$

$$ = \mathcal{N}_{Q,z}(\lambda) \quad (435) $$

$$ = \left\{ \boldsymbol{\theta} \in \mathcal{M} : \mathrm{L}_z(\boldsymbol{\theta}) \le K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \right\}. \quad (436) $$

Hence, three cases might arise:

(a) there exists a $\lambda \in \mathcal{K}_{Q,z}$, such that $\delta_{Q,z}^* < K_{Q,z}^{(1)}(-\frac{1}{\lambda})$ and it holds that

$$ \{\boldsymbol{\nu} \in \mathcal{M} : \delta_{Q,z}^* < \mathrm{L}_z(\boldsymbol{\nu}) \le K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right)\} = \emptyset; $$

(b) there exists a $\lambda \in \mathcal{K}_{Q,z}$, such that $\delta_{Q,z}^* > K_{Q,z}^{(1)}(-\frac{1}{\lambda})$ and it holds that

$$ \{\boldsymbol{\nu} \in \mathcal{M} : K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) < \mathrm{L}_z(\boldsymbol{\nu}) \le \delta_{Q,z}^*\} = \emptyset; $$

or (c) there exists a $\lambda \in \mathcal{K}_{Q,z}$, such that $\delta_{Q,z}^* = K_{Q,z}^{(1)}(-\frac{1}{\lambda})$.

The cases (a) and (b) are absurd. Hence, the proof is complete only by considering the case (c). In the case (c), it holds that,

$$ \mathcal{R}_1(\lambda) = \{\boldsymbol{\nu} \in \mathcal{M} : \mathrm{L}_z(\boldsymbol{\nu}) < \delta_{Q,z}^*\}, \quad (437) $$

and from the definition of $\delta_{Q,z}^*$ in (37), it holds that

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_1(\lambda)) = 0. \quad (438) $$

From Lemma 26 and (438), it follows that,

$$ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_2(\lambda)) = 0. \quad (439) $$

Finally, by noticing that

$$ \begin{aligned} 1 &= P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_0(\lambda)) + P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_1(\lambda)) \\ &+ P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_2(\lambda)) \end{aligned} \quad (440) $$

$$ = P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_0(\lambda)), \quad (441) $$

reveals a contradiction to the assumption that the function $\mathrm{L}_z$ is separable with respect to $P_{\Theta|Z=z}^{(Q,\lambda)}$ (and thus, separable with respect to $Q$ by Lemma 14). This completes the proof of (171).

# APPENDIX R

## PROOF OF THEOREM 10

The proof of (172) is based on the analysis of the derivative of $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A})$ with respect to $\lambda$, for some fixed set $\mathcal{A} \subseteq \mathcal{B}(\mathcal{M})$. More specifically, given a $\gamma \in \mathcal{K}_{Q,z}$, it holds that

$$ P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{A}) = \int_{\mathcal{A}} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\gamma)}}{\mathrm{d}Q}(\boldsymbol{\alpha}) \mathrm{d}Q(\boldsymbol{\alpha}), \quad (442) $$

and from the fundamental theorem of calculus [70, Theorem 6.21], it follows that for all $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$ with $\lambda_1 > \lambda_2$,

$$ \begin{aligned} & P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{A}) - P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{A}) \\ &= \int_{\lambda_2}^{\lambda_1} \frac{\mathrm{d}}{\mathrm{d}\gamma} P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{A}) \mathrm{d}\gamma \end{aligned} \quad (443) $$

$$ = \int_{\lambda_2}^{\lambda_1} \frac{\mathrm{d}}{\mathrm{d}\gamma} \int_{\mathcal{A}} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\gamma)}}{\mathrm{d}Q}(\boldsymbol{\alpha}) \mathrm{d}Q(\boldsymbol{\alpha}) \mathrm{d}\gamma \quad (444) $$

$$ = \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{A}} \frac{\mathrm{d}}{\mathrm{d}\gamma} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\gamma)}}{\mathrm{d}Q}(\boldsymbol{\alpha}) \mathrm{d}Q(\boldsymbol{\alpha}) \mathrm{d}\gamma, \quad (445) $$

where the equality in (444) follows from (442); and the equality in (445) holds from Lemma 2 and the dominated convergence theorem [59, Theorem 1.6.9].

For all $\boldsymbol{\theta} \in \mathrm{supp} \, \mathcal{Q}$, the following holds,

$$ \begin{aligned} & \frac{\mathrm{d}}{\mathrm{d}\lambda} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) \\ &= \frac{\mathrm{d}}{\mathrm{d}\lambda} \frac{\exp\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta})}{\lambda}\right)}{\int \exp\left(-\frac{\mathrm{L}_z(\boldsymbol{\nu})}{\lambda}\right) \mathrm{d}Q(\boldsymbol{\nu})} \end{aligned} \quad (446) $$

$$ \begin{aligned} & = \frac{\frac{1}{\lambda^2} \mathrm{L}_z(\boldsymbol{\theta}) \exp\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta})}{\lambda}\right)}{\int \exp\left(-\frac{\mathrm{L}_z(\boldsymbol{\nu})}{\lambda}\right) \mathrm{d}Q(\boldsymbol{\nu})} \\ & - \frac{\frac{1}{\lambda^2} \exp\left(-\frac{\mathrm{L}_z(\boldsymbol{\theta})}{\lambda}\right) \int \mathrm{L}_z(\boldsymbol{\alpha}) \exp\left(-\frac{\mathrm{L}_z(\boldsymbol{\alpha})}{\lambda}\right) \mathrm{d}Q(\boldsymbol{\alpha})}{\left(\int \exp\left(-\frac{\mathrm{L}_z(\boldsymbol{\nu})}{\lambda}\right) \mathrm{d}Q(\boldsymbol{\nu})\right)^2} \end{aligned} \quad (447) $$

$$ \begin{aligned} & = \frac{1}{\lambda^2} \mathrm{L}_z(\boldsymbol{\theta}) \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) \\ & - \frac{1}{\lambda^2} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) \int \mathrm{L}_z(\boldsymbol{\nu}) \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\nu}) \mathrm{d}Q(\boldsymbol{\nu}) \end{aligned} \quad (448) $$

$$ = \frac{1}{\lambda^2} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\boldsymbol{\theta}) \left(\mathrm{L}_z(\boldsymbol{\theta}) - \int \mathrm{L}_z(\boldsymbol{\nu}) \mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\nu})\right). \quad (449) $$

Plugging (449) into (445) yields,

$$ \begin{aligned} & P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{A}) - P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{A}) \\ &= \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{A}} \frac{1}{\gamma^2} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\gamma)}}{\mathrm{d}Q}(\boldsymbol{\alpha}) \\ & \qquad \left(\mathrm{L}_z(\boldsymbol{\alpha}) - \int \mathrm{L}_z(\boldsymbol{\nu}) \mathrm{d}P_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\nu})\right) \mathrm{d}Q(\boldsymbol{\alpha}) \mathrm{d}\gamma \end{aligned} \quad (450) $$

$$ = \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{A}} \frac{1}{\gamma^2} \left( \mathrm{L}_z(\boldsymbol{\alpha}) - \int \mathrm{L}_z(\boldsymbol{\nu}) \mathrm{d}P_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\nu}) \right) \mathrm{d}P_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) \mathrm{d}\gamma. \quad (451) $$

Note that for all $\boldsymbol{\alpha} \in \mathcal{N}_{Q,z}(\lambda_2)$, it holds that for all $\gamma \in (\lambda_2, \lambda_1)$,

$$ \mathrm{L}_z(\boldsymbol{\alpha}) - \int \mathrm{L}_z(\boldsymbol{\nu}) \mathrm{d}P_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\nu}) \le 0, \quad (452) $$
and thus,

$$
\int_{\mathcal{N}_{Q,z}(\lambda_2)\gamma^2} \frac{1}{\gamma^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - \int \mathbf{L}_z(\boldsymbol{\nu}) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\boldsymbol{\nu}) \right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) \le 0. \quad (453)
$$

The equalities in (451) and (453), with $\mathcal{A} = \mathcal{N}_{Q,z}(\lambda)$, imply that

$$
P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2)) - P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)) \le 0. \quad (454)
$$

The inequality $0 < P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2))$ in (172) is proved by contradiction. Assume that for some $\lambda \in \mathcal{K}_{Q,z}$ it holds that $0 = P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{N}_{Q,z}(\lambda_2))$. Then, $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_0(\lambda_2)) + P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_1(\lambda_2)) = 0$, which implies that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_2(\lambda_2)) = 1$, which is a contradiction. See for instance, Lemma 27. This completes the proof of (172).

The proof of strict inequality in (172) is divided into two parts.
The first part shows that if for all pairs $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$ with $\lambda_1 > \lambda_2$,

$$
P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2)) < P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)), \quad (455)
$$

then the function L_z is separable with respect to Q. The second part of the proof shows that if the function L_z is separable with respect to Q, then, for all pairs $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$ with $\lambda_1 > \lambda_2$, the inequality in (455) holds.

The first part is as follows. In the proof of Theorem 9 it is
shown (see (451)) that for all pairs $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$
with $\lambda_1 > \lambda_2$,

$$
\begin{align}
& P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2)) - P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)) \nonumber \\
& \quad = \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{N}_{Q,z}(\lambda_2)\gamma^2} \frac{1}{\gamma^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right) dP_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) d\gamma. \tag{456}
\end{align}
$$

Assume that for a given pair $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$, with $\lambda_1 > \lambda_2$, the inequality in (455) holds. Then, from (456),

$$
\begin{align}
&> \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{N}_{Q,z}(\lambda_2)\gamma^2} \frac{1}{\gamma^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) d\gamma \nonumber \\
&= \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{R}_1(\lambda_2)\gamma^2} \frac{1}{\gamma^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) d\gamma, \tag{457}
\end{align}
$$

where the equality in (457) follows from noticing
that $\mathcal{R}_0(\lambda_2)$ and $\mathcal{R}_1(\lambda_2)$ form a partition of $\mathcal{N}_{Q,z}(\lambda_2)$
with the sets $\mathcal{R}_0(\lambda_2)$, $\mathcal{R}_1(\lambda_2)$ and $\mathcal{N}_{Q,z}(\lambda_2)$ defined
in (382a), (382b), and (166), respectively.

The inequality in (457) implies that the set $\mathcal{R}_1(\lambda_2)$ is nonneg-
ligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$, for some $\gamma \in (\lambda_2, \lambda_1)$. Hence,
from Lemma 27, it follows that both sets $\mathcal{R}_1(\lambda_2)$ and $\mathcal{R}_2(\lambda_2)$
are nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$.

From the arguments above, it has been proved that given a
pair $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$ with $\lambda_1 > \lambda_2$, if

$$
P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2)) < P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)), \quad (458)
$$

then there always exists a positive $\gamma \in (\lambda_1, \lambda_2)$ such that
the sets $\mathcal{R}_1(\lambda_2)$ and $\mathcal{R}_2(\lambda_2)$ are not negligible with respect
to $P_{\Theta|Z=z}^{(Q,\gamma)}$. Moreover, such sets $\mathcal{R}_1(\lambda_2)$ and $\mathcal{R}_2(\lambda_2)$ satisfy
for all $(\boldsymbol{\nu}_1, \boldsymbol{\nu}_2) \in \mathcal{R}_2(\lambda) \times \mathcal{R}_1(\lambda)$,

$$
+\infty > \mathbf{L}_z(\boldsymbol{\nu}_1) > K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) > \mathbf{L}_z(\boldsymbol{\nu}_2), \quad (459)
$$

which together with Definition 14 verify that the function L_z is separable with respect to P_{\Theta|Z=z}^{(Q,\gamma)} (and thus, with respect to Q by Lemma 14). This ends the first part of the proof.

The second part of the proof is under the assumption that the empirical risk function L_z in (3) is separable with respect to Q (and thus, with respect to P_{\Theta|Z=z}^{(Q,\gamma)} by Lemma 14). That is, from Definition 14, for all $\gamma \in \mathcal{K}_{Q,z}$, there exist a positive real $c_\gamma > 0$ and two subsets $\mathcal{A}(\gamma)$ and $\mathcal{B}(\gamma)$ of $\mathcal{M}$ nonnegligible with respect to P_{\Theta|Z=z}^{(Q,\gamma)} in (25) that verify that for all $(\nu_1, \nu_2) \in \mathcal{A}(\gamma) \times \mathcal{B}(\gamma)$,

$$
\mathbf{L}_z(\boldsymbol{\nu}_1) > c_\gamma > \mathbf{L}_z(\boldsymbol{\nu}_2). \quad (460)
$$

In the proof of Theorem 9, cf. (451), it has been proved that given a pair $(\alpha_1, \alpha_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$, with $\alpha_1 > \gamma > \alpha_2$, it holds that for all subsets $\mathcal{A}$ of $\mathcal{M}$,

$$
\begin{align}
& P_{\Theta|Z=z}^{(Q,\alpha_1)}(\mathcal{A}) - P_{\Theta|Z=z}^{(Q,\alpha_2)}(\mathcal{A}) \nonumber \\
&= \int_{\alpha_2}^{\alpha_1} \int_{\mathcal{A}} \frac{1}{\lambda^2} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\alpha) \left( \mathbf{L}_z(\alpha) - K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) \right) dP(\alpha) d\lambda \nonumber \\
&= \int_{\alpha_2}^{\alpha_1} \int_{\mathcal{A}} \frac{1}{\lambda^2} \left( \mathbf{L}_z(\alpha) - K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) \right) dP_{\Theta|Z=z}^{(Q,\lambda)}(\alpha) d\lambda. \tag{461}
\end{align}
$$

Hence, two cases are studied. The first case considers
that

$$
c_{\gamma} < K_{Q,z}^{(1)} \left(-\frac{1}{\gamma}\right), \qquad (462)
$$

with $c_\gamma$ in (460). The second case considers that

$$
c_{\gamma} \geq K_{Q,z}^{(1)} \left(-\frac{1}{\gamma}\right). \qquad (463)
$$

In the first case, it follows from (166) that

$$
\mathcal{B}(\gamma) \subset \mathcal{N}_{Q,z}(\gamma), \quad (464)
$$

which implies that

$$
P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{N}_{Q,z}(\gamma)) \ge P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{B}(\gamma)) \quad (465)
$$

$$
> 0, \tag{466}
$$

where, the inequality in (466) follows from the fact that $\mathcal{B}(\gamma)$ is nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$. This implies that the set $\mathcal{N}_{Q,z}(\gamma)$ is not negligible with respect $P_{\Theta|Z=z}^{(Q,\gamma)}$. Moreover, from (166) and (464), it follows that for all $\alpha \in \mathcal{N}_{Q,z}(\gamma)$ and for all $\lambda \in (\gamma, \alpha_1)$,

$$
\mathbf{L}_z(\boldsymbol{\alpha}) - \int \mathbf{L}_z(\boldsymbol{\nu}) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\nu}) < \mathbf{L}_z(\boldsymbol{\alpha}) - c_{\gamma} \quad (467)
$$

$$
<0, \tag{468}
$$
and thus,

$$
\int_{\mathcal{N}_{Q,z}(\lambda_2)\gamma^2} \frac{1}{\gamma^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - \int \mathbf{L}_z(\boldsymbol{\nu}) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\boldsymbol{\nu}) \right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) \le 0. \quad (453)
$$

The equalities in (451) and (453), with $\mathcal{A} = \mathcal{N}_{Q,z}(\lambda)$, imply that

$$
P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2)) - P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)) \le 0. \quad (454)
$$

The inequality $0 < P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2))$ in (172) is proved by contradiction. Assume that for some $\lambda \in \mathcal{K}_{Q,z}$ it holds that $0 = P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{N}_{Q,z}(\lambda_2))$. Then, $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_0(\lambda_2)) + P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_1(\lambda_2)) = 0$, which implies that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{R}_2(\lambda_2)) = 1$, which is a contradiction. See for instance, Lemma 27. This completes the proof of (172).

The proof of strict inequality in (172) is divided into two parts.
The first part shows that if for all pairs $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$ with $\lambda_1 > \lambda_2$,

$$
P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2)) < P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)), \quad (455)
$$

then the function $L_z$ is separable with respect to $Q$. The second part of the proof shows that if the function $L_z$ is separable with respect to $Q$, then, for all pairs $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$ with $\lambda_1 > \lambda_2$, the inequality in (455) holds.

The first part is as follows. In the proof of Theorem 9 it is
shown (see (451)) that for all pairs $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$
with $\lambda_1 > \lambda_2$,

$$
\begin{align}
& P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2)) - P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)) \nonumber \\
& \quad = \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{N}_{Q,z}(\lambda_2)\gamma^2} \frac{1}{\gamma^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right) dP_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) \mathrm{d}\gamma. \tag{456}
\end{align}
$$

Assume that for a given pair $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$, with $\lambda_1 > \lambda_2$, the inequality in (455) holds. Then, from (456),

$$
\begin{align}
&> \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{N}_{Q,z}(\lambda_2)} \frac{1}{\gamma^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - K_{Q,z}^{(1)} \left( -\frac{1}{\gamma} \right) \right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) \mathrm{d}\gamma \nonumber \\
&= \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{R}_1(\lambda_2)} \frac{1}{\gamma^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - K_{Q,z}^{(1)} \left( -\frac{1}{\gamma} \right) \right) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) \mathrm{d}\gamma, \tag{457}
\end{align}
$$

where the equality in (457) follows from noticing
that $\mathcal{R}_0(\lambda_2)$ and $\mathcal{R}_1(\lambda_2)$ form a partition of $\mathcal{N}_{Q,z}(\lambda_2)$
with the sets $\mathcal{R}_0(\lambda_2)$, $\mathcal{R}_1(\lambda_2)$ and $\mathcal{N}_{Q,z}(\lambda_2)$ defined
in (382a), (382b), and (166), respectively.

The inequality in (457) implies that the set $\mathcal{R}_1(\lambda_2)$ is nonneg-
ligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$, for some $\gamma \in (\lambda_2, \lambda_1)$. Hence,
from Lemma 27, it follows that both sets $\mathcal{R}_1(\lambda_2)$ and $\mathcal{R}_2(\lambda_2)$
are nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$.

From the arguments above, it has been proved that given a
pair $(\lambda_1, \lambda_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$ with $\lambda_1 > \lambda_2$, if

$$
P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2)) < P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)), \quad (458)
$$

then there always exists a positive $\gamma \in (\lambda_1, \lambda_2)$ such that
the sets $\mathcal{R}_1(\lambda_2)$ and $\mathcal{R}_2(\lambda_2)$ are not negligible with respect
to $P_{\Theta|Z=z}^{(Q,\gamma)}$. Moreover, such sets $\mathcal{R}_1(\lambda_2)$ and $\mathcal{R}_2(\lambda_2)$ satisfy
for all $(\boldsymbol{\nu}_1, \boldsymbol{\nu}_2) \in \mathcal{R}_2(\lambda) \times \mathcal{R}_1(\lambda)$,

$$
+\infty > \mathbf{L}_z(\boldsymbol{\nu}_1) > K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) > \mathbf{L}_z(\boldsymbol{\nu}_2), \quad (459)
$$

which together with Definition 14 verify that the function $L_z$ is separable with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$ (and thus, with respect to $Q$ by Lemma 14). This ends the first part of the proof.

The second part of the proof is under the assumption that the empirical risk function $L_z$ in (3) is separable with respect to $Q$ (and thus, with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$ by Lemma 14). That is, from Definition 14, for all $\gamma \in \mathcal{K}_{Q,z}$, there exist a positive real $c_\gamma > 0$ and two subsets $\mathcal{A}(\gamma)$ and $\mathcal{B}(\gamma)$ of $\mathcal{M}$ nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$ in (25) that verify that for all $(\nu_1, \nu_2) \in \mathcal{A}(\gamma) \times \mathcal{B}(\gamma)$,

$$
L_z(\nu_1) > c_\gamma > L_z(\nu_2). \quad (460)
$$

In the proof of Theorem 9, cf. (451), it has been proved that given a pair $(\alpha_1, \alpha_2) \in \mathcal{K}_{Q,z} \times \mathcal{K}_{Q,z}$, with $\alpha_1 > \gamma > \alpha_2$, it holds that for all subsets $\mathcal{A}$ of $\mathcal{M}$,

$$
\begin{align}
& P_{\Theta|Z=z}^{(Q,\alpha_1)}(\mathcal{A}) - P_{\Theta|Z=z}^{(Q,\alpha_2)}(\mathcal{A}) \nonumber \\
&= \int_{\alpha_2}^{\alpha_1} \int_{\mathcal{A}} \frac{1}{\lambda^2} \frac{\mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\alpha) \left( \mathbf{L}_z(\alpha) - K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) \right) \mathrm{d}P(\alpha) \mathrm{d}\lambda \nonumber \\
&= \int_{\alpha_2}^{\alpha_1} \int_{\mathcal{A}} \frac{1}{\lambda^2} \left( \mathbf{L}_z(\alpha) - K_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) \right) \mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}(\alpha) \mathrm{d}\lambda. \tag{461}
\end{align}
$$

Hence, two cases are studied. The first case considers
that

$$
c_{\gamma} < K_{Q,z}^{(1)} \left(-\frac{1}{\gamma}\right), \qquad (462)
$$

with $c_\gamma$ in (460). The second case considers that

$$
c_{\gamma} \geq K_{Q,z}^{(1)} \left(-\frac{1}{\gamma}\right). \qquad (463)
$$

In the first case, it follows from (166) that

$$
\mathcal{B}(\gamma) \subset \mathcal{N}_{Q,z}(\gamma), \quad (464)
$$

which implies that

$$
P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{N}_{Q,z}(\gamma)) \ge P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{B}(\gamma)) \quad (465)
$$

$$
> 0, \tag{466}
$$

where, the inequality in (466) follows from the fact that $\mathcal{B}(\gamma)$ is nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$. This implies that the set $\mathcal{N}_{Q,z}(\gamma)$ is not negligible with respect $P_{\Theta|Z=z}^{(Q,\gamma)}$. Moreover, from (166) and (464), it follows that for all $\alpha \in \mathcal{N}_{Q,z}(\gamma)$ and for all $\lambda \in (\gamma, \alpha_1)$,

$$
L_z(\alpha) - \int L_z(\nu) dP_{\Theta|Z=z}^{(Q,\lambda)}(\nu) < L_z(\alpha) - c_{\gamma} \quad (467)
$$

$$
<0, \qquad (468)
$$
where the inequality in (467) follows from (462); and the inequality in (468) follows from (460). Thus,

$$ \int_{\gamma}^{\alpha_1} \int_{\mathcal{N}_{Q,z}(\gamma)} \frac{1}{\lambda^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \right) d P_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\alpha}) d\lambda < 0, $$

which implies, from (461), that

$$ P_{\Theta|Z=z}^{(Q,\alpha_1)}(\mathcal{N}_{Q,z}(\gamma)) - P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{N}_{Q,z}(\gamma)) < 0. \quad (469) $$

Assume now that $c_\gamma \ge K_{Q,z}^{(1)}(-\frac{1}{\gamma})$. Hence, the following holds

$$ A(\gamma) \subseteq \mathcal{R}_2(\gamma), \quad (470) $$

which implies that

$$ P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{R}_2(\gamma)) \ge P_{\Theta|Z=z}^{(Q,\gamma)}(A(\gamma)) \quad (471) $$

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

where the inequality in (472) follows from the fact that $A(\gamma)$ is nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$. This implies that the set $\mathcal{R}_2(\gamma)$ is not negligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$. From Lemma 26, it follows that both $\mathcal{R}_1(\gamma)$ and $\mathcal{R}_2(\gamma)$ are nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$. Using this result, the following holds,

$$ P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{N}_{Q,z}(\gamma)) \ge P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{R}_1(\gamma)) \quad (473) $$

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

which proves the set $\mathcal{N}_{Q,z}(\gamma)$ is nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$.

From (166) and Theorem 5, it follows that for all $\alpha \in \mathcal{N}_{Q,z}(\gamma)$ and for all $\lambda \in (\gamma, \alpha_1)$,

$$ 0 \ge \mathbf{L}_z(\boldsymbol{\alpha}) - \int \mathbf{L}_z(\boldsymbol{\nu}) d P_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\nu}) \quad (475) $$

$$ > \mathbf{L}_z(\boldsymbol{\alpha}) - \int \mathbf{L}_z(\boldsymbol{\nu}) d P_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\nu}). \quad (476) $$

Thus,

$$ \int_{\gamma}^{\alpha_1} \int_{\mathcal{N}_{Q,z}(\gamma)} \frac{1}{\lambda^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \right) d P_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\alpha}) d\lambda < 0, $$

which implies, from (461), that

$$ P_{\Theta|Z=z}^{(Q,\alpha_1)}(\mathcal{N}_{Q,z}(\gamma)) - P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{N}_{Q,z}(\gamma)) < 0. \quad (477) $$

This completes the proof.

## APPENDIX S
PROOF OF LEMMA 25

The proof is based on the following two observations. First, note that $(\mathcal{N}_{Q,z}(\lambda_2))^c = \mathcal{R}_2(\lambda_2)$, with the set $\mathcal{R}_2(\cdot)$ defined in (382c). Second, note that

$$ \mathcal{N}_{Q,z}(\lambda_1) = \mathcal{N}_{Q,z}(\lambda_2) \cup (\mathcal{N}_{Q,z}(\lambda_1) \cap \mathcal{R}_2(\lambda_2)), \quad (478) $$

and the fact that the sets $\mathcal{N}_{Q,z}(\lambda_2)$ and $(\mathcal{N}_{Q,z}(\lambda_1) \cap \mathcal{R}_2(\lambda_2))$ are disjoint. Hence, for all $i \in \{1, 2\}$,

$$ P_{\Theta|Z=z}^{(\lambda_i)}(\mathcal{N}_{Q,z}(\lambda_1)) = P_{\Theta|Z=z}^{(\lambda_i)}(\mathcal{N}_{Q,z}(\lambda_2) \cup (\mathcal{N}_{Q,z}(\lambda_1) \cap \mathcal{R}_2(\lambda_2))) \quad (479) $$

$$ = P_{\Theta|Z=z}^{(\lambda_i)}(\mathcal{N}_{Q,z}(\lambda_2)) + P_{\Theta|Z=z}^{(\lambda_i)}(\mathcal{N}_{Q,z}(\lambda_1) \cap \mathcal{R}_2(\lambda_2)) \quad (480) $$

$$ = P_{\Theta|Z=z}^{(\lambda_i)}(\mathcal{N}_{Q,z}(\lambda_2)), \quad (481) $$

where the equality in (480) follows from Lemma 3 and the equality in (173).

Finally, under the assumption that the empirical function $\mathbf{L}_z$ in (3) is separable, it holds from Theorem 10 that

$$ P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2)) < P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)). \quad (482) $$

Plugging (481) into (482), with $i=1$, yields,

$$ P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_1)) < P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)), \quad (483) $$

and this completes the proof.

## APPENDIX T
PROOF OF THEOREM 15

Consider the following lemma.

**Lemma 28:** Given two probability measures $P_1$ and $P_2$ over $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, with $P_2$ absolutely continuous with respect to $P_1$, the following holds for all $z \in (\mathcal{X} \times \mathcal{Y})^n$,

$$ \mathbf{R}_z(P_2) - \mathbf{R}_z(P_1) \quad (484) \\ \le \inf_{t<0} \left( \frac{D(P_2\|P_1) + \log(\int \exp(t(\mathbf{L}_z(\boldsymbol{\theta}) - \mathbf{R}_z(P_1)))dP_1(\boldsymbol{\theta}))}{t} \right), $$

where the function $\mathbf{R}_z$ and the functional $\mathbf{R}_z$ are defined in (3) and in (18), respectively.

*Proof:* From [57, Corollary 4.15, Page 100], it follows that the probability measures $P_1$ and $P_2$ in $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ satisfy the following equality:

$$ D(P_2 \| P_1) = \sup_f \int f(\boldsymbol{\theta}) dP_2(\boldsymbol{\theta}) - \log \int \exp(f(\boldsymbol{\theta})) dP_1(\boldsymbol{\theta}), \quad (485) $$

where the supremum is over the space of all measurable functions $f$ with respect to $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ and $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$, such that $\int \exp(f(\boldsymbol{\theta})) dP_1(\boldsymbol{\theta}) < \infty$. Hence, for all $z \in (\mathcal{X} \times \mathcal{Y})^n$
where the inequality in (467) follows from (462); and the inequality in (468) follows from (460). Thus,

$$ \int_{\gamma}^{\alpha_1} \int_{\mathcal{N}_{Q,z}(\gamma)} \frac{1}{\lambda^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \right) d P_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\alpha}) d\lambda < 0, $$

which implies, from (461), that

$$ P_{\Theta|Z=z}^{(Q,\alpha_1)}(\mathcal{N}_{Q,z}(\gamma)) - P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{N}_{Q,z}(\gamma)) < 0. \quad (469) $$

Assume now that $c_\gamma \ge K_{Q,z}^{(1)}(-\frac{1}{\gamma})$. Hence, the following holds

$$ A(\gamma) \subseteq \mathcal{R}_2(\gamma), \quad (470) $$

which implies that

$$ P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{R}_2(\gamma)) \ge P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{A}(\gamma)) \quad (471) $$

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

where the inequality in (472) follows from the fact that $\mathcal{A}(\gamma)$ is nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$. This implies that the set $\mathcal{R}_2(\gamma)$ is not negligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$. From Lemma 26, it follows that both $\mathcal{R}_1(\gamma)$ and $\mathcal{R}_2(\gamma)$ are nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$. Using this result, the following holds,

$$ P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{N}_{Q,z}(\gamma)) \ge P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{R}_1(\gamma)) \quad (473) $$

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

which proves the set $\mathcal{N}_{Q,z}(\gamma)$ is nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$.

From (166) and Theorem 5, it follows that for all $\alpha \in \mathcal{N}_{Q,z}(\gamma)$ and for all $\lambda \in (\gamma, \alpha_1)$,

$$ 0 \ge \mathbf{L}_z(\boldsymbol{\alpha}) - \int \mathbf{L}_z(\boldsymbol{\nu}) d P_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\nu}) \quad (475) $$

$$ > \mathbf{L}_z(\boldsymbol{\alpha}) - \int \mathbf{L}_z(\boldsymbol{\nu}) d P_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\nu}). \quad (476) $$

Thus,

$$ \int_{\gamma}^{\alpha_1} \int_{\mathcal{N}_{Q,z}(\gamma)} \frac{1}{\lambda^2} \left( \mathbf{L}_z(\boldsymbol{\alpha}) - K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \right) d P_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\alpha}) d\lambda < 0, $$

which implies, from (461), that

$$ P_{\Theta|Z=z}^{(Q,\alpha_1)}(\mathcal{N}_{Q,z}(\gamma)) - P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{N}_{Q,z}(\gamma)) < 0. \quad (477) $$

This completes the proof.

## APPENDIX S
### PROOF OF LEMMA 25

The proof is based on the following two observations. First, note that $(\mathcal{N}_{Q,z}(\lambda_2))^c = \mathcal{R}_2(\lambda_2)$, with the set $\mathcal{R}_2(\cdot)$ defined in (382c). Second, note that

$$ \mathcal{N}_{Q,z}(\lambda_1) = \mathcal{N}_{Q,z}(\lambda_2) \cup (\mathcal{N}_{Q,z}(\lambda_1) \cap \mathcal{R}_2(\lambda_2)), \quad (478) $$

and the fact that the sets $\mathcal{N}_{Q,z}(\lambda_2)$ and $(\mathcal{N}_{Q,z}(\lambda_1) \cap \mathcal{R}_2(\lambda_2))$ are disjoint. Hence, for all $i \in \{1, 2\}$,

$$ P_{\Theta|Z=z}^{(\lambda_i)}(\mathcal{N}_{Q,z}(\lambda_1)) = P_{\Theta|Z=z}^{(\lambda_i)}(\mathcal{N}_{Q,z}(\lambda_2) \cup (\mathcal{N}_{Q,z}(\lambda_1) \cap \mathcal{R}_2(\lambda_2))) \quad (479) $$

$$ = P_{\Theta|Z=z}^{(\lambda_i)}(\mathcal{N}_{Q,z}(\lambda_2)) + P_{\Theta|Z=z}^{(\lambda_i)}(\mathcal{N}_{Q,z}(\lambda_1) \cap \mathcal{R}_2(\lambda_2)) \quad (480) $$

$$ = P_{\Theta|Z=z}^{(\lambda_i)}(\mathcal{N}_{Q,z}(\lambda_2)), \quad (481) $$

where the equality in (480) follows from Lemma 3 and the equality in (173).

Finally, under the assumption that the empirical function $\mathbf{L}_z$ in (3) is separable, it holds from Theorem 10 that

$$ P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_2)) < P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)). \quad (482) $$

Plugging (481) into (482), with $i=1$, yields,

$$ P_{\Theta|Z=z}^{(Q,\lambda_1)}(\mathcal{N}_{Q,z}(\lambda_1)) < P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)), \quad (483) $$

and this completes the proof.

## APPENDIX T
### PROOF OF THEOREM 15

Consider the following lemma.

**Lemma 28:** Given two probability measures $P_1$ and $P_2$ over $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$, with $P_2$ absolutely continuous with respect to $P_1$, the following holds for all $z \in (\mathcal{X} \times \mathcal{Y})^n$,

$$ \mathbf{R}_z(P_2) - \mathbf{R}_z(P_1) \quad (484) \\ \le \inf_{t<0} \left( \frac{D(P_2\|P_1) + \log(\int \exp(t(\mathbf{L}_z(\boldsymbol{\theta}) - \mathbf{R}_z(P_1)))dP_1(\boldsymbol{\theta}))}{t} \right), $$

where the function $\mathbf{R}_z$ and the functional $\mathbf{R}_z$ are defined in (3) and in (18), respectively.

*Proof:* From [57, Corollary 4.15, Page 100], it follows that the probability measures $P_1$ and $P_2$ in $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ satisfy the following equality:

$$ D(P_2 \| P_1) = \sup_f \int f(\boldsymbol{\theta}) dP_2(\boldsymbol{\theta}) - \log \int \exp(f(\boldsymbol{\theta})) dP_1(\boldsymbol{\theta}), \quad (485) $$

where the supremum is over the space of all measurable functions $f$ with respect to $(\mathcal{M}, \mathcal{B}(\mathcal{M}))$ and $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$, such that $\int \exp(f(\boldsymbol{\theta})) dP_1(\boldsymbol{\theta}) < \infty$. Hence, for all $z \in (\mathcal{X} \times \mathcal{Y})^n$
and for all $t \in (-\infty, 0)$, it follows that the empirical risk function $L_z$ in (3) satisfies that

$$
\begin{align*}
& D(P_2 \| P_1) \\
\ge & \int t \mathbf{L}_z(\boldsymbol{\theta}) \, dP_2(\boldsymbol{\theta}) - \log \int \exp(t \mathbf{L}_z(\boldsymbol{\theta})) \, dP_1(\boldsymbol{\theta}) \\
\ge & \int t \mathbf{L}_z(\boldsymbol{\theta}) \, dP_2(\boldsymbol{\theta}) \\
& - \log \int \exp(t \mathbf{L}_z(\boldsymbol{\theta}) + t \mathbf{R}_z(P_1) - t \mathbf{R}_z(P_1)) \, dP_1(\boldsymbol{\theta}) \\
= & \int t \mathbf{L}_z(\boldsymbol{\theta}) \, dP_2(\boldsymbol{\theta}) - t \mathbf{R}_z(P_1) \\
& - \log \int \exp(t \mathbf{L}_z(\boldsymbol{\theta}) - t \mathbf{R}_z(P_1)) \, dP_1(\boldsymbol{\theta}) \\
= & t \mathbf{R}_z(P_2) - t \mathbf{R}_z(P_1) - \log \int \exp(t \mathbf{L}_z(\boldsymbol{\theta}) - t \mathbf{R}_z(P_1)) \, dP_1(\boldsymbol{\theta}),
\end{align*}
$$

which leads to

$$
\le \frac{R_z(P_2) - R_z(P_1)}{D(P_2 \| P_1) + \log \int \exp(t(\mathbf{L}_z(\boldsymbol{\theta}) - \mathbf{R}_z(P_1))) dP_1(\boldsymbol{\theta})} \quad (486)
$$

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

$$
\begin{align*}
& R_z(P_2) - R_z(P_1) \\
\le & \inf_{t \in (-\infty, 0)} \frac{D(P_2 \| P_1) + \log \int \exp(t(\mathbf{L}_z(\boldsymbol{\theta}) - \mathbf{R}_z(P_1))) dP_1(\boldsymbol{\theta})}{t},
\end{align*}
$$

which completes the proof.

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

From Lemma 28, it holds that the probability measure $P_{\Theta|Z=z}^{(Q;\lambda)}$
in (25), satisfies for all $P \in \triangle_Q (\mathcal{M}, \mathcal{B}(\mathcal{M}))$,

$$
\begin{align}
R_z(P) - R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) &\le \inf_{t \in (-\infty,0)} \left( \frac{D(P \| P_{\Theta|Z=z}^{(Q,\lambda)})}{t} \right. \nonumber \\
&\qquad \left. + \frac{\log \left( \int \exp \left( t \left( \mathbf{L}_z(\boldsymbol{\theta}) - K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \right) \right) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right)}{t} \right), \tag{487}
\end{align}
$$

where the function $K_{Q,z}^{(1)}$ is defined in (96) and satisfies (104).
Moreover, for all $t \in (-\infty, 0)$,

$$
\begin{align}
& \log \left( \int \exp \left( t \left( \mathbf{L}_z(\boldsymbol{\theta}) - K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \right) \right) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) \nonumber \\
& = \log \left( \int \exp \left( t \mathbf{L}_z(\boldsymbol{\theta}) \right) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) - t K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \tag{488} \\
& = J_{z,Q,\lambda}(t) - t K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \tag{489} \\
& \le \frac{1}{2} t^2 \beta_{Q,z}^2, \tag{490}
\end{align}
$$

where the equality in (489) follows from (136); the inequality
in (490) follows from Theorem 7; and the constant $\beta_{Q,z}$ is
defined in (159).

Plugging (490) into (487) yields for all $t \in (-\infty, 0)$,

$$
\begin{align}
& R_z(P) - R_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) \nonumber \\
\le & \inf_{t \in (-\infty, 0)} \frac{D\left(P \| P_{\Theta|Z=z}^{(Q,\lambda)}\right) + \frac{1}{2} t^2 \beta_{Q,z}^2}{t}. \tag{491}
\end{align}
$$

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

$$
c \triangleq \mathbf{R}_z(P) - \mathbf{R}_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right). \quad (492)
$$

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

$$
ct - \frac{1}{2} t^2 \beta_{Q,z}^2 \le D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}) . \quad (493)
$$

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

$$
\phi(\alpha) = \frac{1}{2} \alpha^2 \beta_{Q,z}^2, \quad (494)
$$

and note that $\phi$ is a positive and strictly convex function
with $\phi(0) = 0$. Let the Legendre-Fenchel transform of $\phi$ be
the function $\phi^* : \mathbb{R} \to \mathbb{R}$, and thus for all $x \in \mathbb{R}$,

$$
\phi^*(x) = \max_{t \in (-\infty, 0)} xt - \phi(t). \quad (495)
$$

In particular, note that

$$
\phi^*(c) \le D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}). \quad (496)
$$

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

$$
x t - \frac{1}{2} t^2 \beta_{Q,z}^2 \le \phi^*(x) = x \alpha^*(x) - \phi(\alpha^*(x)), \quad (497)
$$

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

$$
\frac{d}{d\alpha} (x\alpha - \phi(\alpha)) = x - \alpha\beta_{Q,z}^2 = 0. \quad (498)
$$

That is,

$$
\alpha^*(x) = \frac{x}{\beta_{Q,z}^2}. \tag{499}
$$

Plugging (499) into (497) yields,

$$
\phi^*(x) = \frac{x^2}{2\beta_{Q,z}^2}. \qquad (500)
$$

Hence, from (496) and (497), given $c$ in (492) for all $t \in (-\infty, 0)$,

$$
ct - \frac{1}{2} t^2 \beta_{Q,z}^2 \le \phi^*(c) \le D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}) , \quad (501)
$$

and thus,

$$
\frac{c^2}{2\beta_{Q,z}^2} \le D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}). \quad (502)
$$

This implies that

$$
c \le \sqrt{2\beta_{Q,z}^2 D(P \| P_{\Theta|Z=z}^{(Q,\lambda)})} \quad (503)
$$

and

$$
c \ge -\sqrt{2\beta_{Q,z}^2 D(P \| P_{\Theta|Z=z}^{(Q,\lambda)})}, \quad (504)
$$

which leads to

$$
\left| \int \mathbf{L}_z(\boldsymbol{\theta}) \mathrm{d}P(\boldsymbol{\theta}) - \int \mathbf{L}_z(\boldsymbol{\theta}) \mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right| \\
\le \sqrt{2\beta_{Q,z}^2 D\left(P \| P_{\Theta|Z=z}^{(Q,\lambda)}\right)}, \quad (505)
$$

and completes the proof.
and for all $t \in (-\infty, 0)$, it follows that the empirical risk function $L_z$ in (3) satisfies that

$$
\begin{align*}
& D(P_2 \| P_1) \\
\ge & \int t \mathbf{L}_z(\boldsymbol{\theta}) \, dP_2(\boldsymbol{\theta}) - \log \int \exp(t \mathbf{L}_z(\boldsymbol{\theta})) \, dP_1(\boldsymbol{\theta}) \\
\ge & \int t \mathbf{L}_z(\boldsymbol{\theta}) \, dP_2(\boldsymbol{\theta}) \\
& - \log \int \exp(t \mathbf{L}_z(\boldsymbol{\theta}) + t \mathbf{R}_z(P_1) - t \mathbf{R}_z(P_1)) \, dP_1(\boldsymbol{\theta}) \\
= & \int t \mathbf{L}_z(\boldsymbol{\theta}) \, dP_2(\boldsymbol{\theta}) - t \mathbf{R}_z(P_1) \\
& - \log \int \exp(t \mathbf{L}_z(\boldsymbol{\theta}) - t \mathbf{R}_z(P_1)) \, dP_1(\boldsymbol{\theta}) \\
= & t \mathbf{R}_z(P_2) - t \mathbf{R}_z(P_1) - \log \int \exp(t \mathbf{L}_z(\boldsymbol{\theta}) - t \mathbf{R}_z(P_1)) \, dP_1(\boldsymbol{\theta}),
\end{align*}
$$

which leads to

$$
\le \frac{R_z(P_2) - R_z(P_1)}{D(P_2 \| P_1) + \log \int \exp(t(\mathbf{L}_z(\boldsymbol{\theta}) - \mathbf{R}_z(P_1))) dP_1(\boldsymbol{\theta})} \quad (486)
$$

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

$$
\begin{align*}
& R_z(P_2) - R_z(P_1) \\
\le & \inf_{t \in (-\infty, 0)} \frac{D(P_2 \| P_1) + \log \int \exp(t(\mathbf{L}_z(\boldsymbol{\theta}) - \mathbf{R}_z(P_1))) dP_1(\boldsymbol{\theta})}{t},
\end{align*}
$$

which completes the proof.

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

From Lemma 28, it holds that the probability measure $P_{\Theta|Z=z}^{(Q;\lambda)}$
in (25), satisfies for all $P \in \triangle_Q (\mathcal{M}, \mathcal{B}(\mathcal{M}))$,

$$
\begin{align}
R_z(P) - R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) &\le \inf_{t \in (-\infty,0)} \left( \frac{D(P \| P_{\Theta|Z=z}^{(Q,\lambda)})}{t} \right. \nonumber \\
&\qquad \left. + \frac{\log \left( \int \exp \left( t \left( \mathbf{L}_z(\boldsymbol{\theta}) - K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \right) \right) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right)}{t} \right), \tag{487}
\end{align}
$$

where the function $K_{Q,z}^{(1)}$ is defined in (96) and satisfies (104).
Moreover, for all $t \in (-\infty, 0)$,

$$
\begin{align}
& \log \left( \int \exp \left( t \left( \mathbf{L}_z(\boldsymbol{\theta}) - K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \right) \right) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) \nonumber \\
& = \log \left( \int \exp \left( t \mathbf{L}_z(\boldsymbol{\theta}) \right) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right) - t K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \tag{488} \\
& = J_{z,Q,\lambda}(t) - t K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right) \tag{489} \\
& \le \frac{1}{2} t^2 \beta_{Q,z}^2, \tag{490}
\end{align}
$$

where the equality in (489) follows from (136); the inequality
in (490) follows from Theorem 7; and the constant $\beta_{Q,z}$ is
defined in (159).

Plugging (490) into (487) yields for all $t \in (-\infty, 0)$,

$$
\begin{align}
& R_z(P) - R_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right) \nonumber \\
\le & \inf_{t \in (-\infty, 0)} \frac{D\left(P \| P_{\Theta|Z=z}^{(Q,\lambda)}\right) + \frac{1}{2} t^2 \beta_{Q,z}^2}{t}. \tag{491}
\end{align}
$$

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

$$
c \triangleq \mathbf{R}_z(P) - \mathbf{R}_z\left(P_{\Theta|Z=z}^{(Q,\lambda)}\right). \quad (492)
$$

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

$$
ct - \frac{1}{2} t^2 \beta_{Q,z}^2 \le D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}) . \quad (493)
$$

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

$$
\phi(\alpha) = \frac{1}{2} \alpha^2 \beta_{Q,z}^2, \quad (494)
$$

and note that $\phi$ is a positive and strictly convex function
with $\phi(0) = 0$. Let the Legendre-Fenchel transform of $\phi$ be
the function $\phi^* : \mathbb{R} \to \mathbb{R}$, and thus for all $x \in \mathbb{R}$,

$$
\phi^*(x) = \max_{t \in (-\infty, 0)} xt - \phi(t). \quad (495)
$$

In particular, note that

$$
\phi^*(c) \le D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}). \quad (496)
$$

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

$$
x t - \frac{1}{2} t^2 \beta_{Q,z}^2 \le \phi^*(x) = x \alpha^*(x) - \phi(\alpha^*(x)), \quad (497)
$$

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

$$
\frac{d}{d\alpha} (x\alpha - \phi(\alpha)) = x - \alpha\beta_{Q,z}^2 = 0. \quad (498)
$$

That is,

$$
\alpha^*(x) = \frac{x}{\beta_{Q,z}^2}. \tag{499}
$$

Plugging (499) into (497) yields,

$$
\phi^*(x) = \frac{x^2}{2\beta_{Q,z}^2}. \quad (500)
$$

Hence, from (496) and (497), given $c$ in (492) for all $t \in (-\infty, 0)$,

$$
ct - \frac{1}{2} t^2 \beta_{Q,z}^2 \le \phi^*(c) \le D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}) , \quad (501)
$$

and thus,

$$
\frac{c^2}{2\beta_{Q,z}^2} \le D(P \| P_{\Theta|Z=z}^{(Q,\lambda)}). \quad (502)
$$

This implies that

$$
c \le \sqrt{2\beta_{Q,z}^2 D(P \| P_{\Theta|Z=z}^{(Q,\lambda)})} \quad (503)
$$

and

$$
c \ge -\sqrt{2\beta_{Q,z}^2 D(P \| P_{\Theta|Z=z}^{(Q,\lambda)})}, \quad (504)
$$

which leads to

$$
\left| \int \mathbf{L}_z(\boldsymbol{\theta}) dP(\boldsymbol{\theta}) - \int \mathbf{L}_z(\boldsymbol{\theta}) dP_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \right| \\
\le \sqrt{2\beta_{Q,z}^2 D(P \| P_{\Theta|Z=z}^{(Q,\lambda)})}, \quad (505)
$$

and completes the proof.
APPENDIX U
PROOF OF THEOREM 17

Under the condition that $\lambda \in K_{Q,PZ}$, from Theorem 14 and Definition 8, it follows that the generalization error $G_{Q,\lambda}(PZ)$ in (205) satisfies

$$G_{Q,\lambda}(PZ) = \lambda \int \left( D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \|Q) + D(P_{\Theta}^{(Q,\lambda)} \|P_{\Theta|Z=\nu}^{(Q,\lambda)}) - D(P_{\Theta}^{(Q,\lambda)} \|Q) \right) dP_Z(\nu), \quad (506)$$

$$= \lambda \left( \int D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \| P_{\Theta}^{(Q,\lambda)}) dP_Z(\nu) + \int D(P_{\Theta}^{(Q,\lambda)} \| P_{\Theta|Z=\nu}^{(Q,\lambda)}) dP_Z(\nu) \right), \quad (507)$$

where the equality in (507) follows from the fact that

$$\int (D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \| Q) - D(P_{\Theta}^{(Q,\lambda)} \| Q)) dP_Z(\nu) = \int D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \| Q) dP_Z(\nu) - D(P_{\Theta}^{(Q,\lambda)} \| Q) \quad (508)$$

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

$$= \int \left( \int \log \left( \frac{dP_{\Theta|Z=\nu}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta|Z=\nu}^{(Q,\lambda)}(\theta) \right) dP_Z(\nu) - \int \log \left( \frac{dP_{\Theta}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (510)$$

$$= \int \left( \int \log \left( \frac{dP_{\Theta|Z=\nu}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta|Z=\nu}^{(Q,\lambda)}(\theta) \right) dP_Z(\nu) - \int \left( \int \log \left( \frac{dP_{\Theta}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta|Z=\nu}^{(Q,\lambda)}(\theta) \right) dP_Z(\nu) \quad (511)$$

$$= \int \left( \int \left( \log \left( \frac{dP_{\Theta|Z=\nu}^{(Q,\lambda)}}{dQ}(\theta) \right) + \log \left( \frac{dQ}{dP_{\Theta}^{(Q,\lambda)}(\theta)} \right) \right) dP_{\Theta|Z=\nu}^{(Q,\lambda)}(\theta) \right) dP_Z(\nu) \quad (512)$$

$$= \int \left( \int \log \left( \frac{dP_{\Theta|Z=\nu}^{(Q,\lambda)}}{dP_{\Theta}^{(Q,\lambda)}(\theta)} \right) dP_{\Theta|Z=\nu}^{(Q,\lambda)}(\theta) \right) dP_Z(\nu) \quad (513)$$

$$= \int D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \| P_{\Theta}^{(Q,\lambda)}) dP_Z(\nu). \quad (514)$$

The equality in (511) follows from (203); and the equality in (512) follows from the fact that the measures $Q$ and $P_{\Theta|Z=\nu}^{(Q,\lambda)}$, with $\nu \in \text{supp } P_Z$, are mutually absolutely continuous (Lemma 3). This completes the proof.

REFERENCES

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

[2] ——, “Empirical risk minimization with generalized relative entropy regularization,” INRIA, Centre Inria d’Université Côte d’Azur, Sophia Antipolis, France, Tech. Rep. RR-9454, Feb. 2022.

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

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

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

[6] H. P. Young, *Strategic Learning and its Limits*, 1st ed. Oxford, UK: Oxford University Press, 2004.

[7] C. P. Robert, *The Bayesian Choice: From Decision-theoretic Foundations to Computational Implementation*, 1st ed. New York, NY, USA: Springer, 2007.

[8] G. Aminian, L. Toni, and M. R. Rodrigues, “Information-theoretic bounds on the moments of the generalization error of learning algorithms,” in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Melbourne, Australia, Jul. 2021, pp. 682–687.

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

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

[11] 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.

[12] X. Zou, S. M. Perlaza, I. Esnaola, and E. Altman, “The worst-case data-generating probability measure,” INRIA, Centre Inria d’Université Côte d’Azur, Sophia Antipolis, France, Tech. Rep. RR-9515, Aug. 2023.

[13] Y. Bu, G. Aminian, L. Toni, G. W. Wornell, and M. Rodrigues, “Characterizing and understanding the generalization error of transfer learning with Gibbs algorithm,” in *Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS)*, Virtual Conference, Mar. 2022, pp. 8673–8699.

[14] H. He, G. Aminian, Y. Bu, M. Rodrigues, and V. Y. Tan, “How does pseudo-labeling affect the generalization error of the semi-supervised Gibbs algorithm?” in *Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS)*, Valencia, Spain, Apr. 2023, pp. 8494–8520.

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

[16] F. Hellström, G. Durisi, B. Guedj, and M. Raginsky, “Generalization bounds: Perspectives from information theory and PAC-Bayes,” arXiv preprint arXiv:2309.04381, Sep. 2023.

[17] 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.

[18] 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.

[19] 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, 2023.
APPENDIX U
PROOF OF THEOREM 17

Under the condition that $\lambda \in K_{Q,PZ}$, from Theorem 14 and Definition 8, it follows that the generalization error $G_{Q,\lambda}(PZ)$ in (205) satisfies

$$G_{Q,\lambda}(PZ) = \lambda \int \left( D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \|Q) + D(P_{\Theta}^{(Q,\lambda)} \|P_{\Theta|Z=\nu}^{(Q,\lambda)}) - D(P_{\Theta}^{(Q,\lambda)} \|Q) \right) dP_Z(\nu), \quad (506)$$

$$= \lambda \left( \int D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \| P_{\Theta}^{(Q,\lambda)}) dP_Z(\nu) + \int D(P_{\Theta}^{(Q,\lambda)} \| P_{\Theta|Z=\nu}^{(Q,\lambda)}) dP_Z(\nu) \right), \quad (507)$$

where the equality in (507) follows from the fact that

$$\int \left( D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \| Q) - D(P_{\Theta}^{(Q,\lambda)} \| Q) \right) dP_Z(\nu) = \int D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \| Q) dP_Z(\nu) - D(P_{\Theta}^{(Q,\lambda)} \| Q) \quad (508)$$

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

$$= \int \left( \int \log \left( \frac{dP_{\Theta|Z=\nu}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta|Z=\nu}^{(Q,\lambda)}(\theta) \right) dP_Z(\nu) - \int \log \left( \frac{dP_{\Theta}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta}^{(Q,\lambda)}(\theta) \quad (510)$$

$$= \int \left( \int \log \left( \frac{dP_{\Theta|Z=\nu}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta|Z=\nu}^{(Q,\lambda)}(\theta) \right) dP_Z(\nu) - \int \left( \int \log \left( \frac{dP_{\Theta}^{(Q,\lambda)}}{dQ}(\theta) \right) dP_{\Theta|Z=\nu}^{(Q,\lambda)}(\theta) \right) dP_Z(\nu) \quad (511)$$

$$= \int \left( \int \left( \log \left( \frac{dP_{\Theta|Z=\nu}^{(Q,\lambda)}}{dQ}(\theta) \right) + \log \left( \frac{dQ}{dP_{\Theta}^{(Q,\lambda)}(\theta)} \right) \right) dP_{\Theta|Z=\nu}^{(Q,\lambda)}(\theta) \right) dP_Z(\nu) \quad (512)$$

$$= \int \left( \int \log \left( \frac{dP_{\Theta|Z=\nu}^{(Q,\lambda)}}{dP_{\Theta}^{(Q,\lambda)}(\theta)} \right) dP_{\Theta|Z=\nu}^{(Q,\lambda)}(\theta) \right) dP_Z(\nu) \quad (513)$$

$$= \int D(P_{\Theta|Z=\nu}^{(Q,\lambda)} \| P_{\Theta}^{(Q,\lambda)}) dP_Z(\nu). \quad (514)$$

The equality in (511) follows from (203); and the equality in (512) follows from the fact that the measures $Q$ and $P_{\Theta|Z=\nu}^{(Q,\lambda)}$, with $\nu \in \text{supp } P_Z$, are mutually absolutely continuous (Lemma 3). This completes the proof.

REFERENCES

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

[2] ——, “Empirical risk minimization with generalized relative entropy regularization,” INRIA, Centre Inria d’Université Côte d’Azur, Sophia Antipolis, France, Tech. Rep. RR-9454, Feb. 2022.

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

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

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

[6] H. P. Young, *Strategic Learning and its Limits*, 1st ed. Oxford, UK: Oxford University Press, 2004.

[7] C. P. Robert, *The Bayesian Choice: From Decision-theoretic Foundations to Computational Implementation*, 1st ed. New York, NY, USA: Springer, 2007.

[8] G. Aminian, L. Toni, and M. R. Rodrigues, “Information-theoretic bounds on the moments of the generalization error of learning algorithms,” in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Melbourne, Australia, Jul. 2021, pp. 682–687.

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

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

[11] 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.

[12] X. Zou, S. M. Perlaza, I. Esnaola, and E. Altman, “The worst-case data-generating probability measure,” INRIA, Centre Inria d’Université Côte d’Azur, Sophia Antipolis, France, Tech. Rep. RR-9515, Aug. 2023.

[13] Y. Bu, G. Aminian, L. Toni, G. W. Wornell, and M. Rodrigues, “Characterizing and understanding the generalization error of transfer learning with Gibbs algorithm,” in *Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS)*, Virtual Conference, Mar. 2022, pp. 8673–8699.

[14] H. He, G. Aminian, Y. Bu, M. Rodrigues, and V. Y. Tan, “How does pseudo-labeling affect the generalization error of the semi-supervised Gibbs algorithm?” in *Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS)*, Valencia, Spain, Apr. 2023, pp. 8494–8520.

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

[16] F. Hellström, G. Durisi, B. Guedj, and M. Raginsky, “Generalization bounds: Perspectives from information theory and PAC-Bayes,” arXiv preprint arXiv:2309.04381, Sep. 2023.

[17] 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.

[18] 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.

[19] 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, 2023.
[20] 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, Jul. 2021, pp. 207–218.

[21] F. Daunas, I. Esnaola, S. M. Perlaza, and H. V. Poor, "Empirical risk minimization with f-divergence regularization in statistical learning," *INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France*, Tech. Rep. RR-9521, Oct. 2023.

[22] C. P. Robert, G. Casella, and G. Casella, *Monte Carlo statistical methods*, 2nd ed. New York, NY, USA: Springer, 2004.

[23] T. Zhang, "Information-theoretic upper and lower bounds for statistical estimation," *IEEE Transactions on Information Theory*, vol. 52, no. 4, pp. 1307–1321, Apr. 2006.

[24] S. Mazuelas, Y. Shen, and A. Pérez, "Generalized maximum entropy for supervised classification," *IEEE Transactions on Information Theory*, vol. 68, no. 4, pp. 2530–2550, 2022.

[25] J. N. Kapur, *Maximum Entropy Models in Science and Engineering*, 1st ed. New York, NY, USA: Wiley, 1989.

[26] V. De Bortoli and A. Desolneux, "On quantitative Laplace-type convergence results for some exponential probability measures, with two applications," *arXiv preprint arXiv:2110.12922*, 2021.

[27] K. B. Athreya and C.-R. Hwang, "Gibbs measures asymptotics," *Sankhyä: The Indian Journal of Statistics, Series A*, vol. 72, no. 1, pp. 191–207, 2010.

[28] C.-R. Hwang, "Laplace's method revisited: Weak convergence of probability measures," *The Annals of Probability*, vol. 8, no. 6, pp. 1177–1182, 1980.

[29] M. Hasenpflug, D. Rudolf, and B. Sprungk, "Wasserstein convergence rates of increasingly concentrating probability measures," *arXiv preprint arXiv:2207.08551*, 2022.

[30] 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.

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

[32] A. R. Asadi and E. Abbe, "Chaining meets chain rule: Multilevel entropic regularization and training of neural networks." *J. Mach. Learn. Res.*, vol. 21, pp. 139–1 Jun. 2020.

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

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

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

[36] 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.

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

[38] T. Jaakkola, M. Meila, and T. Jebara, "Maximum entropy discrimination," *Neural Information Processing Systems*, vol. 12, pp. 470–476, Dec. 1999.

[39] J. Zhu and E. P. Xing, "Maximum entropy discrimination Markov networks," *Journal of Machine Learning Research*, vol. 10, no. 11, pp. 2531–2569, Nov. 2009.

[40] Y. Le Cun, S. Chopra, R. Hadsell, M. Ranzato, and F. Huang, "A tutorial on energy-based learning," in *Predicting structured data*, 1st ed., G. BakIr, T. Hofmann, B. Schölkopf, A. J. Smola, B. Taskar, and S. Vishwanathan, Eds. New York, NY, USA: The MIT Press, 2007, ch. 10, pp. 191–241.

[41] L. P. Barnes, A. Dytso, and H. V. Poor, "Improved information-theoretic generalization bounds for distributed, federated, and iterative learning," *Entropy*, vol. 24, no. 9, 2022.

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

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

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

[45] 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.

[46] I. Issa, A. R. Esposito, and M. Gastpar, "Strengthened information-theoretic bounds on the generalization error," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Paris, France, Jul. 2019, pp. 582–586.

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

[48] A. Asadi, E. Abbe, and S. Verdú, "Chaining mutual information and tightening generalization bounds," *Advances in Neural Information Processing Systems*, pp. 7245–7254, Dec. 2018.

[49] 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.

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

[51] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite, "Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms," *Advances in Neural Information Processing Systems*, pp. 9925–9935, Dec. 2018.

[52] B. Rodríguez Gálvez, G. Bassi, R. Thobaben, and M. Skoglund, "Tighter expected generalization error bounds via Wasserstein distance," *Advances in Neural Information Processing Systems*, vol. 34, pp. 19109–19121, Dec. 2021.

[53] 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.

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

[55] 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.

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

[57] S. Boucheron, G. Lugosi, and P. Massart, *Concentration Inequalities: A Non-asymptotic Theory of Independence*, 1st ed. Oxford, UK: Oxford University Press, 2013.
[20] 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, Jul. 2021, pp. 207–218.

[21] F. Daunas, I. Esnaola, S. M. Perlaza, and H. V. Poor, "Empirical risk minimization with f-divergence regularization in statistical learning," *INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France*, Tech. Rep. RR-9521, Oct. 2023.

[22] C. P. Robert, G. Casella, and G. Casella, *Monte Carlo statistical methods*, 2nd ed. New York, NY, USA: Springer, 2004.

[23] T. Zhang, "Information-theoretic upper and lower bounds for statistical estimation," *IEEE Transactions on Information Theory*, vol. 52, no. 4, pp. 1307–1321, Apr. 2006.

[24] S. Mazuelas, Y. Shen, and A. Pérez, "Generalized maximum entropy for supervised classification," *IEEE Transactions on Information Theory*, vol. 68, no. 4, pp. 2530–2550, 2022.

[25] J. N. Kapur, *Maximum Entropy Models in Science and Engineering*, 1st ed. New York, NY, USA: Wiley, 1989.

[26] V. De Bortoli and A. Desolneux, "On quantitative Laplace-type convergence results for some exponential probability measures, with two applications," *arXiv preprint arXiv:2110.12922*, 2021.

[27] K. B. Athreya and C.-R. Hwang, "Gibbs measures asymptotics," *Sankhyä: The Indian Journal of Statistics, Series A*, vol. 72, no. 1, pp. 191–207, 2010.

[28] C.-R. Hwang, "Laplace's method revisited: Weak convergence of probability measures," *The Annals of Probability*, vol. 8, no. 6, pp. 1177–1182, 1980.

[29] M. Hasenpflug, D. Rudolf, and B. Sprungk, "Wasserstein convergence rates of increasingly concentrating probability measures," *arXiv preprint arXiv:2207.08551*, 2022.

[30] 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.

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

[32] A. R. Asadi and E. Abbe, "Chaining meets chain rule: Multilevel entropic regularization and training of neural networks." *J. Mach. Learn. Res.*, vol. 21, pp. 139–1 Jun. 2020.

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

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

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

[36] 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.

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

[38] T. Jaakkola, M. Meila, and T. Jebara, "Maximum entropy discrimination," *Neural Information Processing Systems*, vol. 12, pp. 470–476, Dec. 1999.

[39] J. Zhu and E. P. Xing, "Maximum entropy discrimination Markov networks," *Journal of Machine Learning Research*, vol. 10, no. 11, pp. 2531–2569, Nov. 2009.

[40] Y. Le Cun, S. Chopra, R. Hadsell, M. Ranzato, and F. Huang, "A tutorial on energy-based learning," in *Predicting structured data*, 1st ed., G. BakIr, T. Hofmann, B. Schölkopf, A. J. Smola, B. Taskar, and S. Vishwanathan, Eds. New York, NY, USA: The MIT Press, 2007, ch. 10, pp. 191–241.

[41] L. P. Barnes, A. Dytso, and H. V. Poor, "Improved information-theoretic generalization bounds for distributed, federated, and iterative learning," *Entropy*, vol. 24, no. 9, 2022.

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

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

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

[45] 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.

[46] I. Issa, A. R. Esposito, and M. Gastpar, "Strengthened information-theoretic bounds on the generalization error," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Paris, France, Jul. 2019, pp. 582–586.

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

[48] A. Asadi, E. Abbe, and S. Verdú, "Chaining mutual information and tightening generalization bounds," *Advances in Neural Information Processing Systems*, pp. 7245–7254, Dec. 2018.

[49] 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.

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

[51] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite, "Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms," *Advances in Neural Information Processing Systems*, pp. 9925–9935, Dec. 2018.

[52] B. Rodríguez Gálvez, G. Bassi, R. Thobaben, and M. Skoglund, "Tighter expected generalization error bounds via Wasserstein distance," *Advances in Neural Information Processing Systems*, vol. 34, pp. 19109–19121, Dec. 2021.

[53] 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.

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

[55] 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.

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

[57] S. Boucheron, G. Lugosi, and P. Massart, *Concentration Inequalities: A Non-asymptotic Theory of Independence*, 1st ed. Oxford, UK: Oxford University Press, 2013.
[58] T. M. Cover and J. A. Thomas, *Elements of Information Theory*, 2nd ed. Hoboken, NJ: Wiley-Interscience, 2006.

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

[60] 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.

[61] H.-O. Georgii, *Gibbs measures and phase transitions*, 2nd ed. New York, NY, USA: De Gruyter, 2011.

[62] A. Dembo and O. Zeitouni, *Large Deviations Techniques and Applications*, 2nd ed. New York, NY, USA: Springer-Verlag, 2009.

[63] E. T. Jaynes, "Information theory and statistical mechanics I," *Physical Review Journals*, vol. 106, no. 4, pp. 620-630, May 1957.

[64] ——, "Information theory and statistical mechanics II," *Physical Review Journals*, vol. 108, no. 2, pp. 171-190, Oct. 1957.

[65] 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.

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

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

[68] B. Guedj, "A primer on PAC-Bayesian learning," in *Proceedings of the International Conference on Machine Learning (ICML)*, Long Beach, CA, USA, May 2019, pp. 2931-2940.

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

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

[71] W. F. Trench, *Introduction to Real Analysis*, 1st ed. Hoboken, NJ, USA: Prentice Hall Pearson Education, 2003.

[72] S. M. Perlaza, I. Esnaola, G. Bisson, and H. V. Poor, "Sensitivity of the Gibbs algorithm to data aggregation in supervised machine learning," INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France, Tech. Rep. RR-9474, Jun. 2022.

[73] D. G. Luenberger, *Optimization by Vector Space Methods*, 1st ed. New York, NY, USA: Wiley, 1997.

[74] W. Feller, *An Introduction to Probability Theory and Its Applications II*, 2nd ed. New York, NY, USA: Jhon Wiley & Sons, 1971.
[58] T. M. Cover and J. A. Thomas, *Elements of Information Theory*, 2nd ed. Hoboken, NJ: Wiley-Interscience, 2006.

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

[60] 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.

[61] H.-O. Georgii, *Gibbs measures and phase transitions*, 2nd ed. New York, NY, USA: De Gruyter, 2011.

[62] A. Dembo and O. Zeitouni, *Large Deviations Techniques and Applications*, 2nd ed. New York, NY, USA: Springer-Verlag, 2009.

[63] E. T. Jaynes, "Information theory and statistical mechanics I," *Physical Review Journals*, vol. 106, no. 4, pp. 620-630, May 1957.

[64] ——, "Information theory and statistical mechanics II," *Physical Review Journals*, vol. 108, no. 2, pp. 171-190, Oct. 1957.

[65] 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.

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

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

[68] B. Guedj, "A primer on PAC-Bayesian learning," in *Proceedings of the International Conference on Machine Learning (ICML)*, Long Beach, CA, USA, May 2019, pp. 2931-2940.

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

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

[71] W. F. Trench, *Introduction to Real Analysis*, 1st ed. Hoboken, NJ, USA: Prentice Hall Pearson Education, 2003.

[72] S. M. Perlaza, I. Esnaola, G. Bisson, and H. V. Poor, "Sensitivity of the Gibbs algorithm to data aggregation in supervised machine learning," INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France, Tech. Rep. RR-9474, Jun. 2022.

[73] D. G. Luenberger, *Optimization by Vector Space Methods*, 1st ed. New York, NY, USA: Wiley, 1997.

[74] W. Feller, *An Introduction to Probability Theory and Its Applications II*, 2nd ed. New York, NY, USA: Jhon Wiley & Sons, 1971.