Tighter Expected Generalization Error Bounds via Wasserstein Distance
Authors: Borja Rodríguez Gálvez
German Bassi
Ragnar Thobaben
Mikael Skoglund
Venue: NeurIPS 2021 Poster (2021)
Keywords: generalization error
wasserstein distance

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 analogous 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.

Tighter Expected Generalization Error Bounds via Wasserstein Distance
Borja Rodriguez-Gälver
Germán Bassi Ericsson Research
KTH Royal Institute of Technology
Stockholm, Sweden
Stockholm, Sweden
german. wws.baasssssssee weweeeeeeeiiccceeeeeeeeeeeeeeeee com
Ragnar Thobaben
Mikael Skoglund
KTH Royal Institute Technology Stockholm, Sweden ragnartOkth.se se
KTH Royal Institute of Technology
Stockholm, Sweden
skoglundkkth.
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 igmored by the choice of the metric the Wasserstein distance. these bounds recover from below (and thus, 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 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 several f-divergences) based on these bounds and how to derive similar bounds with respect to the backward channel using the presented proof techniques.
Introduction
learning algorithm is mechanism that takes a datasel 8 = (zi,..., =n) of n samples z; E Z taken i.i.d. from distribution Pz input, and produces hypothesis w E W by means of the conditional probability distribution Pwis-
The ability of a hypothesis w to characterize a sample described by the loss function f(w, 2) e R. More precisely, hypothesis describes well the samples from population Pz when its population risk, i.e., Lrz (w) e E[E(w, Z)), low. However, the distribution Pz is often not available and the Di=1 l(w, z;), is considered as proxy. Therefore, is of interest to study the discrepancy between population and empirical risks, which is defined as the generalization error:
empiricul risk on the dataset i.e., L, (w)
gen(w, w. s) e Lp (w) (w).
Classical approaches bound the generalization error in expectation and 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 (NcurIPS 2021).

---

[5], it is shown that the expected generalization error, i.e., gen (W - Elgen ())). 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., (W;;5) S). However, this bound becomes vacuous when (W:5) -> Do, 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, (W; Zz), 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., D ( Pw]sye) where j S [rx].
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-sane uper-sample of 2n i.i.d. instances & from Pz. i.e., 8 = (ā1,..., Z2n). This super sample is used to construct the dataset by choosing between the samples & and Ez+n using a Bernoulli random variable U; with probability 2. i.e., a, = Ei+ In this paper, the two settings are referred to as the standard and randomized -ubsaappple settings.' In the randomized-subeen subsample setting, the empirical generalization error is defined as the difference between the empirical risk on the samples from 3 not used to obtain the hypothesis, i.e., 3 5 8, and the empirical risk on the dataset i.e.,
gen(w, 8, u) A (w) (w) = Σ
(C(w,, (1+())))))) - f(w,, Zs+tun));
where u is the sequence of n i.i.d. Bernoulli trial outcomes uy. The expected value of the empirical and the (standard) generalization errors coincide, i.e., Rlgen 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 $ [1], i.e., I I(W UJ.). by the individual conditional mutual information [9], i.e., 7 I(W; U.| Zi+m). and by the "disintegrated" mutual information with a subset J of the Bernoulli trials [10], i.e., DKL v || PP S,U ). 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; UI$)= S I(W; 5) and IWW; 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 / (W;S) S) and the conditional mutual information / (W; U|)). 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; Z.). DKL ( || Pw]ss=), ). and D (Pw1s $. s,ulll PW1$,U,e) and to generate new individual conditional mutual information bounds, i.e., I[W U, Z, Zi+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.c., {2 k/2 / Jus S)},. which can
be finite even if Z SW; + oc. This result stems from 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 function of the Wasserstein distance between the hypothesis distribution after observing the dataset Pwis and its
prior Pw, i.e., Wp (Pwis: Pw)) ). and by a function of the Wasserstein distance between the hypothesis distribution after observing single sample Pwiz, and its prior Pw: i.e., W (Pwi22,, 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 Psiw. i.e., WP WPr P. 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-subaamp 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
In [8] the latter is called the random-subset setting. However, this may cause confusion with the random- subset bounds in the present work.
2

---

information bounds on both the standard and vandomized-subsameee 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 and 2 overeome 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, c.g., the lautum information or several f-divergences like the Hellinger distance or the xivvveegg,,,,, thus making the characterization of the generalization more flexible.
2 Preliminaries
2.1 Notation
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 o-algebras Y in script-style letters. Moreover, the probability distribution of a random variable X is written as Px I + [0, 1]. Hence, the random variable X 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 I y - [0, 1] and their product distribution as Px Py I & y - [0, 1]. Moreover, the conditional probability distribution of Y given X is written as Pr|x y @ X + [o. and defines a probability distribution Py|X== (or Py for brevity) over y for each element x X. Finally, there an abuse of notation writing Px,y Pylx X Px since y [ X (a,, (z.,)) y))ddy (1) dPx (ar) for all B @ Y. where xn is the characteristic function the set B. The natural logarithm is log.
2.2 Necessary definitions, remarks, claims, and lemmas
Definition 1. Let X' x X - R., be a metric. A space (X. p) is Polish if it is complete and separable. Throughout is assumed that all Polish spaces (X are equipped with the Borel a-algebra X generated by p. When there is no ambiguity, both the metric space (X, and the generated measurable space (X, X)) are written X.
Definition 2. Let (X,P) p) be Polish metric space and let E (1) Then, the Wasserstein distance of order p between two probability distributions P and Q on is
( (Fein inf REII(P..) JxXx p(z, (RddR v) 1/P
J.
(p(P.Q)
where IT(P. Q) is the set of all couplings R of P and Q, i.e., all joint distributions on X x X with marginals and Q, that is, P(B) = R(B, B, X) and Q(B) = R(X, B) for all B E X. Remark 1. Hölder's inequality implies that Wp S W for all p S 9 [18, Remark 6.6). Hence, since this work is centered on upper bounds the focus on W A WT.
Definition 3. A function f X - R is said to be L-Lipschitz under the metric p. or simply - < Lp(x,8) v) for all x, E X.
f L-Lip(p),
Lemma Senntorovich-Ruuinstee duality [18, Remark 6.5]). Let Pi (X)) be the space of probability distributions on X with a finite first moment. Then, for any two distributions P and Q in Px())
U f(x)dP(x) -ocup(xx-J((_0 (
W(P,Q) Q) =
sup SE1-Lip(p)
(KR duality)
Definition 4. The total variation between two probability distributions P and Q on X
TV(P,Q Q) & sup (P(A) - Q(A))
Definition 5. The discrete metric is P_( y) 1[x + y), where 1 is the indicator function.
(a, b) is (b Li-sspcchitz under the discrete metric pui Remark 3. The Wasserstein distance of order is dominated by the total variation. For instance, if P and Q are two distributions on X then Wi Q) S X P. Q), where d,(X)) ) the diameter of X. In particular, when the discrete metric is considered W(P.) Q) TV(P, Q) [18, Theorem 6.15].
Remark 2. bounded function f
3

---

Lemma 2 (Pinsker's and Bretagnolle Huber's s (BH) inequalities). Let P and Q be two probability distributions on X' and define (xx v (min - exp(-x)}, then [19, Theorem 6.5] and [20,
Proof of Lemma 2.1] J state that
Tv(P.Q) & ((Dx((P)
Expected Generalization Error Bounds
This section presents our main results. First, in $3.1 and $3.2, single-letter and random- -ubbset 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 proof's and technical details are deferred to the appendix.
3.1 Standard setting
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 Pwis and the marginal distribution of the hypothesis Pw. More specifically, when the loss function é is L-Lipschitz under a metric p for
all z E 2 and the hypothesis space W is Polish, then (W, S
LE (W Pw)] = f W(Pwis Pw )dP (s).
(1)
This bound considers both the geometry of the hypothesis space by means of the metric p and the dependence between the hypothesis and the dataset via the discrepancy between the forward channel Pwis 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 é bounded in (a, b). if the geometry is ignored (i.e., the discrete metric is considered), then
gen S)] I (b- a) [T Pw)) S (b - aI
where the inequalities follow from Remark 2, Lemma 2, and Jensen's 's inequality (note (z)., defined in Lemma 2, is concave z). This result compares negatively with other results employing the mutual information, e.g., [4, Theorem IJ. where the bound has a decaying factor of 1/v7.
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 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 7;, i.e., (Pwiiz, Pw).
Theorem 1. Suppose that the loss function is L-Lipschitz,fon for all & E Z and that the hypothesis space W is Polish. Then,
I. Ben(W, - Σ E[W(Pwiz, Pw)]. i=1
Moreover, when the loss function bounded and the geometry of the space 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 e is bounded in [a, b). then
< b b-a- Σ" " E[TV(PW z, P.)P] < b - a Σ "
gen (en,W,So S) W,
V (Dxi, || Pw))]
Corollary improves upon [6. Proposition 1] in two different ways. First, pulls the expectation with respect to the samples Pz, outside of the concave square root, thus strengthening that result via Jensen's 's inequality. Second, the addition of the BH inequality ensures that heavily influential samples (high / (W; Z,)) 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 11, exhibiting the decaying factor of n/Vn.
b
[(W:S)
(b a)2I(W;
gen(W,S)
<
E (P Pw)] s (b-a)
n
71
2n
(2)

---

It is also possible to obtain a random-suuees version of [15, Theorem 2] using similar strategy to [9, Propositions and 4]. This kind of bounds, rather than looking at how knowing single sample 7i modifies the hypothesis distribution, i.e., W W(Pw [w]z, Pw), look at how the knowledge of a set of samples 55 alters the hypothesis distribution when all the other samples, Sje, used to obtain the hypothesis are known too, i.e., W (Pwis Pw
Theorem 2. Suppose that the loss function is L-Lipschitz, for all & E 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 gen(W, (WS) 0)|=- (Pw S.R. [w]s and
gen( W. - Σ E EEJ
Pwiss |J] 1
In particular, when m 1, the two equations from Theorem reduce to [21, Lemma 3]
gen(WW S [P[[((W]]s.) s, PwiS-J [n)]
where S-1= S Z,. 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: (WW)) S) < (b - ()V(() Pw]S- <
E (Da. (PwisR Pwis->,a))
These data- deta-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 the batch indices of SGLD. In particular, Corollary 2 improves upon [7, Theorem 2.5] tightening the elements of the expectation with respect to for which the divergence is large C 1.6).
is possible prove that Theorem is tighter than [15, Theorem 1]. This results by studying the KR dual representation of the Wasserstein distance and noting that the conditional distribution Pwiz, is smoothed version of the forward channel, ie., Pwiz x = P[[w [Z,]. Comparisons with Theorem also possible using similar arguments and the triangle inequality. These results informally summarized below and presented with more details and the proofs in Appendix D.1.
Proposition 1. Consider the standard setting. Then, for all [m] and all E j:
E [WW(Pizz, Pw]] E [[W]ss Pw)] where j = [n]. (=> Theorem s [15, Theorem 1))
E
W ((Pwiz,, Pw)] W Pw]s: Pw1s,e (e }}. and
(= Theorem Theorem 2)
E ([Pwss Pwiss) )] - 2E
(=> 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 (Gaussian location model). Consider the problem of estimating the mean of a d- dimensional Gaussian distribution with known covariance matrix o² Further consider that there are n samples S = (Zz,..., Zn) available, the loss is measured with the Euclidean distance f(w, 2) = || 2||2, and the estimation is their empirical mean W Eim Zi.
In this example, the expected generalization error can be calculated exactly (see Appendix E):
20 n
r d+1
Vo'd
gen W, S) =
(Vn+I- -n-
(
n
As discussed in [6]. the bound from [4] is not applicable in this setting since I(W: + oo and since f(w, Z) is not subgaussian given that Var[E(w, 2)] - oo as ||w||2 + xo. When 1, the loss E(W, Z) is 1-subgaussian and the individual sample mutual information (ISMI) bound from [6] produces a bound in O( ((Vo2/n) which decreases slower than the true generalization error, see Figure 1. This happens since the bound grows as the square root of I (WW Z.), which is in O(1/n).
5

---

10c
Wasserstein distance
ISMI [6]
-4- Random-subset Wasserstein (Th. 2)
Random subset Wasserstein (Th.
Individual Wasserstein
Indiv dual Wasserstein (Th.
Generalization error
General lizationn crror
10-4
100-
10-3
100
150
200
250
100
150
200
250
Number of samples o
Number of samples
Figure 1: Expected generalization error and generalization error bounds for the Gaussian location model w (N, 1) (left) and (N, 2250) (right). See Appendix E for the details.
In this scenario, the loss is I-L.ischhitz under p(w; w/) || w 22112, and thus the bounds based on the Wasserstein distance are applicable. Applying the bound from [15] yields a bound in O Vo*d/n) which decreases the same sub-optimal rate as the ISMI bound. However, both the individual and random-subset Wasserstein distance bounds from Theorems and produce bounds in O Vo²d/n). which decrease at the same rate as the true generalization error (see Figure 1).
3.1.1 Outline of the proofs
Similarly to [15, 16], the proofs of the theorems in this section are based on operating with gen( W S) until an expression the type [[ Y) - s(X, Y)] is reached, where X' an independent copy of X such that Px',y Px Py, and then applying the KR duality. For example, in Theorem I such an expression is achieved with X = W, Y Zi and f = L. To arrive at these expressions, the proof's of Theorem 3 and 4 operate with gen W, S) in different forms. More precisely,
(Th. 1) Since the samples Z; are independent and the expectation is linear operator, the proof follows working with the quantity gen(W, S)
Z.) 2.)].
(Th. 2) Note that (1),,(()) = (w), where is a uniformly random subset of [n] of size m and 8, is the subset of s indexed by This equality follows since there are (#) subsets of size and each sample z; belongs to only (m=l) of them. Hence, N2
Σ JEJ m Then, the proof follows working with the quantity gen(W, (5) E,Ss, LL, (W)).
E|L,,
[w, 24) n
Σ ((w, 24) Ls(w).
iej
3.2 Randomized-subsat setting
In the randomized-subsanpee setting the focus shifts from studying the impact of the samples on the hypothesis distribution the impact of the samples' identities the hypothesis distribution. For example, the analogous result to (I)
gen W, S) < 2LE ( Pw S.u, Pw]s)].
Similarly to the standard setting, considering the discrete metric and applying Pinsker's and Jensen's inequalities leads to less favorable bound than current bounds based on the mutual information [1, Theorem 5.1] since does not explicitly decrease 1/ However, the bound still admits tighter (see Appendix D.I) single-letter version.
Theorem 3. Suppose that the loss function is L-Lipschitz. all = E Z and that the hypothesis space W is Polish and let S, A (Z,, Z4tn). Then,
2L
gen(N W
E (
As in the standard setting, when the loss function is bounded and the geometry of the space 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. out of the square root. Here, the BH inequality considered since DxI. (PW)ss S..u Pw (..) S log(2); see Appendix for the details.
Corollary 3. Under the conditions of Theorem 3, if the loss é is bounded in (a, b), then
2(b a)
n
gen gen(W,
E PW Pw13.)
n
n
2D (Pw S.U. Pwis.)
72
In this setting, Corollary also decreases at a 1/ V rate and is tighter than [1, Theorem 5.1].
gen(W, S)
< 2(b a)
Σ BIW(PW12,, Pw12.2211n)
2(b - a)3I(W;
Finally, the randomized-subsamppl 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, Je,, and all the samples, S, are known.
Theorem 4. Suppose that the loss function is L-Lipschitz for all 2 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 Wf, W, S, and Let also R be random variable independent of S,U, and J. Then,
gen (WS)) S) S 2LE
(PW11S,,.R. PWIB,Uyo.1i) and
gen W, (WS)| S
2T
E
E
WWPW1S,0 PWIB,Uyo,R) JJ].
17
Although these bounds are weaker than Theorem 3 (see Appendix D.I), their data-dependent nature may lead to more tractable and sharper bounds in practice. For example, when the discrete metric considered, Theorem recovers from below current random-subsel bounds based 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 for m if the loss is bounded in [a, b), then
gen( W.S) s 2(b
(TV S,U.R. P
b
E
2Dr (PW18,t, PwiS,u
n
3.2.1 Outline of the proofs
The proofs of the results in this section similar to those of the standard setting, hence their similar expressions. However, instead of operating with the expected generalization error in the form of Elgen(W, S)] they operate with Elgen W, WWS.U) S.U)].
There are two issues that complicate the application of the KR duality as in the previous proofs. For instance, consider gen(W, S, S, then:
Both (W) and Ls( depend Pu- Hence, considering copy W of W such that Pwr, ,8,0 Pw.s Py does not help since [lgen(W, S, U)] + EEEs (W))
Even if Elgen 5, U)] E
(W') - Ss (W)) were true, for some fixed and u, the functions Lg (w) and L. (w) on are different, and thus the KR duality cannot be invoked.
Nonetheless, these two issues resolved considering instead
gen(W, 3, U) Ls(W) (s( E(Lss(W') -Ls(W)), where W' is an independent copy of W such that Pwr,5,0 = Pw.s & Pt. Hence, the inequalities S [s')] 0 and æ + yl < |<| |yl lead to the upper bound
Elgen(W: S, U)] < ([LLs(W))
L3 (W)] + [[") Ls()])]
where the KR duality be applied to each of the terms, albeit at the expense of extra factor of 2.

---

3.3 Backward channel
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 Pstw motivated by its connection to rate- distorrin 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 as metric, i.e., p(z,, y) = || - y vllv- Namely,
I. 1/p E 2.1.1 (Ps )s
gen W, WWSS)) -
Similarly, the results from $3.1 and $3.2 can be replicated considering the backward channel instead of the forward channel, e.g., PsJw instead of Pwis in (I), Pz: instead of Pwiz, in Theorem 1. However, in this case, the loss would be required to be Lipschitz with respect to the samples space 2 and not the hypothesis space W, i.e., Lipschitz for all fixed E W, thus exploiting the geometry of the samples' space and not the hypotheses' one.
As example, noting that gen(W, S) E[Lss (W)- Sss)) where S' is an independent copy of S such that Pw.s' = Pw @ Ps produces the bound
gen W S) v LE[W Ps]w)].
Compared to [17], these results (i) valid for any metric p long the loss is Lipschitz under p. and (ii) have single-letter and random-subset versions, and (iii) have variants in both the standard and mandoizzed-subaappe settings.
3.4 Other information measures
The bounds obtained in $3.1 and $3.2 may be manipulated to produce 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 incquality yields bounds based on the lautum information L [24]. For instance, a corollary of Theorem 3 is
L (L(W; Z,)). Σ.
gen(W, S) <
n
i=1
Similarly, several new bounds based on different f 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 based on the Hellinger distance H and the x diveeregee (see Appendix H for a tighter and more general version of (6)) are
L "
gen W, S
<
E
H2 H Pw) H (PWiz, Pw)
(4)
2n
gen W,S) S) v
E
log (1 + (PWizz Pw)) and
(5)
V2n
t=1
gen S
<
L
Σ ==1
"
E
(2 Pw)
(6)
2n
3.5 Final remarks on the generality of the results
Due to Bobkov-Göte Götze's theorem [14, Thcorem 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 (W) as per Remark 3. These results were omitted in the main text for clarity of exposition, but are included in Appendix E.
Therefore, only when the loss is not Lipschitz but is subgaussian or has bounded cumulant function, or W 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 p. see Appendix A for a discussion of the role of the metric and the space geometry in the presented bounds.
8

---

4 Discussion
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-subsange
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 mutual- information bounds on the standard setting, Interestingly, the results for the mundomized--ubsamppee 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 terms of, e.g., the lautum information or f-divergences like the total variation, the relative entropy, the Hellinger distance, or the x -ivdiverge.ce.
4.1 Limitations and future work
PAC-Bayes bounds PAC-Bayes bounds ensure that Elgen(W. S) |S] 2 a((31) with probability no greater than 3 E (0, 1). Similarly, single-draw PAC-Bayes bounds ensure that gen(W, () Z a(B-1) with probability no greater than B E (0, 1). These concentration bounds are of high probability when the dependency on 8 is logarithmic, i.e., log(1/3). 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 I implies that
Pw,s gggenn (W,S) Z -"-
8n 1-1 B[W((w Pw]]) S B,
I.
for all B E (0, 1). However, this is not high-probability bound since the dependency on f-1 is linear. Hence, nigh-probabiline concentration bounds based on the Wasserstein distance and the total variation are path of future research. As example, [28-31] provide high-probability single- draw PAC-Bayes bounds based on, respectively, max-information, differential privacy, a-mutual information, and uniform stability. Similarly, relative entropy and the hypothesis' space geometry are given in [8] and [32, 33], respectively.
PAC-Bayes bounds based on the
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-infomm infommaaionn and relative-entropy bounds, have been used to obtain analytical bounds on specific algorithms, e.g., Langevin dynamies 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 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 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 this work, hence also tying stability and generalization, c.f. [1, 35, 36). Therefore, future line of research is to investigate how different notions of stability can 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.
References
[1] I. Steinke and L. Zakynthinou, "Reasoning about generalization via conditional mutual infor- mation," " in Conference on Learning Theory, ser. Proceedings of Machine Learning Research, vol. 125, Jul. 2020, pp. 3437-3452.
[2] S. Shalev-Shwarle and S. Ben-David Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
[3] V. Vapnik, The Nature of Statistical Learning Theory, ser. Information Science and Statistics. Springer Science & Business Media, 2013.
[4] A. Xu and M. Raginsky, "Information-thewn theooretcc analysis of generalization capability of learning algorithms," in Advances in Neural Information Processing Systems, 2017, pp. 2524-2533.
[5] D. Russo and Zou, "How much does your data exploration overfit? Controlling bias via information usage," IEEE Transactions Information Theory, vol. 66, pp. 302-323, Jan. 2020.
[6] Y. Bu, S. Zou, and V. V. Veeravalli, "Tightening mutual information based bounds on generaliza- tion error," IEEE Journal Selected Areas in Information Theory, vol. 1, no. 1, pp. 121-130, May 2020.
[7] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy, "Information-thhoortie gen- eralization bounds for SGLD via data-dependent estimates," Advances in Neural Information Processing Systems, 2019, pp. 11 015-11 025.
[8] F. Hellström and G. Durisi, "Generalization bounds via information density and conditional information density," IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 3, pp. 824-839, Nov. 2020.
[9] B. Bedriguez-Gálvzz G. Bassi, R. Thobaben, and M. Skoglund, "On random subset generaliza- tion error bounds and the stochastic gradient langevin dynamics algorithm," in IEEE Information Theory Workshop (ITW). IEEE, 2020.
[10] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite, "Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms," in Advances in Neural Information Processing Systems, 2020.
[11] H. Hafez-Kolar Z. Golgooni. S. Kasaei, and M. Soleymani. "Conditioning and processing: Techniques to improve information-thooeee generalization bounds," Advances in Neural Information Processing Systems, vol. 33, 2020.
[12] R. Zhou, C. Tian, and T. Liu, "Individually conditional individual mutual information bound on generalization error," arXiv preprint arXiv:2012.00992. 2020.
[13] A. Asadi, E. Abbe, and Verdú, "Chaining mutual information and tightening generalization bounds." in Advances in Neural Information Processing Systems, 2018, pp. 7234-7243.
[14] R. van Handel, "Probability in high dimension," Princeton University, NJ, Tech. Rep., 2014.
[15] H. Wang, M. Diaz, J. C. S. Santos Filho, and F. P. Calmon, "An information-theoretie view of generalization via wasserstein distance," in 2019 IEEE International Symposium on Information Theory (ISIT). IEEE, 2019, pp. 577-581.
[16] J. Zhang, T. Liu, and D. Tao, "An optimal transport view on generalization," arXiv preprint 11Xiv:1811.032700 2018
[17] A. T. Lopez and V. Jog, "Generalization error bounds using wasserstein distances," 2018 IEEE Information Theory Workshop (ITW). IEEE, 2018, pp. 1-5.
10

---

[18] C. Villani, Optimal Transport: Old and New, ser. Grundlehren der mathematischen Wis- Springer Science Business Media, 2008, vol. 338.
senschaften.
[19] Y. Polyanskiy and Y. Wu, "Lecture notes on Information Theory," MIT MIT (6.441), UIUC (ECE 563), Yale (STAT 664), 2017.
[20] J. Bretagnolle and C. Huber, "Estimation des densités: risque minimax," in Séminaire de Probabilités XII. Springer, 1978, pp. 342-363, French.
[21] M. Raginsky, A. Rakhlin, M. Tsao, Y. Wu, and A. Xu, "Information-therrete analysis of stability and bias of learning algorithmss" in 2016 IEEE Information Theory Workshop (ITW). IEEE, 2016, pp. 26-30.
[22] M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. John Wiley & Sons, 2006.
[23] Y. Bu, W. Gao, S. Zou, and V. Veeravalli, cerformation-theoreie understanding of population risk improvement with model compression," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 04, pp. 3300-3307, Apr. 2020.
[24] D. P. Palomar and S. Verdú, "Lautum information," IEEE Transactions Information Theory, vol. 54, no. 3, pp. 964-975, 2008.
[25] I. Steinwart and A. Christmann, Support vector machines. 2008.
Springer Science & Business Media,
[26] B. Gao and L. Pavel, "On the properties of the softmax function with application in game theory and reinforcement learning," 2018.
[27] B. Guedj, "A primer on PAC-Bayesian learning," arXiv preprint arXiv: arXiv:190..0533.0 2019.
[28] C. Dwork, A. Roth et al., "The algorithmic foundations of differential privacy." Foundations and Trends Theoretical Computer Science, vol. 9, no. 3-4, pp. 11-407, 2014.
[29] C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth, "Generalization in adaptive data analysis and holdout reuse," in Advances in Neural Information Processing Systems, 2015, pp. 2350-2358.
[30] 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.
[31] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy, "Sharper bounds for uniformly stable algo- rithms," in Conference Learning Theory, Proceedings of Machine Learning Research, 2020, pp. 610-626.
[32] J.-Y. Audibert and O. Bousquet, "Pac-bayesian generic chaining." NIPS Citeseer, 2003, pp. 1 1135-1132.
[33] J.-Y. Audibert and O. Bousquert, "Combining pac-bayesian and generic chaining bounds." Journal of Machine Learning Research, vol. 8, no. 4, 2007.
[34] O. Bousquet and A. Elisseeff, "Stability and generalization," Journal of machine learning research, vol. 2, no. Mar. pp. 499-526, 2002.
[35] M. Bun and T. Steinke, "Concentrated differential privacy: Simplifications, extensions, and lower bounds." in Theory of Cryptography Conference. Springer, 2016, pp. 635-658.
[36] B. Rodríguez-Gálvee G. Bassi, and M. Skoglund, "Upper bounds on the generalization error of private algorithms for discrete data," JEEE Transactions on Information Theory, vol. 67, no. 11, pp. 7362-7379, 2021.
[37] D. Haussler, "Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik- chervonenkis dimension." Journal of Combinatorial Theory, Series A, vol. 69, no. 2, pp. 217-232, 1995.
11

---

[38] V. Feldman and T. Steinke, "Calibrating noise to variance in adaptive data analysis." pp. 535-544, 2018. [Online]. Available: http:/prooceedings.s httpsesdnnnnmmmppppssssssssennn 8a.html
[39] N. McDonald and A. Weiss, A Course in Real Analysis, 2nd ed. Cambridge, Massachusetts: Elsevier, 2013.
[40] R. M. Gray, Source coding theory, Engineering and Computer Science. Business Media, 2012, vol. 83.
Springer Science
[41] Y. Wu, "Lecture notes on information-theores methods for high-dimensional statistics," Lecture Notes for ECE598YW (UTUC), vol. 16, 2017.
[42] Popoviciu. "Sur les équations algébriques ayant toutes leurs racines réelles," Mathematica, vol. 9, pp. 129-145, 1935.
[43] P. Harremoës and I. Vajda, "On pairs of f-divergences and their joint range." IEEE Transactions on Information Theory, vol. 57, no. 6, pp. 3230-3235, 2011.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] Section follows the abstract statements order.
(b) Did you descrihe the limitations of your work? [Yes] See Section 4.1.
(c) Did you discuss any potential negative societal impacts of your work? [No] We are unaware potential negative societal impacts of this line of work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The i.i.d. assumption is the first paragraph of the introduction. All other assumptions are in the statement of all theorems and corollaries.
(b) Did you include complete proofs of all theoretical results? [Yes] All theoretical results are proved completion the appendix. Nonetheless, some intuition and the most important parts are also given in the main text.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL?[N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "tC63ISQa_zS", "reviewer": "Reviewer_SCNA", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The literature review is very well done, which helps to put the paper contribution in perspective. While no new techniques are introduced, the authors made a good job in refining and combining different existing techniques. As far as the reviewer is concerned, it seems like the bounds presented in this paper are close to the best that can be done with existing techniques at the proposed level of generality. Applying these bounds beyond toy examples still requires some effort (probably a big one), but the paper reveals a clear path to do so. Overall, this paper represents a solid step towards practical generalization bounds.\n\nMinor Suggestions\n- It would be helpful for the reader if the authors emphasize, perhaps in a graphical manner, the taxonomy of current generalization bounds in terms of performance.\n- Bobkov-Götze's theorem has a similar role to the HB inequality, although the former is not presented in the preliminaries. Perhaps it is useful to add the BG theorem to the preliminaries.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "rW13C4kiaZ2", "reviewer": "Reviewer_Bm5Z", "summary": "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.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is technically sound and well-written.\n\nMy major concern about this work is the novelty. The idea of bounding generalization error using Wasserstein distance is presented in [14] and [16] in the reference of the paper. And the techniques used in the paper to tighten the Wasserstein distance-based bounds are originally designed for tightening mutual information-based bounds, including single-letter characterization from [6], random-subset [9] and randomized subsample setting from [1].\n\nHowever, the result obtained by combining those techniques with Wasserstein distance-based bounds is significant. Example 1 shows that the proposed method could provide an order optimal bound for the generalization error of Gaussian mean estimation problem, which seems to be the first order optimal information-theoretic bound based on my knowledge. It was shown in [6] that simply using individual mutual information I(W;Z_i) will result in a sub-optimal bound, so I would like the author to provide more explanation and discussion about this improvements. It seems that the improvement is related to the metric used in the Wasserstein distance. Also, it is the best to include more examples to demonstrate the powerfulness of the proposed bound.  \n\nMinor comments:\n1.\tThe results presented in section 3.3 and 3.4 are quite straight forward, and it is hard for me to see the values of those results based on the discussion in the current paper. More discussion and some potential applications of these results would be helpful. Otherwise, there is no reason to include some looser bounds in the main body of the paper.\n2.\tThe comparison of the Wasserstein distance-based bounds presented in Appendix C should be included in the main body of the paper to demonstrate the tightness of the proposed bound. It would also be helpful to construct a table which summarizes the comparisons between all these bounds.\n3.\tThe ICIMI bound from [12] could be added in Figure 1 as another baseline. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Most limitations are well addressed in Section 3.5 and 4.1. Another limitation is that the Wasserstein distance is hard to evaluate and estimate in practice. I would like the authors to add more discussions to address this issue.   ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "XNlq14_zx2q", "reviewer": "Reviewer_61bD", "summary": "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).\n\nAlso, 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.\n\nThe authors also use the joint-range technique to provide generalization bounds based on f-divergences.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n-The Wasserstien distance is defined using a metric. The most important shortcoming I found with the paper is that there is no discussion on how we can find an appropriate metric for the hypothesis space. I just want to emphasize that the concept of using the geometry of the hypothesis space has been used in learning theory before. For instance for VC classes this seminal work considers the VC classes:\n\n\tHaussler, David. \"Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension.\" Journal of Combinatorial Theory, Series A 69.2 (1995): 217-232.\n\nLater it was used for obtaining bounds on the Radmacher complexity by chaining technique. Another question is what is the impact of the algorithm on the chosen metric? Assume we have a hypothesis space and two different algorithms for learning. Do we need to choose different metrics when analyzing different algorithms for the same hypothesis space?\n\n-The concept of chaining mutual information bounds has been considered in [13], [11], and a recent work by Asadi, Abbe where the authors propose a learning algorithm based on their chaining method. I just want to understand what are the main differences of this paper compared to those results? The aforementioned papers  also provide bounds that depend on the learning algorithm as well as the geometry of the space.\n\n-The example of the Gaussian location model implies that in some cases the proposed bounds can give much tighter characterization of the generalization bound.  Is there any specific practical problem that your generalization bound can give new insights and analysis? Also, does this generalization bound guide us to design a new training algorithm?\n\n-Most of the results in the paper depends on the distribution of output conditioned on a single sample, i.e., P(W|Z_i). I think in most problems it should be hard to quantify this kernel. The authors also discuss the bounds that depend on P(W|S) however those bounds are much looser. Is there any way to improve the bounds based on P(W|S)?\n\n-Another important property of the Wasserstein distance is that it is defined based on “inf” over the coupling. However, in the paper there is no discussion on how to find a good coupling? I think the authors should also comment on this aspect.\n\n-Theorem 2: why do you want to add extra info R? I think we can add extra information by considering a specific coupling.\n\n-Backward channel: I could not understand what is the main idea behind considering backward channel? I think characterizing the kernel P(S|W) is a very very hard problem. How can we use this bound in practice to gain a new insight? I would appreciate it if the authors comment on why they consider the backward channel in the paper. I have looked at the appendix on the connection to the rate distortion theory, but that section is not very clear.\n\n\nSome typos:\nWhat does the word “single letter” mean in the paper? \nLine 33, there are three and in a row and it is difficult to understand the sentence.\nLine 38, what is j?\nLine 151: in the first sentence it seems there is a typo.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the limitations discussed by the authors in the paper is important. Also, I would like to add that the authors should add results regarding how we can choose a good metric and how we can find a good coupling.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no specific ethical concerns with this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Cck-p6x3QtF", "reviewer": "Reviewer_EsUW", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The first four main results of the paper are for single-letter and random-subset generalization bounds in the standard and randomized-subsample settings. Note that in the latter setting, twice the typical number of samples are drawn, but coin flips are used to decide which subset of those samples is actually used; the distributions considered differ in whether the results of those coin flips / the identities of the samples are known. The bounds in the standard setting are showcased by considering a particular application regarding estimating the mean of a Gaussian distribution given its covariance matrix and comparing the proposed bounds to previous Wasserstein / mutual information bounds. Since this setting is simple, the precise generalization error can be computed and is plotted as well; the new bounds are much closer to the correct generalization error than previous work.\n\nThe paper then also discusses how the results above can be made to work with backward channels instead of forward channels (e.g. how knowing the hypothesis changes the distribution over samples), as well as how they can be converted to other information measures, such as launtum information.\n\nOverall, I think this is a thorough collection of theory results that pushes the boundaries relative to a variety of prior work. I am a bit concerned about the practicality of these results (see the Limitations and Societal Impact section), but I would still lean towards acceptance.\n\nMiscellaneous:\n- Line 3: “and their analogous in” analogous -> analogues.\n- Line 153: “tighter than (1)” Took a moment for me to parse this reference, I think it would be clearer if it were more explicit e.g. Inequality (1) or perhaps Formula (1)? Similarly on line 160.\n- Line 210: “impact on the samples’ identities” on -> of\n\n-----\nI have read the author's response and they have addressed my concern about there being cases where these bounds improve on practical cases, so I have adjusted my score accordingly to an accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper itself admits “The Wasserstein distance is difficult to characterize and/or estimate,” and the one application presented (Gaussian mean estimation) is already on the easy side because its generalization can directly be computed. Is there an application where these results produce the generalization bounds, even compared to non-information based techniques?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, the reviewers were positive about the paper. My main concern is regarding its novelty: it seems that this paper combines Wang et al. 2019 with the individual sample approach proposed by Bu et al., 2020 and with the conditional mutual information approach proposed by Steinke and Zakynthinou, 2020, respectively. There are also limitations in terms of how useful the Wasserstein-based generalization bounds proposed in this paper are in practice, particularly regarding estimation of Wasserstein distance from data. The bounds seem difficult to instantiate even for very basic examples. As noted by several reviewers, it is unclear how the paper's results would translate to more complex models. Note that recent work in the area of information-theoretic generalization bounds provide numerical results to fairly sophisticated settings (e.g., the analysis of SGLD by Negrea and Haghifam et. al.) and, despite the bounds themselves often being vacuous, at least they correlate with the generalization behavior of neural networks on real-world data. The reviewers also pointed out several changes to the paper that I view as "mandatory," especially the points raised by reviewer 61bD. 

However, I do find that this paper moves the needle on generalization bounds forward. Despite mostly relying on a combination of existing theoretical tools used in the area of information-theoretic generalization bounds, it combines these tools in a novel way. The limitations/future work section is particularly thoughtful and reveals interesting new research directions. Together, the positive aspects of the paper outweigh its limitations, making me lean towards acceptance --- with the caveat that the authors should add the changes promised in their rebuttal.
Decision: Accept (Poster)