and Random-Subset Settings {#standard-and-random-subset-settings .unnumbered}

Let $\mathcal{Z}$ be the instance space, $\mathcal{W}$ be the hypothesis space, and $\ell:\mathcal{W}\times\mathcal{Z}\rightarrow \reals^+$ be the loss function. In the standard setting, $n$ training samples ${\boldsymbol{Z}}=(Z_1,\dots,Z_n)$ are available. These $n$ samples constitute the training data. We assume that all entries of ${\boldsymbol{Z}}$ are drawn independently from some unknown distribution $P_Z$ on $\mathcal{Z}$. In the random-subset setting, $2n$ training samples ${\widetilde{\boldsymbol{Z}}}=(\tilde Z_1,\dots,\tilde Z_{2n})$ are available, with all entries of ${\widetilde{\boldsymbol{Z}}}$ being drawn independently from $P_Z$. However, only a randomly selected subset of cardinality $n$ is actually used as the training data. Following [@steinke20-a], we assume that the training data ${\boldsymbol{Z}}({\boldsymbol{S}})$ is selected as follows. Let ${\boldsymbol{S}}=(S_1,\dots,S_n)$ be an $n$-dimensional random vector, the elements of which are drawn independently from a $\mathrm{Bern}(1/2)$ distribution and are independent of ${\widetilde{\boldsymbol{Z}}}$. Then, for $i=1,\dots,n$, the $i$th training sample in ${\boldsymbol{Z}}({\boldsymbol{S}})$ is $Z_i(S_i)=\tilde Z_{i+S_in}$. A randomized learning algorithm is a conditional distribution $P_{W\vert {\boldsymbol{Z}}}$. We let $L_{{\boldsymbol{Z}}}(W)=\tfrac{1}{n}\sum_{i=1}^n\ell(w,Z_i)$ denote the empirical loss and $L_{P_Z}(W)=\Exop_{P_Z}[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}]$ the population loss. The generalization error is defined as ${{\textnormal{gen}}(W,{\boldsymbol{Z}})}= L_{P_Z}(W)-L_{{\boldsymbol{Z}}}(W)$.

#### Information Measures {#information-measures .unnumbered}

A quantity that will appear in many of our bounds is the information density, defined as $$\label{eq:def_info_dens}
\imath(W,{\boldsymbol{Z}}) = \log \frac{\dv P_{W\!{\boldsymbol{Z}}} 