---
abstract: |
    We present a general approach to deriving bounds on the generalization error of randomized learning algorithms. Our approach can be used to obtain bounds on the average generalization error as well as bounds on its tail probabilities, both for the case in which a new hypothesis is randomly generated every time the algorithm is used—as often assumed in the probably approximately correct (PAC)-Bayesian literature—and in the single-draw case, where the hypothesis is extracted only once.

    For this last scenario, we present a novel bound that is explicit in the central moments of the information density. The bound reveals that the higher the order of the information density moment that can be controlled, the milder the dependence of the generalization bound on the desired confidence level.

    Furthermore, we use tools from binary hypothesis testing to derive a second bound, which is explicit in the tail of the information density. This bound confirms that a fast decay of the tail of the information density yields a more favorable dependence of the generalization bound on the confidence level.
author:
- '\'
bibliography:
- 'reference.bib'
title: Generalization Error Bounds via $m$th Central Moments of the Information Density
---

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

A recent line of research, initiated by the work of Russo and Zou [@russo16-05b] and then followed by many recent contributions [@xu17-05a; @bassily18-02a; @bu19-01a; @esposito19-12a], has focused on obtaining bounds on the generalization error of randomized learning algorithms in terms of information-theoretic quantities, such as mutual information. The resulting bounds are *deterministic*, i.e., data-independent, and allow one to assess the speed of convergence of a given learning algorithm in terms of sample complexity [@shalev-shwartz14-a p. 44].

A parallel development has taken place in the machine learning and statistics community, where the probably approximately correct (PAC)-Bayesian framework, pioneered by McAllester [@mcallester98-07a], has resulted in several upper bounds on the generalization error. These bounds, which are expressed in terms of the relative entropy between a prior and a posterior distribution on the hypothesis class (see, e.g., [@guedj19-01a] for a recent review), are typically *empirical*, i.e., data-dependent, and can be used to design learning algorithms [@catoni07-a].

One difficulty in comparing the bounds on the generalization error available in the literature is that they sometimes pertain to different quantities. To illustrate this point, we need to introduce some key quantities, which will be used in the remainder of the paper. Following the standard terminology in statistical learning theory, we let $\setZ$ be the instance space, be the hypothesis space, and $\ell: \setW\times \setZ \rightarrow \positivereals$ be the loss function. A training data set $Z^n=[Z_1,\dots,Z_n]$ is a set of $n$ samples drawn from a distribution $P_Z$ defined on $\setZ$. We denote by $P_{Z^n}$ the product distribution induced by $P_Z$. A randomized learning algorithm is characterized by a conditional probability distribution $P_{W\!\given\! Z^n}$ on $\mathcal{W}$. Finally, we let the generalization error for a given hypothesis $w$ be defined as the difference between the population and empirical risks $$\label{eq:gen}
    {\textnormal{gen}}(w,z^n)=\frac{1}{n}\sum_{k=1}^{n}\ell(w,z_k) -\Ex{P_Z}{\ell(w,Z)}.$$ Throughout the paper, we shall assume that the loss function $\ell(w,Z)$ is $\sigma$-subgaussian [@wainwright19-a Def. 2.2] under $P_Z$ for all $w\in \setW$.

The line of work initiated with [@russo16-05b] deals with bounding the average generalization error $$\label{eq:average-gen}
    \Ex{P_{W\! Z^n}}{ {{\textnormal{gen}}(W,Z^n)}}.$$ Specifically, upper bounds on the absolute value of this quantity were first presented in [@russo16-05b] and then improved in [@xu17-05a Thm. 1] and [@bu19-01a Prop. 1].

On the contrary, the PAC-Bayesian approach seeks lower bounds on the probability [@guedj19-01a] $$\label{eq:pac-bayesian}
  P_{Z^n}\lefto[\abs{\Ex{P_{W\!\given\! Z^n}}{{{\textnormal{gen}}(W,Z^n)}}} \leq \epsilon \right].$$ Characterizing such a probability, which is in the spirit of the PAC framework, is relevant when a new hypothesis $W$ is drawn from $P_{W\!\given\! Z^n}$ every time the algorithm is used. As can be verified by, e.g., comparing the proof of [@xu17-05a Lemma 1] and the proof of [@guedj19-10a Prop. 3],[^1] for the subgaussian case, one can obtain bounds both on  and on  that are explicit in the mutual information $I(W;Z^n)$ and in the relative entropy $\relent{P_{W\!\given\! Z^n}}{P_W}$, respectively, by using the Donsker-Varadhan variational formula for relative entropy.

One may also be interested in the scenario in which the hypothesis $W$ is drawn from $P_{W\!\given\! Z^n}$ only once, i.e., it is kept fixed for all uses of the algorithm. In such a scenario, which, following the terminology used in [@catoni07-a p. 12], we shall refer to as a *single-draw* scenario, the probability of interest is $$\label{eq:single-draw}
  P_{W\! Z^n}\lefto[\abs{{{\textnormal{gen}}(W,Z^n)}} \leq \epsilon \right].$$ Bounds on this probability that depend on the mutual information $I(W;Z^n)$ were provided in [@xu17-05a Thm. 3] and [@bassily18-02a]. Several novel bounds, which are explicit in information-theoretic quantities such as $f$-divergence, $\alpha$-mutual information, and maximal leakage, were recently derived in [@esposito19-12a]. Interestingly, all these bounds make use of a different set of tools compared with the ones used to establish bounds on  and , with one of the main ingredients being the data processing inequality for $f$-divergences.

Furthermore, they yield drastically different estimates for the generalization error. Specifically, let us assume that we want  to be greater than $1-\delta$ where, throughout the paper, $\delta \in (0,1)$. Then a slight refinement of the analysis in [@bassily18-02a] yields the following bound on $\epsilon$: $$\label{eq:sample_complexity_mi}
    \epsilon\geq \sqrt{\frac{2\sigma^2}{n}\left(\frac{I(W;Z^n)+H_b(\delta)}{\delta}+\log 2\right)}. $$ Here, $H_b(\delta)$ denotes the binary entropy function. Throughout the paper, $\log(\cdot)$ denotes the natural logarithm. In contrast, the analysis in [@esposito19-12a Cor. 5], yields the following bound for $\alpha>1$: $$\label{eq:sample_complexity_alpha_mi}
    \epsilon\geq \sqrt{\frac{2\sigma^2}{n} \left[I_{\alpha}(W;Z^n)+\log 2 + \frac{\alpha}{\alpha-1} \log \frac{1}{\delta}\right]}.$$ Here, $I_{\alpha}(\cdot,\cdot)$ is the $\alpha$-mutual information

[rCl]{}\[eq:alpha\_MI\] I\_(W;Z\^n)& = & \_[P\_[Z\^n]{} ]{},

where $\dv P_{W\! Z^n}/\dv P_W\! P_{Z^n}$ is the Radon-Nikodym derivative. Note that, since $\lim_{\delta\to 0} H_b(\delta)/\delta+\log \delta = 1$, the dependence of $\epsilon$ on $\delta$ in  is of order $1/\sqrt{\delta}$. In contrast, it is of order $\sqrt{(\alpha/(\alpha-1)) \log(1/\delta)}$ in , which is typically more favorable. For example, in the limit $\alpha\to\infty$, the $\alpha$-mutual information converges to the maximal leakage [@issa16-a Thm. 1], and $\epsilon$ depends on $\delta$ only through the term $\sqrt{\log(1/\delta)}$.

The analysis in [@esposito19-12a], however, does not reveal why using $\alpha$-mutual information rather than mutual information results in a more benign dependence of the generalization error on the confidence parameter $\delta$. Moreover, the choice $\alpha=1$, for which $I_{\alpha}(W;Z^n)$ reduces to $I(W;Z^n)$, renders the bound in  vacuous.

#### Contributions {#contributions .unnumbered}

Inspired by the treatment of the generalization error for the case of the $0-1$ loss function reported in [@catoni07-a], we present a single framework for deriving bounds on the generalization error that can be applied to both average and tail analyses, both of a PAC-Bayesian and single-draw flavor. As a product of our analysis, we obtain a probabilistic generalization error bound for the single-draw scenario, which results in the following bound on $\epsilon$ to guarantee that  is greater than $1-\delta$: $$\label{eq:sample_complexity_moments}
    \epsilon\geq  \sqrt{\frac{2\sigma^2}{n}\left(I(W;Z^n)+\frac{M_m(W;Z^n)}{(\delta/2)^{1/m}}+\log\frac{2}{\delta}\right)}.$$ Here, $$\label{eq:central_moment_infodens}
    M_m(W;Z^n) = \Exop^{1/m}_{P_{W\! Z^n}}\lefto[\abs{ \imath(W,Z^n) - I(W;Z^n)}^m \right]$$ is the $m$th root of the $m$th central moment of the information density $$\label{eq:info_density}
    \imath(w,z^n)=\log \frac{\dv P_{W\! Z^n} }{\dv P_W\! P_{Z^n}}(w,z^n).$$ The bound in  is derived as a data-independent relaxation of an underlying data-dependent bound. Comparing  with , we see that the existence of higher central moments of $\imath(W,Z^n)$ results in a more favorable scaling of the error bound with $\delta$. This implies that one can obtain generalization error bounds that are explicit in the mutual information and have a more favorable dependence on $\delta$ than the one given in . In the limit $m\to\infty$, the dependence is of order $\sqrt{\log (1/\delta)}$, but the resulting bound is less tight than the maximal leakage bound in [@esposito19-12a Cor. 5]. However, through a more refined analysis, we also obtain a bound that is tighter than the maximal leakage bound in some cases.

To shed further light on the role of the tail of the information density in determining the dependence of $\epsilon$ on $\delta$, we derive an additional probabilistic single-draw bound, based on a change of measure argument [@polyanskiy19-a Thm. 12.5] that is used to establish strong converse bounds in binary hypothesis testing. It results in the following bound on $\epsilon$:

[rCl]{} &&.\[eq:strongconv\_gen\_thm\_intro\]

Similar to , this bound reveals that for a fixed $\delta$, low values of $\epsilon$ require fast-decaying tails of the information density random variable. Indeed, $\gamma$ in  should be chosen sufficiently large to make the argument of the $\log$ positive. However, large values of $\gamma$ also contribute to a large $\epsilon$.

Bounds via a Subgaussian Inequality {#sec:main_results}
===================================

In this section, we derive several types of bounds on the absolute value of the generalization error of a randomized learning algorithm. The following theorem gives an inequality that will later be used to derive both average and tail bounds for the generalization error.

\[thm:mainineq\] Let $Z^n$ be according to $P_Z$. Assume that $\ell(w,Z)$ is $\sigma$-subgaussian under $P_Z$ for all $w\in \mathcal W$. Assume that $P_{W\! Z^n}$ is absolutely continuous with respect to $P_W\! P_{Z^n}$. Then, for all $\lambda\in \reals$,

[rCl]{}\[eq:mainineq\] && 1.

Since $\ell(w,Z)$ is $\sigma$-subgaussian and the $Z_i$ are , the random variable $\frac{1}{n}\sum_{i=1}^n  \ell(w,Z_i)$ is $\sigma/\sqrt{n}$-subgaussian, i.e., $$\begin{gathered}
    \Exop_{P_{Z^n} } \lefto[\exp\lefto(\lambda\left(\frac{1}{n}\sum_{i=1}^n \ell(w,Z_i) - \Exop_{P_Z}\lefto[\ell(w,Z)\right] \right)\right)\right] \\
    \leq \exp\lefto(\frac{\lambda^2\sigma^2}{2n}\right).\end{gathered}$$ Reorganizing terms and taking the expectation with respect to $P_W$, we get $$\label{eq:subgauss_without_indicator}
    \Exop_{P_W\! P_{Z^n} } \lefto[\exp\lefto(\lambda {{\textnormal{gen}}(W,Z^n)}- \frac{\lambda^2\sigma^2}{2n}\right)\right]\leq 1.$$ Now, let $E$ be the union of all sets $\setE\in \mathcal{W}\times \mathcal{Z}^n$ such that $P_{W\!Z^n}(\setE)=0$, and let $\bar E$ denote its complement. It follows from  that $$\Exop_{P_W\! P_{Z^n} } \lefto[1_{\bar E}\cdot\exp\lefto(\lambda {{\textnormal{gen}}(W,Z^n)}- \frac{\lambda^2\sigma^2}{2n}\right)\right]\leq 1,$$ where $1_{\bar E}$ is the indicator function of the set $\bar E$. To obtain , we perform a change of measure from $P_W\! P_{Z^n}$ to $P_{W\! Z^n}$, as per [@polyanskiy19-a Prop. 17.1(4)].

We next show how the inequality  can be used to derive previously known and novel bounds on the generalization error.

Average Generalization Error
----------------------------

As a first corollary of Theorem \[thm:mainineq\], we derive a bound on the average generalization error , recovering the result in [@xu17-05a Thm. 1].

\[cor:ExpectedGen\] Under the assumptions of Theorem \[thm:mainineq\], $$\abs{ \Ex{P_{W\! Z^n}}{{{\textnormal{gen}}(W,Z^n)}}} \leq \sqrt{\frac{2\sigma^2}{n}I(W;Z^n)}.$$

We apply Jensen’s inequality to , which yields $$\label{eq:intermediate_average}
    \exp\biggl(\lambda\Ex{P_{W\! Z^n}}{{{\textnormal{gen}}(W,Z^n)}} - \frac{\lambda^2\sigma^2}{2n} 
 -\Ex{P_{W\! Z^n}}{\imath(W,Z^n)} \biggr)  \leq   1.$$ Noting that $\Ex{P_{W\! Z^n}}{\imath(W,Z^n)}=I(W;Z^n)$ we get, after taking the $\log$ of both sides of  and reorganizing terms, the nonnegative parabola in $\lambda$ $$\lambda^2\frac{\sigma^2}{2n} - \lambda \Ex{P_{W\! Z^n}}{{{\textnormal{gen}}(W,Z^n)}} + I(W;Z^n) \geq 0.$$ Since the discriminant of a nonnegative parabola is nonpositive, we get $$\Exop^2_{P_{W\! Z^n}}[{{\textnormal{gen}}(W,Z^n)}] - \frac{2\sigma^2}{n}I(W;Z^n)\leq 0,$$ which yields the desired bound.

PAC-Bayesian Tail Bounds {#sec:pac-bayesian-results}
------------------------

Next, we use Theorem \[thm:mainineq\] to obtain two tail bounds on the absolute value of the generalization error averaged over $P_{W\!\given\! Z^n}$ in . The first one, presented in Corollary \[cor:PAC-bayesian\], recovers a classical data-dependent PAC-Bayesian bound (see, e.g., [@guedj19-10a Prop. 3]) for the special case in which $P_W$ is taken as the prior distribution and $P_{W\!\given\! Z^n}$ is taken as the posterior distribution. The second one, presented in Corollary \[cor:PAC-bayesian-data-independent\], is a relaxation of the first bound, which makes it data-independent. This bound, which depends on the $m$th moment of the relative entropy $\relent{P_{W\vert Z^n}}{P_W}$, recovers the bound given in [@bassily18-02a App. A.3] for the case $m=1$.

\[cor:PAC-bayesian\] Under the assumptions in Theorem \[thm:mainineq\], the following bound holds with probability at least $1-\delta$ under $P_{Z^n}$: $$\begin{gathered}
    \abs{ \Exop_{P_{W\vert Z^n} }{{\textnormal{gen}}(W,Z^n)}} 
     \\ \leq \sqrt{\frac{2\sigma^2}{n}\left(\relent{P_{W\vert Z^n}}{P_W} +\log \frac{1}{\delta}\right)}.\label{eq:multidrawBase}
     \end{gathered}$$

Similarly to the proof of Corollary \[cor:ExpectedGen\], we apply Jensen’s inequality to , but now only with respect to the conditional expectation of $W$ given $Z^n$. This yields

[rrCl]{} \_[P\_[Z\^n]{}]{} && 1, \[eq:singleDrawJensen\]

where we used that $$\Ex{P_{W\vert Z^n=z^n}}{i(W,z^n)}=\relent{P_{W\vert Z^n=z^n}}{P_W}.$$ Next, we use Markov’s inequality in the following form: let $U\distas P_U$ be a nonnegative random variable s.t. $\Ex{}{U}\leq 1$. Then $$\begin{aligned}
P_U[U>1/\delta]< \Ex{}{U}\delta\leq \delta.\label{eq:MarkovTrick}\end{aligned}$$ Using  in , we conclude that

[rrCl]{} P\_[Z\^n]{}&& 1-.

Reorganizing terms, we obtain:

[rrCl]{} P\_[Z\^n]{}&1&-.

The desired bound  now follows from the same discriminant analysis as in the proof of Corollary \[cor:ExpectedGen\].

The bound in Corollary \[cor:PAC-bayesian\] is data-dependent because the upper bound on the generalization error depends on the specific instance of $Z^n$. In the next corollary, we apply Markov’s inequality once more to make the bound data-independent.

\[cor:PAC-bayesian-data-independent\] Under the assumptions in Theorem \[thm:mainineq\], the following bound holds with probability at least $1-\delta$ under $P_{Z^n}$ for all $m>0$: $$\begin{gathered}
    \abs{ \Ex{P_{W\vert Z^n} } {{{\textnormal{gen}}(W,Z^n)}} } 
    \\ \leq \sqrt{\frac{2\sigma^2}{n}\left(\frac
    {\Exop^{1/m}_{P_{Z^n}}\lefto[\relent{P_{W\vert Z^n}}{P_W}^m\right] }
    {(\delta/2)^{1/m}} +\log \frac{2}{\delta}\right)}.\label{eq:multidrawMI}\end{gathered}$$

Applying Markov’s inequality to the random variable $\relent{P_{W\vert Z^n}}{P_W}^m$, we obtain after some manipulations $$\begin{gathered}
P_{Z^n}\Biggl[\relent{P_{W\vert Z^n}}{P_W} \leq 
\frac
    {\Exop^{1/m}_{P_{Z^n}}\lefto[\relent{P_{W\vert Z^n}}{P_W}^m\right] }
    {\delta^{1/m}} \Biggr]\\
    \geq 1-\delta. \label{eq:MultidrawProofMarkov}\end{gathered}$$ We now observe that the two probability bounds  and  together with the union bound imply that, with probability at least $1-2\delta$ under $P_{Z^n}$, $$\begin{gathered}
    \abs{ \Ex{P_{W\vert Z^n} } {{{\textnormal{gen}}(W,Z^n)}} }\\ \leq  \sqrt{\frac{2\sigma^2}{n}\left(\frac
    {\Exop^{1/m}_{P_{Z^n}}\lefto[\relent{P_{W\vert Z^n}}{P_W}^m\right] }
    {\delta^{1/m}} +\log \frac{1}{\delta}\right)}.\end{gathered}$$ The desired result then follows by the substitution $\delta\rightarrow \delta/2$.

Note that when $m=1$, we have $$\Exop_{P_{Z^n}}\lefto[\relent{P_{W\vert Z^n}}{P_W}\right]=I(W;Z^n)$$ and the bound  coincides with the one reported in [@bassily18-02a App. 3]. Some additional remarks on  are provided in Section \[sec:remarks\].

Single-Draw Probabilistic Bounds {#sec:sigle-draw-results}
--------------------------------

We now use Theorem \[thm:mainineq\] to derive two tail bounds on the absolute value of the single-draw generalization error in . As in Section \[sec:pac-bayesian-results\], we first state a data-dependent bound in Corollary \[cor:single-draw-data-dependent\]. Then, we relax this to two different data-independent bounds in Corollaries \[cor:single-draw-data-independent\] and \[cor:single-draw-maximal-leakish\]. All three bounds are novel, to the best of our knowledge.

\[cor:single-draw-data-dependent\] Under the assumptions in Theorem \[thm:mainineq\], the following bound holds with probability at least $1-\delta$ under $P_{W\! Z^n}$:[^2] $$\label{eq:singledrawBase}
    \abs{ {{\textnormal{gen}}(W,Z^n)}} \leq \sqrt{\frac{2\sigma^2}{n}\left(\imath(W,Z^n) +\log \frac{1}{\delta}\right)}.$$

Applying Markov’s inequality  directly to , we conclude that $$\begin{gathered}
P_{W\! Z^n}\biggo[\exp\biggo(\lambda {{\textnormal{gen}}(W,Z^n)}- \frac{\lambda^2\sigma^2 }{2n}
-{{\imath}(W,Z^n)}\bigg)\leq \frac{1}{\delta} \bigg]\\ \geq 1-\delta,\end{gathered}$$ from which the desired result follows by the same discriminant analysis as in the proof of Corollary \[cor:ExpectedGen\].

\[cor:single-draw-data-independent\] Under the assumptions in Theorem \[thm:mainineq\], the following bound holds with probability at least $1-\delta$ under $P_{W\! Z^n}$: $$\begin{gathered}
    \abs{  {{\textnormal{gen}}(W,Z^n)}} \leq \label{eq:singledrawMoment} \\
     \sqrt{\frac{2\sigma^2}{n}\left(I(W;Z^n)+\frac{M_m(W;Z^n)}{(\delta/2)^{1/m}} +\log \frac{2}{\delta}\right)},\end{gathered}$$ where $M_m(W;Z^n)$, defined in , is the $m$th root of the $m$th central moment of the information density.

We shall use Markov’s inequality in the following form: for a random variable $U$, $$\label{eq:markov-for-arbitrary-rv}
P_U\lefto[U \leq \Exop[U]+ \frac{\Exop^{1/m}[\abs{U-\Exop[U]}^m]}{\delta^{1/m}} \right]\geq 1-\delta.$$ Applying  to the information density random variable, we conclude that, with probability at least $1-\delta$, $$\label{eq:moment_bound_on_inf_dens}
    {{\imath}(W,Z^n)}\leq I(W;Z^n)+\frac{M_m(W;Z^n)}{\delta^{1/m}}.$$ It now follows from , , and the union bound that, with probability at least $1-2\delta$, $$\begin{gathered}
\abs{{{\textnormal{gen}}(W,Z^n)}}\leq \\
\sqrt{\frac{2\sigma^2}{n}\left(I(W;Z^n)+\frac{M_m(W;Z^n)}{\delta^{1/m}}+\log \frac{1}{\delta}   \right)}.\end{gathered}$$ The desired result follows after the substitution $\delta\rightarrow \delta/2$.

\[cor:single-draw-maximal-leakish\] Under the assumptions in Theorem \[thm:mainineq\], the following bound holds with probability at least $1-\delta$ under $P_{W\! Z^n}$: $$\begin{gathered}
    \abs{  {{\textnormal{gen}}(W,Z^n)}} \leq \label{eq:singledrawMaximalLeakish} \\
     \sqrt{\frac{2\sigma^2}{n}\left(\log  \esssup_{P_{Z^n} }\Exop_{P_{W}}\lefto[ \frac{\dv P_{W\! Z^n}}{\dv P_W\!P_{Z^n}}\right] +2\log \frac{2}{\delta}\right)}.\end{gathered}$$

The following holds with probability $1$ under $P_{W\! Z^n}$: $$\begin{aligned}
\imath(W,Z^n) = \log \frac{\dv P_{W\! Z^n}}{\dv P_W\!P_{Z^n}} \leq \log \esssup_{P_{Z^n\vert W}} \frac{\dv P_{W\! Z^n}}{\dv P_W\!P_{Z^n}}.\end{aligned}$$ The assumption that $P_{W\!Z^n}\ll P_W\!P_{Z^n}$ means that any set in the support of $P_{W\!Z^n}$ is also in the support of $P_W\!P_{Z^n}$. We can therefore weaken the $\esssup$ as follows: $$\begin{aligned}
\log \esssup_{P_{Z^n\vert W}} \frac{\dv P_{W\! Z^n}}{\dv P_W\!P_{Z^n}} \leq \log \esssup_{P_{Z^n}} \frac{\dv P_{W\! Z^n}}{\dv P_W\!P_{Z^n}}.\end{aligned}$$ Markov’s inequality implies that, with probability at least $1-\delta$ under $P_W$, $${{\imath}(W,Z^n)}\leq \log \esssup_{P_{Z^n}}\Ex{P_W}{\frac{\dv P_{W\! Z^n}}{\dv P_W\!P_{Z^n}}} + \log\lefto(\frac{1}{\delta}\right),$$ which, combined with  through the union bound and the substitution $\delta\rightarrow \delta/2$, gives the desired result.

Remarks on the Tail Bounds in Sections \[sec:pac-bayesian-results\] and \[sec:sigle-draw-results\] {#sec:remarks}
--------------------------------------------------------------------------------------------------

The single-draw tail bound in  reveals a relation between the central moments of the information density and the confidence parameter $\delta$. Specifically, the higher the moment of the information density that can be controlled, the more benign the dependence of the generalization error bound on $\delta$. A similar observation holds for the data-independent PAC-Bayesian bound , in which controlling higher moments of the random variable $\relent{P_{W\!\given\! Z^n}}{P_W}$ leads to a more favorable dependence of the generalization bound on $\delta$.

In the limit $m\to\infty$ the bound in  reduces to $$\begin{gathered}
\label{eq:singledrawMomentInf}
    \abs{  {{\textnormal{gen}}(W,Z^n)}} \leq  \\
     \sqrt{\frac{2\sigma^2}{n}\left(I(W;Z^n)+{M_\infty(W;Z^n)} +\log \frac{2}{\delta}\right)},\end{gathered}$$ where $M_\infty(W;Z^n)=\esssup_{P_{W\!Z^n}} \abs{\imath(w,z^n)- I(W;Z^n)}$. So, in this limit, the dependence on $\delta$ is of order $\sqrt{\log(1/\delta)}$. However, the bound  is tighter than , up to the factor $2$ multiplying the logarithm. It is also tighter than the maximal leakage bound in [@esposito19-12a Cor. 10] and the max information bound in [@dwork15-06a Thm. 4] with $\beta=0$, up to the aforementioned factor of $2$. Indeed, let the max information be defined as $$\label{eq:max_mi}
    I_{\textnormal{max}}(W;Z^n) = \esssup_{w,z^n}\imath(w,z^n).$$ It is readily verified that $$I_\textnormal{max}(W;Z^n)\leq I(W;Z^n)+{M_\infty(W;Z^n)}.$$ As shown in [@esposito19-12a Lem. 12], $\mathcal{L}(Z^n \rightarrow W)\leq I_{\textnormal{max}}(W;Z^n)$, where $\mathcal{L}(Z^n \rightarrow W)$ denotes the maximal leakage. The bound in  can be relaxed to give a maximal leakage bound, since

[rCl]{} (Z\^n W)& =&\_[P\_[W]{}]{}\
\[eq:lower\_bound\_of\_maximal\_leakage\] && \_[P\_[Z\^n]{} ]{}\_[P\_[W]{}]{}.

Thus, provided that $$\log  \esssup_{P_{Z^n} }\Exop_{P_{W}}\lefto[ \frac{\dv P_{W\! Z^n}}{\dv P_W\!P_{Z^n}}\right] \leq \mathcal{L}(Z^n \rightarrow W) + \log\frac{2}{\delta},$$ we have established that the bound in  is stronger than, in turn, the maximal leakage bound in [@esposito19-12a Cor. 10], the max information bound in [@dwork15-06a Thm. 4] with $\beta=0$, and .

In the next section, we present a different approach to obtaining single-draw tail bounds, which reveals a coupling between $\delta$ and the tail of the information density random variable.

Bounds via the Strong Converse
==============================

As pointed out in Section \[sec:introduction\], a key tool for deriving the single-draw bound  is the data processing inequality for $f$-divergences. This is also true for some of the bounds presented in [@esposito19-12a]. In the context of binary hypothesis testing, it is known that such an inequality only leads to a weak converse bound on the region of achievable error rates. To obtain a strong converse, one needs to use [@polyanskiy19-a Lem. 12.2] (restated in Lemma \[lem:strong\_converse\_lemma\] below for convenience), which provides a bound on the probability of an event under a distribution $P$ in terms of its probability under $Q$.

\[lem:strong\_converse\_lemma\] Let $E$ be an arbitrary event and $P$ and $Q$ be probability measures such that $P$ is absolutely continuous with respect to $Q$. Then, for all $\gamma\in\reals$, $$\label{lem:StrongConv}
    P[E] \leq P\lefto[\log \frac{\dv P}{\dv Q} >  \gamma \right] + e^\gamma Q[E].$$

As we shall show next, this inequality can be turned into a generalization bound by choosing $P$, $Q$, and $E$ appropriately.

\[thm:strong\_conv\_bound\] Under the assumptions of Theorem \[thm:mainineq\], the following bound holds with probability at least $1-\delta$ over $P_{W\! Z^n}$: $$\begin{gathered}
\label{eq:strongconv_gen_thm}
    \abs{{{\textnormal{gen}}(W,Z^n)}}\\
    \leq\sqrt{ \frac{2\sigma^2}{n}
    \left(
        \gamma + \log\lefto(\frac{2}{\delta-P_{W\! Z^n}\lefto[\imath(W,Z^n)\geq \gamma\right]} \right)
    \right)}\end{gathered}$$ for all $\gamma$ for which the arguments of the logarithm and the square root are nonnegative.

With $P=P_{W\! Z^n}$, $Q=P_W\! P_{Z^n}$ and $$\label{eq:high_error_event}
E=\{(w,z^n): \abs{\textnormal{gen}(w,z^n)} > \epsilon  \},$$ we apply Lemma \[lem:strong\_converse\_lemma\] to get $$\label{eq:StrongConvPf1}
P_{W\! Z^n} [E] \leq {P_{W\! Z^n} }\left[\imath(W,Z^n)\geq \gamma  \right] + e^\gamma {P_W\! P_{Z^n}}[E].$$ The $\sigma$-subgaussianity of the loss function implies that [@wainwright19-a Eq. (2.9)] $${P_{Z^n}}\lefto[\abs{\textnormal{gen}(w,Z^n)}>\epsilon\right] \leq 2\exp\lefto(-n{\epsilon^2}/{(2\sigma^2)} \right).\label{eq:hoeffding_q_bound}$$ Inserting  into , we obtain $$\begin{gathered}
\label{eq:strong_conv_bound}
    P_{W\! Z^n}[\abs{{{\textnormal{gen}}(W,Z^n)}}>\epsilon] \\\leq P_{W\! Z^n}\lefto[\imath(W,Z^n)\geq \gamma\right] + 2\exp\lefto(\gamma-n{\epsilon^2}/{(2\sigma^2)}\right).\end{gathered}$$ We get the desired result by imposing that the right-hand side of  is less than $\delta$ and solving for $\epsilon$.

Unlike the bounds in Section \[sec:main\_results\], this bound depends on the tail distribution of the information density. For a given $\delta$, the parameter $\gamma$ needs to be chosen large enough to make the factor $\delta-P_{W\! Z^n}[\imath(W,Z^n)\geq \gamma]$ positive. However, choosing $\gamma$ too large makes the bound loose because of the $\gamma$ term that is added to the $\log$. This reveals a trade-off between the rate of decay of the tail of the information density and the confidence level $\delta$.

Controlling the tail of the information density results in a tighter bound than the moment-based bound in  and the maximal leakage bound  [@esposito19-12a Cor. 10] (up to constants). Indeed, these two bounds can be obtained by further upper-bounding the right-hand side of , as we shall discuss next.

Moment-Based Single-Draw Tail Bound {#sec:rederive_sd_tail_moments}
-----------------------------------

By Markov’s inequality,

[rCl]{} & &P\_[W Z\^n]{}\
&& P\_[W Z\^n]{}\
&& .\[eq:strong\_conv\_rederive\_2\]

We now set $$\begin{aligned}
\label{eq:gamma}
    \gamma = \frac{M_m(W;Z^n)}{(\delta/2)^{1/m}}+I(W;Z^n).\end{aligned}$$ Subsituting  in , we conclude that $$P_{W\! Z^n}\lefto[\imath(W,Z^n)\geq \gamma\right] \leq {\delta}/{2}.$$ Inserting this upper bound into we obtain $$\epsilon \leq \sqrt{\frac{2\sigma^2}{n} \left(I(W;Z^n)+\frac{M_m(W;Z^n)}{(\delta/2)^{1/m}} + \log\frac{4}{\delta} \right)},$$ which coincides with , up to a $\log 2$ term.

Maximal Leakage Single-Draw Tail Bound {#sec:rederive_max_info}
--------------------------------------

With probability $1$ over $P_{W\! Z^n}$, using the assumption that $P_{W\!Z^n}\ll P_W\!P_{Z^n}$, $$P_{W\! Z^n}[{{\imath}(W,Z^n)}\geq \gamma] \leq P_W\lefto[\esssup_{P_{Z^n}}\frac{\dv P_{W\! Z^n}}{\dv P_W\!P_{Z^n}}\geq e^\gamma\right].$$ Thus, Markov’s inequality implies that $$P_{W\! Z^n}[{{\imath}(W,Z^n)}\geq \gamma] \leq e^{-\gamma}\Ex{P_W}{\esssup_{P_{Z^n}}\frac{\dv P_{W\! Z^n}}{\dv P_W\!P_{Z^n}}}.$$ Setting $\gamma = \mathcal{L}(Z^n \rightarrow W) + \log(2/\delta)$ and using this result in , we get, with probability at least $1-\delta$ over $P_{W\! Z^n}$,

[rCl]{} && .

[^1]: For the case in which the prior and posterior distributions in [@guedj19-10a Prop. 3] are set to $P_W$ and $P_{W\!\given\! Z^n}$, respectively.

[^2]: Note that the argument of the square root 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$.
