hypothesis according to $P_{W\vert {\boldsymbol{Z}}}$ each time we want to use our algorithm. We derive bounds of this type in Section \[sec:uncond\_pacb\].

Finally, we also consider the single-draw scenario. In this setting, we are interested in bounds of the following flavor: with probability at least $1-\delta$ under $P_{W\!{\boldsymbol{Z}}}$, $$\label{eq:uncond_singledraw_generalization_bound_def}
\abs{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}} \leq \epsilon.$$ This type of result is relevant when we draw a single hypothesis $W$ based on our training data, and want to bound the generalization error of this particular $W$ with high probability. The probabilistic bounds in  and  are said to be high-probability bounds if the dependence of $\epsilon$ on the confidence parameter $\delta$ is at most of order $\log(1/\delta)$.

In Theorem \[thm:unconditional\_subgaussian\] below, we present an exponential inequality that will be used in Section \[sec:uncond\_exp\], Section \[sec:uncond\_pacb\], and Section \[sec:uncond\_sd\] to derive generalization bounds of all three flavors.

\[thm:unconditional\_subgaussian\] Let ${\boldsymbol{Z}}=(Z_1,\dots,Z_n)\in\mathcal{Z}^n$ consist of $n$ training samples generated from $P_Z$, and let $P_{W\vert {\boldsymbol{Z}}}$ be a probabilistic learning algorithm. Assume that $\ell(w,Z): \mathcal{W}\times \mathcal{Z}\rightarrow \reals$ is $\sigma$-subgaussian under $P_Z$ for all $w\in \mathcal W$. Also, assume that $P_{W\!{\boldsymbol{Z}}}$ is absolutely continuous with respect to $P_W\!P_{{\boldsymbol{Z}}}$. Then, for all $\lambda\in \reals$, $$\label{eq:unconditional_subgaussian_thm}
    \Exop_{P_{W\! {\boldsymbol{Z}}}}\lefto[{\exp\lefto(\lambda {{\textnormal{gen}}(W,{\boldsymbol{Z}})}-\frac{\lambda^2\sigma^2}{2n}-\imath(W,{\boldsymbol{Z}})  \right)}\right]\leq 1.$$

Since $\ell(w,Z)$ is 