survey of the vast PAC-Bayesian literature, which is beyond the scope of this paper, can be found in, e.g., [@guedj19-01a].

Finally, we survey the single-draw bounds that are relevant for our discussion. In addition to the aforementioned average and PAC-Bayesian bounds, both Xu and Raginsky [@xu17-05a Thm. 3] and Bassily *et al.* [@bassily18-02a] also provided single-draw generalization bounds in terms of mutual information. For both of them, the dependence on $\delta$ is of order $1/\delta$. In [@esposito19-12a], Esposito *et al.* provided bounds in terms of a whole host of information-theoretic quantities, such as the Rényi divergence, the $\alpha$-mutual information, and the maximal leakage. An interesting aspect of their $\alpha$-mutual information bound is that, unlike the mutual information bounds in [@xu17-05a Thm. 3] and [@bassily18-02a], it is a high-probability bound. However, this bound does not imply a stronger mutual information bound. Indeed, if one lets $\alpha \rightarrow 1$, for which the $\alpha$-mutual information reduces to the ordinary mutual information, the bound becomes vacuous. Bounds on the average generalization error are also provided [@esposito19-12a Sec. III.D], but these are generally weaker than the mutual information bounds in [@xu17-05a]. In the same vein, Dwork *et al.* derived single-draw generalization bounds in terms of 