root of the $t$th central moment of $\imath(W,{\boldsymbol{Z}})$: $$\label{eq:def_M_P_WZn}
M_t(W;{\boldsymbol{Z}}) = \Exop^{1/t}_{P_{W\! {\boldsymbol{Z}}}}\lefto[\abs{ \imath(W,{\boldsymbol{Z}}) - \relent{P_{W\!{\boldsymbol{Z}}}}{P_W\!P_{{\boldsymbol{Z}}} }}^t \right].$$

By directly applying Markov’s inequality  to , we conclude that $$P_{W\! {\boldsymbol{Z}}}\lefto[\exp\biggo(\lambda {{\textnormal{gen}}(W,{\boldsymbol{Z}})}- \frac{\lambda^2\sigma^2 }{2n}
-\imath(W,{\boldsymbol{Z}}) \right)\leq \frac{1}{\delta} \bigg] \geq 1-\delta$$ from which  follows after setting $\lambda=n{{\textnormal{gen}}(W,{\boldsymbol{Z}})}/\sigma^2$. To prove , we use Markov’s inequality in the following form: for a random variable $U\distas P_U$, the following holds for all $t>0$: $$\label{eq:markov_for_arbitrary_u}
P_U\lefto[U \leq \Exop[U]+ \frac{\Exop^{1/t}[\abs{U-\Exop[U]}^t]}{\delta^{1/t}} \right]\geq 1-\delta.$$ Applying  with $U=\imath(W,{\boldsymbol{Z}})$ and using the union bound to combine the resulting inequality with , we obtain  after performing the substitution $\delta \rightarrow \delta/2$.

As usual, we can obtain more general bounds by substituting $Q_W$ for $P_W$ in Corollary \[cor:singledraw\_uncond\], provided that the necessary absolute continuity assumption is satisfied.

Similarly to what we noted for the PAC-Bayesian bound , the $\delta$-dependence in  can be made more benign by letting the bound depend on higher central moments of ${{\imath}(W,{\boldsymbol{Z}})}$, but the tightness of the resulting bound hinges on how well one can control these higher moments. In particular, if we let $t\rightarrow \infty$ in , we obtain the following high-probability bound: $$\label{eq:cor_singledraw_uncond_t_inf}
    \abs{  {{\textnormal{gen}}(W,{\boldsymbol{Z}})}} \leq  
     \sqrt{\frac{2\sigma^2}{n}\left(I(W;{\boldsymbol{Z}})+{M_\infty(W;{\boldsymbol{Z}})} +\log \frac{2}{\delta}\right)}.$$ Here, ${M_\infty(W;{\boldsymbol{Z}})}$ is given by $$\label{eq:def_M_infinity}
 M_\infty(W;{\boldsymbol{Z}})=\esssup_{P_{W\!{\boldsymbol{Z}}}} \abs{\imath(W,{\boldsymbol{Z}})- 