respect to $P_{\Theta|Z=z}^{(Q,\alpha)}$ and moreover, it holds that for all $(\nu_1, \nu_2) \in \mathcal{R}_1(\alpha) \times \mathcal{R}_2(\alpha)$,

$$ +\infty > \mathbf{L}_z(\nu_1) > K_{Q,z}^{(1)}\left(-\frac{1}{\alpha}\right) > \mathbf{L}_z(\nu_2), \quad (402) $$

where $\mathbf{L}_z(\nu_1) < +\infty$ follows from the fact that $P_{\Theta|Z=z}^{(Q,\lambda)}(\{\theta \in \mathcal{M} : \mathbf{L}_z(\theta) = +\infty\}) = 0$ (Lemma 3.2). This proves that under the assumption that for all $\alpha \in \mathcal{K}_{Q,z}$, $K_{Q,z}^{(2)}(-\frac{1}{\alpha}) > 0$, the function $\mathbf{L}_z$ in (3) is separable with respect to $P_{\Theta|Z=z}^{(Q,\alpha)}$. From Lemma 5.1, it holds that the function $\mathbf{L}_z$ is separable with respect to $\mathcal{Q}$. This completes the first part of the proof.

The second part of the proof is simpler. Assume that the empirical risk function $\mathbf{L}_z$ in (3) is separable with respect to $P_{\Theta|Z=z}^{(Q,\alpha)}$. That is, 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}$ that are nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$ in (25) and verify that for all $(\nu_1, \nu_2) \in \mathcal{A}(\gamma) \times \mathcal{B}(\gamma)$,

$$ +\infty > \mathbf{L}_z(\nu_1) > c_\gamma > \mathbf{L}_z(\nu_2). \quad (403) $$

From Lemma 5.4, it holds that

$$ K_{Q,z}^{(2)}\left(-\frac{1}{\gamma}\right) = \int \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) \quad (404) $$

$$ = \int_{\mathcal{A}(\gamma)} \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) \quad (405) $$

$$ + \int_{\mathcal{B}(\gamma)} \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) \quad (406) $$

$$ + \int_{\mathcal{M} \setminus (\mathcal{A}(\gamma) \cup \mathcal{B}(\gamma))} \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) \quad (407) $$

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

where the inequality (408) follows from the following facts. First, if $c_\gamma < K_{Q,z}^{(1)}(-\frac{1}{\gamma})$, with $c_\gamma$ in (403), then for all $\nu \in \mathcal{B}(\gamma)$, it holds that $K_{Q,z}^{(1)}(-\frac{1}{\gamma}) > c_\gamma > \mathbf{L}_z(\nu)$, and thus,

$$ \left( \mathbf{L}_z(\nu) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 > \left( c_\gamma - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2, \quad (409) $$

which implies,

$$ \int_{\mathcal{B}(\gamma)} \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) > \left( c_\gamma - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{B}(\gamma)) \quad (410) $$

$$ > 0. \quad (411) $$
respect to $P_{\Theta|Z=z}^{(Q,\alpha)}$ and moreover, it holds that for all $(\nu_1, \nu_2) \in \mathcal{R}_1(\alpha) \times \mathcal{R}_2(\alpha)$,

$$ +\infty > \mathbf{L}_z(\nu_1) > K_{Q,z}^{(1)}\left(-\frac{1}{\alpha}\right) > \mathbf{L}_z(\nu_2), \quad (402) $$

where $\mathbf{L}_z(\nu_1) < +\infty$ follows from the fact that $P_{\Theta|Z=z}^{(Q,\lambda)}(\{\theta \in \mathcal{M} : \mathbf{L}_z(\theta) = +\infty\}) = 0$ (Lemma 3.2). This proves that under the assumption that for all $\alpha \in \mathcal{K}_{Q,z}$, $K_{Q,z}^{(2)}(-\frac{1}{\alpha}) > 0$, the function $\mathbf{L}_z$ in (3) is separable with respect to $P_{\Theta|Z=z}^{(Q,\alpha)}$. From Lemma 5.1, it holds that the function $\mathbf{L}_z$ is separable with respect to $\mathcal{Q}$. This completes the first part of the proof.

The second part of the proof is simpler. Assume that the empirical risk function $\mathbf{L}_z$ in (3) is separable with respect to $P_{\Theta|Z=z}^{(Q,\alpha)}$. That is, 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}$ that are nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$ in (25) and verify that for all $(\nu_1, \nu_2) \in \mathcal{A}(\gamma) \times \mathcal{B}(\gamma)$,

$$ +\infty > \mathbf{L}_z(\nu_1) > c_\gamma > \mathbf{L}_z(\nu_2). \quad (403) $$

From Lemma 5.4, it holds that

$$ K_{Q,z}^{(2)}\left(-\frac{1}{\gamma}\right) = \int \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) \quad (404) $$

$$ = \int_{\mathcal{A}(\gamma)} \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) \quad (405) $$

$$ + \int_{\mathcal{B}(\gamma)} \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) \quad (406) $$

$$ + \int_{\mathcal{M} \setminus (\mathcal{A}(\gamma) \cup \mathcal{B}(\gamma))} \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) \quad (407) $$

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

where the inequality (408) follows from the following facts. First, if $c_\gamma < K_{Q,z}^{(1)}(-\frac{1}{\gamma})$, with $c_\gamma$ in (403), then for all $\nu \in \mathcal{B}(\gamma)$, it holds that $K_{Q,z}^{(1)}(-\frac{1}{\gamma}) > c_\gamma > \mathbf{L}_z(\nu)$, and thus,

$$ \left( \mathbf{L}_z(\nu) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 > \left( c_\gamma - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2, \quad (409) $$

which implies,

$$ \int_{\mathcal{B}(\gamma)} \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) > \left( c_\gamma - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{B}(\gamma))(410) \\ > 0. \quad (411) $$
Second, if $c_γ \ge K_{Q,z}^{(1)}(-\frac{1}{γ})$ then for all $ν \in A(γ)$, it holds that $L_z(ν) > c_γ \ge K_{Q,z}^{(1)}(-\frac{1}{γ})$, and thus,

$$ (L_z(ν) - K_{Q,z}^{(1)}(-\frac{1}{γ}))^2 > (c_γ - K_{Q,z}^{(1)}(-\frac{1}{γ}))^2, \quad (412) $$

which implies,

$$ \int_{A(γ)} \left( L_z(θ) - K_{Q,z}^{(1)}\left(-\frac{1}{γ}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,γ)}(θ) > \begin{aligned}[t] & \left(c_γ - K_{Q,z}^{(1)}\left(-\frac{1}{γ}\right)\right)^2 P_{\Theta|Z=z}^{(Q,γ)}(A(γ)) \\ & > 0. \end{aligned} \quad (413) $$

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

## O Proof of Lemma 6.1

Consider the partition of the set $M$ formed by the sets $A_0$, $A_1$, and $A_2$ in (307). From (96), for all $λ \in K_{Q,z}$, with $K_{Q,z}$ in (23), it holds that,

$$ K_{Q,z}^{(1)}(-\frac{1}{λ}) = \int_{A_0} L_z(θ) dP_{\Theta|Z=z}^{(Q,λ)}(θ) + \int_{A_1} L_z(θ) dP_{\Theta|Z=z}^{(Q,λ)}(θ) \quad (415) $$

$$ + \int_{A_2} L_z(θ) dP_{\Theta|Z=z}^{(Q,λ)}(θ) \quad (416) $$

$$ = \int_{A_0} L_z(θ) dP_{\Theta|Z=z}^{(Q,λ)}(θ) + \int_{A_2} L_z(θ) dP_{\Theta|Z=z}^{(Q,λ)}(θ) \quad (417) $$

$$ = \delta_{Q,z}^{*} P_{\Theta|Z=z}^{(Q,λ)}(\mathcal{L}_{Q,z}^{*}) + \int_{A_2} L_z(θ) dP_{\Theta|Z=z}^{(Q,λ)}(θ) \quad (418) $$

$$ \ge \delta_{Q,z}^{*} P_{\Theta|Z=z}^{(Q,λ)}(\mathcal{L}_{Q,z}^{*}) + \delta_{Q,z}^{*} P_{\Theta|Z=z}^{(Q,λ)}(A_2) \quad (419) $$

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

where the equality in (417) follows by noticing that $Q(A_1) = 0$, which implies that $P_{\Theta|Z=z}^{(Q,λ)}(A_1) = 0$ (Lemma 3.3); the equality in (418) follows from noticing that $A_0 = \mathcal{L}_{Q,z}^{*}$, with $\mathcal{L}_{Q,z}^{*}$ in (38); and the equality in (419) follows from (307c). This completes the proof.
Second, if $c_{\gamma} \ge K_{Q,z}^{(1)}(-\frac{1}{\gamma})$ then for all $\nu \in \mathcal{A}(\gamma)$, it holds that $\mathbf{L}_z(\nu) > c_{\gamma} \ge K_{Q,z}^{(1)}(-\frac{1}{\gamma})$, and thus,

$$ \left( \mathbf{L}_z(\nu) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 > \left( c_{\gamma} - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2, \quad (412) $$

which implies,

$$ \int_{\mathcal{A}(\gamma)} \left( \mathbf{L}_z(\theta) - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right) \right)^2 dP_{\Theta|Z=z}^{(Q,\gamma)}(\theta) > \begin{aligned}[t] & \left(c_{\gamma} - K_{Q,z}^{(1)}\left(-\frac{1}{\gamma}\right)\right)^2 P_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{A}(\gamma)) \\ & > 0. \end{aligned} \quad (413) $$

Hence, under the assumption that the empirical risk function $\mathbf{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.

## O Proof of Lemma 6.1

Consider the partition of the set $\mathcal{M}$ formed by the sets $\mathcal{A}_0, \mathcal{A}_1$, and $\mathcal{A}_2$ in (307). 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} \mathbf{L}_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) + \int_{\mathcal{A}_1} \mathbf{L}_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (415) $$

$$ + \int_{\mathcal{A}_2} \mathbf{L}_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (416) $$

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

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

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

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

where the equality in (417) follows by noticing that $Q(\mathcal{A}_1) = 0$, which implies that $P_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}_1) = 0$ (Lemma 3.3); the equality in (418) follows from noticing that $\mathcal{A}_0 = \mathcal{L}_{Q,z}^{*}$, with $\mathcal{L}_{Q,z}^{*}$ in (38); and the equality in (419) follows from (307c). This completes the proof.
## P Proof of Theorem 6.2

From (418) in the proof of Lemma 6.1, 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_{A_2} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (421) $$

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

$$ + \lim_{\lambda \to 0^+} \int_{A_2} L_z(\theta) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \quad (422) $$

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

$$ + \int_{A_2} L_z(\theta) \lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \quad (423) $$

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

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

where, the equality in (423) 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 3.2); and (b) For all $\theta \in A_2$, it holds that $\lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 0$ (Lemma 3.6). Hence, the dominated convergence theorem [58, Theorem 1.6.9] holds. The inequality in (424) follows from Lemma 3.7. This completes the proof.

## Q Proof of Theorem 9.1

From Theorem 6.1, 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 (426a) $$

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

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

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

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

$$ \mathcal{N}_{Q,z}(\lambda_1) \supseteq \mathcal{N}_{Q,z}(\lambda_2). \quad (428) $$
## P Proof of Theorem 6.2

From (418) in the proof of Lemma 6.1, 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_{A_2} L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (421) $$

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

$$ + \lim_{\lambda \to 0^+} \int_{A_2} L_z(\theta) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \quad (422) $$

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

$$ + \int_{A_2} L_z(\theta) \lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \quad (423) $$

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

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

where, the equality in (423) 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 3.2); and (b) For all $\theta \in A_2$, it holds that $\lim_{\lambda \to 0^+} \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 0$ (Lemma 3.6). Hence, the dominated convergence theorem [58, Theorem 1.6.9] holds. The inequality in (424) follows from Lemma 3.7. This completes the proof.

## Q Proof of Theorem 9.1

From Theorem 6.1, 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 (426a) $$

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

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

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

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

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

$$ \mathbb{R}_z \left( P_{\Theta|Z=z}^{(Q, \lambda_2)} \right) \geq \delta_{Q,z}^* = \mathbb{L}_z(\nu), \qquad (429) $$

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 [69, Theorem 4.23] and the assumption that the empirical risk function $\mathbb{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

$$ \mathbb{L}_z(\theta) = \int \mathbb{L}_z(\alpha) dP_{\Theta|Z=z}^{(Q, \lambda)}(\alpha), \qquad (430) $$

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 (428), verifies that

$$ \mathcal{N}_{Q,z}(\lambda_1) \supset \mathcal{N}_{Q,z}(\lambda_2). \qquad (431) $$

The strict inclusion $\mathcal{M} \supset \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 N.1, 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. \qquad (432) $$

This contradicts the assumption that the function $\mathbb{L}_z$ is separable (Definition 5.1). Hence, $\mathcal{M} \supset \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,

$$ \{ \theta \in \mathcal{M} : \mathbb{L}_z(\theta) \leq \delta_{Q,z}^* \} = \mathcal{N}_{Q,z}^* \qquad (433) $$

$$ = \mathcal{N}_{Q,z}(\lambda) \qquad (434) $$

$$ = \{ \theta \in \mathcal{M} : \mathbb{L}_z(\theta) \leq K_{Q,z}^{(1)} \left( -\frac{1}{\lambda} \right) \}. \qquad (435) $$

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}^* < \mathbb{L}_z(\nu) \leq K_{Q,z}^{(1)} \left( -\frac{1}{\lambda} \right) \} = \emptyset; $$
The inclusion $\mathcal{M} \supseteq \mathcal{N}_{Q,z}(\lambda_1)$ follows from (166). Alternatively, the inclusion $\mathcal{N}_{Q,z}(\lambda_2) \supset \mathcal{N}_{Q,z}^*$, follows from Lemma 6.1 and from observing that for all $\nu \in \mathcal{N}_{Q,z}^*$,

$$ \mathbb{R}_z \left( P_{\Theta|Z=z}^{(Q, \lambda_2)} \right) \geq \delta_{Q,z}^* = \mathbb{L}_z(\nu), \qquad (429) $$

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 [69, Theorem 4.23] and the assumption that the empirical risk function $\mathbb{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

$$ \mathbb{L}_z(\theta) = \int \mathbb{L}_z(\alpha) dP_{\Theta|Z=z}^{(Q, \lambda)}(\alpha), \qquad (430) $$

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 (428), verifies that

$$ \mathcal{N}_{Q,z}(\lambda_1) \supset \mathcal{N}_{Q,z}(\lambda_2). \qquad (431) $$

The strict inclusion $\mathcal{M} \supset \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 N.1, 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. \qquad (432) $$

This contradicts the assumption that the function $\mathbb{L}_z$ is separable (Definition 5.1). Hence, $\mathcal{M} \supset \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,

$$ \{\theta \in \mathcal{M} : \mathbb{L}_z(\theta) \leq \delta_{Q,z}^*\} = \mathcal{N}_{Q,z}^* \qquad (433) $$

$$ = \mathcal{N}_{Q,z}(\lambda) \qquad (434) $$

$$ = \{\theta \in \mathcal{M} : \mathbb{L}_z(\theta) \leq K_{Q,z}^{(1)} \left(-\frac{1}{\lambda}\right)\}. \qquad (435) $$

Hence, three cases might arise:

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

$$ \{\nu \in \mathcal{M} : \delta_{Q,z}^* < \mathbb{L}_z(\nu) \leq 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) < \mathbf{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} : \mathbf{L}_z(\boldsymbol{\nu}) < \delta_{Q,z}^* \}, \quad (436) $$

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 (437) $$

From Lemma N.1 and (437), it follows that,

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

Finally, by noticing that

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

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

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

## R Proof of Theorem 9.2

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} (\boldsymbol{\alpha}) \, dQ (\boldsymbol{\alpha}), \quad (441) $$

and from the fundamental theorem of calculus [69, 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 (442) $$

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

$$ = \int_{\lambda_2}^{\lambda_1} \int_{\mathcal{A}} \frac{d}{d\gamma} \frac{dP_{\Theta|Z=z}^{(Q,\gamma)}}{dQ} (\boldsymbol{\alpha}) \, dQ (\boldsymbol{\alpha}) \, d\gamma, \quad (444) $$
(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) < \mathcal{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} : \mathcal{L}_z(\boldsymbol{\nu}) < \delta_{Q,z}^* \}, \quad (436) $$

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 (437) $$

From Lemma N.1 and (437), it follows that,

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

Finally, by noticing that

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

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

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

## R Proof of Theorem 9.2

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 (441) $$

and from the fundamental theorem of calculus [69, 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{\mathrm{d}}{\mathrm{d}\gamma} P_{\Theta|Z=z}^{(Q,\gamma)} (\mathcal{A}) \mathrm{d}\gamma \quad (442) $$

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

$$ = \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 (444) $$
where the equality in (443) follows from (441); and the equality in (444) holds from Lemma 3.2 and the dominated convergence theorem [58, Theorem 1.6.9].

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

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

$$ = \frac{\frac{1}{\lambda^2} L_z(\theta) \exp\left(-\frac{L_z(\theta)}{\lambda}\right)}{\int \exp\left(-\frac{L_z(\nu)}{\lambda}\right) dQ(\nu)} - \frac{\frac{1}{\lambda^2} \exp\left(-\frac{L_z(\theta)}{\lambda}\right) \int L_z(\alpha) \exp\left(-\frac{L_z(\alpha)}{\lambda}\right) dQ(\alpha)}{\left(\int \exp\left(-\frac{L_z(\nu)}{\lambda}\right) dQ(\nu)\right)^2} \quad (446) $$

$$ = \frac{1}{\lambda^2} 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 L_z(\nu) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\nu) dQ(\nu) \quad (447) $$

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

Plugging (448) into (444) yields,

$$ 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( L_z(\alpha) - \int L_z(\nu) dP_{\Theta|Z=z}^{(Q,\gamma)}(\nu) \right) dQ(\alpha) d\gamma \quad (449) $$

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

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

$$ L_z(\alpha) - \int L_z(\nu) dP_{\Theta|Z=z}^{(Q,\gamma)}(\nu) \le 0, \quad (451) $$

and thus,

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

The equalities in (450) and (452), 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 (453) $$
where the equality in (443) follows from (441); and the equality in (444) holds from Lemma 3.2 and the dominated convergence theorem [58, Theorem 1.6.9].

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

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

$$ = \frac{\frac{1}{\lambda^2} L_z(\theta) \exp\left(-\frac{L_z(\theta)}{\lambda}\right)}{\int \exp\left(-\frac{L_z(\nu)}{\lambda}\right) dQ(\nu)} - \frac{\frac{1}{\lambda^2} \exp\left(-\frac{L_z(\theta)}{\lambda}\right) \int L_z(\alpha) \exp\left(-\frac{L_z(\alpha)}{\lambda}\right) dQ(\alpha)}{\left(\int \exp\left(-\frac{L_z(\nu)}{\lambda}\right) dQ(\nu)\right)^2} \quad (446) $$

$$ = \frac{1}{\lambda^2} 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 L_z(\nu) \frac{dP_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\nu) dQ(\nu) \quad (447) $$

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

Plugging (448) into (444) yields,

$$ 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( L_z(\alpha) - \int L_z(\nu) dP_{\Theta|Z=z}^{(Q,\gamma)}(\nu) \right) dQ(\alpha) d\gamma \quad (449) $$

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

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

$$ L_z(\alpha) - \int L_z(\nu) dP_{\Theta|Z=z}^{(Q,\gamma)}(\nu) \le 0, \quad (451) $$

and thus,

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

The equalities in (450) and (452), 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 (453) $$
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 N.2. 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 (454)$$

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 (454) holds.

The first part is as follows. In the proof of Theorem 9.1 it is shown (see (450)) that for all pairs $(\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{N}_{Q,z}(\lambda_2)) - P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)) \\ & = \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. \end{aligned} \quad (455)$$

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 (454) holds. Then, from (455),

$$\begin{aligned} & 0 > \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_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) d\gamma \\ & = \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_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) d\gamma, \end{aligned} \quad (456)$$

where the equality in (456) 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 (381a), (381b), and (166), respectively.

The inequality in (456) implies that the set $\mathcal{R}_1(\lambda_2)$ is nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$, for some $\gamma \in (\lambda_2, \lambda_1)$. Hence, from Lemma N.2, 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 (457)$$

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}{\gamma}\right) > \mathbf{L}_z(\boldsymbol{\nu}_2), \quad (458)$$
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 N.2. 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 (454)$$

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 (454) holds.

The first part is as follows. In the proof of Theorem 9.1 it is shown (see (450)) that for all pairs $(\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{N}_{Q,z}(\lambda_2)) - P_{\Theta|Z=z}^{(Q,\lambda_2)}(\mathcal{N}_{Q,z}(\lambda_2)) \\ &= \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. \end{aligned} \quad (455)$$

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 (454) holds. Then, from (455),

$$\begin{aligned} & 0 > \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_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) d\gamma \\ &= \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_{\Theta|Z=z}^{(Q,\gamma)}(\boldsymbol{\alpha}) d\gamma, \end{aligned} \quad (456)$$

where the equality in (456) 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 (381a), (381b), and (166), respectively.

The inequality in (456) implies that the set $\mathcal{R}_1(\lambda_2)$ is nonnegligible with respect to $P_{\Theta|Z=z}^{(Q,\gamma)}$, for some $\gamma \in (\lambda_2, \lambda_1)$. Hence, from Lemma N.2, 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 (457)$$

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}{\gamma}\right) > \mathbf{L}_z(\boldsymbol{\nu}_2), \quad (458)$$
which together with Definition 5.1 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 5.1). 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 5.1). That is, from Definition 5.1, for all $\gamma \in 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 (459)$$

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

$$ \begin{aligned} & P_{\Theta|Z=z}^{(Q,\alpha_1)}(\mathcal{A}) - P_{\Theta|Z=z}^{(Q,\alpha_2)}(\mathcal{A}) \\ &= \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 \\ &= \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. \end{aligned} \quad (460) $$

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

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

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

$$c_\gamma \ge K_{Q,z}^{(1)} \left(-\frac{1}{\gamma}\right). \quad (462)$$

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

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

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 (464)$$

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

where, the inequality in (465) 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 to $P_{\Theta|Z=z}^{(Q,\gamma)}$. Moreover, from (166) and (463), 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) \mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}(\nu) < L_z(\alpha) - c_\gamma \quad (466)$$

$$<0, \quad (467)$$
which together with Definition 5.1 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 5.1). 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 5.1). That is, from Definition 5.1, for all $\gamma \in 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). \qquad (459)$$

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

$$ \begin{aligned} & P_{\Theta|Z=z}^{(Q,\alpha_1)}(\mathcal{A}) - P_{\Theta|Z=z}^{(Q,\alpha_2)}(\mathcal{A}) \\ &= \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 \\ &= \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. \end{aligned} \qquad (460) $$

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

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

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

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

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

$$\mathcal{B}(\gamma) \subset \mathcal{N}_{Q,z}(\gamma), \qquad (463)$$

which implies that

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

$$>0, \qquad (465)$$

where, the inequality in (465) 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 to $P_{\Theta|Z=z}^{(Q,\gamma)}$. Moreover, from (166) and (463), it follows that for all $\alpha \in \mathcal{N}_{Q,z}(\gamma)$ and for all $\lambda \in (\gamma, \alpha_1)$,

$$\mathbf{L}_z(\alpha) - \int \mathbf{L}_z(\nu) \mathrm{d}P_{\Theta|Z=z}^{(Q,\lambda)}(\nu) < \mathbf{L}_z(\alpha) - c_\gamma \qquad (466)$$

$$<0, \qquad (467)$$
where the inequality in (466) follows from (461); and the inequality in (467) follows from (459). 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) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\alpha}) d\lambda < 0, $$

which implies, from (460), that

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

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

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

which implies that

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

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

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

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

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

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

From (166) and Theorem 6.1, it follows that for all $\boldsymbol{\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}) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\boldsymbol{\nu}) \quad (474) $$

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

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) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\alpha}) d\lambda < 0, $$

which implies, from (460), that

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

This completes the proof.
where the inequality in (466) follows from (461); and the inequality in (467) follows from (459). 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) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\alpha}) d\lambda < 0, $$

which implies, from (460), that

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

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

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

which implies that

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

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

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

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

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

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

From (166) and Theorem 6.1, it follows that for all $\boldsymbol{\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}) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\boldsymbol{\nu}) \quad (474) $$

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

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) dP_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\alpha}) d\lambda < 0, $$

which implies, from (460), that

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

This completes the proof.
## S Proof of Lemma 9.2

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 (381c). 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 (477) $$

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 (478) $$

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

$$ + P_{\Theta|Z=z}^{(\lambda_i)}(\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)), \quad (480) $$

where the equality in (479) follows from Lemma 3.3 and the equality in (173).

Finally, under the assumption that the empirical function $L_z$ in (3) is separable, it holds from Theorem 9.2 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 (481) $$

Plugging (480) into (481), 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 (482) $$

and this completes the proof.

## T Proof of Theorem 11.2

Consider the following lemma.

**Lemma T.1.** 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$,

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

where the function $\mathbb{L}_z$ and the functional $\mathbb{R}_z$ are defined in (3) and in (18), respectively.
## S Proof of Lemma 9.2

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 (381c). 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 (477) $$

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 (478) $$

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

$$ + P_{\Theta|Z=z}^{(\lambda_i)}(\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)), \quad (480) $$

where the equality in (479) follows from Lemma 3.3 and the equality in (173).

Finally, under the assumption that the empirical function $L_z$ in (3) is separable, it holds from Theorem 9.2 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 (481) $$

Plugging (480) into (481), 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 (482) $$

and this completes the proof.

## T Proof of Theorem 11.2

Consider the following lemma.

**Lemma T.1.** 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$,

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

where the function $\mathbb{L}_z$ and the functional $\mathbb{R}_z$ are defined in (3) and in (18), respectively.
*Proof:* From [56, 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(\theta)dP_2(\theta) - \log \int \exp(f(\theta))dP_1(\theta), \quad (484)$$

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(\theta))dP_1(\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 tL_z(\theta) dP_2(\theta) - \log \int \exp(tL_z(\theta)) dP_1(\theta) \\
&\ge \int tL_z(\theta) dP_2(\theta) \\
&\quad - \log \int \exp(tL_z(\theta) + tR_z(P_1) - tR_z(P_1)) dP_1(\theta) \\
&= \int tL_z(\theta) dP_2(\theta) - tR_z(P_1) \\
&\quad - \log \int \exp(tL_z(\theta) - tR_z(P_1)) dP_1(\theta) \\
&= tR_z(P_2) - tR_z(P_1) - \log \int \exp(tL_z(\theta) - tR_z(P_1)) dP_1(\theta),
\end{align*}
$$

which leads to

$$R_z(P_2) - R_z(P_1) \le \frac{D(P_2\|P_1) + \log \int \exp(t(L_z(\theta) - R_z(P_1))) dP_1(\theta)}{t}. \quad (485)$$

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

$$R_z(P_2) - R_z(P_1) \le \inf_{t \in (-\infty, 0)} \frac{D(P_2\|P_1) + \log \int \exp(t(L_z(\theta) - R_z(P_1))) dP_1(\theta)}{t},$$

which completes the proof. ■

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

$$R_z(P) - R_z(P_0) \le \inf_{t \in (-\infty, 0)} \left( \frac{D(P\|P_0) + \log \int \exp(t(L_z(\theta) - K_{Q,z}^{(1)}(-\frac{1}{\lambda})) dP_0(\theta)}{t} \right), (486)$$

where the function $K_{Q,z}^{(1)}$ is defined in (96) and satisfies (104). Moreover, for
*Proof:* From [56, 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(\theta)dP_2(\theta) - \log \int \exp(f(\theta))dP_1(\theta), \quad (484)$$

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(\theta)) dP_1(\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 tL_z(\theta) dP_2(\theta) - \log \int \exp(tL_z(\theta)) dP_1(\theta) \\
&\ge \int tL_z(\theta) dP_2(\theta) \\
&\quad - \log \int \exp(tL_z(\theta) + tR_z(P_1) - tR_z(P_1)) dP_1(\theta) \\
&= \int tL_z(\theta) dP_2(\theta) - tR_z(P_1) \\
&\quad - \log \int \exp(tL_z(\theta) - tR_z(P_1)) dP_1(\theta) \\
&= tR_z(P_2) - tR_z(P_1) - \log \int \exp(tL_z(\theta) - tR_z(P_1)) dP_1(\theta),
\end{align*}
$$

which leads to

$$R_z(P_2) - R_z(P_1) \le \frac{D(P_2\|P_1) + \log \int \exp(t(L_z(\theta) - R_z(P_1))) dP_1(\theta)}{t}. \quad (485)$$

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

$$R_z(P_2) - R_z(P_1) \le \inf_{t \in (-\infty, 0)} \frac{D(P_2\|P_1) + \log \int \exp(t(L_z(\theta) - R_z(P_1))) dP_1(\theta)}{t},$$

which completes the proof. ■

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

$$R_z(P) - R_z(P_0) \le \inf_{t \in (-\infty, 0)} \left( \frac{D(P\|P_0) + \log \int \exp(t(L_z(\theta) - K_{Q,z}^{(1)}(-\frac{1}{\lambda})) dP_0(\theta)}{t} \right), (486)$$

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

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

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

$$ \le \frac{1}{2} t^2 \beta_{Q,z}^2, \quad (489) $$

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

Plugging (489) into (486) yields for all $t \in (-\infty, 0)$,

$$ \mathbf{R}_z(P) - \mathbf{R}_z(P_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}) \le \inf_{t \in (-\infty, 0)} \frac{D(P \| P_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}) + \frac{1}{2} t^2 \beta_{Q,z}^2}{t}. \quad (490) $$

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

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

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

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

The rest of the proof consists in finding an explicit expression for the absolute value of $c$ in (492). 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 (493) $$

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 (494) $$

In particular, note that

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

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

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

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 (497) $$
all $t \in (-\infty, 0)$,

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

$$ =J_{z,Q,\lambda}(t)-tK_{Q,z}^{(1)}\left(-\frac{1}{\lambda}\right) \quad (488) $$

$$ \leq \frac{1}{2} t^2 \beta_{Q,z}^2, \quad (489) $$

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

Plugging (489) into (486) yields for all $t \in (-\infty, 0)$,

$$ \mathbf{R}_z(P) - \mathbf{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)}) \le \inf_{t \in (-\infty, 0)} \frac{D(P\|P_{\Theta|Z=z}^{(Q,\lambda)}) + \frac{1}{2}t^2\beta_{Q,z}^2}{t} \quad (490) $$

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

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

Hence, from (490), 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 (492) $$

The rest of the proof consists in finding an explicit expression for the absolute value of $c$ in (492). 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 (493) $$

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 (494) $$

In particular, note that

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

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

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

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 (497) $$
That is,

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

Plugging (498) into (496) yields,

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

Hence, from (495) and (496), given $c$ in (491) 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)}), \qquad (500) $$

and thus,

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

This implies that

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

and

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

which leads to

$$ \left| \int L_z(\theta) dP(\theta) - \int L_z(\theta) dP_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \right| \le \sqrt{2\beta_{Q,z}^2 D(P\|P_{\Theta|Z=z}^{(Q,\lambda)})}, \qquad (504) $$

and completes the proof.

## U Proof of Theorem 11.4

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

$$ G_{Q,\lambda}(P_Z) = \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), \qquad (505) $$

$$ = \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), \qquad (506) $$
That is,

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

Plugging (498) into (496) yields,

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

Hence, from (495) and (496), given $c$ in (491) 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)}), \qquad (500) $$

and thus,

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

This implies that

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

and

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

which leads to

$$ \left| \int \mathcal{L}_z(\boldsymbol{\theta}) dP(\boldsymbol{\theta}) - \int \mathcal{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)})}, \qquad (504) $$

and completes the proof.

## U Proof of Theorem 11.4

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

$$ G_{Q,\lambda}(P_Z) = \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), \qquad (505) $$

$$ = \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), \qquad (506) $$
where the equality in (506) 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 (507) $$

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

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

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

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

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

The equality in (510) follows from (203); and the equality in (511) 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. This completes the proof.
where the equality in (506) 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 (507) $$

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

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

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

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

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

The equality in (510) follows from (203); and the equality in (511) 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. 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] 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.

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

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

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

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

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

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

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

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

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

[12] Y. Bu, G. Aminian, L. Toni, G. W. Wornell, and M. Rodrigues, “Characterizing and understanding the generalization error of transfer learning with
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] 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[22] 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.
Gibbs algorithm,” in Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), Virtual Conference, Mar. 2022, pp. 8673–8699.

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

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

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

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

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

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

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

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

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

[22] 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.
[23] 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[36] 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.
[37] T. Jaakkola, M. Meila, and T. Jebara, "Maximum entropy discrimination," *Neural Information Processing Systems*, vol. 12, pp. 470–476, Dec. 1999.

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

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

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

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

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

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

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

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

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

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

[48] 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.
[37] T. Jaakkola, M. Meila, and T. Jebara, "Maximum entropy discrimination," *Neural Information Processing Systems*, vol. 12, pp. 470–476, Dec. 1999.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[56] S. Boucheron, G. Lugosi, and P. Massart, *Concentration Inequalities: A Non-asymptotic Theory of Independence*, 1st ed. Oxford, UK: Oxford University Press, 2013.

[57] T. M. Cover and J. A. Thomas, *Elements of Information Theory*, 2nd ed. Hoboken, NJ: Wiley-Interscience, 2006.

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

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

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

[61] A. Dembo and O. Zeitouni, *Large Deviations Techniques and Applications*, 2nd ed. New York, NY, USA: Springer-Verlag, 2009.
[49] 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.

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

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

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

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

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

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

[56] S. Boucheron, G. Lugosi, and P. Massart, *Concentration Inequalities: A Non-asymptotic Theory of Independence*, 1st ed. Oxford, UK: Oxford University Press, 2013.

[57] T. M. Cover and J. A. Thomas, *Elements of Information Theory*, 2nd ed. Hoboken, NJ: Wiley-Interscience, 2006.

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

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

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

[61] A. Dembo and O. Zeitouni, *Large Deviations Techniques and Applications*, 2nd ed. New York, NY, USA: Springer-Verlag, 2009.
[62] E. T. Jaynes, "Information theory and statistical mechanics I," *Physical Review Journals*, vol. 106, no. 4, pp. 620-630, May 1957.

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

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

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

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

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

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

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

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

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

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

[73] W. Feller, *An Introduction to Probability Theory and Its Applications II*, 2nd ed. New York, NY, USA: Jhon Wiley & Sons, 1971.
[62] E. T. Jaynes, “Information theory and statistical mechanics I,” *Physical Review Journals*, vol. 106, no. 4, pp. 620–630, May 1957.

[63] —, “Information theory and statistical mechanics II,” *Physical Review Journals*, vol. 108, no. 2, pp. 171–190, Oct. 1957.

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

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

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

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

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

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

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

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

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

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

RESEARCH CENTRE
SOPHIA ANTIPOLIS – MÉDITERRANÉE

2004 route des Lucioles - BP 93
06902 Sophia Antipolis Cedex

Publisher
Inria
Domaine de Voluceau -
Rocquencourt
BP 105 - 78153 Le Chesnay
Cedex
inria.fr
informatics mathematics
Inria

RESEARCH CENTRE
SOPHIA ANTIPOLIS – MÉDITERRANÉE

2004 route des Lucioles - BP 93
06902 Sophia Antipolis Cedex

Publisher
Inria
Domaine de Voluceau -
Rocquencourt
BP 105 - 78153 Le Chesnay
Cedex
inria.fr