Tighter Expected Generalization Error Bounds via Wasserstein Distance
Year: 2022

Abstract:
This work presents several expected generalization error bounds based on the Wasserstein distance. More specifically, it introduces full-dataset, single-letter, and random-subset bounds, and their analogues in the randomized subsample setting from Steinke and Zakynthinou [1]. Moreover, when the loss function is bounded and the geometry of the space is ignored by the choice of the metric in the Wasserstein distance, these bounds recover from below (and thus, are tighter than) current bounds based on the relative entropy. In particular, they generate new, non-vacuous bounds based on the relative entropy. Therefore, these results can be seen as a bridge between works that account for the geometry of the hypothesis space and those based on the relative entropy, which is agnostic to such geometry. Furthermore, it is shown how to produce various new bounds based on different information measures (e.g., the lautum information or several f -divergences) based on these bounds and how to derive similar bounds with respect to the backward channel using the presented proof techniques.

heading: 1 Introduction
text: A learning algorithm is a mechanism that takes a dataset s = (z1, . . . , zn) of n samples zi ∈ Z taken i.i.d. from a distribution PZ as an input, and produces a hypothesis w ∈ W by means of the conditional probability distribution PW |S .
The ability of a hypothesis w to characterize a sample z is described by the loss function `(w, z) ∈ R. More precisely, a hypothesis w describes well the samples from a population PZ when its population risk, i.e., LPZ (w) , E[`(w,Z)], is low. However, the distribution PZ is often not available and the empirical risk on the dataset s, i.e., Ls(w) , 1n ∑n i=1 `(w, zi), is considered as a proxy. Therefore, it is of interest to study the discrepancy between the population and empirical risks, which is defined as the generalization error: gen(w, s) , LPZ (w)−Ls(w). Classical approaches bound the generalization error in expectation and in probability (PAC Bayes) either by studying the complexity and the geometry of the hypothesis’ space W or by exploring properties of the learning algorithm itself; see, e.g., [2, 3] for an overview.
More recently, the relationship (or amount of information) between the generated hypothesis and the training dataset has been used as an indicator of the generalization performance. In [4], based on
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
[5], it is shown that the expected generalization error, i.e., gen(W,S) , E[gen(W,S)], is bounded from above by a function that depends on the mutual information between the hypothesis W and the dataset S with which it is trained, i.e., I(W ;S). However, this bound becomes vacuous when I(W ;S) → ∞, which occurs for example when W and S are separately continuous and W is a deterministic function of S. To address this issue, it is shown in [6] that the generalization error is also bounded by a function on the dependency between the hypothesis and individual samples, I(W ;Zi), which is usually finite due to the smoothing effect of marginalization. Following this line of work, in [7], the authors present data-dependent bounds based on the relationship between the hypothesis and random subsets of the data, i.e., DKL(PW |s ‖ PW |sjc ) where j ⊆ [n]. After that, a more structured setting is introduced in [1], studying instead the relationship between the hypothesis and the identity of the samples. The authors consider a super-sample of 2n i.i.d. instances z̃i from PZ , i.e., s̃ = (z̃1, . . . , z̃2n). This super sample is used to construct the dataset s by choosing between the samples z̃i and z̃i+n using a Bernoulli random variable Ui with probability 12 , i.e., zi = z̃i+uin. In this paper, the two settings are referred to as the standard and randomized-subsample settings.1 In the randomized-subsample setting, the empirical generalization error is defined as the difference between the empirical risk on the samples from s̃ not used to obtain the hypothesis, i.e., s̄ = s̃ \ s, and the empirical risk on the dataset s, i.e.,
ĝen(w, s̃, u) , L̄s(w)−Ls(w) = 1
n ∑n i=1 ( `(w, z̃i+(1−ui)n)− `(w, z̃i+uin) ) ,
where u is the sequence of n i.i.d. Bernoulli trial outcomes ui. The expected value of the empirical and the (standard) generalization errors coincide, i.e., E[ĝen(W, S̃, U)] = gen(W,S). Also, the expected generalization error is controlled by the conditional mutual information between the hypothesis W and the Bernoulli trials U , given the super sample S̃ [1], i.e., I(W ;U |S̃), by the individual conditional mutual information [9], i.e., I(W ;Ui|Z̃i, Z̃i+n), and by the “disintegrated” mutual information with a subset UJ of the Bernoulli trials [10], i.e.,DKL(PW |S̃,U ‖PW |S̃,UJc ). A highlight of this setting is that these conditional notions of information are always finite [1] and smaller than their “unconditional” counterparts [10], e.g., I(W ;U |S̃) ≤ I(W ;S) and I(W ;U |S̃) ≤ n log(2). Some steps towards unifying these results are taken in [8], where the authors develop a framework that makes it possible to recover the expected generalization error bounds based on the mutual information I(W ;S) and the conditional mutual information I(W ;U |S̃). Then, the aforementioned framework is further exploited in [9] to recover the single-sample and the random-subsets bounds, which are based on I(W ;Zi), DKL(PW |S ‖PW |SJc ), andDKL(PW |S̃,U ‖PW |S̃,UJc ), and to generate new individual conditional mutual information bounds, i.e., I(W ;Ui|Z̃i, Z̃i+n). Finally, in [11, 12], other systematic ways to recover some of the said bounds and obtain similar new ones are studied.
In parallel, there were some attempts to bridge the gap between employing the geometry and complexity of the hypothesis space and the relationship between the hypothesis and the training samples. In [13], the authors bound gen(W,S) with a function of weighted dependencies between the dataset and increasingly finer quantizations of the hypothesis, i.e., {2−k/2I([W ]k;S)}k, which can be finite even if I(W ;S)→∞. This result stems from a clever usage of the chaining technique [14, Theorem 5.24], and a comparison with this kind of approaches is given in Appendix A. Later, in [15] and [16], it is shown that the expected generalization error is bounded from above by a function of the Wasserstein distance between the hypothesis distribution after observing the dataset PW |S and its prior PW , i.e., Wp(PW |S , PW ), and by a function of the Wasserstein distance between the hypothesis distribution after observing a single sample PW |Zi and its prior PW , i.e., Wp(PW |Zi , PW ), which are finite when a suitable metric is chosen but are difficult to evaluate. Concurrently, in [17] it is shown that a similar result holds, if the metric is the Minkowski distance, for the distribution of the data PS and the backward channel PS|W , i.e., Wpp,‖·‖(PS|W , PS).
The main contributions of this paper are the following:
• It introduces new, tighter single letter and random-subset Wasserstein distance bounds for the standard and randomized-subsample settings (Theorems 1, 2, 3, and 4).
• It shows that when the loss is bounded and the geometry of the space is ignored, these bounds recover from below (and thus are tighter than) the current relative entropy and mutual
1In [8] the latter is called the random-subset setting. However, this may cause confusion with the randomsubset bounds in the present work.
information bounds on both the standard and randomized-subsample settings. In fact, they are also tighter when the loss is additionally subgaussian or under certain milder conditions on the geometry. However, these results are deferred to Appendix B to expose the main ideas more clearly. Moreover, Corollaries 1 and 2 overcome the issue of potentially vacuous relative entropy bounds on the standard setting.
• It introduces new bounds based on the backward channel, which are analogous to those based on the forward channel and more general than previous results in [17].
• It shows how to generate new bounds based on a variety of information measures, e.g., the lautum information or several f -divergences like the Hellinger distance or the χ2-divergence, thus making the characterization of the generalization more flexible.

heading: 2 Preliminaries

heading: 2.1 Notation
text: Random variables X are written in capital letters, their realizations x in lower-case letters, their set of outcomes X in calligraphic letters, and their Borel σ-algebras X in script-style letters. Moreover, the probability distribution of a random variable X is written as PX : X→ [0, 1]. Hence, the random variable X or the probability distribution PX induce the probability space (X ,X, PX). When more than one random variable is considered, e.g.,X and Y , their joint distribution is written as PX,Y : X⊗ Y→ [0, 1] and their product distribution as PX ⊗ PY : X⊗ Y→ [0, 1]. Moreover, the conditional probability distribution of Y given X is written as PY |X : Y⊗X → [0, 1] and defines a probability distribution PY |X=x (or PY |x for brevity) over Y for each element x ∈ X . Finally, there is an abuse of notation writing PX,Y = PY |X × PX since PX,Y (B) = ∫ ( ∫ χB ( (x, y) ) dPY |X=x(y) ) dPX(x) for all B ∈ X⊗Y, where χB is the characteristic function of the set B. The natural logarithm is log.

heading: 2.2 Necessary definitions, remarks, claims, and lemmas
text: Definition 1. Let ρ : X × X → R+ be a metric. A space (X , ρ) is Polish if it is complete and separable. Throughout it is assumed that all Polish spaces (X , ρ) are equipped with the Borel σ-algebra X generated by ρ. When there is no ambiguity, both the metric space (X , ρ) and the generated measurable space (X ,X) are written as X . Definition 2. Let (X , ρ) be a Polish metric space and let p ∈ [1,∞). Then, the Wasserstein distance of order p between two probability distributions P and Q on X is
Wp(P,Q) , (
inf R∈Π(P,Q)
∫
X×X ρ(x, y)pdR(x, y)
)1/p ,
where Π(P,Q) is the set of all couplings R of P and Q, i.e., all joint distributions on X × X with marginals P and Q, that is, P (B) = R(B,X ) and Q(B) = R(X , B) for all B ∈ X. Remark 1. Hölder’s inequality implies that Wp ≤Wq for all p ≤ q [18, Remark 6.6]. Hence, since this work is centered on upper bounds the focus is on W , W1. Definition 3. A function f : X → R is said to be L-Lipschitz under the metric ρ, or simply f ∈ L-Lip(ρ), if |f(x)− f(y)| ≤ Lρ(x, y) for all x, y ∈ X . Lemma 1 (Kantorovich-Rubinstein duality [18, Remark 6.5]). Let P1(X ) be the space of probability distributions on X with a finite first moment. Then, for any two distributions P and Q in P1(X )
W(P,Q) = sup f∈1-Lip(ρ)
{∫
X f(x)dP (x)−
∫
X f(x)dQ(x)
} . (KR duality)
Definition 4. The total variation between two probability distributions P and Q on X is TV(P,Q) , supA∈X { P (A)−Q(A)}.
Definition 5. The discrete metric is ρH(x, y) , 1[x 6= y], where 1 is the indicator function. Remark 2. A bounded function f : X → [a, b] is (b− a)-Lipschitz under the discrete metric ρH. Remark 3. The Wasserstein distance of order 1 is dominated by the total variation. For instance, if P and Q are two distributions on X then W(P,Q) ≤ dρ(X )TV(P,Q), where dρ(X ) is the diameter of X . In particular, when the discrete metric is considered W(P,Q) = TV(P,Q) [18, Theorem 6.15].
Lemma 2 (Pinsker’s and Bretagnolle–Huber’s (BH) inequalities). Let P and Q be two probability distributions on X and define Ψ(x) , √ min{x/2, 1− exp(−x)}, then [19, Theorem 6.5] and [20, Proof of Lemma 2.1] state that TV(P,Q) ≤ Ψ(DKL(P ‖Q)).

heading: 3 Expected Generalization Error Bounds
text: This section presents our main results. First, in §3.1 and §3.2, single-letter and random-subset bounds based on the Wasserstein distance are introduced for the studied settings. These subsections also show how these bounds are tighter than current bounds based on the Wasserstein distance and the relative entropy. Moreover, an example where these bounds outperform current bounds is provided. Then, in §3.3 it is shown how to obtain analogous bounds to those in §3.1 and §3.2 for the backward channel. Finally, §3.4 shows how the presented results lead to a rich set of new bounds based on different information measures. All complete proofs and technical details are deferred to the appendix.

heading: 3.1 Standard setting
text: In [15, Theorem 2], the authors show that the expected generalization error is bounded from above by the Wasserstein distance between the forward channel distribution PW |S and the marginal distribution of the hypothesis PW . More specifically, when the loss function ` is L-Lipschitz under a metric ρ for all z ∈ Z and the hypothesis spaceW is Polish, then∣∣gen(W,S) ∣∣ ≤ LE [ W(PW |S , PW ) ] = L ∫
Zn W(PW |S=s, PW )dP⊗nZ (s). (1)
This bound considers both the geometry of the hypothesis space by means of the metric ρ and the dependence between the hypothesis and the dataset via the discrepancy between the forward channel PW |S and the marginal PW . Nonetheless, it is not clear how it relates with other results agnostic to the geometry of the space. For instance, when the loss function ` is bounded in [a, b], if the geometry is ignored (i.e., the discrete metric is considered), then∣∣gen(W,S) ∣∣ ≤ (b− a)E [ TV(PW |S , PW ) ] ≤ (b− a)Ψ(I(W ;S)),
where the inequalities follow from Remark 2, Lemma 2, and Jensen’s inequality (note Ψ(x), defined in Lemma 2, is concave on x). This result compares negatively with other results employing the mutual information, e.g., [4, Theorem 1], where the bound has a decaying factor of 1/ √ n.
Nonetheless, it is possible to find a single-letter version of [15, Theorem 2] using a similar strategy to [6, Proposition 1] and [9, Propositions 1 and 3], which generalizes [16, Theorem 1] to algorithms that may consider the ordering of the samples. More concretely, the expected generalization error is controlled by a function of the Wasserstein distance of the hypothesis’ distribution before and after observing a single sample Zi, i.e., W(PW |Zi , PW ). Theorem 1. Suppose that the loss function ` is L-Lipschitz for all z ∈ Z and that the hypothesis spaceW is Polish. Then,
∣∣gen(W,S) ∣∣ ≤ L
n
n∑
i=1
E [ W(PW |Zi , PW ) ] .
Moreover, when the loss function is bounded and the geometry of the space is ignored by considering the discrete metric, this single-letter result can improve upon current relative entropy and mutual information bounds. Corollary 1. Under the conditions of Theorem 1, if the loss ` is bounded in [a, b], then ∣∣gen(W,S)
∣∣ ≤ b− a n ∑n i=1 E [ TV(PW |Zi , PW ) ] ≤ b− a n ∑n i=1 E [ Ψ ( DKL(PW |Zi ‖ PW ) )]
Corollary 1 improves upon [6, Proposition 1] in two different ways. First, it pulls the expectation with respect to the samples PZi outside of the concave square root, thus strengthening that result via Jensen’s inequality. Second, the addition of the BH inequality ensures that heavily influential samples (high I(W ;Zi)) do not contribute too negatively to the bound, which is ensured to be non-vacuous. Moreover, contrarily to (1), a further application of Jensen’s inequality and [6, Proposition 2] indicates that Corollary 1 compares positively to [4, Theorem 1], exhibiting the decaying factor of 1/ √ n,
∣∣gen(W,S) ∣∣ ≤ b− a
n
n∑
i=1
E [ W(PW |Zi , PW ) ] ≤ (b− a)Ψ (I(W ;S) n
) ≤ √
(b− a)2I(W ;S) 2n .
(2)
It is also possible to obtain a random-subset version of [15, Theorem 2] using a similar strategy to [9, Propositions 2 and 4]. This kind of bounds, rather than looking at how knowing a single sample Zi modifies the hypothesis distribution, i.e., W(PW |Zi , PW ), look at how the knowledge of a set of samples SJ alters the hypothesis distribution when all the other samples, SJc , used to obtain the hypothesis are known too, i.e., W (PW |S , PW |SJc ). Theorem 2. Suppose that the loss function ` is L-Lipschitz for all z ∈ Z and that the hypothesis space W is Polish. Let J be a uniformly random subset of [n] such that |J | = m, and that is independent of W and S. Let also R be a random variable independent of S and J . Then,
∣∣gen(W,S) ∣∣ ≤ LE [ W(PW |S,R, PW |SJc ,R) ] and ∣∣gen(W,S) ∣∣ ≤ L
m E [∑ i∈J E [ W(PW |SJc∪Zi,R, PW |SJc ,R) | J ]] .
In particular, when m = 1, the two equations from Theorem 2 reduce to [21, Lemma 3]∣∣gen(W,S) ∣∣ ≤ LE [ W(PW |S,R, PW |S−J ,R) ] , where S−J = S \ ZJ , i.e., the whole dataset except sample ZJ . Moreover, if the loss is bounded and the geometry is ignored, Theorem 2 improves upon the tightest bounds in terms of the relative entropy of random subsets, cf. [7, Theorem 2.5]. Corollary 2. In the conditions of Theorem 2, if the loss is bounded in [a, b], then ∣∣gen(W,S) ∣∣ ≤ (b− a)E [ TV(PW |S,R, PW |S−J ,R) ] ≤ b− a
n
n∑
j=1
E [ Ψ ( DKL(PW |S,R ‖ PW |S−j ,R) )] .
These data-dependent bounds characterize well the expected generalization error of the Langevin dynamics (LD) and stochastic gradient Langevin dynamics (SGLD) algorithms [7, Theorems 3.1 and 3.3], where R is an artificial random variable used to encode some knowledge necessary to characterize the hypothesis distribution, such as the batch indices of SGLD. In particular, Corollary 2 improves upon [7, Theorem 2.5] tightening the elements of the expectation with respect to J for which the divergence is large (' 1.6).
It is possible to prove that Theorem 1 is tighter than [15, Theorem 1]. This results by studying the KR dual representation of the Wasserstein distance and noting that the conditional distribution PW |Zi is a smoothed version of the forward channel, i.e., PW |Zi = E[PW |S |Zi]. Comparisons with Theorem 2 are also possible using similar arguments and the triangle inequality. These results are informally summarized below and presented with more details and the proofs in Appendix D.1. Proposition 1. Consider the standard setting. Then, for all j ⊆ [n] and all i ∈ j: E [ W(PW |Zi , PW ) ] ≤ E [ W(PW |S , PW ) ] ,where j = [n], (=⇒ Theorem 1 ≤ [15, Theorem 1])
E [ W(PW |Zi , PW ) ] ≤ E [ W(PW |S , PW |Sjc ) ] , and (=⇒ Theorem 1 ≤ Theorem 2) E [ W(PW |S , PW |Sjc ) ] ≤ 2E [ W(PW |S , PW ) ] . (=⇒ Theorem 2 ≤ 2·[15, Theorem 1])
The following example showcases a situation where the presented bounds outperform the current known bounds based on the Wasserstein distance and the mutual information. Example 1 (Gaussian location model). Consider the problem of estimating the mean µ of a ddimensional Gaussian distribution with known covariance matrix σ2Id. Further consider that there are n samples S = (Z1, . . . , Zn) available, the loss is measured with the Euclidean distance `(w, z) = ‖w − z‖2, and the estimation is their empirical mean W = 1n ∑n i=1 Zi.
In this example, the expected generalization error can be calculated exactly (see Appendix E):
gen(W,S) =
√ 2σ2
n
(√ n+ 1− √ n− 1
)Γ ( d+1
2
)
Γ ( d 2 ) ∈ O
(√ σ2d
n
) .
As discussed in [6], the bound from [4] is not applicable in this setting since I(W ;S) → ∞ and since `(w,Z) is not subgaussian given that Var[`(w,Z)] → ∞ as ‖w‖2 → ∞. When d = 1, the loss `(W,Z) is 1-subgaussian and the individual sample mutual information (ISMI) bound from [6] produces a bound in O (√ σ2/n ) , which decreases slower than the true generalization error, see Figure 1. This happens since the bound grows as the square root of I(W ;Zi), which is in O(1/n).
In this scenario, the loss is 1-Lipschitz under ρ(w,w′) = ‖w − w′‖2, and thus the bounds based on the Wasserstein distance are applicable. Applying the bound from [15] yields a bound in O (√ σ2d/n ) , which decreases at the same sub-optimal rate as the ISMI bound. However, both the individual and random-subset Wasserstein distance bounds from Theorems 1 and 2 produce bounds in O (√ σ2d/n ) , which decrease at the same rate as the true generalization error (see Figure 1).

heading: 3.1.1 Outline of the proofs
text: Similarly to [15, 16], the proofs of the theorems in this section are based on operating with gen(W,S) until an expression of the type E[f(X ′, Y )− f(X,Y )] is reached, where X ′ is an independent copy of X such that PX′,Y = PX ⊗ PY , and then applying the KR duality. For example, in Theorem 1 such an expression is achieved with X = W , Y = Zi, and f = `. To arrive at these expressions, the proofs of Theorem 3 and 4 operate with gen(W,S) in different forms. More precisely,
(Th. 1) Since the samples Zi are independent and the expectation is a linear operator, the proof follows working with the quantity gen(W,S) = 1n ∑n i=1 E[`(W ′, Zi)− `(W,Zi)]. (Th. 2) Note that E[LsJ (w)] = Ls(w), where J is a uniformly random subset of [n] of size m and sJ is the subset of s indexed by J . This equality follows since there are ( n m ) subsets of size
m and each sample zi belongs to only ( n−1 m−1 ) of them. Hence,
E[LsJ (w)] = 1( n m
) ∑
j∈J 1 m
∑ i∈j `(w, zi) = 1 n n∑ i=1 `(w, zi) = Ls(w).
Then, the proof follows working with the quantity gen(W,S) = E[LSJ (W ′)−LSJ (W )].

heading: 3.2 Randomized-subsample setting
text: In the randomized-subsample setting the focus shifts from studying the impact of the samples on the hypothesis distribution to the impact of the samples’ identities on the hypothesis distribution. For example, the analogous result to (1) is
∣∣gen(W,S) ∣∣ ≤ 2LE [ W(PW |S̃,U , PW |S̃) ] . (3)
Similarly to the standard setting, considering the discrete metric and applying Pinsker’s and Jensen’s inequalities leads to a less favorable bound than current bounds based on the mutual information [1, Theorem 5.1] since it does not explicitly decrease as 1/ √ n. However, the bound still admits a tighter (see Appendix D.1) single-letter version. Theorem 3. Suppose that the loss function ` is L-Lipschitz for all z ∈ Z and that the hypothesis spaceW is Polish and let S̃i , (Z̃i, Z̃i+n). Then,
∣∣gen(W,S) ∣∣ ≤ 2L
n
n∑
i=1
E [ W(PW |S̃i,Ui , PW |S̃i) ] .
As in the standard setting, when the loss function is bounded and the geometry of the space is ignored, this result improves upon current single-letter bounds based on the mutual information [9, 12] by
pulling the expectation with respect to the samples PS̃i out of the square root. Here, the BH inequality is not considered since DKL(PW |S̃i,Ui ‖ PW |S̃i) ≤ log(2); see Appendix F for the details. Corollary 3. Under the conditions of Theorem 3, if the loss ` is bounded in [a, b], then
∣∣gen(W,S) ∣∣ ≤ 2(b− a)
n
n∑
i=1
E [ TV(PW |S̃i,Ui , PW |S̃i) ]
≤ b− a n
n∑
i=1
E [√ 2DKL(PW |S̃i,Ui ‖ PW |S̃i) ] .
In this setting, Corollary 3 also decreases at a 1/ √ n rate and is tighter than [1, Theorem 5.1].
∣∣gen(W,S) ∣∣ ≤ 2(b− a)
n
n∑
i=1
E [ W(PW |Z̃i,Z̃i+n,Ui , PW |Z̃i,Z̃i+n) ] ≤
√ 2(b− a)2I(W ;U |S̃)
n .
Finally, the randomized-subsample setting also accepts random-subset bounds. These bounds study how the knowledge of the identities of a set of samples that where used for training, UJ , alters the hypothesis distribution when all the other identities, UJc , and all the samples, S̃, are known. Theorem 4. Suppose that the loss function ` is L-Lipschitz for all z ∈ Z and that the hypothesis space W is Polish. Let J be a uniformly random subset of [n] such that |J | = m, and that is independent of W , S̃, and ULet also R be a random variable independent of S̃,U , and J . Then,
∣∣gen(W,S) ∣∣ ≤ 2LE [ W(PW |S̃,U,R, PW |S̃,UJc ,R) ] and ∣∣gen(W,S) ∣∣ ≤ 2L
m E [∑ i∈J E [ W(PW |S̃,UJc∪Ui,R, PW |S̃,UJc ,R) | J ]] .
Although these bounds are weaker than Theorem 3 (see Appendix D.1), their data-dependent nature may lead to more tractable and sharper bounds in practice. For example, when the discrete metric is considered, Theorem 4 recovers from below current random-subset bounds based on the relative entropy, which are used to obtain some of the tightest bounds for LD and SGLD [9, 10]. Corollary 4. In the conditions of Theorem 4, for m = 1, if the loss is bounded in [a, b], then
∣∣gen(W,S) ∣∣ ≤ 2(b− a)E [ TV(PW |S̃,U,R, PW |S̃,U−J ,R) ]
≤ b− a n
n∑
j=1
E [√ 2DKL(PW |S̃,U,R ‖ PW |S̃,U−j ,R) ] .

heading: 3.2.1 Outline of the proofs
text: The proofs of the results in this section are similar to those of the standard setting, hence their similar expressions. However, instead of operating with the expected generalization error in the form of E[gen(W,S)] they operate with E[ĝen(W, S̃, U)]. There are two issues that complicate the application of the KR duality as in the previous proofs. For instance, consider ĝen(W, S̃, U), then:
• Both LS̄(W ) and LS(W ) depend on PU . Hence, considering a copy W ′ of W such that PW ′,S̃,U = PW,S̃ ⊗ PU does not help since E[ĝen(W, S̃, U)] 6= E[LS̄(W ′)−LS(W )]. • Even if E[ĝen(W, S̃, U)] = E[LS̄(W ′)−LS(W )] were true, for some fixed s̃ and u, the functions L̄s(w) and Ls(w) on w are different, and thus the KR duality cannot be invoked.
Nonetheless, these two issues are resolved considering instead ĝen(W, S̃, U) = LS̄(W )−LS(W )− E[LS̄(W ′)−LS(W ′)], where W ′ is an independent copy of W such that PW ′,S̃,U = PW,S̃ ⊗ PU . Hence, the inequalities E[LS̄(W ′)−LS(W ′)] = 0 and |x+ y| ≤ |x|+ |y| lead to the upper bound∣∣E[ĝen(W, S̃, U)] ∣∣ ≤ ∣∣E[LS̄(W ′)−LS̄(W )] ∣∣+ ∣∣E[LS(W ′)−LS(W )]
∣∣, where the KR duality can be applied to each of the terms, albeit at the expense of an extra factor of 2.

heading: 3.3 Backward channel
text: In [17], the authors study the characterization of the expected generalization error in terms of the discrepancy between the data distribution PS and the backward channel distribution PS|W motivated by its connection to rate–distortion theory, see e.g., [19, Chapters 25–57] or [22, Chapter 10]. An approach formalizing this intuitive connection is given in Appendix G and different angles, based on chaining mutual information [13] and compression, are found in [11, Section 5] and [23].
More concretely, they proved that the generalization error is bounded from above by the discrepancy of these distributions, where the discrepancy is measured by the Wasserstein distance of order p with the Minkowski distance of order p as a metric, i.e., ρ(x, y) = ‖x− y‖p. Namely,
∣∣gen(W,S) ∣∣ ≤ L
n1/p E[Wpp,|·|(PS , PS|W )] 1/p.
Similarly, the results from §3.1 and §3.2 can be replicated considering the backward channel instead of the forward channel, e.g., PS|W instead of PW |S in (1), PZi|W instead of PW |Zi in Theorem 1. However, in this case, the loss ` would be required to be Lipschitz with respect to the samples space Z and not the hypothesis spaceW , i.e., Lipschitz for all fixed w ∈ W , thus exploiting the geometry of the samples’ space and not the hypotheses’ one.
As an example, noting that gen(W,S) = E[LS′(W )−LS(W )], where S′ is an independent copy of S such that PW,S′ = PW ⊗ PS produces the bound∣∣gen(W,S)
∣∣ ≤ LE[W(PS , PS|W )]. Compared to [17], these results (i) are valid for any metric ρ as long as the loss ` is Lipschitz under ρ, and (ii) have single-letter and random-subset versions, and (iii) have variants in both the standard and randomized-subsample settings.

heading: 3.4 Other information measures
text: The bounds obtained in §3.1 and §3.2 may be manipulated to produce a variety of new bounds based on common information measures. For example, once the discrete metric is assumed and since the total variation is symmetric, applying Pinsker’s inequality with the distributions in the opposite order to Corollaries 1, 2, 3, and 4 and further applying Jensen’s inequality yields bounds based on the lautum information L [24]. For instance, a corollary of Theorem 3 is
∣∣gen(W,S) ∣∣ ≤ b− a
n ∑n i=1 Ψ ( L(W ;Zi) ) .
Similarly, several new bounds based on different f -divergences [19, Chapter 7] may be obtained employing the joint range strategy once the discrete metric is assumed. As an example, some corollaries of Theorem 1 based on the Hellinger distance H and the χ2-divergence (see Appendix H for a tighter and more general version of (6)) are
∣∣gen(W,S) ∣∣ ≤ L
2n ∑n i=1 E [ H(PW |Zi , PW ) √ 4− H2(PW |Zi , PW ) ] , (4)
∣∣gen(W,S) ∣∣ ≤ L√
2n
∑n i=1
E [√ log ( 1 + χ2(PW |Zi , PW ) )] , and (5)
∣∣gen(W,S) ∣∣ ≤ L
2n ∑n i=1
E [√
χ2(PW |Zi , PW )
] . (6)

heading: 3.5 Final remarks on the generality of the results
text: Due to Bobkov–Götze’s theorem [14, Theorem 4.8], the relative entropy results still hold when the loss is both Lipschitz and subgaussian. Hence, the presented Wasserstein distance bounds are tighter than [4, 6, 7, 9, 10] in a more general setting. Moreover, the total variation results also hold for any metric with the added factor of dρ(W) as per Remark 3. These results were omitted in the main text for clarity of exposition, but are included in Appendix B.
Therefore, only when the loss is not Lipschitz but is subgaussian or has a bounded cumulant function, or W is not Polish, the bounds from [6, 7, 10, 12] are preferred. As an example, some common loss functions such as the cross-entropy, the Hinge loss, the Huber loss, or any Lp norm are Lipschitz [25, 26] under an appropriate metric ρ, see Appendix A for a discussion of the role of the metric and the space geometry in the presented bounds.

heading: 4 Discussion
text: This paper introduced several expected generalization error bounds based on the Wasserstein distance. In particular, these are full-dataset, single-letter, and random-subset bounds on both the standard and the randomized-subsample settings. When the Wasserstein distance ignores the geometry of the hypothesis space and the loss is bounded, the presented bounds are tighter and recover from below the current bounds based on the relative entropy and the mutual information [4, 6, 7, 9, 10], see also Appendix B for stronger, more general statements. Furthermore, the obtained total variation and relative-entropy bounds on the standard setting are ensured to be non-vacuous, i.e., smaller or equal than the trivial bound, thus resolving the issue of potentially vacuous relative-entropy and mutualinformation bounds on the standard setting. Interestingly, the results for the randomized-subsample setting are tighter than their analogous in the standard setting only if their Wasserstein distance (or total variation) is twice as small.
Moreover, the techniques employed to obtain these bounds can also be used to obtain analogous bounds considering the backward channel and the samples’ space geometry, aiming to facilitate connections between the generalization error characterization and rate–distortion theory, as suggested by Lopez and Jog [17]. Nonetheless, when the backward channel can be characterized, these bounds are interesting in their own right. Finally, the presented bounds may be used to generate a variety of new bounds in terms of, e.g., the lautum information or f -divergences like the total variation, the relative entropy, the Hellinger distance, or the χ2-divergence.

heading: 4.1 Limitations and future work
text: PAC-Bayes bounds PAC-Bayes bounds ensure that E[gen(W,S) | S] ≥ α(β−1) with probability no greater than β ∈ (0, 1). Similarly, single-draw PAC-Bayes bounds ensure that gen(W,S) ≥ α(β−1) with probability no greater than β ∈ (0, 1). These concentration bounds are of high probability when the dependency on β−1 is logarithmic, i.e., log(1/β). See, [27, 2] for an overview.
The bounds from this work may be used to obtain single-draw PAC-Bayes bounds applying Markov’s inequality [22, Problem 3.1] directly. For instance, employing it in Theorem 1 implies that
PW,S
( gen(W,S) ≥ L
βn ∑n i=1 E[W(PW |Zi , PW )] ) ≤ β,
for all β ∈ (0, 1). However, this is not a high-probability bound since the dependency on β−1 is linear. Hence, high-probability concentration bounds based on the Wasserstein distance and the total variation are a path of future research. As an example, [28–31] provide high-probability singledraw PAC-Bayes bounds based on, respectively, max-information, differential privacy, α-mutual information, and uniform stability. Similarly, high-probability PAC-Bayes bounds based on the relative entropy and the hypothesis’ space geometry are given in [8] and [32, 33], respectively.
New bounds to specific algorithms The Wasserstein distance is difficult to characterize and/or estimate. Nonetheless, some of the bounds that can be obtained from it, e.g., mutual-information and relative-entropy bounds, have been used to obtain analytical bounds on specific algorithms, e.g., Langevin dynamics and stochastic gradient Langevin dynamics [6, 7, 9, 10]. Some of these results can be readily tightened with Corollaries 1, 2, and 4. Thence, deriving new analytical bounds for specific algorithms based on the presented results is also a topic for further research.
Connections to stability and privacy measures A learning algorithm is said to be stable if a small change on the input dataset produces a small variation in the output hypothesis. There are various attempts at quantifying this notion such as uniform stability [34], where the variation in the output hypothesis is seen in terms of the loss, and differential privacy (DP) [28], where this variation is seen in terms of the hypothesis distribution. These notions are tied to the generalization capability of an algorithm, i.e., the less a hypothesis depends on the specifics of the data samples, the better it will generalize, and hence there are works obtaining generalization bounds based on stability, see e.g., [29, 31]. In particular, there are some works that, assuming some stability notion such as DP, bound from above the relative entropy and the mutual information appearing in some of the bounds that can be derived from the results presented in this work, hence also tying stability and generalization, c.f. [1, 35, 36]. Therefore, a future line of research is to investigate how different notions of stability can be combined with the measures of similarity between distributions employed in this work to characterize the generalization error.
Funding
This work was funded in part by the Swedish research council under contract 2019-03606.

Review summaries:
This work provides novel generalization bounds, which limit (in expectation) the gap between a classifier’s empirical risk, i.e. how well it performs on the training data, and population risk, i.e. how well it performs on the true distribution. Generalization bounds can be in terms of many parameters of the problem, and this paper focuses on Wasserstein distances. Specifically, it provides bounds in terms of the Wasserstein distance between the hypothesis distribution before and after a single sample (“single-letter”), before and after a random subset of the samples (“random-subset”), and before and after the full set of samples (“full-dataset”). These Wasserstein distances were studied in previous work as well, but these bounds are tighter than the predecessor bounds. 

This paper considers the problem of obtaining generalization bounds using the statistical measure of dependence between the input and output of a learning algorithm. Tha main contribution of this paper is to provide a generalization bound using the Wasserstein distance between the posterior distribution and P(W). This result is further improved by considering the single sample case where the generalization bounds are based on the Wasserstein distance P(W|Z_i) and P(W). Also the authors extend their results to the setup of Steinke and Zakynthinou ‘20. The authors specifically follow the literature of information-theoretic generalization bounds, and compare their bounds to the existing bounds in the literature. In all cases, the authors show that the bounds using Wasserstein distance are tighter than the bound using mutual information (or KL).  Also, they show for a toy example of estimating the mean of gaussian distribution their bound provides “order-wise” improvement over the mutual information bounds where the mutual information based bounds gives upper bounds on the generalization that decays as 1/sqrt(n) but the Wasserstein distance based bound gives a bound that decays as 1/n.  The authors also use the joint-range technique to provide generalization bounds based on f-divergences.  

This work presents several expected generalization error bounds in terms of the Wasserstein distance. Several settings (full-dataset, single-letter, and random-subset) are considered in the paper. Under the assumption that the loss function is bounded and using Hamming distance in the Wasserstein distance, the proposed bounds are shown to be tighter than the existing mutual information (or KL divergence) based generalization error bound. The author also claims that serval new bounds based on a variety of information measures can be obtained using these Wasserstein distance-based bounds.  

In this paper new generalization error bounds based on Wasserstein distance are derived. As shown in the paper, these bounds are tighter than existing bounds based on mutual information. Also, the authors briefly discuss how their bounds could be extended to deal with backward channels (instead of forward channels), and how they could lead to bounds based on general f-divergences.