As noted in Remark \[rem:uncond\_conversion\_to\_Q\_bounds\], we can substitute an arbitrary $Q_W$ for $P_W$ in , provided that the necessary absolute continuity criterion is fulfilled. This leads to a more general bound involving the relative entropy $\relent{P_{W\!{\boldsymbol{Z}}}}{Q_W\!P_{{\boldsymbol{Z}}} }$.

PAC-Bayesian Generalization Error Bounds {#sec:uncond_pacb}
----------------------------------------

We now turn to PAC-Bayesian bounds of the form given in . In the following corollary, we reobtain a known data-dependent bound and present a novel data-independent relaxation.

\[cor:pacb\_uncond\] Under the setting of Theorem \[thm:unconditional\_subgaussian\], the following holds with probability at least $1-\delta$ under $P_{{\boldsymbol{Z}}}$ for all $t>0$:

[rCl]{}\[eq:cor\_pacb\_uncond\] &&\
\[eq:cor\_pacb\_uncond\_second\] && .

Here, the first inequality yields a data-dependent bound, while the second inequality provides a data-independent relaxation.

As in Corollary \[cor:exp\_uncond\], we start from  and use Jensen’s inequality, but now only with respect to $P_{W\vert {\boldsymbol{Z}}}$. This leads to $$\label{eq:pacb_uncond_after_jensen}
\Exop_{P_{{\boldsymbol{Z}}}}\lefto[\exp\left(\lambda \Ex{P_{W\vert {\boldsymbol{Z}}} }{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}} - \frac{\lambda^2\sigma^2}{2n}-\relent{P_{W\!\given\! {\boldsymbol{Z}}}}{P_W}
\right) \right] \leq 1$$ where we used that, for a fixed ${\boldsymbol{Z}}$, $$\Ex{P_{W\vert {\boldsymbol{Z}}}}{\imath(W,{\boldsymbol{Z}})}=\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}.$$ Next, we use the following result. Let $U\distas P_U$ be a nonnegative random variable satisfying $\Ex{}{U}\leq 1$. Then, Markov’s inequality implies that $$\label{eq:markov_inequality_Pu}
P_U[U\leq 1/\delta]\geq 1- \Ex{ }{U}\delta\geq 1- \delta.$$ By applying  to the random variable in , we obtain $$P_{{\boldsymbol{Z}}}\lefto[\exp\lefto(\lambda \Ex{P_{W\vert {\boldsymbol{Z}}} 