---
abstract: 'We present a general approach, based on an exponential inequality, to derive bounds on the generalization error of randomized learning algorithms. Using this approach, we provide bounds on the average generalization error as well as bounds on its tail probability, for both the PAC-Bayesian and single-draw scenarios. Specifically, for the case of subgaussian loss functions, we obtain novel bounds that depend on the information density between the training data and the output hypothesis. When suitably weakened, these bounds recover many of the information-theoretic available bounds in the literature. We also extend the proposed exponential-inequality approach to the setting recently introduced by Steinke and Zakynthinou (2020), where the learning algorithm depends on a randomly selected subset of the available training data. For this setup, we present bounds for bounded loss functions in terms of the conditional information density between the output hypothesis and the random variable determining the subset choice, given all training data. Through our approach, we recover the average generalization bound presented by Steinke and Zakynthinou (2020) and extend it to the PAC-Bayesian and single-draw scenarios. For the single-draw scenario, we also obtain novel bounds in terms of the conditional $\alpha$-mutual information and the conditional maximal leakage.'
author:
- 'Fredrik Hellström, , Giuseppe Durisi,  [^1] [^2] [^3]'
bibliography:
- 'reference.bib'
title: Generalization Bounds via Information Density and Conditional Information Density
---

Introduction {#sec:introduction}
============

A randomized learning algorithm $P_{W\vert {\boldsymbol{Z}}}$ consists of a probabilistic mapping from a set of training data ${\boldsymbol{Z}}=(Z_1,\dots,Z_n)\in \mathcal{Z}^n$, which we assume to have been generated independently from an unknown distribution $P_Z$ on the instance space $\mathcal{Z}$, to an output hypothesis $W\in\mathcal{W}$, where $\mathcal{W}$ is the hypothesis space. The goal is to find a hypothesis $W$ that results in a small expected loss $L_{P_Z}(W)= \Exop_{P_Z}[\ell(W,Z)]$, where $\ell(\cdot,\cdot)$ is some suitably chosen loss function. A typical strategy to achieve this goal is *empirical risk minimization*, according to which $W$ is selected so as to minimize the empirical loss $L_{{\boldsymbol{Z}}}(W)=\tfrac{1}{n}\sum_{i=1}^n\ell(W,Z_i)$. A central objective in statistical learning theory is to determine when this choice results in a small population loss $L_{P_Z}(W)$. To this end, one seeks to bound the *generalization error*, defined as $\textnormal{gen}(W,{\boldsymbol{Z}}) = L_{P_Z}(W)-L_{{\boldsymbol{Z}}}(W)$. Since the learning algorithm is randomized, bounds on ${{\textnormal{gen}}(W,{\boldsymbol{Z}})}$ can come in several flavors. One possibility is to bound the average generalization error $\abs{\Exop_{P_{W\!{\boldsymbol{Z}}}}[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}]}$. In practice, one might be more interested in an upper bound on $\abs{\Exop_{P_{W\vert {\boldsymbol{Z}}}}[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}]}$ that holds 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 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], 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 {\boldsymbol{Z}}}}{P_W}$, which they call *disintegrated* mutual information, in place of the mutual information leads to further improvements on the basic bound.

Recent studies, starting with the work of Steinke and Zakynthinou [@steinke20-a], have considered a setting with more structure, where it is assumed that a set ${\widetilde{\boldsymbol{Z}}}$ consisting of $2n$ independent and identically distributed () training samples from $P_Z$ is available, and that ${\boldsymbol{Z}}$ is formed by selecting $n$ entries of ${\widetilde{\boldsymbol{Z}}}$ at random. We will refer to this setup as the *random-subset setting*, and call the setting without this additional structure the *standard setting*. In the random-subset setting, the average generalization error can be bounded by a quantity that depends on the conditional mutual information between the output hypothesis and the random variable that determines the selected training data ${\boldsymbol{Z}}$, given ${\widetilde{\boldsymbol{Z}}}$ [@steinke20-a Thm. 5.1]. One advantage of this bound over the standard mutual information bound is that the conditional mutual information is always bounded. This broadens the applicability of the bound and results in tighter estimates. Also, as discussed in [@steinke20-a Sec. 4], the conditional mutual information that appears in the bound has strong connections to classical generalization measures, such as VC dimension, compressibility, and stability. In [@Haghifam2020], Haghifam *et al.* provided an individual-sample strengthening of this result, as well as improvements through their use of disintegration. In all of these derivations, the loss function is required to be bounded, which is a stronger requirement than what is needed in the standard setting.

All of the information-theoretic results discussed so far pertain to bounds on the average generalization error. In [@bassily18-02a App. A.3], Bassily *et al.* provided a PAC-Bayesian bound in terms of mutual information. This bound is essentially a data-independent relaxation of a well-known data-dependent bound from the PAC-Bayesian literature [@guedj19-10a]. The dependence of the original data-dependent PAC-Bayesian bound on the confidence parameter $\delta$ is of order $\log(1/\delta)$, making it a high-probability bound. However, its mutual information relaxation in [@bassily18-02a] has a less benign $1/\delta$-dependence. PAC-Bayesian techniques have recently found some success in producing non-vacuous generalization bounds for (randomized) deep neural networks. In [@Dziugaite2017], Dziugaite and Roy optimized a PAC-Bayesian bound to get non-vacuous generalization estimates for a simple neural network setup. In [@zhou2018nonvacuous], Zhou *et al.* derived a bound for compressed networks, i.e., small neural networks that are formed by pruning larger ones, and illustrated numerically that the bound is non-trivial for realistic settings. An extensive 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 other algorithmic stability measures, such as differential privacy [@Dwork-14] and (approximate) max-information [@dwork15-06a]. These bounds are of the high-probability variety, but are typically weaker than the aforementioned maximal leakage bound [@esposito19-12a Sec. V]. All of the single-draw bounds mentioned here are data-independent.

#### Contributions {#contributions .unnumbered}

In this paper, we derive bounds of all three flavors—average, PAC-Bayesian, and single-draw—for both the standard setting and the random-subset setting. In the standard setting, we use the subgaussianity of the loss function, together with a change of measure argument, to obtain an exponential inequality in terms of the *information density* between the hypothesis $W$ and the training data ${\boldsymbol{Z}}$. This exponential inequality provides a framework that can be used to recover several known results, which were originally derived using a host of different tools. In this sense, it provides a unifying approach for deriving information-theoretic generalization bounds. Through simple manipulations of the exponential inequality, we recover the average generalization bound in [@xu17-05a Thm. 1] and the data-dependent PAC-Bayesian bound in [@guedj19-10a Prop. 3]. We also derive a novel data-dependent single-draw bound. Moreover, by further relaxing the PAC-Bayesian bound and the single-draw bound, we obtain two novel data-independent bounds that are explicit in the $t$th moments of the relative entropy $\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}$ and of the information density, respectively. The dependence of these bounds on the confidence parameter $\delta$ is of order $1/\delta^t$. This is more favorable than that of similar bounds reported in [@xu17-05a] and [@bassily18-02a], which have a dependence of order $1/\delta$. The moment bounds that we obtain illustrate that tighter estimates of the generalization error are available with higher confidence if the higher moments of the information measures that the bounds depend on are sufficiently small. Through a more refined analysis, we also derive a high-probability data-independent single-draw bound that is as simple to compute as the maximal leakage bound in [@esposito19-12a Cor. 10], but tighter in some cases. Finally, by using a different approach that relies on tools from binary hypothesis testing, we obtain a data-independent single-draw bound in terms of the tail of the information density. Similarly to the moment bounds, this bound illustrates that the faster the decay of the tail of the information density random variable, the more benign the dependence of the bound on $\delta$.

Moving to the random-subset setting, we establish an exponential inequality, similar to that for the standard setting, in terms of the *conditional information density* between the hypothesis and a random variable that selects the data to be used for training, given all data samples. This exponential inequality is derived under the more stringent assumption of a bounded loss function. Then, we use this inequality to reobtain the average generalization bound in [@steinke20-a Cor. 5.2], and to derive novel PAC-Bayesian and single-draw bounds, both of data-dependent and of data-independent flavor. Similarly to the standard setting, we also obtain a bound that is explicit in the tail of the conditional information density by using tools from binary hypothesis testing. Finally, inspired by [@esposito19-12a], we derive a parametric inequality that can be used to obtain data-independent single-draw bounds. Using this inequality, we extend the results in [@esposito19-12a] for bounded loss functions to the random-subset setting, and obtain bounds in terms of the conditional versions of the $\alpha$-mutual information, the Rényi divergence, and the maximal leakage. Under some conditions, the conditional maximal leakage bound turns out to be stronger than its maximal leakage counterpart.

Preliminaries {#sec:preliminaries}
=============

In this section, we introduce some notation, define relevant information-theoretic quantities, and present some general results that will be used repeatedly in the remainder of this paper.

#### Standard 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}}} }{\dv P_W\!P_{{\boldsymbol{Z}}}}$$ where $\dv P_{W\!{\boldsymbol{Z}}}/\dv P_W\!P_{{\boldsymbol{Z}}}$ is the Radon-Nikodym derivative of $P_{W\!{\boldsymbol{Z}}}$ with respect to $P_W\!P_{{\boldsymbol{Z}}}$. Here, $P_W$ is the distribution induced on the hypothesis space $\mathcal W$ by $P_Z$ through $P_{W\vert {\boldsymbol{Z}}}$. The information density is well defined whenever $P_{W\!{\boldsymbol{Z}}}$ is absolutely continuous with respect to $P_W\!P_{{\boldsymbol{Z}}}$, which we denote by $P_{W\!{\boldsymbol{Z}}}\ll P_W\!P_{{\boldsymbol{Z}}}$. The name information density is motivated by the fact that its expectation under $P_{W\!{\boldsymbol{Z}}}$ is the mutual information $I(W;{\boldsymbol{Z}})$. In the random-subset setting, several of our bounds will be in terms of the conditional information density $$\label{eq:conditional_info_density}
\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}) = \log \frac{\dv P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }{\dv P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}} }$$ where $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ is a conditional distribution on $\mathcal{W}$ given ${\widetilde{\boldsymbol{Z}}}$, obtained by marginalizing out ${\boldsymbol{S}}$. Here, the absolute continuity requirement is that $P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}\ll P_{W\vert{\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$. In the random-subset setting, this is satisfied since $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ is obtained by marginalizing out the discrete random variable ${\boldsymbol{S}}$ from $P_{W\vert {\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$. If we take the expectation of $\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$ under the joint distribution $P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$, we obtain the conditional mutual information $I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$, a key quantity in the bounds developed in [@steinke20-a].

Let $\alpha\in (0,1)\cup(1,\infty)$. The Rényi divergence of order $\alpha$ is defined as [@VanErven2014] $$\label{eq:def_renyi_divergence}
\alpharelent{\alpha}{P_{W\!{\boldsymbol{Z}}}}{P_W\!P_{{\boldsymbol{Z}}}}=\frac{1}{\alpha-1} \log \Exop_{P_W\!P_{{\boldsymbol{Z}}}}\lefto[\exp\lefto(\alpha{{\imath}(W,{\boldsymbol{Z}})}\right)\right].$$ In the limit $\alpha\rightarrow 1$, it reduces to the relative entropy $\relent{P_{W\!{\boldsymbol{Z}}}}{P_W\!P_{{\boldsymbol{Z}}}}$. The conditional Rényi divergence of order $\alpha$ is given by [@verdu15-02a] $$\label{eq:def_cond_renyi_divergence}
\alphaconrelent{\alpha}{P_{W\vert {\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}P_{{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}} }{P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}}}{P_{{\widetilde{\boldsymbol{Z}}}}} = \frac{1}{\alpha-1}\log \Exop_{P_ {{\widetilde{\boldsymbol{Z}}}}P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}}}\lefto[\exp\lefto(\alpha{{\imath}(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})}\right) \right].$$ The $\alpha$-mutual information, which is studied in depth in [@verdu15-02a], is defined as$$\label{eq:def_alpha_MI}
I_\alpha({\boldsymbol{Z}};W) = \frac{1}{\alpha-1}\log \Exop_{P_W}^\alpha\lefto[ \Exop_{P_{{\boldsymbol{Z}}} }^{1/\alpha} \lefto[\exp\lefto(\alpha{{\imath}(W,{\boldsymbol{Z}})}\right)  \right] \right].$$ In the limit $\alpha\rightarrow 1$, it reduces to the mutual information $I(W;{\boldsymbol{Z}})$, whereas for $\alpha\rightarrow \infty$, it becomes the maximal leakage [@issa16-a]: $$\label{eq:def_maximal_leakage}
\mathcal{L}({\boldsymbol{Z}}\rightarrow W)=\log \Exop_{P_W}\lefto[ \esssup_{P_{{\boldsymbol{Z}}}}\exp\lefto({{\imath}(W,{\boldsymbol{Z}})}\right)  \right].$$ The conditional  $\alpha$-mutual information does not have a commonly accepted definition. In [@Tomamichel2018], three definitions are provided and given operational interpretations, two of which have known closed-form expressions. The first coincides with the conditional Rényi divergence, while the second, which we will term $I_\alpha(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$, is defined as $$\label{eq:def_cond_alpha_MI}
I_\alpha(W; \boldsymbol{S}\vert  \tilde{\boldsymbol{Z}} )=\frac{1}{\alpha-1}\log \Exop_{P_ {\tilde{\boldsymbol{Z}}}}\lefto[\Exop_{P_{W\vert \tilde{\boldsymbol{Z}} } }^{\alpha}\lefto[ \Exop_{P_{ \boldsymbol{S}\vert \tilde{\boldsymbol{Z}}}}^{1/\alpha}
\lefto[\exp\lefto(\alpha{{\imath}(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})}\right) \right]\right]\right].$$ In the limit $\alpha\rightarrow \infty$, this reduces to the conditional maximal leakage[@issa16-a Thm. 6] $$\label{eq:def_cond_maximal_leakage}
 \mathcal{L}({\boldsymbol{S}}\rightarrow W\vert {\widetilde{\boldsymbol{Z}}})=\log\esssup_{P_{{\widetilde{\boldsymbol{Z}}}}} \Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}}}\lefto[ \esssup_{P_{{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}} }\exp\lefto({{\imath}(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})}\right) \right].$$ Note that ${\boldsymbol{S}}$ and ${\widetilde{\boldsymbol{Z}}}$ are independent in the random-subset setting. Hence, $P_{{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}}$ can be replaced by $P_{{\boldsymbol{S}}}$ in , , and .

#### Useful Results {#useful-results .unnumbered}

Many previous studies have used the data-processing inequality as a tool for deriving generalization bounds [@bassily18-02a; @esposito19-12a]. In binary hypothesis testing, it is known that the data-processing inequality only provides weak converse bounds on the region of achievable error rates. To get strong converse bounds, one relies on the following lemma instead [@polyanskiy19-a Lem. 12.2].

\[lem:strong\_converse\_lemma\] Let $P$ and $Q$ be probability distributions on some common space $\mathcal{X}$ such that $P$ is absolutely continuous with respect to $Q$, and let $\setE\in \mathcal{X}$ be a measurable set. Then, for all $\gamma\in\reals$, $$\label{eq:lem_strong_converse_lemma}
    P[\setE] \leq P\lefto[\log \frac{\dv P}{\dv Q} >  \gamma \right] + e^\gamma Q[\setE].$$

In Section \[sec:uncond\_sd\_strong\_conv\] and Section \[sec:cond\_sd\_strong\_conv\], we will show how to use this result to derive generalization bounds.

We will also make repeated use of the following result, due to Hoeffding [@wainwright19-a Prop. 2.5].

\[lem:hoeffdings\_inequality\] Let $X\distas P_X$ be a $\sigma$-subgaussian random variable, i.e., a random variable satisfying the following inequality for all $\lambda\in\reals$: $$\label{eq:lem_hoeffdings_inequality}
\Exop\lefto[\exp(\lambda(X-\Exop[X]) ) \right] \leq \exp\lefto(\frac{\lambda^2\sigma^2}{2}\right).$$ Then, for all $\epsilon>0$, $$P_X\lefto(\abs{X-\Exop[X]}\geq \epsilon \right) \leq 2\exp\lefto(-\frac{\epsilon^2}{2\sigma^2} \right).$$ Note that a random variable bounded on $[a,b]$ is $\sigma$-subgaussian with $\sigma=(b-a)/2$. Also, if $X_i$, for $i=1,\dots,n$, are independent $\sigma$-subgaussian random variables, the average $(1/n)\sum_{i=1}^n X_i$ is $\sigma/\sqrt{n}$-subgaussian.

Generalization Bounds for the Standard Setting {#sec:uncond_results}
==============================================

In this section, we study the standard setting described in Section \[sec:preliminaries\]. We will assume that the loss function $\ell(w,Z)$ is $\sigma$-subgaussian under $P_Z$ for all $w\in\mathcal{W}$. This means that, for all $\lambda\in\reals$ and for all $w\in\mathcal{W}$, $$\label{eq:subgaussian_def}
\Exop_{P_Z}\lefto[ \exp\lefto(\lambda(\Exop_{P_Z}\lefto[\ell(w,Z)\right]-\ell(w,Z) \right) \right]\leq \exp\lefto(\frac{\lambda^2\sigma^2}{2}\right).$$ We will derive bounds on the generalization error of a probabilistic learning algorithm $P_{W\vert {\boldsymbol{Z}}}$ in terms of some function of the information density . As previously mentioned, several different notions of generalization error bounds have been investigated in the literature. One such notion is that of average generalization bounds, where we want to find an $\epsilon$ such that $$\label{eq:uncond_exp_generalization_bound_def}
\abs{\Exop_{P_{W\!{\boldsymbol{Z}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}\right]} \leq \epsilon.$$ This $\epsilon$ will in general depend on the joint distribution $P_{W\!{\boldsymbol{Z}}}$, on properties of the loss function, and on the cardinality $n$ of the training data. We will study this type of bounds in Section \[sec:uncond\_exp\].

Another approach, typically studied in the PAC-Bayesian literature, is to find probabilistic bounds of the following form: with probability at least $1-\delta$ under $P_{{\boldsymbol{Z}}}$, $$\label{eq:uncond_pacb_generalization_bound_def}
\abs{\Exop_{P_{W\vert {\boldsymbol{Z}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}\right]} \leq \epsilon.$$ This bound is interesting when we have a fixed data set ${\boldsymbol{Z}}$, but draw a new hypothesis according to $P_{W\vert {\boldsymbol{Z}}}$ each time we want to use our algorithm. We derive bounds of this type in Section \[sec:uncond\_pacb\].

Finally, we also consider the single-draw scenario. In this setting, we are interested in bounds of the following flavor: with probability at least $1-\delta$ under $P_{W\!{\boldsymbol{Z}}}$, $$\label{eq:uncond_singledraw_generalization_bound_def}
\abs{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}} \leq \epsilon.$$ This type of result is relevant when we draw a single hypothesis $W$ based on our training data, and want to bound the generalization error of this particular $W$ with high probability. The probabilistic bounds in  and  are said to be high-probability bounds if the dependence of $\epsilon$ on the confidence parameter $\delta$ is at most of order $\log(1/\delta)$.

In Theorem \[thm:unconditional\_subgaussian\] below, we present an exponential inequality that will be used in Section \[sec:uncond\_exp\], Section \[sec:uncond\_pacb\], and Section \[sec:uncond\_sd\] to derive generalization bounds of all three flavors.

\[thm:unconditional\_subgaussian\] Let ${\boldsymbol{Z}}=(Z_1,\dots,Z_n)\in\mathcal{Z}^n$ consist of $n$ training samples generated from $P_Z$, and let $P_{W\vert {\boldsymbol{Z}}}$ be a probabilistic learning algorithm. Assume that $\ell(w,Z): \mathcal{W}\times \mathcal{Z}\rightarrow \reals$ is $\sigma$-subgaussian under $P_Z$ for all $w\in \mathcal W$. Also, assume that $P_{W\!{\boldsymbol{Z}}}$ is absolutely continuous with respect to $P_W\!P_{{\boldsymbol{Z}}}$. Then, for all $\lambda\in \reals$, $$\label{eq:unconditional_subgaussian_thm}
    \Exop_{P_{W\! {\boldsymbol{Z}}}}\lefto[{\exp\lefto(\lambda {{\textnormal{gen}}(W,{\boldsymbol{Z}})}-\frac{\lambda^2\sigma^2}{2n}-\imath(W,{\boldsymbol{Z}})  \right)}\right]\leq 1.$$

Since $\ell(w,Z)$ is $\sigma$-subgaussian for all $w\in\mathcal{W}$ and the $Z_i$ are ,  $(1/n)\sum_{i=1}^n  \ell(w,Z_i)$ is $\sigma/\sqrt{n}$-subgaussian for all $w\in\mathcal{W}$, as remarked after Lemma \[lem:hoeffdings\_inequality\]. Thus, for all $w\in\mathcal{W}$, $$\label{eq:proof_of_uncond_thm_subgaussian_assuption}
    \Exop_{P_{{\boldsymbol{Z}}} } \lefto[\exp\lefto(\lambda\left(\Exop_{P_Z}\lefto[\ell(w,Z)\right]-\frac{1}{n}\sum_{i=1}^n \ell(w,Z_i) \right)\right)\right]
    \leq \exp\lefto(\frac{\lambda^2\sigma^2}{2n}\right).$$ Reorganizing terms and taking the expectation with respect to $P_W$, we get$$\label{eq:thm_1_proof_before_E}
    \Exop_{P_W\! P_{{\boldsymbol{Z}}} } \lefto[\exp\lefto(\lambda {{\textnormal{gen}}(W,{\boldsymbol{Z}})}- \frac{\lambda^2\sigma^2}{2n}\right)\right]\leq 1.$$ Now, let $\setE=\textnormal{supp}(P_{W\!{\boldsymbol{Z}}})$ be the support of $P_{W\!{\boldsymbol{Z}}}$. From , it follows that $$\Exop_{P_W\! P_{{\boldsymbol{Z}}} } \lefto[1_\setE\cdot\exp\lefto(\lambda {{\textnormal{gen}}(W,{\boldsymbol{Z}})}- \frac{\lambda^2\sigma^2}{2n}\right)\right]\leq 1$$ where $1_\setE$ is the indicator function of the set $\setE$. To obtain , we perform a change measure from $P_W\! P_{{\boldsymbol{Z}}}$ to $P_{W\! {\boldsymbol{Z}}}$ [@polyanskiy19-a Prop. 17.1].

Note that Theorem \[thm:unconditional\_subgaussian\] holds *verbatim* if $P_W$ is replaced with an auxiliary distribution $Q_W$, under a suitable absolute continuity assumption. This is detailed in the next remark.

\[rem:uncond\_conversion\_to\_Q\_bounds\] Consider the setting of Theorem \[thm:unconditional\_subgaussian\], but with the altered absolute continuity assumption that $P_{W\!{\boldsymbol{Z}}}\ll Q_W\!P_{{\boldsymbol{Z}}}$ for some distribution $Q_W$ on $\mathcal{W}$. Then, $$\label{eq:unconditional_subgaussian_with_Q}
    \Exop_{P_{W\! {\boldsymbol{Z}}}}\lefto[{\exp\lefto(\lambda {{\textnormal{gen}}(W,{\boldsymbol{Z}})}-\frac{\lambda^2\sigma^2}{2n}-\log\frac{\dv P_{W\!{\boldsymbol{Z}}} }{\dv Q_W\!P_{{\boldsymbol{Z}}}}  \right)}\right]\leq 1.$$

For the bounds that we will later derive, the choice $Q_W=P_W$ is optimal. Unfortunately, since the data distribution $P_Z$ is considered to be unknown in the statistical learning framework, the marginal distribution $P_W$ is also unavailable. Hence, $P_W$ needs to be replaced by some suitably chosen auxiliary distribution $Q_W$ whenever one wants to numerically evaluate the generalization bounds that we derive later in this section.[^4] In the remainder of this paper, all bounds will be given in terms of $P_W$. Thanks to this choice, many of the terms that appear in our results will be expressible in terms of familiar information-theoretic quantities. However, through repeated references to Remark \[rem:uncond\_conversion\_to\_Q\_bounds\], we will emphasize that the bounds can easily be generalized to the case in which $P_W$ is replaced by an auxiliary distribution $Q_W$.

Average Generalization Error Bounds {#sec:uncond_exp}
-----------------------------------

We now use Theorem \[thm:unconditional\_subgaussian\] to obtain an average generalization error bound of the form given in .

\[cor:exp\_uncond\] Under the setting of Theorem \[thm:unconditional\_subgaussian\], $$\label{eq:cor_exp_uncond}
    \abs{ \Ex{P_{W\! {\boldsymbol{Z}}}}{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}}} \leq \sqrt{\frac{2\sigma^2}{n}I(W;{\boldsymbol{Z}})}.$$

We apply Jensen’s inequality to , resulting in $$\exp\lefto(\lambda\Exop_{P_{W\! {\boldsymbol{Z}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}\right] - \frac{\lambda^2\sigma^2}{2n} 
 -\Ex{P_{W\! {\boldsymbol{Z}}}}{{{\imath}(W,{\boldsymbol{Z}})}} \right)  \leq   1.$$ Note that $\Exop_{P_{W\! {\boldsymbol{Z}}}}\lefto[\imath(W, {\boldsymbol{Z}})\right]=\relent{P_{W\!{\boldsymbol{Z}}}}{P_W\!P_{{\boldsymbol{Z}}} }=I(W;{\boldsymbol{Z}})$. By reorganizing terms, we get $$\lambda \Exop_{P_{W\! {\boldsymbol{Z}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}\right]-\lambda^2\frac{\sigma^2}{2n}  - \relent{P_{W\!{\boldsymbol{Z}}}}{P_W\!P_{{\boldsymbol{Z}}} } \leq 0.$$ We now set $\lambda=n\Exop_{P_{W\! {\boldsymbol{Z}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}\right]/\sigma^2$ to optimize the bound, and thereby get $$\label{eq:exp_uncond_final_line_of_proof}
\Exop^2_{P_{W\! {\boldsymbol{Z}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}\right] - \frac{2\sigma^2}{n}\relent{P_{W\!{\boldsymbol{Z}}}}{P_W\!P_{{\boldsymbol{Z}}} }\leq 0$$ from which  directly follows.

The bound in  coincides with the result reported in [@xu17-05a Thm. 1]. As noted in Remark \[rem:uncond\_conversion\_to\_Q\_bounds\], we can substitute an arbitrary $Q_W$ for $P_W$ in , provided that the necessary absolute continuity criterion is fulfilled. This leads to a more general bound involving the relative entropy $\relent{P_{W\!{\boldsymbol{Z}}}}{Q_W\!P_{{\boldsymbol{Z}}} }$.

PAC-Bayesian Generalization Error Bounds {#sec:uncond_pacb}
----------------------------------------

We now turn to PAC-Bayesian bounds of the form given in . In the following corollary, we reobtain a known data-dependent bound and present a novel data-independent relaxation.

\[cor:pacb\_uncond\] Under the setting of Theorem \[thm:unconditional\_subgaussian\], the following holds with probability at least $1-\delta$ under $P_{{\boldsymbol{Z}}}$ for all $t>0$:

[rCl]{}\[eq:cor\_pacb\_uncond\] &&\
\[eq:cor\_pacb\_uncond\_second\] && .

Here, the first inequality yields a data-dependent bound, while the second inequality provides a data-independent relaxation.

As in Corollary \[cor:exp\_uncond\], we start from  and use Jensen’s inequality, but now only with respect to $P_{W\vert {\boldsymbol{Z}}}$. This leads to $$\label{eq:pacb_uncond_after_jensen}
\Exop_{P_{{\boldsymbol{Z}}}}\lefto[\exp\left(\lambda \Ex{P_{W\vert {\boldsymbol{Z}}} }{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}} - \frac{\lambda^2\sigma^2}{2n}-\relent{P_{W\!\given\! {\boldsymbol{Z}}}}{P_W}
\right) \right] \leq 1$$ where we used that, for a fixed ${\boldsymbol{Z}}$, $$\Ex{P_{W\vert {\boldsymbol{Z}}}}{\imath(W,{\boldsymbol{Z}})}=\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}.$$ Next, we use the following result. Let $U\distas P_U$ be a nonnegative random variable satisfying $\Ex{}{U}\leq 1$. Then, Markov’s inequality implies that $$\label{eq:markov_inequality_Pu}
P_U[U\leq 1/\delta]\geq 1- \Ex{ }{U}\delta\geq 1- \delta.$$ By applying  to the random variable in , we obtain $$P_{{\boldsymbol{Z}}}\lefto[\exp\lefto(\lambda \Ex{P_{W\vert {\boldsymbol{Z}}} } {{{\textnormal{gen}}(W,{\boldsymbol{Z}})}} - \frac{\lambda^2\sigma^2}{2n}-\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}
\right) \leq \frac{1}{\delta} 
\right] \geq  1-\delta.$$ Reorganizing terms, we conclude that $$\label{eq:uncond_pacb_proof_markov_pz}
    P_{{\boldsymbol{Z}}}\lefto[\frac{\lambda^2\sigma^2}{2n} -\lambda \Ex{P_{W\vert {\boldsymbol{Z}}} } {{{\textnormal{gen}}(W,{\boldsymbol{Z}})}} 
    +\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W} +\log\frac{1}{\delta} \geq 0 
\right] \geq 1-\delta$$ from which  follows after setting $\lambda=n\Exop_{P_{W\vert {\boldsymbol{Z}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}})}\right]/\sigma^2$. To prove , we apply Markov’s inequality to the random variable $\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}^t$, which after some manipulation yields $$\label{eq:uncond_pacb_proof_markov_with_t}
P_{{\boldsymbol{Z}}}\lefto[\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W} \leq 
\frac
    {\Exop^{1/t}_{P_{{\boldsymbol{Z}}}}\lefto[\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}^t\right] }
    {\delta^{1/t}} \right]
    \geq 1-\delta.$$ We now use the union bound to combine  with  and perform the substitution $\delta\rightarrow \delta/2$, after which  follows.

Note that by setting $t=1$ in , we get $\Exop_{P_{{\boldsymbol{Z}}}}\lefto[\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W} \right]=I(W;{\boldsymbol{Z}})$. This choice recovers the result reported in [@bassily18-02a App. 3]. Instead, if we let $t\rightarrow \infty$, the polynomial $\delta$-dependence in  disappears and the bound becomes a high-probability bound. This illustrates that one can get progressively better dependence on $\delta$ by letting the bound depend on higher moments of $\relent{P_{W\vert {\boldsymbol{Z}}}}{P_W}$. The tightness of the resulting bound depends on how well one can control these higher moments. Finally, as per Remark \[rem:uncond\_conversion\_to\_Q\_bounds\], we can obtain more general bounds by replacing $P_W$ in  and  with an arbitrary $Q_W$ that satisfies a suitable absolute continuity property.

Single-Draw Generalization Error Bounds {#sec:uncond_sd}
---------------------------------------

We now turn our attention to single-draw bounds of the form given in . We will derive generalization bounds by using two different approaches. Our first approach relies on the exponential inequality from Theorem \[thm:unconditional\_subgaussian\], which we use to get a data-dependent bound in terms of the information density ${{\imath}(W,{\boldsymbol{Z}})}$. We relax this result in different ways to obtain several data-independent bounds, some of which are tighter than existing results. Our second approach, which yields a generalization bound that is explicit in the tail of the information density, relies on the change of measure result stated in Lemma \[lem:strong\_converse\_lemma\]. This bound can be relaxed to obtain essentially the same data-independent bounds obtained using the first approach.

### Generalization Bounds from the Exponential Inequality

We begin by using Theorem \[thm:unconditional\_subgaussian\] to derive a data-dependent single-draw generalization bound and a data-independent relaxation, similar to the PAC-Bayesian results in Corollary \[cor:pacb\_uncond\]. Both of these bounds are novel.

\[cor:singledraw\_uncond\] Under the setting of Theorem \[thm:unconditional\_subgaussian\], with probability at least $1-\delta$ under $P_{W\!{\boldsymbol{Z}}}$, the following inequalities hold for all $t>0$:[^5]

[rCl]{}\[eq:cor\_singledraw\_uncond\] &&\
\[eq:cor\_singledraw\_uncond\_second\] & & .

Here, the first inequality provides a data-dependent bound and the second inequality is a data-independent relaxation. In , $M_t(W;{\boldsymbol{Z}})$ is the $t$th root of the $t$th central moment of $\imath(W,{\boldsymbol{Z}})$: $$\label{eq:def_M_P_WZn}
M_t(W;{\boldsymbol{Z}}) = \Exop^{1/t}_{P_{W\! {\boldsymbol{Z}}}}\lefto[\abs{ \imath(W,{\boldsymbol{Z}}) - \relent{P_{W\!{\boldsymbol{Z}}}}{P_W\!P_{{\boldsymbol{Z}}} }}^t \right].$$

By directly applying Markov’s inequality  to , we conclude that $$P_{W\! {\boldsymbol{Z}}}\lefto[\exp\biggo(\lambda {{\textnormal{gen}}(W,{\boldsymbol{Z}})}- \frac{\lambda^2\sigma^2 }{2n}
-\imath(W,{\boldsymbol{Z}}) \right)\leq \frac{1}{\delta} \bigg] \geq 1-\delta$$ from which  follows after setting $\lambda=n{{\textnormal{gen}}(W,{\boldsymbol{Z}})}/\sigma^2$. To prove , we use Markov’s inequality in the following form: for a random variable $U\distas P_U$, the following holds for all $t>0$: $$\label{eq:markov_for_arbitrary_u}
P_U\lefto[U \leq \Exop[U]+ \frac{\Exop^{1/t}[\abs{U-\Exop[U]}^t]}{\delta^{1/t}} \right]\geq 1-\delta.$$ Applying  with $U=\imath(W,{\boldsymbol{Z}})$ and using the union bound to combine the resulting inequality with , we obtain  after performing the substitution $\delta \rightarrow \delta/2$.

As usual, we can obtain more general bounds by substituting $Q_W$ for $P_W$ in Corollary \[cor:singledraw\_uncond\], provided that the necessary absolute continuity assumption is satisfied.

Similarly to what we noted for the PAC-Bayesian bound , the $\delta$-dependence in  can be made more benign by letting the bound depend on higher central moments of ${{\imath}(W,{\boldsymbol{Z}})}$, but the tightness of the resulting bound hinges on how well one can control these higher moments. In particular, if we let $t\rightarrow \infty$ in , we obtain the following high-probability bound: $$\label{eq:cor_singledraw_uncond_t_inf}
    \abs{  {{\textnormal{gen}}(W,{\boldsymbol{Z}})}} \leq  
     \sqrt{\frac{2\sigma^2}{n}\left(I(W;{\boldsymbol{Z}})+{M_\infty(W;{\boldsymbol{Z}})} +\log \frac{2}{\delta}\right)}.$$ Here, ${M_\infty(W;{\boldsymbol{Z}})}$ is given by $$\label{eq:def_M_infinity}
 M_\infty(W;{\boldsymbol{Z}})=\esssup_{P_{W\!{\boldsymbol{Z}}}} \abs{\imath(W,{\boldsymbol{Z}})- I(W;{\boldsymbol{Z}})}.$$ Note that the supremization in  is over the argument of ${{\imath}(W,{\boldsymbol{Z}})}$, whereas $I(W;{\boldsymbol{Z}})$ is a constant.

The data-independent relaxation in Corollary \[cor:singledraw\_uncond\] is not as tight as the one obtained in Corollary \[cor:pacb\_uncond\]. Indeed, since ${{\imath}(W,{\boldsymbol{Z}})}$ can be negative, we had to use a weaker version of Markov’s inequality (compare  with ). In the following corollary, we provide two alternative data-independent bounds, both of which are novel. The first bound depends on $\esssup_{P_{{\boldsymbol{Z}}}}\Exop_{P_W}[\exp({{\imath}(W,{\boldsymbol{Z}})})]$, which is a lower bound to the maximal leakage $\mathcal{L}({\boldsymbol{Z}}\rightarrow W)$ defined in . The second bound is in terms of the Rényi divergence .

\[cor:singledraw\_uncond\_alphadiv\_leakage\] Under the setting of Theorem \[thm:unconditional\_subgaussian\], the following inequalities hold with probability at least $1-\delta$ under $P_{W\!{\boldsymbol{Z}}}$: $$\label{eq:cor_singledraw_uncond_leakage}
\abs{ {{\textnormal{gen}}(W,{\boldsymbol{Z}})}} \leq \sqrt{\frac{2\sigma^2}{n}\left(\log \esssup_{P_{{\boldsymbol{Z}}}}\Exop_{P_{W} }\lefto[\exp(\imath(W,{\boldsymbol{Z}})) \right] +2\log \frac{2}{\delta}\right)}$$ and, for all $\alpha,\gamma> 1$ such that $1/\alpha+1/\gamma=1$,

[rCl]{}\[eq:cor\_singledraw\_uncond\_alphadiv\] .

We start by noting that, with probability $1$ under $P_{W\!{\boldsymbol{Z}}}$, $$\imath(W,{\boldsymbol{Z}}) = \log \frac{\dv P_{W\! {\boldsymbol{Z}}}}{\dv P_W\!P_{{\boldsymbol{Z}}}} \leq \log \esssup_{P_{{\boldsymbol{Z}}\vert W}} \frac{\dv P_{W\! {\boldsymbol{Z}}}}{\dv P_W\!P_{{\boldsymbol{Z}}}}.$$ The assumption that $P_{W\!{\boldsymbol{Z}}}\ll P_W\!P_{{\boldsymbol{Z}}}$ means that any set in the support of $P_{W\!{\boldsymbol{Z}}}$ is also in the support of $P_W\!P_{{\boldsymbol{Z}}}$. We can therefore upper-bound the $\esssup$ as $$\label{eq:singledraw_uncond_leakage_esssup_weakening}
\log \esssup_{P_{{\boldsymbol{Z}}\vert W}} \frac{\dv P_{W\! {\boldsymbol{Z}}}}{\dv P_W\!P_{{\boldsymbol{Z}}}} \leq \log \esssup_{P_{{\boldsymbol{Z}}}} \frac{\dv P_{W\! {\boldsymbol{Z}}}}{\dv P_W\!P_{{\boldsymbol{Z}}}}.$$ Applying Markov’s inequality with respect to $P_W$ to the random variable $\dv P_{W{\boldsymbol{Z}}} /\dv P_W \!P_{{\boldsymbol{Z}}}$, we conclude that, with probability at least $1-\delta$ under $P_{W}$, $$\label{eq:cor_uncond_sd_leakage_proof_infdens_bound}
\imath(W,{\boldsymbol{Z}}) \leq \log \esssup_{P_{{\boldsymbol{Z}}} } \Exop_{P_{W}}\lefto[  \frac{\dv P_{W\! {\boldsymbol{Z}}}}{\dv P_W\!P_{{\boldsymbol{Z}}}}\right] + \log\frac{1}{\delta}.$$ By using the union bound to combine  with  and performing the substitution $\delta\rightarrow \delta/2$, we obtain .

To prove , we first apply Markov’s inequality and then perform a change of measure to conclude that the following inequalities hold with probability at least $1-\delta$ under $P_{W\! {\boldsymbol{Z}}}$: $$\label{eq:cor_singledraw_uncond_alphadiv_pf_markov_com}
\imath(W,{\boldsymbol{Z}}) \leq \log\Exop_{P_{W\!{\boldsymbol{Z}}}}\lefto[\frac{\dv P_{W\! {\boldsymbol{Z}}}}{\dv P_W\!P_{{\boldsymbol{Z}}}}\right] + \log\frac{1}{\delta} \leq  \log\Exop_{P_W\!P_{{\boldsymbol{Z}}}}\lefto[\left(\frac{\dv P_{W\! {\boldsymbol{Z}}}}{\dv P_W\!P_{{\boldsymbol{Z}}}}\right)^2\right] + \log\frac{1}{\delta}.$$ Next, we apply Hölder’s inequality twice as follows. Let $\alpha,\gamma,\alpha',\gamma'> 1$ be constants such that $1/\alpha+1/\gamma=1/\alpha'+1/\gamma'=1$. Then,

[rCl]{} \_[P\_WP\_]{} && \_[P\_W]{}\
&& \_[P\_W]{}\^[1/’]{}\_[P\_W]{}\^[1/’]{}.

Setting $\alpha=\alpha'$, which implies $\gamma=\gamma'$, we conclude that

[rCl]{} \_[P\_WP\_]{} && \_[P\_WP\_ ]{}\^[1/]{}+ \_[P\_WP\_ ]{}\^[1/ ]{}\[eq:choosePandQ\]\
\[eq:cor\_uncond\_sd\_alphadiv\_proof\_infdens\_bound\] &=&D\_(P\_[W ]{}||P\_WP\_)+D\_(P\_[W ]{}||P\_WP\_).

Substituting  into , and then combining  with  through the union bound, we establish  after the substitution $\delta\rightarrow \delta/2$.

The bound in  can be relaxed to recover the maximal leakage bound in [@esposito19-12a Cor. 10], the max information bound in [@dwork15-06a Thm. 4] for the case in which the parameter $\beta$ therein is set to $0$, and , all up to a $(2\sigma^2/n)\log(2/\delta)$ term inside the square root. Indeed, we can relax the information density term in  as $$\label{eq:measure_lower_bounding_maximal_leakage}
\log \esssup_{P_{{\boldsymbol{Z}}}}\Exop_{P_{W} }\lefto[\exp(\imath(W,{\boldsymbol{Z}})) \right] \leq \log \Exop_{P_{W} }\lefto[\esssup_{P_{{\boldsymbol{Z}}}}\exp(\imath(W,{\boldsymbol{Z}})) \right] = \mathcal{L}({\boldsymbol{Z}}\rightarrow W).$$ Now, let the max information be defined as $$\label{eq:max_mi}
    I_{\textnormal{max}}(W;{\boldsymbol{Z}}) = \esssup_{P_{W\!{\boldsymbol{Z}}} }\imath(W,{\boldsymbol{Z}}).$$ As shown in [@esposito19-12a Lem. 12], $\mathcal{L}({\boldsymbol{Z}}\rightarrow W)\leq I_{\textnormal{max}}(W;{\boldsymbol{Z}})$. It is also readily verified that $$I_\textnormal{max}(W;{\boldsymbol{Z}})\leq I(W;{\boldsymbol{Z}})+{M_\infty(W;{\boldsymbol{Z}})}.$$ To summarize, we have that $$\log \esssup_{P_{{\boldsymbol{Z}}}}\Exop_{P_{W}}\lefto[\exp(\imath(W,{\boldsymbol{Z}})) \right] \leq \mathcal{L}({\boldsymbol{Z}}\rightarrow W) \leq  I_{\textnormal{max}}(W;{\boldsymbol{Z}}) \leq I(W;{\boldsymbol{Z}})+{M_\infty(W;{\boldsymbol{Z}})}.$$ In particular, provided that $$\log  \esssup_{P_{{\boldsymbol{Z}}} }\Exop_{P_{W}}\lefto[ \exp\lefto(\imath(W,{\boldsymbol{Z}})\right)\right] \leq \mathcal{L}({\boldsymbol{Z}}\rightarrow W) + \log\frac{2}{\delta}$$ the bound in  is tighter than the maximal leakage bound in [@esposito19-12a Cor. 10], the max information bound in [@dwork15-06a Thm. 4] with $\beta=0$, and .

As usual, we can obtain more general bounds by replacing $P_W$ with an arbitrary $Q_W$ in Corollary \[cor:singledraw\_uncond\_alphadiv\_leakage\], provided that $P_{W\!{\boldsymbol{Z}}}\ll Q_W\!P_{{\boldsymbol{Z}}}$. However, for the proof of , we still need the original absolute continuity assumption $P_{W\!{\boldsymbol{Z}}}\ll P_W\!P_{{\boldsymbol{Z}}}$ to guarantee that  holds. Note that a similar extension can easily be performed on [@esposito19-12a Thm. 1] and on the corollaries that are based on it, including [@esposito19-12a Cor. 10].

### Generalization Bounds from the Strong Converse {#sec:uncond_sd_strong_conv}

Next, we use Lemma \[lem:strong\_converse\_lemma\] to derive an additional data-independent single-draw generalization bound. This novel bound depends on the tail of the information density.

\[thm:unconditional\_hypothesis\_main\_bound\] Under the setting of Theorem \[thm:unconditional\_subgaussian\], with probability at least $1-\delta$ under $P_{W\! {\boldsymbol{Z}}}$, the following holds: $$\label{eq:thm_unconditional_hypothesis_main_bound}
    \abs{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}}
    \leq\sqrt{ \frac{2\sigma^2}{n}
    \left(
        \gamma + \log\lefto(\frac{2}{\delta-P_{W\! {\boldsymbol{Z}}}\lefto[\imath(W,{\boldsymbol{Z}})\geq \gamma\right]} \right)
    \right)}.$$ This is valid for all $\gamma$ such that the right-hand side is defined and real.

The proof relies on Lemma \[lem:strong\_converse\_lemma\]. We set $P=P_{W\!{\boldsymbol{Z}}}$, $Q=P_W\!P_{{\boldsymbol{Z}}}$, and$$\label{eq:high_error_event}
\setE=\{W,{\boldsymbol{Z}}: \abs{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}}>\epsilon \}.$$ Due to the $\sigma$-subgaussianity of the loss function, Hoeffding’s inequality (Lemma \[lem:hoeffdings\_inequality\]) implies that $$\label{eq:thm_main_uncond_hyp_bound_pf_QE_bound}
P_W\!P_{{\boldsymbol{Z}}}[\setE] =P_W\!P_{{\boldsymbol{Z}}}\lefto[\abs{ L_{{\boldsymbol{Z}}}(W)-\Exop_{P_{{\boldsymbol{Z}}} }\lefto[L_{{\boldsymbol{Z}}}(W)\right]}>\epsilon  \right] \leq 2\exp\lefto(-\frac{n\epsilon^2}{2\sigma^2} \right).$$ Substituting  into , we get $$\label{eq:strong_conv_solve_for_eps}
    P_{W\! {\boldsymbol{Z}}}[\abs{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}}>\epsilon] \leq P_{W\! {\boldsymbol{Z}}}\lefto[\imath(W,{\boldsymbol{Z}})\geq \gamma\right] + 2\exp\lefto(\gamma-n\frac{\epsilon^2}{2\sigma^2}\right).$$ We obtain the desired result by requiring the right-hand side of  to be equal to $\delta$ and solving for $\epsilon$.

As for the previous results, a more general bound can be obtained by setting $Q=Q_W\!P_{{\boldsymbol{Z}}}$, where $Q_W$ is an arbitrary auxiliary distribution on $\mathcal{W}$, provided that a suitable absolute continuity criterion is fulfilled.

The result in Theorem \[thm:unconditional\_hypothesis\_main\_bound\] indicates a trade-off between the decay of the tail of the information density and the tightness of the generalization bound. Indeed, the parameter $\gamma$ has to be chosen sufficiently large to make the argument of the logarithm positive. However, increasing $\gamma$ too much may yield a loose bound because of the $\gamma$ term that is added to the logarithm.

The bound in Theorem \[thm:unconditional\_hypothesis\_main\_bound\] can be relaxed to recover some of the data-independent bounds discussed earlier in this section, up to a $(2\sigma^2/n)\log 2$ penalty term inside the square root. In Remarks \[rem:uncond\_alt\_deriv\_moment\] and \[rem:uncond\_alt\_deriv\_leakage\], we present these alternative derivations.

\[rem:uncond\_alt\_deriv\_moment\] Using Markov’s inequality, we conclude that

[rCl]{}\[eq:moment\_bound\_from\_hyptest\_markov\] P\_[W ]{}&& P\_[W ]{}\
&&

where $M_t(W;{\boldsymbol{Z}})$ is defined in . Next, we set $$    \gamma =\relent{P_{W\!{\boldsymbol{Z}}}}{P_W\!P_{{\boldsymbol{Z}}}}+\frac{M_t(W;{\boldsymbol{Z}})}{(\delta/2)^{1/t}}$$ which, once substituted into , implies that $P_{W\! {\boldsymbol{Z}}}\lefto[\imath(W,{\boldsymbol{Z}})\geq \gamma\right] \leq {\delta}/{2}$. Using this inequality in , we obtain $$\abs{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}}
    \leq\sqrt{ \frac{2\sigma^2}{n}
    \left(
        \relent{P_{W\!{\boldsymbol{Z}}}}{P_W\!P_{{\boldsymbol{Z}}}}+\frac{M_t(W;{\boldsymbol{Z}})}{(\delta/2)^{1/t}} + \log\frac{4}{\delta}
    \right)}.$$ This coincides with the bound in , up to a $(2\sigma^2/n)\log 2$ term inside the square root.

\[rem:uncond\_alt\_deriv\_leakage\] Note that $$P_{W\! {\boldsymbol{Z}}}[\imath(W,{\boldsymbol{Z}}) \geq \gamma] \leq P_W\lefto[\esssup_{P_{{\boldsymbol{Z}}\vert W}} \exp\lefto({{\imath}(W,{\boldsymbol{Z}})}\right)\geq e^\gamma\right].$$ Since $P_{W\!{\boldsymbol{Z}}}\ll P_W\!P_{{\boldsymbol{Z}}}$, the $\esssup$ can be upper-bounded as in . Hence, $$\label{eq:max_leak_alt_deriv_esssup_weakening}
P_{W\! {\boldsymbol{Z}}}[\imath(W,{\boldsymbol{Z}}) \geq \gamma] \leq P_W\lefto[\esssup_{P_{{\boldsymbol{Z}}}}\exp\lefto({{\imath}(W,{\boldsymbol{Z}})}\right)\geq e^\gamma\right].$$ By applying Markov’s inequality to the right-hand side of , we find that $$\label{eq:max_leak_alt_deriv_tail_bound}
P_{W\! {\boldsymbol{Z}}}[\imath(W,{\boldsymbol{Z}}) \geq \gamma] \leq e^{-\gamma}\Ex{P_W}{\esssup_{P_{{\boldsymbol{Z}}}}\exp\lefto({{\imath}(W,{\boldsymbol{Z}})}\right)}=e^{-\gamma} \exp\lefto(\mathcal{L}({\boldsymbol{Z}}\rightarrow W)\right).$$ Substituting  into  and setting $\gamma = \mathcal{L}({\boldsymbol{Z}}\rightarrow W) + \log(2/\delta)$, we conclude that with probability at least $1-\delta$ under $P_{W\! {\boldsymbol{Z}}}$, $$\abs{{{\textnormal{gen}}(W,{\boldsymbol{Z}})}}\leq \sqrt{ \frac{2\sigma^2}{n}\left(\mathcal{L}({\boldsymbol{Z}}\rightarrow W)+\log 2+2\log \frac{2}{\delta} \right) }.$$ This coincides with the maximal leakage-weakening of  up to a $(2\sigma^2/n)\log 2$ term inside the square root, and with [@esposito19-12a Cor. 10] up to a $(2\sigma^2/n)\log (4/\delta)$ term inside the square root.

Generalization Bounds for the Random-Subset Setting
===================================================

We now consider the random-subset setting described in Section \[sec:preliminaries\]. For this setting, we will require the stronger assumption that the loss function $\ell(\cdot,\cdot)$ is bounded, rather than the subgaussian assumption in Section \[sec:uncond\_results\]. As detailed in the proof of Theorem \[thm:conditional\_bounded\_inequality\] below, boundedness will be crucial to establish an inequality similar to  for the case in which the expectation over ${\widetilde{\boldsymbol{Z}}}$ is replaced by an expectation over the selection random variable ${\boldsymbol{S}}$.

The bounds in this section will depend on the conditional information density . Intuitively, rather than asking how much information on the training data ${\boldsymbol{Z}}$ can be inferred from $W$, we instead ask how much information $W$ reveals about whether ${\widetilde{\boldsymbol{Z}}}_{i}$ or ${\widetilde{\boldsymbol{Z}}}_{i+n}$ has been used for training, for $i=1,\dots,n$, given the knowledge of ${\widetilde{\boldsymbol{Z}}}$. We will make this intuition more precise and highlight the advantages of the random-subset approach when we compare the generalization error bounds obtained in this section to the ones in Section \[sec:uncond\_results\], under the assumption of a bounded loss function.

As in Section \[sec:uncond\_results\], the generalization bounds in this section will take different forms: average generalization bounds, PAC-Bayesian bounds, and single-draw bounds. The average bound for the random-subset setting has a form similar to , namely $$\label{eq:conditional_exp_gen_error_def}
\abs{\Exop_{P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}} }\lefto[ \textnormal{gen}(W,{\boldsymbol{Z}}({\boldsymbol{S}})) \right] } \leq \epsilon.$$ For the PAC-Bayesian and single-draw settings, it will turn out to be convenient to first obtain probabilistic bounds on the following quantity: $$\label{eq:genshat_definition}
{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}= \frac{1}{n}\sum_{i=1}^n \lefto(\ell(W,( Z_i(\bar S_i)) - \ell(W,Z_i(S_i)) \right).$$ Here, $\bar {\boldsymbol{S}}$ is a vector whose entries are modulo-$2$ complements of the entries of ${\boldsymbol{S}}$. As a consequence, ${\boldsymbol{Z}}(\bar{\boldsymbol{S}})$ contains all the elements of ${\widetilde{\boldsymbol{Z}}}$ that are not in ${\boldsymbol{Z}}({\boldsymbol{S}})$. So, instead of comparing the loss on the training data to the expected loss on a new sample, we compare it to a test loss, i.e., the loss on $n$ samples that are independent of $W$. Note that quantities similar to  are what one computes when empirically assessing the generalization performance of a learning algorithm.

In the PAC-Bayesian setting, we will be interested in deriving bounds of the following form: with probability at least $1-\delta$ under $P_{{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}} =P_{{\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}}$, $$\label{eq:conditional_pacb_gen_error_def}
\abs{ \Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}} \lefto[{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}\right] } \leq \epsilon.$$ Similarly, in the single-draw setting, the bounds of interest will be of the following form: with probability at least $1-\delta$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}=P_{W\vert {\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}P_{{\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}}$, $$\label{eq:conditional_sd_gen_error_def}
\abs{ {\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}} \leq \epsilon.$$ As we establish in Theorem \[thm:hoeffding\_genshat\_to\_gens\] below, the probabilistic bounds on ${\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}$ given in  and  can be converted into probabilistic bounds on ${{\textnormal{gen}}(W,{\boldsymbol{Z}}({\boldsymbol{S}}))}$ by adding a $\delta$-dependent penalty term.

\[thm:hoeffding\_genshat\_to\_gens\] Let ${\widetilde{\boldsymbol{Z}}}=(\tilde Z_1,\dots,\tilde Z_{2n})\in \mathcal{Z}^{2 n}$ consist of $2n$ training samples generated from $P_Z$ and let ${\boldsymbol{S}}$ be a random vector, independent of ${\widetilde{\boldsymbol{Z}}}$, with entries drawn independently from a $\mathrm{Bern}(1/2)$ distribution. Let ${\boldsymbol{Z}}({\boldsymbol{S}})$ denote the subset of ${\widetilde{\boldsymbol{Z}}}$ obtained through ${\boldsymbol{S}}$ by the rule $Z_i(S_i)=\tilde Z_{i+S_in}$, for $i=1,\dots,n$. Also, let $\bar {\boldsymbol{S}}$ be the modulo-$2$ complement of ${\boldsymbol{S}}$. Let $P_{W\vert {\boldsymbol{Z}}({\boldsymbol{S}})}$ be a randomized learning algorithm.[^6] Assume that $\ell(w,z)$ is bounded on $[a,b]$ for all $w\in \mathcal W$ and all $z\in\mathcal{Z}$. Also, assume that the following two probabilistic inequalities hold: with probability at least $1-\delta$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$, $$\label{eq:pf_of_lem_genShat_condition}
\abs{{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}} \leq \epsilon_{\textnormal{SD}}(\delta)$$ and with probability at least $1-\delta$ under $P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$, $$\label{eq:pf_of_lem_genShat_condition_pb}
\abs{\Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}}\lefto[{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}\right]} \leq \epsilon_{\textnormal{PB}}(\delta).$$ Then, with probability at least $1-\delta$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$, $$\label{eq:lem_genShat_to_gen_bound}
\abs{ \textnormal{gen}(W,{\boldsymbol{Z}}({\boldsymbol{S}})) } \leq \epsilon_{\textnormal{SD}}\lefto(\frac{\delta}{2}\right) +  \sqrt{\frac{(b-a)^2}{2n}\log\frac{4}{\delta}}$$ and with probability at least $1-\delta$ under $P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$, $$\label{eq:lem_genShat_to_gen_bound_pb}
\abs{\Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}}\lefto[\textnormal{gen}(W,{\boldsymbol{Z}}({\boldsymbol{S}}))\right]} \leq \epsilon_{\textnormal{PB}}\lefto(\frac{\delta}{2}\right) +  \sqrt{\frac{(b-a)^2}{2n}\log\frac{4}{\delta}}.$$

Since $\ell(w,Z_i(S_i))$ is bounded on $[a,b]$ for all $i=1,\dots,n$, it is $(b-a)/2$-subgaussian for all $w\in \mathcal{W}$. From this, it follows that $L_{{\boldsymbol{Z}}(\bar{\boldsymbol{S}})}(w)$ is $(b-a)/2\sqrt{n}$-subgaussian for all $w\in \mathcal{W}$. Hence, using Hoeffding’s inequality, stated in Lemma \[lem:hoeffdings\_inequality\], we have that, for all $\epsilon>0$,

[rCl]{} &= &

with probability no larger than $\delta=2\exp(-2\epsilon^2n/(b-a)^2)$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$. From this it follows that, with probability at least $1-\delta$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$, $$\label{eq:genshat_to_gens}
    \abs{ L_{{\boldsymbol{Z}}(\bar{\boldsymbol{S}})}(W) - \Exop_{P_Z}\lefto[\ell(W,Z)\right] } \leq \sqrt{\frac{(b-a)^2}{2n}\log\frac{2}{\delta}}.$$ Now note that, by the triangle inequality, $$\abs{{{\textnormal{gen}}(W,{\boldsymbol{Z}}({\boldsymbol{S}}))}} \leq \abs{{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}} + \abs{ L_{{\boldsymbol{Z}}(\bar{\boldsymbol{S}})}(W) - \Exop_{P_Z}\lefto[\ell(W,Z)\right] } .$$ The result in  now follows by combining  and  via the union bound and performing the substitution $\delta\rightarrow \delta/2$. The proof of  follows along the same lines.

We now turn to proving an exponential inequality similar to Theorem \[thm:unconditional\_subgaussian\], but for the random-subset setting. This inequality will later be used to derive generalization bounds of the forms given in , , and .

\[thm:conditional\_bounded\_inequality\] Consider the setting of Theorem \[thm:hoeffding\_genshat\_to\_gens\]. Then, for all $\lambda\in \reals$, $$\label{eq:conditional_inequality_thm}
    \Exop_{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}} \lefto[{\exp\lefto(\lambda {\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}-\frac{\lambda^2(b-a)^2}{2n}-\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})  \right)} \right]\leq 1.$$

Due to the boundedness of $\ell(\cdot,\cdot)$, the random variable $\ell(W,Z_i(\bar S_i))-\ell(W,Z_i(S_i))$ is bounded on $[(a-b),(b-a)]$ for $i=1,\dots,n$. As remarked in Lemma \[lem:hoeffdings\_inequality\], this implies that it is $(b-a)$-subgaussian, and that ${\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}$ therefore is $(b-a)/\sqrt{n}$-subgaussian. Furthermore, ${\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}$ enjoys the symmetry property ${\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}=-\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, \bar{\boldsymbol{S}})$. From this, it follows that $\Exop_{P_{{\boldsymbol{S}}}}\lefto[{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}\right]=0$. By the definition of subgaussianity, we therefore have that $$\Exop_{P_{{\boldsymbol{S}}} }\lefto[\exp(\lambda {\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})})\right] \leq \exp\left(\frac{\lambda^2(b-a)^2}{2n} \right).$$ Reorganizing terms and taking the expectation with respect to $P_{W\!{\widetilde{\boldsymbol{Z}}}}$, we obtain $$\label{eq:where_we_can_choose_other_QWZ_in_thm}
\Exop_{P_{W\!{\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}} }\lefto[\exp\left(\lambda {\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}- \frac{\lambda^2 (b-a)^2}{2n} \right) \right] \leq 1.$$ Now let $\setE=\textnormal{supp}(P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}})$ be the support of $P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$. Then,  implies that $$\Exop_{P_{W\!{\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}} }\lefto[1_\setE \cdot \exp\left(\lambda {\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}- \frac{\lambda^2 (b-a)^2}{2n} \right) \right] \leq 1.$$ Since $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ is induced from $P_{W\vert {\widetilde{\boldsymbol{Z}}}{\boldsymbol{S}}}$ by the probability mass function $P_{{\boldsymbol{S}}}$, the probability distribution $P_{W\!{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$ is absolutely continuous with respect to $P_{W\!{\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}}$. We can therefore perform a change of measure to $P_{W \! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$, as per [@polyanskiy19-a Prop. 17.1(4)], after which the desired result follows.

Similar to the discussion in Remark \[rem:uncond\_conversion\_to\_Q\_bounds\], Theorem \[thm:conditional\_bounded\_inequality\] holds *verbatim* with $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ replaced by an auxiliary conditional distribution $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$, provided that a suitable absolute continuity assumption holds. This is detailed in the following remark.

\[rem:cond\_conversion\_to\_Q\_bounds\] Consider the setting of Theorem \[thm:hoeffding\_genshat\_to\_gens\]. Also, assume that the absolute continuity assumption $P_{W\!{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}\ll Q_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}}$ holds for some conditional distribution $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$ on $\mathcal{W}$. Then, $$\label{eq:conditional_inequality_thm_with_Q}
    \Exop_{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}} \lefto[{\exp\lefto(\lambda {\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}-\frac{\lambda^2(b-a)^2}{2n}-\log \frac{\dv P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }{\dv Q_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}} } \right)} \right]\leq 1.$$ The proof of  is exactly the same as the proof of Theorem \[thm:conditional\_bounded\_inequality\], except that we choose $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$ in place of $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ in .

For the bounds that we will later derive, the optimal choice is $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}=P_{W\vert {\widetilde{\boldsymbol{Z}}}}$. However, similar to the standard setting, this choice is not always feasible when one is interested in numerically evaluating the bounds. While it is technically possible to compute $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ for a given instance of ${\widetilde{\boldsymbol{Z}}}$ by marginalizing out ${\boldsymbol{S}}$, this would involve executing the probabilistic learning algorithm $P_{W\vert {\boldsymbol{Z}}({\boldsymbol{S}})}$ a total of $2^n$ times. For many algorithms, this is prohibitively expensive from a computational standpoint. Therefore, it can be convenient to have the choice of relaxing the bound by expressing it in terms of some auxiliary distribution $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$, suitably chosen so as to trade accuracy with computational complexity.

In the remainder of this section, we will use Theorem \[thm:conditional\_bounded\_inequality\] to derive an average generalization bound, as well as PAC-Bayesian bounds and single-draw bounds. We start with the average generalization bound.

Average Generalization Error Bounds {#sec:cond_exp}
-----------------------------------

In the same spirit as Corollary \[cor:exp\_uncond\], the following bound on the average generalization error, which is explicit in the conditional mutual information $I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$, is directly derived from Theorem \[thm:conditional\_bounded\_inequality\].

\[cor:exp\_cond\] Under the setting of Theorem \[thm:hoeffding\_genshat\_to\_gens\], $$\label{eq:cor_exp_cond}
    \abs{ \Ex{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}{ \textnormal{gen}(W,{\boldsymbol{Z}}({\boldsymbol{S}})) }} \leq \sqrt{\frac{2(b-a)^2}{n}I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})}.$$

Starting from , we apply Jensen’s inequality, which results in $$\exp\lefto(\lambda\Exop_{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}\lefto[{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}\right] - \frac{\lambda^2(b-a)^2}{2n} 
 -\Ex{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}{\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}} \right)  \leq   1.$$ From , it follows that $\Exop_{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}\lefto[{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}\right] = \Exop_{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}\lefto[\textnormal{gen}(W,{\boldsymbol{Z}}({\boldsymbol{S}}))\right]$, since $W$ and ${\boldsymbol{Z}}(\bar{\boldsymbol{S}})$ are independent. Also, we have that $$\Exop_{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}\lefto[\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})\right] = \conrelent{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}P_{{\boldsymbol{S}}} }{P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}} }{P_{{\widetilde{\boldsymbol{Z}}}}}=I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}).$$ We therefore get, after reorganizing terms, $$\lambda\Exop_{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}}({\boldsymbol{S}}))}\right] - \frac{\lambda^2(b-a)^2}{2n} 
 -\conrelent{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}P_{{\boldsymbol{S}}} }{P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}} }{P_{{\widetilde{\boldsymbol{Z}}}}}  \leq   0.$$ Setting $\lambda = n \Exop_{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}}({\boldsymbol{S}}))}\right] / (b-a)^2$ to optimize the bound, we obtain $$\label{eq:exp_cond_final_line_of_proof}
    \Exop_{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}^2\lefto[{{\textnormal{gen}}(W,{\boldsymbol{Z}}({\boldsymbol{S}}))}\right] - \frac{2(b-a)^2}{n}\conrelent{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}P_{{\boldsymbol{S}}} }{P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}} }{P_{{\widetilde{\boldsymbol{Z}}}}} \leq 0$$ from which  follows directly.

The bound in  recovers the result from [@steinke20-a Cor. 5.2]. As detailed in Remark \[rem:cond\_conversion\_to\_Q\_bounds\], we can substitute $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$ for $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ in  to obtain a more general but weaker bound in terms of the conditional relative entropy $\conrelent{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}P_{{\boldsymbol{S}}} }{Q_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}} }{P_{{\widetilde{\boldsymbol{Z}}}}}$, provided that an appropriate absolute continuity assumption is satisfied.

Under some conditions, the bound in Corollary \[cor:exp\_cond\] can be shown to be tighter than that in Corollary \[cor:exp\_uncond\] for the case of a bounded loss function. Indeed, using the chain rule for mutual information, the Markov property $({\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})$—${\boldsymbol{Z}}({\boldsymbol{S}})$—$W$, and the fact that ${\boldsymbol{Z}}({\boldsymbol{S}})$ is a deterministic function of $({\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})$, we can rewrite the bound in  as $$\textnormal{gen}(W,{\boldsymbol{Z}}({\boldsymbol{S}})) \leq \sqrt{ \frac{(b-a)^2}{2n}I(W;
{\boldsymbol{Z}}({\boldsymbol{S}}))
} = \sqrt{ \frac{(b-a)^2}{2n}\left(I(W;{\widetilde{\boldsymbol{Z}}})+I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}) \right) }.$$ Hence, if $I(W;{\widetilde{\boldsymbol{Z}}})>3I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$, the bound in Corollary \[cor:exp\_cond\] is tighter than that in Corollary \[cor:exp\_uncond\]. In particular, note that there are many practical scenarios in which the bound in Corollary \[cor:exp\_uncond\] is vacuous because $I(W;{\boldsymbol{Z}}({\boldsymbol{S}}))=\infty$. On the contrary, $I(W;{\boldsymbol{S}}\vert{\widetilde{\boldsymbol{Z}}})\leq n\log 2$.

PAC-Bayesian Generalization Error Bounds {#sec:cond_pacb}
----------------------------------------

We now turn to PAC-Bayesian bounds of the form given in . The next corollary provides bounds that are analogous to those in Corollary \[cor:pacb\_uncond\], but for the random-subset setting. The bounds in the corollary are novel, and extend known PAC-Bayesian bounds to the random-subset setting.

\[cor:pacb\_cond\] Under the setting of Theorem \[thm:hoeffding\_genshat\_to\_gens\], the following holds with probability at least $1-\delta$ under $P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$ for all $t>0$:

[rCl]{}\[eq:cor\_pacb\_cond\] &&\
\[eq:cor\_pacb\_cond\_second\] && .

Here, the first inequality is a data-dependent bound, while the second provides a data-independent relaxation.

Since the proof follows along the same lines as that of Corollary \[cor:pacb\_uncond\], we only highlight the differences. We start from , apply Jensen’s inequality with respect to $P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$, and note that $$\Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }\lefto[{{\imath}(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})}\right] = \relent{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}{P_{W\vert {\widetilde{\boldsymbol{Z}}}} }.$$ To obtain , we use  and set $\lambda = n \Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}\lefto[{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}\right] / (b-a)^2$. To prove , we apply Markov’s inequality to $\relent{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}{P_{W\vert {\widetilde{\boldsymbol{Z}}}} }^t$, similarly to . Combining the resulting inequality with  through the union bound and then performing the substitution $\delta \rightarrow \delta/2$, we obtain the desired result.

For the case $t=1$ in , we have $\Exop_{P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }\lefto[\relent{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}{P_{W\vert {\widetilde{\boldsymbol{Z}}}} }\right]=I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$. The corresponding bound extends the results in [@steinke20-a] by providing a PAC-Bayesian generalization error bound in terms of the conditional mutual information $I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$. Similar to the discussion following Corollary \[cor:exp\_cond\], this bound is, under some conditions, tighter than the corresponding bounds for the standard setting in Corollary \[cor:pacb\_uncond\]. Much like the moment bounds in  and , the bound in  illustrates a trade-off between the confidence and the tightness of the generalization estimate, mediated by the magnitude of the higher moments of $\relent{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}{P_{W\vert {\widetilde{\boldsymbol{Z}}}} }$. Also, as indicated in Remark \[rem:cond\_conversion\_to\_Q\_bounds\], if the appropriate absolute continuity criterion is satisfied, we can replace $P_{W\vert{\widetilde{\boldsymbol{Z}}}}$ with $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$ in  and  to obtain more general bounds that are better suited for numerical evaluations.

Single-Draw Generalization Error Bounds {#sec:cond_sd}
---------------------------------------

In this section, we will derive several bounds on the single-draw generalization error  in the random-subset setting. Three different approaches will be used to obtain these bounds. The first one relies on the exponential inequality given in Theorem \[thm:conditional\_bounded\_inequality\], and results in a data-dependent bound from which several data-independent relaxations follow. The second one relies on Lemma \[lem:strong\_converse\_lemma\], and allows us to derive a bound that is explicit in the tail of the conditional information density, similar to Theorem \[thm:unconditional\_hypothesis\_main\_bound\]. Essentially equivalent versions of the data-independent relaxations obtainable via the first approach can be derived from this tail-based bound. The third approach, which is inspired by [@esposito19-12a], builds on repeated applications of Hölder’s inequality. This results in a family of data-independent bounds. Through this approach, we extend many of the results for bounded loss functions in [@esposito19-12a] to the random-subset setting.

### Generalization Bounds from the Exponential Inequality

In the next two corollaries, we derive novel bounds that are analogous to the ones in Corollaries \[cor:singledraw\_uncond\] and \[cor:singledraw\_uncond\_alphadiv\_leakage\], but for the random-subset setting.

\[cor:singledraw\_cond\] Under the setting of Theorem \[thm:hoeffding\_genshat\_to\_gens\], the following holds with probability at least $1-\delta$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$ for all $t>0$:[^7]

[rCl]{}\[eq:cor\_singledraw\_cond\] &&\
\[eq:cor\_singledraw\_cond\_second\] && .

Here, the first inequality provides a data-dependent bound and the second is a data-independent relaxation. In , the term $\widetilde M_t(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$ is the $t$th root of the $t$th central moment of $\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$: $$\label{eq:def_tilde_M_conditional}
\widetilde M_t(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}) = \Exop^{1/t}_{P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}\lefto[\abs{ \imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}) - I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}) }^t \right].$$

The proof is analogous to that of Corollary \[cor:singledraw\_uncond\]. We start by applying Markov’s inequality in the form of  to , which with $\lambda=n{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}/(b-a)^2$ results in . We then apply  with $U=\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$. Combining the resulting inequality with  through the union bound, we obtain  after performing the substitution $\delta\rightarrow \delta/2$.

By increasing $t$ in , a more benign $\delta$-dependence can be obtained by letting the bound depend on higher central moments of ${{\imath}(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})}$. The tightness of the resulting bound depends on how well these higher moments are controlled. As usual, we can get more general bounds by replacing $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ with an arbitrary $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$, provided that a suitable absolute continuity assumption is satisfied.

Just as in Corollary \[cor:singledraw\_uncond\_alphadiv\_leakage\], we can derive alternative data-independent relaxations for the data-dependent bound in . We present these novel bounds in the following corollary. The first bound is given in terms of $\log\esssup_{P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}} \Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}}}\lefto[ \exp\lefto(\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})\right) \right]$, which is a lower bound to the conditional maximal leakage . The second bound depends on the conditional Rényi divergence .

\[cor:singledraw\_cond\_alphadiv\_leakage\] Under the setting of Theorem \[thm:hoeffding\_genshat\_to\_gens\], the following inequalities hold with probability at least $1-\delta$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$: $$\label{eq:cor_singledraw_cond_leakage}
\abs{ {\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}} \leq \sqrt{\frac{2(b-a)^2}{n}\left(\log\esssup_{P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}} \Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}}}\lefto[ \exp\lefto(\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})\right) \right] +2\log \frac{2}{\delta}\right)}$$ and, for all $\alpha,\gamma> 1$ such that $1/\alpha+1/\gamma = 1$, $$\begin{gathered}
\label{eq:cor_singledraw_cond_alphadiv}
\abs{ {\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}} \leq \bigg[\frac{2(b-a)^2}{n}\bigg(\frac{\alpha-1}{\alpha}\alphaconrelent{\alpha}{P_{W\vert {\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}P_{{\boldsymbol{S}}} }{P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}}}{P_{{\widetilde{\boldsymbol{Z}}}}} \\+ \frac{\gamma-1}{\gamma}\alphaconrelent{\gamma}{P_{W\vert {\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}P_{{\boldsymbol{S}}} }{P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}}}{P_{{\widetilde{\boldsymbol{Z}}}}}+2\log \frac{2}{\delta}\bigg)\bigg]^{1/2}.\end{gathered}$$

Analogously to the proof of Corollary \[cor:singledraw\_uncond\_alphadiv\_leakage\], we start from the inequality in  and bound $\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$. With probability $1$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$, $$\label{eq:singledraw_cond_leakage_esssup_weakening}
\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}) = \log \frac{\dv P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }{\dv P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} } \leq \log \esssup_{P_{{\boldsymbol{S}}\vert W\!{\widetilde{\boldsymbol{Z}}}}} \frac{\dv P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }{\dv P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} } \leq \log \esssup_{P_{{\boldsymbol{S}}} } \frac{\dv P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }{\dv P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }.$$ Here, the second inequality holds due to the absolute continuity property $P_{W\!{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}\ll P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$. By applying Markov’s inequality with respect to $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ to the random variable $\dv P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}/\dv P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$, we conclude that, with probability at least $1-\delta$ under $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$: $$\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}}) \leq \log  \esssup_{P_{{\boldsymbol{S}}} } \Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}}}\lefto[ \frac{\dv P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }{\dv P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }\right] + \log\frac{1}{\delta}.$$ Finally, with probability $1$ under $P_{{\widetilde{\boldsymbol{Z}}}}$, we get $$\label{eq:cor_cond_sd_leakage_proof_infdens_bound_last}
    \log  \esssup_{P_{{\boldsymbol{S}}} } \Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}}}\lefto[ \frac{\dv P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }{\dv P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }\right] \leq \log \esssup_{P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} } \Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}}}\lefto[ \frac{\dv P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }{\dv P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }\right].$$ Using the union bound to combine  with the probabilistic inequality on ${{\imath}(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})}$ resulting from -, we obtain  after performing the substitution $\delta\rightarrow \delta/2$.

To prove , we apply Markov’s inequality and then perform a change of measure from $P_{W\vert {\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$ to $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ to conclude that, with probability at least $1-\delta$ under $P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$,

[rCl]{} (W,) && \_[P\_[W ]{}P\_ [ ]{}]{}+\
&=& \_[P\_[W]{}P\_ [ ]{}]{}+ .\[eq:infodens\_bound\_by\_holder\]

Next, we apply Hölder’s inequality thrice as follows. Let $\alpha,\gamma,\alpha',\gamma',\tilde \alpha, \tilde \gamma> 1$ be constants such that $1/\alpha+1/\gamma=1/\alpha'+1/\gamma'=1/\tilde \alpha + 1/\tilde \gamma=1$. Then,

[rCl]{} & & \_[P\_[W]{}P\_ [ ]{}]{}= \_[P\_[W]{}P\_ P\_]{}\
&& \_[P\_[W]{}P\_ ]{}\
&& \_[P\_ ]{}\
&&\_[P\_ ]{}\^[1/’]{}\_[P\_ ]{}\^[1/’]{}. \[eq:holdering\_gives\_alphadiv\]

We now substitute  into  and set $\alpha=\alpha'=\tilde \alpha$, which implies $\gamma=\gamma'=\tilde \gamma$. Using , we conclude that, with probability at least $1-\delta$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$, $$\begin{gathered}
\label{eq:infodens_bounded_by_alpha_divs}
\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})   \leq \frac{\alpha-1}{\alpha}\alphaconrelent{\alpha}{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}P_{{\boldsymbol{S}}} }{P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}}}{P_{{\widetilde{\boldsymbol{Z}}}}} \\+ \frac{\gamma-1}{\gamma}\alphaconrelent{\gamma}{P_{W\vert {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}P_{{\boldsymbol{S}}} }{P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}}}{P_{{\widetilde{\boldsymbol{Z}}}}}+\log\frac{1}{\delta}.\end{gathered}$$ Combining  with  through the union bound and performing the substitution $\delta\rightarrow \delta/2$, we obtain .

As usual, we can replace $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ by some auxiliary $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$ to get more general bounds, provided that a suitable absolute continuity assumption is satisfied.

We can relax the bound in  and express it in terms of the conditional maximal leakage $\mathcal{L}({\boldsymbol{S}}\rightarrow W \vert {\widetilde{\boldsymbol{Z}}})$. Indeed, we have the following inequality:

[rCl]{} \_[P\_[ ]{}]{} \_[P\_[W]{}]{}&& \_[P\_]{} \_[P\_[W]{}]{}\
\[eq:lower\_bound\_to\_conditional\_leakage\] &=& (W).

Substituting  into , we obtain the desired generalization bound. The bound in  and its relaxation in terms of the conditional maximal leakage can be tighter than the maximal leakage bound in [@esposito19-12a Cor. 9].[^8] This is the case since the conditional maximal leakage $\mathcal{L}({\boldsymbol{S}}\rightarrow W \vert {\widetilde{\boldsymbol{Z}}})$ is upper-bounded by the maximal leakage $\mathcal{L}({\boldsymbol{Z}}({\boldsymbol{S}})\rightarrow W )$. We prove this result in the following theorem.

\[propo:leakage\_bounds\_cond\_leakage\] Consider the setting of Theorem \[thm:hoeffding\_genshat\_to\_gens\]. Then, $$\label{eq:propo_leakage_bounds_cond_leakage}
\mathcal{L}({\boldsymbol{S}}\rightarrow W \vert {\widetilde{\boldsymbol{Z}}}) \leq \mathcal{L}( {\boldsymbol{Z}}({\boldsymbol{S}}) \rightarrow W).$$

Because of the Markov property $({\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})$—${\boldsymbol{Z}}({\boldsymbol{S}})$—$W$ and the fact that ${\boldsymbol{Z}}({\boldsymbol{S}})$ is a deterministic function of $({\widetilde{\boldsymbol{Z}}},{\boldsymbol{S}})$, the equality $\mathcal{L}({\boldsymbol{Z}}({\boldsymbol{S}}) \rightarrow W) =\mathcal{L}(({\widetilde{\boldsymbol{Z}}},{\boldsymbol{S}}) \rightarrow W)$ holds [@issa16-a Lem. 1]. We begin by moving one essential supremum outside of the expectation:

[rCl]{}\[eq:cond\_max\_leak\_prop\_proof\_eq\_1\] ((,)W) = \_[P\_W]{}\_[P\_ ]{} \_[P\_W]{}.

Now, let $\setE_{{\widetilde{\boldsymbol{Z}}}}=\textnormal{supp}(P_{W\vert {\widetilde{\boldsymbol{Z}}}})$. It follows from  that $$\mathcal{L}(({\widetilde{\boldsymbol{Z}}},{\boldsymbol{S}})\rightarrow W) 
\geq \log \esssup_{P_{{\widetilde{\boldsymbol{Z}}}} } \Exop_{P_W}\lefto[ 1_{\setE_{{\widetilde{\boldsymbol{Z}}}} } \esssup_{P_{{\boldsymbol{S}}}} \frac{\dv P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}}{\dv P_W \! P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}} }\right].$$ Next, we perform a change of measure from $P_W$ to $P_{W\vert{\widetilde{\boldsymbol{Z}}}}$:

[rCl]{} \_[P\_ ]{} \_[P\_W]{}= \_[P\_ ]{} \_[P\_[W]{} ]{}.

Finally, since $\dv P_W/\dv P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ is independent of ${\boldsymbol{S}}$,

[rCl]{} \_[P\_ ]{} \_[P\_[W]{} ]{}&=&\_[P\_ ]{} \_[P\_[W]{} ]{}\
&=&(W).

### Generalization Bounds from the Strong Converse {#sec:cond_sd_strong_conv}

In this section, we will use Lemma \[lem:strong\_converse\_lemma\] to derive single-draw generalization error bounds in the random-subset setting. In Theorem \[thm:conditional\_hypothesis\_main\_bound\] below, we use Lemma \[lem:strong\_converse\_lemma\] to obtain a novel bound in terms of the tail of the conditional information density ${{\imath}(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})}$.

\[thm:conditional\_hypothesis\_main\_bound\] Under the setting of Theorem \[thm:hoeffding\_genshat\_to\_gens\], with probability at least $1-\delta$ under $P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$, $$\label{eq:thm_conditional_hypothesis_main_bound}
    \abs{{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}}
    \leq\sqrt{ \frac{2(b-a)^2}{n}
    \left(
        \gamma + \log\lefto(\frac{2}{\delta-P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}\lefto[\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})\geq \gamma\right]} \right)
    \right)}.$$ This is valid for all $\gamma$ such that the right-hand side is defined and real.

We will use Lemma \[lem:strong\_converse\_lemma\] with $P=P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$, $Q=P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$ and $$\label{eq:high_error_event_cond}
\setE=\{W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}}: \abs{{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}}>\epsilon \}.$$ Let the set $\setE_{W\! {\widetilde{\boldsymbol{Z}}}}=\{{\boldsymbol{S}}: (W,{\widetilde{\boldsymbol{Z}}},{\boldsymbol{S}})\in \setE \}$ denote the fibers of $\setE$ with respect to $W$ and ${\widetilde{\boldsymbol{Z}}}$. As noted in the proof of Theorem \[thm:conditional\_bounded\_inequality\], ${\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}$ is a $(b-a)/\sqrt{n}$-subgaussian random variable with $\Exop_{P_{{\boldsymbol{S}}}}\lefto[{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}\right]=0$. By using Hoeffding’s inequality (Lemma \[lem:hoeffdings\_inequality\]), we therefore conclude that, for all $W$ and ${\widetilde{\boldsymbol{Z}}}$, $$\label{eq:mcdiarmid_es_bound}
P_{{\boldsymbol{S}}}\lefto[\setE_{W\!{\widetilde{\boldsymbol{Z}}}} \right] \leq 2 \exp\lefto(-\frac{n\epsilon^2}{2(b-a)^2} \right).$$ From this, it follows that $Q[\setE]\leq  2\exp\lefto(-n\epsilon^2/2(b-a)^2 \right)$. Inserting this inequality into , we get $$\label{eq:strong_conv_cond_solve_for_eps}
    P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}\lefto[\abs{{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}}>\epsilon\right] \leq P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}\lefto[\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})\geq \gamma\right] + 2\exp\lefto(\gamma-\frac{n\epsilon^2}{2(b-a)^2}\right).$$ We obtain the desired result by requiring the right-hand side of  to be equal to $\delta$ and solving for $\epsilon$.

Similar to the discussion in Remark \[rem:cond\_conversion\_to\_Q\_bounds\], a completely analogous result holds with an auxiliary distribution $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$ in place of $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$, provided that a suitable absolute continuity assumption is satisfied.

As for the bound in Theorem \[thm:unconditional\_hypothesis\_main\_bound\], the bound in  illustrates that the faster the rate of decay of the tail of the conditional information density, the sharper the generalization bound. Specifically, the parameter $\gamma$ has to be chosen large enough so that the argument of the logarithm is positive, but a greater $\gamma$ also contributes to an increased value for the bound.

The bound in Theorem \[thm:conditional\_hypothesis\_main\_bound\] can be relaxed to give essentially equivalent versions of some of the previously presented data-independent bounds. We show this in the following remarks.

Markov’s inequality implies that

[rCl]{}\[eq:moment\_bound\_from\_hyptest\_markov\_cond\] P\_[W ]{}&&

where $\widetilde M_t(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})$ is defined in . Next, we set $$    \gamma =I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})+\frac{\widetilde M_t(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})}{(\delta/2)^{1/t}}$$ which, once substituted into , implies that $P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}\lefto[\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})\geq \gamma \right] \leq {\delta}/{2}$. Using this inequality in , we conclude that, with probability at least $1-\delta$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$, $$\abs{{\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}}
    \leq\sqrt{ \frac{2(b-a)^2}{n}
    \left(
        I(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})+\frac{\widetilde M_t(W;{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})}{(\delta/2)^{1/t}} + \log\frac{4}{\delta}
    \right)}.$$ This coincides with the bound in , up to a $(2(b-a)^2/n)\log 2$ term inside the square root.

Note that

[rCl]{} P\_[W ]{}&& P\_[W]{}\
&& \_[P\_]{}P\_[W]{}.

By upper-bounding the $\esssup$ as in  and using Markov’s inequality, we conclude that

[rcl]{} P\_[W ]{}&& (-) \_[P\_ ]{}\
&=& ((W)-).

Setting $\gamma=\mathcal{L}({\boldsymbol{S}}\rightarrow W\vert {\widetilde{\boldsymbol{Z}}}) + \log(2/\delta)$ and substituting the resulting upper-bound on the probability $P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}\lefto[\imath(W,{\boldsymbol{S}}\vert {\widetilde{\boldsymbol{Z}}})\geq \gamma\right]$ into , we conclude that, with probability at least $1-\delta$ under $P_{W\!{\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}$, $$\abs{ {\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}} \leq \sqrt{\frac{2(b-a)^2}{n}\left(\mathcal{L}({\boldsymbol{S}}\rightarrow W\vert {\widetilde{\boldsymbol{Z}}})+\log 2 + 2\log \frac{2}{\delta}\right)}.$$ This recovers the conditional maximal leakage weakening of , as detailed in , up to a $(2(b-a)^2/n)\log 2$ term inside the square root.

### Generalization Bounds from a Hölder-Based Inequality

We now present a third approach to obtain data-independent single-draw bounds in the random-subset setting. The approach is based on a proof technique developed in [@esposito19-12a], where similar bounds are derived in the standard setting. We first prove a useful inequality in Theorem \[thm:esposito\_cond\], from which several generalization bounds follow.

\[thm:esposito\_cond\] Under the setting of Theorem \[thm:hoeffding\_genshat\_to\_gens\], for all $\alpha, \gamma,\alpha',\gamma',\tilde \alpha, \tilde \gamma> 1$ such that $1/\alpha + 1/\gamma =1/\alpha'+1/\gamma'=1/\tilde \alpha + 1/\tilde \gamma =1$ and all measurable sets $\setE\in \mathcal{W}\times \mathcal{Z}^{2n}\times \{0,1\}^n$, $$\label{eq:thm_esposito_cond}
P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}[\setE] 
\leq \Exop_{P_{{\widetilde{\boldsymbol{Z}}}} }^{1/\tilde \gamma}\lefto[ \Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}}}^{\tilde \gamma/\gamma '}\lefto[P_{{\boldsymbol{S}}}^{\gamma'/\gamma}\lefto[\setE_{W\! {\widetilde{\boldsymbol{Z}}}}\right] \right] \right]   \cdot  \Exop_{P_{{\widetilde{\boldsymbol{Z}}}}}^{1/\tilde \alpha}\lefto[ \Exop_{P_{W\vert {\widetilde{\boldsymbol{Z}}}}}^{\tilde \alpha/\alpha '}\lefto[\Exop_{P_S}^{\alpha ' /\alpha}\lefto[\exp\lefto(\alpha\imath(W,{\boldsymbol{S}}\vert{\widetilde{\boldsymbol{Z}}})\right) \right] \right] \right].$$ Here, $\setE_{W\!{\widetilde{\boldsymbol{Z}}}}=\{{\boldsymbol{S}}: (W,{\widetilde{\boldsymbol{Z}}},{\boldsymbol{S}})\in \setE \}$ denotes the fibers of $\setE$ with respect to $W$ and ${\widetilde{\boldsymbol{Z}}}$.

First, we rewrite $P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}[\setE] $ in terms of the expectation of the indicator function $1_\setE$ and perform a change of measure:

[rCl]{} P\_[W ]{}\[\]&=& \_[P\_[W]{}P\_[ ]{}]{} = \_[ P\_[W]{} P\_ P\_]{} .

To obtain the desired result, we apply Hölder’s inequality thrice. Let $\alpha, \gamma,\alpha',\gamma',\tilde \alpha, \tilde \gamma> 1$ be constants such that $1/\alpha + 1/\gamma =1/\alpha'+1/\gamma'=1/\tilde \alpha + 1/\tilde \gamma =1$. Then,

[rCl]{} [P\_[W ]{}]{}\[\] &&\_[P\_[W]{}P\_]{}\
&&\_[P\_]{}\
&&\_[P\_]{}\^[1/]{}\_[P\_]{}\^[1/]{}.

Similar to the discussion in Remark \[rem:cond\_conversion\_to\_Q\_bounds\], the result in Theorem \[thm:esposito\_cond\] would still hold if we were to substitute an auxiliary distribution $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$ for $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$, provided that a suitable absolute continuity condition is satisfied.

By choosing particular values for the three free parameters in the inequality , we can derive generalization bounds in terms of various information-theoretic quantities. We will focus on a bound that depends on the conditional $\alpha$-mutual information $\alphaconMI{\alpha}{W }{{\boldsymbol{S}}}{{\widetilde{\boldsymbol{Z}}}}$, which can be relaxed to obtain a bound in terms of the conditional Rényi divergence $\alphaconrelent{\alpha}{P_{W\vert {\widetilde{\boldsymbol{Z}}}\!{\boldsymbol{S}}}P_{{\boldsymbol{S}}} }{P_{W\vert {\widetilde{\boldsymbol{Z}}}}P_{{\boldsymbol{S}}}}{P_{{\widetilde{\boldsymbol{Z}}}}}$ or be specialized to obtain a bound that depends on the conditional maximal leakage $\mathcal{L}({\boldsymbol{S}}\rightarrow W\vert {\widetilde{\boldsymbol{Z}}})$.

\[cor:singledraw\_esposito\_cond\_alphaMI\] Under the setting of Theorem \[thm:hoeffding\_genshat\_to\_gens\], the following holds with probability at least $1-\delta$ under $P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}$ for all $\alpha > 1$: $$\label{eq:cor_singledraw_esposito_cond_alphaMI}
\abs{ {\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}} \leq \sqrt{\frac{2(b-a)^2}{n}\left(\alphaconMI{\alpha}{W }{{\boldsymbol{S}}}{{\widetilde{\boldsymbol{Z}}}}+\log 2 + \frac{\alpha}{\alpha-1}\log \frac{1}{\delta}\right)}.$$

In , set $\tilde \alpha = \alpha$ and let $\alpha' \rightarrow 1$, which implies that $\tilde \gamma = \gamma$ and $\gamma' \rightarrow\infty$. Also, let $\setE$ be the error event . For this choice of parameters, the second factor in  reduces to $$\label{eq:esposito_alphami_proof_info_dens_factor}
\Exop_{P_{{\widetilde{\boldsymbol{Z}}}}}^{1/\alpha}\lefto[ \Exop^{\alpha}_{P_{W\vert {\widetilde{\boldsymbol{Z}}}}}\lefto[\Exop^{1/\alpha}_{P_S}\lefto[\exp\lefto(\alpha\imath(W,{\boldsymbol{S}}\vert{\widetilde{\boldsymbol{Z}}})\right) \right] \right] \right] = \exp\lefto(\frac{\alpha-1}{\alpha}\alphaconMI{\alpha}{W }{{\boldsymbol{S}}}{{\widetilde{\boldsymbol{Z}}}}\right).$$ Furthermore, we can bound $P_{{\boldsymbol{S}}}\lefto[\setE_{W\! {\widetilde{\boldsymbol{Z}}}}\right]$ in the first factor in  by using . Substituting  into the first factor in , we conclude that

[rCl]{}\[eq:esposito\_alphami\_proof\_E\_dep\_factor\] \_[’ ]{} \_[P\_]{}\^[1/ ]{}&=& \^[1/]{}\_[P\_]{}\
&& ( 2 (- ))\^[1/]{}.

By substituting  and  into , noting that $1/\gamma = (\alpha-1)/\alpha$, we conclude that $$P_{W\! {\widetilde{\boldsymbol{Z}}}\! {\boldsymbol{S}}}[\setE]
\leq \left( 2 \exp\lefto(-\frac{n\epsilon^2}{2(b-a)^2} \right) \right)^{\frac{\alpha-1}{\alpha} }  \cdot  \exp\lefto(\frac{\alpha-1}{\alpha}\alphaconMI{\alpha}{W }{{\boldsymbol{S}}}{{\widetilde{\boldsymbol{Z}}}}\right).$$ We obtain the desired result by requiring the right-hand side to be equal to $\delta$ and solving for $\epsilon$.

As usual, we can obtain a more general version of Corollary \[cor:singledraw\_esposito\_cond\_alphaMI\] by replacing $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ with an auxiliary distribution $Q_{W\vert {\widetilde{\boldsymbol{Z}}}}$, provided that a suitable absolute continuity assumption is satisfied.

We can also obtain a bound in terms of the conditional maximal leakage by letting $\alpha\rightarrow \infty$ in  and using that $\lim_{\alpha\rightarrow\infty} \alphaconMI{\alpha}{W }{{\boldsymbol{S}}}{{\widetilde{\boldsymbol{Z}}}}= \mathcal{L}({\boldsymbol{S}}\rightarrow W\vert {\widetilde{\boldsymbol{Z}}})$. The resulting bound is tighter than the conditional maximal leakage bound obtained from  by a $(2(b-a)^2/n)\log (2/\delta)$ term inside the square root.

Furthermore, the conditional $\alpha$-mutual information that appears in  can be relaxed to obtain a novel bound in terms of the conditional Rényi divergence of order $\alpha$. Indeed, by Jensen’s inequality, the following holds for $\alpha>1$:

[rCl]{}\[eq:cond\_alpha\_mi\_to\_cond\_renyi\_start\] & = &\_[P\_ ]{}\
& & \_[P\_ ]{}\
&=& .\[eq:cond\_alpha\_mi\_to\_cond\_renyi\_end\]

The conditional Rényi divergence bound obtained by substituting  into  is different from the one in , and there is no clear ordering between them in general. The two bounds can, however, be directly compared if we set $\alpha=\gamma=2$, or if we let $\alpha\rightarrow \infty$, and hence $\gamma \rightarrow 1$. For both of these choices of parameters, the conditional Rényi divergence bound obtained from  is tighter than  by a $(2(b-a)^2/n)\log (2/\delta)$ term inside the square root.

Conclusion
==========

We have presented a general framework for deriving generalization bounds for probabilistic learning algorithms, not only in the average sense, but also for the PAC-Bayesian and the single-draw setup. Using this framework, we recovered several known results, and also presented new ones. Due to its unifying nature, the framework enables the transfer of methods for tightening bounds in one setup to the other two setups. In particular, by reobtaining previously known results, we showed that our framework subsumes proofs that are based on the Donsker-Varadhan variational formula for relative entropy [@xu17-05a Thm. 1], [@guedj19-10a Prop. 3], on Hölder’s inequality [@esposito19-12a Thm. 1], and on the data-processing inequality [@bassily18-02a Thm. 8], [@esposito19-12a p. 10]. We further demonstrated the versatility of the framework by applying it to the random-subset setting recently introduced by Steinke and Zakynthinou [@steinke20-a]. In doing so, we were able to extend the bounds on the average generalization error obtained in [@steinke20-a] to the PAC-Bayesian setup and the single-draw setup. In addition to this, we used tools inspired by binary hypothesis testing to derive generalization bounds in terms of the tail of the conditional information density. We also obtained novel bounds in terms of the conditional maximal leakage and the conditional $\alpha$-mutual information by adapting a proof technique due to Esposito *et al.* [@esposito19-12a] to the random-subset setting.

As pointed out throughout this paper, the numerical evaluation of the presented generalization bounds requires that one replaces the marginal distribution $P_W$ (or $P_{W\vert {\widetilde{\boldsymbol{Z}}}}$ in the random-subset setting) with a suitably chosen auxiliary distribution that can be computed without *a priori* knowledge of the data distribution $P_Z$. Some possible choices, in the context of deep neural networks, are provided in [@Negrea2019], [@Dziugaite2017]. However, the extent to which information-theoretic bounds such as the ones presented in this paper can guide the design of modern machine learning algorithms remains unclear.

[^1]: This work was partly supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

[^2]: Parts of the material of this paper will be presented at the International Symposium on Information Theory (ISIT), June 2020, Los Angeles, CA. [@hellstrom-20a]

[^3]: F. Hellström and G. Durisi are with the Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden, (e-mail: {frehells,durisi}@chalmers.se).

[^4]: This issue is well understood in the PAC-Bayesian literature, where the available bounds are given in terms of an auxiliary distribution $Q_W$ that does not depend on the unknown data distribution $P_Z$.

[^5]: Note that the argument of the square root in  can be negative, but that this happens with probability at most $\delta$. Therefore, the right-hand side of  is well-defined with probability at least $1-\delta$.

[^6]: Note that, by construction, $W$ and $({\widetilde{\boldsymbol{Z}}},{\boldsymbol{S}})$ are conditionally independent given ${\boldsymbol{Z}}({\boldsymbol{S}})$.

[^7]: Note that the argument of the square root in  can be negative, but that this happens with probability at most $\delta$. Therefore, the right-hand side of  is well-defined with probability at least $1-\delta$.

[^8]: Note that $\eqref{eq:cor_singledraw_cond_leakage}$ provides a bound on ${\widehat{\textnormal{gen}}(W,{\widetilde{\boldsymbol{Z}}}, {\boldsymbol{S}})}$, whereas the bound in [@esposito19-12a Cor. 9] is on ${{\textnormal{gen}}(W,{\boldsymbol{Z}})}$. To compare the two, one therefore has to add the $\delta$-dependent penalty term in Theorem \[thm:hoeffding\_genshat\_to\_gens\].
