with probability at least $1-\delta$ under the product distribution $P_{{\boldsymbol{Z}}}$. Here, $\delta\in(0,1)$ is the so-called confidence parameter. Bounds of this type, which are typically referred to as *probably approximately correct (PAC)-Bayesian* bounds [@mcallester98-07a; @guedj19-01a], are relevant for the scenario in which a new hypothesis $W$ is drawn from $P_{W\vert {\boldsymbol{Z}}}$ every time the algorithm is used. For the scenario in which $W$ is drawn from $P_{W\vert {\boldsymbol{Z}}}$ only once—a setup that, following the terminology in [@catoni07-a], we shall refer to as *single-draw*—one may instead be interested in obtaining an upper bound on $\abs{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}}$ that holds with probability at least $1-\delta$ under the joint distribution $P_{W\!{\boldsymbol{Z}}}$. If the dependence of a probabilistic bound (PAC-Bayesian or single-draw) on $\delta^{-1}$ is at most logarithmic, the bound is usually referred to as a *high-probability* bound. Furthermore, a probabilistic bound is termed *data-independent* if it does not depend on the specific instance of ${\boldsymbol{Z}}$, and *data-dependent* if it does. Data-independent bounds allow one to characterize the sample complexity [@shalev-shwartz14-a p. 44], defined as the minimum number of training samples needed to guarantee that the generalization error is within a desired range, with a desired confidence level. However, data-dependent results are often tighter. Indeed, many of 