} {{{\textnormal{gen}}(W,{\boldsymbol{Z}})}} - \frac{\lambda^2\sigma^2}{2n}-\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}
\right) \leq \frac{1}{\delta} 
\right] \geq  1-\delta.$$ Reorganizing terms, we conclude that $$\label{eq:uncond_pacb_proof_markov_pz}
    P_{{\boldsymbol{Z}}}\lefto[\frac{\lambda^2\sigma^2}{2n} -\lambda \Ex{P_{W\vert {\boldsymbol{Z}}} } {{{\textnormal{gen}}(W,{\boldsymbol{Z}})}} 
    +\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W} +\log\frac{1}{\delta} \geq 0 
\right] \geq 1-\delta$$ from which  follows after setting $\lambda=n\Exop_{P_{W\vert {\boldsymbol{Z}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}\right]/\sigma^2$. To prove , we apply Markov’s inequality to the random variable $\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}^t$, which after some manipulation yields $$\label{eq:uncond_pacb_proof_markov_with_t}
P_{{\boldsymbol{Z}}}\lefto[\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W} \leq 
\frac
    {\Exop^{1/t}_{P_{{\boldsymbol{Z}}}}\lefto[\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}^t\right] }
    {\delta^{1/t}} \right]
    \geq 1-\delta.$$ We now use the union bound to combine  with  and perform the substitution $\delta\rightarrow \delta/2$, after which  follows.

Note that by setting $t=1$ in , we get $\Exop_{P_{{\boldsymbol{Z}}}}\lefto[\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W} \right]=I(W;{\boldsymbol{Z}})$. This choice recovers the result reported in [@bassily18-02a App. 3]. Instead, if we let $t\rightarrow \infty$, the polynomial $\delta$-dependence in  disappears and the bound becomes a high-probability bound. This illustrates that one can get progressively better dependence on $\delta$ by letting the bound depend on higher moments of $\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}$. The tightness of the resulting bound depends on how well one can control these higher moments. Finally, as per Remark \[rem:uncond\_conversion\_to\_Q\_bounds\], we can obtain more general bounds by replacing $P_W$ in  and  with an arbitrary $Q_W$ that satisfies a suitable absolute continuity property.

Single-Draw Generalization Error Bounds {#sec:uncond_sd}
---------------------------------------

We now turn 