Milad Sefidgaran<EMAIL_ADDRESS>
LTCI, Télécom Paris, Institut Polyetechnique de Paris and Amin Gohari
<EMAIL_ADDRESS>
Tehran Institute for Advanced Studies, Khatam University and Gaël Richard
<EMAIL_ADDRESS>
LTCI, Télécom Paris, Institut Polyetechnique de Paris and Umut Şimşekli
<EMAIL_ADDRESS>
INRIA & ENS – PSL Research University

# Rate-Distortion Theoretic Generalization Bounds
for Stochastic Learning Algorithms

###### Abstract

Understanding generalization in modern machine learning settings has been one
of the major challenges in statistical learning theory. In this context,
recent years have witnessed the development of various generalization bounds
suggesting different complexity notions such as the mutual information between
the data sample and the algorithm output, compressibility of the hypothesis
space, and the fractal dimension of the hypothesis space. While these bounds
have illuminated the problem at hand from different angles, their suggested
complexity notions might appear seemingly unrelated, thereby restricting their
high-level impact. In this study, we prove novel generalization bounds through
the lens of rate-distortion theory, and explicitly relate the concepts of
mutual information, compressibility, and fractal dimensions in a single
mathematical framework. Our approach consists of (i) defining a generalized
notion of compressibility by using _source coding_ concepts, and (ii) showing
that the ‘compression error rate’ can be linked to the generalization error
both in expectation and with high probability. We show that in the ‘lossless
compression’ setting, we recover and improve existing mutual information-based
bounds, whereas a ‘lossy compression’ scheme allows us to link generalization
to the _rate-distortion dimension_ – a particular notion of fractal dimension.
Our results bring a more unified perspective on generalization and open up
several future research directions.

###### keywords:

Generalization error, rate-distortion theory, source coding.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Notation and problem setup
    2. 2.2 Technical background on source coding
  3. 3 Generalization Bounds via Rate Distortion Theory
    1. 3.1 Compressibility of an algorithm
    2. 3.2 Bounds on the expected value of the generalization gap
    3. 3.3 Tail bounds on the generalization gap
  4. 4 Proof Outline
    1. 4.1 Tail bound via information-theoretic covering
  5. 5 Conclusion
  6. A Conditional Compressibility
    1. A.1 Bounds on the expected value of the generalization gap
    2. A.2 Tail bounds on the generalization gap
  7. B On the Donsker-Varadhan’s Inequality
    1. B.1 Donsker-Varadhan’s inequality via compression
    2. B.2 Variational representation of $\mathbb{E}[X]$
  8. C Tail Bound on an Arbitrary Random Variable
  9. D Other Results
    1. D.1 Extension of the in expectation bound
    2. D.2 Extension of the tail bound
    3. D.3 Examples for Lipschitz loss
  10. E Proofs
    1. E.1 Proof of Theorem 3.2
    2. E.2 Proof of Theorem 3.3
    3. E.3 Proof of Theorem 3.4
    4. E.4 Proof of Corollary 3.7
    5. E.5 Proof of Theorem 3.9
    6. E.6 Proof of Theorem 3.10
      1. E.6.1 First Proof
      2. E.6.2 Second Proof
    7. E.7 Proof of Theorem 4.1
    8. E.8 Proof of Theorem 4.3
    9. E.9 Proof of Theorem A.2
    10. E.10 Proof of Corollary A.4
    11. E.11 Proof of Theorem A.5
    12. E.12 Proof of Theorem A.6
    13. E.13 Proof of Corollary A.8
    14. E.14 Proof of Lemma
    15. E.15 Proof of Lemma C.1
      1. E.15.1 First Proof
      2. E.15.2 Second Proof
    16. E.16 Proof of Corollary D.2
    17. E.17 Proof of Lemma E.1
    18. E.18 Proof of Lemma E.8
    19. E.19 Proof of Lemma E.21

##  1 Introduction

Many important problems in statistical learning can be cast as the _population
risk minimization_ problem, which is defined as follows (Shalev-Shwartz and
Ben-David, 2014):

$\displaystyle\min\limits_{w\in\mathcal{W}}\Bigl{\\{}\mathcal{L}(w)\coloneq\mathbb{E}_{Z\sim\mu}\left[\ell(Z,w)\right]\Bigr{\\}},$
(1)

where $\mathcal{W}\subset\mathbb{R}^{d}$ denotes a parametric _hypothesis
class_ , $Z\in\mathcal{Z}$ denotes the _input data_ with $\mathcal{Z}$ being
the _data space_ , $\mu$ denotes an unknown _data distribution_ over
$\mathcal{Z}$, and $\ell\colon\mathcal{Z}\times\mathcal{W}\to\mathbb{R}^{+}$
is a _loss function_ that measures the quality of a hypothesis
$w\in\mathcal{W}$. As the data distribution $\mu$ is unknown in practice, we
instead consider the _empirical risk minimization_ problem, given as follows:

$\displaystyle\min\limits_{w\in\mathcal{W}}\Bigl{\\{}\hat{\mathcal{L}}(S,w)\coloneq\frac{1}{n}\sum\limits_{i=1}^{n}\ell(Z_{i},w)\Bigr{\\}},$
(2)

where $S:=\\{Z_{1},\ldots,Z_{n}\\}$ denotes a _training dataset_ with
independent and identically distributed (i.i.d.) elements, i.e., each
$Z_{i}\sim_{\text{i.i.d.}}\mu$.

To attack the optimization problem (2), arguably, the most common approach is
to utilize a stochastic optimization algorithm
$\mathcal{A}:\mathcal{Z}^{n}\to\mathcal{W}$ (e.g., stochastic gradient
descent), such that the algorithm outputs a _random_ hypothesis, i.e.,
$\mathcal{A}(S)=W\in\mathcal{W}$. One of the main challenges in statistical
learning theory has been then to understand the behavior of the so-called
_generalization error_ associated with the algorithm output, that is the
difference between the population and empirical risks induced by the algorithm
output:
$\operatorname*{gen}(S,\mathcal{A}(S))\coloneq\mathcal{L}(\mathcal{A}(S))-\hat{\mathcal{L}}(S,\mathcal{A}(S))$.
It has been illustrated that classical algorithm-independent generalization
bounds fall short at explaining the (perhaps unexpected) success of modern
machine learning systems (Zhang et al., 2017). This has motivated the
development of algorithm-dependent generalization bounds, a field that has
been evolving in different directions.

An important direction in this context, and the one that is closest to our
study, is based on analyzing the generalization error by using information-
theoretic tools. Initiated by Russo and Zou (2016) and Xu and Raginsky (2017),
these approaches link the generalization error to the _mutual information_
between the data sample $S$ and the algorithm output $W$; suggesting that a
lower statistical dependence between $S$ and $W$ implies better
generalization. Their initial results were later improved by using different
conditional versions of the mutual information (Harutyunyan et al., 2021;
Haghifam et al., 2021; Negrea et al., 2020b; Steinke and Zakynthinou, 2020; Bu
et al., 2020; Haghifam et al., 2020), and were further generalized to more
general notions of the mutual information that are defined through
f-divergences (rather than the Kullback-Leibler divergence) (Esposito et al.,
2020; Hellstrom and Durisi, 2020; Masiha et al., 2021).

A second approach has been based on the observation that the algorithm output
$W$ can be ‘compressible’ in different senses. Littlestone and Warmuth (1986)
in a pioneer work, considered a compressibility framework for the binary
classification problem, in which _compressed hypothesis_ are chosen based on a
subset of length $k$ of $S$ such that the picked hypothesis predicts correctly
the label for all $Z_{i}\in S$. They showed that whenever such a compressing
strategy exists, the algorithm generalizes well. The compressibility approach
is later applied in different ways especially to overparametrized neural
networks (Arora et al., 2018; Suzuki et al., 2020a, b; Negrea et al., 2020a;
Hsu et al., 2021; Barsbey et al., 2021; Baykal et al., 2019; Kuhn et al.,
2021). Loosely speaking, under different compressibility assumptions for $W$,
these studies showed that a higher level of compressibility indicates a lower
generalization error since the hypothesis class $\mathcal{W}$ can be
approximated by a smaller, ‘compressed’ space, which intuitively induces a
lower worst-case error.

Finally, a recently initiated line of research has illustrated that when
$\mathcal{A}$ is chosen as an iterative optimization algorithm, due to its
recursive nature, $\mathcal{A}$ might generate a ‘fractal structure’, either
in its optimization trajectories (Şimşekli et al., 2020; Birdal et al., 2021;
Hodgkinson et al., 2021), or in the support of its stationary distribution
(Camuto et al., 2021). These studies showed that the generalization error can
be linked to the ‘intrinsic dimension’ of the fractal structure that is
generated by the algorithm; suggesting that a smaller intrinsic dimension
implies improved generalization.

Even though these three research directions have shed light on different
façades of the problem of understanding the generalization error, the
mathematical frameworks that underlie their theoretical results and their
implied take-home messages might be seemingly unrelated, thereby restricting
their high-level impact. In this paper, we prove novel generalization bounds
through the lens of rate-distortion theory (Berger, 1975), and explicitly
relate the concepts of mutual information, compressibility, and fractal
dimensions in a single mathematical framework.

To achieve this goal, we first define a generalized notion of compressibility
by using _source coding_ concepts from information theory, which then allows
us to use ‘information-theoretic coverings’ for $\mathcal{W}$ that we will
detail in Section 3. Within this context, we show that the ‘compression error
rate’ of an algorithm $\mathcal{A}$ can be linked to its generalization error
both in expectation and with high probability. Next, we show that the
aforementioned information-theoretical frameworks can be obtained as a special
case of our setup, which is referred to as ‘lossless compression’. Thanks to
this connection, the results of Xu and Raginsky (2017) can be re-derived. The
bound in (Xu and Raginsky, 2017, Theorem 1) is in terms of the _mutual
information_ between $S$ and $W$, denoted as $I(S;W)$, which was previously
viewed as the dataset dependency of the algorithm. However, our framework
reveals that it is an upper-bound on the compression rate in terms of
_lossless algorithm compressibility_. This new perspective allows us to
introduce the notion of _lossy algorithm compressibility_ to handle continuous
or large alphabets where (Xu and Raginsky, 2017, Theorem 1) can be vacuous as
$I(S;W)$ can be very large; implying that a large $I(S;W)$ does not
necessarily indicate the algorithm will not generalize as long as the
algorithm is ‘lossily’ compressible. We further established novel _tail
bounds_ suggesting that $I(S;W)$ (or its lossy version) needs to be small not
only for the underlying distribution of $(S,W)$, but also for any distribution
in its vicinity. This is in the spirit of _stability_ : the algorithm should
be compressible under any small perturbation of the dataset and hypothesis.
The new tail bounds are established using a new ‘information-theoretic
covering’ technique, highlighted in Section 4.

Similarly, we derive and improve the results based on ‘conditional mutual
information’ (Steinke and Zakynthinou, 2020) in Appendix A. Thanks to this
approach, we established tail and in expectation bounds that recover the VC-
dimension bounds (Corollaries A.4 and A.8); the recovery in terms of the tail
bound is novel.

By exploiting the flexibility of our lossy compression framework, we further
extend our results and obtain bounds in terms of the intrinsic dimension of
the marginal distribution of $W$, namely the _rate-distortion dimension_
(Kawabata and Dembo, 1994). Our results bring a unified perspective on mutual
information, compressibility, and fractal dimensions, and open up several
future research directions as we will point out in Section 5.

##  2 Preliminaries

###  2.1 Notation and problem setup

Random variables, their realizations, and their domains are denoted by upper-
case letters, lower-case letters, and calligraphy fonts, _e.g._ $X$, $x$, and
$\mathcal{X}$. We assume that all the domains are endowed with their Borel
sigma fields. By $P_{X}$, we denote the distribution of $X$, defined on some
measurable space $(\mathcal{X},\mathcal{F})$, and by
$\operatorname{supp}(P_{X})$ we denote its support. The expected value of $X$
is denoted by $\mathbb{E}[X]$. We call a random variable $X$ (absolutely)
continuous if it admits a density with respect to the Lebesgue measure. The
random variable $X$ is called $\sigma$-subgaussian, if
$\mathbb{E}[\exp(t(X-\mathbb{E}[X]))]\leq\exp(\sigma^{2}t^{2}/2)$, $\forall
t\in\mathbb{R}$. A collection of $m\in\mathbb{N}$ random variables is denoted
by $X^{m}=(X_{1},\ldots,X_{m})$, or simply by bold letters $\mathbf{X}$, when
$m$ is known by the context. A sequence of $m$ real numbers
$x_{1},\ldots,x_{m}$ is denoted by $\\{x_{i}\\}_{i=1}^{m}$. Similar
conventions are used for sequences of sets or functions. The set of integers
$\\{1,\ldots,m\\}$ is denoted by $[m]$. We use $\mathbb{R}^{+}$ to denote
nonnegative real numbers.

As mentioned in the introduction, we consider a generic _randomized algorithm_
$\mathcal{A}:\mathcal{Z}^{n}\to\mathcal{W}$, that has access to dataset
$S=\\{Z_{1},\ldots,Z_{n}\\}$. This randomized algorithm induces a conditional
distribution $P_{W|S}$. We denote the joint distribution of the dataset $S$
and the hypothesis $W$ by $P_{S,W}=\mu^{\otimes n}P_{W|S}$ and the marginal
distribution of $W$ by $P_{W}$.

Most of our results are expressed in terms of information-theoretic
constructs, which we define as follows. For discrete random variables, the
Shannon entropy function is defined as
$H(X)\coloneq\mathbb{E}[\log(1/P_{X}(X))]$. Similarly, conditional entropy is
defined as $H(X|Y)\coloneq\mathbb{E}[\log(1/P_{X|Y}(X|Y))]$. The mutual
information between $X$ and $Y$ is defined as $I(X;Y)\coloneq H(X)-H(X|Y)$,
and intuitively measures the amount of _information_ these random variables
contain about each other. For continuous random variables, the differential
entropy $h(X)$ is defined as $-D_{KL}(P_{X}\|\operatorname{Leb})$, where
$\operatorname{Leb}$ is the Lebesgue measure on Euclidean spaces. In
particular, if $X$ has pdf $\mathrm{p}$, then
$h(X)=\mathbb{E}[\log(1/\mathrm{p}(X))]$, and $-\infty$ otherwise. Similarly,
$h(X|Y)$ and $I(X;Y)\coloneq h(X)-h(X|Y)$ are defined. The Kullback–Leibler
(KL) divergence between two distributions $Q$ and $P$ defined on the same
measurable space is defined as
$D_{KL}(Q\|P)\coloneq\mathbb{E}_{Q}\left[\log\frac{\mathrm{d}Q}{\mathrm{d}P}\right]$,
when $Q\ll P$, and equals $\infty$, otherwise. Here,
$\frac{\mathrm{d}Q}{\mathrm{d}P}$ is the Radon-Nikodym derivative of $Q$ with
respect to $P$.

###  2.2 Technical background on source coding

In this section, we will briefly review some results from the literature on
source coding that will ease the introduction of our theoretical
framework.111For a more detailed introduction, we refer the reader to (Berger,
1975; Cover and Thomas, 2006; Csiszár and Körner, 2011; El Gamal and Kim,
2011; Polyanskiy and Wu, 2014). Consider a random variable $W$ taking values
in a finite set $\mathcal{W}$. It is well-known that one can represent $W$
using $\lceil\log_{2}(|\mathcal{W}|)\rceil$222For $a\in\mathbb{R}$, $\lceil
a\rceil$ denotes the ceiling of $a$,_i.e._ $\min_{n\in\mathbb{N}}$, such that
$n\geq a$.  bits,333Depending on the base of logarithm in the Shannon entropy
function, the unit of information is either _bit_ (base 2: $\log_{2}$) or
_nat_ (base $e$: $\log_{e}$). We state all results with base $e$ for
simplicity and compatibility with previous results. However, for the unit of
information we use bit, as it is more common in the (digital) source coding
context. from which $W$ can be recovered with no error. For instance, if $W$
is a Bernoulli random variable, i.e.,
$\mathbb{P}(W=1)=1-\mathbb{P}(W=0)=\theta$, one bit suffices to represent $W$.
However, intuitively speaking if $\theta$ is very close to zero or very close
to one, using one full bit to represent $W$ is wasteful because in such cases
$W$ is almost deterministic.

In his seminal paper, Shannon (1948) formalized this intuition by introducing
the concept of _‘block-coding’_ , where he showed that the _‘source’_ $W$ can
be represented in a _compressed_ way by using a significantly smaller number
of bits, provided we can allow for a negligible probability of recovery error.
The main idea behind block coding can be summarized as follows. As opposed to
considering a single realization of the source $W$, we instead assume that we
have access to a vector of $m$ _independent_ realizations of the source,
denoted by $W^{m}$, and we are allowed to compress these $m$ instances
_simultaneously_. Moreover, the zero-error constraint in recovering
$m$-instances is replaced by the ‘asymptotically negligible error’ criterion
(i.e., the reconstruction error vanishes as $m\rightarrow\infty$). It turns
out that joint description of such independent sources is more efficient than
their individual description (Cover and Thomas, 2006). For instance, in our
running example of $W$ being a Bernoulli variable with parameter $\theta$,
$W^{m}$ is a binary string of length $m$. By the law of large numbers, we
expect $W^{m}$ to have around $m\theta$ ones in it. So, even though there are
$2^{m}$ binary strings of length $m$, roughly speaking $W^{m}$ has about

$\displaystyle\binom{m}{m\theta}\approx e^{mH(W)}$ (3)

‘effective’ possibilities where in (3) we use Stirling’s approximation of
factorial to express the number of possibilities in terms of the $H(W)$, the
Shannon entropy of $W$. Intuitively, for a discrete random variable $W$, ‘the
effective size’ of $m$ independent realizations is asymptotically about
$e^{mH(W)}$, rather than $|\mathcal{W}|^{m}$. Concretely, there exist sets
$\\{\mathcal{C}_{m}\\}_{m\in\mathbb{N}}$,
$\mathcal{C}_{m}\subseteq\mathcal{W}^{m}$ with
$|\mathcal{C}_{m}|=e^{m(H(W)+\varepsilon_{m})}$ such that
$\lim_{m\rightarrow\infty}\mathbb{P}(W^{m}\in\mathcal{C}_{m})=1$ and
$\lim_{m\rightarrow\infty}\varepsilon_{m}=0$. Thus, Shannon showed that the
fundamental limit for the compression of information is determined by the
Shannon entropy function $H(W)$, which can be much smaller than
$\log(|\mathcal{W}|)$.

Unfortunately, the number of bits required to represent even a single
realization of a continuous random variable $W$ is infinity. For instance, if
$W$ is a uniform random variable on $[0,1]$, we need infinitely many bits to
convey it. However, one bit is enough to represent a single realization of $W$
within distance $0.5$ by mapping $W$ to either $\hat{W}=0$ if $W<0.5$, and to
$\hat{W}=1$ if $W\geq 0.5$, and then conveying $\hat{W}$ instead of $W$. In
this example, the reconstruction space (or the set of quantization points) is
$\hat{\mathcal{W}}=\\{0,1\\}$, the reconstruction is _lossy_ (almost surely we
never recover the original $W$) and we measure the distance (or the
distortion) between $W$ and its reconstruction $\hat{W}$ by $|W-\hat{W}|$.

Let us begin by describing the lossy compression of a _single instance_ of an
arbitrary random variable $W$. In many information-theoretic and signal
processing applications, it suffices to recover a _distorted_ version
$\hat{W}\in\hat{\mathcal{W}}$ of $W$, as long as the incurred distortion is
within an ‘acceptable’ range, _i.e._ for $\epsilon\geq 0$ and a chosen
_distortion function_
$\varrho\colon\mathcal{W}\times\hat{\mathcal{W}}\to\mathbb{R}^{+}$, we have
$\varrho(W;\hat{W})\leq\epsilon$. While the quantized (distorted) space
$\hat{\mathcal{W}}$ is equal to $\mathcal{W}$ in many cases, it can be
different in general.444For example, to convey the sign of
$W\in\mathcal{W}=\mathbb{R}$, it is natural to consider
$\hat{\mathcal{W}}=\\{-1,+1\\}$ and
$\varrho(w,\hat{w})=\mathbbm{1}_{\\{w\hat{w}<0\\}}$. To facilitate the
explanation, assume $\hat{\mathcal{W}}=\mathcal{W}$ for the rest of this
section, _i.e.,_ we are required to produce $\hat{W}\in\mathcal{W}$. Next, let
us consider the case of block coding where instead of a single realization of
the source $W$, we have access to $W^{m}$ which is a vector of $m$
_independent_ realizations of the source. This problem is known as the vector-
quantization problem. Intuitively speaking, to compress $W^{m}$ we can take a
collection of $k$ quantization points
$\hat{\mathbf{w}}_{1},\hat{\mathbf{w}}_{2},\ldots,\hat{\mathbf{w}}_{k}$ in
$\mathcal{W}^{m}$, where
$\hat{\mathbf{w}}_{j}=(\hat{w}_{j,1},\ldots,\hat{w}_{j,m})$ for $j\in[k]$, and
map $W^{m}=(W_{1},\ldots,W_{m})$ to its closest quantization point. Here, the
distortion function between $W^{m}$ and a quantization point
$\hat{\mathbf{w}}_{j}$ should be defined; it is often chosen to be the average
of coordinate-wise distortions:

$\displaystyle\frac{1}{m}\sum\nolimits_{i=1}^{m}\varrho(W_{i},\hat{w}_{j,i}).$

Because the number of quantization points is $k$, we require $\log_{2}(k)$
bits to convey the index of the quantization point. The ratio $\log_{2}(k)/m$
is called the compression _rate_ , because it represents the number of
compression bits per source realization. For the selection of quantization
points $\hat{\mathbf{w}}_{1},\hat{\mathbf{w}}_{2},\ldots,\hat{\mathbf{w}}_{k}$
to succeed, we can consider balls of radius $\epsilon$ around these
quantization points and require that with high probability $W^{m}$ falls into
the union of these balls. This can be seen as a “block covering” of
$\mathcal{W}^{m}$ with average distortion $\epsilon$. Note that block covering
may need a smaller number of quantization points than the case where the
complete covering of the space $\mathcal{W}^{m}$ with the worst-case
distortion $\epsilon$ is required, as in $\epsilon$-net coverings (Anthony and
Bartlett, 1999).

In this context, the goal becomes finding the minimum number of bits that is
required to compress i.i.d. repetitions of the source $W$ so that it can be
recovered within a given distortion margin. Shannon (1948) showed that the
minimum compression rate needed for recovering a source with distortion
$\epsilon$ is determined by the _rate-distortion function_

$\displaystyle\mathfrak{RD}(\epsilon;P_{W},\varrho)\coloneq\inf
I(W;\hat{W}),\quad\text{such
that}\quad\mathbb{E}_{W,\hat{W}}[\varrho(W,\hat{W})]\leq\epsilon,$

where the infimum is over all conditional probability distributions (Markov
kernels) $P_{\hat{W}|W}$. Specifically, Shannon showed that for any _rate_
$R>\mathfrak{RD}(\epsilon;P_{W},\varrho)$, a sequence of _quantization
codebooks_ $\\{\mathcal{C}_{m}\\}_{m\in\mathbb{N}}$,
$\mathcal{C}_{m}{=}\\{\hat{\mathbf{w}}_{j}{=}(\hat{w}_{j,1},\ldots,\hat{w}_{j,m}),j\in[l_{m}]\\}\subseteq\mathcal{W}^{m}$
exists such that $l_{m}\leq e^{mR}$ and

$\displaystyle\lim_{m\rightarrow\infty}\mathbb{P}_{W^{\otimes m}}\left(\forall
j\colon\frac{1}{m}\sum\nolimits_{i=1}^{m}\varrho(W_{i},\hat{w}_{j,i})>\epsilon\right)=0.$
(4)

Intuitively, for discrete variables, the _effective size_ of $m$ independent
realizations of $W$ is about $e^{mH(W)}$, and each codeword
$\hat{\mathbf{w}}_{j}$ covers about $e^{mH(W|\hat{W})}$ of them, and thus, the
total needed codewords to cover $\mathcal{W}^{m}$ with high probability is
about $e^{mI(W;\hat{W})}$. Similar intuition holds for the continuous $W$, by
considering $h(W)$ and $h(W|\hat{W})$, and by considering the _effective
volume_ of $W^{m}$.

Finally, a series of works, _e.g._ (Marton, 1974; Han, 2000; Iriyama, 2005;
Bakshi and Bansal, 2005), studied the rate of convergence of the probability
in (4) to zero for a fixed rate $R$. Equivalently, one can formulate this
problem as the minimum needed rate $R$ to have the above error probability
decaying at least as fast as $\delta^{m}$. For sources with finite alphabets,
this quantity is equal to (Marton, 1974, Theorem 1)
$\sup\limits_{\begin{subarray}{c}Q\colon
D_{KL}(Q\|P_{W})\leq\log\left(1/\delta\right)\end{subarray}}\mathfrak{RD}(\epsilon;Q,\varrho)$,
where the supremum is over all distributions $Q$ defined over $\mathcal{W}$
such that $Q\ll P_{W}$. Intuitively, the empirical distribution
$\hat{P}_{W^{m}}$ of a vector of realizations $W^{m}$ satisfies
$D_{KL}(\hat{P}_{W^{m}}\|P_{W})\leq\log\left(1/\delta\right)$, with
probability at least $1-\delta^{m}$. The idea is to “cover” all such high
probable realizations in the balls with radius $\epsilon$. It turns out the
needed rate is the supremum of the needed rate for each empirical distribution
$Q$. Similar error exponent term for continuous sources can be found in
(Iriyama, 2005, Theorem 1).

In this work, we apply source coding concepts and techniques to establish
bounds on the generalization error. To this end, we attempt to ‘reliably
compress’ the hypothesis space with respect to a distortion that depends on
the excess generalization error induced by compression. We allow the
compression to be lossy within a distortion level. Then, we establish bounds
on the generalization error in terms of the compression rate, amount of
distortion, and reliability level.555The rate-distortion theory was previously
used in (Bu et al., 2021; Masiha et al., 2021). For instance, in (Bu et al.,
2021), it is used to compare the expectation of the generalization error of a
_compressed_ learning model with respect to the _original_ model. Herein, we
use it to analyze the generalization performance of the _original_ learning
model. In Masiha et al. (2021), generalization error is related to the rate-
distortion theory by noting the similarity of the related formulas. The
connection provided in this work is operational and thus much deeper.

##  3 Generalization Bounds via Rate Distortion Theory

We start by explaining our notion of compressibility adapted to algorithms.

###  3.1 Compressibility of an algorithm

The compression, in its classical source coding sense, aims to save a
compressed version of a source that is _close enough_ to the source and
requires a smaller storage capacity. Similarly, for a learning algorithm
$\mathcal{A}\colon\mathcal{S}\to\mathcal{W}$, where
$\mathcal{S}=\mathcal{Z}^{n}$, by having a dataset $S$ and a picked hypothesis
choice $\mathcal{A}(S)=W\in\mathcal{W}$, we are interested in finding another
algorithm
$\hat{\mathcal{A}}(S,W)=\hat{W}\in\hat{\mathcal{W}}\subseteq\mathcal{W}$ that
has fewer number of probable output hypotheses and _performs closely_ to the
original algorithm. In this work, we consider the generalization error as the
compression performance. Consider a training dataset $s$ and two hypotheses
$w$ and $\hat{w}$. We define the distortion function
$d\colon\mathcal{W}\times\hat{\mathcal{W}}\times\mathcal{S}\to\mathbb{R}$
between these two pairs of realizations as the difference of their
generalization performances:666While $d$ is clearly not a metric, it also
depends on the underlying distribution $\mu$; we drop this dependence for ease
of notations.

$\displaystyle d(w,\hat{w};s)\coloneq$
$\displaystyle\operatorname*{gen}(s,w)-\operatorname*{gen}(s,\hat{w}).$ (5)

Note that here, unlike the source-coding literature, we allow the distortion
function to take negative values.

To guarantee that this distortion (between single outputs of the original and
compressed algorithms) does not exceed a threshold, we need to control the
_worst-case_ distortion caused by compression, among all probable $w$ and
$\hat{w}$, which might end up with overly pessimistic results. To avoid this,
we utilize the _block coding_ technique as follows. For a block of
$m\in\mathbb{N}$ independent datasets $s^{m}=(s_{1},\ldots,s_{m})$ and a block
of picked hypotheses $W^{m}=(W_{1},\ldots,W_{m})$, where $W_{i}$ is a
hypothesis choice based on dataset $s_{i}$, i.e. $\mathcal{A}(s_{i})=W_{i}$,
$i\in[m]$, with a slight abuse of notations, denote
$\mathcal{A}(s^{m})=W^{m}$. We then consider a compression algorithm
$\hat{\mathcal{A}}_{m}\colon\mathcal{S}^{m}\times\mathcal{W}^{m}\to\hat{\mathcal{W}}^{m}$
that takes as input particular realizations $(s^{m},w^{m})$, where
$\mathcal{A}(s^{m})=w^{m}$, and outputs a block of hypotheses
$\hat{W}^{m}=(\hat{W}_{1},\ldots,\hat{W}_{m})$. We also need to extend our
definition in (5) to measure the distortion between two blocks of algorithm
realizations $\mathcal{A}(s^{m})=w^{m}$ and
$\hat{\mathcal{A}}_{m}(s^{m},w^{m})=\hat{w}^{m}$. For now, let us use
$d_{m}\colon\mathcal{S}^{m}\times\mathcal{W}^{m}\times\hat{\mathcal{W}}^{m}\to\mathbb{R}$
for $m\in\mathbb{N}$ to denote this extended distortion function, whose
details will be provided in the next section. In particular, we will use the
extended distortion function defined in (8) to obtain in expectation bounds
and an alternative definition given in (12) to obtain tail bounds on the
generalization gap.

Next, we define our compression algorithm. Fix a set
$\mathcal{H}_{m}\subseteq\hat{\mathcal{W}}^{m}$, that we coin a _hypothesis
book_ (as an analogy to code book), and denote its cardinality by $l_{m}$.
Denote the elements of $\mathcal{H}_{m}$ by
$\hat{\mathbf{w}}_{j}=(\hat{w}_{j,1},\ldots,\hat{w}_{j,m})\in\hat{\mathcal{W}}^{m}$,
where $j\in[l_{m}]$, i.e.,
$\mathcal{H}_{m}=\\{\hat{\mathbf{w}}_{j}\\}_{j=1}^{l_{m}}$. Having defined a
distortion function $d_{m}$ and fixed a set $\mathcal{H}_{m}$, among all
compression algorithms $\hat{\mathcal{A}}_{m}$ such that
$\hat{\mathcal{A}}_{m}(s^{m},w^{m})\in\mathcal{H}_{m}$, we consider the
_optimal_ compression algorithm, denoted by
$\hat{\mathcal{A}}^{*}_{m}(s^{m},w^{m};\mathcal{H}_{m})=\mathbf{\hat{w}}_{j}$,
where
$j=\operatorname*{arg\min}\nolimits_{j\in[l_{m}]}d_{m}(w^{m},\hat{\mathbf{w}}_{j};s^{m})$.
With this choice and for a fixed distortion level $\epsilon$, we define the
error event that happens when the average distortion between the original and
the optimal compressed algorithm exceeds $\epsilon$:

$\displaystyle\mathcal{E}_{m}(\mathcal{H}_{m},\epsilon;d_{m})\coloneq\left\\{\min\nolimits_{j\in[l_{m}]}d_{m}\left(\mathcal{A}(S^{m}),\hat{\mathbf{w}}_{j};S^{m}\right)>\epsilon\right\\}.$
(6)

Now, we are ready to define our compressibility notion, which will lay the
basis of our generalization bounds.

######  Definition 3.1.

The learning algorithm $\mathcal{A}$ is
$(R,\epsilon;\left\\{d_{m}\right\\}_{m})$-compressible777While many terms in
this work, including $R$ and the rate-distortion terms in the rest of the
text, depend on $\mu$, $P_{W|S}$, $n$, and the loss function, we drop these
dependencies for ease of exposition. for some $R\in\mathbb{R}^{+}$ and
$\epsilon\in\mathbb{R}$, if there exists a sequence of hypothesis books
$\left\\{\mathcal{H}_{m}\right\\}_{m\in\mathbb{N}}$,
$\mathcal{H}_{m}=\\{\mathbf{\hat{w}}_{j},j\in[l_{m}]\\}\subseteq\mathcal{\hat{W}}^{m}$
such that $l_{m}\leq e^{mR}$ and

$\displaystyle\lim_{m\rightarrow\infty}\mathbb{P}_{(S,W)^{\otimes
m}}\left(\mathcal{E}_{m}(\mathcal{H}_{m},\epsilon;d_{m})\right)=0,$ (7)

where $\mathcal{E}_{m}(\mathcal{H}_{m},\epsilon;d_{m})$ is defined in (6) and
$\mathbb{P}_{(S,W)^{\otimes m}}$ denotes the $m$-times product measure of the
joint distribution of $W$ and $S$.

###  3.2 Bounds on the expected value of the generalization gap

In this section, we prove bounds on the expected generalization error,
provided $\mathcal{A}$ is compressible. Intuitively, we first find compression
schemes that _cover_ $(S^{m},W^{m})$ with high probability, in a sense that is
defined in (7), such that on average the difference of generalization errors
of the original and compressed algorithms does not exceed a threshold. Then,
we show that the expected generalization error can be bounded in terms of the
parameters of this compressed algorithm. To do so, by borrowing from the
source coding literature, we define a distortion function between $m$
realizations of the two algorithms as:

$\displaystyle\vartheta_{m}(w^{m},\hat{w}^{m};s^{m})\coloneq\frac{1}{m}\sum\nolimits_{i=1}^{m}d(w_{i},\hat{w}_{i};s_{i}),$
(8)

where $d(w,\hat{w};s)$ was defined in (5).

Having condition (7) for this distortion function guarantees that the
expectation of the difference of the generalization errors of the original and
compressed algorithms does not exceed $\epsilon$. This is stated in Lemma E.1,
which is used in the proof of the following result, proved in Appendix E.1.

######  Theorem 3.2.

If a learning algorithm $\mathcal{A}(S)$ is
$(R,\epsilon;\left\\{|\vartheta_{m}|\right\\}_{m})$-compressible,888By
$|\vartheta_{m}|$ we mean simply the distortion function which is equal to
$|\vartheta_{m}(w^{m},\hat{w}^{m};s^{m})|$ for any $w^{m},\hat{w}^{m},s^{m}$.,
if $\mathbb{E}_{S,W}[|\operatorname*{gen}(S,W)|]<\infty$, and if for all
$w\in\mathcal{W}$, $\ell(Z,w)$ is $\sigma$-subgaussian, then
$\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|\leq\sqrt{2\sigma^{2}R/n}+\epsilon$.

This result shows that the compressibility of an algorithm directly translates
into having a good generalization performance, which can be seen as an
information theoretic counterpart of the existing compression bounds, e.g.,
(Arora et al., 2018; Suzuki et al., 2020b). To make the above bound more
explicit, we establish the following bound on the compressibility of any
arbitrary algorithm, whose proof is given in Appendix E.2. Let999Intuitively,
$\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]$
can be seen as the limit of the distortion function $\vartheta_{m}$ when
$m\rightarrow\infty$.

$\displaystyle R_{E}(\epsilon)=$
$\displaystyle\inf\limits_{P_{\hat{W}|S}}I(S;\hat{W}),\quad\text{such
that}\quad\left|\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]\right|\leq\epsilon,$
(9)

where the expectation is with respect to $P_{S,W}$ and $P_{S}\times
P_{\hat{W}|S}$.

######  Theorem 3.3.

Assume that the algorithm $\mathcal{A}(S)=W$ induces $P_{S,W}$, where
$\mathcal{S}$ and $\mathcal{W}$ are finite sets. Then, for every
$\epsilon\in\mathbb{R}$ and any $\nu_{1},\nu_{2}>0$, the algorithm
$\mathcal{A}(s)$ is
$\left(R_{E}(\epsilon)+\nu_{1},\epsilon+\nu_{2};\\{|\vartheta_{m}|\\}_{m}\right)$-compressible.

This theorem can be extended to infinite sets, with some further assumptions
on separability of $\operatorname*{gen}(S,W)$ with respect to $(S,W)$ and
using the quantization technique used in the proof of (El Gamal and Kim, 2011,
Theorem 3.6). Now, combining Theorems 3.2 and 3.3 yields:

######  Theorem 3.4.

Assume that the algorithm $\mathcal{A}(S)=W$ induces $P_{S,W}$ and for all
$w\in\mathcal{W}$, $\ell(Z,w)$ is $\sigma$-subgaussian. Then, for any
$\epsilon\in\mathbb{R}$,
$\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|\leq\sqrt{2\sigma^{2}R_{E}(\epsilon)/n}+\epsilon$.

The extended versions of Theorems 3.2 and 3.4 that include bounds on
$\mathbb{E}\left[\operatorname*{gen}(S,W)\right]$ and
$\mathbb{E}\left[|\operatorname*{gen}(S,W)|\right]$ as well, can be found in
Appendix D.1.101010The mild sufficient condition
$\mathbb{E}[|\operatorname*{gen}(S,W)|]{<}\infty$ is used to bound
$\mathbb{E}[|\operatorname*{gen}(S,W)|]$,
$\mathbb{E}[\operatorname*{gen}(S,W)]$, and
$|\mathbb{E}[\operatorname*{gen}(S,W)]|$ in the extended version of Theorem
3.2. The sufficiency of the condition
$|\mathbb{E}[\operatorname*{gen}(S,W)]|{<}\infty$ for bounding
$|\mathbb{E}[\operatorname*{gen}(S,W)]|$, although seemingly true, is not
shown in this work.

In addition to finite sets, Theorem 3.4 can be derived using Theorems 3.2 and
3.3 also for the infinite sets that satisfy some further separability
assumptions. However, for the infinite set, without any further assumptions,
we show this alternatively and trivially in Appendix E.3 by using and
extending the existing results of Xu and Raginsky (2017, Theorems 1, 4),
corresponding to Theorem 3.4 with $\epsilon=0$ (see Corollary 3.5 in below).
Theorem 3.4 is extended similarly to (Bu et al., 2020) in Theorem D.1
(Appendix D.1) that recovers and potentially improves over (Bu et al., 2020,
Proposition 1).

######  Corollary 3.5.

Suppose the algorithm $\mathcal{A}(S)=W$ induces $P_{S,W}$ and the loss
function $\ell(Z,w)$ is $\sigma$-subgaussian for any $w\in\mathcal{W}$. Then,
$\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|\leq\sqrt{2\sigma^{2}I(S;W)/n}$.

In this corollary, by applying a compressibility approach we could recover the
results obtained using the Donsker–Varadhan’s identity. Indeed, in Appendix
B.1 we showed that this identity can be interpreted and derived via a
compressibility approach.

The case of $\epsilon=0$, considered in (Xu and Raginsky, 2017; Bu et al.,
2020), corresponds to the lossless compression in source coding. While for
countable sets of $S$ or $W$, we can reliably cover $(S^{m},W^{m})$ with
$\epsilon=0$ (in the sense of (7)) and bounded $R$, for continuous sources and
hypotheses, this term could be infinite. In contrast, considering
$\epsilon\neq 0$, corresponds to the lossy compression in source coding, which
allows to reliably cover $(S^{m},W^{m})$ with bounded $R$ within distortion
$\epsilon$. Note that even for countable sets, $\epsilon\neq 0$ can give
better bounds.111111The approach applied in in (Negrea et al., 2020a) for
studying $\mathbb{E}[\operatorname*{gen}(S,W)]$ also can be seen as lossy
compression. They considered choosing a randomized ‘surrogate hypothesis’
$\hat{W}$ for each $W$, and argue that to establish a good bound on
$\mathbb{E}[\operatorname*{gen}(S,W)]$, one could benefit from the trade-off
between $\mathbb{E}[\hat{\mathcal{L}}(S,\hat{W})-\hat{\mathcal{L}}(S,W)]$ and
$\mathbb{E}[\mathcal{L}(\hat{W})-\hat{\mathcal{L}}(S,\hat{W})]$. However, they
have not proposed general explicit bounds on these terms, and rather
considered ad-hoc strategies for overparameterized linear regression and
hypercube classification problems, when $\hat{\mathcal{L}}(S,W)=0$.

The benefit of $\epsilon\neq 0$ becomes more clear by having a Lipschitz loss
assumption. Combining this assumption with the above theorem directly yields
an upper bound on the expected generalization error in terms of the rate-
distortion function of the hypothesis.

######  Corollary 3.6 (Lipschitz loss).

Suppose that for a distortion function
$\varrho\colon\mathcal{W}\times\hat{\mathcal{W}}\to\mathbb{R}^{+}$ and every
$z,w,\hat{w}$,
$|\ell(z,w)-\ell(z,\hat{w})|\leq\mathfrak{L}\varrho(w,\hat{w})$121212Note that
this condition and imposing the Markov chain $\hat{W}-W-S$ yield
$\left|\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]\right|\leq
2\mathfrak{L}\mathbb{E}_{W,\hat{W}}\left[\varrho(W,\hat{W})\right]$ and
$I(S;\hat{W})\leq I(W;\hat{W})$ by data processing inequality. and $\ell(Z,w)$
is $\sigma$-subgaussian. Then, for any $\epsilon\in\mathbb{R}^{+}$, we have
$\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|\leq\sqrt{2\sigma^{2}\mathfrak{RD}(\epsilon/(2\mathfrak{L});P_{W},\varrho)/n}+\epsilon$,
where $\mathfrak{RD}(\epsilon;P_{W},\varrho)$ is the rate-distortion function
with respect to the distortion function $\varrho$:

$\displaystyle\mathfrak{RD}(\epsilon;P_{W},\varrho)\coloneq\inf\limits_{\begin{subarray}{c}P_{\hat{W}|W}\end{subarray}}I(W;\hat{W}),\quad\text{such
that}\quad\mathbb{E}_{W,\hat{W}}\left[\varrho(W,\hat{W})\right]\leq\epsilon.$
(10)

While the term $R_{E}(\epsilon)$ in (9) is in general intractable, the above
bound is amenable to computation once the marginal distribution $P_{W}$ is
known; a more relaxed constraint than knowing $P_{S,W}$ which is needed in
many of the information-theoretic bounds on generalization error. The rate-
distortion computation is a convex minimization problem over $P_{\hat{W}|W}$
and $\epsilon$, that can be effectively computed for finite alphabets using
Blahut-Arimoto algorithm (Blahut, 1972; Arimoto, 1972). Note that using
Carathéodory’s theorem (El Gamal and Kim, 2011, Appendix C), it can be shown
that it is sufficient to consider $\hat{\mathcal{W}}$ such that
$|\hat{\mathcal{W}}|\leq|\mathcal{W}|+1$. For the continuous alphabets, this
terms can be efficiently estimated using the fine quantization technique
(_e.g._ (El Gamal and Kim, 2011, Proof of Theorem 3.6) or by using the
existing lower bounds, _e.g._ (Riegler et al., 2018), that are almost tight in
the small $\epsilon$ regime.

As an analytical example, suppose that the data $Z\in\mathbb{R}^{d}$ is
composed of $d$ i.i.d. elements, each one distributed according to the normal
distribution $\mathcal{N}(0,\sigma_{0}^{2})$ and suppose that we choose $W$ as
$W=\frac{1}{n}\sum_{i=1}^{n}Z_{i}\sim\mathcal{N}(0,(\sigma_{0}^{2}/n)\mathrm{I}_{d})$,
where $\mathrm{I}_{d}$ is the $d\times d$ identity matrix. Further, suppose
that $\ell(Z,w)$ is $\sigma$-subgaussian for any $w\in\mathbb{R}^{d}$ and
$|\ell(z,w)-\ell(z,\hat{w})|\leq\mathfrak{L}\|w-\hat{w}\|^{2}$. Then, while
$I(S;W)=\infty$, Corollary 3.6 together with (Cover and Thomas, 2006, Theorem
10.3.2) yield $\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|$
is bounded by $\min_{0<\epsilon\leq
d\sigma_{0}^{2}/n}\sqrt{\sigma^{2}d\log\left(2\mathfrak{L}d\sigma_{0}^{2}/(n\epsilon)\right)/n}+\epsilon$,
which equals $2\mathfrak{L}d\sigma_{0}^{2}/n$ for
$\epsilon=2\mathfrak{L}d\sigma_{0}^{2}/n$.

The optimal order of $\epsilon$ (and the corresponding rate-distortion terms)
with respect to $n$ depends on $P_{S,W}$, as well as the loss function. In the
above example, $\epsilon$ is chosen as $\mathcal{O}(1/n)$, and in the
following corollary as $\mathcal{O}(1/\sqrt{n})$, resulting in the rate-
distortion terms of order $\mathcal{O}(1)$ and $\mathcal{O}(\log(n))$,
respectively.

In our next result, we show that our bound in terms of the rate-distortion
function yields a fractal dimension-based bound as well. Let us define the
rate-distortion dimension (Kawabata and Dembo, 1994) for a distribution $Q$ as
$\dim_{\mathrm{R}}(Q)\coloneq\limsup\nolimits_{\epsilon\rightarrow
0}\mathfrak{RD}(\epsilon;Q,\varrho)/\log(1/\epsilon)$.

######  Corollary 3.7 (Rate-distortion dimension).

Suppose that for a distortion function
$\varrho\colon\mathcal{W}\times\hat{\mathcal{W}}\to\mathbb{R}^{+}$ and every
$z,w,\hat{w}$, $|\ell(z,w)-\ell(z,\hat{w})|\leq\mathfrak{L}\varrho(w,\hat{w})$
and $\ell(Z,w)$ is $\sigma$-subgaussian. Moreover, assume that
$\sup\nolimits_{\epsilon\leq\epsilon_{0}}\mathfrak{RD}(\epsilon;P_{W},\varrho)/\log(1/\epsilon)$
converges uniformly over $n$ as $\epsilon_{0}\to 0$. Then, there exists a
$n_{0}$ such that for every $n\geq n_{0}$,
$\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|\leq\sqrt{4\sigma^{2}\dim_{\mathrm{R}}(P_{W})\log(n\mathfrak{L}^{2})/n}$.

This corollary, proved in Appendix E.4, shows the relation of our approach
with dimension-based bounds. The rate-distortion dimension is a lower bound to
the Minkowski (box-counting) dimension of the set $\mathcal{W}$ (Kawabata and
Dembo (1994)), which was considered in (Şimşekli et al., 2020; Birdal et al.,
2021). Moreover $\dim_{\mathrm{R}}(P_{W})$ is equal to the Rényi information
dimension under certain conditions (Kawabata and Dembo, 1994, Proposition
3.3). The latter dimension is shown to be related to the fundamental limits of
the almost lossless compression (Wu and Verdú, 2010).

###  3.3 Tail bounds on the generalization gap

To establish a tail bound on the generalization performance, we need to find a
compression scheme that not only _covers_ $(S^{m},W^{m})$ with high
probability (in a sense of (7)), but also its probability of covering failure
is exponentially decreasing with $m$, which leads us to the following notion.

######  Definition 3.8.

The learning algorithm $\mathcal{A}$ is
$(R,\epsilon,\delta;\left\\{d_{m}\right\\}_{m})$\- exponentially compressible
for some $\delta>0$, if conditions of Definition 3.1 hold and

$\displaystyle\lim_{m\rightarrow\infty}\left[-\frac{1}{m}\log\left(\mathbb{P}_{(S,W)^{\otimes
m}}\left(\mathcal{E}_{m}(\mathcal{H}_{m},\epsilon;d_{m})\right)\right)\right]\geq\log(1/\delta).$
(11)

In other words, the error probability is asymptotically bounded by
$\delta^{m}$.

On the other hand, instead of considering (8), it turns out that it is
sufficient to keep the difference between the _average_ generalization error
of the compressed algorithm and the _lowest_ error of the original algorithm
within a threshold. More precisely, we define the new distortion
function:131313Note that
$\varphi_{m}(w^{m},\hat{w}^{m};s^{m})\leq\vartheta_{m}(w^{m},\hat{w}^{m};s^{m})$.
For further discussion on this distortion function, refer to Section 4.

$\displaystyle\varphi_{m}(w^{m},\hat{w}^{m};s^{m})\coloneq\min_{j\in[m]}\operatorname*{gen}(s_{j},w_{j})-\frac{1}{m}\sum\nolimits_{i=1}^{m}\operatorname*{gen}(s_{i},\hat{w}_{i}).$
(12)

By using this notion, our first tail bound on the generalization performance
of an algorithm is stated in the following theorem, which is proved in
Appendix E.5.

######  Theorem 3.9.

If a learning algorithm $\mathcal{A}$ is
$(R,\epsilon,\delta;\left\\{\varphi_{m}\right\\}_{m})$-exponentially
compressible and if for all $w\in\mathcal{W}$, the loss $\ell(Z,w)$ is
$\sigma$-subgaussian, then with probability at least $1-\delta$, we have that
$\operatorname*{gen}(S,W)\leq\sqrt{2\sigma^{2}(R+\log\left(1/\delta\right))/n}+\epsilon$.

This result shows that exponentially compressible algorithms, with small
$(R,\epsilon)$, generalize well with probability $1-\delta$. Next, in our main
tail bound, we will show that any arbitrary algorithm is exponentially
compressible, and we will establish a bound on its compressibility triplet
$(R,\epsilon,\delta)$. To state this result, we need some definitions. For a
given distribution $Q$ over $\mathcal{S}\times\mathcal{W}$, let

$\displaystyle
d_{Q}(\hat{w};s)\coloneq\inf_{\begin{subarray}{c}(s^{\prime},w^{\prime})\in\operatorname{supp}(Q)\end{subarray}}\left[\operatorname*{gen}(s^{\prime},w^{\prime})\right]-\operatorname*{gen}(s,\hat{w}).$
(13)

Intuitively, $\mathbb{E}_{S,\hat{W}}[d_{Q}(\hat{W};S)]$ can be seen as the
limit of the distortion function $\varphi_{m}$ when $m\rightarrow\infty$.
Moreover, for a distribution $Q$ defined over $\mathcal{S}\times\mathcal{W}$,
let

$\displaystyle\mathfrak{RD}^{*}(\epsilon;Q)\coloneq$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|S}:\\\
\mathbb{E}\left[d_{Q}(\hat{W};S)\right]\leq\epsilon\end{subarray}}I(S;\hat{W})\leq\inf\limits_{\begin{subarray}{c}P_{\hat{W}|S}:\\\
\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]\leq\epsilon\end{subarray}}I(S;\hat{W}),$
(14)

where the infimum is over all Markov kernels
$P_{\hat{W}|S}\colon\hat{\mathcal{W}}\times\mathcal{S}\to\mathbb{R}^{+}$ and
the expectations and the mutual information are with respect to joint
distributions $Q$ and $Q_{S}\times P_{\hat{W}|S}$, where $Q_{S}$ is the
marginal distribution of $S$. Now, we state our main tail bound result, proved
in Appendix E.6.

######  Theorem 3.10.

Suppose that the algorithm $\mathcal{A}(S)=W$ induces $P_{S,W}$ and for all
$w\in\mathcal{W}$, $\ell(Z,w)$ is $\sigma$-subgaussian. Then, for every
$\epsilon\in\mathbb{R}$ and $\delta\geq 0$, with probability at least
$1-\delta$,

$\displaystyle\operatorname*{gen}(S,W)\leq\sqrt{\frac{2\sigma^{2}(R_{p}(\delta,\epsilon)+\log\left(1/\delta\right))}{n}}+\epsilon,~{}R_{p}(\delta,\epsilon)\coloneq\sup\limits_{\begin{subarray}{c}Q\colon
D_{KL}(Q\|P_{S,W})\leq\log\left(1/\delta\right)\end{subarray}}\mathfrak{RD}^{*}(\epsilon;Q),$

where the supremum is over all probability distributions $Q$ over
$\mathcal{S}\times\mathcal{W}$.

To the best of our knowledge, this is the first information-theoretic tail
bound on the generalization error with the logarithmic dependence on
$1/\delta$. The bound does not reduce to previous results even for
$\epsilon=0$. In this case, $\mathfrak{RD}^{*}(0;Q)\leq I_{Q}(S;W)$ as
$\hat{\mathcal{W}}=\mathcal{W}$ and $P_{\hat{W}|S}=Q_{W|S}$ are valid choices,
where $I_{Q}(S;W)$ implies the mutual information under the distribution $Q$.
Hence, as a corollary of the above theorem, with probability at least
$1-\delta$, we have

$\displaystyle\operatorname*{gen}(S,W)\leq\sqrt{2\sigma^{2}(\sup\limits_{\begin{subarray}{c}Q\colon
D_{KL}(Q\|P_{S,W})\leq\log\left(1/\delta\right)\end{subarray}}I_{Q}(S;W)+\log\left(1/\delta\right))/n}.$
(15)

The bound in Theorem 3.10 does not only depend on $P_{S,W}$, but on all $Q$
close to $P_{S,W}$. This is similar to the error exponent result of (Marton,
1974, Theorem 1). Intuitively, by considering all $Q$ satisfying
$D_{KL}(Q\|P_{S,W})\leq\log\left(1/\delta\right)$, we cover realizations of
$(S^{m},W^{m})$ with probability at least $1-\delta^{m}$. In other words, to
have a good generalization bound with high probability, the algorithm should
be compressible under all such $Q$ that are close enough to $P_{S,W}$.

Theorem 3.10 does not take into account any additional stochasticity of the
algorithm, as considered in (Harutyunyan et al., 2021). Considering such a
scenario yields stronger results, presented in Appendix D.2.

Similar to the in expectation part, by having a Lipschitzness property and
using (14), Theorem 3.10 can be upper-bounded in terms of the rate-distortion
functions of the hypothesis set.

######  Corollary 3.11 (Lipschitz loss).

Suppose that for a distortion function
$\varrho\colon\mathcal{W}\times\hat{\mathcal{W}}\to\mathbb{R}^{+}$ and every
$z,w,\hat{w}$, $|\ell(z,w)-\ell(z,\hat{w})|\leq\mathfrak{L}\varrho(w,\hat{w})$
and $\ell(Z,w)$ is $\sigma$-subgaussian. Then, for any
$\epsilon\in\mathbb{R}^{+}$, the term $R_{p}(\delta,\epsilon)$ in Theorem 3.10
can be upper bounded by

$\displaystyle
R_{p}(\delta,\epsilon)\leq\sup\limits_{\begin{subarray}{c}Q_{W}\colon
D_{KL}(Q_{W}\|P_{W})\leq\log\left(1/\delta\right)\end{subarray}}\mathfrak{RD}(\epsilon/(2\mathfrak{L});Q_{W},\varrho),$
(16)

where the supremum is over all possible distributions $Q_{W}$ over
$\mathcal{W}$.

The above corollary recovers some classical results, _e.g._ the bound obtained
by using $\epsilon$-net coverings. This result, together with some other
concrete examples are presented in Appendix D.3. Furthermore, similar to
Corollary 3.7, one can derive a dimension-based bound by using Corollary D.2.

Note that Theorem 3.10 can be made data-dependent using ideas of Negrea et al.
(2020b). Finally, we further extend our results in Appendix A, that recovers
(and improves in specific cases) the conditional mutual information based
results of Steinke and Zakynthinou (2020); Harutyunyan et al. (2021).

##  4 Proof Outline

Our main results are new bounds on the generalization gap. However, we also
develop new techniques which are rather general and applicable to arbitrary
random variables. In particular, we derive a variational representation of the
tail probability in Lemma C.1 (Appendix C) that results the following tail
bound for any arbitrary random variable $X$:

######  Theorem 4.1.

For arbitrary random variables $X\in\mathbb{R}$, $Y\in\mathcal{Y}$ distributed
according to $(X,Y)\sim\mu_{X,Y}$, with marginals $X\sim\mu_{X}$ and
$Y\sim\mu_{Y}$ and for any $\delta\geq 0$ and $\epsilon,\Delta\in\mathbb{R}$,
we have

$\displaystyle\log\mu_{X}\left([\Delta,\infty)\right)\leq$ (17)
$\displaystyle\max\left[\log(\delta),\sup_{\nu_{X,Y}\in\mathcal{G}}\,\inf_{p_{\hat{X}|Y}\in\mathcal{Q}(\nu)}\,\inf_{q_{\hat{X}|Y},\,\lambda\geq
0}\left\\{D_{KL}(p_{\hat{X}|Y}\nu_{Y}\|q_{\hat{X}|Y}\nu_{Y})-\lambda(\Delta-\epsilon)+\log\mathbb{E}_{\mu_{Y}q_{\hat{X}|Y}}[e^{\lambda\hat{X}}]\right\\}\right]$

where
$\mathcal{G}\coloneq\\{\nu_{X,Y}:D_{KL}(\nu_{X,Y}\|\mu_{X,Y})\leq\log(1/\delta)\\}$,
$\hat{X}$ is a real valued random variable and $\mathcal{Q}(\nu)$ is the set
of all conditional distributions $p_{\hat{X}|Y}$ such that under the joint
distribution $p_{\hat{X}|Y}\nu_{X,Y}$ we have:
$\left[\inf_{x\in\operatorname{supp}(\nu_{X})}x\right]-\mathbb{E}[\hat{X}]\leq\epsilon$,
$\nu_{X}$ and $\nu_{Y}$ are marginals of $\nu_{X,Y}$ with respect to $X$ and
$Y$, respectively, and the inner infimum is over all conditional distributions
$q_{\hat{X}|Y}$.

This theorem is proved in Appendix E.7 and implies Theorem 3.10 by considering
$X$ as $\operatorname*{gen}(S,W)$. A key idea used in this paper is leveraging
the block covering technique to establish tail bounds. In the following
subsection, we explain our general approach for this.

###  4.1 Tail bound via information-theoretic covering

Covering is a technique that allows to provide upper bounds on the tail
probability or the expectation of an arbitrary random variable. The standard
covering technique works as follows (see (Vershynin, 2018, Chapter 7)):
consider a random process $(Y_{t})_{t\in T}$, and the random variable
$X=\sup_{t\in T}Y_{t}$. An $\epsilon$-covering (or $\epsilon$-net) of the set
$T$ is a finite number of points
$\mathcal{N}=\\{t_{1},t_{2},\ldots,t_{k}\\}\subset T$ such that every point
$t\in T$ is within distortion $\epsilon$ of some point of $\mathcal{N}$. In
the information theory literature, the points $t_{i}\in\mathcal{N}$ are called
“quantization points”, and the process of mapping an arbitrary point $t\in T$
to its closest point in set $\mathcal{N}$ is called _compression_ because it
allows one to describe each point in set $t$ by just a number from the set
$\\{1,2,\ldots,k\\}$, _i.e.,_ the index of its closest point in $\mathcal{N}$.
Let $\hat{X}_{i}=Y_{t_{i}}$ for $1\leq i\leq k$ be the value of the random
process at points in the $\epsilon$-net. The idea of covering is to
approximate $X=\sup_{t\in T}Y_{t}$ by
$\max(\hat{X}_{1},\hat{X}_{2},\ldots,\hat{X}_{k})$. Since any arbitrary $t\in
T$ is close to some point $t_{i}\in\mathcal{N}$, random variable $X$ too
should be close to $\hat{X}_{i}$ for some $i$. Once we relate $\sup_{t\in
T}Y_{t}$ to the maximum of finitely many terms
$\max(\hat{X}_{1},\hat{X}_{2},\ldots,\hat{X}_{k})$, one can use tools such as
the union bound to study the latter maximum.

The underlying idea of covering is fairly general. Suppose we have an
arbitrary random variable $X$ that is not necessarily arising as the supremum
of an underlying random process. We can still apply similar ideas if we
“cover” $X$ by a finite collection of random variables
$\\{\hat{X}_{1},\hat{X}_{2},\ldots,\hat{X}_{k}\\}$. In this paper, we take a
similar approach but with two crucial differences: (i) instead of covering a
random variable $X$, we start off by taking a vector $X^{m}$ of $m$ i.i.d.
repetitions of $X$, and cover the vector $X^{m}$. This technique is known in
the information literature as “block-coding” and allows for a certain
concentration of measure phenomenon to occur when we let $m$, the number of
repetitions of $X$ to go to infinity. Moreover, it allows to utilize classical
results on compression from information theory (ii) instead of covering the
entire space as in an $\epsilon$-net, we allow for a vanishing fraction of the
space to remain uncovered. This is in line with the information-theoretic
notion of covering. More precisely, we cover the subspace in which $X^{m}$
concentrates on.

To see the idea of block covering in action, let $X_{1},\ldots,X_{m}$ be $m$
i.i.d. repetitions of $X$. Then,
$\mathbb{P}\left(X\geq\Delta\right)^{m}=\mathbb{P}\left(\min_{i}X_{i}\geq\Delta\right)$.
In order to relate $\min_{i}X_{i}$ to an average, we introduce the following
distortion function between two sequences.141414This distortion function is
new and not previously used in the information theory literature to the best
of our knowledge.

######  Definition 4.2.

Given two sequences $\vec{a}=(a_{1},\ldots,a_{m})$ and
$\vec{b}=(b_{1},\ldots,b_{m})$, define
$\rho(\vec{a},\vec{b})\coloneq\min_{i}a_{i}-\frac{1}{m}\sum_{i}b_{i}$.

Then, we have the following result (see Appendix E.8 for a proof):

######  Theorem 4.3.

Let $X$ be an arbitrary random variable. Take $m\in\mathbb{N}$ and let $X^{m}$
be its $m$ i.i.d. repetitions. Let $\hat{X}^{m}(1),\ldots,\hat{X}^{m}(k)$ be
an arbitrary set of $k\in\mathbb{N}$ random variables produced from some
arbitrary conditional distribution
$Q_{\hat{X}^{m}(1),\cdots,\hat{X}^{m}(k)|X^{m}}$. Then, for any
$\epsilon\in\mathbb{R}$,

$\displaystyle\mathbb{P}\left(X\geq\Delta\right)^{m}$
$\displaystyle\leq\mathbb{P}\left(\exists
j:\frac{1}{m}\sum_{i=1}^{m}\hat{X}_{i}(j)\geq\Delta-\epsilon\right)+\mathbb{P}\left(\forall
j\in[k]:\rho(X^{m},{\hat{X}}^{m}(j))>\epsilon\right)$ (18)
$\displaystyle\leq\sum_{j=1}^{k}\mathbb{P}\left(\frac{1}{m}\sum_{i=1}^{m}\hat{X}_{i}(j)\geq\Delta-\epsilon\right)+\mathbb{P}\left(\forall
j\in[k]:\rho(X^{m},{\hat{X}}^{m}(j))>\epsilon\right).$

The random vectors $\hat{X}^{m}(1),\hat{X}^{m}(2),\ldots,\hat{X}^{m}(k)$
represent “quantizations” of the sequences $X^{m}$. The term
$\mathbb{P}\left(\forall j\in[k]:\rho(X^{m},{\hat{X}}^{m}(j))>\epsilon\right)$
represents probability of excess distortion (with respect to $\rho$) when
covering $X^{m}$ by $\hat{X}^{m}(1),\ldots,\hat{X}^{m}(k)$. The term
$\mathbb{P}\left(\frac{1}{m}\sum_{i}\hat{X}_{i}(j)\geq\Delta-\epsilon\right)$
is a tail bound inequality on the quantizations points. We make this more
clear by the following example.

######  Example 4.4.

Let $k=1$, $X{\sim}\text{Bernoulli}(1/2)$, $\Delta{=}0.5$, and $\epsilon{=}0$.
Then, $\mathbb{P}(X\geq\Delta)=0.5$. Let $\hat{X}_{i}=0$ with probability one.
Then, $\mathbb{P}(\sum\hat{X}_{i}\geq\Delta-\epsilon)=0$. The term
$\rho(X^{m},\hat{X}^{m})$ is zero if and only if $X_{i}=0$ for some $i$. Thus,
$\mathbb{P}(\rho(X^{m},\hat{X}^{m})>\epsilon)=(1/2)^{m}$. Hence, we have
equality for this example.

##  5 Conclusion

In this work, using the source coding literature, we developed a
compressibility framework to study the generalization error of the stochastic
learning algorithms. This framework allows establishing bounds on the
generalization gap in terms of rate-distortion function. Further, our defined
compressibility notion makes the connection between several different research
approaches in studying the generalization gap, _e.g._ information-theoretic
and dimension-based approaches. This study opens up new directions, including:
(i) making our bounds computational by applying the numerical methods to
compute or bound the rate-distortion function and rate-distortion dimension,
(ii) investigating the relation between our bounds and other dimensions-based
bounds, by exploiting the relation between rate-distortion dimension and
fractal dimensions, _e.g._ correlation dimension, (iii) making the connection
between our compressibility framework and PAC-Bayesian approaches (McAllester,
1999),151515This relation have been previously established by Blum and
Langford (2003) for the compressibility framework of (Littlestone and Warmuth,
1986). The connection of the PAC-Bayesian approaches, particularly when
applied for neural networks (MacKay, 1995; Langford and Caruana, 2001;
Dziugaite and Roy, 2017; Neyshabur et al., 2018), with our framework also
seems promising. In these approaches the propagated error at the output of the
network due to small perturbation of the weights are studied. Perturbing $W$
can be seen as letting $\hat{W}=W+N$, where $N$ is an independent noise, and
the propagated error as the induced distortion. Then, one needs to properly
bound $I(\hat{W};W)$. (iv) to establish general bounds on the generalization
error by combining rate-distortion theoretic results of this work and the
approach of using surrogate hypothesis (Negrea et al., 2020a), and
contrariwise, to use the ad-hoc approaches of the latter for our
compressibility framework to derive alternative bounds, (v) and finally
combining the information-theoretic covering approach, introduced in Section
4.1, with other related techniques such as chaining.

## Acknowledgments

This work is partly supported by the French National Research Agency grant
ANR-16-CE23-0014 (FBIMATRIX). UŞ’s research is supported by the French
government under management of Agence Nationale de la Recherche as part of the
“Investissements d’avenir” program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA
Institute).

## References

  * Anthony and Bartlett (1999) Martin Anthony and Peter L. Bartlett.  _Neural Network Learning: Theoretical Foundations_.  Cambridge University Press, 1999.
  * Arimoto (1972) Suguru Arimoto.  An algorithm for computing the capacity of arbitrary discrete memoryless channels.  _IEEE Transactions on Information Theory_ , 18(1):14–20, 1972.
  * Arora et al. (2018) Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang.  Stronger generalization bounds for deep nets via a compression approach.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80, pages 254–263. PMLR, 10–15 Jul 2018.
  * Bakshi and Bansal (2005) Mayank Bakshi and Rakesh K. Bansal.  On error exponent in lossy source coding, 2005.
  * Barsbey et al. (2021) Melih Barsbey, Milad Sefidgaran, Murat A Erdogdu, Gaël Richard, and Umut Şimşekli.  Heavy tails in SGD and compressibility of overparametrized neural networks.  In _Thirty-Fifth Conference on Neural Information Processing Systems_ , 2021.
  * Baykal et al. (2019) Cenk Baykal, Lucas Liebenwein, Igor Gilitschenski, Dan Feldman, and Daniela Rus.  Data-dependent coresets for compressing neural networks with applications to generalization bounds.  In _International Conference on Learning Representations_ , 2019.
  * Berger (1975) Toby Berger.  _Rate Distortion Theory and Data Compression_ , pages 1–39.  Springer Vienna, Vienna, 1975.  ISBN 978-3-7091-2928-9.
  * Birdal et al. (2021) Tolga Birdal, Aaron Lou, Leonidas Guibas, and Umut Şimşekli.  Intrinsic dimension, persistent homology and generalization in neural networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Blahut (1972) Richard Blahut.  Computation of channel capacity and rate-distortion functions.  _IEEE Transactions on Information Theory_ , 18(4):460–473, 1972.
  * Blum and Langford (2003) Avrim Blum and John Langford.  Pac-mdl bounds.  In _Learning theory and kernel machines_ , pages 344–357. Springer, 2003.
  * Boucheron et al. (2013) Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  _Concentration Inequalities: A Nonasymptotic Theory of Independence_.  OUP Oxford, 2013.
  * Bu et al. (2020) Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli.  Tightening mutual information-based bounds on generalization error.  _IEEE Journal on Selected Areas in Information Theory_ , 1(1):121–130, May 2020.  ISSN 2641-8770.
  * Bu et al. (2021) Yuheng Bu, Weihao Gao, Shaofeng Zou, and Venugopal V. Veeravalli.  Population risk improvement with model compression: An information-theoretic approach.  _Entropy_ , 23(10), 2021.
  * Camuto et al. (2021) Alexander Camuto, George Deligiannidis, Murat A. Erdogdu, Mert Gürbüzbalaban, Umut Şimşekli, and Lingjiong Zhu.  Fractal structure and generalization properties of stochastic optimization algorithms, 2021.
  * Cover and Thomas (2006) Thomas M. Cover and Joy A. Thomas.  _Elements of information theory (2. ed.)_.  Wiley, 2006.  ISBN 978-0-471-24195-9.
  * Csiszár (1995) Imre Csiszár.  Generalized cutoff rates and renyi’s information measures.  _IEEE Transactions on Information Theory_ , 41(1):26–34, 1995.
  * Csiszár and Körner (2011) Imre Csiszár and János Körner.  _Information Theory: Coding Theorems for Discrete Memoryless Systems_.  Cambridge University Press, 2 edition, 2011.
  * Cuff et al. (2010) Paul Warner Cuff, Haim H. Permuter, and Thomas M. Cover.  Coordination capacity.  _IEEE Transactions on Information Theory_ , 56(9):4181–4206, 2010.
  * Dziugaite and Roy (2017) Gintare Karolina Dziugaite and Daniel M Roy.  Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.  _arXiv preprint arXiv:1703.11008_ , 2017.
  * El Gamal and Kim (2011) Abbas El Gamal and Young-Han Kim.  _Network Information Theory_.  Cambridge University Press, 2011.
  * Esposito et al. (2020) Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa.  Generalization error bounds via Rényi-, $f$-divergences and maximal leakage, 2020.
  * Haghifam et al. (2020) Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M. Roy, and Gintare Karolina Dziugaite.  Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms, 2020.
  * Haghifam et al. (2021) Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran, and Daniel M. Roy.  Towards a unified information-theoretic framework for generalization.  In _Thirty-Fifth Conference on Neural Information Processing Systems_ , 2021.
  * Han (2000) Te Sun Han.  The reliability functions of the general source with fixed-length coding.  _IEEE Transactions on Information Theory_ , 46(6):2117–2132, 2000.
  * Harutyunyan et al. (2021) Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan.  Information-theoretic generalization bounds for black-box learning algorithms, 2021.
  * Hellstrom and Durisi (2020) Fredrik Hellstrom and Giuseppe Durisi.  Generalization bounds via information density and conditional information density.  _IEEE Journal on Selected Areas in Information Theory_ , 1(3):824–839, Nov 2020.  ISSN 2641-8770.
  * Hodgkinson et al. (2021) Liam Hodgkinson, Umut Şimşekli, Rajiv Khanna, and Michael W. Mahoney.  Generalization properties of stochastic optimizers via trajectory analysis, 2021.
  * Hsu et al. (2021) Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang.  Generalization bounds via distillation.  In _International Conference on Learning Representations_ , 2021.
  * Ihara and Kubo (2000) Shunsuke Ihara and Masashi Kubo.  Error exponent for coding of memoryless gaussian sources with a fidelity criterion.  _IEICE Trans. Fundamaentals, A_ , 83(10):1891–1897, oct 2000.  ISSN 09168508.
  * Iriyama (2005) Kiminori Iriyama.  Probability of error for the fixed-length lossy coding of general sources.  _IEEE Transactions on Information Theory_ , 51(4):1498–1507, 2005.
  * Kawabata and Dembo (1994) Tsutomu Kawabata and Amir Dembo.  The rate-distortion dimension of sets and measures.  _IEEE Transactions on Information Theory_ , 40(5):1564–1572, 1994.
  * Kuhn et al. (2021) Lorenz Kuhn, Clare Lyle, Aidan N. Gomez, Jonas Rothfuss, and Yarin Gal.  Robustness to Pruning Predicts Generalization in Deep Neural Networks.  _arXiv:2103.06002 [cs, stat]_ , March 2021.
  * Langford and Caruana (2001) John Langford and Rich Caruana.  (not) bounding the true error.  _Advances in Neural Information Processing Systems_ , 14, 2001.
  * Littlestone and Warmuth (1986) Nick Littlestone and Manfred Warmuth.  Relating data compression and learnability.  _Citeseer_ , 1986.
  * MacKay (1995) David JC MacKay.  Probable networks and plausible predictions-a review of practical bayesian methods for supervised neural networks.  _Network: computation in neural systems_ , 6(3):469, 1995.
  * Marton (1974) Katalin Marton.  Error exponent for source coding with a fidelity criterion.  _IEEE Transactions on Information Theory_ , 20(2):197–199, 1974.
  * Masiha et al. (2021) Mohammad Saeed Masiha, Amin Gohari, Mohammad Hossein Yassaee, and Mohammad Reza Aref.  Learning under distribution mismatch and model misspecification.  In _2021 IEEE International Symposium on Information Theory (ISIT)_ , pages 2912–2917. IEEE, 2021.
  * McAllester (1999) David A McAllester.  Some pac-bayesian theorems.  _Machine Learning_ , 37(3):355–363, 1999.
  * Negrea et al. (2020a) Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy.  In defense of uniform convergence: Generalization via derandomization with an application to interpolating predictors.  In _International Conference on Machine Learning_ , pages 7263–7272. PMLR, 2020a.
  * Negrea et al. (2020b) Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M. Roy.  Information-theoretic generalization bounds for sgld via data-dependent estimates, 2020b.
  * Neyshabur et al. (2018) Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro.  A pac-bayesian approach to spectrally-normalized margin bounds for neural networks, 2018.
  * Polyanskiy and Wu (2014) Yury Polyanskiy and Yihong Wu.  Lecture notes on information theory.  _Lecture Notes for ECE563 (UIUC) and_ , 6(2012-2016):7, 2014.
  * Riegler et al. (2018) Erwin Riegler, Helmut Bölcskei, and Günther Koliander.  Rate-distortion theory for general sets and measures.  In _2018 IEEE International Symposium on Information Theory (ISIT)_ , pages 101–105, 2018.
  * Russo and Zou (2016) Daniel Russo and James Zou.  Controlling bias in adaptive data analysis using information theory.  In Arthur Gretton and Christian C. Robert, editors, _Proceedings of the 19th International Conference on Artificial Intelligence and Statistics_ , volume 51 of _Proceedings of Machine Learning Research_ , pages 1232–1240, Cadiz, Spain, 09–11 May 2016. PMLR.
  * Sauer (1972) Norbert Sauer.  On the density of families of sets.  _Journal of Combinatorial Theory, Series A_ , 13(1):145–147, 1972.  ISSN 0097-3165.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge University Press, 2014.
  * Shannon (1948) Claude E. Shannon.  The mathematical theory of communication.  _The Bell System Technical Journal_ , 27:379–423, July 1948\.
  * Shelah (1972) Saharon Shelah.  A combinatorial problem; stability and order for models and theories in infinitary languages.  _Pacific Journal of Mathematics_ , 41(1):247 – 261, 1972.
  * Şimşekli et al. (2020) Umut Şimşekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu.  Hausdorff dimension, heavy tails, and generalization in neural networks.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 5138–5151. Curran Associates, Inc., 2020.
  * Steinke and Zakynthinou (2020) Thomas Steinke and Lydia Zakynthinou.  Reasoning about generalization via conditional mutual information.  In Jacob Abernethy and Shivani Agarwal, editors, _Proceedings of Thirty Third Conference on Learning Theory_ , volume 125 of _Proceedings of Machine Learning Research_ , pages 3437–3452. PMLR, 09–12 Jul 2020.
  * Suzuki et al. (2020a) Taiji Suzuki, Hiroshi Abe, Tomoya Murata, Shingo Horiuchi, Kotaro Ito, Tokuma Wachi, So Hirai, Masatoshi Yukishima, and Tomoaki Nishimura.  Spectral pruning: Compressing deep neural networks via spectral analysis and its generalization error.  In _International Joint Conference on Artificial Intelligence_ , pages 2839–2846, 2020a.
  * Suzuki et al. (2020b) Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura.  Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network.  In _International Conference on Learning Representations_ , 2020b.
  * Vapnik (1998) Vladimir N. Vapnik.  _Statistical Learning Theory_.  Wiley-Interscience, 1998.
  * Vershynin (2018) Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Wu and Verdú (2010) Yihong Wu and Sergio Verdú.  Rényi information dimension: Fundamental limits of almost lossless analog compression.  _IEEE Transactions on Information Theory_ , 56(8):3721–3748, 2010.
  * Xu and Raginsky (2017) Aolin Xu and Maxim Raginsky.  Information-theoretic analysis of generalization capability of learning algorithms.  In _NeurIPS_ , 2017.
  * Zhang et al. (2017) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  In _International Conference on Learning Representations_ , 2017.

Appendices

The organization of the appendices is as follows.

  * •

In Appendix A, we introduce the notion of conditional compressibility. Using
this concept, we derive several bounds on the generalization performance that
recover (and for certain cases improve) some previous bounds by Steinke and
Zakynthinou (2020); Harutyunyan et al. (2021); Vapnik (1998).

  * •

In Appendix B, we discuss the Donsker-Varadhan’s inequality. The relation with
compressibility is shown and a variational representation of the expectation
of a random variable is presented.

  * •

In Appendix C, the tail bound on the arbitrary random variable (Theorem 4.1)
is discussed. In particular, a variational representation of the tail
probability is presented, which is a key lemma to derive this tail bound.

  * •

In Appendix D, extensions of Theorems 3.2, 3.4, and 3.10 are stated, in
addition to some concrete examples of Corollary 3.11.

  * •

Finally, in Appendix E, proofs of our results are presented.

##### Type of a sequence

Through the appendices, we use the notion of the _type_ (Cover and Thomas,
2006). Here, we give its definition. We say that two sequences
$x^{m},x^{\prime m}\in\mathcal{X}^{m}$ have the same type if their empirical
distributions are the same. The type of a sequence $x^{m}$ is its empirical
distribution and is denoted by $\mathcal{T}(x^{m})$. An $m$-type $Q_{m}$
refers to all sequences of length $m$ whose empirical distributions equal
$Q_{m}$. Note that for any $x\in\mathcal{X}$, $Q_{m}(x)=k/m$ where
$k\in\\{0,1,\ldots,m\\}$. For ease of notation, the type $Q_{m}(x)$ is simply
denoted by $Q(x)$ or $q(x)$, whenever $m$ is known from the context.

##  Appendix A Conditional Compressibility

In this section, we introduce conditional compressibility, using concepts from
Steinke and Zakynthinou (2020). Building based on this notion, we derive both
in expectation and tail bounds that recover and improve over some previous
results. Theorem A.3 recovers (and potentially improves over) (Steinke and
Zakynthinou, 2020, Theorem 1.2.1) and (Harutyunyan et al., 2021, Corollary 2).
Corollaries A.4 and A.8 recover the the in-expectation and tail bound results
when a learning algorithm has a bounded VC-dimension (Vapnik, 1998).

Through this section, assume $\mathfrak{Z}\in\mathcal{Z}^{n\times 2}$ be a
super-dataset of length $2n$, distributed according to
$P_{\mathfrak{Z}}=\mu^{\otimes 2n}$, containing the dataset
$S=\mathfrak{Z}_{\mathbf{K}}$ and a ghost dataset
$\bar{S}=\mathfrak{Z}_{\bar{\mathbf{K}}}$, where
$\mathfrak{Z}_{\mathbf{K}}\coloneq(\mathfrak{Z}_{1,K_{1}},\ldots,\mathfrak{Z}_{n,K_{n}})$
and $\mathbf{K}\coloneq(K_{1},\ldots,K_{n})$ and
$\bar{\mathbf{K}}\coloneq(\bar{K}_{1},\ldots,\bar{K}_{n})$ are vectors of
length $n$ such that each $K_{i}$ takes values uniformly over $\\{1,2\\}$
independent of $\left\\{K_{j}\colon j\neq i\right\\}$, and
$\bar{K}_{i}\coloneq\\{1,2\\}\setminus K_{i}$. Denote

$\displaystyle
f(\mathfrak{z},\mathbf{k},w)\coloneq\hat{\mathcal{L}}(\mathfrak{z}_{\bar{\mathbf{k}}},w)-\hat{\mathcal{L}}(\mathfrak{z}_{\mathbf{k}},w)=\frac{1}{n}\sum\nolimits_{j=1}^{n}(-1)^{k_{j}}\left(\ell(\mathfrak{z}_{j,1},w)-\ell(\mathfrak{z}_{j,2},w)\right).$
(19)

Let
$d_{m}\coloneq\mathcal{W}^{m}\times\hat{\mathcal{W}}^{m}\times\mathcal{Z}^{2nm}\times\\{1,2\\}^{nm}\to\mathbb{R}$
be a function, measuring a distortion between $m$ realizations of
$f(\mathfrak{z},\mathbf{k},w)$ and $f(\mathfrak{z},\mathbf{k},\hat{w})$. In
particular, we use the following distortion functions:

$\displaystyle\varphi_{m}(w^{m},\hat{w}^{m};\mathfrak{z}^{m},\mathbf{k}^{m})$
$\displaystyle\coloneq\min\limits_{j\in[m]}f(\mathfrak{z}_{j},\mathbf{k}_{j},w_{j})-\frac{1}{m}\sum\nolimits_{i=1}^{m}f(\mathfrak{z}_{i},\mathbf{k}_{i},\hat{w}_{i}),$
(20)
$\displaystyle\vartheta_{m}(w^{m},\hat{w}^{m};\mathfrak{z}^{m},\mathbf{k}^{m})$
$\displaystyle\coloneq\frac{1}{m}\sum\nolimits_{i=1}^{m}\left(f(\mathfrak{z}_{i},\mathbf{k}_{i},w_{i})-f(\mathfrak{z}_{i},\mathbf{k}_{i},\hat{w}_{i})\right),$
(21) $\displaystyle\xi_{m}(w^{m},\hat{w}^{m};\mathfrak{z}^{m},\mathbf{k}^{m})$
$\displaystyle\coloneq\frac{1}{m}\sum\nolimits_{i=1}^{m}\left(|f(\mathfrak{z}_{i},\mathbf{k}_{i},w_{i})|-|f(\mathfrak{z}_{i},\mathbf{k}_{i},\hat{w}_{i})|\right),$
(22)

where $\mathbf{k}_{i}=(k_{i,1},\ldots,k_{i,n})$. In general when
$\mathfrak{z}^{m}=(\mathfrak{z},\ldots,\mathfrak{z})$, the distortion
functions are denoted by
$d_{m}(w^{m},\hat{w}^{m};\mathfrak{z},\mathbf{k}^{m})$.

######  Definition A.1.

The learning algorithm $\mathcal{A}(S)$ is
$(R(\mathfrak{z}),\epsilon(\mathfrak{z});\left\\{d_{m}\right\\}_{m})$-conditionally
compressible for some $R(\mathfrak{z})\in\mathbb{R}^{+}$ and
$\epsilon(\mathfrak{z})\in\mathbb{R}$, if for any
$\mathfrak{z}\in\mathcal{Z}^{2\times n}$, there exists a sequence of
hypothesis books
$\left\\{\mathcal{H}_{m}(\mathfrak{z})\right\\}_{m\in\mathbb{N}}$,
$\mathcal{H}_{m}(\mathfrak{z})=\\{\mathbf{\hat{w}}_{j}(\mathfrak{z}),j\in[l_{m}(\mathfrak{z})]\\}\subseteq\mathcal{\hat{W}}^{m}$
such that $l_{m}(\mathfrak{z})\leq e^{mR(\mathfrak{z})}$ and

$\displaystyle\lim_{m\rightarrow\infty}\mathbb{P}_{(\mathbf{K},W|\mathfrak{z})^{\otimes
m}}\left(\min\limits_{j\in[l_{m}(\mathfrak{z})]}d_{m}(W^{m},\hat{\mathbf{w}}_{j}(\mathfrak{z});\mathfrak{z},\mathbf{K}^{m})>\epsilon(\mathfrak{z})\right)=0,$
(23)

where
$P_{\mathbf{K},W|\mathfrak{z}}=\frac{1}{2^{n}}P_{W|\mathfrak{z}_{\mathbf{K}}}$.

The learning algorithm is
$(R(\mathfrak{z}),\epsilon(\mathfrak{z}),\delta;\left\\{d_{m}\right\\}_{m})$\-
exponentially and conditionally compressible for some $\delta>0$, if in
addition to above conditions, the following also holds:

$\displaystyle\lim_{m\rightarrow\infty}\left[-\frac{1}{m}\log\left(\mathbb{P}_{(\mathbf{K},W|\mathfrak{z})^{\otimes
m}}\left(\min\limits_{j\in[l_{m}(\mathfrak{z})]}d_{m}(W^{m},\hat{\mathbf{w}}_{j}(\mathfrak{z});\mathfrak{z},\mathbf{K}^{m})>\epsilon(\mathfrak{z})\right)\right)\right]\geq\log(1/\delta).$
(24)

In other words, asymptotically the error probability is bounded by
$\delta^{m}$.

Similar to the unconditional part, we state in expectation and tail bounds.

###  A.1 Bounds on the expected value of the generalization gap

The first theorem is a bound on the expectation of the generalization
performance of the conditionally compressible algorithms.

######  Theorem A.2.

Consider a learning algorithm $\mathcal{A}(S)$ and a bounded loss function
$\ell(z,w)\in[0,1]$.

  * i.

If $\mathcal{A}(S)$ is
$(R(\mathfrak{z}),\epsilon(\mathfrak{z});\left\\{\vartheta_{m}\right\\}_{m})$-conditionally
compressible, then

$\displaystyle\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\leq\mathbb{E}_{\mathfrak{Z}}\left[\sqrt{\frac{2R(\mathfrak{Z})}{n}}+\epsilon(\mathfrak{Z})\right].$

  * ii.

If $\mathcal{A}(S)$ is
$(R(\mathfrak{z}),\epsilon(\mathfrak{z});\left\\{|\vartheta_{m}|\right\\}_{m})$-conditionally
compressible, then

$\displaystyle\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|\leq\mathbb{E}_{\mathfrak{Z}}\left[\sqrt{\frac{2R(\mathfrak{Z})}{n}}+\epsilon(\mathfrak{Z})\right].$

  * ii.

If $\mathcal{A}(S)$ is
$(R(\mathfrak{z}),\epsilon(\mathfrak{z});\left\\{\xi_{m}\right\\}_{m})$-conditionally
compressible, then

$\displaystyle\mathbb{E}\left[\left|\operatorname*{gen}(S,W)\right|\right]\leq\mathbb{E}_{\mathfrak{Z}}\left[\sqrt{\frac{2(R(\mathfrak{Z})+\log(2))}{n}}+\epsilon(\mathfrak{Z})\right].$

This theorem is proved in Appendix E.9. We use this result to derive a bound
on the generalization gap of an arbitrary learning algorithm, in the next
theorem. This theorem can be derived from (Steinke and Zakynthinou, 2020,
Theorem 1.2) in the same manner as we have proved Theorem 3.4 using (Xu and
Raginsky, 2017, Theorems 1,4). It can be alternatively derived using Theorem
A.2 and by bounding the conditional compressibility parameters of an arbitrary
learning algorithm, similar to the proof of Theorem 3.3. We omit the proof, as
it is similar to the proofs of Theorems 3.3 and 3.4.

######  Theorem A.3.

Suppose the algorithm $\mathcal{A}(S)=W$ induces $P_{S,W}$ and the loss
function $\ell(z,w)$ is bounded in the range $[0,1]$. Consider any auxiliary
random variable $U$161616Here, $U$ represents the stochasticity of the
algorithm. Note that $U$ being a constant is always a valid choice. For
further discussions, refer to Appendix D.2. defined by the conditional
distribution $P_{U|S,W}$ and satisfying
$P_{U,S,W}=P_{U}P_{S}P_{W|U,S}$171717Note that
$P_{U,\mathfrak{Z},\mathbf{K},W}=P_{\mathfrak{Z}}P_{U}P_{W|U,\mathfrak{Z}_{\mathbf{K}}}$..
Then, for any $\epsilon\in\mathbb{R}$

  * i.

$\displaystyle\left|\mathbb{E}_{S,W}\left[\operatorname*{gen}(S,W)\right]\right|\leq$
$\displaystyle\mathbb{E}_{\mathfrak{Z},U}\left[\sqrt{\frac{2R_{E,\mathfrak{Z},U}(\epsilon)}{n}}+\epsilon\right],$
$\displaystyle\mathbb{E}_{S,W}\left[\operatorname*{gen}(S,W)\right]\leq$
$\displaystyle\mathbb{E}_{\mathfrak{Z},U}\left[\sqrt{\frac{2R^{\prime}_{E,\mathfrak{Z},U}(\epsilon)}{n}}+\epsilon\right],$
$\displaystyle\mathbb{E}_{S,W}\left[\left|\operatorname*{gen}(S,W)\right|\right]\leq$
$\displaystyle\mathbb{E}_{\mathfrak{Z},U}\left[\sqrt{\frac{2(R^{\prime\prime}_{E,\mathfrak{Z},U}(\epsilon)+\log(2))}{n}}+\epsilon\right],$
(25)

where

$\displaystyle R_{E,\mathfrak{z},u}(\epsilon)=$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|\mathfrak{z}_{\mathbf{K}},u}\end{subarray}}I(\mathbf{K};\hat{W}|\mathfrak{z},u),\quad\text{such
that}\quad\left|\mathbb{E}\left[f(\mathfrak{z},\mathbf{K},W)-f(\mathfrak{z},\mathbf{K},\hat{W})\right]\right|\leq\epsilon,$
$\displaystyle R^{\prime}_{E,\mathfrak{z},u}(\epsilon)=$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|\mathfrak{z}_{\mathbf{K}},u}\end{subarray}}I(\mathbf{K};\hat{W}|\mathfrak{z},u),\quad\text{such
that}\quad\mathbb{E}\left[f(\mathfrak{z},\mathbf{K},W)-f(\mathfrak{z},\mathbf{K},\hat{W})\right]\leq\epsilon,$
$\displaystyle R^{\prime\prime}_{E,\mathfrak{z},u}(\epsilon)=$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|\mathfrak{z}_{\mathbf{K}},u}\end{subarray}}I(\mathbf{K};\hat{W}|\mathfrak{z},u),\quad\text{such
that}\quad\mathbb{E}\left[|f(\mathfrak{z},\mathbf{K},W)|-|f(\mathfrak{z},\mathbf{K},\hat{W})|\right]\leq\epsilon.$
(26)

The expectations are with respect to
$P_{\mathbf{K}}P_{W|\mathfrak{z}_{\mathbf{K}},u}$ and
$P_{\mathbf{K}}P_{\hat{W}|\mathfrak{z}_{\mathbf{K}},u}$.

  * ii.

$\displaystyle\left|\mathbb{E}_{S,W}\left[\operatorname*{gen}(S,W)\right]\right|$
$\displaystyle\leq\frac{1}{n}\sum\limits_{i=1}^{n}\mathbb{E}_{\mathfrak{Z},U}\left[\sqrt{2R_{E,\mathfrak{Z},U,i}(\epsilon)}+\epsilon\right],$
$\displaystyle\mathbb{E}_{S,W}\left[\operatorname*{gen}(S,W)\right]$
$\displaystyle\leq\frac{1}{n}\sum\limits_{i=1}^{n}\mathbb{E}_{\mathfrak{Z},U}\left[\sqrt{2R^{\prime}_{E,\mathfrak{Z},U,i}(\epsilon)}+\epsilon\right],$
$\displaystyle\mathbb{E}_{S,W}\left[\left|\operatorname*{gen}(S,W)\right|\right]$
$\displaystyle\leq\frac{1}{n}\sum\limits_{i=1}^{n}\mathbb{E}_{\mathfrak{Z},U}\left[\sqrt{2(R^{\prime\prime}_{E,\mathfrak{Z},U,i}(\epsilon)+\log(2))}+\epsilon\right],$
(27)

where

$\displaystyle R_{E,\mathfrak{z},u,i}(\epsilon)=$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|\mathfrak{z}_{K_{i}},u}\end{subarray}}I(K_{i};\hat{W}|\mathfrak{z}_{i},u),\quad\text{such
that}\quad\left|\mathbb{E}\left[f(\mathfrak{z}_{i},K_{i},W)-f(\mathfrak{z}_{i},K_{i},\hat{W})\right]\right|\leq\epsilon,$
$\displaystyle R^{\prime}_{E,\mathfrak{z},u,i}(\epsilon)=$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|\mathfrak{z}_{K_{i}},u}\end{subarray}}I(K_{i};\hat{W}|\mathfrak{z}_{i},u),\quad\text{such
that}\quad\mathbb{E}\left[f(\mathfrak{z}_{i},K_{i},W)-f(\mathfrak{z}_{i},K_{i},\hat{W})\right]\leq\epsilon,$
$\displaystyle R^{\prime\prime}_{E,\mathfrak{z},u,i}(\epsilon)=$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|\mathfrak{z}_{K_{i}},u}\end{subarray}}I(K_{i};\hat{W}|\mathfrak{z}_{i},u),\quad\text{such
that}\quad\mathbb{E}\left[|f(\mathfrak{z}_{i},K_{i},W)|-|f(\mathfrak{z}_{i},K_{i},\hat{W})|\right]\leq\epsilon,$
(28)

where
$f(\mathfrak{z}_{i},K_{i},w)\coloneq(-1)^{k_{i}}\left(\ell(\mathfrak{z}_{i,1},w)-\ell(\mathfrak{z}_{i,2},w)\right)$
and the expectations are with respect to
$P_{K_{i}}P_{W|\mathfrak{z}_{i,k_{i}},u}$ and
$P_{K_{i}}P_{\hat{W}|\mathfrak{z}_{i,K_{i}},u}$.

The above bound trivially recovers (Steinke and Zakynthinou, 2020, Theorem
1.2.1) and (Harutyunyan et al., 2021, Corollary 2) by letting
$U=\text{Constant}$, $\epsilon=0$, and $\hat{W}=W$.

Next, we show that we can recover the bound in terms of VC-dimension using the
above result.

######  Corollary A.4.

If a learning algorithm has the VC-dimension $d$ and the loss function
$\ell(z,w)\in[0,1]$, then

$\displaystyle\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|$
$\displaystyle\leq\sqrt{\frac{2d\log(2en/d)}{n}},~{}~{}~{}~{}\mathbb{E}\left[\left|\operatorname*{gen}(S,W)\right|\right]\leq\sqrt{\frac{2(d\log(2en/d)+\log(2))}{n}}.$

The corollary is proved in Appendix E.10.

###  A.2 Tail bounds on the generalization gap

In this section, we propose tail bounds on the generalization performance
using exponentially and conditionally compressibility.

######  Theorem A.5.

If the learning algorithm $\mathcal{A}(S)$ is
$(R(\mathfrak{z}),\epsilon(\mathfrak{z}),\delta/2;\left\\{d_{\mathfrak{z},p}\right\\}_{m})$\-
exponentially and conditionally compressible, then with probability at least
$1-\delta$ for the bounded loss function $\ell(z,w)\in[0,1]$,

$\displaystyle\operatorname*{gen}(S,W)\leq\sup\limits_{\mathfrak{z}\in\mathcal{Z}^{2n}}\left[\sqrt{\frac{2(R(\mathfrak{z})+\log\left(2/\delta\right))}{n}}+\epsilon(\mathfrak{z})\right]+\sqrt{\frac{\log(2/\delta)}{n}}.$

The theorem is proved in Appendix E.11.

Now, we establish a tail bound on the generalization performance of the
arbitrary learning algorithm. For a given distribution $Q_{\mathbf{k},W}$ over
$\\{1,2\\}^{n}\times\mathcal{W}$, let

$\displaystyle
d_{Q_{\mathbf{K},W}}(\hat{w};\mathfrak{z},\mathbf{k})\coloneq\inf_{\begin{subarray}{c}(\mathbf{k}^{\prime},w^{\prime})\in\operatorname{supp}(Q_{\mathbf{K},W})\end{subarray}}\left[f(\mathfrak{z},\mathbf{k}^{\prime},w^{\prime})\right]-f(\mathfrak{z},\mathbf{k},\hat{w}).$
(29)

Moreover, for a set $\mathcal{U}$181818As mentioned before, $U$ represents the
stochasticity of the algorithm. For further discussions, refer to Appendix
D.2. and a distribution $Q$ defined over
$\\{1,2\\}^{n}\times\mathcal{W}\times\mathcal{U}$, define

$\displaystyle\mathfrak{RD}^{\dagger}(\epsilon;Q|\mathfrak{z})\coloneq$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|\mathfrak{z}_{\mathbf{K}},U}:\\\
\mathbb{E}\left[d_{Q_{\mathbf{K},W}}(\hat{W};\mathfrak{z},\mathbf{K})\right]\leq\epsilon\end{subarray}}I(\mathbf{K};\hat{W}|U)$
$\displaystyle\leq$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|\mathfrak{z}_{\mathbf{K}},U}:\\\
\mathbb{E}\left[f(\mathfrak{z},\mathbf{K},W)-f(\mathfrak{z},\mathbf{K},\hat{W})\right]\leq\epsilon\end{subarray}}I(\mathbf{K};\hat{W}|U)$
(30) $\displaystyle=$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|\mathfrak{z}_{\mathbf{K}},U}:\\\
\mathbb{E}\left[\operatorname*{gen}(\mathfrak{z}_{\mathbf{K}},W)-\operatorname*{gen}(\mathfrak{z}_{\mathbf{K}},\hat{W})\right]\leq\epsilon\end{subarray}}I(\mathbf{K};\hat{W}|U),$
(31)

where $Q_{\mathbf{K},W}$ is the marginal distribution of $(\mathbf{K},W)$, the
infimum is over all conditional probability distributions (Markov kernels)
$P_{\hat{W}|S,U}:\hat{\mathcal{W}}\times\mathcal{S}\times\mathcal{U}\to\mathbb{R}^{+}$,
the expectation and the mutual information are with respect to joint
distributions $Q$ and $Q_{U,\mathbf{K}}\times
P_{\hat{W}|\mathfrak{z}_{\mathbf{K}},U}$, where $Q_{U,\mathbf{K}}$ is the
marginal distribution of $(U,\mathbf{K})$ . Then, we have the below tail
bound, proved in Appendix E.12.

######  Theorem A.6.

Suppose the algorithm $\mathcal{A}(S)=W$ induces $P_{S,W}$ and $\ell(z,w)$ is
bounded in the range $[0,1]$. Consider any auxiliary random variable $U$
defined by the conditional distribution $P_{U|S,W}$ and satisfying
$P_{U,S,W}=P_{U}P_{S}P_{W|U,S}$191919Note that
$P_{\mathfrak{Z},\mathbf{K},W,U}=P_{\mathfrak{Z}}P_{\mathbf{K}}P_{U}P_{W|U,\mathfrak{Z}_{\mathbf{K}}}=\frac{1}{2^{n}}\mu^{\otimes
2n}P_{U}P_{W|U,\mathfrak{Z}_{\mathbf{K}}}$.. Then, for any values of
$\\{\epsilon(\mathfrak{z})\\}_{\mathfrak{z}}$ and $\delta\geq 0$, with
probability at least $1-\delta$

$\displaystyle\operatorname*{gen}(S,W)\leq\sup\limits_{\mathfrak{z}}\left[\sqrt{\frac{2(R(\mathfrak{z},\delta,\epsilon)+\log\left(2/\delta\right))}{n}}+\epsilon(\mathfrak{z})\right]+\sqrt{\frac{\log(2/\delta)}{n}}.$
(32)

where

$\displaystyle
R(\mathfrak{z},\delta,\epsilon)\coloneq\sup\limits_{\begin{subarray}{c}Q\colon
D_{KL}(Q\|P_{\mathbf{K},W,U|\mathfrak{z}})\leq\log\left(2/\delta\right)\end{subarray}}\mathfrak{RD}^{\dagger}(\epsilon(\mathfrak{z});Q|\mathfrak{z}),$
(33)

where the supremum is over all possible distributions $Q$ over
$\\{1,2\\}^{n}\times\mathcal{W}\times\mathcal{U}$.

######  Remark A.7.

By considering the exponentially and conditionally compressibility with
respect to $\mathbb{P}_{(\mathbf{K},W,\mathfrak{Z})^{\otimes m}}$ rather than
$\mathbb{P}_{(\mathbf{K},W|\mathfrak{z})^{\otimes m}}$ in (24), the following
result also can be achieved with the assumptions of Theorem A.6. For any
$\epsilon$ and $\delta\geq 0$, with probability at least $1-\delta$

$\displaystyle\operatorname*{gen}(S,W)\leq\sqrt{\frac{2(R(\delta,\epsilon)+\log\left(2/\delta\right))}{n}}+\epsilon+\sqrt{\frac{\log(2/\delta)}{n}}.$
(34)

where

$\displaystyle
R(\delta,\epsilon)\coloneq\sup\limits_{\begin{subarray}{c}Q\colon
D_{KL}(Q\|P_{K,W,\mathfrak{Z},U})\leq\log\left(2/\delta\right)\end{subarray}}\mathbb{E}_{\mathfrak{Z}\sim
Q_{\mathfrak{Z}}}\left[\mathfrak{RD}^{\dagger}(\epsilon;Q_{\mathbf{K},W,U|\mathfrak{Z}}|\mathfrak{Z})\right],$
(35)

where the supremum is over all possible distributions $Q$ over
$\\{1,2\\}^{n}\times\mathcal{W}\times\mathcal{Z}^{2n}\times\mathcal{U}$,
$Q_{\mathbf{K},W,U|\mathfrak{Z}}$ is the conditional distribution of
$(\mathbf{K},W,U)$ given $\mathfrak{Z}$, and $Q_{\mathfrak{Z}}$ is the
marginal distribution of $\mathfrak{Z}$.

Finally, we use Theorem A.6 to recover the generalization bound for the
algorithms having a bounded VC-dimension Vapnik (1998).

######  Corollary A.8.

If a learning algorithm has VC-dimension $d$ and the loss function
$\ell(z,w)\in[0,1]$, then with probability at least $1-\delta$

$\displaystyle\operatorname*{gen}(S,W)$
$\displaystyle\leq\sqrt{\frac{2(d\log(2en/d)+\log(2/\delta))}{n}}+\sqrt{\frac{\log(2/\delta)}{n}}.$

The corollary is proved in Appendix E.13.

##  Appendix B On the Donsker-Varadhan’s Inequality

The Donsker-Varadhan’s identity implies that for arbitrary distributions
$p(x)$ and $q(x)$ on a set $\mathcal{X}$ and for any arbitrary function
$\Phi:\mathcal{X}\to\mathbb{R}$ we have

$\displaystyle D_{KL}(q\|p)\geq\mathbb{E}_{X\sim
q}[\Phi(X)]-\log\left(\mathbb{E}_{X\sim p}\left[e^{\Phi(X)}\right]\right).$
(36)

In this appendix, we first show that this inequality can be proved using a
compressibility approach for a finite set $\mathcal{X}$. Then, we also derive
a lemma based on (36) that is used to derive a tail bound on an arbitrary
random variable.

###  B.1 Donsker-Varadhan’s inequality via compression

Take some arbitrary function $\Phi:\mathcal{X}\to\mathbb{R}$. Generate
$2^{mR}$ sequences

$X^{m}(1),X^{m}(2),\ldots,X^{m}(2^{mR}),$

where $X^{m}(i)=(X_{1}(i),\ldots,X_{m}(i))$, in an i.i.d. fashion from $p(x)$,
_i.e._ each $X_{j}(i)\sim p$ for $i\in[2^{mR}],j\in[m]$, independent of other
instances. Consider the expression

$\mathbb{E}\left[\max_{k}\sum_{i=1}^{m}\Phi(X_{i}(k))\right].$

On the one hand,

$e^{\mathbb{E}\left[\max_{k}\sum_{i}\Phi(X_{i}(k))\right]}\leq\mathbb{E}\left[e^{\max_{k}\sum_{i}\Phi(X_{i}(k))}\right]\leq\mathbb{E}\left[\sum_{k}e^{\sum_{i}\Phi(X_{i}(k))}\right]=2^{mR}\left(\mathbb{E}_{X\sim
p}\left[e^{\Phi(X)}\right]\right)^{m}.$

Therefore,

$\displaystyle\mathbb{E}\left[\max_{k}\sum_{i}\Phi(X_{i}(k))\right]\leq
mR+m\log\left(\mathbb{E}_{X\sim p}\left[e^{\Phi(X)}\right]\right).$ (37)

On the other hand, let $\gamma_{m}$ be the probability that at least one of
the sequences $X^{m}(k)$ for some $k$ will have type $q(x)$. It is known that
(for example by using Cover and Thomas (2006, Theorem 11.1.4))
$\gamma_{m}\rightarrow 1$ as $m$ tends to infinity if $R>D_{KL}(q\|p)$. Under
the event that the sequence $X^{m}(k)$ has type $q(x)$,
$\sum_{i}\Phi(X_{i}(k))$ equals $m\mathbb{E}_{X\sim q}[\Phi(X)]$. Thus,

$\displaystyle\mathbb{E}\left[\max_{k}\sum_{i}\Phi(X_{i}(k))\right]\geq
m\gamma_{m}\mathbb{E}_{X\sim q}[\Phi(X)]+m(1-\gamma_{m})\min_{x}\Phi(x).$ (38)

From (37) and (38) and by letting $m$ tend to infinity, we obtain

$D_{KL}(q\|p)+\log\left(\mathbb{E}_{X\sim
p}\left[e^{\Phi(X)}\right]\right)\geq\mathbb{E}_{X\sim q}[\Phi(X)].$

This yields the desired inequality.

###  B.2 Variational representation of $\mathbb{E}[X]$

In this subsection, we state a variational lemma on $\mathbb{E}[X]$, used in
proof of Theorem 4.1. The lemma is proved in Appendix E.14, by using (36).

######  Lemma B.1.

For every distribution $\nu$, we have

$\displaystyle\mathbb{E}_{\nu}[X]=\frac{1}{\lambda}\inf_{\mu}\left[D_{KL}(\nu\|\mu)+\log\mathbb{E}_{\mu}\left[e^{\lambda
X}\right]\right].$ (39)

##  Appendix C Tail Bound on an Arbitrary Random Variable

The key to the proof of the tail bound in Theorem 4.1 is a variational
representation of the tail probability, stated in the next lemma.

######  Lemma C.1.

Let $\epsilon$ be an arbitrary real number. For any arbitrary distribution
$\nu_{X}$ on $\mathbb{R}$, let $\mathcal{P}(\nu_{X})$ denote the set of
distributions $p_{\hat{X}}$ on $\mathbb{R}$ for which

$\left[\inf_{x\in\operatorname{supp}(\nu_{X})}x\right]-\mathbb{E}\left[\hat{X}\right]\leq\epsilon.$

Let $X\sim\mu_{X}$ where $\mu_{X}$ is an arbitrary distribution on the sample
space $\mathcal{X}\subseteq\mathbb{R}$. Then, for any $\Delta\in\mathbb{R}$ we
have202020For $a\in\mathbb{R}$, $[a]_{+}\coloneq\max(0,a)$.

$\displaystyle\log\mathbb{P}_{X\sim\mu_{X}}\left(X\geq\Delta\right)$
$\displaystyle=\sup_{\nu_{X}\ll\mu_{X}}~{}~{}\inf_{p_{\hat{X}}\in\mathcal{P}(\nu_{X}),~{}\lambda\geq
0}\left\\{-D_{KL}(\nu_{X}\|\mu_{X})-\lambda\bigg{[}\Delta-\epsilon-\mathbb{E}_{p}[\hat{X}]\bigg{]}_{+}\right\\}.$

We give two proofs for this lemma. The first proof is provided in Appendix
E.15.1. We give also an alternative proof (in the inequality form) when
$\mathcal{X}$ and $\mathcal{S}$ are finite sets. This proof illustrates the
connections between the tail bound and compression. To this end, consider the
distortion function $\rho$ defined in Definition 4.2. Note that $\varphi_{m}$
can be expressed in terms of this distortion function, _i.e._
$\varphi_{m}(w^{m},\hat{w}^{m};s^{m})=\rho\left(\left\\{\operatorname*{gen}(s_{i},w_{i})\right\\}_{i\in[m]},\left\\{\operatorname*{gen}(s_{i},\hat{w}_{i})\right\\}_{i\in[m]}\right)$.
To establish the tail bound, first we upper bound it in terms of the tail of
some quantizations of $X^{m}$ and the probability of covering $X^{m}$ by this
quanitzation points. This is exactly the bound established in Theorem 4.3.
Indeed, Theorem 4.3 shows the connection between the tail bound and
compression. Note that Theorem 4.3 also holds if the conditions
$\geq\Delta-\epsilon$ and $>\epsilon$ are replaced by conditions
$>\Delta-\epsilon$ and $\geq\epsilon$ respectively in (18). The rest of proof
applies some information-theoretic techniques, as detailed in Appendix E.15.2.

##  Appendix D Other Results

In this section, we state some further obtained results.

###  D.1 Extension of the in expectation bound

In a similar manner as (8), let
$\xi_{m}(w^{m},\hat{w}^{m};s^{m})\coloneq\frac{1}{m}\sum\nolimits_{i=1}^{m}\left(|\operatorname*{gen}(s_{i},w_{i})|-|\operatorname*{gen}(s_{i},\hat{w}_{i})|\right)$.
Here, we state the extended version of Theorem 3.2.

###### Theorem 3.2

Consider a learning algorithm $\mathcal{A}(S)$ and suppose that
$\mathbb{E}_{S,W}[|\operatorname*{gen}(S,W)|]<\infty$ and for all
$w\in\mathcal{W}$, $\ell(Z,w)$ is $\sigma$-subgaussian.

  * i.

If $\mathcal{A}(S)$ is
$(R,\epsilon;\left\\{\vartheta_{m}\right\\}_{m})$-compressible, then
$\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\leq\sqrt{2\sigma^{2}R/n}+\epsilon$.

  * ii.

If $\mathcal{A}(S)$ is
$(R,\epsilon;\left\\{|\vartheta_{m}|\right\\}_{m})$-compressible, then
$\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|\leq\sqrt{2\sigma^{2}R/n}+\epsilon$.

  * iii.

If $\mathcal{A}(S)$ is
$(R,\epsilon;\left\\{\xi_{m}\right\\}_{m})$-compressible, then
$\mathbb{E}\left[\,|\operatorname*{gen}(S,W)|\,\right]\leq\sqrt{2\sigma^{2}(R+\log(2))/n}+\epsilon$.

All above expectations are with respect to $P_{S,W}$.

Next, we state the extended version of Theorem 3.4.

###### Theorem 3.4

Assume that the algorithm $\mathcal{A}(S)=W$ induces $P_{S,W}$ and for all
$w\in\mathcal{W}$, $\ell(Z,w)$ is $\sigma$-subgaussian. Then, for any
$\epsilon\in\mathbb{R}$,

$\displaystyle\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|$
$\displaystyle\leq\sqrt{\frac{2\sigma^{2}R_{E}(\epsilon)}{n}}+\epsilon,$
$\displaystyle\mathbb{E}\left[\operatorname*{gen}(S,W)\right]$
$\displaystyle\leq\sqrt{\frac{2\sigma^{2}R^{\prime}_{E}(\epsilon)}{n}}+\epsilon,$
$\displaystyle\mathbb{E}\left[\,|\operatorname*{gen}(S,W)|\,\right]$
$\displaystyle\leq\sqrt{\frac{2\sigma^{2}(R^{\prime\prime}_{E}(\epsilon)+\log(2))}{n}}+\epsilon,$
(40)

where

$\displaystyle R_{E}(\epsilon)$
$\displaystyle=\inf\limits_{P_{\hat{W}|S}}I(S;\hat{W}),\quad\text{such
that}\quad\left|\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]\right|\leq\epsilon,$
$\displaystyle R^{\prime}_{E}(\epsilon)$
$\displaystyle=\inf\limits_{P_{\hat{W}|S}}I(S;\hat{W}),\quad\text{such
that}\quad\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]\leq\epsilon,$
$\displaystyle R^{\prime\prime}_{E}(\epsilon)$
$\displaystyle=\inf\limits_{P_{\hat{W}|S}}I(S;\hat{W}),\quad\text{such
that}\quad\mathbb{E}\left[|\operatorname*{gen}(S,W)|-|\operatorname*{gen}(S,\hat{W})|\right]\leq\epsilon.$
(41)

All expectations in above are with respect to $P_{S,W}$ and $P_{S}\times
P_{\hat{W}|S}$.

This theorem can be trivially extended to the case where we have access to an
internal randomness $U$ of the algorithm, as defined in Appendix D.2. For
example, by using
$\mathbb{E}\left[\operatorname*{gen}(S,W)\right]=\mathbb{E}_{U}\mathbb{E}_{S,W|U}\left[\operatorname*{gen}(S,W)\right]$,
it can be shown that
$\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\leq\mathbb{E}_{U}[\sqrt{2\sigma^{2}R_{E,U}/n}]+\epsilon$,
where $R_{E,u}(\epsilon)\coloneq\inf I(S;\hat{W}|U=u)$, in which the infimum
is over all Markov kernels $P_{\hat{W}|S,u}$ such that
$\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]\leq\epsilon$.

In the following, Theorem 3.4 is extended similarly to Bu et al. (2020). The
proof trivially follows from the relation
$\mathbb{E}\left[\operatorname*{gen}(S,W)\right]=\frac{1}{n}\sum\limits_{i=1}^{n}\mathbb{E}\left[\operatorname*{gen}(\\{Z_{i}\\},W)\right]$
and Theorem 3.4, where
$\mathbb{E}\left[\operatorname*{gen}(\\{z_{i}\\},w)\right]=\mathcal{L}(w)-\ell(z_{i},w)$.

######  Theorem D.1.

Suppose the algorithm $\mathcal{A}(S)=W$ induces $P_{S,W}$ and for all
$w\in\mathcal{W}$, $\ell(Z,w)$ is $\sigma$-subgaussian. Then, for any
$\epsilon\in\mathbb{R}$,

$\displaystyle\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|$
$\displaystyle\leq\frac{1}{n}\sum\limits_{i=1}^{n}\left[\sqrt{2\sigma^{2}R_{E,i}(\epsilon)}\right]+\epsilon,$
(42) $\displaystyle\mathbb{E}\left[\operatorname*{gen}(S,W)\right]$
$\displaystyle\leq\frac{1}{n}\sum\limits_{i=1}^{n}\left[\sqrt{2\sigma^{2}R^{\prime}_{E,i}(\epsilon)}\right]+\epsilon,$
(43) $\displaystyle\mathbb{E}\left[\,|\operatorname*{gen}(S,W)|\,\right]$
$\displaystyle\leq\frac{1}{n}\sum\limits_{i=1}^{n}\left[\sqrt{2\sigma^{2}(R^{\prime\prime}_{E,i}(\epsilon)+\log(2))}\right]+\epsilon,$
(44)

where the expectation is with respect to $P_{S,W}$ and

$\displaystyle R_{E,i}(\epsilon)=$
$\displaystyle\inf\limits_{P_{\hat{W}|Z_{i}}}I(Z_{i};\hat{W}),\quad\text{such
that}\quad\left|\mathbb{E}\left[\operatorname*{gen}(\\{Z_{i}\\},W)-\operatorname*{gen}(\\{Z_{i}\\},\hat{W})\right]\right|\leq\epsilon,$
(45) $\displaystyle R^{\prime}_{E,i}(\epsilon)=$
$\displaystyle\inf\limits_{P_{\hat{W}|Z_{i}}}I(Z_{i};\hat{W}),\quad\text{such
that}\quad\mathbb{E}\left[\operatorname*{gen}(\\{Z_{i}\\},W)-\operatorname*{gen}(\\{Z_{i}\\},\hat{W})\right]\leq\epsilon,$
(46) $\displaystyle R^{\prime\prime}_{E,i}(\epsilon)=$
$\displaystyle\inf\limits_{P_{\hat{W}|Z_{i}}}I(Z_{i};\hat{W}),\quad\text{such
that}\quad\mathbb{E}\left[|\operatorname*{gen}(\\{Z_{i}\\},W)|-|\operatorname*{gen}(\\{Z_{i}\\},\hat{W})|\right]\leq\epsilon,$
(47)

where
$\mathbb{E}\left[\operatorname*{gen}(\\{z_{i}\\},w)\right]=\mathcal{L}(w)-\ell(z_{i},w)$
and the expectations are with respect to $P_{Z_{i},W}$ and $P_{Z_{i}}\times
P_{\hat{W}|Z_{i}}$.

Letting $\epsilon=0$ and $\hat{W}=W$, this theorem recovers (and potentially
improves over) (Bu et al., 2020, Proposition 1).

###  D.2 Extension of the tail bound

It has been already shown by Harutyunyan et al. (2021) that taking into
account the stochasticity of the algorithm could yield tighter bounds on the
expectation of the generalization gap. Here, we apply a similar idea for the
tail bound. To this end, we represent partial or full stochasticity of the
algorithm which is independent of the dataset by $U\in\mathcal{U}$. This means
that the hypothesis is chosen according to $P_{W|S,U}$ (deterministically or
randomly). Having this stochasticity available, we can make our compression
more efficient, by letting the hypothesis books in Definition 3.1 depend on
$U$ as well, _i.e._ for each arbitrary distribution $Q$ defined over
$\mathcal{U}$, we choose a sequence of hypothesis books
$\mathcal{H}_{m}(Q)=\\{\mathbf{\hat{w}}_{j}(Q),j\in[l_{m}(Q)]\\}\subseteq\mathcal{\hat{W}}^{m}$,
such that $l_{m}(Q)\leq e^{mR(Q)}$ and

$\displaystyle\lim_{m\rightarrow\infty}-\frac{1}{m}\log\left(\mathbb{P}_{(U,S,W)^{\otimes
m}}\left(\min\limits_{j\in[l_{m}(\hat{P}_{U^{m}})]}\varphi_{m}\left(W^{m},\hat{\mathbf{w}}_{j}(\hat{P}_{U^{m}});S^{m}\right)>\epsilon\right)\right)\geq\log(1/\delta),$
(48)

where $\hat{P}_{U^{m}}$ is the empirical distribution of $U^{m}$. Then, it can
be shown that $R$ in Theorem 3.9 can be replaced by $\sup_{Q}R(Q)$, where the
supremum is over all $Q$ such that $D_{KL}(Q\|P_{U})\leq\log(1/\delta)$.

In order to define the extended version of Theorem 3.10, we need to define an
extended definition of $\mathfrak{RD}^{*}(\epsilon;Q)$, that takes $U$ also
into account. For a distribution $Q$ defined over
$\mathcal{S}\times\mathcal{W}\times\mathcal{U}$, let

$\displaystyle\mathfrak{RD}^{*}(\epsilon;Q)\coloneq$
$\displaystyle\inf\limits_{\begin{subarray}{c}P_{\hat{W}|S,U}:\\\
\mathbb{E}\left[d_{Q_{S,W}}(\hat{W};S)\right]\leq\epsilon\end{subarray}}I(S;\hat{W}|U)\leq\inf\limits_{\begin{subarray}{c}P_{\hat{W}|S,U}:\\\
\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]\leq\epsilon\end{subarray}}I(S;\hat{W}|U),$
(49)

where $Q_{S,W}$ is the marginal distribution of $(S,W)$, the infimum is over
all Markov kernels
$P_{\hat{W}|S,U}:\hat{\mathcal{W}}\times\mathcal{S}\times\mathcal{U}\to\mathbb{R}^{+}$,
the expectation and the mutual information are with respect to joint
distributions $Q$ and $Q_{S,U}\times P_{\hat{W}|S,U}$, where $Q_{S,U}$ is the
marginal distribution of $(S,U)$. Note that letting $U$ being a constant, (49)
will be reduced to (14). Now, we state an extended version of Theorem 3.10,
proved in Appendix E.6.

###### Theorem 3.10

Suppose that the algorithm $\mathcal{A}(S)=W$ induces $P_{S,W}$ and for all
$w\in\mathcal{W}$, $\ell(Z,w)$ is $\sigma$-subgaussian. Consider any auxiliary
random variable $U$ defined by $P_{U|S,W}$ and satisfying
$P_{U,S,W}=P_{U}P_{S}P_{W|U,S}$. Then, for every $\epsilon\in\mathbb{R}$ and
$\delta\geq 0$, with probability at least $1-\delta$,

$\displaystyle\operatorname*{gen}(S,W)\leq\sqrt{\frac{2\sigma^{2}(R_{p}(\delta,\epsilon)+\log\left(1/\delta\right))}{n}}+\epsilon,~{}R_{p}(\delta,\epsilon)\coloneq\sup\limits_{\begin{subarray}{c}Q\colon
D_{KL}(Q\|P_{S,W,U})\leq\log\left(1/\delta\right)\end{subarray}}\mathfrak{RD}^{*}(\epsilon;Q),$

where the supremum is over all possible distributions $Q$ over
$\mathcal{S}\times\mathcal{W}\times\mathcal{U}$.

Note that the above bound holds for any $U$ that satisfies the assumptions of
the theorem and $U$ being a constant is always valid choice. By the choice of
$U=\text{Constant}$, this extended version becomes the same as the original
one, stated in Section 3.3.

As a special case, when $S$ and $W$ are independent, the above theorem, by
choosing $U=W$, results that with probability $1-\delta$,
$\operatorname*{gen}(S,W)\leq\sqrt{2\sigma^{2}\log(1/\delta)/n}$. This bound
is equal to the one obtainable by direct application of Hoeffding’s
inequality. However, we may not be able to achieve this bound using Theorem
3.10 with constant $U$. Since, while for example $I(S;W)=0$ under $P_{S,W}$,
it may not be equal to zero under distribution $Q$, where
$D_{KL}(Q\|P_{S,W})\leq\log(1/\delta)$; as under distribution $Q$, random
variables $S$ and $W$ might be (weakly) dependent.

###  D.3 Examples for Lipschitz loss

In the following, we show some consequences of Corollary 3.11.

######  Corollary D.2.

Suppose that the loss function $\ell(Z,w)$ is $\sigma$-subgaussian for any
$w\in\mathcal{W}$.

  * i.

[$\varepsilon$-net covering] Let $\mathcal{W}=\mathbb{R}^{d}$ and let $W$ with
probability one take value in the $d$-dimensional ball
$\mathcal{V}_{d}=\\{w\in\mathbb{R}^{d}\colon\|w\|\leq r_{0}\\}$ and suppose
that for every $z,w,\hat{w}$,
$|\ell(z,w)-\ell(z,\hat{w})|\leq\mathfrak{L}\|w-\hat{w}\|$. Then, for every
$\delta>0$, with probability at least $1-\delta$,

$\displaystyle\operatorname*{gen}(S,W)\leq\min\limits_{\epsilon\geq
0}\left[\sqrt{\frac{2\sigma^{2}(d\log(2r_{0}/\epsilon)+\log(1/\delta))}{n}}+2\mathfrak{L}\epsilon\right].$

In particular, for $n\geq 16$, with probability at least $1-e^{-d/2}$, we have
$\operatorname*{gen}(S,W)\leq(4r_{0}\mathfrak{L}+\sigma\sqrt{d})\sqrt{\log(n)/n}$.

  * ii.

Suppose that $W\in\\{0,1\\}^{d}$ is composed of $d$ i.i.d. elements
distributed according to Bernoulli distribution with an unknown parameter
$\mathbb{P}(W_{i}=1)=p$ and
$|\ell(z,w)-\ell(z,\hat{w})|\leq\mathfrak{L}d_{H}(w,\hat{w})$, where $d_{H}$
is the Hamming distance.212121For binary vectors $x=(x_{1},\ldots,x_{d})$ and
$y=(y_{1},\ldots,y_{d})$,
$d_{H}(x,y)\coloneq\sum_{i=1}^{d}\mathbbm{1}_{\\{x_{i}\neq y_{i}\\}}$. Then,
for every $\delta>0$, with probability at least $1-\delta$,

$\displaystyle\operatorname*{gen}(S,W)\leq\min\limits_{0\leq\epsilon\leq
d}\left[\sqrt{\frac{2\sigma^{2}[d\log(2)-dh_{b}(\epsilon/d)+\log(1/\delta)]}{n}}+2\mathfrak{L}\epsilon\right],$

where $h_{b}(\cdot)$ is the binary entropy function, _i.e._
$h_{b}(p)=-p\log(p)-(1-p)\log(1-p)$, for $p\in[0,1]$ and $0\log(0)=0$ by
convention.

  * iii.

Suppose that $W\in\mathbb{R}^{d}$ is composed of $d$ i.i.d. elements
distributed according to the two-sided exponential distribution
$p(w_{i})=\frac{\lambda}{2}e^{-\lambda|w_{i}|},~{}i\in[d]$ and
$|\ell(z,w)-\ell(z,\hat{w})|\leq\mathfrak{L}\|w-\hat{w}\|_{1}$. Then, for
every $\delta>0$, with probability at least $1-\delta$,

$\displaystyle\operatorname*{gen}(S,W)\leq\min\limits_{\epsilon\geq
0}\left[\sqrt{\frac{2\sigma^{2}\left(dR^{\prime}(\epsilon,\delta)+\log(1/\delta)\right)}{n}}+2\mathfrak{L}\epsilon\right],$

where $R^{\prime}(\epsilon,\delta)$ is determined by

$\displaystyle\log(1/\delta)=\alpha\lambda-1-\log(\alpha\lambda),$

in which $\alpha\coloneq\epsilon\exp(R^{\prime}(\epsilon,\delta))/d$.

  * iv.

Suppose that $W\in\mathbb{R}^{d}$ is composed of $d$ i.i.d. elements
distributed according to the normal distribution
$\mathcal{N}(0,\sigma_{N}^{2})$ and
$|\ell(z,w)-\ell(z,\hat{w})|\leq\mathfrak{L}\|w-\hat{w}\|_{2}^{2}$. Then, for
every $\delta>0$, with probability at least $1-\delta$,

$\displaystyle\operatorname*{gen}(S,W)\leq\min\limits_{\epsilon\geq
0}\left[\sqrt{\frac{\sigma^{2}\left(d\log\left(\max\left(d\alpha^{2}/\epsilon,1\right)\right)+2\log(1/\delta)\right)}{n}}+2\mathfrak{L}\epsilon\right],$

where $\alpha\geq\sigma$ is determined by

$\displaystyle\log(1/\delta)=\frac{1}{2}\left(\frac{\alpha^{2}}{\sigma^{2}_{N}}-1-\log\left(\frac{\alpha^{2}}{\sigma^{2}_{N}}\right)\right).$

The corollary is proved in Appendix E.16.

##  Appendix E Proofs

In this section, we present the proofs of all our results, in the order of
their appearances in the paper.

###  E.1 Proof of Theorem 3.2

Here we state the proof for the long version of the theorem, stated in
Appendix D.1. Note that as defined in that appendix,
$\xi_{m}(w^{m},\hat{w}^{m};s^{m})\coloneq\frac{1}{m}\sum\nolimits_{i=1}^{m}\left(|\operatorname*{gen}(s_{i},w_{i})|-|\operatorname*{gen}(s_{i},\hat{w}_{i})|\right)$.

Before stating the proof, we show that having condition (8) for the distortion
functions $\left\\{\vartheta_{m},|\vartheta_{m}|,\xi_{m}\right\\}$ guarantees
that the expectation of the difference of the original and compressed
algorithms does not exceed $\epsilon$.

######  Lemma E.1.

If $\mathbb{E}[|\operatorname*{gen}(S,W)|]<\infty$, then for
$d_{m}\in\left\\{\vartheta_{m},|\vartheta_{m}|,\xi_{m}\right\\}$ condition (7)
yields

$\displaystyle\lim_{m\rightarrow\infty}\mathbb{E}_{(S,W)^{\otimes
m}}\left[\min_{j\in[l_{m}]}d_{m}(W^{m},\hat{\mathbf{w}}_{j};S^{m})\right]\leq\epsilon.$
(50)

The above lemma is proved in Appendix E.17. Now, we proceed with the proof of
the extended version of Theorem 3.2, appeared in Appendix D.1.

######  Proof E.2.

##### Part i.

Suppose that for each $(s^{m},w^{m})$,
$\hat{\mathbf{w}}(s^{m},w^{m})\coloneq\hat{\mathbf{w}}_{j}$ where
$j=\operatorname*{arg\min}\limits_{j\in[l_{m}]}\vartheta_{m}(w^{m},\hat{\mathbf{w}}_{j};s^{m})$,
which will be denoted by $\hat{\mathbf{w}}=(\hat{w}_{1},\ldots,\hat{w}_{m})$
for simplicity. Then,

$\displaystyle\mathbb{E}_{(S,W)}$
$\displaystyle\left[\operatorname*{gen}(S,W)\right]$ $\displaystyle=$
$\displaystyle\frac{1}{m}\mathbb{E}_{(S,W)^{\otimes
m}}\left[\sum\limits_{i=1}^{m}\operatorname*{gen}(S_{i},W_{i})\right]$
$\displaystyle=$ $\displaystyle\frac{1}{m}\mathbb{E}_{(S,W)^{\otimes
m}}\left[\sum\limits_{i=1}^{m}\operatorname*{gen}(S_{i},W_{i})-\operatorname*{gen}(S_{i},\hat{W}_{i})\right]+\frac{1}{m}\mathbb{E}_{(S,W)^{\otimes
m}}\left[\sum\limits_{i=1}^{m}\operatorname*{gen}(S_{i},\hat{W}_{i})\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\frac{1}{m}\mathbb{E}_{(S,W)^{\otimes
m}}\left[\sum\limits_{i=1}^{m}\operatorname*{gen}(S_{i},\hat{W}_{i})\right]+\epsilon+\varepsilon_{m}$
$\displaystyle\leq$ $\displaystyle\frac{1}{m}\mathbb{E}_{S^{\otimes
m}}\left[\max_{j\in[l_{m}]}\sum\limits_{i=1}^{m}\operatorname*{gen}(S_{i},\hat{w}_{j,i})\right]+\epsilon+\varepsilon_{m}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\frac{1}{m}\sqrt{\frac{2\sigma^{2}m\log(l_{m})}{n}}+\epsilon+\varepsilon_{m}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$
$\displaystyle\sqrt{\frac{2\sigma^{2}R}{n}}+\epsilon+\varepsilon_{m},$

where $(a)$ is by Lemma E.1, $(b)$ is derived since
$\sum\limits_{i=1}^{m}\operatorname*{gen}(S_{i},\hat{w}_{j,i})$ is
$\sigma\sqrt{m/n}$-subgaussian, and $(c)$ is obtained by bounding $l_{m}\leq
e^{mR}$. Taking the limit for $m\rightarrow\infty$ completes the proof.

##### Part ii.

Similarly, let $\hat{\mathbf{w}}(s^{m},w^{m})\coloneq\hat{\mathbf{w}}_{j}$
where
$j=\operatorname*{arg\min}\limits_{j\in[l_{m}]}|\vartheta_{m}(w^{m},\hat{\mathbf{w}}_{j};s^{m})|$.
Then, we have

$\displaystyle\big{|}\mathbb{E}_{(S,W)}$
$\displaystyle\left[\operatorname*{gen}(S,W)\right]\big{|}$
$\displaystyle\leq$ $\displaystyle\frac{1}{m}\mathbb{E}_{(S,W)^{\otimes
m}}\left[\big{|}\sum\limits_{i=1}^{m}\operatorname*{gen}(S_{i},W_{i})\big{|}\right]$
$\displaystyle\leq$ $\displaystyle\frac{1}{m}\mathbb{E}_{(S,W)^{\otimes
m}}\left[\big{|}\sum\limits_{i=1}^{m}\operatorname*{gen}(S_{i},W_{i})-\operatorname*{gen}(S_{i},\hat{W}_{i})\big{|}\right]+\frac{1}{m}\mathbb{E}_{(S,W)^{\otimes
m}}\left[\big{|}\sum\limits_{i=1}^{m}\operatorname*{gen}(S_{i},\hat{W}_{i})\big{|}\right]$
$\displaystyle\leq$ $\displaystyle\frac{1}{m}\mathbb{E}_{S^{\otimes
m}}\left[\max_{j\in[l_{m}]}\big{|}\sum\limits_{i=1}^{m}\operatorname*{gen}(S_{i},\hat{w}_{j,i})\big{|}\right]+\epsilon+\varepsilon_{m}$
$\displaystyle\leq$
$\displaystyle\frac{1}{m}\sqrt{\frac{2\sigma^{2}m\log(2l_{m})}{n}}+\epsilon+\varepsilon_{m}$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{2\sigma^{2}(R+\log(2)/m)}{n}}+\epsilon+\varepsilon_{m}.$

Taking the limit for $m\rightarrow\infty$ completes the proof.

##### Part iii.

Similarly, let $\hat{\mathbf{w}}(s^{m},w^{m})\coloneq\hat{\mathbf{w}}_{j}$
where
$j=\operatorname*{arg\min}\limits_{j\in[l_{m}]}\xi_{m}(w^{m},\hat{\mathbf{w}}_{j};s^{m})$.
Then, we have

$\displaystyle\mathbb{E}_{(S,W)}$
$\displaystyle\left[\big{|}\operatorname*{gen}(S,W)\big{|}\right]$
$\displaystyle=$ $\displaystyle\frac{1}{m}\mathbb{E}_{(S,W)^{\otimes
m}}\left[\sum\limits_{i=1}^{m}\big{|}\operatorname*{gen}(S_{i},W_{i})\big{|}-\big{|}\operatorname*{gen}(S_{i},\hat{W}_{i})\big{|}\right]+\frac{1}{m}\mathbb{E}_{(S,W)^{\otimes
m}}\left[\sum\limits_{i=1}^{m}\big{|}\operatorname*{gen}(S_{i},\hat{W}_{i})\big{|}\right]$
$\displaystyle\leq$ $\displaystyle\frac{1}{m}\mathbb{E}_{S^{\otimes
m}}\left[\max_{j\in[l_{m}]}\sum\limits_{i=1}^{m}\big{|}\operatorname*{gen}(S_{i},\hat{w}_{j,i})\big{|}\right]+\epsilon+\varepsilon_{m}$
$\displaystyle\leq$
$\displaystyle\frac{1}{m}\sqrt{\frac{2\sigma^{2}m\log(2^{m}l_{m})}{n}}+\epsilon+\varepsilon_{m}$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{2\sigma^{2}(R+\log(2))}{n}}+\epsilon+\varepsilon_{m}.$

Taking the limit for $m\rightarrow\infty$ completes the proof.

###  E.2 Proof of Theorem 3.3

######  Proof E.3.

Fix $\epsilon$ and $\nu_{1},\nu_{2}>0$. Assume that there exists a
$\hat{W}\in\hat{\mathcal{W}}$ defined by the conditional distribution
$P_{\hat{W}|S}$, such that
$\left|\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]\right|\leq\epsilon$.
It is sufficient to show $R_{E}(\epsilon)\leq I(S;\hat{W})+\nu_{1}$.

Denote the empirical distribution of a sequence $x^{m}$ by $\hat{P}_{x^{m}}$,
_i.e._

$\displaystyle\hat{P}_{x^{m}}(x)\coloneq\frac{\\#i\in[m]\colon x_{i}=x}{m}.$
(51)

Then, using the proof of (Cuff et al., 2010, Theorem 3), there exists a
required sequence of $\left\\{\mathcal{H}_{m}\right\\}_{m\in\mathbb{N}}$ such
that $|\mathcal{H}_{m}|\leq e^{m(I(S;\hat{W})+\nu_{1})}$ and such that for
each $S^{m}$, a vector $\hat{W}^{m}(S^{m})\in\mathcal{H}_{m}$, that we denote
for ease of notations as $\hat{W}^{m}$, can be chosen such that

$\displaystyle\|\hat{P}_{(S^{m},\hat{W}^{m})}(s,\hat{w})-P_{(S,\hat{W})}(s,\hat{w})\|_{TV}\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0.$ (52)

where $\stackrel{{\scriptstyle p}}{{\longrightarrow}}$ means convergence in
probability and _TV_ denotes the total variation distance between two
distributions (Cuff et al., 2010, Definition 4). Moreover, by strong law of
large numbers, for $m$ independent instances $(S_{i},W_{i})$ chosen according
to $P_{S,W}$, we have

$\displaystyle\|\hat{P}_{(S^{m},W^{m})}(s,w)-P_{S,W}(s,w)\|_{TV}\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0.$ (53)

This yields

$\displaystyle\left|\frac{1}{m}\sum\limits_{i=1}^{m}\left[\operatorname*{gen}(S_{i},W_{i})-\operatorname*{gen}(S_{i},\hat{W}_{i})\right]\right|\leq$
$\displaystyle\left|\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]\right|+\epsilon_{m}$
(54) $\displaystyle\leq$ $\displaystyle\epsilon+\varepsilon_{m},$ (55)

where $\varepsilon_{m}$ vanishes as $m\rightarrow\infty$. Now,

$\displaystyle\mathbb{P}_{(S,W)^{\otimes
m}}\left(\vartheta_{m}(W^{m},\hat{W}^{m};S^{m})\geq\epsilon+\nu_{2}\right)\leq$
$\displaystyle\mathbb{P}_{(S,W)^{\otimes
m}}\left(\epsilon+\varepsilon_{m}\geq\epsilon+\nu_{2}\right)$
$\displaystyle\rightarrow$ $\displaystyle 0,$

where the last line is when $m\rightarrow\infty$. This completes the proof.

###  E.3 Proof of Theorem 3.4

######  Proof E.4.

We show

$\displaystyle\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|\leq\sqrt{\frac{2\sigma^{2}R_{E}(\epsilon)}{n}}+\epsilon,$
(56)

and the proof for the rest of bounds in (40) is similar. Consider any Markov
kernel $P_{\hat{W}|S}$ that satisfies
$\left|\mathbb{E}\left[\operatorname*{gen}(S,W)-\operatorname*{gen}(S,\hat{W})\right]\right|\leq\epsilon$.
Then,

$\displaystyle\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|\leq$
$\displaystyle\left|\mathbb{E}\left[\operatorname*{gen}(S,\hat{W})\right]\right|+\epsilon$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{2\sigma^{2}I(S;\hat{W})}{n}}+\epsilon,$

where the last step is deduced from (Xu and Raginsky, 2017, Theorem 1). This
completes the proof.

###  E.4 Proof of Corollary 3.7

######  Proof E.5.

Let $n^{\prime}_{0}$ be large enough such that for $n\geq n^{\prime}_{0}$ and
$\epsilon\coloneq 2\mathfrak{L}/\sqrt{n\mathfrak{L}^{2}}=2/\sqrt{n}$,

$\displaystyle\mathfrak{RD}(\epsilon/(2\mathfrak{L});P_{W},\varrho)/\log(2\mathfrak{L}/\epsilon)\leq
2\dim_{\mathrm{R}}(P_{W}).$

Note that this holds due to the uniform convergence assumption of the
corollary. Then, using Corollary 3.6, we have

$\displaystyle\left|\mathbb{E}\left[\operatorname*{gen}(S,W)\right]\right|$
$\displaystyle\leq\sqrt{\frac{2\sigma^{2}\dim_{\mathrm{R}}(P_{W},\delta)\log(n\mathfrak{L}^{2})}{n}}+\sqrt{\frac{4}{n}}$
$\displaystyle\leq\sqrt{\frac{4\sigma^{2}\dim_{\mathrm{R}}(P_{W},\delta)\log(n\mathfrak{L}^{2})}{n}},$

where the last inequality holds for $n\geq n_{0}$, where $n_{0}\geq
n^{\prime}_{0}$ is a sufficiently large integer.

###  E.5 Proof of Theorem 3.9

######  Proof E.6.

Some of the steps in this proof are identical to the proof of Theorem 4.3, by
considering $X^{m}$ as
$(\operatorname*{gen}(S_{1},W_{1}),\ldots,\operatorname*{gen}(S_{m},W_{m}))$
and $\hat{X}^{m}(j)$ as
$(\operatorname*{gen}(S_{1},\hat{w}_{j,1}),\ldots,\operatorname*{gen}(S_{m},\hat{w}_{j,m}))$.
Here, for the sake of completeness, we re-state all steps for the particular
setup and notations used for the generalization error problem.

For any $\nu\in(0,\log(1/\delta))$ sufficiently small, choose $m_{0}$ such
that for $m\geq m_{0}$,

$\displaystyle-\frac{1}{m}\log\left(\mathbb{P}_{(S,W)^{\otimes
m}}\left(\mathcal{E}_{m}(\mathcal{H}_{m},\epsilon;\varphi_{m})\right)\right)\geq\log(1/\delta)-\nu.$
(57)

For ease of notations, let
$\mathcal{E}_{m}\coloneq\mathcal{E}_{m}(\mathcal{H}_{m},\epsilon;\varphi_{m})$.
Then,

$\displaystyle\mathbb{P}_{S,W}$
$\displaystyle\left(\operatorname*{gen}(S,W)\geq\Delta\right)^{m}$
$\displaystyle=$ $\displaystyle\mathbb{P}_{(S,W)^{\otimes m}}\left(\forall
i,\operatorname*{gen}(S_{i},W_{i})\geq\Delta\right)$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{(S,W)^{\otimes m}}\left(\forall
i,\operatorname*{gen}(S_{i},W_{i})\geq\Delta,\mathcal{E}_{m}^{c}\right)+\mathbb{P}_{(S,W)^{\otimes
m}}\left(\mathcal{E}_{m}\right)$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{(S,W)^{\otimes m}}\left(\forall
i,\operatorname*{gen}(S_{i},W_{i})\geq\Delta,\mathcal{E}_{m}^{c}\right)+e^{-m(\log(1/\delta)-\nu)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{S^{\otimes m}}\left(\exists
w^{m}\colon\forall
i,\operatorname*{gen}(S_{i},w_{i})\geq\Delta,\mathcal{E}_{m}^{c}\right)+e^{-m(\log(1/\delta)-\nu)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{S^{\otimes m}}\left(\exists
j\in[l_{m}],\\{\Delta_{i}\\}_{i=1}^{m}\in\mathbb{R}\colon\forall
i,\operatorname*{gen}(S_{i},\hat{w}_{j,i})\geq\Delta-\Delta_{i},\sum_{i=1}^{m}\Delta_{i}\leq
m\epsilon\right)+e^{-m(\log(1/\delta)-\nu)}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{S^{\otimes m}}\left(\exists
j\in[l_{m}],\\{\Delta_{i}\\}_{i=1}^{m}\in\mathbb{R}\colon\sum_{i=1}^{m}\operatorname*{gen}(S_{i},\hat{w}_{j,i})\geq\sum_{i=1}^{m}\left(\Delta-\Delta_{i}\right),\sum_{i=1}^{m}\Delta_{i}\leq
m\epsilon\right)+e^{-m(\log(1/\delta)-\nu)}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{S^{\otimes m}}\left(\exists
j\in[l_{m}]\colon\sum_{i=1}^{m}\operatorname*{gen}(S_{i},\hat{w}_{j,i})\geq
m\left(\Delta-\epsilon\right)\right)+e^{-m(\log(1/\delta)-\nu)}$
$\displaystyle\leq$
$\displaystyle\sum\limits_{j\in[l_{m}]}\mathbb{P}_{S^{\otimes
m}}\left(\sum_{i=1}^{m}\operatorname*{gen}(S_{i},\hat{w}_{j,i})\geq
m\left(\Delta-\epsilon\right)\right)+e^{-m(\log(1/\delta)-\nu)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\sum\limits_{j\in[l_{m}]}e^{-mn(\Delta-\epsilon)^{2}/(2\sigma^{2})}+e^{-m(\log(1/\delta)-\nu)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$ $\displaystyle
e^{m(R-n(\Delta-\epsilon)^{2}/(2\sigma^{2}))}+e^{-m(\log(1/\delta)-\nu)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$ $\displaystyle
2e^{-m(\log(1/\delta)-\nu)}$

where $(a)$ is derived using the Hoeffding’s inequality, $(b)$ is derived
since $l_{m}\leq e^{mR}$, and $(c)$ is derived by choosing $\Delta$ as
$\Delta\coloneq\sqrt{\frac{2\sigma^{2}(R+\log(1/\delta))}{n}}+\epsilon$. The
proof completes by taking the $m$’th root of both sides, and since $\nu$ can
be chosen arbitrarily small.

###  E.6 Proof of Theorem 3.10

Theorem 3.10 is stated in Section 3.3 for $U$ being a constant and in Appendix
D.2 has been extended to take into account the stochasticity of the algorithm.
In the following, we first state the proof for finite sets and for the $U$
being a constant using Theorem 3.9. The result can be extended to the case of
arbitrary $U$ that satisfies the conditions of the theorem, and to infinite
sets, with some further assumptions on $(S,W)$, using the quantization
technique used in the proof of (El Gamal and Kim, 2011, Theorem 3.6) and by
applying (Iriyama, 2005, Theorem 1) and its adaptation for the memoryless
sources in (Bakshi and Bansal, 2005, Theorem 3). However, for the general
case, we state an alternative proof that applies the Donsker–Varadhan’s
variational representation of the KL divergence.

####  E.6.1 First Proof

######  Proof E.7.

Suppose that $\mathcal{S}\times\mathcal{W}$ is a finite set and $U$ is a
constant. We start by showing that for every $\epsilon\in\mathbb{R}$ and any
$\nu_{1},\nu_{2}>0$, the algorithm $\mathcal{A}(S)$ is
$\left(R(\delta,\epsilon)+\nu_{1},\epsilon+\nu_{2},\delta;\\{\varphi_{m}\\}_{m}\right)$-exponentially
compressible. Our proof is similar to (Marton, 1974, Theorem 1).

Let $Q_{m}$ be an arbitrary type of $\mathcal{S}^{m}\times\mathcal{W}^{m}$.
For the definition of the type, refer to the beginning of the appendices.
Define

$\displaystyle\mathcal{Q}_{m}(\delta)\coloneq\left\\{Q_{m}\colon
D_{KL}\left(Q_{m}\|P_{S,W}\right)\leq\log(1/\delta)\right\\}.$ (58)

Note that,

$\displaystyle\mathbb{P}_{(S,W)^{\otimes
m}}\left(\mathcal{T}(S^{m},W^{m})\notin\mathcal{Q}_{m}(\delta)\right)=$
$\displaystyle\sum\limits_{Q^{\prime}_{m}\notin\mathcal{Q}(\delta)}\mathbb{P}_{(S,W)^{\otimes
m}}\left(\mathcal{T}(S^{m},W^{m})=Q^{\prime}_{m}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\sum\limits_{Q^{\prime}_{m}\notin\mathcal{Q}(\delta)}e^{-mD_{KL}\left(Q^{\prime}_{m}\|P_{S,W}\right)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$ $\displaystyle
m^{\left|\mathcal{S}\right|\times\left|\mathcal{W}\right|}e^{m\log(\delta)}$
$\displaystyle=$ $\displaystyle
e^{m\left(\log(\delta)+\left|\mathcal{S}\right|\times\left|\mathcal{W}\right|\log(m)/m\right)}$
$\displaystyle=$ $\displaystyle(\delta+\varepsilon_{m})^{m},$ (59)

where $\lim_{m\rightarrow\infty}\varepsilon_{m}=0$, the step $(a)$ is due to
(Cover and Thomas, 2006, Theorem 11.1.4), and the step $(b)$ is deduced since
number of types can be bounded by
$m^{\left|\mathcal{S}\right|\times\left|\mathcal{W}\right|}$.

First, we state a variant of type covering lemma (Berger, 1975, Section 6.1.2,
Lemma 1) (appeared also in (Csiszár and Körner, 2011, Lemma 9.1)), proved in
Appendix E.18:

######  Lemma E.8.

For any $\nu>0$ and any type $Q_{m}$, there exists a hypothesis book
$\mathcal{H}_{Q_{m}}=\\{\mathbf{\hat{w}}_{Q_{m},j},j\in[l_{Q_{m}}]\\}\subseteq\mathcal{\hat{W}}^{m}$,
such that $l_{Q_{m}}\leq e^{mR_{Q_{m}}}$, where

$\displaystyle
R_{Q_{m}}=\mathfrak{RD}^{*}(\epsilon;Q_{m})+\varepsilon_{Q_{m}},$ (60)

and $\lim_{m\rightarrow\infty}\varepsilon_{Q_{m}}=0$, and such that for $m\geq
m_{\nu,Q_{m}}$,

$\displaystyle\mathbb{P}_{(S,W)^{\otimes
m}}\left(\mathcal{T}(S^{m},W^{m})=Q_{m},\min_{j\in[l_{Q_{m}}]}\varphi_{m}\left(W^{m},\mathbf{\hat{w}}_{Q_{m},j};S^{m}\right)\geq\epsilon+\nu\right)=0.$
(61)

Let $m\geq m_{\nu}$, where $m_{\nu}$ is sufficiently large such that the above
lemma holds for all types. Letting
$\mathcal{H}_{m}\coloneq\bigcup\limits_{Q_{m}\in\mathcal{Q}_{m}(\delta)}\mathcal{H}_{Q_{m}}$,
we have

$\displaystyle l_{m}\leq$
$\displaystyle\sum\limits_{Q_{m}\in\mathcal{Q}_{m}(\delta)}l_{Q_{m}}$
$\displaystyle\leq
m^{\left|\mathcal{S}\right|\times\left|\mathcal{W}\right|}e^{m\left(\max\limits_{Q_{m}\in\mathcal{Q}_{m}(\delta)}\left[\mathfrak{RD}^{*}(\epsilon;Q_{m})+\varepsilon_{Q_{m}}\right]\right)}$
$\displaystyle=$ $\displaystyle
e^{m\left(\max\limits_{Q_{m}\in\mathcal{Q}_{m}(\delta)}\mathfrak{RD}^{*}(\epsilon;Q_{m})+\varepsilon^{\prime}_{m}\right)},$
(62)

where $\lim_{m\rightarrow\infty}\varepsilon^{\prime}_{m}=0$. Moreover,

$\displaystyle\mathbb{P}_{(S,W)^{\otimes m}}$
$\displaystyle\left(\mathcal{E}_{m}(\mathcal{H}_{m},\epsilon+\nu;\varphi_{m})\right)$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{(S,W)^{\otimes
m}}\left((S^{m},W^{m})\notin\mathcal{Q}_{m}\right)$
$\displaystyle+\mathbb{P}_{(S,W)^{\otimes
m}}\left((S^{m},W^{m})\in\mathcal{Q}_{m},\min_{Q_{m}\in\mathcal{Q}_{m}}\min_{j\in[l_{Q_{m}}]}\varphi_{m}\left(W^{m},\mathbf{\hat{w}}_{Q_{m},j};S^{m}\right)\geq\epsilon+\nu\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle(\delta+\varepsilon_{m})^{m}.$

where the last steps is derived using Lemma E.8 and relation (59).

Hence,

$\displaystyle\lim\limits_{m\rightarrow\infty}-\frac{1}{m}\log\left(\mathbb{P}_{(S,W)^{\otimes
m}}\left(\mathcal{E}_{m}(\mathcal{H}_{m},\epsilon+\nu;\varphi_{m})\right)\right)\leq\log(1/\delta).$
(63)

The relations (62) and (63) show that for every $\epsilon\in\mathbb{R}$ and
any $\nu_{1},\nu_{2}>0$, the algorithm $\mathcal{A}(S)$ is
$\left(R(\delta,\epsilon)+\nu_{1},\epsilon+\nu_{2},\delta;\\{\varphi_{m}\\}_{m}\right)$-exponentially
compressible. Using Theorem 3.9 completes the proof.

####  E.6.2 Second Proof

######  Proof E.9.

In this proof, since we use Theorem 4.1, we denote $P_{U,S,W}$ by
$\mu_{U,S,W}$, to be compatible with the notations of Theorem 4.1. Note that
$\mu_{U,S,W}=\mu_{S}\mu_{U}\mu_{W|S,U}$ where $U$ is an independent noise in
the algorithm and $W$ is the output hypothesis of the algorithm.

Let $X\coloneq\operatorname*{gen}(W,S)$. This defines $\mu_{S,U,W,X}$. Writing
Theorem 4.1 with the choice of $Y=(S,U,W)$, we get that

$\displaystyle\log\mathbb{P}_{X\sim\mu_{X}}\left(X\geq\Delta\right)$ (64)
$\displaystyle\leq\max\bigg{[}\log(\delta),~{}~{}~{}\sup_{\nu_{S,U,W,X}\in\mathcal{G}}~{}~{}~{}\inf_{p_{\hat{X}|S,U,W}\in\mathcal{Q}(\nu),~{}q_{\hat{X}|S,U,W},~{}\lambda\geq
0}\bigg{\\{}D_{KL}(p_{\hat{X}|S,U,W}\nu_{S,U,W}\|q_{\hat{X}|S,U,W}\nu_{S,U,W})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad-\lambda(\Delta-\epsilon)+\log\mathbb{E}_{\mu_{S,U,W}q_{\hat{X}|S,U,W}}[e^{\lambda\hat{X}}]\bigg{\\}}\bigg{]}$

where $\mathcal{G}$ is the following set of distributions:

$\displaystyle\mathcal{G}=\\{\nu_{X,S,U,W}:D_{KL}(\nu_{X,S,U,W}\|\mu_{X,S,U,W})\leq\log(1/\delta),\\}$

and $\mathcal{Q}(\nu)$ is the set of conditional distributions
$p_{\hat{X}|S,U,W}$ such that under $p_{\hat{X}|S,U,W}\nu_{S,U,W}$ we have:

$\left[\inf_{x\in\operatorname{supp}(\nu_{X})}x\right]-\mathbb{E}[\hat{X}]\leq\epsilon.$

Since $X=\operatorname*{gen}(W,S)$ under $\mu_{X,U,W,S}$, and
$D_{KL}(\nu_{X,S,U,W}\|\mu_{X,S,U,W})<\infty$, we obtain that
$X=\operatorname*{gen}(W,S)$ under $\nu_{X,U,W,S}$ too. Therefore, the
supremum is over distribution $\nu$ of the form