Bu *et al.* rectified this by obtaining a tighter bound in terms of the individual-sample mutual information $I(W;Z_i)$, which can be bounded even when $I(W;{\boldsymbol{Z}})=\infty$. In [@Asadi2018], Asadi *et al.* combined the mutual information bound with the chaining technique [@vanHandel-16], which exploits structure in the hypothesis class to tighten bounds. In some cases, this is shown to give stronger bounds than either the mutual information bound or the chaining bound individually.

To be evaluated, all of the aforementioned bounds require knowledge of the marginal distribution $P_W$, which depends on the data distribution $P_Z$. In practice, this data distribution is unknown, making the marginal $P_W$ intractable. In light of this, Achille and Soatto [@Achille-18] provided an upper bound on the mutual information between the training data and the output hypothesis in terms of the relative entropy between $P_{W\vert{\boldsymbol{Z}}}$ and a fixed, auxiliary distribution on the hypothesis space $\mathcal{W}$, and showed that this results in a computable upper bound on the average generalization error. Similarly, Negrea *et al.* [@Negrea2019] provided generalization bounds in terms of an auxiliary, possibly data-dependent distribution on $\mathcal{W}$. This weakens the bound, but makes it computable. Their use of the expected square root of the relative entropy $\relent{P_{W\vert 