Information-theoretic generalization bounds for black-box learning algorithms
Authors: Hrayr Harutyunyan
Maxim Raginsky
Greg Ver Steeg
Aram Galstyan
Venue: NeurIPS 2021 Poster (2021)
Keywords: generalization
information theory
deep learning theory
stability
memorization

Abstract: We derive information-theoretic generalization bounds for supervised learning algorithms based on the information contained in predictions rather than in the output of the training algorithm. These bounds improve over the existing information-theoretic bounds, are applicable to a wider range of algorithms, and solve two key challenges: (a) they give meaningful results for deterministic algorithms and (b) they are significantly easier to estimate. We show experimentally that the proposed bounds closely follow the generalization gap in practical scenarios for deep learning.


Information-theeretie generalization bounds for black-box learning algorithms
Hrayr Harutyunyan's Maxim Raginsky", Greg Ver Steeg', Aram Galstyan' USC Information Sciences Institute, 2 University of Illinois Urbana-Champaign
Abstract
We derive reformatiin-theorreter generalization bounds for supervised learning al- gorithms based on the information contained in predictions rather than in the output of the training algorithm. These bounds improve over the existing information- theoretic bounds, are applicable to a wider range of algorithms, and solve two key challenges: (a) they give meaningful results for deterministic algorithms and (b) they are significantly easier to estimate. We show experimentally that the proposed bounds closely follow the generalization gap in practical scenarios for deep learning.
1 Introduction
Large neural networks trained with variants of stochastic gradient descent have excellent gener- alization capabilities, even in regimes where the number of parameters is much larger than the number of training examples. Zhang et al. [41] showed that classical generalization bounds based on various notions of complexity of hypothesis set fail explain this phenomenon, as the same neural network can generalize well for one choice of training data and memorize completely for another one. This observation has spurred tenacious search for degrrihhm-dependent and data-dependent generalization bounds that give meaningful results in practical settings for deep learning [17].
One line of attack bounds generalization error based the information about training dataset stored in the weights [39, 4, 22, 6, 33, 14, 23, 27]. The main idea is that when the training and testing performance of a neural network different, the network weights necessarily capture some information about the training dataset. However, the opposite might not be true: A neural network can store significant portions of training set in its weights and still generalize well [32, 40, 21J. Furthermore, because of their information-thhrt theoretic nature, these generalization bounds become infinite or produce trivial bounds for deterministic algorithms. When such bounds are not infinite, they are notoriously hard to estimate, due to the challenges arising in estimation of Shannon mutual information between high-dimensional variables (e.g.. weights of a ResNet and training dataset).
This work addresses the aforementioned challenges. We first improve some of the existing ioninaationnhhorettii generalization bounds, providing unified view and derivation of them (Sec. 2). We then derive novel generalization bounds that measure information with predictions, rather than with the output of the training algorithm (Sec. 3). These bounds applicable wide range of meth- ods, including neural networks, Bayesian algorithms, ensembling algorithms, and non-parametric approaches. In the case of neural networks, the proposed bounds improve the existing weight- based bounds, partly because they avoid counter- counter-productiee property of weight-based bounds that information stored in unused weights affects generalization bounds, even though it has effect on generalization. The proposed bounds produce meaningful results for deterministic algorithms and are significantly easier to estimate. For example, case of classification, computing our most efficient bound involves estimating mutual information between a pair of predictions and a binary variable.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We apply the proposed bounds to ensembling algorithms, binary classification algorithms with finite VC dimension hypothesis classes, and to stable learning algorithms (Sec. 4). We compute our most efficient bound on realistic classification problems involving neural networks, and show that the bound closely follows the generalization error, even in situations when a neural network with 3M parameters is trained deterministically on 4000 examples, achieving 1% generalization error.
2
Weight-based generalization bounds
We start by describing the necessary notation and definitions, after which we present some of the existing weigh-based information-theorete generalization bounds, slightly improve some of them, and prove relations between them. The purpose of this section is to introduce the relevant existing bounds and prepare grounds for the functional conditional mutual information bounds introduced in Sec. 3, which we consider our main contribution. All proofs are presented in Appendix A.
Preliminaries. We use capital letters for random variables, corresponding lowercase letters for their values, and calligraphic letters for their domains. If X is random variable, X denotes an independent copy of X. For example, if (X, Y) is pair of random variables with joint distribution Px,y, then the joint distribution of (X, Y) will be Px y Px @ Pr Px @ Py. A random variable X is called o-subgaussian if E exp(t(X - ExX)) < (xxp(o2t//2) Vt E R. For example, random variable that takes values in (a, bj almost surely, is (b - a)//2suugaausian. Given probability measures P and Q defined on the same measurable space, such that P is absolutely continuous with respect to Q, the Kullback-Leibler divergence from P to Q is defined as KL((P || Q) = log aP dP, aQ
where dP aQ the Radon-Nikodym derivative of P with respect to Q. If X and Y are random variables defined on the same probability space, then KL (X || Y) mutual information between random variables X and Y is ((;Y) this paper, all information-theoreti quantities are measured in nats, instead of bits. Throughout the paper [n] denotes the set (1,2....,y) n). Finally, if A (01,...,,,) is collection, then A_; & (ai,..., 0;-1, (i+11.......................1... an.)
denotes KL (Px || Py). The Shannon
KL (L.xxxy || Px @ Py). In
Theorems proved in the subsequent sections will be relying on the following lemma. Lemma 1. Let ( V be pair of random variables with joint distribution Pv.a. If g(6, v) measurable function such that Eq, & [g } exists and g( (b, 4 is o-subgaussian, then
Ex, v 1,( } Eg, [o( T)] S (202I(
(1)
Furthermore, if g( T) is o-subgaussian for each & and the expectation below exists, then
Es,0 [g((0, V) - E.g g =))² < (T vD + log
(2)
and
1) 2() (T² v) +lg log
P (( V) Es (
Ve > 0.
2
The first part of this lemma is equivalent to Lemma of Xu and Raginsky [39], which in turn has its roots in Russo and Zou [29]. The second part generalizes Lemma 2 of Kafez-Kolahi et al. [13] by also providing bounds on the expected squared difference.
2.1 Generalization bounds with input-output mutual information
Let S = (Zz, Zz...., Zn) D be a dataset of n i...d examples, R R be source of randomness (a random variable independent of S) and : z" x R + W be training algorithm. Let W = A(S, R) be the output of the training algorithm applied on the dataset S with randomness R. Given loss function E W x Z + IR, the empirical risk is Cemp(A) (A, S, It) = E &(W, Z,) and the population risk is L(A, S, R))
Enzn E(W, Z'), where Z' is a test example independent from and R. The generalization gap, also call generalization emoor is C(A, S, R) Lemp (A, S. R). In this setting, Xu and Raginsky [39] establish the following information-theoret value of the expected generalization gap.
bound on the absolute

---

Theorem 2.1 (Thm. of Xu and Raginsky [39]). If Z'), where Z' D, is o-subgaussian for all w E W, then
20²I(W:S)
ES.R (A(A, R) - (A,5, S
(4)
n
We generalize this result by showing that instead of measuring information with the entire dataset, one can measure information with a subset of size m chosen uniformly at random. For brevity, hereafter we call subsets chosen uniformly at random just "random subsets".
Theorem 2.2. Let U be random subset of [n] with size m, independent of S and R. If f(w, Z'), where Z' D, is o-subgaussian for all W, then
20²
Bs.a (A,,, - Cempl (A, (A) S Euwi V I(W;Sw):
(5)
and
40² n
Es,8 (C(A, Lemp S,),
(I(WS))+
With a simple application of Markov's inequality one can get tail bounds from the second part the theorem. Furthermore, by taking square root of both sides of (6) and using Jensen's inequality on the left side, one can also construct an upper bound for the expected absolute value of generalization gap. Es.a (A,, R) Lemp( A, S, R)]- These observations apply also to the other generalization gap bounds presented later this work.
Note the bound on the squared generalization gap is written only for the case m = n.. is possible to derive squared generalization gap bounds of form 4x- (En-tt I(W; S.) log 3). Unfortunately, for small m the log constant starts to dominate, resulting in vacuous bounds.
Picking small m decreases the mutual information term in (5), however, it also decreases the denominator. When setting the bound of (5) becomes n i=1 V 22 I(W: Z.), matching the result of Bu et al. [6] (Proposition 1). A similar bound, but for a different notion of information, was derived by Alabdulmohsin [2]. Bu
n, we get the bound of Xu and Raginsky [39] (Thm. 2.1). When
Σ
al. [6] prove that the bound with m = tighter than the bound with m = n. We generalize this result by proving that the bound of (5) is non-descreasing in YTt.
Proposition 1. Let m E In - 1}, U be a random subset of [n] of size m, U' be a random subset of size + 1, and Φ + IR be any non-decreasing concave function. Then
Ey ( (= S Er & + I(W:5w)
When dxx) VT. this result proves that the optimal value for in (5) is 1. Furthermore, when use Jensen's 's inequality to move expectation over U inside the square root in (5), then the resulting
bound becomes 2 Eu-U I(W; Sw) and matches the result of Negrea et al. [22] (Thm. 2.3).
These bounds are also non con-decreasing with respect to m (using Proposition with <(z) xt).
Thm. 2.1 can be used to derive generalization bounds that depend on the information between W and single example Z; conditioned the remaining examples Z-i (Zi,..., Zi-1, Zit1,..., Zm
Theorem 2.3. If (ww, Z'), where Z' D, is o-subguussian for all W, then
ES.R S) Cemp((,,)))) (A,
<
20= 2, Z_.)
(8)
n i=1
and
2
EsSa (C(A, R) (A, (A) <
Σ
I(W: Z, Z_,) + log
n
3

---

This theorem is a simple corollary of Thm. 2.2, using the facts that I(W; 2,) S I(W; Z Z-1)
and that IWW :) is upper bounded by Σi= I(W; Z, Z-1), which is also known as erasure information [35]. The first part of it improves the result of Raginsky et al. [26] (Thm. 2), as the averaging over i is outside of the square root. While these bounds are worse that the corresponding bounds of Thm. 2.2, it is sometimes easier to manipulate them analytically.
The bounds described above measure information with the output W of the training algorithm. In the case of prediction tasks with parametric methods, the parameters W might contain information about the training dataset, but not use it to make predictions. Partly for this reason, the main goal of this paper is to derive generalization bounds that measure information with the prediction function, rather than with the weights. In general, there no straightforward way of encoding the prediction function into a random variable. However, when the domain 2 is finite, we can encode the prediction function as the collection of predictions on all examples of 2. This naturally leads us to the next setting (albeit with a different motivation), first considered by Steinke and Zakynthinou [33], where one first fixes a set of 2n examples, and then randomly selects n of them to form the training set. We use this setting provide prediction-based generalization bounds in Sec. 3. Before describing these bounds we present the setting of Steinke and Zakynthinou [33] in detail and generalize some of the existing weight-based bounds in that setting.
2.2 Generalization bounds with conditional mutual information
Let Ž E znx2 be a collection of 2n i.i.d samples from D. grouped in n pairs. The random variable S ~ Uniform( {0, 1}") specifies which example to select from each pair to form the training set Zs = (Z.,s > Let R be random variable, independent of Z and S, that captures the stochasticity of training. In this setting Steinke and Zakynthinou [33] defined condition mutual information (CMI) of algorithm A with respect to the data distribution D as
(AI (A(2s, S ž) = E (A(is, R); S),
(10)
and proved the following upper bound on expected generalization gap.
Theorem 2.4 (Thm. 2, Steinke and Zakynthinou [33]). If the loss function E(w, 2) E [0, 1], Vw e
W, 2 E Z, then the expected generalization gap can be bounded as follows:
R2,5 [[AA, 2s, R) Cemp (A, Es, Ri S V CMI.(A).
(11)
Haghifam et al. [14] improved this bound in two aspects. First, they provided bounds where expectation over Z is outside of the square root. Second, they considered measuring information with subsets of S, as we did in the previous section.
Theorem 2.5 (Thm. 3.1 of Haghifam et al. [14]) Let m E [n] and U C [n]] be a random subset of size m, independent from R, Z, and S. If the loss function E(w, 2) [0,1], Vi E W, E 2, then
E2,s,R C(A,Zs. R)) - Lomp (A, 2s, r0]] < E2a2 V Ensy T(A(Es, ();
(12)
Furthermore, for m 1 they tighten the bound by showing that one can move the expectation over U outside of the squared root (Haghifam et al. [14], Thm 3.4). We generalize these results by showing that for all m expectation over U can be done outside of the square root. Furthermore, our proof closely follows the proof of Thm. 2.2.
Theorem 2.6. Let E [n]] and U C [n]] be random subset of size m, independent from R. 2, and S. If f(w. 2) E [0, 1]. Vw E W, 2 E Z, then
B2,5. [(A, Žs. R) - Leup (A, R)]
2 < E Bz V I(A(2s, Rw) (13)
and
Bg,5, (C(A, 2s, R) -emm (A, (A, Zs, R1)
8 (Ez IA R); + +).
S
(14)
n

---

The bound of (13) improves over the bound of Thm. 2.5 and matches the special result for m 1. Rodriguez- Galvez et al. [28] proved even tighter expected generalization gap bound by replacing [[,,Zs, R); S. Z 2) with T (Asss R); Su Zu 2n). Haghifam et al. [14] showed that if one takes the expectations over 2 inside the square root (12), then the resulting looser upper bounds become non-decreasing over m. Using this result they showed that their special case bound for = 1 the tightest. We generalize their results by showing that even without taking the expectations inside the squared root, the bounds of Thm. 2.5 are non-decreasing over We also show that the same holds for our tighter bounds of (13).
Proposition 2. Let m E [n - 1). U be a random subset of [n] of size m. U' be a random subset of size m 2 be any fixed value of Z, and Φ 12 + IR be any non-decreasing concave function. Then
Bu- Φ ((A(S,, R); S Bu &
mm+1 T(A(2s, R);
(15)
777
By setting d(x) z, taking square root of both sides of (15), and then taking expectation over 2, we prove that bounds of (12) are non-decreasing over m. By setting o(x) = va and then taking expectation over ž, we prove that bounds of (13) are non-decreasing with m.
Similarly to the Thm. 2.3 of the previous section, Thm, A. presented in Appendix A establishes generalization bounds with information-theorett stability quantities.
3 Functional conditional mutual information
The bounds in Sec. 2 leverage information in the output of the algorithm, W. In this section we focus on supervised learning problems: 2 = X' x y. To encompass many types of approaches, we do not assume that the training algorithm has an output W. which is then used to make predictions. Instead, we assume that the learning method implements a function f Z" x X' x R - X. that takes a training set z, a test input z', an auxiliary argument capturing the stochasticity of training and predictions, and outputs a prediction f(2, 2², r) on the test example. Note that the prediction domain I. can be different from D. This setting includes non- non-paramen parametric methods (for which W is the training dataset itself), parametric methods, Bayesian algorithms, and more. For example, in parametric methods, where a hypothesis set = (h.:: : X + w E W} is defined, [(z, x, r) = (r))
In this supervised setting, the loss function é: K. x y + R measures the discrepancy between a prediction and a label. As in the previous subsection, we assume that collection of 2n i.i.d examples Z D is given, grouped in n pairs, and the random variable S Uniform 1)") specifies which example to select from each pair to form the training set Zş (Z..s, ) Let be an auxiliary random variable, independent of Ž and S, that provides stochasticity for predictions (c.g.. in neural net- works R can be used to make the training stochastic). The empirical risk of learning method f trained on dataset 2 with randomness It is defined as Lemp (J, 2s. R2) = 1 E'= e([(2s, X,, R),, Y,). The population risk is defined as L(f, Σs, R) = EZzzD (f X', R), Y"). Before moving forward we adopt two conventions. First, if z is collection of examples, then and y denote the collection of its inputs and labels respectively. Second, if is a collection of inputs, then [(z, 2, r) denotes the collection of predictions on after training on with randomness r.
We define functional conditional mutual information (f-CMI).
Definition 3.1. Let D, S. R, S,S be defined as above and let C [n]] be subset of size m. Then pointwise functional conditional mutual information f- f-CMI(f, 2, u) is defined as
f-CMI(f, 2, u) = [(f Rus R); Sw). while functional conditional mutual information f-CMI (f, u) is defined as f-CMIp(f. u) Eg f- f-CMI(f, u).
(16)
(17)
When u = [n] we will simply use the notations f-CMI(f, and f-CMIo(f). instead of F-CMT(J, 2, (n]) and J-CMI [rl), respectively.
Theorem 3.1. Let U be random subset size m, independent of Z, S. and randomness of training
algorithm f. If ((G.v) v) E [0, 1], Vg e K, 2 E Z, then
E E, [CS, Žs. R) Cemp (f, Żs, R)) E EgnZZun V m
2 f-CMI(f 2, u),
(18)
5

---

and
8 (B (-
R2 (cf,, Zs, R) Lemp 2s, R))
S n
(19)
For parametric methods, the bound of (18) improves over the bound of (13), as the Markov chain
(2g. S. A(ās, R) fās,, Tu. R) allows use the data processing inequality (f T.. R); S.) < [[A(ss R); S.). For deterministic algorithms / (A(ās); S.) is often equal to (S,)) = m log 2. as most likely each choice of S produces a different W A(ās). In such cases the bound with I(W;S, S.)) is vacuous. In contrast, the proposed bounds with f-CMI (especially when m = 1) do not have this problem. Even when the algorithm is stochastic, information between W and S,, can be much larger than information between predictions and S., as having access to weights makes easier to determine S. (e.g., by using gradients). A similar phenomenon has been observed in the context of membership attacks, where having access to weights a neural network allows constructing more successful membership attacks compared to having access predictions only [21, 12].
Corollary 1. When m = n, the bound of (18) becomes
E2,n, 2f, 2s. R) Camp (f. Zs. R)
s B 2 V J.CMI(F. S
2 f. (20)
For parametric models, this improves over the CMI bound (Thm. 2.4), as by data processing inequality, f-CMIp(f) = (ff X, R); 2) = (A(Zs, R); S Ž) CM)p(A).
Note that the collection of training and testing predictions s( X, Rt) cannot be replaced with only testing predictions f(žs. Se))()), R). As an example, consider an algorithm that memorizes the training examples and outputs constant prediction any other example. This algorithm will have non-zero generalization gap, but Xnee())) R) will be constant and will have zero information with conditioned on any random variable. Moreover, we replace f(Zs, X, R) with only training predictions f(z. Xs, R), the resulting bound can become too loose, as one can deduce S by comparing training set predictions with the labels Y. Corollary 2. When m L. the bound of (18) becomes
Remark 1.
E2 E2 [U,, R)- Comp (1, 2s, R3]|
S
Σ 1
E B 2I(((Es, S.)
(21)
A great advantage of this bound compared to all other bounds described so far is that the mutual information term is computed between a relatively low-dimensional random variable f(ās,, T,, R) and binary random variable S,. For example, in the case of binary classification with K. {0, 1}. fās, E,, R) will be a pair of 2 binary variables. This allows us to estimate the bound efficiently and accurately (please refer Appendix B for more details). Note that estimating other information- theoretic bounds is significantly harder. The bounds of Xu and Raginsky [39]. Negrea et al. [22], and Bu et al. [6] are hard to estimate as they involve estimation of mutual information between high-dimensional non-discrete variable W and at least one example Z;. Furthermore, this mutual information can be infinite in case of deterministic algorithms when H HZ,)) is infinite. The bounds of Haghifam et al. [14] and Steinke and Zakynthinou [33] are also hard to estimate as they involve estimation of mutual information between W and least one train-test split variable S..
As in the case of bounds presented in the previous section (Thm. 2.2 and Thm. 2.6), we prove that the bound of Thm. 3.1 is non non-decreasing in m. This stays true when increase the upper bounds by moving the expectation over U or the expectation over Z or both under the square root. The following proposition allows us to prove all these statements.
Proposition 3. Let E [n- - -1,, U be a random subset of (n) of size m, U' be random subset of size m + be any fixed value of Z, and Φb I2 + lR be any non-decreasing concave function. Then
1 m
Ey-t &
[([(2s, N.. R); R); S Earrer Φ m +1
[(J(Es, Tws R); Sw:)
(22)

---

By setting o(z) = vI and then taking expectation over è and u, we prove that bounds of Thm. 3.1 are non-decreasing over m. By setting ((x) z, taking expectation over ž, and then taking square root of both sides of (22), we prove that bounds are non-decreasing in when both expectations are under the square root. Proposition proves that m 1 is the optimal choice in Thm. 3.1. Notably, the bound that is the easiest to compute is also the tightest!
Analogously to Thm. A.I, we provide the following stability-based bounds. Theorem 3.2. If ((7. v) E [o, 1), Vy E K., = E 2, then
E R. Zff,Zs, R) Lempl (f. Zs. R?)
- B B
/21(f(2s; R,, R); s
(23)
and
8 R
2, (clf, Zs. R) Lemp (f, Zs. R)
E 2
Σ
(,; (_,) +
n
Note that unlike (23), in the second part of Thm. 3.2 we measure information with predictions on all 2n pairs and S; conditioned on S_,. is an open question whether f(žs, ã, R) can be replaced with f(zs, R;, R) predictions only on the i-th pair.
4
Applications
In this section we describe 3 applications of the f-CMI-based generalization bounds.
4.1 Ensembling algorithms
Ensembling algorithms combine predictions of multiple learning algorithms to obtain better per- formance. Let us consider & learning algorithms, Sí, f2..,,, Sk. each with its own independent randomness R4, i E [b:]. Some ensembling algorithms can be viewed as possibly stochastic function g .c + K. that takes predictions of the k algorithms and combines them into a single prediction. Relating the generalization gap of the resulting ensembling algorithm to that of individual fis can be challenging for complicated choices of g. However, it is easy to bound the generalization gap of g(f1..... fx) in terms of f-CMIs of individual predictors. Let be a fixed value of Z and be an arbitrary collection of inputs. Denoting F; = fi x, R.), E [K]. we have that
(f 5) < [(Fi,...,FF:: S)
(data processing inequality) , S) I(Fi; P2....... FR) I(Fi; F2,... ..... P& ()) (chain rule) (as MI is nonnegative and F1 IL F2,..., F& 1) (repeating the arguments above to separate all F.)
=I(Fi;S)+ [[22, F.;,..,,,......
< ((F;;)) + T F S)
S... ((F;;S(FFF;S)))) + + T(Fs;
Unfortunately, the same derivation above does not work if replace S with S,, where is proper subset of [n]. as 1(F1; F3 Sw) will not be zero in general.
4.2 Binary classification with finite VC dimension
Let us consider the case of binary classification: y {0, 1). where the learning method f
z" X' R + {0, 1} is implemented using learning algorithm A : - x R- W that selects classifier from hypothesis set H. = {hw X + )}. If 76 has finite VC dimension d [34], then for any algorithm f. the quantity f-CMI(f, 2) can be bounded the following way.
Theorem 4.1. Let Z, H. f be defined as above, and let d < oo be the VC dimension of H. Then for any algorithm and znx2
f-CMT(f, max {(d + log 2, dlog (eendd)]
(24)
Considering the 0-1 loss function and using this result in Corollary 1, get an expect generalization gap bound that is O (V* log (*) matching the classical uniform convergence bound [34]. The
/ Vl factor can be removed in some cases [13].
7

---

Both Xu and Raginsky [39] and Steinke and Zakynthinou [33] prove similar information theoretic bounds in the case of finite VC dimension classes, but their results holds for spe- cific algorithms only. Even in the simple case of threshold functions: X' [0, 1] and H = {hw I + [a>w) w E [0, 1]}. all weight-based bounds described in Sec. 2 are vacuous if one uses training algorithm that encodes the training in insignificant bits of W, while still getting zero error on the training set and hence achieving low test error.
4.3 Stable deterministic or stochastic algorithms
Theorems 2.3, A.1 and 3.2 provide generalization bounds involving cottrmmationtthhorette stability measures, such as [(W; Z; Z_1). I (A(šs, Rt); S S_x) and I (f ã. R); S; S_;). In this section we build upon the predication- stability bounds of Thm. 3.2. First, we show that for any collection of examples x, the mutual information [[f(ās, x);;; S_;)) can be bounded as follows.
Proposition 4. Let Sit denote S with S; set Then for any E g and I E X* the mutual information [[[ x, RI;; St S-i) is upper bounded by
KL (f(Eg--1, R)JS- fāg. I, R)JS-)) 1 KL RYJS, f(ăg R))S-:).
To compute the right-hand side of Proposition 4 one needs to know how much on-average the distribution of predictions on changes after replacing the i-th example in the training dataset. The problem arises when we consider deterministic algorithms. In such cases, the right-hand side is infinite, while the left-hand side [(f(ās, x. R); S; S_;) is always finite and could be small. Therefore, for deterministic algorithms, directly applying the result of Proposition 4 will not give meaningful generalization bounds. Nevertheless, we show that we can add optimal amount of noise to predictions, upper bound the generalization gap of the resulting noisy algorithm, and relate that to the generalization gap of the original deterministic algorithm.
Let us consider a deterministic algorithm f 2 x X + Rd. We define the following notions of functional stability.
Definition 4.1 (Functional stability). Let S = (Z....., 2n) ~ Dn be a collection of n i..dd samples, and Z' and Zue be two additional independent samples from D. Let sti) & (Z...... 2,,,,,,,, L', "Z,1....... Zn) be the collection constructed from S by replacing the i-th example + Rd is
with Z'. A deterministic algorithm f 2" X
a) 8 self-stable if Vi E [n], Es.z ((S),2)) Zi) - -(S()) 2.) SB?,
(25)
b) 31 test-stable if Vi E [n], Es,z [(SS Zmer) - [(S(1), Zrese) ||= S 87
(26)
c) 32 train-stable if Vi,j E [n], + j, Es.z (1) f( 2z) S $2.
(27)
Theorem 4.2. Let y = Rd, f: 2n x X - Rd be a deterministic algorithm that is 3 self-stable, and ((T. v) E [0 be loss function that is 7- Lipschitz in the first coordinate. Then
E2.n. [(f. Zs, R) Lemp (f, 2s. R)]
s 2 V7B.
(28)
Furthermore, if f is also Bi train-stable and (32 test-stable, then
Bz,n, Zs. R) - Cemp (f. 2s. R))
s + 123 Vol 2,2 + n + n.3..
32
(29)
It is expected that Bg is smaller than 3 and B. For example, in the case of neural networks interpolating the training data or in the case of empirical risk minimization in the realizable setting, 32 will be zero. It is also expected that , is larger than 31. However, the relation of 3 and n.3 is not trivial.
The notion of pointwise hypothesis stability By defined by Bousquet and Elisseeff [5] (definition
4) is comparable to our notion of self-stability 3. The first part of Theorem 11 in [5] describes generalization bound where the difference between empirical and population losses is of order
8

---

0.25
FCMI boure
boond
LCH toard
0.4
0.10
0.15
0.2
0.05
0.05
0.0
250
1000
4000
1000
5000
20000
10
20
30
40
Epocits
(b)
(c)
Figure 1: Comparison of expected generalization gap and f-CMI bound in 3 settings: (a) MNIST 4 9 classification with a CNN trained using a deterministic algorithm, (b) pretrained ResNet-50 finetuned on CIFAR-10, and (c) MNIST 4 vs 9 with CNN trained using SGLD.
0.10
0.08
Error
Negreset bound
FCMI (CMileeee
0.06
LCN bound
0.02
2.5
10.0 Spochs
12.5
2.5
5.0
10.0
12.5
35.0
Epochs
Comparison of expected generalization gap, Negrea et al. [22] SGLD bound and f-CMI bound in case of a pretrained ResNet-50 fine-tuned with SGLD on subset of CIFAR-I0 of size 20000. The figure on the right is the zoomed-in version of the figure on the left.
Figure 2:
1/v7 + VBz. which is comparable with result of Thm. 4.2 (0(V3).. The proof there also contains a bound on the expected squared difference empirical and population losses. That bound of order 1/n + 8% In contrast, our result of (29) contains two extra terms related test-stability and train-stability (the terms n²3 and n,82). If 8 dominates n + n22, then the bound of (29) will match the result of Bousquet and Elisseeff [5].
5 Experiments
As mentioned earlier, the expected generalization gap bound of Corollary 2 is significantly easier to compute compared to existing information-theorett bounds, and does not give trivial results for deterministic algorithms. To understand how well the bound does in challenging situations, consider cases when the algorithm generalizes well despite the high complexity the hypothesis class and relatively small number of training examples. Due to space constraints omit some experimental details and present them Appendix B. The code can be found at g github. cow/com////o///e http:/haarharrrree CMI.
First, we consider the MNIST 4 vs digit classification task [20] using 4-layer convolutional neural network (CNN) that has approximately 200K parameters. We train the network using for 200 epochs using the ADAM algorithm [18] with 0.001 learning rate, 31 = 0.9, and mini-batches of 128 examples. Importantly, we fix the random seed that controls the initialization of weights and the shuffling of training data, making the training algorithm deterministic. Fig. Ia plots the expected generalization gap and the f-CMI bound (21). We see that the bound is not vacuous and is not too far from the expected generalization gap when considering only 75 training examples. As shown in the Fig. 3a of Appendix B, if we increase the width of all layers 4 times, making the number of parameters approximately 3M, the results remain largely unchanged.
Next, we move away from binary classification and consider the CIFAR-10 10 classication task [19]. To construct well- gell-generalizing algorithm, we use the ResNet-50 [16] network pretrained on the ImageNet [7], and fine-tune it for 40 epochs using SGD with mini-batches size 64, 0.01 learning rate, 0.9 momentum, and standard data augmentations. The results presented in Fig. 1b indicate that the /-CMI bound always approximately 3 times larger than the expected generalization gap. In particular, when 20000, the expected generalization gap is 5%, while the bound predicts 16%.

---

Note that the weight-based information -heooretic bounds discussed in Sec. 2 would give either infinite or trivial bounds for the deterministic algorithm described above. Even when we make the training algorithm stochastic by randomizing the seed, the quantities like T(W; S) still remain infinite, while both the generalization gap and the f-CMI bound do not change significantly (see Fig. 3b of Appendix B). For this reason, we change the training algorithm to Stochastic Gradient Langevin Dynamics (SGLD) [10, 38] and compare the f-CMI-based bound against the specialized bound of Negrea et al. [22] (see eq. (6) of [22]). This bound (referred as SGLD bound here) is derived from weight-based information-theoreti generalization bound, and depends on the the hyper-parametent of SGLD and on the variance of per-example gradients along the training trajectory. The SGLD algorithm is trained for 40 epochs, with learning rate and inverse temperature schedules described in Appendix B. Fig. 1c plots the expected generalization gap, the expected test error, the f-CMI bound and the SGLDD bound. We see that the test accuracy plateaus after 16 epochs. At this time and afterwards, the f-CMI bound closely follows the generalization gap, while the SGL.D bound increases to very high values. However, we see that the SGLD bound does better up to epoch 12.
The difference between the f-CMI bound and the SGLD bound becomes more striking when we change the dataset to be a subset of CIFAR-10 consisting of 20000 examples, and fine-tune a pretrained ResNet-50 with SGLD. As shown in Fig, 2, even after single epoch the SGLD bound is approximately 0.45, while the generalization gap is around 0.02. For comparison, the f-CMI is approximately 0.1 after one epoch of training.
Interestingly, Fig. Ic shows that the f-CMI bound is large in the early epochs, despite of the extremely small generalization gap. In fact, similar trend, albeit with lesser extent, is visible in the MNIST 4 vs 9 experiment, where CNN is trained with deterministic algorithm (see Fig. 3c of Appendix B). This indicates a possible area of improvement for the f-CMI bound.
6 Related Work
This work is closely related to rich literature of information-thhooee
generalization bounds, some of which were discussed earlier [39, 4, 25, 22, 6, 33, 14, 13, 1, 23, 27, 8]. Most of these work derive generalization bounds that depend on mutual information quantity measured between the output of the training algorithm and some quantity related training data. Different from this major idea, Xu and Raginsky [39] and Russo and Zou [29] discussed the idea of bounding generalization gap with the information between the input and the vector of loss functions computed on training examples. This idea was later extended to the setting of conditional mutual information by Steinke and Zakynthinou [33]. This works are similar to ours in the sense that they move away from measuring information with weights. but they did not develop this line of reasoning enough to arrive to efficient bounds similar to Corollary 2. Additionally, we believe that measuring information with the prediction function allows better interpretation and is casier to work with analytically.
Another related line of research are the stability-based bounds [5. 2, 26, 3, 9, 37, 27]. In Sec. and Sec. 3 we improve existing generalization bounds that use information stability. In Sec. 4.3 we describe a technique of applying information stability bounds to deterministic algorithms. The main idea is to add noise to predictions, but only for analysis purposes. A similar idea, but in the context of measuring information content of an individual example, was suggested by Harutyunyan et al. [15]. In fact, our notion of test-stability defined in See. 4.3 comes very close to their definition of functional sample information. A similar idea was recently used by Neu et al. [23] in analyzing generalization performance of SGD. More broadly this work is related to PAC-Bayes bounds and to classical generalization bounds. Please refer to the the survey by Jiang* et al. [17] for more information on these bounds.
Finally, our work has connections with attribute and membership inference attacks [32, 40, 21, 12]. Some of these works show that having white- box access to models allows constructing better membership inference attacks, compared to having a black-box access. This is analogous to our observation that prediction- based bounds are better than weight-based bounds. Shokri et al. [32] and Yeom et al. [40] demonstrate that even in the case of black-box access to a well-generalizing model, sometimes it is still possible to construct successful membership attacks. This is in line with our observation that the J-CMI bound can significantly large, despite of small generalization gap (see epoch 4 of Fig. Ic). This suggests possible direction of improving the f-CMI-based bounds.
10

---

Acknowledgments and Disclosure of Funding
This work is based on research sponsored by Air Force Research Laboratory (AFRL) under agreement number 118750-19-1-1000 The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation therein. The views and conclusions contained herein are those of the authors and should not be interpreted necessarily representing the official policies or endorsements, either expressed or implied, of Air Force Laboratory. DARPA or the U.S. Government. HH partially supported by USC Annenberg Fellowship.
References
[1] I. Alabdulmohsin. Towards a unified theory of learning and information. Entropy. 22(4):438. 2020.
[2] M. Alabdulmohsin. Algorithmic stability and uniform generalization. Advances Neural Information Processing Systems, 28:19-27, 2015.
[3] R. Bassily, K. Nissim, A. Smith, T. Steinke, U. Stemmer, and J. Ullman, Algorithmic stability for adaptive data analysis. In Proceedings of the firth-eighth annual ACM symposium Theory of Computing, pages 1046-1059, 2016.
[4] R. Bassily, S. Moran, I. Nachum, J. Shafer, and A. Ychudayoff. Learners that use little information. In Algorithmic Learning Theory, pages 25-55. PMLR, 2018.
[5] O. Bousquet and A. Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[6] Y. Bu, S. Zou, and V. V. Veeravalli. Tightening mutual information bounds on generaliza- tion error. IEEE Journal on Selected Areas in Information Theory, 1(1):121-130, 2020.
[7] Deng, W. Dong, Socher, L.-J. Li, K. Li, and L. Fei-Fei. Imagenet: large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248 148-255. leee, 2009.
[8] A. R. Esposito, M. Gastpar, and I. Issa. Generalization error bounds via rényi-, f-divergences and maximal leakage. IEEE Transactions on Information Theory, 2021.
[9] V. Feldman and T. Steinke. Calibrating noise to variance in adaptive data analysis. In Conference On Learning Theory, pages 535-544, 2018
[10] S. B. Gelfand and S. K. Mitter. Recursive stochastic algorithms for global optimization in r'd. SIAM Journal on Control and Optimization, 2995);99--1118, 1991.
[11] R. M. Gray. Entropy and information theory. Springer Science & Business Media, 2011.
[12] U. Gupta, D. Stripelis, P. K. Lam, P. Thompson, J. L. Ambite, and G. V. Steeg. Membership inference attacks deep regression models for neuroimaging. In Medical Imaging with Deep Learning, 2021.
[13] H. Kolez-Kolahi, Z. Golgooni, S. Kasaei, and M. Soleymani. Conditioning and processing: Techniques to improve information-theeretic generalization bounds. Advances in Neural Information Processing Systems, 33, 2020.
[14] 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 H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9925 9935.. Curran Associates, Inc., 2020.
[15] H. Harutyunyan, A. Achille, G. Paolini, O. Majumder, A. Ravichandran, R. Bhotika, and Soatto. Estimating informativeness of samples with smooth unique information. In Interna- tional Conference on Learning Representations, 2021.

---

[16] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[17] Y. Jiang*, B. Neyshabur*, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures and where to find them. In International Conference on Learning Representations. 2020. URL http:::///peervviiii
met//forum'iddsJJIIPJB
[18] D. P. Kingma and Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[19] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[20] Y. LeCun, C. Cortes, and C. Burges. Mnist handwritten digit database. ATT Labs [Online]. 2, 2010.
Available: http://yann.eecue
[21] M. Nasr, R. Shokri, and A. Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE symposium on security and privacy (SP), pages 739-753. IEEE, 2019.
[22] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy. coormatiiontheoreiiee generalization bounds for sgld via data-dependent estimates. In Advances in Neural Information Processing Systems, pages 1015-11025, 2019.
[23] G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy. croomatioo-tthooetiie generalization bounds for stochastic gradient descent. In M. Belkin and S. Kpotufe, editors, Proceedings of Thirty Fourth Conference Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3526-3545. PMLR, 15-19 Aug 2021.
[24] L. Paninski. Estimation of entropy and mutual information. Neural computation, 15(6): 1191-1253, 2003.
[25] A. Pensia, V. Jog, and P.-L. Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550. IEEE, 2018.
[26] M. Raginsky, A. Rakhlin, M. Tsao, Wu, and Xu. Informmaion-thheortiicc analysis of stability and bias of learning algorithms. In 2016 IEEE Information Theory Workshop (ITW), pages 26-30. IEEE, 2016.
[27] M. Raginsky, A. Rakhlin, and A. Xu. Information-theoree stability and generalization. Information-Theoree Methods in Data Science, page 302, 2021.
(28) B. Gádiee, G. Bassi, R. Thobaben, and M. Skoglund. On random subset general- ization error bounds and the stochastic gradient langevin dynamics algorithm. In 2020 IEEE Information Theory Workshop (ITW), pages 1-5. IEEE, 2021.
[29] D. Russo and Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory,
2019.
[30] N. Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1): 145-147, 1972.
[31] S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematies, 41(1):247-261, 1972.
[32] R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), pages 3-18. IEEE, 2017.
[33] T. Steinke and Zakynthinou. Reasoning About Generalization via Conditional Mutual Information. In J. Abernethy and S. Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3437- 3452. PMLR, 09-12 Jul 2020.
12

---

[34] V. Vapnik. Statistical learning theory new york. NY: Wiley, 1998.
[35] S. Verdu and T. Weissman. The information lost in erasures. IEEE Transactions on Information Theory, 54(11):5030-5058 2008.
[36] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[37] Y.-X. Wang, J. Lei, and S. E. Fienberg. On-average kl-privacy and its equivalence gener- alization for max-entropy mechanisms. In International Conference on Privacy in Statistical Databases, pages 121-134. Springer, 2016.
[38] M. Welling and Y. W. Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11), pages 681-688 Citeseer, 2011.
[39] A. Xu and M. Raginsky. information-theoreet analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, pages
2017.
[40] S. Yeom, I. Giacomelli, M. Fredrikson, and S. Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. 2018 IEEE 31st Computer Security Foundations Symposium (CSF), pages 268-282. IEEE, 2018.
[41] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint
2016.
13


Reviews:
[{"review_id": "fKs2x9hz1f", "reviewer": "Reviewer_RQQn", "summary": "The paper derives information-theoretic bounds for learning algorithms. The bounds are based on the predictions of the learned model, rather than the weights (output), which makes them tighter by the data-processing inequality and can yield non-vacuous bounds in cases where weight-based mutual information bounds are vacuous. The authors validate the analysis with a few experiments. ", "questions": "", "limitations": "", "rating": 7, "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": "The paper derives information-theoretic bounds for learning algorithms. The bounds are based on the predictions of the learned model, rather than the weights (output), which makes them tighter by the data-processing inequality and can yield non-vacuous bounds in cases where weight-based mutual information bounds are vacuous.  The new bounds build upon the earlier works of Xu & Raginsky (2017) and the more recent work of Steinke & Zakynthinou (2020) using the notion of the conditional mutual information (CMI). \n\nFirst, the authors present a theorem that generalizes a bound of  Xu & Raginsky (2017) (Theorem 2.2 in the paper) in which the mutual information is measured between the weights W and the full dataset S. Theorem 2.2 uses a subset of S. However, I don't see how this theorem is different from Theorem 2.1 since taking a proper subset of a training set (i.e. for any fixed choice of u in the theorem), the distribution of S_u is the same as the distribution of a training sample of size m drawn iid. Would you please clarify why Eq 5 is not equivalent to Eq 4?\n\nThe authors then discuss the choice of the subset size m. They argue that having a smaller m yields a tighter bound. However, there is an early work that makes the same argument and is not discussed in the paper. In Alabdulmohsin (2015),  m=1 is used to derive non-vacuous bounds and it is shown that those bounds were tight (see for instance [1] and the subsequent works summarized in [2]). Note that the difference between using the weights and using the function itself (decision boundary) was discussed there as well using data-processing. Since this is an earlier work that makes the same argument, it should be discussed. \n\nThe main contribution of this work is Theorem 3.1, in which the authors introduce the notion of functional CMI. It is analogous to the notion of CMI introduced by Steinke & Zakynthinou (2020) but uses the predictions rather than the weights (output). One interesting difference is on the connections between mutual information and the VC dimension. Earlier works (e.g. Alabdulmohsin (2018) and Steinke & Zakynthinou (2020)) prove that an ERM *exists* in a VC class that has a small mutual information between the weights and the data. Using functional CMI, the authors show that all functions in a VC class have a finite f-CMI, which is a neat result. The difference here is that by looking at the predictions, they rule out cases in which the data is encoded in the weights without impacting the decision boundary significantly. \n\nThe authors then discuss some implications. For example, they look into the case of ensemble learning and show that the f-CMI of an ensemble can be bounded using the f-CMI of the base models. However, this argument is not really useful because it does not explain why an ensemble method tends to generalize better. The bound for the ensemble is larger than the bound of any base classifier. \n\nFinally, the authors validate the analysis with a few experiments. The authors argue that the f-CMI bound \"closely tracks\" the generalization gap but this is misleading because the difference is one order of magnitude and the fact it is decreasing with increasing sample size does not make it \"tracking\" the generalization gap. After all, all useful generalization bounds decrease with increasing sample size. I suggest that the authors rephrase that claim (perhaps by only arguing that the bound is non-vacuous). Also, in Line 319, the statement is false because weight-based mutual information bounds need not be vacuous (e.g. when m=1 as discussed earlier). Yes, they can be vacuous but need not be. \n\nOne minor comment. In Lines 128 and 129, I think there is a typo. Shouldn't \"n\" be \"2n\"? \n\nOverall, the paper is well-written and brings together several recent works. The only comment I have is that there is a related line of work missing in the discussion. As mentioned above, Alabdulmohsin (2015) was an early work that proposed measuring the mutual information with a subset of size m=1 and showed that it was tight (in a certain sense). Based on that, a bound similar to Theorem 2.1 was derived for bounded losses and an equivalence relation was established with the VC dimension, which is similar to the works discussed in Section 4.2, in addition to concentration bounds. These are summarized in [2]. They should be included in the related works for completeness.\n\n[1] Alabdulmohsin, \"Algorithmic stability and uniform generalization.\" NeurIPS (2015).\n\n[2] Alabdulmohsin, \"Towards a Unified Theory of Learning and Information.\" Entropy 22.4 (2020): 438.\n\n======== \n\nPost-rebuttal:\n\nI have read the authors' response and I intend to keep my score as is. I find this paper a worthwhile contribution overall.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "MWR-1Ww1C-", "reviewer": "Reviewer_3S6u", "summary": "The paper continues a line of work which develops information-theoretic bounds on the generalization gap (i.e. the difference between e,pirical and population loss) in supervised learning.\nIts main contributions are:\n1. the authors introduce a natural “transductive” variant of the conditional mutual information bound (Section 3) and show that it is stronger than all previous bound. (Eg one can use it to prove that any proper learner for a VC class generalizes).\n2. The authors quantitatively improve some of the previous bounds on input-output mutual information (theorem 2.2, 2.3), and on conditional mutual information (Theorem 2.6), by moving the expectation outside the square-root in the RHS of the inequality.\n", "questions": "", "limitations": "", "rating": 7, "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": "Overall I liked this paper: I think it the transductive variant of the recently-well-studied conditional mutual information is natural, simple, and they show that this variant is in fact stronger. \nMoreover, they also derive quantitative improvements over the previous bounds. \n\nSome specific comments and questions to the authors:\n1. I was not very convinced by the motivation using deep learning. The main reason is because the bounds studied in this paper imply that the empirical and population losses are close, and perhaps the greatest mystery DNN demonstrate is that they generalize, however they do not necessarily satisfy this property.\n2. I would appreciate if the authors can elaborate more on their quantitative improvement over previous bound (by moving the expectation outside the square-root). Are there concrete, natural examples where it gives better bounds? How complicated is this improvement comparing to the previous (weaker) derivations?\n3. In Theorem 4.1, please add that the learning algorithm is proper. Otherwise the statements seems false.\n4. Can you please elaborate on the application wrt to ensemble methods? In which ways is it better than previous bounds?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potential negative social impact.", "review_text": "", "extra_scores": {"ethical_concerns": "As far as I can see, there are none.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "JuOaUf7N84Y", "reviewer": "Reviewer_AGS2", "summary": "The authors build upon recent literature on information theoretic bounds on generalization error and specifically the conditional mutual information bound by Steinke and Zakynthinou [28]. They propose an improved bound that is tigther than [28] and easier to compute in practice. It is achieved by replacing the weight-parameter vector in the mutual information expression of [28] with a prediction function evaluated on a subset of in-sample (training) data and a subset of out-of-sample data.  This enables the authors to give performance guarantees on deterministic training algorithms. Several toy examples and experimental results are presented to illustrate the advantages of the improved generalization bound.", "questions": "", "limitations": "", "rating": 6, "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 proposed bound involving mutual information between the sample index variables and prediction function involving the first n samples is interesting and has practical advantages. However the proof seems to follow prior works and builds upon Lemma 1. Can the authors explain what aspects are non-trivial in the derivation of the new bound? \n\nCan the authors comment on how the result in Thm. 4.2 compares with other generalization results on deterministic algorithms n the literature? \n\nIn the experimental section I was wondering why the authors did not compare their bound with bounds other than Negrea et al.? There are other state of the art bounds (such as the work of Haghifam et al) that are better than Negrea et al. for SGLD.  Are there difficulties in comparing with these works?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not listed societal impact. Limitations have been discussed. ", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hrs"}, "extra_text": {}}, {"review_id": "4uCR-0bOmz3", "reviewer": "Reviewer_LtsL", "summary": "This paper studies information-based generalization bounds and derive several improved versions of existing generalization bounds using mutual information. The paper suggests a function-based conditional mutual information in order to tighten the existing generalization bounds and discusses some numerical results to support the shown generalization bounds.", "questions": "", "limitations": "", "rating": 5, "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": "This work uses an information-theoretic approach to analyze the generalization properties of neural network classifiers. The work uses the mutual information between observed data and model parameters to bound the generalization error and then proves several variants of the existing information-based bounds through the application of conditional mutual information and function-based mutual information measures that focus on the classifier's output instead of the input samples. \n\nIn general, the paper tries to address an important problem in learning theory on the generalization properties of overparameterized deep neural networks. The paper's analysis seems to improve the existing mutual information-based generalization bounds. However, I am not completely sure how to estimate the bounds from real data because the paper has no guarantees that the estimation error for the information measures is bounded. In addition, the paper contains many theoretical statements, which makes it hard for a reader to focus on and understand the paper's main contribution.\n\nTo further explain the comments above, my main concern with this work is how to evaluate the generalization bounds for standard datasets and deep neural network classifiers. The generalization bounds include conditional mutual information terms which are hard to evaluate from real data in practical settings. Also, the upper bound in Corollary 2 includes n mutual information terms where for every term we have only one observed sample. Therefore, it is not clear how one should estimate every mutual information term from only one sample.\n\nIn addition to the estimation of information measures, the current paper includes too many theoretical statements that makes it hard to distinguish the paper's main contribution from the existing results in the literature. I highly suggest removing the less important results from the main text and further explaining how the generalization bounds in this work can be more useful than existing information-based generalization bounds. The current draft seems to only suggest that the new bounds rely on conditional information measures, while this new feature may not be that useful in practice because the conditional information measures are statistically unaffordable to estimate.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please refer to my comments in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "-j8GGRd5d5Q", "reviewer": "Reviewer_FhFb", "summary": "This paper proposes new information-theoretic generalization bounds. These bounds extend some existing results and seem easier to compute. The authors also demonstrate their bounds through some applications and experiments.", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\nUsing the information-theoretic framework, introduced by Xu and Raginsky, for studying the generalization error is interesting.\n\nThe new generalization bounds in Section 3 seem easier to compute compared with existing mutual-information-based generalization bounds. \n\nThe experimental results seem to suggest that the new bounds in this paper are promising. \n\nWeaknesses:\n\nMy main concern of this paper is its novelty and unclear comparison with existing literature. \n\n1. The comparison with existing literature is unclear. For example, in the abstract, the authors claimed that their bounds improve over the existing information-theoretic bounds since (a) they give meaningful results for deterministic algorithms and (b) they are significantly easier to estimate. In the second paragraph of the paper, the authors echoed their claim and provided some references. However, it seems that many existing papers have already contributed to the above two challenges. In fact, the generalization bounds in [4,28] are applicable to deterministic algorithms, and the bounds in [11,19,20] seem easy to compute as well. There are some missing references that also contribute to these two directions. Hence, I recommend the author revise their introduction and clarify their contributions.\n\n2. The authors provided a generalization bound in Theorem 2.2 and stated that this bound matches the result of Bu et al. [4] when m=1. Then authors proved that this bound is non-decreasing in m. Hence, if I understand correctly, Bu et al. have already derived the tightest case. Then what is the purpose of introducing other weaker bounds? In the same vein, bounds with similar forms have already appeared before. For example, Raginsky has presented a similar result in a tutorial at NASIT 2019 (see the recorded video at https://www.itsoc.org/conferences/schools/nasit2019 1:25:05). Negrea et al introduced a similar bound. Although their bound is slightly weaker than Thm 2.2. in this paper, it does not seem that the improvement is significant. \n\nSimilar comments also apply to some bounds in Section 2.2.\n\n3. Section 3. The authors considered a different framework where they assumed that the learning method implements a function f: Z^n \\times X \\times R \\to K. This framework has been considered in the following missing reference for studying excess risk. Hence, it seems that the authors just applied the existing bounds introduced in [28] to this new framework.\n\nXu, A. and Raginsky, M., 2020. Minimum excess risk in Bayesian learning. arXiv preprint arXiv:2012.14868.\n\nMy second concern is the experiments in this paper. \n1. The authors compared their bound with the one in Negrea et al [19] in Fig 1 (b). For the first 12 epochs, the bound in Negrea et al [19] outperforms the bound in this paper. Given that the SGLD algorithm converges in 16 epochs, it seems that the new bound introduced in this paper is often weaker than the bound in Negrea et al [19] before the algorithm converges. \n\n2. The bound in Negrea et al [19] blows up after the algorithm convergences and that’s the region where the bound in this paper is sharper. However, a follow-up work [11] has already proposed a new generalization bound which seems to address this issue and becomes much tighter. This bound is extended to the setting of SGLD in the following missing reference. Hence, I wonder how the generalization bound in this paper compares with these new bounds. \n\nRodríguez-Gálvez, B., Bassi, G., Thobaben, R. and Skoglund, M., 2021, April. On random subset generalization error bounds and the stochastic gradient Langevin dynamics algorithm. In 2020 IEEE Information Theory Workshop (ITW) (pp. 1-5). IEEE.\n\n3. The generalization bound in this paper is decreasing w.r.t. the number of epochs in Fig. 1. However, it seems that the true generalization gap is increasing which is captured by the bound in Negrea et al [19]. How can you interpret this phenomenon?\n\nOther comments\n\nThe generalization bounds in Eq.(29). It is unclear to me why the second term has a $n$ inside the square root. How to explain this dependence? Does that suggest that the generalization gap is increasing w.r.t. the sample size. Also, how does this bound compare with other existing stability bounds?\n\nThe authors provided some high-probability bounds (e.g., Eq. 3 and Line 88) in the paper. I wonder how they compare with the one in [34]. It seems that using the “monitor technique” can lead to a tighter bound compared with the bound obtained from Markov’s inequality. Also, how do these high-probability bounds compare with the ones in the following reference?\nEsposito, A.R., Gastpar, M. and Issa, I., 2021. Generalization error bounds via Rényi-, f-Divergences and Maximal Leakage. IEEE Transactions on Information Theory.\n\nLine 112—113. The authors wrote “While these bounds are worse than the corresponding bounds of Thm. 2.2, it is sometimes easier to manipulate them analytically.” This is unclear to me. Can the authors elaborate more?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See my above comments.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper continues a line of work which develops information-theoretic bounds on the generalization gap (i.e. the difference between e,pirical and population loss) in supervised learning. Almost all reviewers were favorable for acceptance, and found the results innovative.


Please address reviewers comments in the final version.
Decision: Accept (Poster)