it follows that

$$ \frac{\lambda}{\bar{K}_{Q,z}(\lambda) + \mathbf{L}_z(\theta_1)} \geq \frac{\lambda}{\bar{K}_{Q,z}(\lambda) + \mathbf{L}_z(\theta_2)}, \quad (166a) $$

where the function $\bar{K}_{Q,z}$ is defined in (23); and equality holds if and only if (165) holds with equality. The proof is completed by noticing that from (24), the inequality above can be rewritten as

$$ \frac{d\bar{P}^{(Q,\lambda)}_{\Theta|Z=z}(\theta_1)}{dQ} \geq \frac{d\bar{P}^{(Q,\lambda)}_{\Theta|Z=z}(\theta_2)}{dQ}, \quad (167) $$

which completes the proof.

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

## H Proof of Lemma 5.2

From Lemma 5.1, it follows that for all $\theta \in \text{supp } Q$, and for all $\phi \in \mathcal{L}_{Q,z}^* \cap \text{supp } Q$, it holds that

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

$$ = \frac{\lambda}{\mathbf{L}_z(\phi) + \bar{K}_{Q,z}(\lambda)} \quad (168b) $$

$$ \leq \frac{\lambda}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} \quad (168c) $$

$$ < \infty, \quad (168d) $$

where (168b) follows from (24); the equality in (168c) follows from the fact that $\mathbf{L}_z(\phi) \geq \delta_{Q,z}^*$; and (168d) follows from the fact that $\bar{K}_{Q,z}(\lambda) < \infty$. Note that equalities in (168a) and (168c) hold if and only if $\theta \in \mathcal{L}_{Q,z}^* \cap \text{supp } Q$ (Lemma 4.6). This completes the proof of finiteness.

For the proof of positivity, observe that from Lemma 4.2, it holds that

$$ -\delta_{Q,z}^* < \bar{K}_{Q,z}(\lambda) < \infty, \quad (169) $$

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

$$ 0 < \delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda) \quad (170) $$

$$ \leq \mathbf{L}_z(\theta) + \bar{K}_{Q,z}(\lambda). \quad (171) $$

Hence, from the fact that $\lambda > 0$, it holds from (24) and (171) that

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

which completes the proof.

<figure><img src="image_17.png" /></figure>
such that

$$ \lim_{i \to \infty} \mathbf{L}_z(\nu_i) = \delta_{Q,z}^* \qquad (172) $$

From (172) the function inside the integral in (169c) is unbounded over the set $A_1$. Therefore,

$$ \lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{1}{0 + (\infty)\epsilon} \qquad (173a) $$

$$ = 0. \qquad (173b) $$

The third part of the proof follows by noticing that the set $\{\nu \in \text{supp } Q : \mathbf{L}_z(\nu) < \delta_{Q,z}^*\}$ has measure zero with respect to $Q$ and thus, for all $\theta \in \{\nu \in \text{supp } Q : \mathbf{L}_z(\nu) < \delta_{Q,z}^*\}$, the value $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta)$ is unchanged. Hence, it is assumed that for all $\theta \in \{\nu \in \text{supp } Q : \mathbf{L}_z(\nu) < \delta_{Q,z}^*\}$, it holds that

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

This completes the third part and the entire proof.

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

## J Proof of Lemma 4.13

*Proof:* Consider the following partition of the set $\mathcal{M}$ formed by the sets

$$ A_0 = \{\theta \in \mathcal{M} : \mathbf{L}_z(\theta) = \delta_{Q,z}^*\}, \qquad (175a) $$

$$ A_1 = \{\theta \in \mathcal{M} : \mathbf{L}_z(\theta) > \delta_{Q,z}^*\}, \qquad (175b) $$

$$ A_2 = \{\theta \in \mathcal{M} : \mathbf{L}_z(\theta) < \delta_{Q,z}^*\}, \qquad (175c) $$

with $\delta_{Q,z}^*$ in (28) and the function $\mathbf{L}_z$ in (3). Note that $A_0 = \mathcal{L}_{Q,z}^*$, with $\mathcal{L}_{Q,z}^*$ in (29).

For all $\lambda \in (0, \infty)$, it holds that

$$ 1 = \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_1) + \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_2) \qquad (176a) $$

$$ = \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_1) \qquad (176b) $$

$$ = \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \int_{A_1} d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta), \qquad (176c) $$

where equality (176b) follows from the fact that $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_2) = 0$, which follows from the definition of $\delta_{Q,z}^*$ in (28) and the fact that the probability measure
# I Proof of Lemma 5.3

From Theorem 1, the Radon-Nikodym derivative of the measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ with respect to $Q$, satisfies for all $\theta \in \text{supp } Q$,

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

$$ = \frac{1}{\beta + \mathbf{L}_z(\theta)} \frac{1}{\int \frac{1}{\beta + \mathbf{L}_z(\nu)} dQ(\nu)} \quad (173b) $$

$$ = \frac{1}{\int \frac{\beta}{\beta + \mathbf{L}_z(\nu)} dQ(\nu) + \int \frac{\mathbf{L}_z(\theta)}{\beta + \mathbf{L}_z(\nu)} dQ(\nu)}, \quad (173c) $$

where (173b) follows from (26), which implies that

$$ \lambda = \bar{K}_{Q,z}^{-1}(\beta) = \frac{1}{\int \frac{1}{\mathbf{L}_z(\theta) + \beta} dQ(\theta)}, \quad (174) $$

with the function $\bar{K}_{Q,z}^{-1}$ being the inverse of the function $\bar{K}_{Q,z}$ in (23). Using the function $\bar{K}_{Q,z}$, the equation in (173) can be written in term of $\lambda$ such that

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{1}{\int \frac{\bar{K}_{Q,z}(\lambda)}{\bar{K}_{Q,z}(\lambda)+\mathbf{L}_z(\nu)} dQ(\nu) + \int \frac{\mathbf{L}_z(\theta)}{\bar{K}_{Q,z}(\lambda)+\mathbf{L}_z(\nu)} dQ(\nu)}. \quad (175) $$

Furthermore, using Lemma 4.1 and Lemma 4.2, the following holds from (175),

$$ \lim_{\lambda \to \infty} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \lim_{\lambda \to \infty} \frac{1}{\int \frac{\bar{K}_{Q,z}(\lambda)}{\bar{K}_{Q,z}(\lambda)+\mathbf{L}_z(\nu)} dQ(\nu) + \int \frac{\mathbf{L}_z(\theta)}{\bar{K}_{Q,z}(\lambda)+\mathbf{L}_z(\nu)} dQ(\nu)} \quad (176a) $$

$$ = \frac{1}{\lim_{\beta \to \infty} \int \frac{\beta}{\beta + \mathbf{L}_z(\nu)} dQ(\nu) + \lim_{\beta \to \infty} \int \frac{\mathbf{L}_z(\theta)}{\beta + \mathbf{L}_z(\nu)} dQ(\nu)}, \quad (176b) $$

where the function $\mathbf{L}_z$ is defined in (3); and (176b) follows from Theorem 3.1, which implies that the terms in the denominator are positive and the fact that the function $g(x) = \frac{1}{x}$ is continuous. Recall that from the definition of the function $\mathbf{L}_z$ in (3), for all $\theta \in \text{supp } Q$, the empirical risk satisfies that $\mathbf{L}_z(\theta) < \infty$. Using this fact, the proof continues by evaluating the limits in the denominator, which yields

$$ \lim_{\beta \to \infty} \int \frac{\beta}{\beta + \mathbf{L}_z(\nu)} dQ(\nu) = \int \lim_{\beta \to \infty} \frac{\beta}{\beta + \mathbf{L}_z(\nu)} dQ(\nu) \quad (177a) $$

$$ = \int dQ(\nu) \quad (177b) $$

$$ = 1, \quad (177c) $$
$\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ is mutually absolutely continuous with respect to the reference measure $Q$. The above implies that

$$ \lim_{\lambda \to 0^+} \left( \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \int_{A_1} d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \right) = \lim_{\lambda \to 0^+} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \lim_{\lambda \to 0^+} \int_{A_1} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \quad (177a) $$

$$ = \lim_{\lambda \to 0^+} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \int_{A_1} \lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \quad (177b) $$

$$ = \lim_{\lambda \to 0^+} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0), \quad (177c) $$

$$ = 1, \quad (177d) $$

where, the equality in (177b) follows from the dominated convergence theorem [45, Theorem 1.6.9 page 50], given that from Lemma 4.10 for all $\lambda \in \bar{K}_{Q,z}$, the Radon-Nikodym derivative $\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}$ is positive and finite; and the equality in (177c) follows from the fact that for all $\theta \in A_1$, it holds that $\lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = 0$ from Lemma 4.12.

Hence, it holds that

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

which completes the proof.

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

## K Proof of Lemma 5.1

*Proof:* From Lemma 4.1 and the fact that the measures $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ are mutually absolutely continuous, it holds that for all $\theta \in \text{supp} Q$,

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

where the functions $L_z$ and $\bar{K}_{Q,z}$ are in (3) and (23b), respectively. From (179), it follows that for all $\theta \in \text{supp} Q$,

$$ 0 = \lambda \frac{dQ}{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) - L_z(\theta) - \bar{K}_{Q,z}(\lambda). \quad (180) $$

Integrating both sides of (180) with respect to the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ yields

$$ 0 = \int \left( L_z(\theta) - \lambda \left( \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right)^{-1} + \bar{K}_{Q,z}(\lambda) \right) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (181a) $$
where (177a) follows from the dominated convergence theorem [54, Theorem 1.6.9]; and,

$$ \lim_{\beta \to \infty} \int \frac{L_z(\theta)}{\beta + L_z(\nu)} dQ(\nu) = \int \lim_{\beta \to \infty} \frac{L_z(\theta)}{\beta + L_z(\nu)} dQ(\nu) \quad (178a) $$

$$ = \int 0 dQ(\nu) \quad (178b) $$

$$ = 0, \quad (178c) $$

where (178a) also follows from the dominated convergence theorem [54, Theorem 1.6.9]. Substituting (177) and (178) into (176) yields

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

which completes the proof.

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

## J Proof of Lemma 5.4

From Theorem 3.1, the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ satisfies for all $\theta \in \text{supp } Q$,

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

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

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

$$ = \frac{\frac{1}{\int_{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu)}}{L_z(\theta) + \bar{K}_{Q,z}(\lambda)} \quad (180d) $$

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

where (180b) follows from (23); and (180d) follows from (26) and observing that $\lambda = \bar{K}_{Q,z}^{-1}(\beta)$. Given $\theta \in \text{supp } Q$, consider the partition of the supp $Q$ formed by the sets $A_0(\theta)$, $A_1(\theta)$, and $A_2(\theta)$, which satisfy the following:

$$ A_0(\theta) = \{\nu \in \text{supp } Q : L_z(\theta) - L_z(\nu) = 0\}, \quad (181a) $$

$$ A_1(\theta) = \{\nu \in \text{supp } Q : L_z(\theta) - L_z(\nu) < 0\}, \quad \text{and} \quad (181b) $$

$$ A_2(\theta) = \{\nu \in \text{supp } Q : L_z(\theta) - L_z(\nu) > 0\}. \quad (181c) $$

Using the sets $A_0(\theta)$, $A_1(\theta)$, and $A_2(\theta)$ in (181), the following holds for all $\theta \in \text{supp } Q$.

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \left( \int_{A_0(\theta)} \frac{L_z(\theta) + \bar{K}_{Q,z}(\lambda)}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right) $$
$$ = \int \mathbf{L}_z(\boldsymbol{\theta}) d\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) - \lambda \int \left( \frac{d\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}}{dQ}(\boldsymbol{\theta}) \right)^{-1} d\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \\ + \int \bar{K}_{Q,z}(\lambda) d\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \qquad (181b) $$

$$ = \mathbf{R}_z \left( \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)} \right) - \lambda \int dQ(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda) \qquad (181c) $$

$$ = \mathbf{R}_z \left( \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)} \right) - \lambda + \bar{K}_{Q,z}(\lambda). \qquad (181d) $$

From (181d), it holds that

$$ \mathbf{R}_z \left( \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)} \right) = \lambda - \bar{K}_{Q,z}(\lambda), \qquad (182) $$

which completes the proof.

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

## L Proof of Lemma 5.2

*Proof:* The proof is divided into four parts. The first part characterizes the functional inverse of the function $\bar{K}_{Q,z}$ in (23b). The second part provides necessary conditions for the differentiation lemma [48, Theorem 6.28, page 160] to hold, which is used in the third and fourth parts of the proof. The third part presents the first derivative of the functional inverse and shows that its derivative is strictly positive. The fourth part shows the expected empirical risk $\mathbf{R}_z(\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)})$ decreases with lambdas decreasing.

The first part is as follows. Under the assumption that $t \in (0, \infty)$ and $\gamma \in \mathbb{R}$ satisfy that

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

$$ = \int \frac{t}{\mathbf{L}_z(\boldsymbol{\theta}) + \gamma} dQ(\boldsymbol{\theta}), \qquad (183b) $$

which implies that

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

where $\bar{K}_{Q,z}$ is defined in (23b). From Lemma 4.4, let the functional $\bar{K}_{Q,z}^{-1}$: $(-\delta_{Q,z}^*, \infty) \to (0, \infty)$ be the functional inverse of $\bar{K}_{Q,z}$ in (23b) given by

$$ \bar{K}_{Q,z}^{-1}(\beta) = \frac{1}{\int \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \beta} dQ(\boldsymbol{\theta})}, \qquad (185) $$

which follows from the constraint in (15b) and completes the first part of the proof.
$$ 
\begin{aligned}
&+ \int_{A_1(\theta)} \frac{L_z(\theta) + \bar{K}_{Q,z}(\lambda)}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \\
&+ \left( \int_{A_2(\theta)} \frac{L_z(\theta) + \bar{K}_{Q,z}(\lambda)}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1} && (182a) \\
&= \left( Q(A_0(\theta)) + \int_{A_1(\theta)} \frac{L_z(\theta) + \bar{K}_{Q,z}(\lambda)}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right. \\
&\qquad \left. + \int_{A_2(\theta)} \frac{L_z(\theta) + \bar{K}_{Q,z}(\lambda)}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) \right)^{-1}. && (182b)
\end{aligned}
$$

Consider the following partition of the supp $Q$:

$$ \{ \nu \in \text{supp } Q : L_z(\nu) = \delta_{Q,z}^* \}, \quad (183a) $$

$$ \{ \nu \in \text{supp } Q : L_z(\nu) > \delta_{Q,z}^* \}, \text{ and} \quad (183b) $$

$$ \{ \nu \in \text{supp } Q : L_z(\nu) < \delta_{Q,z}^* \}, \quad (183c) $$

with $\delta_{Q,z}^*$ in (28). The proof is divided into two cases. The first case follows under the assumption that

$$ \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) = \infty; \quad (184) $$

and the second case follows under the assumption that

$$ \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) < \infty. \quad (185) $$

From Lemma 4.2, it follows that in Case 1, the set $A_{Q,z}$ in (23) is $(0, \infty)$. Similarly, in Case 2, the set $A_{Q,z}$ is $[\lambda_{Q,z}^*, \infty)$. Hence, Case 1 considers the limit $\lambda \to 0^+$, which comprehends the equalities (39) and (40). Case 2 considers the limit $\lambda \to \lambda_{Q,z}^+$, which comprehends the equality (41).

## J.1 Case 1

This case is divided into three parts. The first part evaluates $\lim_{\lambda \to 0^+} \frac{d\bar{P}_{(Q,\lambda)}(\theta)}{dQ}$, with $\theta \in \{\nu \in \text{supp } Q : L_z(\nu) = \delta_{Q,z}^*\}$. The second part considers the case in which $\theta \in \{\nu \in \text{supp } Q : L_z(\nu) > \delta_{Q,z}^*\}$. The third part considers the remaining case in (183).

### J.1.1 Part 1

The first part is as follows. Consider that $\theta \in \{\nu \in \text{supp } Q : L_z(\nu) = \delta_{Q,z}^*\}$ and note that

$$ \{ \nu \in \text{supp } Q : L_z(\nu) = \delta_{Q,z}^* \} = \mathcal{L}_{Q,z}^*, \quad (186) $$
The second part is as follows. From Lemma 4.4, for all $\lambda \in (0, \infty)$, it holds that

$$ \bar{K}_{Q,z}(\lambda) > -\delta_{Q,z}^* \qquad (186) $$

Then, for the third case, if $\gamma > -\delta_{Q,z}^*$, it follows that

$$ \int \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \gamma} dQ(\boldsymbol{\theta}) \le \int \frac{1}{\delta_{Q,z}^* + \gamma} dQ(\boldsymbol{\theta}) \qquad (187\text{a}) $$

$$ = \frac{1}{\delta_{Q,z}^* + \gamma} \qquad (187\text{b}) $$

From the equality in (187b) and the fact that $Q$ is a probability measure, it follows that the integral on the right-hand side in (187a) is bounded. Hence, from the dominated convergence theorem [45, Theorem 1.6.9, page 50] the left-hand side of (187a) is finite for all $\beta \in (-\delta_{Q,z}^*, \infty)$. Furthermore, for all $\boldsymbol{\theta} \in \mathcal{M}$ the partial derivative of $\frac{1}{\mathbf{L}_z(\boldsymbol{\theta})+\beta}$ in (187a) with respect to $\beta$ yields

$$ \frac{\partial}{\partial \beta} \left( \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \beta} \right) = - \frac{1}{(\beta + \mathbf{L}_z(\boldsymbol{\theta}))^2}, \qquad (188) $$

which exists for all $\beta \in (-\delta^*, \infty)$. Then, from the differentiation lemma [48, Theorem 6.28, page 160], the interchange of the integral with the derivative on the right-hand side of (187a) is possible. Hence,

$$ \frac{d}{d\beta} \int \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \beta} dQ(\boldsymbol{\theta}) = \int \frac{\partial}{\partial \beta} \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \beta} dQ(\boldsymbol{\theta}), \qquad (189) $$

which completes the second part of the proof.

The third part is as follows.

For all $\beta \in (-\delta_{Q,z}^*, \infty)$, the derivative of the function $\bar{K}_{Q,z}^{-1}$ in (185) satisfies:

$$ \bar{K}_{Q,z}^{-1(1)}(\beta) = \frac{d}{d\beta} \left( \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \right)^{-1} \qquad (190\text{a}) $$

$$ = - \left( \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \right)^{-2} \frac{d}{d\beta} \left( \bar{K}_{Q,z}^{-1}(\beta) \right)^{-1} \qquad (190\text{b}) $$

$$ = - \left( \frac{1}{\int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta})} \right)^2 \frac{d}{d\beta} \left( \bar{K}_{Q,z}^{-1}(\beta) \right)^{-1} \qquad (190\text{c}) $$

$$ = - \frac{\frac{d}{d\beta} \left( \bar{K}_{Q,z}^{-1}(\beta) \right)^{-1}}{\left( \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \right)^2} \qquad (190\text{d}) $$

$$ = - \frac{\int - \frac{1}{(\beta + \mathbf{L}_z(\boldsymbol{\theta}))^2} dQ(\boldsymbol{\theta})}{\left( \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \right)^2} \qquad (190\text{e}) $$
with $\mathcal{L}_{Q,z}^*$ defined in (30). Hence, the sets $\mathcal{A}_0(\theta)$, $\mathcal{A}_1(\theta)$, and $\mathcal{A}_2(\theta)$ in (181) satisfy the following:

$$ \mathcal{A}_0(\theta) = \mathcal{L}_{Q,z}^*, \qquad (187a) $$

$$ \mathcal{A}_1(\theta) = \{ \boldsymbol{\mu} \in \text{supp } Q : \mathbf{L}_z(\boldsymbol{\mu}) > \delta_{Q,z}^* \}, \quad \text{and} \qquad (187b) $$

$$ \mathcal{A}_2(\theta) = \{ \boldsymbol{\mu} \in \text{supp } Q : \mathbf{L}_z(\boldsymbol{\mu}) < \delta_{Q,z}^* \}. \qquad (187c) $$

From the definition of $\delta_{Q,z}^*$ in (28), it follows that $Q(\mathcal{A}_2(\theta)) = 0$. Substituting the equalities in (187) in (182) yields for all $\theta \in \{\boldsymbol{\nu} \in \text{supp } Q : \mathbf{L}_z(\boldsymbol{\nu}) = \delta_{Q,z}^*\}$,

$$ \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \left( Q(\mathcal{L}_{Q,z}^*) + \int_{\mathcal{A}_1(\theta)} \frac{\mathbf{L}_z(\theta) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right)^{-1}, \qquad (188) $$

which implies that for all $\theta \in \{\boldsymbol{\nu} \in \text{supp } Q : \mathbf{L}_z(\boldsymbol{\nu}) = \delta_{Q,z}^*\}$,

$$ \lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \left( Q(\mathcal{L}_{Q,z}^*) + \lim_{\lambda \to 0^+} \int_{\mathcal{A}_1(\theta)} \frac{\mathbf{L}_z(\theta) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right)^{-1} \qquad (189) $$

$$ = \begin{cases} \infty & \text{if } Q(\mathcal{L}_{Q,z}^*) = 0 \\ \frac{1}{Q(\mathcal{L}_{Q,z}^*)} & \text{otherwise} \end{cases}, \qquad (190) $$

where (190) follows from verifying that the dominated convergence theorem [54, Theorem 2.6.9] holds. That is,

(a) For all $\boldsymbol{\nu} \in \mathcal{A}_1(\theta)$, it holds that $\frac{\mathbf{L}_z(\theta) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} \le \frac{\lambda}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)}$.

(b) For all $\boldsymbol{\nu} \in \mathcal{A}_1(\theta)$, it holds that

$$ \lim_{\lambda \to 0^+} \frac{\mathbf{L}_z(\theta) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} = \lim_{\lambda \to 0^+} \frac{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} \qquad (191a) $$

$$ = \left( \delta_{Q,z}^* + \lim_{\lambda \to 0^+} \bar{K}_{Q,z}(\lambda) \right) \lim_{\lambda \to 0^+} \frac{1}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} \qquad (191b) $$

$$ = 0, \qquad (191c) $$

where (191b) follows from observing that for all $\boldsymbol{\nu} \in \mathcal{A}_1(\theta)$, it holds that $\lim_{\lambda \to 0^+} \mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda) \ne 0$ and [57, Theorem 4.4]; and (191c) follows from Lemma 4.6. This completes the first part of Case 1.

### J.1.2 Part 2

For all $\delta > \delta_{Q,z}^*$ and for all $\theta \in \{\boldsymbol{\nu} \in \text{supp } Q : \mathbf{L}_z(\boldsymbol{\nu}) = \delta\}$, the sets $\mathcal{A}_0(\theta)$, $\mathcal{A}_1(\theta)$, and $\mathcal{A}_2(\theta)$ in (181) satisfy the following:

$$ \mathcal{A}_0(\theta) = \{ \boldsymbol{\mu} \in \text{supp } Q : \mathbf{L}_z(\boldsymbol{\mu}) = \delta \}, \qquad (192a) $$

$$ \mathcal{A}_1(\theta) = \{ \boldsymbol{\mu} \in \text{supp } Q : \mathbf{L}_z(\boldsymbol{\mu}) > \delta \}, \quad \text{and} \qquad (192b) $$

$$ \mathcal{A}_2(\theta) = \{ \boldsymbol{\mu} \in \text{supp } Q : \mathbf{L}_z(\boldsymbol{\mu}) < \delta \}. \qquad (192c) $$
$$ = \frac{\int \frac{1}{(\beta + \mathbf{L}_z(\boldsymbol{\theta}))^2} dQ(\boldsymbol{\theta})}{\left(\int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta})\right)^2}. \qquad (190f) $$

where the equality in (190b) follows from (189); and the equality in (190d) follows from (188).

Note that from Jensen's inequality, it follows that

$$ \left( \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \right)^2 \le \int \frac{1}{(\beta + \mathbf{L}_z(\boldsymbol{\theta}))^2} dQ(\boldsymbol{\theta}). \qquad (191) $$

Then, from (190f) and (191), for all $\beta \in (\delta_{Q,z}^*, \infty)$ it holds that

$$ \bar{K}_{Q,z}^{-1(1)}(\beta) \ge 1. \qquad (192) $$

which completes the third part of the proof.

The fourth part is as follows. Let the real values $(\lambda_1, \lambda_2) \in (0, \infty)^2$ be such that $\lambda_2 > \lambda_1$, which implies from Lemma 4.4 that $\bar{K}_{Q,z}(\lambda_2) > \bar{K}_{Q,z}(\lambda_1)$. Then, from Lemma 5.1 it follows that

$$ \begin{aligned} \mathrm{R}_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda_2)}) - \mathrm{R}_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda_1)}) &= \lambda_2 - \lambda_1 + \bar{K}_{Q,z}(\lambda_1) - \bar{K}_{Q,z}(\lambda_2) \quad (193\mathrm{a}) \\ &= \bar{K}_{Q,z}^{-1}(\beta_2) - \bar{K}_{Q,z}^{-1}(\beta_1) + \beta_1 - \beta_2, \quad (193\mathrm{b}) \end{aligned} $$

where equality (193b) follows from substituting (185) into (193a). Note that (192) implies that

$$ \bar{K}_{Q,z}^{-1}(\beta_2) - \bar{K}_{Q,z}^{-1}(\beta_1) \ge \beta_2 - \beta_1. \qquad (194) $$

Thus, from (193b) and (194) it follows that

$$ \mathrm{R}_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda_2)}) - \mathrm{R}_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda_1)}) \ge 0, \qquad (195) $$

Furthermore, from Lemma 4.4 and $\mathbf{L}_z$ in (3), for all $\boldsymbol{\theta} \in \mathrm{supp} Q$ the fraction $(\beta + \mathbf{L}_z(\boldsymbol{\theta}))^{-1}$ is strictly convex. Hence, equality in (192) and in (195) holds if and only if $\mathbf{L}_z$ is nonseparable with respect to $Q$, which completes the proof.

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

# M Proof of Lemma 5.3

*Proof:* From Theorem 4.1 and the definition of the Type-II relative entropy, it holds that

$$ \mathrm{D}\left(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}\right) = \int \log \left( \frac{dQ}{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}} \right) dQ(\boldsymbol{\theta}) \qquad (196\mathrm{a}) $$
Consider the sets

$$ \mathcal{A}_{2,1}(\boldsymbol{\theta}) = \{\boldsymbol{\mu} \in \mathcal{A}_2(\boldsymbol{\theta}) : \mathbf{L}_z(\boldsymbol{\mu}) < \delta_{Q,z}^*\}, \text{ and} \quad (193a) $$

$$ \mathcal{A}_{2,2}(\boldsymbol{\theta}) = \{\boldsymbol{\mu} \in \mathcal{A}_2(\boldsymbol{\theta}) : \delta_{Q,z}^* \le \mathbf{L}_z(\boldsymbol{\mu}) < \delta\}, \quad (193b) $$

and note that $\mathcal{A}_{2,1}(\boldsymbol{\theta})$ and $\mathcal{A}_{2,2}(\boldsymbol{\theta})$ form a partition of $\mathcal{A}_2(\boldsymbol{\theta})$. Moreover, from the definition of $\delta_{Q,z}^*$ in (28), it holds that

$$ Q(\mathcal{A}_{2,1}(\boldsymbol{\theta})) = 0. \quad (194) $$

Hence, substituting the equalities in (192) and (194) in (182) yields,

$$ \lim_{\lambda \to 0^+} \frac{d\bar{P}^{(Q,\lambda)}_{\boldsymbol{\Theta}|\mathbf{Z}=\mathbf{z}}(\boldsymbol{\theta})}{dQ} = \left( Q(\mathcal{A}_0(\boldsymbol{\theta})) + \lim_{\lambda \to 0^+} \int_{\mathcal{A}_1(\boldsymbol{\theta})} \frac{\mathbf{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right. \\ \left. + \lim_{\lambda \to 0^+} \int_{\mathcal{A}_2(\boldsymbol{\theta})} \frac{\mathbf{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right)^{-1} \quad (195a) $$

$$ = \left( Q(\mathcal{A}_0(\boldsymbol{\theta})) + \lim_{\lambda \to 0^+} \int_{\mathcal{A}_1(\boldsymbol{\theta})} \frac{\mathbf{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right. \\ \left. + \lim_{\lambda \to 0^+} \int_{\mathcal{A}_{2,2}(\boldsymbol{\theta})} \frac{\mathbf{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right)^{-1} \quad (195b) $$

$$ = \left( Q(\mathcal{A}_0(\boldsymbol{\theta})) + \int_{\mathcal{A}_1(\boldsymbol{\theta})} \lim_{\lambda \to 0^+} \frac{\mathbf{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right. \\ \left. + \int_{\mathcal{A}_{2,2}(\boldsymbol{\theta})} \lim_{\lambda \to 0^+} \frac{\mathbf{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) \right)^{-1}, \quad (195c) $$

where (195c) follows by verifying that the dominated convergence theorem [54, Theorem 1.6.9] holds. That is,

(a) For all $\boldsymbol{\nu} \in \mathcal{A}_{2,2}(\boldsymbol{\theta})$, it holds that $\frac{\mathbf{L}_z(\boldsymbol{\theta})+\bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu})+\bar{K}_{Q,z}(\lambda)} \le \frac{\lambda}{\delta_{Q,z}^*+\bar{K}_{Q,z}(\lambda)} < \infty$; and

(b) For all $\boldsymbol{\nu} \in \mathcal{A}_{2,2}(\boldsymbol{\theta})$, it holds that

$$ \lim_{\lambda \to 0^+} \frac{\mathbf{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} = \lim_{\lambda \to 0^+} \frac{\delta + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} \quad (196a) $$

$$ = \left( \delta + \lim_{\lambda \to 0^+} \bar{K}_{Q,z}(\lambda) \right) \lim_{\lambda \to 0^+} \frac{1}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} \quad (196b) $$

$$ = (\delta - \delta_{Q,z}^*) \frac{1}{\mathbf{L}_z(\boldsymbol{\nu}) - \delta_{Q,z}^*}, \quad (196c) $$

where (196b) follows from observing that for all $\boldsymbol{\nu} \in \mathcal{A}_{2,2}(\boldsymbol{\theta})$, it holds that $\lim_{\lambda \to 0^+} \mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda) \ne 0$ and [57, Theorem 4.2]; and (196c) follows from Lemma 4.6. From (196c), it follows that

$$ \int_{\mathcal{A}_{2,2}(\boldsymbol{\theta})} \lim_{\lambda \to 0^+} \frac{\mathbf{L}_z(\boldsymbol{\theta}) + \bar{K}_{Q,z}(\lambda)}{\mathbf{L}_z(\boldsymbol{\nu}) + \bar{K}_{Q,z}(\lambda)} dQ(\boldsymbol{\nu}) $$
$$ \leq \log \left( \int \frac{dQ}{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) dQ(\boldsymbol{\theta}) \right) \quad (196b) $$

$$ = \log \left( \int \frac{\bar{K}_{Q,z}(\lambda) + L_z(\boldsymbol{\theta})}{\lambda} dQ(\boldsymbol{\theta}) \right) \quad (196c) $$

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

$$ = \log \left( \frac{1}{\lambda} (\bar{K}_{Q,z}(\lambda) + R_z(Q)) \right), \quad (196e) $$

where inequality (196b) follows from Jensen's Inequality. From (196e), it follows that

$$ R_z(Q) \geq \exp\left(D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)})\right) \lambda - \bar{K}_{Q,z}(\lambda). \quad (196f) $$

Hence, the difference between the expected empirical risk of the probability measures $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$, from Lemma 5.1 and (196f), satisfies that

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

which completes the proof. ■

## N Proof of Lemma 5.5

*Proof:* From Lemma 4.4 and Lemma 5.1, it holds that

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

Similarly, from the definition of the Rashmon set in (27) and $\delta_{Q,z}^*$ in (28), it follows that

$$ R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \geq \delta_{Q,z}^*. \quad (199) $$

The proof continues by determining the conditions for which the equality in (199) holds. Assume the empirical risk $L_z$ in (3) is separable with respect to the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) (see Definition 4.1). Then, there exists a real value $\epsilon > 0$ and two nonnegligible sets $A$ and $B$ with respect to the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16), such that

$$ A = \{ \boldsymbol{\theta} \in \mathcal{M} : L_z(\boldsymbol{\theta}) < \delta_{Q,z}^* + \epsilon \}, \text{ and} \quad (200a) $$

$$ B = \{ \boldsymbol{\theta} \in \mathcal{M} : L_z(\boldsymbol{\theta}) \geq \delta_{Q,z}^* + \epsilon \}. \quad (200b) $$

Under the assumption that $L_z$ is separable, the expected empirical risk satisfies

$$ R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = \int_A L_z(\boldsymbol{\theta}) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\boldsymbol{\theta}) $$
$$ = (\delta - \delta_{Q,z}^*) \int_{A_{2,2}(\theta)} \frac{1}{L_z(\nu) - \delta_{Q,z}^*} dQ(\nu). \quad (197) $$

Moreover, from the fact that

$$ Q(A_0(\theta)) \le 1, \quad (198) $$

and the fact that

$$ \int_{A_1(\theta)} \lim_{\lambda \to 0^+} \frac{L_z(\theta) + \bar{K}_{Q,z}(\lambda)}{L_z(\nu) + \bar{K}_{Q,z}(\lambda)} dQ(\nu) = \int_{A_1(\theta)} \frac{\delta - \delta_{Q,z}^*}{L_z(\nu) - \delta_{Q,z}^*} dQ(\nu) \quad (199) $$

$$ < \int_{A_1(\theta)} \frac{\delta - \delta_{Q,z}^*}{\delta - \delta_{Q,z}^*} dQ(\nu) \quad (200) $$

$$ = Q(A_1(\theta)) \quad (201) $$

$$ \le 1, \quad (202) $$

the following holds from Lemma 4.2 under the assumptions of Case 1:

$$ \infty = (\delta - \delta_{Q,z}^*) \int \frac{1}{L_z(\nu) - \delta_{Q,z}^*} dQ(\nu) \quad (203) $$

$$ = (\delta - \delta_{Q,z}^*) \left( \int_{A_0(\theta)} \frac{1}{L_z(\nu) - \delta_{Q,z}^*} dQ(\nu) + \int_{A_1(\theta)} \frac{1}{L_z(\nu) - \delta_{Q,z}^*} dQ(\nu) + \int_{A_{2,2}(\theta)} \frac{1}{L_z(\nu) - \delta_{Q,z}^*} dQ(\nu) \right) \quad (204) $$

$$ = \left( Q(A_0(\theta)) + \int_{A_1(\theta)} \frac{\delta - \delta_{Q,z}^*}{L_z(\nu) - \delta_{Q,z}^*} dQ(\nu) + \int_{A_{2,2}(\theta)} \frac{\delta - \delta_{Q,z}^*}{L_z(\nu) - \delta_{Q,z}^*} dQ(\nu) \right). \quad (205) $$

From (198), (202), and (205), it follows that

$$ (\delta - \delta_{Q,z}^*) \int_{A_{2,2}(\theta)} \frac{1}{L_z(\nu) - \delta_{Q,z}^*} dQ(\nu) = \infty. \quad (206) $$

Finally, from (195c), (197), and (206), for all $\theta \in \{\nu \in \text{supp } Q : L_z(\nu) > \delta_{Q,z}^*\}$,

$$ \lim_{\lambda \to 0^+} \frac{d\bar{P}^{(Q,\lambda)}_{\Theta|Z=z}(\theta)}{dQ} = 0. \quad (207) $$

This completes the second part of Case 1.
$$ + \int_{\mathcal{B}} \mathbf{L}_z(\boldsymbol{\theta}) \, d\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \quad (201a) $$

$$ \begin{aligned} & \ge \int_{\mathcal{A}} \delta_{Q,z}^{*} d\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \\ & + \int_{\mathcal{B}} (\delta_{Q,z}^{*} + \epsilon) d\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\boldsymbol{\theta}) \end{aligned} \quad (201b) $$

$$ \begin{aligned} & = \delta_{Q,z}^{*} \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\mathcal{A}) \\ & + (\delta_{Q,z}^{*} + \epsilon) \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\mathcal{B}), \end{aligned} \quad (201c) $$

$$ \begin{aligned} & = \delta_{Q,z}^{*} \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\mathcal{A}) \\ & (\delta_{Q,z}^{*} + \epsilon) (1 - \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\mathcal{A})) \end{aligned} \quad (201d) $$

$$ = \delta_{Q,z}^{*} + \epsilon (1 - \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\mathcal{A})) \quad (201e) $$

$$ > \delta_{Q,z}^{*} \quad (201f) $$

where inequality (201b) follows from the fact that $\delta_{Q,z}^*$ and $(\delta_{Q,z}^* + \epsilon)$ are the minimum empirical risk for the set $\mathcal{A}$ and $\mathcal{B}$ respectively; and inequality (201f) follows from the fact that the sets $\mathcal{A}$ and $\mathcal{B}$ are nonnegligible with respect to the probability measure $\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}$, which implies $\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}(\mathcal{A}) < 1$. This proves that for separable empirical risk functions $\mathbf{L}_z$ the inequality in (199) is strict.

Considering the case in which the empirical risk $\mathbf{L}_z$ in (3) is not separable with respect to $\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}$ in (16). Then, for all $\boldsymbol{\theta} \in \text{supp } \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}$, the empirical risk satisfies $\mathbf{L}_z(\boldsymbol{\theta}) = \delta_{Q,z}^*$, which implies $\mathbf{R}_z(\bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\lambda)}) = \delta_{Q,z}^*$. Hence, equality in (199) holds for all nonseparable empirical risk functions $\mathbf{L}_z$, which completes the proof. ■

## O Proof of Theorem 6.1

*Proof:* Let $\delta$ be a real in $(\delta_{Q,z}^*, \infty)$, with $\delta_{Q,z}^*$ in (28). Let also $\gamma \in (0, \infty)$ satisfy the following equality:

$$ \mathbf{R}_z \left( \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)} \right) \le \delta. \quad (202) $$

Note that from Lemma 4.4 the function $\bar{K}_{Q,z}$ is continuous and from Lemma 4.4 the set $(0, \infty)$ is convex. Moreover, from Lemma 5.6, it follows that such $\gamma$ in (202) always exists. From (27), for all $\delta \in (\delta_{Q,z}^*, \infty)$, it holds that

$$ \mathcal{L}_z(\delta) \supseteq \mathcal{L}_{Q,z}^*, \quad (203) $$

and thus,

$$ \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\mathcal{L}_z(\delta)) \ge \bar{P}_{\boldsymbol{\Theta}|\mathbf{Z}=z}^{(Q,\gamma)}(\mathcal{L}_{Q,z}^*), \quad (204) $$
### J.1.3 Part 3

The third part of the proof follows by noticing that the set $\{\mu \in \text{supp } Q : L_z(\mu) < \delta_{Q,z}^*\}$ is a negligible set with respect to $Q$ and thus, for all $\theta \in \{\mu \in \text{supp } Q : L_z(\mu) < \delta_{Q,z}^*\}$, the value $\frac{d\bar{P}^{(Q,\lambda)}_{\Theta|Z=z}(\theta)}{dQ}(\theta)$ is immaterial. Hence, it is arbitrarily assumed that for all $\theta \in \{\mu \in \text{supp } Q : L_z(\mu) < \delta_{Q,z}^*\}$, it holds that

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

which implies that for all $\theta \in \{\mu \in \text{supp } Q : L_z(\mu) < \delta_{Q,z}^*\}$, it holds that

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

This completes the third part of Case 1.

Under the assumption that $Q(\mathcal{L}_{Q,z}^*) > 0$, from (190), (207), and (209), for all $\theta \in \text{supp } Q$, it follows that

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

which completes the proof of (39). Alternatively, under the assumption that $Q(\mathcal{L}_{Q,z}^*) = 0$, from (190), (207), and (209), for all $\theta \in \text{supp } Q$, it follows that

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

which completes the proof of (40).

## J.2 Case 2

Under the assumptions of Case 2, namely (185), it holds that

$$ Q(\mathcal{L}_{Q,z}^*) = 0. \qquad (212) $$

This can be proved by noticing that if $Q(\mathcal{L}_{Q,z}^*) > 0$, then

$$ \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) = \int_{\mathcal{L}_{Q,z}^*} \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) + \int_{\mathcal{L}_{Q,z}^*} \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) \qquad (213a) $$

$$ > \int_{\mathcal{L}_{Q,z}^*} \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) \qquad (213b) $$
with $\mathcal{L}_{Q,z}^*$ defined in (29). Let $\lambda$ be a positive real such that $\lambda \le \gamma$, and

$$ \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_z(\delta)) > 1 - \epsilon. \qquad (205) $$

The existence of such a positive real $\lambda$ that satisfies (205) follows from Lemma 4.13. From Theorem 4.1 and (203), it follows that

$$ \bar{P}_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{L}_z(\delta)) \ge \bar{P}_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{L}_{Q,z}^*) \qquad (206a) $$

Hence, from equality (206a) it holds that

$$ 1 - \epsilon < \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) \qquad (207) $$

$$ \le \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_z(\delta)). \qquad (208) $$

The equality in (208) implies that the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ is $(\delta, \epsilon)$-optimal (Definition 6.1), which completes the proof. ■

## P Proof of Lemma 7.1

*Proof:* From Theorem 4.1, it follows that for all $\theta \in \mathcal{M}$,

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

$$ = \log(\lambda) - \log(\bar{K}_{Q,z}(\lambda) + L_z(\theta)) \qquad (209b) $$

$$ = \log(\lambda) - V_{z,\lambda}(\theta), \qquad (209c) $$

where the function $V_{z,\lambda}$ is defined in (60). Thus,

$$ D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q) = \int \log \left( \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \qquad (210a) $$

$$ = \log(\lambda) - \int V_{z,\lambda}(\theta) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \qquad (210b) $$

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

where the functional $\bar{R}_{z,\lambda}$ is defined in (61). Hence, it follows from (210c) that

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

which completes the proof for (64).

From (209), it follows that

$$ D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = - \int \log \left( \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) dQ(\theta) \qquad (212a) $$
$$= \frac{1}{\delta_{Q,z}^{*} - \delta_{Q,z}^{*}} Q(\mathcal{L}_{Q,z}^{*}) \qquad (213c)$$

$$= \infty, \qquad (213d)$$

which contradicts (212).

The proof of Case 2 is divided into three parts. The first part evaluates $\lim_{\lambda \to \lambda_{Q,z}^*} + \frac{d\bar{P}^{(Q,\lambda)}_{\Theta|Z=z}(\theta)}{dQ}(\theta)$, with $\theta \in \{\nu \in \text{supp } Q : \mathcal{L}_z(\nu) = \delta_{Q,z}^*\}$. The second part considers the case in which $\theta \in \{\nu \in \text{supp } Q : \mathcal{L}_z(\nu) > \delta_{Q,z}^*\}$. The third part considers the remaining case in (183).

### J.2.1 Part 1

From (212) it holds that the set $\{\mu \in \text{supp } Q : \mathcal{L}_z(\mu) = \delta_{Q,z}^*\}$ is a negligible set with respect to $Q$ and thus, for all $\theta \in \{\mu \in \text{supp } Q : \mathcal{L}_z(\mu) = \delta_{Q,z}^*\}$, the value $\frac{d\bar{P}^{(Q,\lambda)}_{\Theta|Z=z}(\theta)}{dQ}(\theta)$ is immaterial.

### J.2.2 Part 2

For all $\theta \in \{\nu \in \text{supp } Q : \mathcal{L}_z(\nu) > \delta_{Q,z}^*\}$, it holds that

$$\lim_{\lambda \to \lambda_{Q,z}^*} + \frac{d\bar{P}^{(Q,\lambda)}_{\Theta|Z=z}(\theta)}{dQ}(\theta) = \lim_{\lambda \to \lambda_{Q,z}^*} + \frac{\lambda}{\mathcal{L}_z(\theta) + \bar{K}_{Q,z}(\lambda)} \qquad (214a)$$

$$= \frac{\lambda_{Q,z}^*}{\mathcal{L}_z(\theta) - \delta_{Q,z}^*}, \qquad (214b)$$

where (214b) follows from observing that $\lim_{\lambda \to \lambda_{Q,z}^*} + \mathcal{L}_z(\theta) + \bar{K}_{Q,z}(\lambda) = \mathcal{L}_z(\theta) - \delta_{Q,z}^* \neq 0$ (Lemma 4.6) and [57, Theorem 4.2].

### J.2.3 Part 3

The third part of the proof follows by noticing that the set $\{\mu \in \text{supp } Q : \mathcal{L}_z(\mu) < \delta_{Q,z}^*\}$ is a negligible set with respect to $Q$ and thus, for all $\theta \in \{\mu \in \text{supp } Q : \mathcal{L}_z(\mu) < \delta_{Q,z}^*\}$, the value $\frac{d\bar{P}^{(Q,\lambda)}_{\Theta|Z=z}(\theta)}{dQ}(\theta)$ is immaterial. Hence, it is arbitrarily assumed that

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

This completes the third part of Case 2.

From (214b), for all $\theta \in \text{supp } Q$, it follows that

$$\lim_{\lambda \to \lambda_{Q,z}^*} + \frac{d\bar{P}^{(Q,\lambda)}_{\Theta|Z=z}(\theta)}{dQ}(\theta) = \frac{\lambda_{Q,z}^*}{\mathcal{L}_z(\theta) - \delta_{Q,z}^*}, \qquad (216)$$

which completes the proof of (41). This completes the proof. ■
$$ = -\log(\lambda) + \int \nu_{z,\lambda}(\theta) dQ(\theta) \quad (212b) $$

$$ = -\log(\lambda) + \bar{\mathbb{R}}_{z,\lambda}(Q), \quad (212c) $$

Hence, it follows from (210c) that

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

which completes the proof for (65).

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

## Q Proof of Lemma 7.2

*Proof:* The proof uses the fact that the probability measure $\bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) is mutually absolutely continuous with the probability measure $Q$ in Theorem 4.1. Hence, the probability measure $P$ is mutually absolutely continuous with $\bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)}$, as a consequence of the assumption that $P \in \mathcal{O}_Q(\mathcal{M})$.

The proof follows by noticing that for all $\theta \in \mathcal{M}$,

$$ \log \left( \frac{dP}{d\bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \right) = \log \left( \frac{dP}{dQ}(\theta) \frac{dQ}{d\bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \right) \quad (214a) $$

$$ = \log \left( \frac{dP}{dQ}(\theta) \right) - \log \left( \frac{d\bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) \quad (214b) $$

$$ = \log \left( \frac{dP}{dQ}(\theta) \right) - \log \left( \frac{\lambda}{\bar{K}_{Q,z}(\lambda) + \mathbf{L}_z(\theta)} \right) \quad (214c) $$

$$ = \log \left( \frac{dP}{dQ}(\theta) \right) - \log(\lambda) + \log(\bar{K}_{Q,z}(\lambda) + \mathbf{L}_z(\theta)) \quad (214d) $$

$$ = \log \left( \frac{dP}{dQ}(\theta) \right) - \log(\lambda) + \nu_{z,\lambda}(\theta), \quad (214e) $$

where the functions $\mathbf{L}_z$, $\bar{K}_{Q,z}$ and $\nu_{z,\lambda}$ are defined in (3), (23b) and in (60), respectively; and the equality in (214c) follows from (16). Hence, the relative entropy $D(P \| \bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)})$ satisfies,

$$ \mathrm{D}\left(P \| \bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)}\right) = \int \log \left( \frac{dP}{d\bar{\mathbb{P}}_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \right) dP(\theta) \quad (215a) $$

$$ = \int \left( \log \left( \frac{dP}{dQ}(\theta) \right) - \log(\lambda) + \nu_{z,\lambda}(\theta) \right) dP(\theta) \quad (215b) $$

$$ = \int \log \left( \frac{dP}{dQ}(\theta) \right) dP(\theta) - \log(\lambda) $$
## K Proof of Lemma 5.5

The proof is divided into two cases. The first case follows under the assumption that

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

and the second case follows under the assumption that

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

with $\delta_{Q,z}^*$ in (28) and the function $L_z$ in (3). From Lemma 4.2, it follows that in Case 1, the set $A_{Q,z}$ in (23) is $(0, \infty)$. Similarly, in Case 2, the set $A_{Q,z}$ is $[\lambda_{Q,z}^*, \infty)$. Hence, Case 1 considers the limit $\lambda \to 0^+$, which comprehends the equality (42). Case 2 considers the limit $\lambda \to \lambda_{Q,z}^+$, which comprehends the equality (43).

### K.1 Case 1

The first case is as follows. Consider the following partition of the set $\mathcal{M}$ formed by the sets

$$ A_0 = \{ \theta \in \mathcal{M} : L_z(\theta) = \delta_{Q,z}^* \}, \qquad (219a) $$

$$ A_1 = \{ \theta \in \mathcal{M} : L_z(\theta) > \delta_{Q,z}^* \}, \text{ and} \qquad (219b) $$

$$ A_2 = \{ \theta \in \mathcal{M} : L_z(\theta) < \delta_{Q,z}^* \}. \qquad (219c) $$

Note that $A_0 = \mathcal{L}_{Q,z}^*$, with $\mathcal{L}_{Q,z}^*$ in (30). For all $\lambda \in (0, \infty)$, it holds that

$$ 1 = \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_1) + \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_2) \qquad (220a) $$

$$ = \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_1) \qquad (220b) $$

$$ = \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \int_{A_1} d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta), \qquad (220c) $$

where (220b) follows from the fact that $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_2) = 0$, which follows from the mutual absolute continuity of $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$ (Corollary 3.3). The above implies that

$$ \lim_{\lambda \to 0^+} \left( \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \int_{A_1} d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \right) = \lim_{\lambda \to 0^+} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \lim_{\lambda \to 0^+} \int_{A_1} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \qquad (221a) $$

$$ = \lim_{\lambda \to 0^+} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) + \int_{A_1} \lim_{\lambda \to 0^+} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \qquad (221b) $$
$$ + \int V_{z,\lambda}(\theta) dP(\theta) \qquad (215c) $$

$$ = D(P\|Q) - \log(\lambda) + \bar{R}_{z,\lambda}(P) \qquad (215d) $$

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

where equality (215b) follows from (214); and equality (215e) follows from Lemma 7.1. Thus, from (215), it follows that

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

which completes the proof.

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

## R Proof of Lemma 7.4

*Proof:* The proof is presented in two parts. First, the sensitivity $S_{Q,\lambda}$ ([49, Definition 3.1 page 9]) is evaluated with respect to the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16). Second, the log sensitive defined $\bar{S}_{Q,\lambda}$ in (67) is evaluated with respect to the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ in (9).

For the first part, from Lemma 7.1, for all $\alpha \in (0, \infty)$, it holds that

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

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

Similarly, from [49, Lemma 2.2, page 8], for all $\lambda \in (0, \infty)$, it holds that

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

with the functional $R_z$ defined in (6).

From [49, Theorem 3.1 page 9] the sensitivity of the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\alpha)}$ satisfies

$$ S_{Q,\lambda}(z, \bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) = R_z(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) - R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) \qquad (219a) $$

$$ = \lambda \left( D(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)} \| P_{\Theta|Z=z}^{(Q,\lambda)}) - D(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)} \| Q) + D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \right). \qquad (219b) $$

Plugging (217) and (218) into (219) yields

$$ \frac{1}{\lambda} R_z(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) - \bar{R}_{z,\alpha}(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) $$
$$= \lim_{\lambda \to 0^+} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0), \qquad (221c)$$

$$= 1, \qquad (221d)$$

where, (221b) follows from Lemma 5.2 and the dominated convergence theorem [54, Theorem 1.6.9 page 50]; and (221c) follows from Lemma 5.4. Hence, it holds that

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

which completes the proof of (42).

## K.2 Case 2

Under the assumptions of Case 2, namely (218), it holds that

$$Q(\mathcal{L}_{Q,z}^*) = 0, \qquad (223)$$

which can be shown using the arguments in (213). Hence, the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ satisfies

$$\lim_{\lambda \to \lambda_{Q,z}^*} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A_0) = \lim_{\lambda \to \lambda_{Q,z}^*} \int_{A_0} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \qquad (224a)$$

$$= \lim_{\lambda \to \lambda_{Q,z}^*} \int_{A_0} \frac{\lambda}{L_z(\theta) + \bar{K}_{Q,z}(\lambda)} dQ(\theta) \qquad (224b)$$

$$= \lim_{\lambda \to \lambda_{Q,z}^*} \int_{A_0} \frac{\lambda}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} dQ(\theta) \qquad (224c)$$

$$= \lim_{\lambda \to \lambda_{Q,z}^*} \frac{\lambda}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} Q(A_0) \qquad (224d)$$

$$= \lim_{\lambda \to \lambda_{Q,z}^*} \frac{\lambda}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} Q(\mathcal{L}_{Q,z}^*) \qquad (224e)$$

$$= \lim_{\lambda \to \lambda_{Q,z}^*} \frac{\lambda}{\delta_{Q,z}^* + \bar{K}_{Q,z}(\lambda)} 0 \qquad (224f)$$

$$= 0, \qquad (224g)$$

which completes the proof of (43). This completes the proof. ■

## L Proof of Lemma 6.1

From Lemma 3.1 and Corollary 3.3, it holds that for all $\theta \in \text{supp } Q$,

$$\frac{dQ}{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) = \left( \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right)^{-1} \qquad (225)$$
$$= D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| P_{\Theta|Z=z}^{(Q,\lambda)} ) - \log(\alpha) - K_{Q,z} \left(-\frac{1}{\lambda}\right), \quad (220)$$

which completes the first part of the proof.

For the second part, from Lemma 7.1, for all $\alpha \in (0, \infty)$, it holds that

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

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

Similarly, from [49, Lemma 2.2, page 8], for all $\lambda \in (0, \infty)$, it holds that

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

with the functional $R_z$ defined in (6).

From Lemma 7.2 the logarithmic sensitivity of the probability measure $P_{\Theta|Z=z}^{(Q,\lambda)}$ is

$$\begin{aligned} \bar{R}_{z,\alpha}(P_{\Theta|Z=z}^{(Q,\lambda)}) - \bar{R}_{z,\alpha}(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) \\ = D(P_{\Theta|Z=z}^{(Q,\lambda)} \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) - D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) + D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q). \end{aligned} \quad (223)$$

Plugging (221) and (222) into (223) yields

$$\begin{aligned} \frac{1}{\lambda} R_z(P_{\Theta|Z=z}^{(Q,\lambda)}) - \bar{R}_{z,\alpha}(P_{\Theta|Z=z}^{(Q,\lambda)}) \\ = -D(P_{\Theta|Z=z}^{(Q,\lambda)} \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) - \left(\log(\alpha) + K_{Q,z} \left(-\frac{1}{\lambda}\right)\right). \end{aligned} \quad (224)$$

The proof proceeds by subtracting (224) from (220), resulting in

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

where the functions $S_{Q,\lambda}$ and $\bar{S}_{Q,\alpha}$ are respectively defined in [49, Definition 8] and (67). From [34, Theorem 1] and Lemma 7.4, it follows that

$$\begin{aligned} \frac{1}{\lambda} S_{Q,\lambda}(z, \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) - \bar{S}_{Q,\alpha}(z, P_{\Theta|Z=z}^{(Q,\lambda)}) \\ = 2 \left( D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) - D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q) \right) + D(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)} \| P_{\Theta|Z=z}^{(Q,\lambda)}) \\ - D(P_{\Theta|Z=z}^{(Q,\lambda)} \| \bar{P}_{\Theta|Z=z}^{(Q,\alpha)}). \end{aligned} \quad (226)$$

Substituting (226) into (225) yields

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

which completes the proof.

<figure><img src="image_21.png" /></figure>
$$ = \frac{\bar{K}_{Q,z}(\lambda) + L_z(\theta)}{\lambda}, \qquad (226) $$

where the functions $L_z$ and $\bar{K}_{Q,z}$ are in (3) and (23b), respectively. From (226), it follows that for all $\theta \in \text{supp } Q$,

$$ 0 = \lambda \frac{\mathrm{d}Q}{\mathrm{d}\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) - L_z(\theta) - \bar{K}_{Q,z}(\lambda). \qquad (227) $$

Integrating both sides of (227) with respect to the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ yields

$$ 0 = \int \left( L_z(\theta) - \lambda \left( \frac{\mathrm{d}\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) \right)^{-1} + \bar{K}_{Q,z}(\lambda) \right) \mathrm{d}\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (228a) $$

$$ = \int L_z(\theta) \mathrm{d}\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) - \lambda \int \left( \frac{\mathrm{d}\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{\mathrm{d}Q}(\theta) \right)^{-1} \mathrm{d}\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \\ + \int \bar{K}_{Q,z}(\lambda) \mathrm{d}\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \qquad (228b) $$

$$ = \mathrm{R}_z \left( \bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \right) - \lambda \int \mathrm{d}Q(\theta) + \bar{K}_{Q,z}(\lambda) \qquad (228c) $$

$$ = \mathrm{R}_z \left( \bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \right) - \lambda + \bar{K}_{Q,z}(\lambda). \qquad (228d) $$

From (228d), it holds that

$$ \mathrm{R}_z \left( \bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \right) = \lambda - \bar{K}_{Q,z}(\lambda), \qquad (229) $$

which completes the proof.

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

## M Proof of Lemma 6.2

The proof of continuity is immediate from Lemma 4.1 and Lemma 6.1. The proof of monotonicity is divided into two parts. The first part presents the first derivative of the functional inverse $\bar{K}_{Q,z}^{-1}$ in (26) and shows that its derivative is strictly positive. The second part shows the expected empirical risk $\mathrm{R}_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ is decreasing with $\lambda$.

The first part is as follows. For all $\theta \in \mathcal{M}$, the partial derivative of $\frac{1}{L_z(\theta)+\beta}$, with respect to $\beta \in (-\delta_{Q,z}^*, \infty)$, with $\delta_{Q,z}^*$ in (28), is

$$ \frac{\partial}{\partial \beta} \left( \frac{1}{L_z(\theta) + \beta} \right) = - \frac{1}{(\beta + L_z(\theta))^2}. \qquad (230) $$
S Example 4.3

*Proof.* The Lagrangian multiplier $\beta$ for the optimization problem in (11) satisfies

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

From the empirical risk function $\mathbf{L}_z : \mathcal{M} \to \mathbb{R}_0^+$ in (41), which is a simple function, and the probability measure $Q$ in (40a), it holds that

$$ \int \frac{\lambda}{\beta + \mathbf{L}_z(\boldsymbol{\nu})} dQ(\boldsymbol{\nu}) = \lambda \left( \frac{1}{\beta + c_0} Q(\mathcal{T}(z)) + \frac{1}{\beta + c_1} Q(\mathcal{M} \setminus \mathcal{T}(z)) \right) \quad (229a) $$

$$ = \lambda \left( \frac{1}{\beta + c_0} Q(\mathcal{T}(z)) + \frac{1}{\beta + c_1} (1 - Q(\mathcal{T}(z))) \right) \quad (229b) $$

$$ = \lambda \left( \frac{(\beta + c_1)Q(\mathcal{T}(z)) + (\beta + c_0)(1 - Q(\mathcal{T}(z)))}{\beta^2 + \beta(c_0 + c_1) + c_0c_1} \right) \quad (229c) $$

$$ = \lambda \left( \frac{(c_1 - c_0)Q(\mathcal{T}(z)) + \beta + c_0}{\beta^2 + \beta(c_0 + c_1) + c_0c_1} \right). \quad (229d) $$

From (228) and (229d), it follows that

$$ 0 = \beta^2 + \beta(c_0 + c_1) + c_0c_1 - \lambda((c_1 - c_0)Q(\mathcal{T}(z)) + \beta + c_0) \quad (230a) $$

$$ = \beta^2 + \beta(c_0 + c_1 - \lambda) + c_0c_1 - \lambda c_0 - \lambda(c_1 - c_0)Q(\mathcal{T}(z)). \quad (230b) $$

From (230b) and the fact that $c_0 = 0$ in equation (41), it holds that

$$ 0 = \beta^2 + \beta(c_1 - \lambda) - \lambda c_1 Q(\mathcal{T}(z)). \quad (230c) $$

Observe that the equality in (230c) is a quadratic polynomial that has two roots $r_1$ and $r_2$. Hence, (230c) in terms of $r_1$ and $r_2$ satisfies

$$ 0 = \beta^2 - (r_1 + r_2)\beta + r_1 r_2 \quad (231a) $$

$$ = (\beta - r_1)(\beta - r_2), \quad (231b) $$

where the roots $r_1$ and $r_2$ are given by the quadratic formula such that

$$ r_1 = - \frac{(c_1 - \lambda)}{2} - \sqrt{\left(\frac{c_1 - \lambda}{2}\right)^2 + \lambda c_1 Q(\mathcal{T}(z))}, \quad (232a) $$

and

$$ r_2 = - \frac{(c_1 - \lambda)}{2} + \sqrt{\left(\frac{c_1 - \lambda}{2}\right)^2 + \lambda c_1 Q(\mathcal{T}(z))}. \quad (232b) $$

The proof continues by verifying that the roots in (232a) and (232b) are real and there is only one positive root for all $\lambda \in (0, +\infty)$ and for all $Q(\mathcal{T}(z)) \in [0, 1)$.
From [58, Theorem 6.28, page 160], the following holds

$$ \frac{d}{d\beta} \int \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \beta} dQ(\boldsymbol{\theta}) = \int \frac{\partial}{\partial\beta} \frac{1}{\mathbf{L}_z(\boldsymbol{\theta}) + \beta} dQ(\boldsymbol{\theta}) \quad (231) $$

$$ = - \int \frac{1}{(\beta + \mathbf{L}_z(\boldsymbol{\theta}))^2} dQ(\boldsymbol{\theta}). \quad (232) $$

From Lemma 4.1, the derivative of the function $\bar{K}_{Q,z}^{-1}$ in (26) satisfies:

$$ \frac{d}{d\beta} \bar{K}_{Q,z}^{-1}(\beta) = \frac{d}{d\beta} \left( \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \right)^{-1} \quad (233a) $$

$$ = - \left( \frac{1}{\int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta})} \right)^2 \frac{d}{d\beta} \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \quad (233b) $$

$$ = - \frac{\int - \frac{1}{(\beta + \mathbf{L}_z(\boldsymbol{\theta}))^2} dQ(\boldsymbol{\theta})}{\left( \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \right)^2} \quad (233c) $$

$$ = \frac{\int \frac{1}{(\beta + \mathbf{L}_z(\boldsymbol{\theta}))^2} dQ(\boldsymbol{\theta})}{\left( \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \right)^2}, \quad (233d) $$

where (233c) follows from (232).

Jensen's inequality [59, Theorem 2.6.2] leads to the following inequality:

$$ \left( \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \right)^2 \le \int \frac{1}{(\beta + \mathbf{L}_z(\boldsymbol{\theta}))^2} dQ(\boldsymbol{\theta}), \quad (234) $$

with equality if and only if the function $\mathbf{L}_z$ in (3) is nonseparable (Definition 2.2). Then, from (233d) and (234), for all $\beta \in (-\delta_{Q,z}^*, \infty)$, it holds that

$$ \frac{d}{d\beta} \bar{K}_{Q,z}^{-1}(\beta) = \frac{\int \frac{1}{(\beta + \mathbf{L}_z(\boldsymbol{\theta}))^2} dQ(\boldsymbol{\theta})}{\left( \int \frac{1}{\beta + \mathbf{L}_z(\boldsymbol{\theta})} dQ(\boldsymbol{\theta}) \right)^2} \quad (235) $$

$$ \ge 1. \quad (236) $$

This completes the first part of the proof.

The second part is as follows. Consider the pairs $(\lambda_1, \beta_1) \in \mathcal{A}_{Q,z} \times \mathcal{C}_{Q,z}$ and $(\lambda_2, \beta_2) \in \mathcal{A}_{Q,z} \times \mathcal{C}_{Q,z}$, such that $\lambda_2 > \lambda_1$, which implies that $\bar{K}_{Q,z}(\lambda_2) > \bar{K}_{Q,z}(\lambda_1)$ (Lemma 4.1). Then, from Lemma 6.1, it follows that

$$ \begin{aligned} \mathrm{R}_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda_2)}) - \mathrm{R}_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda_1)}) \\ = \lambda_2 - \lambda_1 + \bar{K}_{Q,z}(\lambda_1) - \bar{K}_{Q,z}(\lambda_2) & \quad (237a) \end{aligned} $$

$$ = \bar{K}_{Q,z}^{-1}(\beta_2) - \bar{K}_{Q,z}^{-1}(\beta_1) + \beta_1 - \beta_2, \quad (237b) $$
Note that for all $c_1 \in (0, \infty)$ and for all $\lambda \in [0, +\infty)$, it holds that

$$ -\frac{c_1 - \lambda}{2} \leq \left| \frac{c_1 - \lambda}{2} \right| \qquad (233) $$

$$ = \sqrt{\left(\frac{c_1 - \lambda}{2}\right)^2} \qquad (234) $$

$$ \leq \sqrt{\left(\frac{c_1 - \lambda}{2}\right)^2 + \lambda c_1 Q(\mathcal{T}(z))}. \qquad (235) $$

Observe that for all $Q(\mathcal{T}(z)) \in [0, 1)$, $c_1 \in (0, \infty)$ and $\lambda \in [0, \infty)$ the expressions $(\frac{c_1-\lambda}{2})^2$ and $\lambda c_1 Q(\mathcal{T}(z))$ are always positive. Thus, the square roots in (232a) and (232b) are real, which implies that $r_1$ and $r_2$ are real. From (235), for all $\lambda \in [0, +\infty)$ and for all $Q(\mathcal{T}(z)) \in [0, 1)$, it holds

$$ r_1 < 0; \qquad (236a) $$

and following the same arguments

$$ r_2 > 0. \qquad (236b) $$

Hence, the solution for the Lagrange Multiplier $\beta$ that satisfies (228) given the empirical risk function $L_z$ in (41) and the probability measure $Q$ in (40a) is

$$ \beta = -\frac{(c_1 - \lambda)}{2} + \sqrt{\left(\frac{c_1 - \lambda}{2}\right)^2 + \lambda c_1 Q(\mathcal{T}(z))}, \qquad (237) $$

which completes the proof. □

# T Example 4.2

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

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

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

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

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

$$ \ell(f(\theta, x), y) = (x\theta - y)^2. \qquad (240) $$
where (237b) follows from substituting (26) into (237a). Note that (236) implies that

$$ \bar{K}_{Q,z}^{-1}(\beta_2) - \bar{K}_{Q,z}^{-1}(\beta_1) \geq \beta_2 - \beta_1, \quad (238) $$

with equality if and only if the function $L_z$ is nonseparable. Thus, from (237b) and (238) it follows that

$$ R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda_2)}) - R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda_1)}) \geq 0, \quad (239) $$

with equality if and only if the function $L_z$ is nonseparable. This completes the second part of the proof. ■

## N Proof of Lemma 6.3

From Theorem 3.1 and Corollary 3.3, it holds that

$$ D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = \int \log \left( \frac{dQ}{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}} \right) dQ(\theta) \quad (240) $$

$$ \leq \log \left( \int \frac{dQ}{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}} (\theta) dQ(\theta) \right) \quad (241) $$

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

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

$$ = \log \left( \frac{1}{\lambda} (\bar{K}_{Q,z}(\lambda) + R_z(Q)) \right), \quad (244) $$

where (241) follows from Jensen's inequality [59, Theorem 2.6.2]; (242) follows from (16); and (244) follows from (6). From (244), it follows that

$$ R_z(Q) \geq \lambda \exp \left( D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) - \bar{K}_{Q,z}(\lambda) \right) \quad (245) $$

$$ = \lambda \exp \left( D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) + R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) - \lambda \right), \quad (246) $$

where (246) follows from Lemma 6.1. Hence, the difference between the expected empirical risk of the probability measures $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ and $Q$, from (246), satisfies that

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

which completes the proof. ■
Hence, from the fact that $z$ is a single data point and the definition of $L_z$ in (3), it follows that

$$L_z(\theta) = \ell(f(\theta, x), y) \qquad (241a)$$

$$= (x\theta - y)^2. \qquad (241b)$$

Based on the previous assumptions regarding the functions $\ell$ and $f$, as well as the sets $\mathcal{M}$, $\mathcal{X}$, $\mathcal{Y}$, and the measure $Q$, the definition of $\delta_{Q,z}^*$ in (28) implies that $\delta_{Q,z}^* = 0$.

From Theorem 4.1, the solution to the Type-II ERM-RER problem in (11) is the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ that is mutually absolutely continuous with respect to $Q$, which implies that under the above assumptions $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ is absolutely continuous with respect to the Lebesgue measure $\mu$ such that

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

Hence, it follows that

$$\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{M}) = \int_{\mathcal{M}} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) dQ(\theta) \qquad (243a)$$

$$= \int_{\mathcal{M}} \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{d\mu}(\theta) d\mu(\theta) \qquad (243b)$$

$$= \int_{0}^{\infty} \frac{\lambda 4\theta^2 \exp(-2\theta)}{(x\theta - y)^2 + \beta} d\theta \qquad (243c)$$

$$= 4\lambda \int_{0}^{\infty} \frac{\theta^2 \exp(-2\theta)}{(\theta - 1)^2} d\theta \qquad (243d)$$

(243e)

The integral in (243d) can be rewritten as

$$\begin{aligned}
& \int_{0}^{\infty} \frac{\theta^2 \exp(-2\theta)}{(\theta - 1)^2} d\theta \\
&= \int_{0}^{\infty} \left( \frac{\theta \exp(-2\theta) + \frac{1}{2} \exp(-2\theta)}{\theta - 1} + \frac{\frac{1}{2} \theta \exp(-2\theta) + \frac{1}{2} \exp(-2\theta)}{(\theta - 1)^2} \right) d\theta \quad (244) \\
&= \frac{1}{2} \int_{0}^{\infty} \frac{2\theta \exp(-2\theta) + \exp(-2\theta)}{\theta - 1} d\theta \\
&\quad + \frac{1}{2} \int_{0}^{\infty} \frac{\theta \exp(-2\theta) + \exp(-2\theta)}{(\theta - 1)^2} d\theta. \qquad (245)
\end{aligned}$$

Using integration by parts on the second integral in (245) yields

$$\int_{0}^{\infty} \frac{\theta \exp(-2\theta) + \exp(-2\theta)}{(\theta - 1)^2} d\theta$$
O Proof of Lemma 6.5

From Lemma 4.1, Lemma 4.2, and Lemma 6.1, it holds that

$$
R_z \left( \bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \right) = \lambda - \bar{K}_{Q,z}(\lambda) \quad (248)
$$

$$
< \lambda + \delta_{Q,z}^{*}. \qquad (249)
$$

Note also that

$$
R_z \left( \bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \right) = \int L_z(\theta) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (250)
$$

$$
\geq \int \delta_{Q,z}^{*} d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (251)
$$

$$
= \delta_{Q,z}^{*}, \tag{252}
$$

with L_z in (3). The proof continues by determining the conditions for which (252)
holds with equality. Assume the empirical risk L_z in (3) is separable with re-
spect to the probability measure P̃<sup>(Q,λ)</sup><sub>Θ|Z=z</sub> in (16) (see Definition 2.2). Then,
there exists a real value ϵ > 0 and two nonnegligible sets A and B with respect
to the probability measure P̃<sup>(Q,λ)</sup><sub>Θ|Z=z</sub> in (16), such that

$$
\mathcal{A} = \{ \boldsymbol{\theta} \in \mathcal{M} : L_z(\boldsymbol{\theta}) < \delta_{Q,z}^* + \epsilon \}, \text{ and} \quad (253)
$$

$$
\mathcal{B} = \{ \theta \in \mathcal{M} : L_z(\theta) \geq \delta_{Q,z}^* + \epsilon \}. \quad (254)
$$

Note that the sets $\mathcal{A}$ and $\mathcal{B}$ form a partition of the set $\mathcal{M}$. Hence, the expected empirical risk satisfies

$$
R_z \left( \bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \right) = \int L_z(\theta) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (255)
$$

$$
= \int_{\mathcal{A}} L_z(\theta) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) + \int_{\mathcal{B}} L_z(\theta) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (256)
$$

$$
\geq \int_A \delta_{Q,z}^* d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) + \int_B (\delta_{Q,z}^* + \epsilon) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (257)
$$

$$
= \delta_{Q,z}^{*} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A) + (\delta_{Q,z}^{*} + \epsilon) \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(B), \quad (258)
$$

$$
= \delta_{Q,z}^{*} \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A) + (\delta_{Q,z}^{*} + \epsilon) (1 - \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A)) \quad (259)
$$

$$
= \delta_{Q,z}^{*} + \epsilon (1 - \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(A)) \quad (260)
$$

$$
> \delta_{Q,z}^{*}, \tag{261}
$$

where inequality (257) follows from (28) and (254); (259) follows from the fact
that the sets $\mathcal{A}$ and $\mathcal{B}$ form a partition of the set $\mathcal{M}$; and (261) follows from the
fact that the sets $\mathcal{A}$ and $\mathcal{B}$ are nonnegligible with respect to the probability mea-
sure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$, which implies $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{A}) < 1$. This proves the strict inequality
in (251).

Consider the case in which the empirical risk L_z in (3) is not separable with
respect to P̃<sup>(Q,λ)</sup><sub>Θ|Z=z</sub> in (16). Then, for all θ ∈ supp P̃<sup>(Q,λ)</sup><sub>Θ|Z=z</sub>, the empirical risk
$$ = -\frac{(\theta + 1) \exp(-2\theta)}{(\theta - 1)} - \int_{0}^{\infty} \frac{2\theta \exp(-2\theta) + \exp(-2\theta)}{\theta - 1} d\theta. \quad (246) $$

Plugging (246) into (245) yields

$$ \int_{0}^{\infty} \frac{\theta^2 \exp(-2\theta)}{(\theta - 1)^2} d\theta = \left[ -\frac{(\theta + 1) \exp(-2\theta)}{2(\theta - 1)} \right]_{0}^{\infty}. \quad (247) $$

From (247), it follows that

$$ 4\lambda \int_{0}^{\infty} \frac{\theta^2 \exp(-2\theta)}{(\theta - 1)^2} d\theta = 4\lambda \left[ -\frac{(\theta + 1) \exp(-2\theta)}{2(\theta - 1)} \right]_{0}^{\infty} \quad (248a) $$

$$ = 4\lambda \left[ -\frac{(\theta + 1) \exp(-2\theta)}{2(\theta - 1)} \right]_{0}^{1} + 4\lambda \left[ -\frac{(\theta + 1) \exp(-2\theta)}{2(\theta - 1)} \right]_{1}^{\infty} \quad (248b) $$

$$ \geq 4\lambda \left[ -\frac{(\theta + 1) \exp(-2\theta)}{2(\theta - 1)} \right]_{0}^{1} \quad (248c) $$

$$ = \lim_{a \to 1^{-}} 4\lambda \left[ -\frac{(\theta + 1) \exp(-2\theta)}{2(\theta - 1)} \right]_{0}^{a} \quad (248d) $$

$$ = \lim_{a \to 1^{-}} -4\lambda \frac{(a + 1) \exp(-2a)}{2(a - 1)} -4\lambda \frac{(0 + 1) \exp(-0)}{2(0 - 1)} \quad (248e) $$

$$ = \lim_{a \to 1^{-}} -4\lambda \frac{(a + 1) \exp(-2a)}{2(a - 1)} - 2\lambda \quad (248f) $$

$$ = \infty, \quad (248g) $$

which completes the proof. □

## References

[1] V. Vapnik, “Principles of risk minimization for learning theory,” *Advances in Neural Information Processing Systems*, vol. 4, pp. 831–838, Jan. 1992.

[2] V. Vapnik and A. Y. Chervonenkis, “On a perceptron class,” *Avtomatika i Telemkhanika*, vol. 25, no. 1, pp. 112–120, Feb. 1964.

[3] M. R. Rodrigues and Y. C. Eldar, *Information-theoretic Methods in Data Science*, 1st ed. Cambridge, UK: Cambridge University Press, 2021.

[4] M. Mezard and A. Montanari, *Information, Physics, and Computation*, 1st ed. New York, NY, USA: Oxford University Press, 2009.

[5] M. J. Wainwright, *High-dimensional Statistics: A Non-asymptotic Viewpoint*, 1st ed. New York, NY, USA: Cambridge University Press, 2019.
satisfies $L_z(\theta) = \delta_{Q,z}^*$, which implies $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = \delta_{Q,z}^*$. Hence, if the function $L_z$ is nonseparable, then (251) holds with equality. Therefore, (251) holds with equality, if and only if the function $L_z$ is nonseparable, which completes the proof. ■

## P Proof of Theorem 6.1

Let $\delta$ be a real in $(\delta_{Q,z}^*, \infty)$, with $\delta_{Q,z}^*$ in (28). Let also $\gamma \in (0, \infty)$ satisfy the following equality:

$$R_z(\bar{P}_{\Theta|Z=z}^{(Q,\gamma)}) \le \delta, \qquad (262)$$

where the existence of such a $\gamma$ is ensured by the continuity of $R_z(\bar{P}_{\Theta|Z=z}^{(Q,\gamma)})$ with respect to $\gamma$ (Lemma 6.2); and Lemma 6.5 and Lemma 6.6. From (27), it holds that

$$\mathcal{L}_z(\delta) \supseteq \mathcal{L}_{Q,z}^*, \qquad (263)$$

and thus,

$$\bar{P}_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{L}_z(\delta)) \ge \bar{P}_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{L}_{Q,z}^*), \qquad (264)$$

with $\mathcal{L}_{Q,z}^*$ defined in (30). Let $\lambda$ be a positive real such that $\lambda \le \gamma$, and

$$\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) > 1 - \epsilon. \qquad (265)$$

The existence of such a positive real $\lambda$ follows from Lemma 5.5. From (263), it follows that

$$\bar{P}_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{L}_z(\delta)) \ge \bar{P}_{\Theta|Z=z}^{(Q,\gamma)}(\mathcal{L}_{Q,z}^*). \qquad (266)$$

Hence, from (265) and (266), it holds that

$$1 - \epsilon < \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_{Q,z}^*) \qquad (267)$$

$$\le \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\mathcal{L}_z(\delta)). \qquad (268)$$

The equality in (268) implies that the probability measure $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ is $(\delta, \epsilon)$-optimal (Definition 6.1), which completes the proof. ■

## Q Proof of Lemma 7.1

The proof is divided into two parts. The first part is as follows, from Theorem 3.1, it follows that for all $\theta \in \mathcal{M}$,

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

Inria
[6] R. Vershynin, *High-dimensional probability: An Introduction with Applications in Data Science*, 1st ed. New York, NY, USA: Cambridge University Press, 2018.

[7] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, “Learnability and the Vapnik-Chervonenkis dimension,” *Journal of the ACM*, vol. 36, no. 4, pp. 929–965, Oct. 1989.

[8] I. Guyon, V. Vapnik, B. Boser, L. Bottou, and S. A. Solla, “Structural risk minimization for character recognition,” *Advances in Neural Information Processing Systems*, vol. 4, Dec. 1991.

[9] G. Lugosi and K. Zeger, “Nonparametric estimation via empirical risk minimization,” *IEEE Transactions on Information Theory*, vol. 41, no. 3, pp. 677–687, May 1995.

[10] P. L. Bartlett, “The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network,” *IEEE Transactions on Information Theory*, vol. 44, no. 2, pp. 525–536, Mar. 1998.

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

[12] V. Cherkassky, X. Shao, F. M. Mulier, and V. N. Vapnik, “Model complexity control for regression using VC generalization bounds,” *IEEE Transactions on Neural Networks*, vol. 10, no. 5, pp. 1075–1089, Sep. 1999.

[13] V. Vapnik, “An overview of statistical learning theory,” *IEEE Transactions on Neural Networks*, vol. 10, no. 5, pp. 988–999, Sep. 1999.

[14] L. Bottou, F. E. Curtis, and J. Nocedal, “Optimization methods for large-scale machine learning,” *SIAM Review*, vol. 60, no. 2, pp. 223–311, May 2018.

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

[16] W. Deng, Q. Zheng, and L. Chen, “Regularized extreme learning machine,” in *Proceedings of the IEEE Symposium on Computational Intelligence in Data Mining (CIDM)*, Nashville, TN, USA, Apr. 2009, pp. 389–395.

[17] D. Arpit, S. Jastrzębski, N. Ballas, D. Krueger, E. Bengio, M. S. Kanwal, T. Maharaj, A. Fischer, A. Courville, Y. Bengio, and S. Lacoste-Julien, “A closer look at memorization in deep networks,” in *Proceedings of the 34th International Conference on Machine Learning (ICML)*, vol. 70, Aug. 2017, pp. 233–242.
$$= \log(\lambda) - \log(\bar{K}_{Q,z}(\lambda) + L_z(\theta)) \quad (270)$$

$$= \log(\lambda) - V_{Q,z,\lambda}(\theta), \quad (271)$$

where the function $V_{Q,z,\lambda}$ is defined in (57b). Thus,

$$D(\bar{P}_{\Theta|Z=z}^{(Q,\lambda)} \| Q) = \int \log \left( \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (272)$$

$$= \log(\lambda) - \int V_{Q,z,\lambda}(\theta) d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}(\theta) \quad (273)$$

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

where the functional $\bar{R}_{Q,z,\lambda}$ is defined in (70). Hence, it follows from (274) that

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

which completes the proof of (72) and concludes the first part.

The second part is as follows. From (271), it follows that

$$D(Q \| \bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = - \int \log \left( \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) dQ(\theta) \quad (276)$$

$$= -\log(\lambda) + \int V_{Q,z,\lambda}(\theta) dQ(\theta) \quad (277)$$

$$= -\log(\lambda) + \bar{R}_{Q,z,\lambda}(Q). \quad (278)$$

Hence, it follows from (278) that

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

which completes the proof of (73). This completes the proof. ■

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

## R Proof of Lemma 7.2

The proof uses the mutual absolute continuity between $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) and $Q$ (Corollary 3.3). Hence, a probability measure $P \in \mathcal{O}_Q(\mathcal{M})$ is mutually absolutely continuous with $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$. The proof follows by noticing that for such $P$ and for all $\theta \in \mathcal{M}$, it holds that

$$\log \left( \frac{dP}{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \right) = \log \left( \frac{dP}{dQ}(\theta) \frac{dQ}{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}(\theta) \right) \quad (280)$$

$$= \log \left( \frac{dP}{dQ}(\theta) \right) - \log \left( \frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) \right) \quad (281)$$
[18] 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.

[19] O. Bousquet and A. Elisseeff, “Stability and generalization,” *The Journal of Machine Learning Research*, vol. 2, no. 1, pp. 499–526, Mar. 2002.

[20] V. N. Vapnik and A. Y. Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities,” *Measures of Complexity: Festschrift for Alexey Chervonenkis*, vol. 16, no. 2, pp. 11–30, Oct. 2015.

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

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

[23] D. A. McAllester, “Some PAC-Bayesian theorems,” in *Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT)*, Madison, WI, USA, Jul. 1998, pp. 230–234.

[24] L. G. Valiant, “A theory of the learnable,” *Communications of the ACM*, vol. 27, no. 11, pp. 1134–1142, Nov. 1984.

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

[26] D. Cullina, A. N. Bhagoji, and P. Mittal, “PAC-learning in the presence of adversaries,” *Advances in Neural Information Processing Systems*, vol. 31, no. 1, pp. 1–12, Dec. 2018.

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

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

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

[30] M. Raginsky, A. Rakhlin, M. Tsao, Y. Wu, and A. Xu, “Information-theoretic analysis of stability and bias of learning algorithms,” in *Proceedings of the IEEE Information Theory Workshop (ITW)*, Cambridge, UK, Sep. 2016, pp. 26–30.
$$ = \log\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) - \log\left(\frac{\lambda}{\bar{K}_{Q,z}(\lambda) + L_z(\boldsymbol{\theta})}\right) \quad (282) $$

$$ = \log\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) - \log(\lambda) + \log(\bar{K}_{Q,z}(\lambda) + L_z(\boldsymbol{\theta})) \quad (283) $$

$$ = \log\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) - \log(\lambda) + V_{Q,z,\lambda}(\boldsymbol{\theta}), \quad (284) $$

where the functions $L_z$, $\bar{K}_{Q,z}$ and $V_{Q,z,\lambda}$ are defined in (3), (23) and in (57b), respectively. The equality (282) follows from (16). Hence, the relative entropy $D(P||\bar{P}_{\Theta|Z=z}^{(Q,\lambda)})$ satisfies,

$$ D(P||\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}) = \int \log \left( \frac{dP}{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}(\boldsymbol{\theta}) \right) dP(\boldsymbol{\theta}) \quad (285) $$

$$ = \int \left( \log\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) - \log(\lambda) + V_{Q,z,\lambda}(\boldsymbol{\theta}) \right) dP(\boldsymbol{\theta}) \quad (286) $$

$$ = \int \log\left(\frac{dP}{dQ}(\boldsymbol{\theta})\right) dP(\boldsymbol{\theta}) - \log(\lambda) + \int V_{Q,z,\lambda}(\boldsymbol{\theta}) dP(\boldsymbol{\theta}) \quad (287) $$

$$ = D(P||Q) - \log(\lambda) + \bar{R}_{Q,z,\lambda}(P) \quad (288) $$

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

where (286) follows from (284); (288) follows from (70); and (289) follows from Lemma 7.1. Thus, from (289), it follows that

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

which completes the proof.

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

## S Proof of Lemma 7.4

From Lemma 7.1, for all $\alpha \in (0, \infty)$, it holds that

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

where the functional $\bar{R}_{Q,z,\lambda}$ is defined in (70).
[31] D. Russo and J. Zou, "How much does your data exploration overfit? Controlling bias via information usage," *IEEE Transactions on Information Theory*, vol. 66, no. 1, pp. 302–323, Jan. 2019.

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

[33] G. Aminian, Y. Bu, L. Toni, M. R. D. Rodrigues, and G. W. Worrell, "Information-theoretic characterizations of generalization error for the Gibbs algorithm," *arXiv preprint arXiv:2210.09864*, Oct. 2022.

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

[35] X. Wang and Q. He, "Enhancing generalization capability of SVM classifiers with feature weight adjustment," in *Proceedings of the Knowledge-Based Intelligent Information and Engineering Systems: 8th International Conference (KES)*, Wellington, New Zealand, Sep. 2004, pp. 1037–1043.

[36] Q. Lin, Z. Lu, and L. Xiao, "An accelerated proximal coordinate gradient method and its application to regularized empirical risk minimization," *arXiv preprint arXiv:1407.1296*, Jul. 2014.

[37] X. Yang and D. Li, "Estimation of the empirical risk-return relation: A generalized-risk-in-mean model," *Journal of Time Series Analysis*, vol. 43, no. 6, pp. 938–963, May 2022.

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

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

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

[41] J. Liao, O. Kosut, L. Sankar, and F. P. Calmon, "A tunable measure for information leakage," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Vail, CO, USA, Jun. 2018, pp. 701–705.

[42] T. Sypherd, M. Diaz, L. Sankar, and P. Kairouz, "A tunable loss function for binary classification," in *Proceedings of the IEEE international symposium on information theory (ISIT)*, Paris, France, Jul. 2019, pp. 2479–2483.
Similarly, from [30, Lemma 20], for all $\lambda \in (0, \infty)$, it holds that

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

with the functional $\mathrm{R}_z$ defined in (6). From [30, Theorem 3], the function $S_{Q,\lambda}$ in [30, Definition 7] satisfies that

$$ S_{Q,\lambda}(z, \bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) = \mathrm{R}_z(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) - \mathrm{R}_z(P_{\Theta|Z=z}^{(Q,\lambda)}) \quad (293) $$

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

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

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

where (295) follows from (291); and (296) follows from (292). Rearranging (296) yields

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

Similarly, from Lemma 7.2 the function $\bar{S}_{Q,\alpha}$ in (75) satisfies that

$$ \bar{S}_{Q,\alpha}(z, P_{\Theta|Z=z}^{(Q,\lambda)}) = \bar{R}_{Q,z,\alpha}(P_{\Theta|Z=z}^{(Q,\lambda)}) - \bar{R}_{Q,z,\alpha}(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) \quad (298) $$

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

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

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

where (300) follows from (291); and (301) follows from (292). Rearranging (301) yields

$$ \frac{1}{\lambda} \mathrm{R}_z \left( P_{\Theta|Z=z}^{(Q,\lambda)} \right) - \bar{R}_{Q,z,\alpha} \left( P_{\Theta|Z=z}^{(Q,\lambda)} \right) = -D \left( P_{\Theta|Z=z}^{(Q,\lambda)} \| \bar{P}_{\Theta|Z=z}^{(Q,\alpha)} \right) $$
[43] G. R. Kurri, T. Sypherd, and L. Sankar, "Realizing GANs via a tunable loss function," in *Proceedings of the IEEE Information Theory Workshop (ITW)*, virtual conference, 2021, pp. 1-6.

[44] H. Hsu and F. Calmon, "Rashomon capacity: A metric for predictive multiplicity in classification," *Advances in Neural Information Processing Systems*, vol. 35, pp. 2898-2900, Dec. 2022.

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

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

[47] R. G. Bartle and D. R. Sherbert, *Introduction to Real Analysis*, 2nd ed. New York, NY, USA: Wiley New York, 2000.

[48] A. Klenke, *Probability Theory: A Comprehensive Course*, 3rd ed. New York, NY, USA: Springer, 2020.

[49] 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.
$$ - \left( \log(\alpha) + K_{Q,z} \left( -\frac{1}{\lambda} \right) \right). \quad (302) $$

The proof proceeds by subtracting (302) from (297), resulting in

$$ \begin{aligned} & \frac{1}{\lambda} S_{Q,\lambda} (z, \bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) - \bar{S}_{Q,\alpha} (z, P_{\Theta|Z=z}^{(Q,\lambda)}) \\ & = D(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)} \| P_{\Theta|Z=z}^{(Q,\lambda)}) - D(P_{\Theta|Z=z}^{(Q,\lambda)} \| \bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) \\ & \quad + 2 \left( \log(\alpha) + K_{Q,z} \left( -\frac{1}{\lambda} \right) \right), \end{aligned} \quad (303) $$

where the functions $S_{Q,\lambda}$ and $\bar{S}_{Q,\alpha}$ are respectively defined in [30, Definition 7] and (75). From [36, Theorem 1] and Lemma 7.2, it follows that

$$ \begin{aligned} & \frac{1}{\lambda} S_{Q,\lambda} (z, \bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) - \bar{S}_{Q,\alpha} (z, P_{\Theta|Z=z}^{(Q,\lambda)}) \\ & = D(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)} \| P_{\Theta|Z=z}^{(Q,\lambda)}) - D(P_{\Theta|Z=z}^{(Q,\lambda)} \| \bar{P}_{\Theta|Z=z}^{(Q,\alpha)}) \\ & \quad + 2(D(P_{\Theta|Z=z}^{(Q,\lambda)} \| Q) - D(\bar{P}_{\Theta|Z=z}^{(Q,\alpha)} \| Q)). \end{aligned} \quad (304) $$

Substituting (304) into (303) yields

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

which completes the proof. ■

# T Examples

## T.1 Example 1

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

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

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

$$ f(\theta, x) = x\theta, \quad (307) $$

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

$$ \ell(f(\theta, x), y) = (x\theta - y)^2, \quad (308) $$

which implies

$$ L_z(\theta) = (x\theta - y)^2, \quad (309) $$
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
with the function L_z defined in (3). Furthermore, from assumptions (a), (b), and (309), it follows that there exists $\theta^* \in \text{supp } Q$ such that $L_z(\theta^*) = 0$, which implies that

$$ \delta_{Q,z}^* = 0. \qquad (310) $$

Under the current assumptions, the objective of this example is to show that $C_{Q,z} = [\delta_{Q,z}^*, \infty)$. For this purpose, from Lemma 4.2, it is sufficient to show that the condition in (31) holds. From Theorem 3.1, it follows that $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies for all $\theta \in \text{supp } Q$,

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

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

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

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

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

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

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

$$ = 2, \qquad (312f) $$

where (312a) follows from (306); (312c) follows from the assumption that $(x, y) = (1, 0)$; and (312d) follows from the fact that $\delta_{Q,z}^* = 0$. Finally, the function $\bar{K}_{Q,z}$ in (23) satisfies $\bar{K}_{Q,z}(\frac{1}{2}) = 0$, which implies $-\delta_{Q,z}^* \in C_{Q,z}$, thus the set $A_{Q,z} = (0, \infty)$.

## T.2 Example 2

Consider Example 1 in Appendix T.1 with $z = ((1,1))$. Note that (310) holds for this example. Under the current assumptions, the objective of this example is to show that $A_{Q,z} = (\delta_{Q,z}^*, \infty)$. For this purpose, from Lemma 4.2, it is sufficient to show that the condition in (31) does not hold. That is,

$$ \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} dQ(\theta) = \int \frac{1}{L_z(\theta) - \delta_{Q,z}^*} \frac{dQ}{d\mu}(\theta) d\mu(\theta) \qquad (313a) $$

$$ = \int \frac{4\theta^2 \exp(-2\theta)}{L_z(\theta) - \delta_{Q,z}^*} d\mu(\theta) \qquad (313b) $$

$$ = \int \frac{4\theta^2 \exp(-2\theta)}{(x\theta - y)^2 - \delta_{Q,z}^*} d\mu(\theta) \qquad (313c) $$
$$ = \int \frac{4\theta^2 \exp(-2\theta)}{(\theta - 1)^2} d\mu(\theta) \qquad (313d) $$

$$ = 4 \int \frac{\theta^2 \exp(-2\theta)}{(\theta - 1)^2} d\mu(\theta) \qquad (313e) $$

$$ = 4 \int \left( \frac{\theta \exp(-2\theta) + \frac{\exp(-2\theta)}{2}}{\theta - 1} - \frac{\frac{\theta \exp(-2\theta)}{2} - \frac{\exp(-2\theta)}{2}}{(\theta - 1)^2} \right) d\mu(\theta) \qquad (313f) $$

$$ = 4 \left( \int \frac{\theta \exp(-2\theta) + \frac{\exp(-2\theta)}{2}}{\theta - 1} d\mu(\theta) + \int \frac{\frac{\theta \exp(-2\theta)}{2} + \frac{\exp(-2\theta)}{2}}{(\theta - 1)^2} d\mu(\theta) \right) \qquad (313g) $$

$$ = 4 \left( \frac{1}{2} \int \frac{2\theta \exp(-2\theta) + \exp(-2\theta)}{\theta - 1} d\mu(\theta) + \frac{1}{2} \int \frac{\theta \exp(-2\theta) + \exp(-2\theta)}{(\theta - 1)^2} d\mu(\theta) \right), \qquad (313h) $$

where (313a) follows from the assumption that $Q \ll \mu$, (313b) follows from (306), (313d) follows from (310) and the assumption that $(x, y) = (1, 1)$. Using integration by parts on the second integral in (313h), let the functions $\phi: M \to \mathbb{R}$ and $\psi: M \to \mathbb{R}$ be

$$ \phi(\theta) = \theta \exp(-2\theta) + \exp(-2\theta), \quad \text{and} \qquad (314a) $$

$$ \psi(\theta) = -\frac{1}{\theta - 1}. \qquad (314b) $$

The derivatives of $\phi$ and $\psi$ satisfy

$$ \frac{d\phi}{d\mu}(\theta) = -2\theta \exp(-2\theta) - \exp(-2\theta), \quad \text{and} \qquad (315a) $$

$$ \frac{d\psi}{d\mu}(\theta) = \frac{1}{(\theta - 1)^2}, \qquad (315b) $$

respectively. Note that given a subset $[a, b] \subset M$ with $a, b \in \mathbb{R}$ such that $a < b$ it holds that,

$$ \int_{[a,b]} \frac{\exp(-2\theta) + \exp(-2\theta)}{(\theta - 1)^2} d\mu(\theta) = \int_{[a,b]} \phi(\theta) \frac{d\psi}{d\mu}(\theta) d\mu(\theta) \qquad (316a) $$

$$ = \left[ \phi(\theta) \psi(\theta) \right]_a^b - \int_{[a,b]} \frac{d\phi}{d\mu}(\theta) \psi(\theta) d\mu(\theta) \qquad (316b) $$
$$ = \left[ - \frac{\theta \exp(-2\theta) + \exp(-2\theta)}{\theta - 1} \right]_a^b + \int_{[a,b]} \frac{-2\theta \exp(-2\theta) - \exp(-2\theta)}{\theta - 1} d\mu(\theta), \quad (316c) $$

where (316c) follows the equalities (314) and (315). Substituting (316c) into (313h) yields

$$ \int \frac{1}{\mathcal{L}_z(\theta) - \delta_{Q,z}^*} dQ(\theta) = 4 \int_{[0,\infty)} \frac{\theta^2 \exp(-2\theta)}{(\theta-1)^2} d\mu(\theta) \quad (317a) $$

$$ = 4 \int_{[0,1]} \frac{\theta^2 \exp(-2\theta)}{(\theta-1)^2} d\mu(\theta) + 4 \int_{(1,\infty)} \frac{\theta^2 \exp(-2\theta)}{(\theta-1)^2} d\mu(\theta) \quad (317b) $$

$$ \geq 4 \int_{[0,1]} \frac{\theta^2 \exp(-2\theta)}{(\theta-1)^2} d\mu(\theta) \quad (317c) $$

$$ = 2 \left( \int_{[0,1]} \frac{2\theta \exp(-2\theta) + \exp(-2\theta)}{\theta - 1} d\mu(\theta) + \int_{[0,1]} \frac{\exp(-2\theta) + \exp(-2\theta)}{(\theta - 1)^2} d\mu(\theta) \right) \quad (317d) $$

$$ = 2 \left( \int_{[0,1]} \frac{2\theta \exp(-2\theta) + \exp(-2\theta)}{\theta - 1} d\mu(\theta) + \left[ - \frac{\theta \exp(-2\theta) + \exp(-2\theta)}{\theta - 1} \right]_0^1 - \int_{[0,1]} \frac{2\theta \exp(-2\theta) + \exp(-2\theta)}{\theta - 1} d\mu(\theta) \right) \quad (317e) $$

$$ = 2 \left[ - \frac{\theta \exp(-2\theta) + \exp(-2\theta)}{\theta - 1} \right]_0^1 \quad (317f) $$

$$ = \infty, \quad (317g) $$

where (317a) follows from the assumption that $\mathcal{M} = [0, \infty)$, (317c) follows from observing that for all $\theta \in [0, \infty)$, it holds that $\frac{\theta^2 \exp(-2\theta)}{(\theta-1)^2} > 0$, in (317d) follows from (313h), and (317e) follows from substituting (316c) into (317d). From (317g), it follows that the function $\bar{K}_{Q,z}$ in (23) is undefined at zero, which implies $\delta_{Q,z}^* \notin \mathcal{A}_{Q,z}$, and this, $\mathcal{A}_{Q,z} = (0, \infty)$.

## T.3 Example 3

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

$$ Q(\mathcal{B}) = \epsilon, \quad \text{and} \quad (318a) $$
$$Q(\mathcal{M} \setminus \mathcal{B}) = 1 - \epsilon, \qquad (318b)$$

with $\epsilon > 0$. Let the empirical risk function $L_z$ in (3) be

$$L_z(\theta) = \begin{cases} 0 & \text{if } \theta \in \mathcal{B} \\ c & \text{if } \theta \in \mathcal{M} \setminus \mathcal{B}, \end{cases} \qquad (319)$$

with $c > 0$. Under the current assumptions, the objective of this example is to show that for all $z \in (\mathcal{X} \times \mathcal{Y})^n$, it holds that $C_{Q,z} = (-\delta_{Q,z}^*, \infty)$ and $A_{Q,z} = (0, \infty)$. To show this, it is necessary to characterize the function $\bar{K}_{Q,z}$ in (23b). Hence, from the fact that the Lagrangian multiplier $\beta$ for the optimization problem in (11) satisfies

$$\int \frac{\lambda}{\beta + L_z(\boldsymbol{\nu})} dQ(\boldsymbol{\nu}) = 1, \qquad (320)$$

which follows from Theorem 3.1, the empirical risk function $L_z : \mathcal{M} \to \mathbb{R}_0^+$ in (319), which is a simple function, and the probability measure $Q$ in (318a), it holds that

$$\int \frac{\lambda}{\beta + L_z(\boldsymbol{\nu})} dQ(\boldsymbol{\nu}) = \lambda \left( \frac{1}{\beta + c_0} Q(\mathcal{T}(z)) + \frac{1}{\beta + c_1} Q(\mathcal{M} \setminus \mathcal{T}(z)) \right) \quad (321a)$$

$$= \lambda \left( \frac{1}{\beta + c_0} Q(\mathcal{T}(z)) + \frac{1}{\beta + c_1} (1 - Q(\mathcal{T}(z))) \right) \quad (321b)$$

$$= \lambda \left( \frac{(\beta + c_1)Q(\mathcal{T}(z)) + (\beta + c_0)(1 - Q(\mathcal{T}(z)))}{\beta^2 + \beta(c_0 + c_1) + c_0c_1} \right) \quad (321c)$$

$$= \lambda \left( \frac{(c_1 - c_0)Q(\mathcal{T}(z)) + \beta + c_0}{\beta^2 + \beta(c_0 + c_1) + c_0c_1} \right). \qquad (321d)$$

From (320) and (321d), it follows that

$$0 = \beta^2 + \beta(c_0 + c_1) + c_0c_1 - \lambda((c_1 - c_0)Q(\mathcal{T}(z)) + \beta + c_0) \quad (322a)$$

$$= \beta^2 + \beta(c_0 + c_1 - \lambda) + c_0c_1 - \lambda c_0 - \lambda(c_1 - c_0)Q(\mathcal{T}(z)). \quad (322b)$$

Hence,

$$0 = \beta^2 + \beta(c_1 - \lambda) - \lambda c_1 Q(\mathcal{T}(z)). \qquad (322c)$$

Observe that the expression in (322c) is a quadratic polynomial that has two roots $r_1$ and $r_2$. Hence, (322c) in terms of $r_1$ and $r_2$ satisfies

$$0 = \beta^2 - (r_1 + r_2)\beta + r_1 r_2 \qquad (323a)$$

$$= (\beta - r_1)(\beta - r_2), \qquad (323b)$$

where the roots $r_1$ and $r_2$ are given by the quadratic formula such that

$$r_1 = - \frac{(c_1 - \lambda)}{2} - \sqrt{\left(\frac{c_1 - \lambda}{2}\right)^2 + \lambda c_1 Q(\mathcal{T}(z))}, \quad (324a)$$
and

$$r_2 = - \frac{(c_1 - \lambda)}{2} + \sqrt{\left(\frac{c_1 - \lambda}{2}\right)^2 + \lambda c_1 Q(\mathcal{T}(z))}. \quad (324\text{b})$$

The proof continues by verifying that the roots in (324a) and (324b) are real and there is only one positive root for all $\lambda \in (0, +\infty)$ and for all $Q(\mathcal{T}(z)) \in [0, 1)$.

Note that for all $c_1 \in (0, \infty)$ and for all $\lambda \in [0, +\infty)$, it holds that

$$-\frac{c_1 - \lambda}{2} \le \left|\frac{c_1 - \lambda}{2}\right| \quad (325)$$

$$= \sqrt{\left(\frac{c_1 - \lambda}{2}\right)^2} \quad (326)$$

$$\le \sqrt{\left(\frac{c_1 - \lambda}{2}\right)^2 + \lambda c_1 Q(\mathcal{T}(z))}. \quad (327)$$

Observe that for all $Q(\mathcal{T}(z)) \in [0, 1)$, $c_1 \in (0, \infty)$ and $\lambda \in [0, \infty)$ the expressions $(\frac{c_1-\lambda}{2})^2$ and $\lambda c_1 Q(\mathcal{T}(z))$ are always positive. Thus, the square roots in (324a) and (324b) are real, which implies that $r_1$ and $r_2$ are real. From (324) and (327), for all $\lambda \in [0, +\infty)$ and for all $Q(\mathcal{T}(z)) \in [0, 1)$, it holds that

$$r_1 < 0; \quad (328\text{a})$$

and following the same arguments

$$r_2 > 0. \quad (328\text{b})$$

Hence, the solution for the Lagrange Multiplier $\beta$ that satisfies (320) given the empirical risk function $L_z$ in (319) and the probability measure $Q$ in (318a) is

$$\beta = -\frac{(c_1 - \lambda)}{2} + \sqrt{\left(\frac{c_1 - \lambda}{2}\right)^2 + \lambda c_1 Q(\mathcal{T}(z))}, \quad (329)$$

which implies that the function $\bar{K}_{Q,z}$ in (23b) under the current assumptions in (318) and (319) satisfies

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

From Theorem 3.1, it follows that $\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}$ in (16) satisfies for all $\theta \in \text{supp } Q$,

$$\frac{d\bar{P}_{\Theta|Z=z}^{(Q,\lambda)}}{dQ}(\theta) = \frac{\lambda}{L_z(\theta) - \frac{(c-\lambda)}{2} + \sqrt{\left(\frac{c-\lambda}{2}\right)^2 + \lambda c Q(\mathcal{B})}}. \quad (331)$$
Under the current assumptions, from Lemma 4.2, it is sufficient to show that for all $c \in (0, \infty)$ and $\lambda \in (0, \infty)$ in (319), the function $\bar{K}_{Q,z}$ in (23b) is strictly greater than $-\delta_{Q,z}^*$. From equality (330), it holds that

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

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

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

$$ \geq 0 \quad (332d) $$

$$ = -\delta_{Q,z}^*, \quad (332e) $$

which proves that for all $c \in (0, \infty)$ and for all $\lambda \in (0, \infty)$, it holds that $\bar{K}_{Q,z}(\lambda) > -\delta_{Q,z}^*$ which implies that $-\delta_{Q,z}^* \notin C_{Q,z}$ with the set $C_{Q,z}$ defined in (23) and thus $A_{Q,z} = (0, \infty)$.

# U Numerical Simulation

The MNIST dataset consists of 60,000 images for training and 10,000 images for testing. Out of the 60,000 training images, 12,183 are labeled as the digits six or seven, while 1,986 out of the 10,000 test images correspond to these digits. Each image is a 28 × 28 grayscale picture and is represented by the matrix $I \in [0, 1]^{28 \times 28}$.

## U.1 Feature Extraction of the Histogram of Oriented Gradients

The grayscale images are processed by calculating their corresponding histogram of oriented gradients (HOG) [60]. The HOG for each image is computed through the following steps:

1.) For each pixel location $(i, j) \in \{1, 2, ..., 28\}^2$ in the image, the gradients in the w- and h-directions (width, height) are computed using finite differences given by the functions $G_w : \{1, 2, ..., 28\}^2 \to \mathbb{R}$ and $G_h : \{1, 2, ..., 28\}^2 \to \mathbb{R}$, which are defined as

$$ G_w(i, j) = \begin{cases} I(i+1, j) - I(i-1, j) & \text{if } i \in \{2, \dots, 27\} \\ I(i+1, j) - I(i, j) & \text{if } i = 1 \\ I(i, j) - I(i-1, j) & \text{if } i = 28 \end{cases}, \quad (333) $$

and

$$ G_h(i, j) = \begin{cases} I(i, j+1) - I(i, j-1) & \text{if } j \in \{2, \dots, 27\} \\ I(i, j+1) - I(i, j) & \text{if } j = 1 \\ I(i, j) - I(i, j-1) & \text{if } j = 28 \end{cases}, \quad (334) $$
where $I(i,j) \in [0, 1]$ represents the pixel intensity at location $(i, j)$.

2.) Given a pixel location $(i, j) \in \{1, 2, ..., 28\}^2$, the magnitude and orientation of a pixel at location $(i, j)$ is given by the functions $M: \{1, 2, ..., 28\}^2 \to \mathbb{R}$ and $\phi: \{1, 2, ..., 28\}^2 \to \mathbb{R}$, such that

$$M(i, j) = \sqrt{G_w(i, j)^2 + G_h(i, j)^2}, \quad \text{and} \quad (335)$$

$$\phi(i, j) = \arctan\left(\frac{G_h(i, j)}{G_w(i, j)}\right). \quad (336)$$

3.) The matrix $I$ is divided into sub-matrices of size $4 \times 4$, such that the number of sub-matrices is 7. These sub-matrices are referred to as *cells* and are denoted, for all $(w, h) \in \{1, \dots, 7\}^2$, by

$$C_{w,h} = \begin{bmatrix} I(a_w, b_h) & \cdots & I(a_w + 3, b_h) \\ \vdots & \ddots & \vdots \\ I(a_w, b_h + 3) & \cdots & I(a_w + 3, b_h + 3) \end{bmatrix}, \quad (337)$$

where the real values $a_w$ and $b_h$ are

$$a_w = 4(w - 1) + 1 \quad (338)$$

$$b_h = 4(h - 1) + 1. \quad (339)$$

This implies that the matrix $I$ can be represented as

$$I = \begin{bmatrix} C_{1,1} & \cdots & C_{7,1} \\ \vdots & \ddots & \vdots \\ C_{1,7} & \cdots & C_{7,7} \end{bmatrix}. \quad (340)$$

From (337), the set of all pairs $(i, j)$ of pixel coordinates in $I$ that lie within the cell $C_{w,h}$ is given by:

$$\mathcal{A}_{w,h} = \{a_w, a_w + 3\} \times \{b_h, b_h + 3\}, \quad (341)$$

with $a_w$ in (338) and $b_h$ in (339).

4.) For each cell $C_{w,h}$ in (337) the orientations $\phi(i, j)$ in (336) are divided into 9 bins. That is, the $n^{th}$ bin, with $1 \le n \le 9$, satisfies that

$$\mathcal{B}_{w,h}^{(n)} = \left\{ \phi(i, j) \in \mathbb{R} : 180\left(\frac{n-1}{9}\right) \le \phi(i, j) < 180\left(\frac{n}{9}\right) : (i, j) \in \mathcal{A}_{w,h} \right\}. \quad (342)$$

The contribution of each pixel to its corresponding bin is based on its gradient magnitude. That is, the value of the $n$-th bin from the $(w, h)$-th cell $C_{w,h}$ in (337) is given by the function $H_{w,h}(n): \{1, 2, \dots, 9\} \to \mathbb{R}$, such that

$$H_{w,h}(n) = \sum_{(i,j) \in \mathcal{A}_{w,h}} M(i,j) \mathbf{1}_{\{\phi(i,j) \in \mathcal{B}_{w,h}^{(n)}\}}, \quad (343)$$
with M in (335); and $\mathcal{B}_{w,h}^{(n)}$ in (342). Thus, the histogram of gradient orientations of the cell $C_{w,h}$ is represented by the vector $\mathbf{H}_{w,h} \in \mathbb{R}^9$, such that

$$ \mathbf{H}_{w,h} = [H_{w,h}(1), H_{w,h}(2), \dots, H_{w,h}(9)], \quad (344) $$

with the function $H_{w,h}$ in (343).

5.) To account for illumination and contrast variations, the histogram $\mathbf{H}_{w,h}$ in (344) is normalized. To normalize the histograms for all cells $C_{w,h}$ in (337), the cells are grouped into sub-matrices formed by 2 × 2 cells with a cell overlap set to 1 pixel, such that the number of sub-matrices is:

$$ (7-1) \times (7-1) = 36. \quad (345) $$

These sub-matrices of the matrix I in (340), with $(m,s) \in \{1, \dots, \sqrt{36}\}^2$ are referred to as blocks, and denoted by

$$ B_{m,s} = \begin{bmatrix} C_{m,s} & C_{m+1,s} \\ C_{m,s+1} & C_{m+1,s+1} \end{bmatrix}, \quad (346) $$

with the matrix $C_{m,s}$ in (337). From (340) and (346), a block $B_{m,s}$ is a sub-matrix of size 8 × 8, i.e., $B_{m,s} \in \mathbb{R}^{8 \times 8}$. The size of a block is given by the ratio of the total number of pixels in a block to the number of pixels in a cell:

$$ \frac{8 \times 8}{4 \times 4} = 4, \quad (347a) $$

The normalized histogram of a cell $C_{w,h}$ in a block $B_{m,s}$ is denoted by the vector $\hat{\mathbf{H}}_{w,h}^{(m,s)} \in \mathbb{R}^9$. This normalization of is typically done using the $\ell_2$-norm, such that

$$ \hat{\mathbf{H}}_{w,h}^{(m,s)} = \frac{\mathbf{H}_{w,h}}{\sqrt{\sum_{(i,j) \in \{m,m+1\} \times \{s,s+1\}} \mathbf{H}_{i,j}^2 + \epsilon^2}}, \quad (348) $$

where $\mathbf{H}_{w,h}$ in (344) is the unnormalized histogram, and the $\epsilon = 10^{-4}$ to avoid division by zero.

6.) For an image with 36 blocks (see (345)), 9 orientation bins, and a size of block 4 (see (347)), the dimension of the HOG feature vector $\hat{\mathbf{x}}$ is:

$$ 36 \times 4 \times 9 = 1296. \quad (349) $$

The HOG feature vector $\hat{\mathbf{x}} \in \mathbb{R}^{1296}$ is formed by concatenating all the normalized histograms $\hat{\mathbf{H}}_{w,h}^{(m,s)}$ such that

$$ \hat{\mathbf{x}} = \begin{bmatrix} \hat{\mathbf{H}}_{1,1}^{(1,1)}, \hat{\mathbf{H}}_{1,2}^{(1,1)}, \hat{\mathbf{H}}_{2,1}^{(1,1)}, \hat{\mathbf{H}}_{2,2}^{(1,1)}, \\ \hat{\mathbf{H}}_{2,1}^{(2,1)}, \hat{\mathbf{H}}_{2,2}^{(2,1)}, \hat{\mathbf{H}}_{3,1}^{(2,1)}, \hat{\mathbf{H}}_{3,2}^{(2,1)}, \dots, \\ \hat{\mathbf{H}}_{6,6}^{(6,6)}, \hat{\mathbf{H}}_{6,7}^{(6,6)}, \hat{\mathbf{H}}_{7,6}^{(6,6)}, \hat{\mathbf{H}}_{7,7}^{(6,6)} \end{bmatrix}^{\top}. \quad (350) $$
## U.2 Principal Component Analysis

The final step in the data processing is to reduce the dimensionality of the pattern $\hat{x}$ in (350) from $\mathbb{R}^{1296}$ to $\mathbb{R}^2$, while ensuring that the important structure of the pattern is preserved. In this simulation, principal component analysis (PCA) is used to project the high-dimensional data onto a lower-dimensional subspace. From 60,000 images for training in the MNIST, the HOG of two handwritten numbers (in this simulation 6 and 7) are computed, as mentioned in Appendix U.1. The resulting 12,183 HOG vectors $\hat{x} \in \mathbb{R}^{1296}$ are reduced to $\mathbb{R}^2$ using PCA as follows:

1.) To reduce the dimensionality, the first step in PCA is to compute the covariance matrix of the data. This matrix captures the relationships between the different features (or dimensions) of the data. The covariance matrix is calculated as follows:

$$C = \frac{1}{n-1} \sum_{i=1}^{n} (\hat{x}_i - \mu)(\hat{x}_i - \mu)^{\top}, \quad (351)$$

where $n = 12,183$, $C \in \mathbb{R}^{1296 \times 1296}$, and $\mu$ is the mean of all the training patterns given by

$$\mu = \frac{1}{n} \sum_{i=1}^{n} \hat{x}_i. \quad (352)$$

2.) The next step in PCA is to perform an eigenvalue decomposition of the covariance matrix $C$ in (351). The decomposition can be written as:

$$C = V \Lambda V^{\top}, \quad (353)$$

where $V \in \mathbb{R}^{1296 \times 1296}$ is a matrix whose columns are the eigenvectors of $C$ and $\Lambda \in \mathbb{R}^{1296 \times 1296}$ is a diagonal matrix containing the corresponding eigenvalues.

3.) Following the computation of the eigenvectors, the dimensionality is reduced from $\mathbb{R}^{1296}$ to $\mathbb{R}^2$ by selecting the two eigenvectors associated with the largest eigenvalues. Denote these top two eigenvectors as $w_1$ and $w_2$. These eigenvectors constitute the columns of the projection matrix $W \in \mathbb{R}^{1296 \times 2}$, defined as

$$W = [w_1 \ w_2]. \quad (354)$$

4.) Once the projection matrix $W$ is computed, each high-dimensional pattern $\hat{x} \in \mathbb{R}^{1296}$ can be projected onto the new $\mathbb{R}^2$ subspace. The projection is performed as follows:

$$x = W^{\top} \hat{x}, \quad (355)$$
with $\hat{\mathbf{x}}$ in (350), $\mathbf{W}$ in (354) and $\mathbf{x} \in \mathbb{R}^2$ is the 2-dimensional coordinates of the original pattern $\hat{\mathbf{x}}$ in the reduced-dimensional space.

## U.3 Simulation Dataset

In this simulation, a datapoint is a tuple $(\hat{\mathbf{x}}, \mathbf{y}) \in \mathbb{R}^{1296} \times \{6, 7\}$, with $\hat{\mathbf{x}}$ in (350) and $\mathbf{y}$ being the label assigned by MNIST to the image $I$ in (340). The label $\mathbf{y}$ corresponds to the digit in the image $I$. Such an image produces the vector $\hat{\mathbf{x}}$, when its HOG features are computed.

## References

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

[2] ——, “Asymmetry of the relative entropy in the regularization of empirical risk minimization,” *IEEE Transactions on Information Theory*, vol. 71, no. 8, pp. 6198–6226, Aug. 2025.

[3] V. Vapnik, “Principles of risk minimization for learning theory,” *Advances in Neural Information Processing Systems*, vol. 4, pp. 831–838, Jan. 1991.

[4] V. Vapnik and A. Y. Chervonenkis, “On a perceptron class,” *Avtomatika i Telemkhanika*, vol. 25, no. 1, pp. 112–120, Feb. 1964.

[5] M. R. Rodrigues and Y. C. Eldar, *Information-theoretic Methods in Data Science*, 1st ed. Cambridge, UK: Cambridge University Press, 2021.

[6] M. Mezard and A. Montanari, *Information, Physics, and Computation*, 1st ed. New York, NY, USA: Oxford University Press, 2009.

[7] M. J. Wainwright, *High-dimensional Statistics: A Non-asymptotic Viewpoint*, 1st ed. New York, NY, USA: Cambridge University Press, 2019.

[8] R. Vershynin, *High-dimensional Probability: An Introduction with Applications in Data Science*, 1st ed. New York, NY, USA: Cambridge University Press, 2018.

[9] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, “Learnability and the Vapnik-Chervonenkis dimension,” *Journal of the ACM*, vol. 36, no. 4, pp. 929–965, Oct. 1989.

[10] I. Guyon, V. Vapnik, B. Boser, L. Bottou, and S. A. Solla, “Structural risk minimization for character recognition,” *Advances in Neural Information Processing Systems*, vol. 4, Dec. 1991.
[11] G. Lugosi and K. Zeger, "Nonparametric estimation via empirical risk minimization," *IEEE Transactions on Information Theory*, vol. 41, no. 3, pp. 677-687, May 1995.

[12] P. L. Bartlett, "The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network," *IEEE Transactions on Information Theory*, vol. 44, no. 2, pp. 525-536, Mar. 1998.

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

[14] V. Cherkassky, X. Shao, F. M. Mulier, and V. N. Vapnik, "Model complexity control for regression using VC generalization bounds," *IEEE Transactions on Neural Networks*, vol. 10, no. 5, pp. 1075-1089, Sep. 1999.

[15] V. Vapnik, "An overview of statistical learning theory," *IEEE Transactions on Neural Networks*, vol. 10, no. 5, pp. 988-999, Sep. 1999.

[16] L. Bottou, F. E. Curtis, and J. Nocedal, "Optimization methods for large-scale machine learning," *SIAM Review*, vol. 60, no. 2, pp. 223-311, May 2018.

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

[18] W. Deng, Q. Zheng, and L. Chen, "Regularized extreme learning machine," in *Proceedings of the IEEE Symposium on Computational Intelligence in Data Mining (CIDM)*, Nashville, TN, USA, Apr. 2009, pp. 389-395.

[19] D. Arpit, S. Jastrzębski, N. Ballas, D. Krueger, E. Bengio, M. S. Kanwal, T. Maharaj, A. Fischer, A. Courville, Y. Bengio, and S. Lacoste-Julien, "A closer look at memorization in deep networks," in *Proceedings of the 34th International Conference on Machine Learning (ICML)*, vol. 70, Aug. 2017, pp. 233-242.

[20] F. Hellström, G. Durisi, B. Guedj, and M. Raginsky, "Generalization bounds: Perspectives from information theory and PAC-Bayes," *Foundations and Trends in Machine Learning*, vol. 18, no. 1, pp. 1-223, Jan. 2025.

[21] O. Bousquet and A. Elisseeff, "Stability and generalization," *The Journal of Machine Learning Research*, vol. 2, no. 1, pp. 499-526, Mar. 2002.

[22] V. N. Vapnik and A. Y. Chervonenkis, "On the uniform convergence of relative frequencies of events to their probabilities," *Measures of Complexity: Festschrift for Alexey Chervonenkis*, vol. 16, no. 2, pp. 11-30, Oct. 2015.
[23] 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.

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

[25] D. A. McAllester, "Some PAC-Bayesian theorems," in *Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT)*, Madison, WI, USA, Jul. 1998, pp. 230-234.

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

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

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

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

[30] —, "Empirical risk minimization with relative entropy regularization," *IEEE Transactions on Information Theory*, vol. 70, no. 7, pp. 5122-5161, Jul. 2024.

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

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

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

[34] B. Zou, L. Li, and Z. Xu, "The generalization performance of ERM algorithm with strongly mixing observations," *Machine Learning*, vol. 75, no. 3, pp. 275-295, Feb. 2009.
[35] 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, Nov. 2023.

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

[37] S. M. Perlaza and X. Zou, “The generalization error of machine learning algorithms,” arXiv preprint 2411.12030, Nov. 2024.

[38] X. Wang and Q. He, “Enhancing generalization capability of SVM classifiers with feature weight adjustment,” in *Proceedings of the Knowledge-Based Intelligent Information and Engineering Systems: 8th International Conference (KES)*, Wellington, New Zealand, Sep. 2004, pp. 1037–1043.

[39] Q. Lin, Z. Lu, and L. Xiao, “An accelerated proximal coordinate gradient method and its application to regularized empirical risk minimization,” *SIAM Journal on Optimization*, vol. 25, no. 4, pp. 2244–2273, Jul. 2015.

[40] X. Yang and D. Li, “Estimation of the empirical risk-return relation: A generalized-risk-in-mean model,” *Journal of Time Series Analysis*, vol. 43, no. 6, pp. 938–963, May 2022.

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

[42] B. Rodríguez Gálvez, “An information-theoretic approach to generalization theory,” PhD thesis, KTH Royal Institute of Technology, Stockholm, Sweden, Jun. 2024.

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

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

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

[46] A. R. Esposito and M. Gastpar, “From generalisation error to transportation-cost inequalities and back,” in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Aalto, Finland, Jun. 2022, pp. 294–299.
[47] J. Liao, O. Kosut, L. Sankar, and F. P. Calmon, "A tunable measure for information leakage," in *Proceedings of the IEEE International Symposium on Information Theory (ISIT)*, Vail, CO, USA, Jun. 2018, pp. 701-705.

[48] T. Sypherd, M. Diaz, L. Sankar, and P. Kairouz, "A tunable loss function for binary classification," in *Proceedings of the IEEE international symposium on information theory (ISIT)*, Paris, France, Jul. 2019, pp. 2479-2483.

[49] G. R. Kurri, T. Sypherd, and L. Sankar, "Realizing GANs via a tunable loss function," in *Proceedings of the IEEE Information Theory Workshop (ITW)*, virtual conference, 2021, pp. 1-6.

[50] H. Hsu and F. Calmon, "Rashomon capacity: A metric for predictive multiplicity in classification," *Advances in Neural Information Processing Systems*, vol. 35, pp. 2898-2900, Dec. 2022.

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

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

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

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

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

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

[57] W. Rudin, *Principles of Mathematical Analysis*, 3rd ed. New York, NY, USA: McGraw-Hill Book Company, Inc., 1976.

[58] A. Klenke, *Probability Theory: A Comprehensive Course*, 3rd ed. New York, NY, USA: Springer, 2020.

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

[60] N. Dalal and B. Triggs, "Histograms of oriented gradients for human detection," in *Proceedings of the IEEE Computer Society Conference on*
*Computer Vision and Pattern Recognition (CVPR)*, San Diego, CA, USA, Apr. 2005, pp. 886–893.
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