A New Family of Generalization Bounds Using Samplewise Evaluated CMI
Authors: Fredrik Hellström
Giuseppe Durisi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Generalization bounds
information theory
PAC-Bayes
multiclass classification
Natarajan dimension
deep learning

Abstract: We present a new family of information-theoretic generalization bounds, in which the training loss and the population loss are compared through a jointly convex function. This function is upper-bounded in terms of the disintegrated, samplewise, evaluated conditional mutual information (CMI), an information measure that depends on the losses incurred by the selected hypothesis, rather than on the hypothesis itself, as is common in probably approximately correct (PAC)-Bayesian results. We demonstrate the generality of this framework by recovering and extending previously known information-theoretic bounds. Furthermore, using the evaluated CMI, we derive a samplewise, average version of Seeger's PAC-Bayesian bound, where the convex function is the binary KL divergence. In some scenarios, this novel bound results in a tighter characterization of the population loss of deep neural networks than previous bounds. Finally, we derive high-probability versions of some of these average bounds. We demonstrate the unifying nature of the evaluated CMI bounds by using them to recover average and high-probability generalization bounds for multiclass classification with finite Natarajan dimension.

A New Family of Generalization Bounds Using Samplewise Evaluated CMI
Fredrik Hellström
Giuseppe Durisi
Chalmers University of Technology Gothenburg, Sweden frehells@chalmers.cc
Chalmers University of Technology Gothenburg, Sweden durisi @wweeehhaalareremmmmmmmmeeeeeeee
Abstract
We present a new family of information-theoreti generalization bounds, in which the training loss and the population loss are compared through jointly convex function. This function is upper-bounded in terms of the disintegrated, sample- wise, evaluated conditional mutual information (CMI), an information measure that depends on the losses incurred by the selected hypothesis, rather than on the hypothesis itself, is common probably approximately correct (PAC)-Bayesian results. We demonstrate the generality of this framework by recovering and ex- tending previously known coormation-thhorees evaluated CMI, we derive samplewise, average version of Seeger's 's PAC-Bayesian bound, where the convex function is the binary KL divergence. In some scenarios, this novel bound results in tighter characterization of the population loss of deep neural networks than previous bounds. Finally, we derive high-probability versions of some of these average bounds. We demonstrate the unifying nature of the evaluated CMI bounds by using them to recover average and high-probe probbibbbayility generalization bounds for multiclass classification with finite Natarajan dimension.
bounds. Furthermore, using the
Introduction
Information -eeeorttin-thhoretiic generalization bounds, i.e., generalization bounds that expressed in terms of intormatioonthhoreehe metrics such as the Kullback-Leiller (KL) divergence, mutual information, and conditional mutual information (CMI), have emerged useful tools to obtain accurate characterization of the performance deep neural networks. To obtain such bounds, one compares posterior, that is, the distribution over the hypotheses induced by the learning algorithm, reference distribution called the prior, an approach first introduced to provide probably approximately correct (PAC) bounds for Bayesian classifiers [1, 2, 3, 4]. The connection between these results and classic information-theoree with respect the joint posterior and data distribution, bounded in terms of the mutual information between the training data and the hypothesis. These bounds have since been extended in several ways [7. 8, 9, 10, 11. 12, 13, 14, 15].
metrics was clarified in [5, 6]. where the generalization gap, averaged
major step was taken in [16], which a setting where the training set is randomly selected from a larger supersample is considered. We refer to this setup the CMI setting, it leads to generalization bounds terms of the CMI between the hypothesis and training set selection, given the supersample. It turns out that these bounds can be further tightened by observing that the selected hypothesis enters the derivation only through the loss that induces on the supersample. Using this observation, [16] also derives bounds terms of the information encoded in these losses rather than in the hypothesis itself, quantity referred to as the evaluated CMI (e-CMI). Due to the data-processing inequality, these bounds are always tighter than the regular CMI bounds. This observation recently further
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

exploited by [17], which derived samplewise versions of these bounds. Intriguingly, these bounds are both easier to evaluate than their hypothesis- based counterparts, due the lower dimensionality of the random variables involved, and quantitatively tighter for deep neural networks. In particular, while bounds involving information measures based on the hypothesis space tend to increase as training progresses [11, [11, 18), the bound of [17] remains stable.
The results that have so far been derived for the CMI setting pertain only the (weighted) difference between population loss and training loss, or to its squared or absolute value [8, 9, 14, 16, 17, 18]. In the PAC-Bayesian literature, other types of discrepancy measures have been considered, and shown to result in tighter bounds on the population loss. For example, [19, 20, 21, 22] consider the binary KL divergence (i.e., the KL divergence between two Bernoulli distributions) with parameters given by the training and population loss, respectively. while [23, 24] consider arbitrary jointly convex functions. Finally, (25] allows for arbitrary functions. It should be noted that in all of these results, a nomenttggneeaatee function that depends on the selected function has to be controlled for the bound to be computable.
Recently, the e-CMI framework was proven to be expressive enough to allow one to rederive known results in learning theory, e.g., generalization bounds expressed in terms of algorithmic stability, VC dimension, and related complexity measures [17, 26]. Tightening and extending e-CMI bounds, which is the main objective of this paper, has the potential to further increase the unifying nature of the e- e-CMI framework.
Contributions Leveraging a basic inequality involving a generic convex function of two random variables (Lemma 1), we establish several novel disintegrated, samplewise, e-CMI bounds on the average generalization error. Specifically, we present i) square-root bound (Theorem 1) on the generalization error, together with a mean-squared error extension, which tightens the bound recently reported in [17]; ii) linear bound (Theorem 3) that tightens the bound given in [18]; iii binary KL bound (Theorem 4), which is a natural extension to the e-CMI setting of a well-known bound in the PAC-Bayes literature [22]. While the derivation of the first two bounds involves adaptation of results available in the literature, to obtain the binary KL bound we need a novel concentration inequality involving independent but not identically distributed random variables (Lemma 2). As an additional contribution, we show how to adapt the techniques presented in the paper to obtain illustrate the
gigh-probability (rather than average) e- e-CMI bounds (Theorem 7). Furthermore, expressiveness of the e-CMI framework by using our bounds to recover average and high-probability generalization bounds for multiclass classification with finite Natarajan dimension (Theorem 8). Finally, we conduct numerical experiments on MNIST and CIFAR 10, which reveal that the binary KL bound results in tighter characterization of the population loss compared the square-root bound and linear bound for some deep learning scenarios.
Preliminaries and Notation
We let D(P || Q) denote the KL. divergence between the two probability measures P and Q. This quantity is well-defined if P is absolutely continuous with respect to Q. When P and Q are Bernoulli distributions with parameters p and respectively, we let D(P Q) d(y q) p log(p/g) (1 (1-77 (1-p) log((1 p1 - 4)), and we refer to d(p || 4) as the binary KL divergence. For two random variables X and Y with joint distribution Pxy and respective marginals Px and Py, let YY = D(Pxy || Px) denote their mutual information. Throughout the paper, we use uppercase letters to denote random variables and lowercase letters to denote their realizations. We denote the conditional joint distribution of X and Y given an instance 7 = 2 by Pxy|z== and the corresponding conditional distribution for the product of marginals by Px|z== Priz= Furthermore, we let (x;; Y)= = D(Pxy|z== || Py]2=xPy|2=2> which is referred to as the disintegrated mutual information [11]. Its expectation is the conditional mutual information T(X: YIZ) Ez [x)]
CMI Setting Let Z be the sample space and let D denote the gettaagenerainng distribution. Consider a supersample Z gax2, where each entry is generated independently from D. For convenience, we index the columns of Ž starting from and the rows starting from 1. Furthermore, we denote the ith
'hile [17] considers the information stored in predictions rather than losses, referred to as the f-CMI, the derivations therein can be adapted to obtain bounds that depend on the losses, we clarify in Section 2.2.

---

row of E as Zz Let S = (Si..... S,) denote a membership vector, with entries generated indepen- dently according denote the modulo-2 complement S. We refer to S as a membership vector because is used to divide the supersample into an n-dimensional training vector Zs with entries [2s] = Z.s,, and an a-- dimensional test vector Z5 with entries [Z Zz S. To be able handle arbitrary learning settings, we consider learning algorithms as maps A 2" x R + F, where R E R is a random variable (independent of Z and S) that captures the stochasticity of the algorithm and F is space, for instance, parameter space function space. For fixed /t and Zs ã.. A(ž., r) is deterministic function of 2g. The quality of the learning algorithm's 's output is evaluated using a bounded loss func- tion e: F x Z + [0. 1]. We let U be vector of size m, the elements of which are sampled without replacement uniformly at random from (I,...,7) n). For a given realization U = u = (U1..... Um). let Σ, denote the
Bern(1/2) distribution, independently of Z. Let S (1 S 1
S.)
2 matrix obtained by stacking the vectors S.,, for i 1,.... m. Simi- larly, {(AA R), ) denotes the m x 2 matrix of losses obtained by applying ((A(2,, R), elemen- twise eq. We denote the population loss as (A, 2z, r) = Ez (e((,,(((,,,)))
Z")], where Z ~ 'D. The training loss is Lg (A, gg. r) - ((A(2, r), (2.1.). ). In general, for any p-dimensional vector of data points 2, we let L3 (A, kg, = 1 E ((A r),2). 21). Since A(ž,, does not P
depend on Zz. Lg, (A, r) is a test loss. Finally, we let Lp = E &2,.RRlLD(A Zs, R)] denote the average population loss and L = Lz,,, (A, Zs. R)] denote the average training loss.
2 Average Generalization Bounds
In this section, we present the main results of this paper: a new family of disintegrated samplewise e- CMI bounds for the average population loss. High Highh-robabiilty versions of these bounds are given in Section
2.1 Main Lemma
We now present the generic inequality upon which the bounds in this section are based. This inequality, which is similar in nature to the ones provided in [23] and [25], gives us generic framework derive generalization bounds, as it allows for a wide choice of functions for comparing training loss and population loss. A crucial difference compared [23] and [25] that our focus in this section is on average rather than PAC-Bayesiae generalization bounds, and on bounds based on the disintegrated, samplewise e-CMI, rather than traditional KL-based bounds.
Lemma 1. Lei Jy 1], - R be function that is jointly convex in its arguments and is parameterized by 7. Let X and Y be two random variables, and let Y' be a random variable with the same marginal distribution joint distribution of X. is absolutely continuous with respect to the joint distribution of X, Y'. Let 9i (X, Y) and (2(X, Y) be measurable functions with range [0, 1] and finite first moments, such that, for all 7, Ex,y If (X, (),9((X))))) Y))l is finite. Let
Y such that Y' and X are independent. Assume that the
S = log Ex.y' (ex.r-/fflloxxxeee (ex
(I)
and assume that Ey is finite. Then,
sup (Ex. (x, (X,Y)) Ex, (xxxxr En S sup L1 >
II(XYY).
(2)
The proof, which is an application of Jensen's 's inequality and Ponsker-Varadhar 's variational repre- sentation of the KL divergence, is given in Appendix A, along with the proofs of all other results provided in this paper.
Note that contrast, when we derive high- probabiiyyyyltty bounds in Section 3, we need to fix 7. Optimizing y over a set of candidate values in the nigh-probability scenario incurs a union bound cost (27, Sec. 1.2.2].
allowed to optimize y because, in this section, only consider average bounds. In
To apply Lemma 1, we need to identify functions (:.)) for which the moment generating function in (1) can be controlled. A theme throughout this section is that we identify functions fx())) for
3

---

which there exist concentration results that imply that & S 0. This allows us to loosen the bound in (2) by discarding 7
Throughout this section, we assume that the loss is bounded, so that ((:-)) E [0. 1]. Note that the reported results be extended to more general losses by of scaling. In particular, assume that there is function K : F + R., such that, for all f E F, sup, {(f,z) < K (f) (referred to as the hypethesis-dependent range condition in [28]). Then, all of the results that we present for bounded losses also hold for the scaled loss ((f,z)/e (f).
2.2 Extending (f)-CMI Bounds e-CMI
We now apply Lemma to recover the average bounds of [17, 18]. These works derive bounds using the information contained either in the hypothesis itself or the resulting predictions, i.e., the CMI or the f-CMI. We instead derive bounds in terms of the information captured by the matrix of losses, i.e., the e-CMI. For parametric supervised learning algorithms, we can recover the original bounds via the data-processing inequality. This is formalized in the following remark.
Remark Consider a parametric supervised learning setting, where Z X y and A(žs, R) W E F are the parameters of a function Φw : X + y. Let T. denote the m x 2 matrix obtained by projecting each element of En onto X, i.e., the matrix of unlabeled examples. Let @w (ãa) denote the matrix of predictions obtained by elementwise application of ow to Ru. Then, for any fixed & and u,
1 1 (w) S [ow ( S 12"(W:S.).
(3)
We now use Lemma I to recover some of the results reported in [17]. Let A Lage (A, Eg, R)
T:ag: (A, -z; R), where S is an independent copy of S,. For fixed 2, symmetry implies that ss; ] = 0. Furthermore, since ((..)) E [0, 1], we have that A E [-,, Thus, A is 1- sub-Gausee Gabssaasi By using properties of Lub-Gaussian random variables, we can control &, in Lemma I when choosing (:) as A or >A?. The resulting bounds are given in the following theorem.
Theorem (Square-root bound and squared bound). Consider the CMI setting. Then,
LD i
1
2
(4)
i=1
221
(5)
Furthermore,
27 E Ez,n, (L. Zs. -R) (A, (A, - (10 {,
8
(6)
In (4), the expectation over is taken outside of the square root, and the generalization bound is in terms of the disintegrated mutual information. By Jensen's inequality, this is tighter than (5).
As shown in Appendix A, one can further generalize (4) to obtain an upper bound of the form
Z (
Zo);
However, since (7) increases with the size m of the random subset U [17, Prop. 1], we focus only on the case = 1, as this leads to the tightest bound. The same holds for (5), as well as for all of the bounds that we present in the remainder of this section, where we also focus only on m = 1. In contrast, the choice of m = 1 in the squared bound in (6) is suboptimal and actually yields vacuous bound due to the 2/ m term.
It is possible to obtain a bound similar to (4), but where an expectation over R is taken outside the square root and the mutual information also conditioned on R. We present this bound in the following theorem.

---

Theorem 2 (R-conditioned square-root bound). Consider the CMI setting. Then.
72 n1
LD - 7
E Z.R
21 R), 2.);
(8)
1
2T(E(A(Zs, R), 5, R)-
(9)
A similar bound, but given in terms of mutual information rather than e-CMI, is reported in [11, Thm. 2.4]. The randomness of the learning algorithm reduce the mutual information between its output and the selection variable S.. Specifically, one can show that
1 (e(A(22s R), 2,); - R) S)
(10)
which implies that the square-root bound in (5) is tighter than the R-conditioned square-rool root bound in (9). However, the ordering between the disintegrated square-root bound in (4) and the disintegrated R- conditioned square-root bound in (8) is unclear.
Next, we generalize the linear bounds of [18], which samplewise extensions of the bounds in [16]. to the e-CMI framework. We consider two scenarios. For the first one, we assume that 7 = (71 72) are positive constants that satisfy a certain constraint, and let [T, LD) = >n<LL - 72 L). For the second one, we assume that L 0, the so-called interpolating setting, and let f (L, LD)
n (og(2)Lp For both these scenarios, can be shown that & S 0. yielding the following.
Theorem (Linear bound and interpolation bound). Consider the CMI setting. Ler r C R2 denote the set of parameters 7 = (7, that satisfy (1 - 72) + (e - - m))(1 + +2) S 0. Then,
I(e(A(Zs, R), Z.);
LD S min 72L + yer
(11)
71
Furthermore, if O.
n
I[E(A(Zs, R), Z,): Sal2) n (2)(2)
LD S
(12)
The interpolation bound in (12) improves on the linear bound in (11) when L = 0, as the constraint 1-m)== 2 0. This means that n < 0.37, whereas log > 0.69.
implies that 7 4(e 1)
2.3 Binary KL Bound with Samplewise e-CMI
We now derive bounds in terms of the binary KL divergence between the training loss and the test loss. To this end, similar to [27, 29], define
(a lI p) 74 log(1 p + pe?).
(13)
An important property of this function is that
(a d).
(14)
Note that both d. and d(. .) are jointly convex in their arguments. For our next result, we need the following lemma.
Lemma 2. For 11...,,.. n. let X4 Px,, [[X nu jt 4 X,, and j 1 - i=1 Mi. Assume that X; E [0, 1] almost surely and that all X₃ are independent. Then, for every fixed 7 > 0.
E (exxp(nd, (f p))] $
(15)
This inequality, which, to the best of our knowledge, has previously been reported only for identically distributed random variables, follows by combining [30, Lemma 1], [31, Thm. 3], and [29, Eq. (17)) (which is generalization of [27, Lemma 1.1.1] from binary to bounded random variables).
A similar result, with (1.) instead of (- is established [32, Lemma 2].

---

Consider a fixed 2. For each i, Esy [E where S is an independent copy of St Thus,
(.gr): (A, Ez. Ri] = (e(A((2) R), 2.,) + R
21)22)
Es (A, 2s, R)] (A, Rs, R) L2 (A,
(16)
2
This observation allows us to bound the binary KL. divergence between the training loss L. and the
arithmetic mean of the training and population loss, (L+ Lp)/2. Combining (15) and (2), with appropriate choices for the variables and functions therein, we obtain the following result.
Theorem (Binary KL bound). Consider the CMI setting. Then,
<(E.)
a( f..1 1 (T
T(e(A(Zs, R), S(Z)
(17)
2
1=1
which implies that Lp can be bounded as
LD S d- L,
R))
(18)
where
d () sup { p [0,1] d ( q11
9 q
S cc
(19)
2
Similar to Theorem 1, we can obtain a disintegrated version of (18) where the expectation over Ž is outside of the inversion of the binary KL divergence. We present this result in the following theorem.
Theorem 5 (Disintegrated binary KL bound). Consider the CMI setting. Then,
"
LD S Ez d
ERRS (A,
(A, Zs, R8)
Σ
(e(A(Zss R), Z.): S.)
(20)
By using Pinsker's inequality, which implies that 2(g-p)2
p)² 3 S d(q |p). one can weaken (18) to obtain
n
LD LD-
-i|s 1--
(21)
However, since the average over i is inside the square root, this bound is weaker than (5) by Jensen's inequality.
To establish Theorem 4, it is crucial that the supremum over y in Lemma is outside the expectation that defines E,. Indeed, sup, (1 ll p) = d(q p), and with the notation from Lemma 2, we have [22, Thm. 1]
E [nx @ [))] 2 Vn.
(22)
Therefore, having the supremum inside of the expectation would unavoidably lead to an additional term greater than log( /n)/n in the upper bound of (18).
The binary KL bound in (18) is an average, samplewise, e-CMI analogue of the PAC-Bayesian bound with binary KL divergence on the left-hand side, sometimes referred to as Seeger's 's bound [4, 20]. However, as noted after Lemma 2, the concentration inequality needed establish Theorem is refinement of the result used [20]. Also, the dependence on f. and L. in the binary KI. bound is nonstandard. As we show in Section 5, the binary KI. bound in (18) is sometimes tighter than the square-root bound in Theorem and the linear bound in Theorem 3.
The binary KL bounds in (18) and (20) can be tightened by considering affine transformations of the arguments of d(- [l-). However, this does not lead to improvements for the low training loss scenarios that we focus on in this paper. Therefore, we relegate these extensions to Appendix B, where we also present an analogue of Theorem 4 in terms of the samplewise mutual information between the learning algorithm's 's output and the training data, rather than the e-CMI.
While (:-)) does not admit analytical expression, d- (0,-) is tractable. This leads to the following simplified form of the disintegrated binary KL bound in (20) when f. 0.
Theorem 6 (Disintegrated interpolation binary KL bound). Assume that L 0. Then, (20) becomes
Lp < Eg 2 2e Ei_, (eLA R), 2.)..))).)
(23)

---

3 Higb-Probability Bounds
The techniques presented in Section can be adapted to allow for the derivation high-probabilit bounds, in particular through the of exponential inequalities [33, 34, 35]. To demonstrate this, now present two such high-probability bounds.
Theorem 7 (High-probabille probability square-root and binary KL bounds), Let x ((A(ss, R) 2). Fur- thermore, let P 22zS denote the conditional distribution of X given Z and S, and Pa Pxiz denote the conditional distribution of X given Z. Then, with probability at least 5 over the draw of and S.
2
(DCP D(PNIss Px12) + log vi)
En L.g (A, Zs. R) Lzg (A, Zs, R) S n-1
(24)
Furthermore, also with probability at least 1 5 over the draw of Z and S,
( ER Lzg (A, Zs.
Lz (A, Zs R) + L ng (A, Zs. R
1)
Zs. (4.
ER
2
2ym s D(Px2s || Px(z) + log 8
(25)
n2
These probbabbbbbitt bounds involve the empirical test loss of the learner, and not the population loss. However, simple use of the triangle inequality, as detailed in [34, Thm. 3], allows one to make (24) and (25) explicit in the population loss. Note that the information measures that appear in the bounds depend on the full training set, rather than individual samples. As proven in [36], samplewise versions of these tail bounds are typically loose. For instance, the tail bound with samplewise information measures in [37, Lemma 8] contains a constant term and has a detrimental linear dependence on 1/5, instead of the benign logarithmic dependence in (24) and (25). Finally, under stronger technical assumption of absolute continuity, can obtain high-probabilie bounds not only with respect to the draw of Z and S, but also the randomness R of the learning algorithm. We present this result in Appendix B.
4 Expressiveness of the e-CMI Framework
We now illustrate the unifying nature of the e-CMI framework by demonstrating its expressiveness. Specifically, proceeding similarly to [17, 26), we use the e-CMI framework to rederive known bounds in learning theory. In particular, In the next theorem, we provide a bound on the e-CMI appearing in the results reported in Section 2, well bound the data-dependent KI. divergence appearing in (24) and (25).
consider multiclass classification with finite Natarajan dimension.
Theorem 8. Consider a multiclass classification setting, for which 2 = X V, where X is the instance space and y the label space, and assume that [)] = N. Furthermore, assume that the learning algorithm implements a function f + y where f F belongs to a class of finite Natarajan dimension dx [38]. Finally, assume that 2n > dN + 1. Then,
2en ((M)
I(E(A(Zs, RJ, S): 21) S dN log
(26)
dv
Furthermore, with probability at least 8 under the draw of Z and S,
D(P || Pxzz) S dN log (22)
2en
log
(27)
dN
To obtain generalization bounds from Theorem 8, we need to upper-bound the information terms that appear in the bounds of Sections 2 and 3 by using either (26) or (27). While this can be done for any of the noormatiionthhoreete generalization bounds in this paper, we present two concrete examples in the following corollary.

---

Corollary 1. Consider a multiclass classification setting, for which Z = 2 X y, where X' is the instance space and y the label space, and assume that [3]] N. Furthermore, assume that the learning algorithm implements function f X + where f E F belongs to class of finite Natarajan dimension dx [38]. Finally, assume that 2n 2 dx + Then,
2dN log
2em (
LD L S
dN
(28)
n
Furthermore, with probability at least
8 under the draw of 7 and S,
df ER Lz, (A, Es. (s. ER
2 (A. 7s, R) + 1. (A, Zs, R)
2
dy log
(2) 2en dx
log 2 + log
1yπ
(29)
The scaling behavior of (28) with respect to n recovers the standard rate found the literature [39]. This is minimax optimal up to logarithmic term [40, Thm. 29.3].
Comparing the Bounds
We now perform some comparisons between the bounds obtained in Section 2. As it turns out, there is no clear ordering between the different bounds in general. For a first comparison, we consider the interpolating setting, where the training loss is zero. We focus the size m of the random subset U equals 1. Since the squared bound in (6) is vacuous for this choice,
the case where
considered for this comparison. Moreover, we assume that the learning algorithm is, on average, indifferent to permutations of the training set. Specifically, we assume that the value of [(((A(Zs, R), 24); S: equals constant B that does not depend on the index i. For a more straightforward comparison, we also exclude the disintegrated bounds in (4) and (20), and postpone their evaluation to Section 6. Thus, in this section, compare the squarc-root bound in (5), the linear bound in (1I), the interpolation bound in (12), and the binary KL bound in (18). In the following proposition, we establish an ordering between these bounds. The result follows by straightforward arithmetic.
Proposition 1. Assume that I(E(AAZs, 2,) ()) the largest such that of - 4(e 1)(e" - 1 2 Then, the upper bounds on LD are, in increasing order, the interpolation bound in (12), the binary KL bound in (18), the linear bound in (11), and the square-roon bound in (5). If B 2 the ordering between the square-root bound in (11) and the linear bound (5) is inverted.
B for all and that L = 0. Let ooo be O, and assume that B < 2n RJ 0.27.
While Proposition 1 gives the ordering between the bounds for the interpolating scenario, the quantitative difference between them not clear. A numerical illustration given in Figure la, under the same assumptions as in Proposition 1. As established in Proposition 1, the interpolation bound in (12) superior across the range of values for B, and the binary KL bound in (18) is slightly looser. However, while the constant log 2 in (12) is sharp, the derivation is valid only for interpolating learning algorithms. In contrast, the other bounds are only marginally affected when we allow for small, non-zero training loss. This added flexibility shows the usefulness of (18) as compared to (12).
To obtain a more complete picture, we numerically evaluate the bounds for range of values for and B. This is illustrated Figure 1b. While the binary KL bound (18) is tightest for most small values of and f., a region of this space is dominated by the linear bound in (11). When both B and L grow larger, the square-root bound in (5) is the tightest. Thus, the picture that emerges from these comparisons is that, when the training loss is zero, it is best to use (12), while we need (18) for the case of a small, but non-zero, training loss. However, the training loss high, one needs to evaluate all three bounds and take the minimum.
8

---

1.0
Trivial
0.8
0.75
Bound on
0.6
Square root
0.4
Square
Linear
0.25
Interpslation Binary
Binary KL
0.0
0.27
1og12)
0.0
log1212
lng(2)
(a)
(b)
Figure 1: (a): A quantitative comparison between the square-root bound in (5), the linear bound in (11), the interpolation bound in (12), and the binary KL. bound in (18) under the assumptions of Proposition 1. (b): A comparison between the square-root bound in (5), the linear bound (11) and the binary KL bound in (18) under the assumptions of Proposition 1, but with non-zero L. Each point in the figure color-coded according which bound gives the tightest characterization of Lp for the given parameters. For the region labeled Trivial, no bound performs better than the trivial Lp S 1.
0.25
Square roct
0.35
Sqaare noot
Text ererr
0.20
Brary
0.25
SCLB (11, Et. (40)
0.15
0.3
0.15
0.2
0.05
0.05
0.00
0.0
75
250
1000
4000
1000
5000
20000
10
20
30
40
Epochs
(a) MNIST, Adam
(b) CIFARIO, SGD
(c) MNIST, SGLD
Figure 2: Numerical evaluation of the test error in three deep learning scenarios, along with the upper bounds provided by the square-root bound in (4), the binary KL bound in (20) and, when applicable, the interpolation bound (12) and the SGLD bound in [11, Eq. 6].
6 Numerical Results
We now consider three deep learning settings and evaluate the bounds derived in Section 2. To the best of our knowledge, the tightest average generalization bounds available in the literature for typical deep learning scenarios, such as CNNs trained on MNIST [41] or CIFAR1O [42], are found in [17]. These numerical results are based on [17, Eq. 22]. which is version of (4) where the e-CMI is replaced by the f-CMI. In order to perform a direct comparison, we consider the same experimental
setups. The code for our experiments is largely based on the code from [17].3 Additional numerical results for a setting with randomized labels are given Appendix C. detailed description of the training methods, network architectures, and experimental setup is given in Appendix D.
The previous section indicated that the interpolation bound (12) and the binary KL bound in (20) are the superior bounds when the training loss is zero or low, respectively, which is common for deep learning. Hence, we focus on these bounds, as well as on the square-root bound in (4). When evaluating the bounds, we use the classification eтror as the loss function. We consider two learning algorithms, namely stochastic gradient descent (SGD) with a fixed random seed and stochastic gradient Langevin dynamics (SGLD). The first is deterministic learning algorithm with high relevance for current practice. For deterministic learning algorithms, generalization bounds based on the information captured by the weights of neural network are vacuous, but as noted by [17], bounds based on the information contained in the predictions (or the losses they induce) are typically nonvacuous. The second is a randomized learning algorithm, which allows for comparison to weight- based cetemaation-hhoorrtee generalization bounds. For this setting, we also evaluate the SGLD bound of [11, Eq. 6).
Available: httpp:://itthut com//rrayraar/t-CMM http:p///ggggttt.ooo//o//h////tt

---

First, we consider a CNN trained with Adam (a variant of SGD) on binarized version of MNIST, where we only consider the digits 4 and The results are reported Figure 2a. In binary classifi- cation, there is a one-to-one mapping between predictions and losses. Hence, for this scenario, the information captured by the matrix of losses the same as the information captured by the matrix of predictions. For this scenario, the binary KL. bound in (20) significantly improves on the square-root bound in (4). For 7 = 75, 250, and 1000, all of the neural networks that we trained achieved zero training error, making the interpolation bound in (12) valid bound. This bound results in the tightest characterization the test error. However, for 7 4000, the training error was non-zero for some neural networks. As consequence, the interpolation bound in (12) not applicable.
Next, in Figure 2b, we look ResNet-50 pretrained on ImageNet and fine-tuned using SGD on CIFARIO. In multi-class classification, the map from predictions to losses is no longer one-to-one Thus, this is a setting where the e-CMI is potentially lower than the f-CMI. Again, the binary KI. bound in (20) significantly improves on the square-root bound in (4).
Finally, as an example of randomized learning algorithm, we consider CNN trained with SGLD on the binarized MNIST data set. This is shown in Figure 2c. As training progresses, both (20) and (4) improve on the SGLD bound in [11, Eq. 6]. However, the latter is lower for the initial epochs. While (20) reduces the magnitude of this discrepancy, which was also observed in [17]. it does not fully close the gap. This may partially be due the fact that the bound in [11, Eq. 6] has an expectation over R outside of the square root, similar to (8), which may be beneficial during early epochs. Another possibility is that the value that we compute for the mutual information may be an overestimate, especially for low values of the true mutual information. This is an effect of the non-negativity of the mutual information.
Discussion and Limitations
In this paper, we presented several generalization bounds in terms of the evaluated CMI. While the results hold for a generically formulated learning problem, they are derived under the assumption of bounded loss function and independent and identically distributed (i.i.d)) training data. While the boundedness assumption can be alleviated to some degree by using the same type of argument as in [16, Thm. 5. it is unclear to what extent the i.i.d. assumption can be relaxed.
Our experiments demonstrate that some the derived bounds are numerically accurate for several deep learning scenarios. As shown in Appendix C, this remains true also when one considers randomized labels and varies the width, depth, and learning rate of the neural network. These results indicate that this family of bounds is potentially powerful enough to guide the design of deep neural networks. This an intriguing avenue for future research.
Acknowledgements
We thank Hrayr Harutyunyan for helpful comments regarding the numerical evaluation. This work was partly supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation and the Chalmers AI Research Center (CHAIR).
10

---

References
[1] J. Shawe- Taylor and R. C. Williamson. PAC analysis of a Bayesian estimator, In Proc. Conf. Learn. Theory (COLT), July 1997.
[2] D. A. McAllester. Some AlC-Bayssian theorems. In Proc. Conf. Learn. Theory (COLT), Madison, WI, USA, July 1998.
[3] B. Guedj. A primer on PAC- Bay-saaesi learning. arXiv, Jan. 2019.
[4] P. Alquier. User-friendly introduction to PAC-Bayes bounds. arXiv, Nov. 2021.
[5] D. Russo and J. Zou. Controlling bias in adaptive data analysis using information theory. In
Proc. Artif. Intell. Statist. (AISTATS), Cadiz, Spain, May 2016.
[6] A. Xu and M. Raginsky. Information-theeortii analysis of generalization capability of learning algorithms. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Long Beach, CA, USA, Dec. 2017.
[7] A. R. Asadi, E. Abbe, and Verdú. Chaining mutual information and tightening generalization bounds. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Montreal, Canada, Dec. 2018.
[8] H. Hafez- Kolahi, Z. Golgooni. S. Kasaei, and M. Soleymani. Conditioning and processing: Techniques to improve information -tteorrttttt generalization bounds. In Proc. Conf. Neural lnf. Process. Syst. (NeurIPS), Vancouver, Canada, Dec. 2020.
[9] B. Golve, G. Bassi, R. Thobaben, and M. Skoglund. On random subset general- ization error bounds and the stochastic gradient Langevin dynamics algorithm. In Proc. Inf. Theory Workshop (ITW), Riva del Garda, Italy, Apr. 2020.
[10] Y. Bu, S. Zou, and V. V. Veeravalli. Tightening mutual information- bounds on generaliza- tion error. IEEE J. Sel. Areas Inf. Theory, 12):121-130, May 2020.
[11] Negrea, M. Haghifam, G. K. Dziugaite, Khisti, and D. M. Roy. Information theooeiii generalization bounds for SGLD via data-dependent estimates. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Vancouver, Canada, Dec. 2019.
[12] 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 Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Vancouver, Canada, 12 2020.
[13] Hellström and G. Durisi. Fast-rate loss bounds via conditional information measures with applications to neural networks. In Proc. IEEE Int. Symp. Inf. Theory (ISIT), Melbourne, Australia, July 2021.
[14] R. Zhou, C. Tian, and T. Liu, Individually conditional individual mutual information bound on generalization error. In Proc. IEEE Int. Symp. Inf. Theory (ISIT), Melbourne, Australia, July 2021.
[15] G. Neu, G. K. Dziugiate, M. Haghifam, and D. M.. Roy. reformation-thhorced generalization bounds for stochastic gradient descent. In Proc. Conf. Learn. Theory (COLT), Boulder, CO, USA, Aug. 2021.
[16] T. Steinke and L. Zakynthinou. Reasoning about generalization via conditional mutual informa- tion. In Proc. Conf. Learn. Theory (COLT), Graz, Austria, July 2020.
[17] H. Harutyunyan, M. Raginsky, Ver Steeg, and A. Galstyan. Information-theoreet gener- alization bounds for black-box learning algorithms. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Virtual Conference, Dec. 2021.
[18] F. Hellström and G. Durisi. Data-dependent PAC-Bayesian bounds in the random-subset setting with applications to neural networks. Workshop on Inf.Theoretic Methods Rigorous, Responsible, and Reliable Mach. Learn. (ITR3), Virtual conference, July 2021.
11

---

[19] J. Langford and M. Seeger. Bounds for averaging classifiers. CMU Technical report, CMU-CS 01-102, 2001.
[20] M. Seeger. PAC- BaC--Baesian generalisation error bounds for Gaussian process classification. J. of Mach. Learn, Res., 3:233-269, Oct. 2002.
[21] Langford. Quantitarively Tight Sample Complexity Bounds. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA, 2002.
[22] A. Maurer. A note the PAC Bayesian theorem. arXiv, Nov. 2004.
[23] Germain, Lacasse, Laviolette, and M. Marchand. PAC-Bayesian learning of linear classifiers. In Proc. Int. Conf. Mach. Learning (ICML), Montreal, Canada, 2009.
[24] L.. Bégin, P. Germain, F. Laviolette, and J. F. Roy. PAC-Bayesian theory for transductive learning. In Proc. Int. Conf. Artif. Intell. Statist. (AISTATS), Reykjavik, Iceland, Apr. 2014.
[25] O. Rívasplata, I. Kuzborskij, C. Szepesvari, and J. Shawe-Taylor. PAC-Bayes analysis beyond the usual bounds. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Vancouver, Canada, Dec. 2020.
[26] M. Haghifam, G. K. Dziugaite, Moran, and D. M. Roy. Towards unified information- theoretic framework for generalization. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Virtual Conference, Dec. 2021.
[27] O. Catoni. BaC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learn- ing, volume 56. IMS Lecture Notes Monogr. Ser., 2007.
[28] M. Haddouche, B. Guedj, O. Rivasplata, and J. Shawe- Taylor PAC-Bayes unleashed: Generali- sation bounds with unbounded losses. Entropy, 23(10), Oct. 2021.
[29] D. A. McAllester. A PAC-Bayesian tutorial with dropout bound. arXiv, July 2013.
[30] Y. Seldin, Laviolette, N. Cesa-Bianchi, J. Shawe-Taylor, and Auer. PAC-Bayesian inequali- ties for martingales. IEEE Trans. Inf. Theory, (812))708666677773 Aug. 2012.
[31] W. Hoeffding. On the distribution of the number of successes in independent trials. The Annals of Mathematical Statistics, 2733)77 Sep. 1956.
[32] J. Guan, Z. Lu, and Y. Liu. Improved generalization risk bounds for meta-learning with PAC-Bayes-kl analysis. https: // openreview. net/ forum? id= XgS9YPYtdj. 2021.
[33] Z. Mhammedi, P. Grünwald, and B. Guedj. PAC-Bayes un-expected Bernstein inequality. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Vancouver, Canada, Dec. 2019.
[34] Hellström and G. Durisi. Generalization bounds via information density and conditional information density. IEEE J. Sel. Areas Inf. Theory, 1(3):824-833) Dec. 2020.
[35] Grünwald, T. Steinke, and L. Zakynthinou. PAC-Bayes, MAC-Bayes and conditional mutual information: Fast rate bounds that handle general VC classes. In Proc. Conf. Learn. Theory (COLT), Boulder, CO, USA, Aug. 2021.
[36] Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Formal limitations of sample-wise informationntheerrett generalization bounds. In 2022 IEEE Inf. Theory Workshop (ITW), Mumbai, India, Nov. 2022.
[37] H. Wang, Y. Huang. R. Gao, and F. Calmon. Analyzing the generalization capability of SGLD using properties of Gaussian channels. Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Virtual Conference, Dec. 2021.
[38] B. K. Natarajan. On learning sets and functions. Machine Learning, 4:67-97, 1989.
[39] Y. Guermeur. Large margin multi-category discriminant models and scale-sensitive psi- dimensions. Research report, INRIA, 2004.
12

---

[40] S. Shalev-Shwarts and S. Ben-David Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, Cambridge, U.K., 2014.
[41] L. Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Process. Mag., 29(6):141-142 2012.
[42] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[43] M. D. Donsker and S. R. S. Varadhan. Asymptotic evaluation of certain Markov process expectations for large time, i. Comm. Pure Appl. Math,
1975.
[44] Y. Polyanskiy and Y. Wu. Lecture Notes On Information Theory. 2019.
[45] M. J. Wainwright. Sige-Dimensional Statistics: a Non-Assyptotiic Viewpoint. Cambridge Univ. Press, Cambridge, U.K., 2019.
[46] D. Haussler and P. M. Long. A generalization of Saucr's lemma. Combinatorial Theory, Series A, 71(2):21-2240 1995.
[47] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proc. Conf. Uncertainty in Artif. Intell. (UAI), Sydney, Australia, Aug. 2017.
[48] I. Csiszar and J. Körner. Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge Univ. Press, Cambridge, U.K., 2nd edition, 2011.
[49] G. K. Dziugaite and D. M. Roy. Data-dependent PAC-Bayes priors via differential privacy. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Montreal, Canada, Dec. 2018.
[50] A. Ambroladze, Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Vancouver, Canada, Dec. 2006.
and J. Shawe-Taylor. Tighter PAC-Bayes bounds. In
[51] G.K. Dziugaite, K. Hsu, W. Gharbieh, and D.M. Roy. On the role of data in PAC-Bayes bounds. In Proc. Artif. Intell. Statist. (AISTATS), San Diego, CA, USA, Apr. 2021.
[52] M. Perez-Ortiz, O. Risvaplata, J. Shawe- Shawe-Taylor, and C. Szepesvari. Tighter risk certificates for neural networks. J. of Mach. Learn. Res., 22(227), Aug. 2021.
[53] L. Paninski. Estimation of entropy and mutual information. Neural Computation, 15(6): 1991- 1253, June 2003.
13

---

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] We clarify our contributions by specifically referencing where they be found in the paper.
(b) Did you describe the limitations of your work? [Yes] We specify the assumptions and settings for which our results hold.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(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 of assumptions of all theoretical results? [Yes] The assump- tions are stated in Section I or in the Theorem statements.
(b) Did you include complete proofs of all theoretical results? [Yes] Full proofs are provided in Appendix A.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as URL)? [Yes] Yes, this is described in the file readme.ter txt in the supplementary material.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] This is specified in the supplementary material.
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] All random results include error bars.
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] This is specified in the supplementary material.
4. If you are using existing assets (e.g.. code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] The assets that we use are cited in Section 6 and Appendix D.
(b) Did you mention the license of the assets? [Yes] The license is discussed in Appendix D.
(c) Did you include any assets either in the supplemental material
URL? [Yes]
See supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] The data used are standard data sets that only include images of objects and animals.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] The data used are standard data sets that only include images of objects and animals.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "jfReBe3wbMp", "reviewer": "Reviewer_kjBx", "summary": "This paper presents a new family of information-theoretic generalization bounds in terms of the disintegrated, sample-wise, evaluated conditional mutual information (CMI), an information measure that depends on the losses incurred by the selected hypothesis rather than on the hypothesis itself. The authors demonstrate the generality of this framework by recovering and extending previously known information-theoretic bounds. In some scenarios, this novel bound results in a tighter characterization of the population loss of deep neural networks than previous bounds.\n", "questions": "I am curious if the proposed e-CMI bound could provide a tight characterization of the generalization for the Gaussian mean estimation example considered in section IV-A of [10]? If it works, it would be a good example for readers to compare different types of bounds and understand the idea.\n\nI have one minor comment about the organization. The high-probability bound in section 3 seems to be standard in this type of analysis, and the usage of e-CMI is more critical here. Maybe the Gaussian example and the current Section 4 (Appendix B.3) should be highlighted?\n\n--------------------------------\nPost rebuttal:\nThe explanation of the Gaussian example resolves my concern. It is a nice paper. I will keep my score unchanged.\n\n\n", "limitations": "I think the authors fully addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper tightens existing information-theoretic generalization error bound using a simple but effective idea, i.e., the information measure involves the losses incurred by the selected hypothesis is always smaller than that of the hypothesis itself. Remark 1 clearly states this benefit using data processing inequality. Although a similar idea of using f-CMI has been adopted in [15], such an improvement significantly enlarges the usage of information-theoretic generalization error bound as it can be evaluated numerically for deep neural networks, as shown in Sections 5 and 6.\n\nThe paper is well-written and technically sound to me.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_dUHa17zLqb", "reviewer": "Reviewer_CMvk", "summary": "PAC-Bayes generalization bounds are often derived from Donsker Varadhan, allowing one to bound a function g that depends on the empirical risk and risk of the predictor. Choosing different forms of g gives rise to different bounds, that may be tighter or loser depending on the regime (often empirical risk magnitude). When it comes to information theoretic bounds, these bounds often come in the most “basic” form, that is comparable to taking g to be of a form of risk - empirical risk. Part of the contribution of the paper is deriving a diverse set of bounds that depend on information-theoretic quantities, similarly as it’s been done in PAC-Bayes setting. The authors present both, bounds that hold in expectations, and high probability bounds.", "questions": "The comment under Theorem 8 says that the “resulting bounds essentially recover previously established generalization guarantees”. Are these previously established guarantees optimal? Are there lower bounds? What does “recover” here mean? Is the rate wrt the number of samples optimal in the minimax sense?\n\nNumerical results (Section 6): \n- the authors do not really explain what they hope to gain by performing the empirical evaluations, and what questions they are answering. It seems that the motivation is evaluating the numerical tightness of the bounds. Is that right? It would have been nice to extend the evaluation in a few dimensions, beyond varying the number of training epochs and the number of training points. I encourage the authors to check out a paper by Dziugaite et al (\"In search of robust measures of generalization\") and proposed evaluation frameworks. How do the bounds vary as the depth changes? Width? As the learning rates vary? \n- What insight would we gain from the bounds if they are tight in the cases tested? What insight into generalization in deep learning in general do evaluated CMI bounds provide?\n- I wanted to confirm that the bounds for SGD (Adam) are for unperturbed-in-any-way classifiers, given that evaluated CMI is used. How was the averaging over draws of the data been done?\n\nOther comments:\n\n - line 27 missing Neu et al COLT ’21, and Haghifam et al ’20 reference;\n\n- Line 39: sounds like the measures are overfitting… but in any case, overfitting is a loaded word and here the authors should choose a different word precisely describing what they mean, in my opinion\n- Eq. 25 bottom line, in P_{lambda | \\tilde{Z}S} is it supposed to be  \\tilde{Z}_S?", "limitations": "There is no explicit discussion of limitations. The assumptions are stated, though, but it might be good to add a short paragraph on the main assumptions that most theorems use, and that could be relaxed in future work. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The connection between PAC-Bayesian bounds and information theoretic ones is one that is, by now, well understood. Indeed, Catoni's 2004 manuscript already spells out the relationship, but it's one that occasionally needs to be rediscovered or reiterated in the literature when we have our heads down and we forget to exploit this connection.\n\nIs this work sufficiently novel/technical? The basic techniques for simultaneously deriving high probability and expected generalization bounds in the PAC-bayesian/info-theory setting have been provided, for example, in Hellstrom and Durisi (who the authors cite) and expanded recently by Grunwald, Steinke, and Zakyinthinou. And the MGF bounds for different g functions follow fairly trivially from Lemma 1, which itself appears in various forms in a number of papers (including Lever et al 2012 and some other works by Shawe-Taylor) used to derive basically any PAC-Bayes bound (just an expectation version of it). \n\nStill, somehow the work on mutual information bounds has never gone beyond linear comparisons of the risk and empirical risk (leading to bounds on expected generalization error). The bounds displayed here for the case where empirical risk is zero are particularly interesting in my opinion, as similar bounds have been derived recently, but not from this perspective. And so I think in fact we had lost sight a bit about the role of a jointly convex comparator and it will be a useful observation for this subcommunity to reacquaint themselves with.\n\nWhile the idea of combining these old insights from PAC-Bayes to mutual information bounds seems now obvious, the form of the resulting bounds (e.g., Theorem 4) is not what I expected, and so there seem to be some surprising consequences.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YIOHs54K_G0", "reviewer": "Reviewer_PHyo", "summary": "This paper derives new information-theoretic generalization bounds based on sample-wise evaluated CMI, among which the square-root bound and the linear bound are tighter than existing bounds, and the binary KL bound is empirically shown to be superior for low-training loss settings. Furthermore, they also show that the derived bounds can be used to recover generalization bounds for multiclass classification with finite Natarajan dimension.", "questions": "1. How tight are the bounds in Theorem 8? Is it possible to have some plots demonstrating how much the improvement is?\n2. It may be worth mentioning in previous sections that some terms in the derived bounds will later be shown to have upper bounds in Section 4.", "limitations": "The assumptions made for the theorems to hold are stated clearly.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper is rich, presenting a series of results both novel and deep. The presentation is complete in the sense that discussions on the comparison of the bounds and the corresponding numerical demonstration are included.\n\nWeaknesses:\nThe notation is heavy, which is necessary, but makes it a bit hard to follow all the results. Maybe adding a table that concludes the derived bounds in Section 5 will make the comparison part more clear.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5P-P4Soi68Y", "reviewer": "Reviewer_4bSW", "summary": "This paper considers the problem of providing generalization bounds based on the information-theoretic measures. In particular, this paper is on extending and improving the work by Steinke-Zakynthinou and Harutyunyan et al. One line of work in this area is on proving generalization bounds based on “sample-wise” measures, initiated by Bu et al. The main contribution of this work is proving new generalization bounds by combining the idea of evaluated CMI and sample-wise generalization bounds. The authors also provide some generalization bounds based on “disintegrated mutual information” formalized by Negrea et al. One generalization bound which is new in this line of work is the binary KL bounds in Section 2.3. Furthermore, the authors provide some numerical results showing that their bounds are not vacuous in DL settings. \n\n", "questions": "I have raised some concerns and asked several questions in the Strengths And Weaknesses part.", "limitations": "I could not find any section on the potential limitations in the paper. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The most interesting aspect of the paper is providing a generic tool in Lemma 1 which can be used to redervie existing bounds, and proving new results. Also, the results on the binary KL bounds are completely novel, and have not been reported before.\n\nMy main concern about this paper is novelty. It seems the authors combine, in a straightforward way, a line of work by Steinke-Zakynthinou, Harutyunyan et al., and Bu et al. Also, in terms of technical novelty, I found the proof of Lemma 1 straightforward. I would like the authors to clarify on the novelty of their work.\n\n-How can we compare the high probability bounds in Section 3 with the results of Grünwald-Steinke-Zakynthinou, Hellström-Durisi? Are the bounds in the paper tighter?\n\n-Is the result in Theorem 8 minmax optimal?  \n\n-I would like to raise a general concern regarding the numerical results. In general, in learning theory we use the generalization frameworks to gain new insights regarding the algorithms. For instance, the existing results for generalization of SGD show that the size of the weights can determine the generalization performance; for SGLD, we know the covariance of the training samples’ gradients affects the generalization, etc. I would like to compare this approach with the case that we are “only” interested in the “value” of the generalization error. In the former case, we often use the validation set, and the numbers we report can accurately estimate the test error. First question is what can we learn about your numerical results? From the experiment details, I think you need the holdout samples to estimate the mutual information.  If you use the holdout samples to estimate the test error, what would be the results? In general, what is the gain of using your bounds compared to the validation set approach? \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept