# From Generalisation Error to Transportation-cost Inequalities and Back

Amedeo Roberto Esposito, Michael Gastpar  School of Computer and Communication
Sciences
EPFL, Lausanne, Switzerland
{amedeo.esposito<EMAIL_ADDRESS>
###### Abstract

In this work, we connect the problem of bounding the expected generalisation
error with transportation-cost inequalities. Exposing the underlying pattern
behind both approaches we are able to generalise them and go beyond Kullback-
Leibler Divergences/Mutual Information and sub-Gaussian measures. In
particular, we are able to provide a result showing the equivalence between
two families of inequalities: one involving functionals and one involving
measures. This result generalises the one proposed by Bobkov and Götze that
connects transportation-cost inequalities with concentration of measure.
Moreover, it allows us to recover all standard generalisation error bounds
involving mutual information and to introduce new, more general bounds, that
involve arbitrary divergence measures.

###### Index Terms:

Wasserstein Distance, Kullback-Leibler Divergence, Information Measures,
Duality, Young’s Inequality, Transportation-Cost Inequalities, Generalisation
Error

##  I Introduction

A recent and interesting line of research has explored the problem of bounding
the generalization error of learning algorithms via information measures [1,
2, 3, 4, 5, 6, 7, 8, 9]. The starting observation is that one can interpret a
learning algorithm as a (potentially) randomised mapping that takes as input a
data-set and provides as output a hypothesis (e.g., a classifier). The purpose
is to retrieve a classifier that has good performance both on the training set
and on an independent test set. Intuitively, if the outcome of the learning
algorithm depends too much on its input then its performance on new data-
points will be poor. In this case, the algorithm is said to overfit to the
training set. One way of measuring said dependence is through information
measures. To this day, virtually every information measure has been connected
to the problem: Mutual Information [1, 2, 8, 9], Total Variation [3], Rényi’s
$\alpha$-Divergences, Sibson’s $\alpha-$Mutual Information, $f-$divergences
and $f-$Mutual Information [7], etc. The connection has been drawn with
respect to expected generalisation error [1, 10, 3, 4] and with respect to the
probability of having a large generalisation error [7].
We noticed a similarity between the bound connecting expected generalisation
error to mutual information and transportation-cost inequalities.
Transportation-cost inequalities connect Wasserstein distances and Kullback-
Leibler divergences to the concentration of measure phenomenon. In this work
we will connect the dots and expose the pattern connecting these objects.
Moreover, unearthing the underlying mechanism we will generalise both type of
results (generalisation-error bounds and transportation-cost inequalities) and
go beyond Kullback-Leibler Divergences and sub-Gaussian tails.

##  II Background and definitions

Following the De Finetti’s notation, instead of denoting the expectation of a
function $f$ with respect to a probability measure $\mu$ with
$\mathbb{E}_{\mu}[f]$ we will denote it with $\mu(f)$. Spaces will be denoted
with calligraphic letters $\mathcal{X},\mathcal{Y}$, random variables with
capital letters $X,Y$ and measures with Greek lower-case letters $\mu,\nu$.
Given a function $f:\mathcal{X}\to\mathcal{Y}$ we will denote with $f^{\star}$
its Legendre-Fenchel dual, defined as follows.

$f^{\star}(x^{\star})=\sup_{x\in\mathcal{X}}\langle x,x^{\star}\rangle-f(x),$
(1)

where $\langle x,x^{\star}\rangle$ denotes the natural pairing between a space
$\mathcal{X}$ and its topological dual $\mathcal{X}^{\star}$, i.e., $\langle
x,x^{\star}\rangle=x^{\star}(x).$ A different but related notion of duality is
Young’s duality. Given a function $f:\mathbb{R}\to\mathbb{R}$ we denote,
through a slight abuse of notation, with $f^{\star}$ its Young’s complementary
function, defined as follows:

$f^{\star}(x^{\star})=\sup_{x>0}\langle
x,x^{\star}\rangle-f(x),\,\,\,x^{\star}>0.$ (2)

Notice that the supremum in (2) is over a different set with respect to (1).
We will always specify which notion of duality we are using throughout the
paper. Given two measures $\mu,\nu$ and a convex functional $\varphi$ we
denote with
$D_{\varphi}(\nu\|\mu)=\mu\left(\varphi\left(\frac{d\nu}{d\mu}\right)\right)$
the $\varphi$-divergence, where $\frac{d\nu}{d\mu}$ is the Radon-Nikodym
derivative. With $\varphi(x)=x\log x$ one recovers the KL-divergence
$D(\nu\|\mu)$, with $\varphi(x)=|x-1|$ one recovers the Total Variation
distance $TV(\nu,\mu)$ and with
$\varphi(x)=\frac{|x|^{\alpha}}{\alpha},\alpha>0$ one recovers the Hellinger
integral $H_{\alpha}(\nu\|\mu)$.

###  II-A Optimal Transport Theory

Denote with $\mathcal{M}(\mathcal{X})$ the set of all signed measures over
$\mathcal{X}$ and with $\mathcal{P}(\mathcal{X})$ the set of all probability
measures over $\mathcal{X}$. Let $\mu,\nu\in\mathcal{P}(\mathcal{X})$,
consider the set $\Pi(\mu,\nu)$ of all the joint probability measures
$\pi\in\mathcal{P}(\mathcal{X}\times\mathcal{X})$ with marginals equal to
$\mu$ and $\nu$, i.e., such that $\pi(\cdot\times\mathcal{X})=\mu(\cdot)$ and
$\pi(\mathcal{X}\times\cdot)=\nu(\cdot)$. The problem advanced by Kantorovich
was the following: given $\mu$ and $\nu$ and a Borel function
$d:\mathcal{X}\times\mathcal{X}\to[0,+\infty]$, can we find a joint measure
$\pi$ that minimises $\pi(d(X,Y))?$ $\pi$ represents a transport plan between
$\mu,\nu$. Under mild assumptions on $d$, optimal transport plans are
guaranteed to exists for extremely general spaces $\mathcal{X}$ [11, Theorem
4.1]. If $d$ itself is a metric over $\mathcal{X}$, then
$\inf_{\pi}\pi(d(X,Y))$ represents a distance over the space of probability
measures. In particular, given a metric $d$, let us denote with
$\mathcal{P}_{p}(\mathcal{X})$ the set of probability measures $\mu$ on
$\mathcal{X}$ such that $\mu(d(X,x_{0})^{p})^{1/p}<+\infty$ for some
$x_{0}\in\mathcal{X}$.

######  Definition 1 ([11, Def. 6.1]).

Let $(\mathcal{X},d)$ be a Polish space and $p\in[1,+\infty).$ Let
$\mu,\nu\in\mathcal{P}_{p}(\mathcal{X})$, the $p-$Wasserstein distance between
$\mu$ and $\nu$ is defined as
$W_{p}(\mu,\nu)=\inf_{\pi\in\Pi(\mu,\nu)}(\pi(d(X,Y)^{p}))^{1/p}.$

Wasserstein distances satisfy interesting properties [12, Lemma 3.4.1].
Moreover, when connected to KL-divergences, in what are known in the
literature as “Transportation-cost Inequalities”, they have interesting
implications in the concentration of measure phenomenon.

######  Definition 2 (Transportation-Cost Inequality).

Let $(\mathcal{X},d)$ be a Polish space and $\mu$ a probability measure on
$\mathcal{X}$, we say that $\mu$ satisfies an $L^{p}$-transportation-cost
inequality with constant $c$ (or $T_{p}(c)$ in short) if for every $\nu\ll\mu$

$W_{p}(\mu,\nu)\leq\sqrt{2cD(\nu\|\mu)}.$ (3)

When $p=1$, for instance, these inequalities are equivalent to concentration
in the following sense:

######  Theorem$\,\diamond$ ([13, Thm 3.1]).

Let $\mu\in\mathcal{P}_{1}(\mathcal{X})$ be a Borel probability measure. There
exists a $c$ such that for every $\lambda\in\mathbb{R}$

$\log\mu(\exp(\lambda f))\leq\left(\frac{c\lambda^{2}}{2}\right)$ (4)

for every $1-$Lipschitz function $f$, if and only if $\mu$ satisfies a
$T_{1}(c)$ inequality, i.e., for every $\nu\ll\mu$

$W_{1}(\mu,\nu)\leq\sqrt{2cD(\nu\|\mu)}.$ (5)

######  Example 1.

Let $\mathcal{X}$ be a discrete space and $d(x,y)=\mathds{1}_{x\neq y}$. We
have that $W_{1}(\mu,\nu)=TV(\mu,\nu)$, i.e., the Total Variation distance
between $\mu,\nu$ [12, Prop. 3.4.1]. In this case the transportation cost
inequality is well-known under the name of Pinsker’s inequality and it holds
for every $\mu\in\mathcal{P}_{1}(\mathcal{X})$ with $c=1/4$. In general, such
inequalities are highly non-trivial and hold for specific distributions (e.g.,
Gaussian, etc.).

###  II-B Learning Theory

For reasons of space we skip a thorough description of the learning framework.
The setting we consider is the one described in [7, Section II.C]. In
particular, in this work, we focus on the expected generalisation error which
can be defined as follows:

######  Definition 3.

Let $\mathcal{P}_{Z}$ be a probability measure over $\mathcal{Z}$. Let
$\ell:\mathcal{H}\times\mathcal{Z}\to\mathbb{R}$ be a loss function. The error
(or risk) of a prediction rule $h$ with respect to $\mathcal{P}$ is defined as
$L_{\mathcal{P}}(h)=\mathcal{P}_{Z}(\ell(h,Z))$ while, given a sample
$S=(z_{1},\ldots,z_{n})$, the empirical error of $h$ with respect to $S$ is
defined as $L_{S}(h)=\frac{1}{n}\sum_{i=1}^{n}\ell(h,z_{i}).$ Moreover, given
a learning algorithm $\mathcal{A}:\mathcal{Z}^{n}\to\mathcal{H}$, its
generalization error with respect to $S$ is defined as follows:

$\text{gen-
err}_{\mathcal{P}}(\mathcal{A},S)=\mathcal{P}_{HS}(L_{S}(\mathcal{A}(S))-L_{\mathcal{P}}(\mathcal{A}(S))).$
(6)

##  III Main Result

Let us start with the main result and then elaborate on it to show how it is
connected to both generalisation error and transportation-cost inequalities.

######  Theorem 1.

Let $f\in C_{c}(\mathcal{X})$ and $\phi$ be a strongly convex function such
that its Legendre-Fenchel dual $\phi^{\star}$ admits a generalised inverse
${\phi^{\star}}^{-1}(t)=\inf\\{s:\phi(s)\geq t\\}$. Let
$\psi^{\star}:\mathcal{M}(\mathcal{X})\to\mathbb{R}$ be the Legendre-Fenchel
dual of $\psi:C_{c}(\mathcal{X})\to\mathbb{R}$. If

$\psi(\lambda f)\leq\phi(\lambda)\text{ for every }\lambda>0$ (7)

then, for every measure $\nu$ such that $\nu(f)<+\infty$ and
${\phi^{\prime}}^{-1}\left({\phi^{\star}}^{-1}(\psi^{\star}(\nu))\right)>0$,

$\nu(f)\leq{\phi^{\star}}^{-1}\left(\psi^{\star}(\nu)\right).$ (8)

###### Proof.

By definition of Legendre-Fenchel transform we know that for a given function
$f$ and any given measure $\nu$:

$\displaystyle\psi^{\star}(\nu)$ $\displaystyle=\sup_{f\in
C_{c}(\mathcal{X})}\langle f,\xi\rangle-\psi(f)$ (9)
$\displaystyle\geq\lambda\langle f,\nu\rangle-\psi(\lambda
f)=\lambda\nu(f)-\psi(\lambda f).$ (10)

Hence, we can say that, given $f\in C_{c}(\mathcal{X})$,
$\nu\in\mathcal{M}(\mathcal{X})$ and $\lambda>0$

$\displaystyle\nu(f)$ $\displaystyle\leq\frac{\psi(\lambda
f)+\psi^{\star}(\nu)}{\lambda}\leq\frac{\phi(\lambda)+\psi^{\star}(\nu)}{\lambda},$
(11)

where in (11) we used our assumption on $\psi$. Denoting with
$c=\psi^{\star}(\nu)$ and choosing
$\lambda={\phi^{\prime}}^{-1}\left({\phi^{\star}}^{-1}(c)\right)$ gives us
that

$\nu(f)\leq{\phi^{\star}}^{-1}(c)={\phi^{\star}}^{-1}(\psi^{\star}(\nu)).$
(12)

Indeed, let us denote, for simplicity, ${\phi^{\star}}^{-1}(c)=t$, then
replacing $\lambda$ with
${\phi^{\prime}}^{-1}\left({\phi^{\star}}^{-1}(c)\right)$ in (11) one has

$\displaystyle\frac{c+\phi({\phi^{\prime}}^{-1}\left(t\right))}{{\phi^{\prime}}^{-1}\left(t\right)}$
$\displaystyle=\frac{c+t\phi^{\prime-1}(t)-\phi^{\star}(t)}{{\phi^{\prime}}^{-1}\left(t\right)}$
(13)
$\displaystyle=t+\frac{c-\phi^{\star}(t)}{{\phi^{\prime}}^{-1}\left(t\right)}$
(14)
$\displaystyle={\phi^{\star}}^{-1}(c)+\frac{c-\phi^{\star}({\phi^{\star}}^{-1}(c))}{{\phi^{\prime}}^{-1}\left(t\right)}$
(15) $\displaystyle\leq{\phi^{\star}}^{-1}(\psi^{\star}(\nu)),$ (16)

where (13) follows from [14, Eq. (1.11)]. ∎

######  Remark 1.

In most settings of interest the assumption that
${\phi^{\prime}}^{-1}\left({\phi^{\star}}^{-1}(\psi^{\star}(\nu))\right)>0$ is
easily satisfied. If one considers $\psi^{\star}(\nu)$ to be a
$\varphi$-Divergence, i.e., $\psi^{\star}(\nu)=D_{\varphi}(\nu\|\mu)$, with
$\mu$ a probability measure fixed before-hand, then $\psi^{\star}(\nu)\geq 0$
for every $\nu\in\mathcal{P}(\mathcal{X})$. Typical functions $\phi$ will be
of the form $\phi(x)=x^{\alpha}/\alpha$ with $\alpha>1$. This implies that
${\phi^{\prime}}^{-1}\left({\phi^{\star}}^{-1}(\psi^{\star}(\nu))\right)=(\beta\psi^{\star}(\nu))^{\frac{1}{\alpha}}$
with $\beta=\alpha/(\alpha-1)>0$, which is clearly positive for
$\psi^{\star}(\nu)>0$.

A variety of assumptions in Theorem 1 can be altered. It is possible, for
instance, to choose different notions of duality regarding both $\psi$ and
$\phi$. If instead of Legendre-Fenchal duality of $\phi$ one uses the notion
of Young’s duality/Young’s complementary functions then it is actually
possible to find the infimum over $\lambda>0$ in (11) using [15, Lemma 2.4]
(modulo some extra assumptions on $\phi$). The result remains unchanged with a
slightly different set of assumptions and the knowledge that such bound is the
tightest with respect to $\lambda$ in (11). Other choices might be suitable as
well. For instance, selecting $\psi_{\mu}^{\star}(f)=\mu(\exp(f))-1$ one
recovers $\psi^{\star}_{\mu}(\nu)$ to be the KL-Divergence between any
positive measure $\nu$ (not necessarily a probability measure) and a fixed
measure $\mu$. Alternatively, considering $\psi_{\mu}(\nu)=\log(\mu(\exp(f)))$
then $\psi^{\star}_{\mu}$ would be the usual KL-Divergence, defined only on
probability measures, (e.g., with $D(\nu\|\mu)=+\infty$ if
$\nu\not\in\mathcal{P}(\mathcal{X}))$. In general, whenever we restrict the
domain of the divergence and, we obtain a potentially tighter variational
representation of $\psi^{\star}$ (in the considered space) which might,
however, be harder to compute. In the case of KL the restriction to
probability measures is well-known in the literature as the “Donsker-Varadhan”
representation of KL. For more details on the matter we refer the reader to
[16].

Let us now proceed with examples with the purpose of better understanding both
the assumptions and the implications of Theorem 1.

######  Corollary 1.

Let $X$ be a random variable over the probability space
$(\mathcal{X},\mathcal{F},\mu)$ and assume $X$ to be a zero-mean
$\sigma^{2}$-sub-Gaussian random variable 111Given a zero-mean random variable
$X$ we say that it is $\sigma^{2}$-sub-Gaussian if the following holds true
for every $\lambda\in\mathbb{R}$ : $\log(\mu(e^{\lambda
X}))\leq\frac{\lambda^{2}\sigma^{2}}{2}$. with respect to $\mu$. We have that
for every measure $\nu$ such that $\nu\ll\mu$ and such that $\nu(X)<+\infty$

$\nu(X)\leq\sqrt{2\sigma^{2}D(\nu\|\mu)}.$ (17)

###### Proof.

The proof follows from Theorem 1, selecting $\psi(f)=\log(\mu(\exp(f)))$ and
thus $\psi^{\star}(\nu)=D(\nu\|\mu)$ with $\nu\in\mathcal{P}(\mathcal{X})$.
The assumption that $X$ is sub-Gaussian under $\mu$ implies that $\psi(\lambda
X)\leq\frac{\lambda^{2}\sigma^{2}}{2}=\phi(\lambda)$ for every
$\lambda\in\mathbb{R}$, where $\phi$ is a strongly convex function. To
complete the argument, we observe that
$\phi^{\star}(\lambda^{\star})=\frac{{\lambda^{\star}}^{2}}{2\sigma^{2}}\implies{\phi^{\star}}^{-1}(t)=\sqrt{2\sigma^{2}t},$
which establishes the claimed bound. ∎

##  IV Generalisaton Error Bounds

General bounds can be provided using Theorem 1 and the well-known Corollary 1.
However, to offer something even more meaningful to the reader, let us set-up
a very specific framework and restrict our assumptions further. Given a convex
functional $\varphi$, we will consider the following family of functionals
over measures $\psi^{\star}_{\mu}(\cdot)=D_{\varphi}(\cdot\|\mu)$, with $\mu$
a measure fixed beforehand. Consequently $\psi_{\mu}$ denotes the Legendre-
Fenchel dual of $D_{\varphi}(\cdot\|\mu)$ [17, Lemma 4.5.8]. We will assume,
as above, that given a function $f\in C_{c}(\mathcal{X})$, $\psi_{\mu}(\lambda
f)\leq\phi(\lambda)$ for some convex function $\phi$ and every $\lambda>0$.
Let us set ourselves in a classical learning setting. Let
$S=(Z_{1},\ldots,Z_{n})$ and $H=\mathcal{A}(S)$ be two random variables
respectively over the spaces
$(\mathcal{Z}^{n},\mathcal{F}_{\mathcal{Z}^{n}},\mathcal{P}_{S}\\!\\!=\\!\\!\mathcal{P}_{Z}^{\otimes
n})$, $(\mathcal{H},\mathcal{F}_{\mathcal{H}},\mathcal{P}_{H})$. Let
$\mathcal{P}_{S}\mathcal{P}_{H}$ denote the joint measure induced by the
product of the marginals of $S$ and $H$ over
$(\mathcal{Z}^{n}\times\mathcal{H},\mathcal{F})$. Let $S$ be the input of a
learning algorithm $\mathcal{A}$ and $H=\mathcal{A}(S)$ the corresponding
output, let $\mathcal{P}_{SH}$ be the joint measure induced by $\mathcal{A}$.
Assume, moreover, that $\mathcal{P}_{SH}\ll\mathcal{P}_{S}\mathcal{P}_{H}$.

In order to match the framework that is typically utilised in the Learning
Theory literature, we will work with
$\psi^{\star}_{\mathcal{P}_{S}\mathcal{P}_{H}}(\cdot)=D_{\varphi}(\cdot\|\mathcal{P}_{S}\mathcal{P}_{H})$
and, following the structure of Theorem 1, one has to assume something about
$\psi_{\mathcal{P}_{S}\mathcal{P}_{H}}$ in order to provide a bound that
involves $\psi^{\star}_{\mathcal{P}_{S}\mathcal{P}_{H}}$. However, our
assumptions (again, matching the literature) will involve
$\psi_{\mathcal{P}_{S}}$ or $\psi_{\mathcal{P}_{Z}}$. The reason why we can do
this is the following. Given the choice of
$\psi^{\star}_{\mu}=D_{\varphi}(\cdot\|\mu)$, we typically know the shape that
$\psi_{\mu}$ will have. If $\psi^{\star}_{\mu}$ is the KL divergence
$\psi_{\mu}(f)=\log\mu(\exp(f))$ while if $\psi^{\star}_{\mu}$ is a
$\varphi-$Divergence $\psi_{\mu}(f)=\mu(\varphi^{\star}(f))$ [14]. This
naturally implies that if we consider product measures, one has the following
characterisation for the dual
$\psi_{\mu\times\xi}(f)=\xi(\mu(\varphi^{\star}(f)))=\xi(\psi_{\mu}(f))$ for
$\varphi$-Divergences and
$\exp(\psi_{\mu\times\xi}(f))=\xi(\mu(\exp(f)))=\xi(\exp(\psi_{\mu}(f)))$ for
KL.

Consequently, since we will consider the product measure
$\mathcal{P}_{S}\mathcal{P}_{H}$ we have that, given the structure of the
dual, an upper-bound on $\psi_{\mathcal{P}_{S}}$ for every $h\in\mathcal{H}$
naturally implies an upper-bound on $\psi{\mathcal{P}_{S}\mathcal{P}_{H}}$.
Another important consideration is that, an assumption of the form
$\psi_{\mathcal{P}_{Z}}(\lambda(\ell(h,Z)-\mathcal{P}_{Z}(\ell(h,Z))))\leq\phi(\lambda)$
for every $h$ typically implies an assumption of the form
$\psi_{\mathcal{P}_{S}}(\frac{\lambda}{n}(\sum_{i}(\ell(h,Z_{i})-\mathcal{P}_{S}(\ell(h,Z_{i})))))\leq\phi(\lambda)/n$,
with $S$ a sequence of $n$ iid samples distributed according to
$\mathcal{P}_{Z}^{\otimes n}$, something that we will informally define as the
“n-sum property” of $\psi_{\mathcal{P}_{Z}},\psi_{\mathcal{P}_{S}}$ and
$\phi$. Under this framework, we can state the following result.

######  Corollary 2.

Let
$\psi^{\star}_{\mathcal{P}_{S}\mathcal{P}_{H}}(\cdot)=D_{\varphi}(\cdot\|\mathcal{P}_{S}\mathcal{P}_{H})$
for some convex functional $\varphi$. Assume that
$\psi_{\mathcal{P}_{S}\mathcal{P}_{H}}(\lambda(L_{S}(H)-\mathcal{P}_{H}(L_{\mathcal{P}}(H))))\leq\phi(\lambda)/n$
for every $h\in\mathcal{H}$ and $n,\lambda>0$. One has that

$\text{gen-
err}_{\mathcal{P}}(\mathcal{A},S)\leq\frac{{\phi^{\star}}^{-1}(nD_{\varphi}(\mathcal{P}_{SH}\|\mathcal{P}_{S}\mathcal{P}_{H}))}{n}.$
(18)

###### Proof.

Let us denote with $\phi_{n}(\lambda)=\frac{\phi(\lambda)}{n}$ one has that
$\phi_{n}^{\star}(\lambda^{\star})=\frac{1}{n}\phi^{\star}(\lambda n)$ and
consequently ${\phi_{n}^{\star}}^{-1}(t)=\frac{1}{n}{\phi^{\star}}^{-1}(nt).$
The statement then follows from Theorem 1. ∎

From this we can now easily recover all the bounds on the expected
generalisation-error that involve KL and that are present in the literature,
for instance:

######  Corollary 3.

Let $\varphi(x)=x\log x$ in Corollary 2, hence
$D_{\varphi}(\cdot\|\mathcal{P}_{S}\mathcal{P}_{H})$ is the KL-Divergence.
Assume that the loss function $\ell(h,Z_{i})$ is $\sigma^{2}$-sub-Gaussian
under $\mathcal{P}_{Z}$ for every $h$. We have that

$\text{gen-
err}_{\mathcal{P}}(\mathcal{A},S)\leq\sqrt{\frac{2\sigma^{2}I(S;\mathcal{A}(S))}{n}}.$
(19)

###### Proof.

Since $\ell(h,Z_{i})$ is $\sigma^{2}$-sub-Gaussian under $\mathcal{P}_{Z}$,
then
$\psi_{\mathcal{P}_{S}}\left(\frac{1}{n}\sum_{i}\lambda(\ell(h,Z_{i})-\mathcal{P}_{Z}(\ell(h,Z)))\right)\leq\frac{\phi(\lambda)}{n}.$
This implies that $\psi_{\mathcal{P}_{Z}},\psi_{\mathcal{P}_{S}}$ and $\phi$
satisfy the “$n$-sum property”. The argument then follows directly from
Corollary 2 along with the fact that
$\frac{1}{n}{\phi^{\star}}^{-1}(nt)=\sqrt{\frac{2\sigma^{2}t}{n}}.$ ∎

######  Remark 2.

Both Corollary 1 and 3 have appeared in the literature in a variety of forms
[10, Prop. 1], [1, Lemma 1].

To conclude the section and emphasise the generality of this approach, let us
choose a different divergence.

######  Corollary 4.

Let $\varphi(x)=\frac{x^{2}}{2}$ in Corollary 2, hence
$\psi^{\star}_{\mathcal{P}_{S}\mathcal{P}_{H}}(\cdot)=D_{\varphi}(\cdot\|\mathcal{P}_{S}\mathcal{P}_{H})=(\chi^{2}(\cdot\|\mathcal{P}_{S}\mathcal{P}_{H})+1)/2$.
Assume that given the loss function $\ell(h,Z_{i})$ there exists a constant
$K>0$ such that for every $h$
$\mathcal{P}_{Z}((\lambda(\ell(h,Z_{i})-\mathcal{P}_{Z}(\ell(h,Z)))^{2})\leq
K\lambda^{2}$ We have that

$\text{gen-
err}_{\mathcal{P}}(\mathcal{A},S)\leq\sqrt{\frac{2K(\chi^{2}(\mathcal{P}_{SH}\|\mathcal{P}_{S}\mathcal{P}_{H})+1)}{n}}.$
(20)

###### Proof.

Given that
$\psi^{\star}_{\mathcal{P}_{S}\mathcal{P}_{H}}(\nu)=\frac{1}{2}(\chi^{2}(\nu\|\mathcal{P}_{S}\mathcal{P}_{H})+1)$
one has that
$\psi_{\mathcal{P}_{S}\mathcal{P}_{H}}(f)=\frac{1}{2}\mathcal{P}_{S}\mathcal{P}_{H}(f^{2})$.
Since the $Z_{i}$ are assumed to be iid random variables the variables
$\ell(h,Z_{i})$ are also iid and by assumption one has that
$\mathcal{P}_{S}((\lambda\frac{1}{n}\sum_{i}(\ell(h,Z_{i})-\mathcal{P}_{Z}(\ell(h,Z)))^{2})\leq\frac{\lambda^{2}}{n}K$,
hence $\psi_{\mathcal{P}_{Z}},\psi_{\mathcal{P}_{S}}$ and $\phi$ satisfy the
“$n$-sum property”. The argument then follows from Corollary 2 and by noticing
that $\phi^{\star}(\lambda^{\star})=\frac{{\lambda^{\star}}^{2}}{2K}$ which in
turn implies that ${\phi^{\star}}^{-1}(t)=\sqrt{2Kt}.$ ∎

######  Remark 3.

Assuming the $\sigma^{2}$-sub-Gaussianity of
$\ell(h,Z_{i})-\mathcal{P}_{Z}(\ell(h,Z))$ naturally implies a bound on
$\mathcal{P}_{Z}((\lambda(\ell(h,Z_{i})-\mathcal{P}_{Z}(\ell(h,Z)))^{\kappa})$
for every $\kappa\geq 1$. For instance, $\sigma^{2}$-sub-Gaussianity implies
that in Corollary 4,
$\mathcal{P}_{Z}((\lambda(\ell(h,Z_{i})-\mathcal{P}_{Z}(\ell(h,Z)))^{2})\leq
K\lambda^{2}$ holds with $K=2\sigma^{2}e^{2/e}$. However, assuming that $\ell$
has bounded variance (for every $h$ or on expectation wrt $\mathcal{P}_{H}$)
is much less restrictive than assuming it is sub-Gaussian. As an example of
this, suppose that the loss $\ell$ is $\sigma^{2}$-sub-Gaussian. One has that
$\ell^{2}$ is sub-Exponential with parameters
$(4\sqrt{2}\sigma^{2},4\sigma^{2})$. This means that $\ell^{2}$ has a finite
log-moment generating function only for $\lambda<1/(4\sigma^{2}).$ Considering
the framework given by Theorem 1 and Corollary 3, in order to solve the
infimum in (11) (which, in turn, provides Eq (19)), one needs to select
$\lambda^{\star}=\sqrt{\frac{2I(S;H)}{\sigma^{2}}}.$ Consequently, if
$I(S;H)\geq\frac{1}{2^{5}\sigma^{2}}$ the bound is not valid as, for that
choice of $\lambda$, the log-moment generating function of $\ell$ with respect
to $\mathcal{P}_{S}\mathcal{P}_{H}$ is actually unbounded (and, thus, cannot
be bounded by $\phi(\lambda)$). On the other hand, a sub-Exponential random
variable is such that all of its moments are bounded, hence, an approach as
the one suggested by Corollary 4 can be successful.

###  IV-A Recovering other known results

Other known results can be recovered, for instance noticing that $\text{gen-
err}_{\mathcal{P}}(\mathcal{A},S)$ can be re-written as
$\frac{1}{n}\sum_{i=1}^{n}\left(\mathcal{P}_{HZ}(\ell(H,Z_{i}))-\mathcal{P}_{H}\mathcal{P}_{Z}(\ell(H,Z))\right)$
and using Corollary 1 on each term inside the summation gives us the main
result in [8, Thm. 2].

Alternatively, the observation that one can consider a super-sample
$\tilde{S}$ of length $2n$ and take two random subsets of length $n$
$S,S^{\prime}$ independently, allows us to rewrite the generalisation error as
follows $\text{gen-
err}_{\mathcal{P}}(\mathcal{A},\tilde{S})=\mathcal{P}_{\tilde{S}}(\mathcal{P}_{SH|\tilde{S}}(L_{\tilde{S}}(H)-L_{\mathcal{P}}(H)))$.
One can then use Theorem 1 for every given choice of $\tilde{S}$ on
$\mathcal{P}_{SH|\tilde{S}=\tilde{s}}(L_{\tilde{S}}(H)-L_{\mathcal{P}}(H))$
and recover [9, Thm 5.1, Corollary 5.2, 5.3]. It represents a bound involving
$D(\mathcal{P}_{SH|\tilde{S}=\tilde{s}}\|\mathcal{P}_{S|\tilde{S}=\tilde{s}}\mathcal{P}_{H|\tilde{S}=\tilde{s}})$
after assuming/showing that
$\psi_{\mathcal{P}_{S|\tilde{S}=\tilde{s}}\mathcal{P}_{H|\tilde{S}=\tilde{s}}}(\lambda(L_{\tilde{s}}(H)-L_{\mathcal{P}}(H)))\leq\frac{\lambda^{2}}{2n}c(\tilde{s})$
with $c(\tilde{s})$ a constant that depends on the realisation of $\tilde{S}$.
Clearly the possible combinations are numerous, however the pattern remains
the same: a bound on the dual of the targeted divergence (or functional of
measure) implies a bound on a difference of expectations. Indeed, still
following the approach undertaken in [8] but with the general spirit that
characterises this work, one can show the following: $\text{gen-
err}_{\mathcal{P}}(\mathcal{A},S)\leq\frac{1}{n}\sum_{i=1}^{n}\sqrt{2K(\chi^{2}(\mathcal{P}_{Z_{i}H}\|\mathcal{P}_{Z_{i}}\mathcal{P}_{H})+1)}.$
Otherwise, following [9] one can recover bounds involving
$\mathcal{P}_{\tilde{S}}\left(\chi^{2}\left(\mathcal{P}_{SH|\tilde{S}}\|\mathcal{P}_{S|\tilde{S}}\mathcal{P}_{H|\tilde{S}}\right)\right)$.

##  V Transportation-Cost inequalities

A recurring theme in the field that lies at the intersection between
Information Theory and Optimal Transport is showing that Transportation-Cost
Inequalities are equivalent to some form of concentration of measure. One such
example is Theorem$\,\diamond$ in Section II-A. An in-depth review of this
connection can be found in [12, Section 3.4]. This type of results are
generally made of two parts: the “if part” (if $\mu$ satisfies concentration
for every function in some family then the $T_{p}(c)$ holds) and the “only if”
part (if $\mu$ satisfies a $T_{p}(c)$ inequality then one has concentration
for every function in some family). So far we have essentially established the
“if part” for general functionals of measures. Let us now establish the “only
if” part and then discuss how it relates to the classical framework.

######  Theorem 2.

Let $\psi:\mathcal{M}(\mathcal{X})\to\mathbb{R}$ be a functional and let
$f\in\mathcal{M}(\mathcal{X})^{\star}$. If there exist a Young function $\phi$
and its complementary function $\phi^{\star}$which admits a generalised
inverse ${\phi^{\star}}^{-1}$ such that for every $\nu$ with $\nu(f)<+\infty$
one has

$\nu(f)\leq{\phi^{\star}}^{-1}\left(\psi(\nu)\right),$ (21)

then

$\psi^{\star}(\lambda f)\leq\phi(\lambda)\text{ for every }\lambda>0,$ (22)

where $\psi^{\star}:\mathcal{M}(\mathcal{X})^{\star}\to\mathbb{R}$ is the
Legendre-Fenchel dual of $\psi$.

###### Proof.

Given that $\phi$ is a Young function, one has that by [15, Lemma 2.4]

$\displaystyle\nu(f)$
$\displaystyle\leq{\phi^{\star}}^{-1}\left(\psi(\nu)\right)=\inf_{\lambda>0}\frac{\phi(\lambda)+\psi(\nu)}{\lambda}.$
(23)

This means that for every $\lambda>0$ and every $\nu$-integrable function $f$,

$\phi(\lambda)\geq\lambda\nu(f)-\psi(\nu).$ (24)

Taking the supremum with respect to $\nu\in\mathcal{M}(\mathcal{X})$ one
recovers the statement: $\phi(\lambda)\geq\psi^{\star}(\lambda f).$ ∎

In order to see how Theorem 1 and Theorem 2 represent, respectively, the “if”
and “only if” part connecting $T_{p}(c)-$like inequalities to concentration
let us recover Theorem$\,\diamond$. In particular, select

  * •

$\psi^{\star}(\nu)=D(\nu\|\mu)$ for a given $\mu$ (consequently, one has that
$\psi(\lambda f)=\log\mu(\exp(\lambda f))$, cf. [17, Lemma 6.2.13]);

  * •

$\phi(\lambda)=\frac{c\lambda^{2}}{2}$ (which implies
${\phi^{\star}}^{-1}(\kappa)=\sqrt{2c\kappa}$);

Theorem 1 is what allows us to reach (5) starting from (4). Keeping the same
$\phi$ but inverting the roles of $\psi$ and $\psi^{\star}$ in Theorem 2 is
what allows us to reach (4) starting from (5). Some extra technical steps are
necessary in order to bring in Wasserstein Distances (which will be considered
in the proof just below). Given the generality of the results we can, as an
example, consider a setting similar to Theorem$\,\diamond$ but involving a
different divergence:

######  Theorem 3.

Let $\mu\in\mathcal{P}_{1}(\mathcal{X})$ and $\beta>1$. There exists a $c$
such that for every $\lambda$ and every $1$-Lipschitz function $f$

$\mu\left(|\lambda f|^{\beta}\right)\leq(c\lambda)^{\beta},$ (25)

if and only if, for every $\nu\ll\mu$

$\displaystyle W_{1}(\mu,\nu)$ $\displaystyle\leq\left(\alpha
c^{\alpha}H_{\alpha}(\nu\|\mu)\right)^{\frac{1}{\alpha}},$ (26)

where $\alpha=\frac{\beta}{\beta-1}.$ Setting $\beta=2$ we recover the
following:

$W_{1}(\mu,\nu)\leq\sqrt{c^{2}2(\chi^{2}(\nu\|\mu)+1)}.$ (27)

###### Proof.

Let $\mu$ be a probability measure and let
$\psi^{\star}(\nu)=H_{\alpha}(\nu\|\mu)$ with $\alpha>1$, one has that
$\psi(f)=\frac{\mu(|f|^{\beta})}{\beta}$ (cf. [14, Theorem 3.3]). Moreover,
let $\phi(\lambda)=\frac{|c\lambda|^{\beta}}{\beta}$, one has that
$\phi_{Y}^{\star}(\lambda^{\star})=\frac{|\lambda^{\star}/c|^{\alpha}}{\alpha}$
with $\alpha=\frac{\beta}{\beta-1}$. Consequently, for positive $\kappa$,
${\phi^{\star}}^{-1}(\kappa)=(\alpha c^{\alpha}\kappa)^{\frac{1}{\alpha}}.$
Let $f$ be a function such that $\left\lVert f\right\rVert_{Lip}\leq 1$ and
$\mu(f)=0$. Assume that for every $\nu\ll\mu$, $W_{1}(\mu,\nu)\leq(\alpha
c^{\alpha}$ $H_{\alpha}(\nu\|\mu))^{\frac{1}{\alpha}}$. By the Kantorovich-
Rubenstein dual representation of $W_{1}$ one has that

$W_{1}(\mu,\nu)=\sup_{f:\left\lVert f\right\rVert_{Lip}\leq
1}\left|\mu(f)-\nu(f)\right|.$ (28)

Hence, for every function $f$ such that $\left\lVert f\right\rVert_{Lip}\leq
1$, $\mu(f)=0$ one can rewrite Equation 27 as follows:

$\nu(f)\leq(\alpha
c^{\alpha}H_{\alpha}(\nu\|\mu))^{\frac{1}{\alpha}}={\phi^{\star}}^{-1}(H_{\alpha}(\nu\|\mu)).$
(29)

Consequently, by Theorem 2 one has that for every such $f$

$\psi^{\star}(\lambda f)=\mu\left(\frac{|\lambda
f|^{\beta}}{\beta}\right)\leq\frac{(c\lambda)^{\beta}}{\beta}=\phi(\lambda).$
(30)

Similarly, assuming (30) leads to (29) for every such $f$ via Theorem 1.
Repeating the same argument with -$f$ one reaches the following statement:

$|\mu(f)-\nu(f)|\leq(\alpha
c^{\alpha}H_{\alpha}(\nu\|\mu))^{\frac{1}{\alpha}}.$ (31)

The assumption that $\mu(f)=0$, can be dropped replacing $f$ with $f-\mu(f)$.
Taking then the supremum over all the $1-$Lipschitz functions $f$ in (31) and
using again the Kantorovich-Rubenstein duality formula for Wasserstein
Distances one reaches that for every $\nu\ll\mu$,

$W_{1}(\mu,\nu)\leq(\alpha
c^{\alpha}H_{\alpha}(\nu\|\mu))^{\frac{1}{\alpha}}.$

∎

Drawing inspiration from Theorem 3 one can consider almost any
$\varphi-$Divergence. Some restrictions on the possible choices of $\varphi$
arise naturally in order to have access to both variational representations
(cf. [14, Theorems 3.3, 3.4]).

######  Remark 4.

In the classical $T_{1}(c)$-setting one assumes that $\log(\mu(\exp(\lambda
f)))\leq\frac{\lambda^{2}c^{2}}{2}$ for every $f$ that is $1-$Lipschitz and
consequently recovers (5). Considering Theorem 3 instead, in Eq. (25) we are
only asking for the $\beta$-th moment to be bounded. The same argument as in
Remark 3 holds: even though it is well known that $\chi^{2}(\nu\|\mu)\geq
D(\nu\|\mu)$ (leading thus, to a worse bound on $W_{1}$), in order to get (27)
we only need to bound the second moment of $f$ with respect to $\mu$ and such
a bound can exist for functions with unbounded log-moment generating function,
which are excluded from a classical $T_{1}(c)$ setting (cf. Remark 3).

Theorem 3 highlights the following approach: starting from the variational
representation of Wasserestein distances $W_{p}$ one understands the
restriction on the family of functions that needs to be considered (cf.
Equation (28)). Let us denote such a family with $\mathcal{F}_{p}$. The next
step is then to fix a measure $\mu$ and a functional $\psi^{\star}_{\mu}$ (in
Theorem 3, the choice of $\psi^{\star}_{\mu}$ has fallen on the Hellinger
integral). The upper-bound that one can provide on $\psi(\lambda f)$ for
$f\in\mathcal{F}_{p}$, characterised by $\phi(\lambda)$ (cf. Equations (4),
(7) and (25)), will determine the shape of the $T_{p}(c)$-like inequality
(through ${\phi^{\star}}^{-1}$, cf. Equations (5), (8) and (26)), here denoted
$\phi_{p}$-inequalities for convenience. Vice versa, bounding a Wasserstein
distance $W_{p}$ through a divergence $\psi^{\star}_{\mu}(\nu)$ via a
$\phi_{p}$-inequality (cf. Equations (5), (21) and (26)) implies a bound on
the dual $\psi_{\mu}$ (cf. Equations (4), (22) and (25)) and that can imply
concentration according to $\psi_{\mu}$, $\phi$ and $\mathcal{F}_{p}$.

##  VI Conclusions

In this work we linked transportation-cost inequalities with generalisation
error bounds. The thread connecting the two approaches is Legendre-Fenchel
duality. As a result, we managed to generalise both approaches to various
divergences and to random variables that are not necessarily sub-Gaussian. The
approach undertaken in this work grants us two extra degrees of freedom:
$\psi^{\star}$ and $\phi$. The functional $\psi^{\star}$ is not necessarily
tied to be the KL-Divergence and the function $\phi$ can be any convex
function that allows us to upper-bound $\psi(\lambda f)$. In the case of KL
and its dual this is tantamount to showing concentration properties of $\mu$.
Assuming a Gaussian-like behaviour of the log-moment generating function
(hence, choosing $\phi(\lambda)=c\lambda^{2}/2$) leads to the familiar
$\sqrt{2cD(\nu\|\mu)}$. On the other hand, trying to show a classical
$T_{p}(c)$-like inequality for some measure $\mu$ while fixing the shape of
the inequality to be approximately $W_{p}(\mu,\nu)\leq\sqrt{cD(\nu\|\mu)}$
(which means, essentially, fixing $\phi$) can be impossible. This depends on
the concentration properties of $\mu$ or the family of functions that we have
to consider $\mathcal{F}_{p}$. One can thus relax the inequality by either
assuming a behaviour of the cumulant generating function that is different
from Gaussian-like (same $\psi^{\star}$ but different $\phi$) or by picking a
completely different divergence (changing $\psi^{\star}$ and/or $\phi$).

## Acknowledgment

The authors would like to thank Professor Ugo Vaccaro for insightful comments
and suggestions on an early draft of this work. The work in this paper was
supported in part by the Swiss National Science Foundation under Grant 200364.

## References

  * [1] A. Xu and M. Raginsky, “Information-theoretic analysis of generalization capability of learning algorithms,” in _Advances in Neural Information Processing Systems_ , 2017, p. 2521–2530.
  * [2] R. Bassily, S. Moran, I. Nachum, J. Shafer, and A. Yehudayoff, “Learners that use little information,” ser. Proceedings of Machine Learning Research, vol. 83. PMLR, 07–09 Apr 2018, pp. 25–55.
  * [3] H. Wang, M. Diaz, J. C. S. S. Filho, and F. P. Calmon, “An information-theoretic view of generalization via Wasserstein distance,” _2019 IEEE International Symposium on Information Theory (ISIT)_ , pp. 577–581, 2019.
  * [4] A. T. Lopez and V. S. Jog, “Generalization error bounds using wasserstein distances,” _2018 IEEE Information Theory Workshop (ITW)_ , pp. 1–5, 2018\.
  * [5] A. Pensia, V. Jog, and P.-L. Loh, “Generalization error bounds for noisy, iterative algorithms,” _2018 IEEE International Symposium on Information Theory (ISIT)_ , pp. 546–550, 2018.
  * [6] Y. Bu, S. Zou, and V. V. Veeravalli, “Tightening mutual information based bounds on generalization error,” _IEEE Journal on Selected Areas in Information Theory_ , pp. 1–1, 2020.
  * [7] A. R. Esposito, M. Gastpar, and I. Issa, “Generalization error bounds via Rényi-, $f$-divergences and Maximal Leakage,” _IEEE Transactions on Information Theory_ , vol. 67, no. 8, pp. 4986–5004, 2021.
  * [8] Y. Bu, S. Zou, and V. V. Veeravalli, “Tightening mutual information based bounds on generalization error,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 587–591.
  * [9] T. Steinke and L. Zakynthinou, “Reasoning About Generalization via Conditional Mutual Information,” in _Proceedings of Thirty Third Conference on Learning Theory_ , ser. Proceedings of Machine Learning Research, J. Abernethy and S. Agarwal, Eds., vol. 125. PMLR, 09–12 Jul 2020, pp. 3437–3452. [Online]. Available: https://proceedings.mlr.press/v125/steinke20a.html
  * [10] D. Russo and J. Zou, “Controlling bias in adaptive data analysis using information theory,” in _Proceedings of the 19th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, vol. 51. PMLR, 09–11 May 2016, pp. 1232–1240.
  * [11] C. Villani, _Optimal Transport: Old and New_. Springer Science & Business Media, 2008.
  * [12] M. Raginsky and I. Sason, _Concentration of Measure Inequalities in Information Theory, Communications, and Coding: Second Edition_. Now Foundations and Trends, 2014.
  * [13] S. Bobkov and F. Götze, “Exponential integrability and transportation cost related to logarithmic sobolev inequalities,” _Journal of Functional Analysis_ , vol. 163, no. 1, pp. 1 – 28, 1999.
  * [14] M. Broniatowski and A. Keziou, “Minimization of divergences on sets of signed measures,” _Studia Scientiarum Mathematicarum Hungarica_ , vol. 43, 03 2010\.
  * [15] S. Boucheron, G. Lugosi, and P. Massart, _Concentration Inequalities: A Nonasymptotic Theory of Independence_. Oxford University Press, 2013.
  * [16] A. Ruderman, M. D. Reid, D. García-García, and J. Petterson, “Tighter variational representations of f-divergences via restriction to probability measures,” in _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , ser. ICML’12. Madison, WI, USA: Omnipress, 2012, p. 1155–1162.
  * [17] A. Dembo and O. Zeitouni, _Large Deviations Techniques and Applications_ , ser. Stochastic Modelling and Applied Probability. Springer Berlin Heidelberg, 2009. [Online]. Available: https://books.google.ch/books?id=d3nnjwEACAAJ