average $(1/n)\sum_{i=1}^n X_i$ is $\sigma/\sqrt{n}$-subgaussian.

Generalization Bounds for the Standard Setting {#sec:uncond_results}
==============================================

In this section, we study the standard setting described in Section \[sec:preliminaries\]. We will assume that the loss function $\ell(w,Z)$ is $\sigma$-subgaussian under $P_Z$ for all $w\in\mathcal{W}$. This means that, for all $\lambda\in\reals$ and for all $w\in\mathcal{W}$, $$\label{eq:subgaussian_def}
\Exop_{P_Z}\lefto[ \exp\lefto(\lambda(\Exop_{P_Z}\lefto[\ell(w,Z)\right]-\ell(w,Z) \right) \right]\leq \exp\lefto(\frac{\lambda^2\sigma^2}{2}\right).$$ We will derive bounds on the generalization error of a probabilistic learning algorithm $P_{W\vert {\boldsymbol{Z}}}$ in terms of some function of the information density . As previously mentioned, several different notions of generalization error bounds have been investigated in the literature. One such notion is that of average generalization bounds, where we want to find an $\epsilon$ such that $$\label{eq:uncond_exp_generalization_bound_def}
\abs{\Exop_{P_{W\!{\boldsymbol{Z}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}\right]} \leq \epsilon.$$ This $\epsilon$ will in general depend on the joint distribution $P_{W\!{\boldsymbol{Z}}}$, on properties of the loss function, and on the cardinality $n$ of the training data. We will study this type of bounds in Section \[sec:uncond\_exp\].

Another approach, typically studied in the PAC-Bayesian literature, is to find probabilistic bounds of the following form: with probability at least $1-\delta$ under $P_{{\boldsymbol{Z}}}$, $$\label{eq:uncond_pacb_generalization_bound_def}
\abs{\Exop_{P_{W\vert {\boldsymbol{Z}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}\right]} \leq \epsilon.$$ This bound is interesting when we have a fixed data set ${\boldsymbol{Z}}$, but draw a new 