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 