&\leq\mathbb{E}_{\theta\sim\mathfrak{m}^{\beta,\sigma}(\nu_{(1)}(\tilde{\lambda}))}\Big{[}g_{1}(\mathfrak{m}_{(1)}(\lambda),\theta)^{2}\Big{]}^{1/2}\big{(}1+\|Z_{1}\|^{2}\big{)}\\\
&\leq
C_{\theta}\Big{(}1+\mathbb{E}_{\theta\sim\mathfrak{m}^{\beta,\sigma}(\nu_{(1)}(\tilde{\lambda}))}\big{[}\|\theta\|^{p}\big{]}+\mathbb{E}_{\theta\sim\mathfrak{m}_{(1)}(\lambda)}\big{[}\|\theta\|^{p}\big{]}\Big{)}\big{(}1+\|Z_{1}\|^{2}\big{)}.\end{split}$
(56)

By definition,
$\mathfrak{m}_{(1)}(\lambda)=\mathfrak{m}(\nu_{n,(1)})+\lambda(\mathfrak{m}(\nu_{n})-\mathfrak{m}(\nu_{n,(1)}))$,
and hence

$\mathbb{E}_{\theta\sim\mathfrak{m}_{(1)}(\lambda)}\big{[}\|\theta\|^{p}\big{]}=(1-\lambda)\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{n,(1)})}\big{[}\|\theta\|^{p}\big{]}+\lambda\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{n})}\big{[}\|\theta\|^{p}\big{]}.$

In a similar approach to (54), we have,

$\begin{split}\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n,(1)})&=\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+\frac{1}{n}\Big{(}\ell(\tilde{\gamma}^{\sigma}_{p},\,\widetilde{\\!{Z}}_{1})-\ell(\tilde{\gamma}^{\sigma}_{p},Z_{1})\Big{)}\\\
&\leq\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+g(\tilde{\gamma}^{\sigma}_{p})\frac{1}{n}\Big{(}2+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2})\Big{)}.\end{split}$
(57)

As before, it follows from Lemma D.1 that

$\begin{split}&\mathbb{E}_{\theta\sim\mathfrak{m}^{\beta,\sigma}(\nu_{(1)}(\tilde{\lambda}))}\big{[}\|\theta\|^{p}\big{]}+\mathbb{E}_{\theta\sim\mathfrak{m}_{(1)}(\lambda)}\big{[}\|\theta\|^{p}\big{]}\\\
&=\mathbb{E}_{\theta\sim\mathfrak{m}^{\beta,\sigma}(\nu_{(1)}(\tilde{\lambda}))}\big{[}\|\theta\|^{p}\big{]}+(1-\lambda)\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{n,(1)})}\big{[}\|\theta\|^{p}\big{]}+\lambda\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{n})}\big{[}\|\theta\|^{p}\big{]}\\\
&\leq\Big{[}\mathrm{R}(\tilde{\gamma}^{\sigma}_{p},\nu_{(1)}(\tilde{\lambda}))+\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)\Big{]}+(1-\lambda)\Big{[}\mathrm{R}(\tilde{\gamma}^{\sigma}_{p},\nu_{n,(1)})+\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)\Big{]}\\\
&\qquad+\lambda\Big{[}\mathrm{R}(\tilde{\gamma}^{\sigma}_{p},\nu_{n})+\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)\Big{]}\\\
&\leq
2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+g(\tilde{\gamma}^{\sigma}_{p})\frac{(2-\tilde{\lambda}-\lambda)}{n}\Big{(}2+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}\Big{)}.\end{split}$
(58)

Therefore, substituting (52), (55), (56) and (58) into (51) and simplifying,
we have

$\begin{split}&h(\mathbf{Z}_{n},\,\widetilde{\\!{Z}}_{1})\\\
&\leq\frac{2\beta^{2}}{\sigma^{2}}C_{\theta}\Big{[}1+2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+2\frac{g(\tilde{\gamma}^{\sigma}_{p})}{n}\Big{(}2+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}\Big{)}\Big{]}\big{(}1+\|Z_{1}\|^{2}\big{)}\\\
&\qquad\times\sqrt{2}C_{\theta}\Big{[}1+2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+2\frac{g(\tilde{\gamma}^{\sigma}_{p})}{n}\Big{(}2+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{1}\|^{2}\Big{)}\Big{]}\Big{(}2+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{1}\|^{2}\Big{)}\\\
&\leq\sqrt{2}\frac{2\beta^{2}}{\sigma^{2}}C_{\theta}^{2}\Big{[}1+2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+2\frac{g(\tilde{\gamma}^{\sigma}_{p})}{n}\Big{(}2+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{1}\|^{2}\Big{)}\Big{]}^{2}\\\
&\qquad\times\big{(}1+\|Z_{1}\|^{2}\big{)}\Big{(}2+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{1}\|^{2}\Big{)}.\end{split}$
(59)

We have the bound

$\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})\leq\int_{\mathcal{Z}}g(\tilde{\gamma}_{p}^{\sigma})(1+\|z\|^{2})\nu_{n}(\mathrm{d}{z})=g(\tilde{\gamma}_{p}^{\sigma})\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2}).$
(60)

Therefore, using the inequality $(a+b(c+d))\leq(a+cb)(c+d)/c$ for $a,b,c,d\geq
0$,

$\begin{split}&h(\mathbf{Z}_{n},\,\widetilde{\\!{Z}}_{1})\\\
&\leq\sqrt{2}\frac{2\beta^{2}}{\sigma^{2}}C_{\theta}^{2}\Big{[}1+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+2\frac{g(\tilde{\gamma}^{\sigma}_{p})}{n}\Big{(}2+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})\Big{)}\Big{]}^{2}\\\
&\qquad\times\big{(}1+\|Z_{1}\|^{2}\big{)}\Big{(}2+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{1}\|^{2}\Big{)}\\\
&\leq\frac{\sqrt{2}}{2}\frac{\beta^{2}}{\sigma^{2}}C_{\theta}^{2}\Big{[}1+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+4\frac{g(\tilde{\gamma}^{\sigma}_{p})}{n}\Big{]}^{2}\\\
&\qquad\times\Big{(}2+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})\Big{)}^{2}\big{(}1+\|Z_{1}\|^{2}\big{)}\Big{(}2+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{1}\|^{2}\Big{)}.\end{split}$
(61)

Applying Lemma D.7 we have

$\begin{split}&\mathbb{E}_{\mathbf{Z}_{n},\,\widetilde{\\!{\mathbf{Z}}}_{n}}\Big{[}\Big{(}2+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})\Big{)}^{2}\big{(}1+\|Z_{1}\|^{2}\big{)}\Big{(}2+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{1}\|^{2}\Big{)}\Big{]}\\\
&\leq\mathbb{E}_{Z_{1}}\Big{[}\Big{(}2+\|Z_{1}\|^{2}+\|Z_{1}\|^{2}+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{1}\|^{2})\Big{)}^{2}\big{(}1+\|Z_{1}\|^{2}\big{)}\Big{(}2+\|Z_{1}\|^{2}+\|Z_{1}\|^{2}\Big{)}\Big{]}\\\
&=(2\times
3^{2})\mathbb{E}_{Z_{1}}\Big{[}(1+\|Z_{1}\|^{2})^{4}\Big{]}\end{split}$ (62)

And therefore, substituting (62) and (61) in (50),

$\begin{split}|\mathrm{gen}(\mathfrak{m}(\nu_{n}),\nu_{\mathrm{pop}})|&\leq
9\sqrt{2}\frac{\beta^{2}}{\sigma^{2}}C_{\theta}^{2}\Big{[}1+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+4\frac{g(\tilde{\gamma}^{\sigma}_{p})}{n}\Big{]}^{2}\mathbb{E}_{Z_{1}}\Big{[}\Big{(}1+\|Z_{1}\|^{2}\Big{)}^{4}\Big{]}.\\\
\end{split}$ (63)

∎

###### Proof of Theorem 4.3.

We start from the result of Theorem 3.7, where we have

$\mathrm{gen}_{L_{2}}(\mathfrak{m},\nu_{\mathrm{pop}})\leq\frac{1}{n}\bigg{(}4K+2K^{1/2}\mathbb{E}_{\mathbf{Z}_{2},\mathbf{\,\widetilde{\\!{Z}}}_{2}}\Big{[}\tilde{h}_{2}(\mathbf{Z}_{2},\mathbf{\,\widetilde{\\!{Z}}}_{2})^{2}\Big{]}^{1/2}+\mathbb{E}_{\mathbf{Z}_{2},\mathbf{\,\widetilde{\\!{Z}}}_{2}}\Big{[}\tilde{h}_{2}(\mathbf{Z}_{2},\mathbf{\,\widetilde{\\!{Z}}}_{2})^{2}\Big{]}\bigg{)},$

where

$\displaystyle\tilde{h}_{2}(\mathbf{Z}_{n},\mathbf{\,\widetilde{\\!{Z}}}_{2})$
$\displaystyle=\int_{0}^{1}\int_{0}^{1}\int_{\Theta}\Big{(}\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}\Big{[}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda_{1}),\,\widetilde{\\!{Z}}_{3},\theta)\Big{]}-\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),Z_{1},\theta)\Big{)}$
$\displaystyle\qquad\times\Delta_{\mathfrak{m}}(\mathbf{Z}_{2},\mathbf{\,\widetilde{\\!{Z}}}_{2};\mathrm{d}\theta)\,\mathrm{d}\lambda\mathrm{d}\tilde{\lambda},$
$\displaystyle\Delta_{\mathfrak{m}}(\mathbf{Z}_{n},\mathbf{\,\widetilde{\\!{Z}}}_{2};\mathrm{d}\theta)$
$\displaystyle=\Big{(}\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),Z_{1})(\mathrm{d}\theta)-\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),\,\widetilde{\\!{Z}}_{1})(\mathrm{d}\theta)$
$\displaystyle\qquad+\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),Z_{2})(\mathrm{d}\theta)-\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),\,\widetilde{\\!{Z}}_{2})(\mathrm{d}\theta)\Big{)}$
$\displaystyle=\int_{\mathcal{Z}}\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),z^{\prime})(\mathrm{d}\theta)\big{(}\delta_{Z_{1}}-\delta_{\tilde{Z}_{1}}+\delta_{Z_{2}}-\delta_{\tilde{Z}_{2}}\big{)}\big{(}\mathrm{d}z^{\prime}).$

Applying Lemma D.4, we compute

$\begin{split}&\Big{|}\int_{\Theta}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),z,\theta)\Delta_{\mathfrak{m}}(\mathbf{Z}_{2},\mathbf{\,\widetilde{\\!{Z}}}_{2};\mathrm{d}\theta)\Big{|}\\\
&=\Big{|}-\frac{2\beta^{2}}{\sigma^{2}}\mathrm{Cov}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),z,\theta),\\\
&\qquad\,\int_{\mathcal{Z}}\frac{\delta
S}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),\theta,z^{\prime})(\delta_{Z_{1}}-\delta_{\,\widetilde{\\!{Z}}_{1}}+\delta_{Z_{2}}-\delta_{\,\widetilde{\\!{Z}}_{2}})(\mathrm{d}z^{\prime})\Big{]}\Big{|}\\\
&\leq\frac{2\beta^{2}}{\sigma^{2}}\mathbb{E}_{\theta\sim\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),z,\theta)\Big{)}^{2}\Big{]}^{1/2}\\\
&\qquad\times\mathbb{E}_{\theta\sim\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\int_{\mathcal{Z}}\frac{\delta
S}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),\theta,z^{\prime})\Big{(}\delta_{Z_{1}}-\delta_{\,\widetilde{\\!{Z}}_{1}}+\delta_{Z_{2}}-\delta_{\,\widetilde{\\!{Z}}_{2}}\Big{)}(\mathrm{d}z^{\prime})\Big{)}^{2}\Big{]}^{1/2},\end{split}$

and similarly

$\begin{split}&\Big{|}\int_{\Theta}\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}\Big{[}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),z,\theta)\Big{]}\Delta_{\mathfrak{m}}(\mathbf{Z}_{2},\mathbf{\,\widetilde{\\!{Z}}}_{2};\mathrm{d}\theta)\Big{|}\\\
&\leq\frac{2\beta^{2}}{\sigma^{2}}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}\Big{(}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),\,\widetilde{\\!{Z}}_{3},\theta)\Big{)}\Big{)}^{2}\Big{]}^{1/2}\\\
&\qquad\times\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\int_{\mathcal{Z}}\frac{\delta
S}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),\theta,z^{\prime})\Big{(}\delta_{Z_{1}}-\delta_{\,\widetilde{\\!{Z}}_{1}}+\delta_{Z_{2}}-\delta_{\,\widetilde{\\!{Z}}_{2}}\Big{)}(\mathrm{d}z^{\prime})\Big{)}^{2}\Big{]}^{1/2}.\end{split}$

Therefore, using the inequality $(a+b)^{2}\leq 2(a^{2}+b^{2})$ and Jensen’s
inequality,

$\begin{split}&\tilde{h}_{2}(\mathbf{Z}_{n},\mathbf{\,\widetilde{\\!{Z}}}_{2})^{2}\\\
&\leq\frac{4\beta^{4}}{\sigma^{4}}\int_{0}^{1}\int_{0}^{1}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\int_{\mathcal{Z}}\frac{\delta
S}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),\theta,z^{\prime})\Big{(}\delta_{Z_{1}}-\delta_{\,\widetilde{\\!{Z}}_{1}}+\delta_{Z_{2}}-\delta_{\,\widetilde{\\!{Z}}_{2}}\Big{)}(\mathrm{d}z^{\prime})\Big{)}^{2}\Big{]}\\\
&\quad\times\Big{(}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}\Big{(}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),\,\widetilde{\\!{Z}}_{3},\theta)\Big{)}\Big{)}^{2}\Big{]}^{1/2}\\\
&\qquad\qquad+\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),Z_{1},\theta)\Big{)}^{2}\Big{]}^{1/2}\Big{)}^{2}\bigg{]}\mathrm{d}\lambda\mathrm{d}\tilde{\lambda}.\\\
&\leq\frac{8\beta^{4}}{\sigma^{4}}\int_{0}^{1}\int_{0}^{1}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\int_{\mathcal{Z}}\frac{\delta
S}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),\theta,z^{\prime})\Big{(}\delta_{Z_{1}}-\delta_{\,\widetilde{\\!{Z}}_{1}}+\delta_{Z_{2}}-\delta_{\,\widetilde{\\!{Z}}_{2}}\Big{)}(\mathrm{d}z^{\prime})\Big{)}^{2}\Big{]}\\\
&\quad\times\bigg{[}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}\Big{[}\Big{(}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),\,\widetilde{\\!{Z}}_{3},\theta)\Big{)}^{2}\Big{]}\Big{]}\\\
&\qquad\qquad+\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),Z_{1},\theta)\Big{)}^{2}\Big{]}\bigg{]}\mathrm{d}\lambda\mathrm{d}\tilde{\lambda}.\end{split}$
(64)

Similarly to (54), we know that

$\begin{split}\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{(1,2)}(\tilde{\lambda}))&\leq\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+g(\tilde{\gamma}^{\sigma}_{p})\frac{1-\tilde{\lambda}}{n}\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}\Big{)},\end{split}$

and hence, as in (58), we have

$\begin{split}&\mathbb{E}_{\theta\sim\mathfrak{m}^{\beta,\sigma}(\nu_{(1,2)}(\tilde{\lambda}))}\big{[}\|\theta\|^{p}\big{]}+\mathbb{E}_{\theta\sim\mathfrak{m}_{(1,2)}(\lambda)}\big{[}\|\theta\|^{p}\big{]}\\\
&=(2-\lambda)\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{n,(1,2)})}\big{[}\|\theta\|^{p}\big{]}+\lambda\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{n})}\big{[}\|\theta\|^{p}\big{]}\\\
&\leq
2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)\\\
&\qquad+g(\tilde{\gamma}^{\sigma}_{p})\frac{(2-\lambda-\tilde{\lambda})}{n}\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}\Big{)}.\end{split}$

Using Proposition D.5, as in (55), we know

$\begin{split}&\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\int_{\mathcal{Z}}\frac{\delta
S}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),\theta,z^{\prime})\Big{(}\delta_{Z_{1}}-\delta_{\,\widetilde{\\!{Z}}_{1}}+\delta_{Z_{2}}-\delta_{\,\widetilde{\\!{Z}}_{2}}\Big{)}(\mathrm{d}z^{\prime})\Big{)}^{2}\Big{]}\\\
&\leq
2\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\int_{\mathcal{Z}}\frac{\delta
S}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),\theta,z^{\prime})\Big{(}\delta_{Z_{1}}-\delta_{\,\widetilde{\\!{Z}}_{1}}\Big{)}(\mathrm{d}z^{\prime})\Big{)}^{2}\Big{]}\\\
&\qquad+2\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\int_{\mathcal{Z}}\frac{\delta
S}{\delta\nu}(\nu_{(1,2)}(\tilde{\lambda}),\theta,z^{\prime})\Big{(}\delta_{Z_{2}}-\delta_{\,\widetilde{\\!{Z}}_{2}}\Big{)}(\mathrm{d}z^{\prime})\Big{)}^{2}\Big{]}\\\
&\leq
4\,C_{\theta}^{2}\Big{(}4+\|Z_{1}\|^{2}+\|\tilde{Z}_{1}\|^{2}+\|Z_{2}\|^{2}+\|\tilde{Z}_{2}\|^{2}\Big{)}^{2}\\\
&\qquad\times\Big{(}1+2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+2g(\tilde{\gamma}^{\sigma}_{p})\frac{1-\tilde{\lambda}}{n}\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}\Big{)}\Big{)}^{2}.\end{split}$

Using Lemma D.1 and (14),

$\begin{split}&\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}\Big{[}\Big{(}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),\,\widetilde{\\!{Z}}_{3},\theta)\Big{)}^{2}\Big{]}\Big{]}\\\
&\leq
C_{\theta}^{2}\Big{(}1+\mathbb{E}_{\theta\sim\mathfrak{m}^{\beta,\sigma}(\nu_{(1,2)}(\tilde{\lambda}))}\big{[}\|\theta\|^{p}\big{]}+\mathbb{E}_{\theta\sim\mathfrak{m}_{(1,2)}(\lambda)}\big{[}\|\theta\|^{p}\big{]}\Big{)}^{2}\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}[(1+\|\,\widetilde{\\!{Z}}_{3}\|^{2})^{2}]\\\
&\leq
C_{\theta}^{2}\Big{(}1+2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)\\\
&\qquad+g(\tilde{\gamma}^{\sigma}_{p})\frac{(2-\lambda-\tilde{\lambda})}{n}\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}\Big{)}\Big{)}^{2}\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}[(1+\|\,\widetilde{\\!{Z}}_{3}\|^{2})^{2}],\end{split}$

and similarly

$\begin{split}&\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1,2)}(\tilde{\lambda}))}\Big{[}\Big{(}\frac{\delta\ell}{\delta
m}(\mathfrak{m}_{(1,2)}(\lambda),Z_{1},\theta)\Big{)}^{2}\Big{]}\\\ &\leq
C_{\theta}^{2}\Big{(}1+2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)\\\
&\qquad+g(\tilde{\gamma}^{\sigma}_{p})\frac{(2-\lambda-\tilde{\lambda})}{n}\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}\Big{)}\Big{)}^{2}(1+\|\,\widetilde{\\!{Z}}_{1}\|^{2})^{2}.\end{split}$

As in (60), we know $R(\tilde{\gamma}_{p}^{\sigma},\nu_{n})\leq
g(\tilde{\gamma}_{p}^{\sigma})\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})$, and
hence

$\begin{split}&\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+g(\tilde{\gamma}^{\sigma}_{p})\frac{1}{n}\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}\Big{)}\\\
&\leq
g(\tilde{\gamma}_{p}^{\sigma})\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})\Big{)}.\end{split}$

By substitution in (64) and simplification we get

$\begin{split}&\tilde{h}_{2}(\mathbf{Z}_{n},\mathbf{\,\widetilde{\\!{Z}}}_{2})^{2}\\\
&\leq\frac{8\beta^{4}}{\sigma^{4}}4\,C_{\theta}^{2}\Big{(}4+\|Z_{1}\|^{2}+\|\tilde{Z}_{1}\|^{2}+\|Z_{2}\|^{2}+\|\tilde{Z}_{2}\|^{2}\Big{)}^{2}\\\
&\quad\times\Big{(}1+2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+2g(\tilde{\gamma}^{\sigma}_{p})\frac{1}{n}\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}\Big{)}\Big{)}^{2}\\\
&\quad\times\bigg{[}C_{\theta}^{2}\Big{(}1+2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)\\\
&\qquad+g(\tilde{\gamma}^{\sigma}_{p})\frac{2}{n}\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}\Big{)}\Big{)}^{2}\Big{[}(1+\|\,\widetilde{\\!{Z}}_{1}\|^{2})^{2}+\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}[(1+\|\,\widetilde{\\!{Z}}_{3}\|^{2})^{2}]\Big{]}\bigg{]}\\\
&\leq
2^{3}\Big{(}\frac{2\beta^{2}}{\sigma^{2}}\Big{)}^{2}\,C_{\theta}^{4}\Big{(}4+\|Z_{1}\|^{2}+\|\tilde{Z}_{1}\|^{2}+\|Z_{2}\|^{2}+\|\tilde{Z}_{2}\|^{2}\Big{)}^{2}\\\
&\quad\times\Big{(}1+2\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+\frac{2g(\tilde{\gamma}^{\sigma}_{p})}{n}\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}\Big{)}\Big{)}^{4}\\\
&\quad\times\Big{[}(1+\|\,\widetilde{\\!{Z}}_{1}\|^{2})^{2}+\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}[(1+\|\,\widetilde{\\!{Z}}_{3}\|^{2})^{2}]\Big{]}\\\
&\leq
2^{3}\Big{(}\frac{2\beta^{2}}{\sigma^{2}}\Big{)}^{2}\,C_{\theta}^{4}\Big{(}4+\|Z_{1}\|^{2}+\|\tilde{Z}_{1}\|^{2}+\|Z_{2}\|^{2}+\|\tilde{Z}_{2}\|^{2}\Big{)}^{2}\\\
&\quad\times\Big{(}1+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+2g(\tilde{\gamma}^{\sigma}_{p})\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})\Big{)}\Big{)}^{4}\\\
&\quad\times\Big{[}(1+\|\,\widetilde{\\!{Z}}_{1}\|^{2})^{2}+\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}[(1+\|\,\widetilde{\\!{Z}}_{3}\|^{2})^{2}]\Big{]}\\\
&\leq
2^{-5}\Big{(}\frac{2\beta^{2}}{\sigma^{2}}\Big{)}^{2}\,C_{\theta}^{4}\Big{(}4+\|Z_{1}\|^{2}+\|\tilde{Z}_{1}\|^{2}+\|Z_{2}\|^{2}+\|\tilde{Z}_{2}\|^{2}\Big{)}^{2}\\\
&\quad\times\Big{(}1+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+8g(\tilde{\gamma}^{\sigma}_{p})\Big{)}^{4}\\\
&\quad\times\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})\Big{)}^{4}\Big{[}(1+\|\,\widetilde{\\!{Z}}_{1}\|^{2})^{2}+\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}[(1+\|\,\widetilde{\\!{Z}}_{3}\|^{2})^{2}]\Big{]}\\\
\end{split}$

where we use the inequality $(a+b(c+d))\leq(a+cb)(c+d)/c$ for $a,b,c,d\geq 0$
when passing to the penultimate line.

Applying Lemma D.7 gives

$\begin{split}&\mathbb{E}_{\mathbf{Z}_{n},\,\widetilde{\\!{\mathbf{Z}}}_{2}}\bigg{[}\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}\Big{)}^{2}\\\
&\qquad\times\Big{(}4+\|\,\widetilde{\\!{Z}}_{1}\|^{2}+\|Z_{1}\|^{2}+\|\,\widetilde{\\!{Z}}_{2}\|^{2}+\|Z_{2}\|^{2}+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})\Big{)}^{4}\\\
&\qquad\times\Big{(}(1+\|\,\widetilde{\\!{Z}}_{1}\|^{2})^{2}+\mathbb{E}_{\,\widetilde{\\!{Z}}_{3}}[(1+\|\,\widetilde{\\!{Z}}_{3}\|^{2})^{2}]\Big{)}\bigg{]}\\\
&\leq(2^{6}\times
5^{4})\mathbb{E}_{Z_{1}}\big{[}(1+\|Z_{1}\|^{2})^{8}\big{]}.\end{split}$

Therefore,

$\begin{split}&\mathbb{E}_{\mathbf{Z}_{n},\mathbf{\,\widetilde{\\!{Z}}}_{2}}\Big{[}\tilde{h}_{2}(\mathbf{Z}_{n},\mathbf{\,\widetilde{\\!{Z}}}_{2})^{2}\Big{]}\leq(2\times
5^{4})\Big{(}\frac{2\beta^{2}}{\sigma^{2}}\Big{)}^{2}C_{\theta}^{4}\Big{(}1+2\int_{\Theta}\|\theta\|^{p}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)+8g(\tilde{\gamma}^{\sigma}_{p})\Big{)}^{4}\mathbb{E}_{Z_{1}}[(1+\|Z_{1}\|^{2})^{8}].\end{split}$

The result follows from Theorem 3.7. ∎

##  Appendix E Proofs from Section 5

###### Proof of Lemma 5.3.

We recall that our loss is of the form
$\ell(m,z)=\ell_{o}(\mathbb{E}_{\theta\sim m}[\phi(\theta,x)],y)$, for
$\ell_{o}$ a convex function. It follows that $\ell$ is convex and nonnegative
with respect to $m$.

We write $\partial_{\hat{y}}\ell_{o}$ for the derivative of $\ell_{o}$ with
respect to its first argument. By the chain rule, we can differentiate with
respect to $m$, to obtain, with $\Phi(m,x):=\mathbb{E}_{\theta\sim
m}[\phi(\theta,x)]$,

$\begin{split}\frac{\delta\Phi}{\delta
m}(m,x,\theta)&=\phi(\theta,x)-\Phi(m,x),\\\ \frac{\delta\ell}{\delta
m}(m,z,\theta)&=\partial_{\hat{y}}\ell_{o}(\Phi(m,x),y)\Big{(}\phi(\theta,x)-\Phi(m,x)\Big{)}.\end{split}$
(65)

Note that,

$\frac{\delta^{2}\ell}{\delta
m^{2}}(m,z,\theta,\theta^{\prime})=\frac{\delta}{\delta
m}\left(\frac{\delta\ell}{\delta
m}(\cdot,\cdot,\theta)\right)(m,z,\theta^{\prime})\,,$

and due to the normalization convention, see [Cardaliaguet et al., 2019,
Remark 2.5],

$\begin{split}\frac{\delta^{2}\ell}{\delta
m^{2}}(m,z,\theta,\theta^{\prime})&=\partial_{\hat{y}\hat{y}}\ell_{o}(\Phi(m,x),y)\Big{(}\phi(\theta,x)-\Phi(m,x)\Big{)}\Big{(}\phi(\theta^{\prime},x)-\Phi(m,x)\Big{)}.\end{split}$
(66)

It follows that $\ell$ is $\mathcal{C}^{2}$ with respect to $m$ (the required
bounds on the derivatives will be obtained below).

Without loss of generality, for notational convenience, we assume that
$L_{\ell},L_{\ell,1},L_{\ell,2}$ and $L_{\phi}$ in Assumption 5 are all at
least $1$. Throughout, $c$ is a constant which can vary from line to line, but
does not depend on $n$.

We first consider obtaining bounds on $\ell$. We know that

$\begin{split}\ell(\mathfrak{m}(\nu_{n}),z)&\leq
L_{\ell}(1+\|y\|^{2}+\|\hat{y}\|^{2})=L_{\ell}(1+\|y\|^{2}+\|\Phi(m,x)\|^{2}))\,.\end{split}$

As

$\|\Phi(m,x)\|^{2}=\|\mathbb{E}_{\theta\sim m}[\phi(\theta,x)]\|^{2}\leq
L_{\phi}^{2}(1+\|x\|)^{2}\mathbb{E}_{\theta\sim m}[1+\|\theta\|^{2}]^{2},$

we know

$\begin{split}\ell(\mathfrak{m}(\nu_{n}),z)&\leq
L_{\ell}\big{(}1+\|y\|^{2}+L_{\phi}^{2}(1+\|x\|)^{2}\mathbb{E}_{\theta\sim
m}[1+\|\theta\|^{2}]^{2}\big{)}\\\ &\leq
2L_{\ell}L_{\phi}^{2}\mathbb{E}_{\theta\sim
m}[1+\|\theta\|^{2}]^{2}\big{(}1+\|y\|^{2}+\|x\|^{2}).\end{split}$

We therefore take $g(m):=2L_{\ell}L_{\phi}^{2}\mathbb{E}_{\theta\sim
m}[1+\|\theta\|^{2}]^{2}$. As we know $p\geq 2$ and
$\tilde{\gamma}_{p}^{\sigma}$ is a density in $\mathcal{P}_{p}$, it follows
that $g(\tilde{\gamma}_{p}^{\sigma})<\infty$.

We can also compute, using the above bounds,

$\begin{split}\max_{Z\in\\{Z_{1},\,\widetilde{\\!{Z}}_{1}\\}}\mathbb{E}\big{[}\big{(}\ell(\mathfrak{m}(\nu_{n}),Z)\big{)}^{2}\big{]}&\leq
4L_{\ell}^{2}L_{\phi}^{4}\mathbb{E}_{\mathbf{Z}_{n}}\Big{[}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{n})}[1+\|\theta\|^{2}]^{4}(1+\|Z_{1}\|^{2})^{2}\Big{]}.\end{split}$

As $\mathfrak{m}(\nu_{n})\in B(\nu_{n})$, we know

$\begin{split}\mathbb{E}_{\theta\sim m}[1+\|\theta\|^{2}]^{2}&\leq
2+2\mathrm{R}(\tilde{\gamma}^{\sigma}_{p},\nu_{n})^{2}+2\mathbb{E}_{\theta\sim\tilde{\gamma}^{\sigma}_{p}}[\|\theta\|^{2}]^{2}\\\
&\leq
2+2\frac{1}{n}\sum_{j=1}^{n}\ell(\tilde{\gamma}^{\sigma}_{p},Z_{j})^{2}+2\mathbb{E}_{\theta\sim\tilde{\gamma}^{\sigma}_{p}}[\|\theta\|^{2}]^{2}\\\
&\leq
2+2\frac{1}{n}\sum_{j=1}^{n}4L_{\ell}^{2}L_{\phi}^{4}\mathbb{E}_{\theta\sim\tilde{\gamma}^{\sigma}_{p}}[1+\|\theta\|^{2}]^{4}\big{(}1+\|Z_{j}\|^{2})^{2}+2\mathbb{E}_{\theta\sim\tilde{\gamma}^{\sigma}_{p}}[\|\theta\|^{2}]^{2}.\end{split}$

As $\tilde{\gamma}^{\sigma}_{p}\in\mathcal{P}_{p}$ and $p\geq 2$, we have
$\mathbb{E}_{\theta\sim\tilde{\gamma}^{\sigma}_{p}}[1+\|\theta\|^{2}]^{4}\leq
c$, and hence, applying Lemma D.7,

$\begin{split}\max_{Z\in\\{Z_{1},\,\widetilde{\\!{Z}}_{1}\\}}\mathbb{E}\big{[}\big{(}\ell(\mathfrak{m}(\nu_{n}),Z)\big{)}^{2}\big{]}&\leq
c\mathbb{E}_{\mathbf{Z}_{n}}\Big{[}\Big{(}1+\frac{1}{n}\sum_{j=1}^{n}\big{(}1+\|Z_{j}\|^{2})^{2}\Big{)}^{2}(1+\|Z_{1}\|^{2})^{2}\Big{]}\\\
&\leq c\mathbb{E}_{Z_{1}}\Big{[}(1+\|Z_{1}\|^{2})^{6}\Big{]}.\end{split}$

We now consider the derivative of $\ell$. Writing
$m_{2}:=\mathbb{E}_{\theta\sim m}[\|\theta\|^{2}]$, we have

$\displaystyle\Big{|}\frac{\delta\ell}{\delta
m}\big{(}m,z,\theta\big{)}\Big{|}$
$\displaystyle=\Big{|}\partial_{\hat{y}}\ell_{o}(\Phi(m,x),y)\Big{|}\,|\phi(\theta,x)-\Phi(m,x)|$
$\displaystyle\leq
L_{\ell,1}(1+|\Phi(m,x)|+\|y\|)\big{|}\phi(\theta,x)-\Phi(m,x)\big{|}$
$\displaystyle\leq
L_{\ell,1}L_{\phi}\Big{(}1+L_{\phi}(1+\|x\|)(1+m_{2})+\|y\|\Big{)}(1+\|x\|)\Big{(}2+\|\theta\|^{2}+m_{2}\Big{)}$
$\displaystyle\leq
L_{\ell,1}L_{\phi}(1+L_{\phi})(1+m_{2})\Big{(}2+\|\theta\|^{2}+m_{2}\Big{)}\Big{(}1+\|x\|+\|y\|\Big{)}(1+\|x\|)$
$\displaystyle\leq
2L_{\ell,1}L_{\phi}(1+L_{\phi})\Big{(}2+\|\theta\|^{2}+m_{2}\Big{)}^{2}\Big{(}1+\|x\|^{2}+\|y\|^{2}\Big{)}$
$\displaystyle\leq
6L_{\ell,1}L_{\phi}(1+L_{\phi})\Big{(}4+\|\theta\|^{4}+\mathbb{E}_{\theta\sim
m}[\|\theta\|^{4}]\Big{)}\Big{(}1+\|x\|^{2}+\|y\|^{2}\Big{)}.$

We then take

$g_{1}(m,\theta)=6L_{\ell,1}L_{\phi}(1+L_{\phi})\Big{(}4+\|\theta\|^{4}+\mathbb{E}_{\theta\sim
m}[\|\theta\|^{4}]\Big{)},$

and we have, with $c$ a constant varying from line to line,

$\begin{split}\mathbb{E}_{\theta\sim
m^{\prime}}\big{[}g_{1}(m,\theta)^{2}\big{]}^{1/2}&=c\mathbb{E}_{\theta\sim
m^{\prime}}\Big{[}\Big{(}4+\|\theta\|^{4}+\mathbb{E}_{\theta\sim
m}[\|\theta\|^{4}]\Big{)}^{2}\Big{]}^{1/2}\\\ &\leq
c\Big{(}8+2\mathbb{E}_{\theta\sim
m^{\prime}}[\|\theta\|^{8}]+2\mathbb{E}_{\theta\sim
m}[\|\theta\|^{8}]\Big{)}^{1/2}\\\ &\leq c\Big{(}1+\mathbb{E}_{\theta\sim
m^{\prime}}[\|\theta\|^{8}]+\mathbb{E}_{\theta\sim
m}[\|\theta\|^{8}]\Big{)}.\end{split}$ (67)

Together with Jensen’s inequality, this yields (14) in the case $p\geq 8$.

Finally, we consider the second derivative of $\ell$. We have,

$\begin{split}&\mathbb{E}_{\theta,\theta^{\prime}\sim
m}\mathbb{E}_{z\sim\nu}\Big{[}\Big{(}\frac{\delta^{2}\mathrm{\ell}}{\delta
m^{2}}(m,z,\theta,\theta^{\prime})\Big{)}^{2}\Big{]}\\\
&=\int_{\mathcal{Z}}\Big{[}\partial_{\hat{y}\hat{y}}\ell_{o}(\Phi(m,x),y)\Big{]}^{2}\mathbb{V}_{\theta\sim
m}\Big{(}\phi(\theta,x)\Big{)}\mathbb{V}_{\theta^{\prime}\sim
m}\Big{(}\phi(\theta^{\prime},x)\Big{)}\nu(\mathrm{d}z)\\\
&=\int_{\mathcal{Z}}\Big{[}\partial_{\hat{y}\hat{y}}\ell_{o}(\Phi(m,x),y)\Big{]}^{2}\Big{[}\mathbb{V}_{\theta\sim
m}\Big{(}\phi(\theta,x)\Big{)}\Big{]}^{2}\nu(\mathrm{d}z)\\\ &\leq
c\,\mathbb{E}_{Z\sim\nu}[(1+\|Z\|)^{2}]\mathbb{E}_{\theta\sim
m}\big{[}(1+\|\theta\|^{2})^{2}\big{]}.\\\ \end{split}$ (68)

giving the stated inequalities. As $\nu\in\mathcal{P}_{2}(\mathcal{Z})$, and
assuming $m\in\mathcal{P}_{p}(\Theta)$ for $p\geq 8$, this implies (15). It
follows that Assumption 4 holds whenever $p\geq 8$. ∎

##  Appendix F Application: Expected parametric loss

For comparison with the neural-network setting considered above, we now
introduce a second application of our model, for the expected parametric loss.
As before, we will derive an upper bound on expected generalization error.

##### Expected loss:

Suppose $\theta$ directly captures the relationship between $X$ and $Y$. We
train using a parametric loss function, $(\theta,z)\mapsto\ell_{p}(\theta,z)$,
inspired by [Xu and Raginsky, 2017]. As described in Section 2.1, we describe
learning as a map $\nu_{n}\mapsto\mathfrak{m}(\nu_{n})\in\mathcal{P}(\Theta)$.
We consider the single-observation expected parametric loss

$(m,z)\mapsto\mathbb{E}_{\theta\sim m}[\ell_{p}(\theta,z)].$ (69)

For example, in a least-squares regression problem, take $\theta=(a,b)$ and
$\ell_{p}(\theta,z)=\big{(}y-(a+bx)\big{)}^{2}$. Note that in this case, our
generic loss function is defined as

$\ell(m,z):=\mathbb{E}_{\theta\sim m}[\ell_{p}(\theta,z)].$ (70)

##### WGE of expected loss:

We apply our approach based on functional derivatives to the expected
parametric loss (69). It is worth noting that the WGE, derived from the
expected parametric loss function in (69), is equivalent to the expected
generalization error proposed by [Xu and Raginsky, 2017, Raginsky et al.,
2016]. Let restate Theorem 3.4 in terms of the parametric loss function.

######  Theorem F.1 (Theorem 3.4 in terms of $\ell_{p}(\theta,z)$).

Assume that $|\ell_{p}(\theta,z)|\leq C(1+|\theta|^{2})$, and training map,
$\nu_{n}\mapsto\mathfrak{m}(\nu_{n})$ is differentiable, in the sense of
Definition 2.2. Then,

$\displaystyle\mathrm{gen}(\mathfrak{m}(\nu_{n}),\nu)=\frac{1}{n}\mathbb{E}_{\mathbf{Z_{n}},\,\widetilde{\\!{Z}}_{1}}\bigg{[}\int_{0}^{1}\int_{\Theta}\ell_{p}(\theta,\,\widetilde{\\!{Z}}_{1})\Big{(}\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{(1)}(\tilde{\lambda}),Z_{1})-\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{(1)}(\tilde{\lambda}),\,\widetilde{\\!{Z}}_{1})\Big{)}\\!(\mathrm{d}\theta)\,\mathrm{d}\tilde{\lambda}\bigg{]}\,,$

To demonstrate an easy application of Theorem F.1, we discuss a simple example
of a learning problem, where the representation of the expected generalization
error in Theorem F.1 can be computed exactly, and regularization is not
needed. This example has been previously considered in [Bu et al., 2020,
Aminian et al., 2021a]; we obtain the same results, based on our more abstract
approach.

######  Example F.2 (Gaussian mean estimation).

We consider the problem of estimating the mean $\mu$ of Gaussian random
variable $Z\sim\mathcal{N}(\mu,\tilde{\sigma}^{2})$ with $n$ i.i.d. samples
$\\{Z_{i}\\}_{i=1}^{n}$. We consider the squared parametric loss function
$\ell_{p}(\theta,Z)=(\theta-Z)^{2}$ and the empirical risk minimization
problem is solved by $\theta=\frac{1}{n}\sum_{i=1}^{n}Z_{i}$. Consequently,
with the empirical risk minimizer, we have
$\theta\sim\mathcal{N}(\mu,\frac{\tilde{\sigma}^{2}}{n})$. Therefore, we
suppose the learning map is given by the distribution
$\mathfrak{m}(\nu_{n})=\mathcal{N}(\mathbb{E}_{Z\sim\nu_{n}}[Z],\frac{\tilde{\sigma}^{2}}{n})$.
Then, we have
$\mathrm{gen}(\mathfrak{m}(\nu_{n}),\nu_{\mathrm{pop}})=\frac{2\tilde{\sigma}^{2}}{n}$.

###### Proof of Example F.2.

We compute $\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{n},z;\theta)$ using the
Gaussian density, to give

$\displaystyle\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{n},z;\theta)=\mathfrak{m}(\nu_{n})\frac{n}{\tilde{\sigma}^{2}}(\theta-\mathbb{E}_{Z\sim\nu_{n}}[Z])(z-\mathbb{E}_{Z\sim\nu_{n}}[Z]).$

Recall that
$\nu_{(1)}(\tilde{\lambda})=\nu_{n,(1)}+\tilde{\lambda}(\nu_{n}-\nu_{n,(1)})$.
Note that

$\begin{split}\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]&=\frac{\tilde{\lambda}}{n}\,\widetilde{\\!{Z}}_{1}+\frac{(1-\tilde{\lambda})}{n}Z_{1}+\frac{1}{n}\sum_{j=2}^{n}Z_{j},\\\
\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1)}(\tilde{\lambda}))}[\theta]&=\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z],\\\
\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1)}(\tilde{\lambda}))}[\theta^{2}]&=\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]^{2}+\frac{\tilde{\sigma}^{2}}{n},\\\
\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1)}(\tilde{\lambda}))}[\theta^{3}]&=\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]^{3}+3\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]\frac{\tilde{\sigma}^{2}}{n}.\end{split}$
(71)

From Theorem 3.4 we have

$\displaystyle\mathrm{gen}(\mathfrak{m}(\nu_{n}),\nu)$
$\displaystyle=\frac{1}{n}\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}\int_{0}^{1}\int_{\Theta}(\theta-\,\widetilde{\\!{Z}}_{1})^{2}\Big{(}\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{(1)}(\tilde{\lambda}),Z_{1};\theta)-\frac{\delta\mathfrak{m}}{\delta\nu}(\nu_{(1)}(\tilde{\lambda}),\,\widetilde{\\!{Z}}_{1};\theta)\Big{)}\\!(\mathrm{d}\theta)\mathrm{d}\tilde{\lambda}\Big{]}$
$\displaystyle=\frac{1}{\tilde{\sigma}^{2}}\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}\int_{0}^{1}\int_{\Theta}(\theta-\,\widetilde{\\!{Z}}_{1})^{2}(\theta-\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z])(Z_{1}-\,\widetilde{\\!{Z}}_{1})\mathfrak{m}(\nu_{(1)}(\tilde{\lambda}))\\!(\mathrm{d}\theta)\mathrm{d}\tilde{\lambda}\Big{]}$
$\displaystyle=\frac{1}{\tilde{\sigma}^{2}}\Bigg{(}\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}(Z_{1}-\,\widetilde{\\!{Z}}_{1})\int_{0}^{1}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1)}(\tilde{\lambda}))}\Big{[}\theta(\theta-\,\widetilde{\\!{Z}}_{1})^{2}\Big{]}\mathrm{d}\tilde{\lambda}\Big{]}$
$\displaystyle\quad-\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}(Z_{1}-\,\widetilde{\\!{Z}}_{1})\int_{0}^{1}\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1)}(\tilde{\lambda}))}\Big{[}(\theta-\,\widetilde{\\!{Z}}_{1})^{2}\Big{]}\mathrm{d}\tilde{\lambda}\Big{]}\Bigg{)}$
$\displaystyle=\frac{1}{\tilde{\sigma}^{2}}\Bigg{(}\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}(Z_{1}-\,\widetilde{\\!{Z}}_{1})\int_{0}^{1}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1)}(\tilde{\lambda}))}\Big{[}\theta^{3}-2\theta^{2}\,\widetilde{\\!{Z}}_{1}+\,\widetilde{\\!{Z}}_{1}^{2}\theta)\Big{]}\mathrm{d}\tilde{\lambda}\Big{]}$
$\displaystyle\quad-\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}(Z_{1}-\,\widetilde{\\!{Z}}_{1})\int_{0}^{1}\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{(1)}(\tilde{\lambda}))}\Big{[}\theta^{2}-2\theta\,\widetilde{\\!{Z}}_{1}+\,\widetilde{\\!{Z}}_{1}^{2}\Big{]}\mathrm{d}\tilde{\lambda}\Big{]}\Bigg{)}$
$\displaystyle=\frac{1}{\tilde{\sigma}^{2}}\Bigg{(}\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}(Z_{1}-\,\widetilde{\\!{Z}}_{1})\int_{0}^{1}\Big{(}\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]^{3}+3\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]\frac{\tilde{\sigma}^{2}}{n}$
$\displaystyle\qquad\qquad-2(\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]^{2}+\frac{\tilde{\sigma}^{2}}{n})\,\widetilde{\\!{Z}}_{1}+\,\widetilde{\\!{Z}}_{1}^{2}\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z])\Big{)}\mathrm{d}\tilde{\lambda}\Big{]}$
$\displaystyle\quad-\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}(Z_{1}-\,\widetilde{\\!{Z}}_{1})\int_{0}^{1}\Big{(}\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]^{3}+\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]\frac{\tilde{\sigma}^{2}}{n}$
$\displaystyle\qquad\qquad-2\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]^{2}\,\widetilde{\\!{Z}}_{1}+\,\widetilde{\\!{Z}}_{1}^{2}\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]\Big{)}\mathrm{d}\tilde{\lambda}\Big{]}\Bigg{)}$
$\displaystyle=\frac{2}{n}\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}(Z_{1}-\,\widetilde{\\!{Z}}_{1})\int_{0}^{1}(\mathbb{E}_{Z\sim\nu_{(1)}(\tilde{\lambda})}[Z]-\,\widetilde{\\!{Z}}_{1})\mathrm{d}\tilde{\lambda}\Big{]}$
$\displaystyle=\frac{2}{n}\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}(Z_{1}-\,\widetilde{\\!{Z}}_{1})\int_{0}^{1}\Big{(}\frac{\tilde{\lambda}}{n}\,\widetilde{\\!{Z}}_{1}+\frac{(1-\tilde{\lambda})}{n}Z_{1}+\frac{1}{n}\sum_{j=2}^{n}Z_{j}-\,\widetilde{\\!{Z}}_{1}\Big{)}\mathrm{d}\tilde{\lambda}\Big{]}$
$\displaystyle=\frac{2}{n}\mathbb{E}_{\mathbf{Z_{n}}\,\widetilde{\\!{Z}}_{1}}\Big{[}\Big{(}Z_{1}-\,\widetilde{\\!{Z}}_{1}\Big{)}\Big{(}\frac{1}{2n}(Z_{1}-\,\widetilde{\\!{Z}}_{1})+\frac{1}{n}\sum_{j=2}^{n}Z_{j}\Big{)}\Big{]}$
$\displaystyle=\frac{2\tilde{\sigma}^{2}}{n}.$

∎

##### Parametric Gibbs measure:

For a slightly less trivial example, we will now apply our approach based on
KL-regularized risk minimization to a parametric loss setting. In [Raginsky et
al., 2016, Aminian et al., 2021a] and Kuzborskij et al. [2019], the KL-
regularized expected empirical risk minimization problem (13) is studied with
an expected parametric loss, leading to the following parametric Gibbs measure
(a.k.a. Gibbs algorithm) as solution:

$\displaystyle\mathfrak{m}_{\theta}^{p,\beta,\sigma}(\nu_{n};\theta)=\frac{1}{F_{\beta,\sigma}}\exp\\{-\frac{2\beta^{2}}{\sigma^{2}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\ell_{p}(\theta,Z_{i})+\frac{1}{2\beta^{2}}U(\theta)\Big{]}\Bigg{\\}}.$
(72)

We make the following assumptions on the parametric loss to investigate
generalization performance.

######  Assumption 6.

For a constant $p\geq 2$, the regularizing potential $U$ satisfies
$\lim_{\|\theta\|\to\infty}\frac{U(\theta)}{\|\theta\|^{p}}=\infty,$ the loss
$\ell_{p}$ is nonnegative, and there exists a constant $M_{p}$ such that, for
all $m\in\mathcal{P}_{2}(\Theta)$,

$\begin{split}|\ell_{p}(\theta,z)|&\leq
M_{p}(1+\|\theta\|^{2})(1+\|z\|^{2}).\end{split}$

######  Lemma F.3.

Under Assumption 6, for all $z\in\mathcal{Z}$, $\theta\in\Theta$,
$m\in\mathcal{P}_{p}(\Theta)$, and $\nu\in\mathcal{P}_{2}(\mathcal{Z})$, we
have

$\displaystyle|\ell(m,z)|$ $\displaystyle\leq M_{p}(1+\mathbb{E}_{\theta\sim
m}[\|\theta\|^{2}])(1+\|z\|^{2})$ (73)
$\displaystyle\Big{|}\frac{\delta\ell}{\delta m}(m,z,\theta)\Big{|}$
$\displaystyle\leq M_{p}(2+\mathbb{E}_{\theta\sim
m}[\|\theta\|^{2}]+\|\theta\|^{2})(1+\|z\|^{2})$ (74)
$\displaystyle\max_{Z\in\\{Z_{1},\,\widetilde{\\!{Z}}_{1}\\}}\mathbb{E}\big{[}\big{(}\ell(\mathfrak{m}(\nu_{n}),Z)\big{)}^{2}\big{]}$
$\displaystyle\leq
4M_{p}^{2}\Big{(}2+\mathbb{E}_{\theta\sim\tilde{\gamma}_{p}^{\sigma}}[\|\theta\|^{2}]\Big{)}^{2}\mathbb{E}_{\mathbf{Z}_{n},\,\widetilde{\\!{Z}}_{1}}\Big{[}(1+\|Z_{1}\|^{2})^{4}\Big{]},$
(75) $\displaystyle\mathbb{E}_{\theta,\theta^{\prime}\sim
m}\mathbb{E}_{z\sim\nu}\Big{[}\Big{(}\frac{\delta^{2}\mathrm{\ell}}{\delta
m^{2}}(m,z,\theta,\theta^{\prime})\Big{)}^{2}\Big{]}$ $\displaystyle=0.$ (76)

In particular, if $\mathbb{E}_{Z\sim\nu_{\mathrm{pop}}}[\|Z\|^{8}]<\infty$
then
$\max_{Z\in\\{Z_{1},\,\widetilde{\\!{Z}}_{1}\\}}\mathbb{E}\big{[}\big{(}\ell(\mathfrak{m}(\nu_{n}),Z)\big{)}^{2}\big{]}<\infty.$

###### Proof.

We recall that our loss is of the form $\ell(m,z)=\mathbb{E}_{\theta\sim
m}\big{[}\ell_{p}(\theta,z)\big{]}$. We can differentiate with respect to $m$,
to obtain

$\begin{split}\frac{\delta\ell}{\delta
m}(m,z,\theta)&=\ell_{p}(\theta,z)-\mathbb{E}_{\theta\sim
m}\big{[}\ell_{p}(\theta,z)\big{]},\\\ \frac{\delta^{2}\ell}{\delta
m^{2}}(m,z,\theta,\theta^{\prime})&=0.\end{split}$ (77)

To obtain (73), we calculate

$\begin{split}|\ell(m,z)|&=|\mathbb{E}_{\theta\sim m}[\ell_{p}(\theta,z)]|\leq
M_{p}(1+\mathbb{E}_{\theta\sim m}[\|\theta\|^{2}])(1+\|z\|^{2}).\end{split}$

Therefore, we have

$g(m)=M_{p}(1+\mathbb{E}_{\theta\sim m}[\|\theta\|^{2}]).$

We can compute the functional derivative of expected loss, (74), for all
$m\in\mathcal{P}_{2}(\Theta)$,

$\begin{split}\Big{|}\frac{\delta\ell}{\delta
m}(m,z,\theta)\Big{|}&=\Big{|}\ell_{p}(\theta,z)-\mathbb{E}_{\theta^{\prime}\sim
m}\big{[}\ell_{p}(\theta^{\prime},z)\big{]}\Big{|}\\\ &\leq
M_{p}(2+\mathbb{E}_{\theta^{\prime}\sim
m}[\|\theta^{\prime}\|^{2}]+\|\theta\|^{2})(1+\|z\|^{2}).\end{split}$ (78)

We then take

$\displaystyle g_{1}(m,\theta)=M_{p}(2+\mathbb{E}_{\theta^{\prime}\sim
m}[\|\theta^{\prime}\|^{2}]+\|\theta\|^{2}),$

and we have

$\begin{split}\mathbb{E}_{\theta\sim
m^{\prime}}[g_{1}(m,\theta)^{2}]^{1/2}&=M_{p}\mathbb{E}_{\theta\sim
m^{\prime}}[(2+\mathbb{E}_{\theta^{\prime}\sim
m}[\|\theta^{\prime}\|^{2}]+\|\theta\|^{2})^{2}]^{1/2}\\\ &\leq
2\sqrt{2}M_{p}\Big{(}1+\mathbb{E}_{\theta\sim
m}[\|\theta\|^{4}]+\mathbb{E}_{\theta\sim
m^{\prime}}[\|\theta\|^{4}]\Big{)}.\end{split}$ (79)

For (75), we have,

$\begin{split}\mathbb{E}\big{[}\big{(}\ell(\mathfrak{m}(\nu_{n}),Z)\big{)}^{2}\big{]}&=\mathbb{E}_{\mathbf{Z}_{n},Z}\Big{[}\Big{(}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{n})}[\ell_{p}(\theta,Z)]\Big{)}^{2}\Big{]}\\\
&\leq
M_{p}^{2}\mathbb{E}_{\mathbf{Z}_{n},Z}\Big{[}\Big{(}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{n})}[(1+\|\theta\|^{2})](1+\|Z\|^{2})\Big{)}^{2}\Big{]}.\end{split}$
(80)

From Lemma D.1, we know

$\begin{split}\mathbb{E}_{\theta\sim\mathfrak{m}(\nu_{n})}\big{[}\|\theta\|^{2}\big{]}&\leq\mathrm{R}(\tilde{\gamma}_{p}^{\sigma},\nu_{n})+\int_{\Theta}\|\theta\|^{2}\tilde{\gamma}_{p}^{\sigma}(\mathrm{d}\theta)\\\
&\leq(1+\mathbb{E}_{\theta\sim\tilde{\gamma}_{p}^{\sigma}}[\|\theta\|^{2}])\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})+\mathbb{E}_{\theta\sim\tilde{\gamma}_{p}^{\sigma}}[\|\theta\|^{2}]\\\
&\leq\Big{(}1+\mathbb{E}_{\theta\sim\tilde{\gamma}_{p}^{\sigma}}[\|\theta\|^{2}]\Big{(}1+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})\Big{)}\Big{)}.\end{split}$
(81)

Substituting (81) in (80), we have,

$\begin{split}\mathbb{E}\big{[}\big{(}\ell(\mathfrak{m}(\nu_{n}),Z)\big{)}^{2}\big{]}&\leq
M_{p}^{2}\mathbb{E}_{\mathbf{Z}_{n},Z}\Big{[}\Big{(}2+\mathbb{E}_{\theta\sim\tilde{\gamma}_{p}^{\sigma}}[\|\theta\|^{2}]\Big{(}1+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})\Big{)}\Big{)}(1+\|Z\|^{2})\Big{)}^{2}\Big{]}\\\
&\leq
M_{p}^{2}\Big{(}2+\mathbb{E}_{\theta\sim\tilde{\gamma}_{p}^{\sigma}}[\|\theta\|^{2}]\Big{)}^{2}\mathbb{E}_{\mathbf{Z}_{n},Z}\Big{[}\Big{(}\Big{(}1+\frac{1}{n}\sum_{j=1}^{n}(1+\|Z_{j}\|^{2})\Big{)}(1+\|Z\|^{2})\Big{)}^{2}\Big{]}\\\
&\leq
4M_{p}^{2}\Big{(}2+\mathbb{E}_{\theta\sim\tilde{\gamma}_{p}^{\sigma}}[\|\theta\|^{2}]\Big{)}^{2}\mathbb{E}_{Z\sim\nu_{\mathrm{pop}}}\Big{[}(1+\|Z\|^{2})^{4}\Big{]}.\end{split}$
(82)

∎

In the following, we derive upper bounds on WGE and LGE of the parametric
Gibbs measure by combining Lemma F.3 with Theorems 4.2 and 4.3, respectively.

######  Proposition F.4 (WGE and the parametric Gibbs measure).

Assume that Assumption 6 and
$\mathbb{E}_{Z\sim\nu_{\mathrm{pop}}}\big{[}\|Z\|^{8}\big{]}<\infty$ hold.
Then, the following upper bound holds on the WGE of the parametric Gibbs
measure

$|\mathrm{gen}(\mathfrak{m}(\nu_{n}),\nu_{\mathrm{pop}})|\leq\frac{c}{n}\frac{2\beta^{2}}{\sigma^{2}}\mathbb{E}_{Z_{1}}\Big{[}\big{(}1+\|Z_{1}\|^{2}\big{)}^{4}\Big{]}$

where $c<\infty$ is independent of $n$.

By leveraging the property of the parametric Gibbs measure being
differentially private for bounded parametric loss functions, as stated in [Xu
and Raginsky, 2017, Theorem 1], a sub-optimal bound, i.e.,
$|\mathrm{gen}(\mathfrak{m}^{\beta,\sigma}(\nu_{n}),\nu_{\mathrm{pop}})|\leq\sqrt{\frac{\beta^{2}}{\sigma^{2}n}}$,
can be obtained. However, a tighter upper bound, i.e.,
$|\mathrm{gen}(\mathfrak{m}^{\beta,\sigma}(\nu_{n}),\nu_{\mathrm{pop}})|\leq\frac{\beta^{2}}{2\sigma^{2}n}$,
can be derived by further examinination with a bounded loss assumption using
Hoeffding’s lemma, as demonstrated in [Raginsky et al., 2016]. This tighter
bound exhibits a similar rate of decay, namely $\mathcal{O}\big{(}1/n\big{)}$.
Another upper bound, i.e.,
$\mathrm{gen}(\mathfrak{m}^{\beta,\sigma}(\nu_{n}),\nu_{\mathrm{pop}})\leq\frac{4\gamma^{2}\beta^{2}}{\sigma^{2}n}$,
is established in [Kuzborskij et al., 2019, Theorem 1], albeit under a
different assumption that $\ell_{p}(\theta,z)$ is $\gamma$-sub-Gaussian under
the parametric Gibbs measure, i.e., $\mathfrak{m}^{\beta,\sigma}(\nu_{n})$.
Similarly, [Aminian et al., 2021a, Theorem 2] presents an upper bound, i.e.,
$\mathrm{gen}(\mathfrak{m}^{\beta,\sigma}(\nu_{n}),\nu_{\mathrm{pop}})\leq\frac{2\gamma^{2}\beta^{2}}{\sigma^{2}n}$,
assuming that the parametric loss function is $\gamma$-sub-Gaussian under the
distribution $\nu_{\mathrm{pop}}$ for all $\theta\in\Theta$.

In contrast to the aforementioned studies, we adopt a weaker assumption in
this work, namely that $\nu_{\mathrm{pop}}$ possesses a finite 8th moment.
This condition holds for sub-Gaussian distributions, as well as numerous
others such as the Student’s $t$ distribution with more than $8$ degrees of
freedom or lognormal distributions. Making the stronger assumption that
$\nu_{\mathrm{pop}}$ possesses a finite $16$th moment (which is still weaker
than assuming it is sub-Gaussian), we can apply Theorem 4.3 to give a bound on
the strong generalization error.

######  Proposition F.5 (LGE and the parametric Gibbs measure).

Assume that Assumption 6 and
$\mathbb{E}_{Z\sim\nu_{\mathrm{pop}}}\big{[}\|Z\|^{16}\big{]}<\infty$ hold.
Then, the following upper bound holds on the $L_{2}$ generalization error of
the parametric Gibbs measure

$\begin{split}|\mathrm{gen}_{L_{2}}(\mathfrak{m}^{\beta,\sigma}(\nu_{n}),\nu_{\mathrm{pop}})|\leq\frac{1}{n}\Big{(}4K_{1}+2K_{1}^{1/2}A^{1/2}+\frac{A}{n}\Big{)},\end{split}$
(83)

where, for some $c>0$ independent of $n$,

$\begin{split}A&=c\,\mathbb{E}_{Z_{1}}[(1+\|Z_{1}\|^{2})^{8}]<\infty,\\\
K_{1}&=c\,\mathbb{E}_{Z_{1}}\Big{[}(1+\|Z\|^{2})^{4}\Big{]}<\infty.\end{split}$