the available data-independent bounds can be recovered as relaxed versions of data-dependent bounds.

Classical PAC bounds on the generalization error, such as those based on the Vapnik-Chervonenkis (VC) dimension [@shalev-shwartz14-a p. 67], are probabilistic bounds of a stronger variety than the PAC-Bayesian and single-draw bounds just introduced. Indeed, they hold uniformly for *all* $w\in \mathcal{W}$ under $P_{{\boldsymbol{Z}}}$. As a consequence, these bounds depend on structural properties of the hypothesis class $\mathcal{W}$ rather than on properties of the algorithm, and tend to be crude when applied to modern machine learning algorithms [@Zhang-16].

#### Prior Work {#prior-work .unnumbered}

By generalizing a result obtained in [@russo16-05b] in the context of adaptive data analysis, Xu and Raginsky [@xu17-05a] obtained a bound on the average generalization error in terms of the mutual information $I(W;{\boldsymbol{Z}})$ between the the output hypothesis $W$ and the training data ${\boldsymbol{Z}}$. A drawback of the bound in [@xu17-05a] is that it is vacuous whenever the joint distribution $P_{W\!{\boldsymbol{Z}}}$ is not absolutely continuous with respect to $P_W\!P_{{\boldsymbol{Z}}}$, the product of the marginal distributions of $W$ and ${\boldsymbol{Z}}$. This occurs, for example, when $W$ is given by a deterministic function of ${\boldsymbol{Z}}$, and $W$ and ${\boldsymbol{Z}}$ are separately continuous random variables. In [@Bu-19-ISIT], 