On Leave-One-Out Conditional Mutual Information For Generalization
Authors: Mohamad Rida Rammal
Alessandro Achille
Aditya Golatkar
Suhas Diggavi
Stefano Soatto
Venue: NeurIPS 2022 Accept (2022)

Abstract: We derive information theoretic generalization bounds for supervised learning algorithms based on a new measure of leave-one-out conditional mutual information (loo-CMI). In contrast to other CMI bounds, which may be hard to evaluate in practice, our loo-CMI bounds are easier to compute and can be interpreted in connection to other notions such as classical leave-one-out cross-validation, stability of the optimization algorithm, and the geometry of the loss-landscape. It applies both to the output of training algorithms as well as their predictions.  We empirically validate the quality of the bound by evaluating its predicted generalization gap in scenarios for deep learning. In particular, our bounds are non-vacuous on image-classification tasks. 

On Leave-One-Out Conditional Mutual Information For Generalization
Mohamad Rida Rammal University of California, Los Angeles ridarammalge ucla. edu
Alessandro Achille Caltech, AWS Al Labs eachille@caltech edu
Aditya Golatkar
Suhas Diggavi University of California, Los Angeles suhasßee .uw...cllleee
University of California, Los Angeles aditya290cs. www.al990ssuccll......e wuw.l.claeee
Stefano Soatto
University of California, Los Angeles soatto@ucla. edu
Abstract
We derive information theoretic generalization bounds for supervised learning gorithms based on new measure of leave-one-out conditional mutual information (loo-CMI). In contrast to other CMI bounds, which may hard to evaluate in practice, our loo-CMI bounds are easier to compute and can be interpreted in con- nection to other notions such as classical leave-one-out cross-validation, stability of the optimization algorithm, and the geometry of the loss-landscape. It applies both to the output training algorithms as well as their predictions. We empiri- cally validate the quality of the bound by evaluating its predicted generalization gap in scenarios for deep learning. particular, our bounds are non-vacuous on ilase-clasiiiicttoo tasks.
Introduction
Generalization in classical machine learning models often understood terms of the bias-variance trade-off: wer-parameterized models fit the data better but are more likely to overfit. However, the push for ever larger deep network models, driven by their remarkable empirical generalization, has spurred race for the development of new theories of generalization with two main objectives: (1) guiding the practitioners in designing over-pan per-pparaeterized architectures and training schemes that would generalize better and (2) providing provable bounds on the performance of the model after deployment.
In this context, information theoretic bounds on generalization [27, 31, 5, 21, 29, 12, 16] are particu- larly appealing. They capture the intuitive idea that models that memorize less about the training set will generalize better. In particular, since they deal with the amount of information stored in the weights rather than the number of weights, they are especially adaptable to over permparrmeteriz models [17, 2. 1]. However, the bounds are often vacuous in realistic settings. require modified training algorithms, or are difficult compute and/or to relate to relevant properties of the net- work/training al algorithm. To remedy this problem, we ask whether it is possible to develop bound (b) interpretable, meaning that they can be rewritten in terms of quantities the practitioners can control during the
that (a) realistically tight for standard training algorithms used in deep learning;
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

training process and that may guide toward the design of better training algorithms, (c) that applies out-of-the-box to standard training algorithms.
Contributions. As a step in this direction, we introduce new information theoretic bound based on leave-one-out conditional mutual information (loo-CMI)'. The main intuition behind the bound to ask the counterfactual question "If we were remove set and retrain, how well would we be able to infer which sample was removed?". As we shall see, bounding this quantity is enough to bound sharply the amount of memorization in a deep network, and hence its generalization (Theorems 3.1 and 3.2). At the same time, the bound is easy to interpret and connects several empirical quantities and other generalization theories, such as: (1) stability of the optimization algorithm (Section 4.4), (2) flatness of the loss landscape at convergence (Section 4.5). Moreover, we show that bound can also be interpreted in the function space (that is, looking the activations rather than the weights, (Theorem 3.2) leading to tighter bounds for over-parameterized models through the data processing inequality.
sample at random from the training
Our loo-CMI bound falls in the general class of conditional mutual information bounds, introduced by [29]. However, while standard CMI bounds iterate over all the subset of samples of size N (2 subsets for dataset of 2NV samples) in order to compute the bound, our loo-CMI bounds only need to iterate over N possible samples remove, leading to exponential reduction in the cost to estimate the bound. Moreover, our strategy of removing a single sample is easy to relate to the stability of the training path to slight perturbation of the training set, thus giving clear connection between generalization and the geometry of the loss landscape (Figure 1). Empirically, we show that our bound can be computed and is non-vacuous for state-of-the-art deep networks fine-tuned on standard image classification tasks (Table 1). We also study the dependency of the bound on the size of the dataset (Figure 2), and the hyper-parameters (Figure 3).
Preliminaries
We denote with [nx] the set {I....;"2) n and with Rd the of real-valued and complex-valued d-dimensional vectors. A and A-i denote the transpose and inverse of a square matrix A. If x is a vector with n elements, then diag(z)) denotes the
square matrix with the elements of on its main diagonal; ||-I| is the standard Fuclidean norm on vectors. We use uppercase letters to denote random variables, and lowercase letters denote specific value the random variable can take. If X is a random variable, then is the probability distribution of X, and Ee-px [x]] denotes the expected value of X. For a pair of random variables X and Y. P(x,Y) and PxPy are the joint and product distributions, respectively. If p and q are two probability densities over Idd such that is absolutely continuous with respect to q (p < q). the Kullback-Leiblee Divergence from p g is defined as:
KL 1l q) = -fe p(z) log
p(x)) ((x)
The Mutual Information between two random variables X and Y, and the conditional mutual information of X and Y given a third random variable are respectively given by:
I(X;Y)= = (L(P(X,)) Pxpr). T(X;Y Z) = E Eg-ry [[X; [=)
(2)
(3)
1(x;11Z=2)
2.1 Problem Formulation
Let z" = -Z,,.... .n) E 2" be collection of n independent and identically distributed samples drawn from some unknown distribution P. We consider the setting of supervised learning where Z = X' x V: i..., each sample is composed of feature vector and label. Let A: 2" + W C R be a possibly stochastic training algorithm, where W is a set of weights (c.g., weights in a neural network). Given loss function l W x Z R4, the empirical risk for weights on 2" is given
was also independently introduced in [1]]. This work was not available at the time of our submission: it was pointed to us along with the paper decision. To our understanding, Doo-CMI was introduced in [11] for mainly studying the generalization properties of interpolating algorithms.

---

by Z(w, = =1/= f(w, Z,), and the "true" loss is given by L(w) = Eg (e(w, Z']]; i... the average loss w inuur on random samples drawn from P.
Our goal is to find a w" E W such that w' = arg win L(w). Since we do not have access to the data-generating distribution P. computing the true loss is infeasible. However, do have access to a set of samples Z", and one approach is empirical risk minimization where we find the w E W that minimizes L(w, 2" If the difference [(w) L(w, Z") is small, then the true loss of an empirical risk minimizer would be nearly optimal within the considered hypothesis class. Therefore, it is of great interest to study the generalization gap of A (given n samples for ease of notation):
gen (A) = E A,," Lapa [C(A(="))) - ),,", 2=>1))]
(4)
2.2 Conditional Mutual Information Bounds
We start by recalling the main results on Conditional Mutual Information (CMI) bounds that we return to later. Let 2 E g be a dataset with 2n samples drawn from a distribution P. grouped into pairs. Let S ~ S = Uniform ( (40, 1)") uniform random binary vector of size n. S selects one sample from each pair in 2 to form Zg E 2" given by (Zg); S. In this setting, the bound of Steinke and Zakynthinou [29] arises from asking the following question "if model is trained with subset of samples chosen through the random binary indexing vector S, how much information does the output of the algorithm provide about S?" Here, the Shannon Mutual Information useful because it is measure of the amount of "information' obtained about one random variable after observing another random variable.
Theorem 2.1 (Theorem 2, [29]. Let E: W x Z -- [0, be a bounded loss function. Let A be possibly stochastic training algorithm. Let W A(g))) be the output of given the dataset 7,g. then
2 I(W: S 2
gen(AA S
V
(5)
n2
Haghifam et al. [12] improved Theorem 2.1 by moving the expectation over 2 outside the square root, and by measuring the information the output of the algorithm provides on random subsets of the indexing vector S. Harutyunyan et al. [16] further improved the bound by moving the expectation over the random subsets outside the square root.
Theorem 2.2 (Theorem 2.6, [16]). Let W x Z + 10, 1] be bounded loss function. Let m E [n] and let V ~ V be a random subset of [m] of size m. Let W A((s) be the output of A given the dataset 7., then
2 (A) S Egan Bp IW; S. 1
One appealing aspect of the CMI bounds is that they work for any training algorithm and any model, including weer-parameterized networks trained with Stochastic Gradient Descent (SGD). However, computing the bounds requires iterating over all possible 2-V values of S. Moreover, the bound is difficult to interpret since the value of W A(?3) for different values of S can vary significantly and in unpredictable ways for large non-convex models. Taking inspiration from leave-one-out cross validation, we propose a different CMI bound which avoids both problems by removing a single sample from the dataset. As we shall see, the bound allows for interpretable expressions, faster computation, and connection to notions of stability.
3 Leave-One-Out Conditional Mutual Information
Let Z" = [21, Zz.... ......,Z, 2n} E Z" be a dataset of n i.i.d. samples drawn from P. Let U ~ U Uniform((x)) ([n)) be uniform random variable taking values over the indices of the samples in Z. U removes a single sample from z" to form -ー=1 z" Zu. the dataset without the tt sample. Let W = A(Z==,)) be the output of the algorithm, then we define the pointwise leave-one-out conditional mutual information as:
loo-CMI(A,2") I(W;U 12").
3

---

In this setting, loo-CMI(A, 2²) measures the amount of information that the output of the algorithm W reveals about U. the index (identity) of the left-out sample. As is the case with the conditional mutual information terms in Theorems 2.1 and 2.2, loo-CMI is bounded. Specifically, loo-CM is upper bounded by the entropy of U, H(U) = log(n). Hence, does not suffer from the same issues as information stability bounds [1]. Moreover, the output of an algorithm is not significantly affected by the inclusion or exclusion of one sample when the input consists of thousands other samples, expect loo-CMI to be small for large values of n. We use (7) to derive bound on the generalization of error in expectation (Theorem 3.1).
3.1 Generalization Bounds Based on loo-CMI
loo-CMT is deeply intertwined with leave-one-out cross validation, so before we derive bounds on the generalization through loo-CMT, it is helpful to first obtain a probabilistic upper bound on the leave-one-out cross validation eггоr (loo-ev). loo-cv measures the difference in loss between the samples which the algorithm trained on, and the sample that was left out. We begin with precise definition of loo-cv and probabilistic bound on it.
loo-cv(w, =" u))
Σ E(w, flw, zu)- ingu
Lemma 3.1. Let 8: W 2 - [0, 1] be a bounded loss function, then for all t 0, w E W, and E Z, Busal (exp (1. (1oo-ov(w, 2", x))) S exp
t
n
Gn
(9)
To derive the generalization bounds included in this paper, make heavy use of Lemma 3.1. We begin with generalization bound in expectation.
Theorem 3.1. Let A: 2n-1 + W be a training algorithm. Let E: W x 2 + 1] be bounded loss function, then
Cn EE EgnnP" V Loo-CMMI 2"), V2
(A))
(10)
where is given in (9). The bound in (10) guarantees a good generalization error when loo-CMT =") is small, i.e., when the output the algorithm W tells us little about the iden- tity of the sample that was removed from the training dataset. If parametric learning algorithm ends up memorizing the samples the training set, the generalization gap could be large, and so would loo-CMI as we can determine U by checking which sample was not memorized by the algorithm. On the other extreme, a learning algorithm which outputs a constant parameter regardless of the training set does not have generalization gap, and in this case loo-CMI would equal 0 W provides no information about U. We note that the bound of Theorem 3.1 most closely resembles the bound of Theorem 2.2 when 1. The latter bound is given by:
gen(A) (A) < Σ Egan / (WW E2n).
(1I)
Recalling the setting of Section 2.2, (11) computed by first going through every possible value of S E (0, 1).. For every value of S and for each i E [n], one fixes S = (S), S S,) excluding S, which varies uniformly over {0. 1). In other words, the tth component of the training set 23 is equally likely be either Z,,1 24,2- The right-hand-side of (11) then bounds the generalization using the information that the weights contain about S;. In other words, the question asked is: "can the output of the algorithm help determine which one of žं, or 21, was present in the training set?". On the other hand, we ask a different question: "can the output of the algorithm help us determine the index of the sample that was removed?". This subtle change leads an exponential reduction in the cost of computing the since we only need to iterate over the values of U E [12]. as opposed which can take 2n possible values.
3.2 Extension To The Function Space
The previous bounds used the output of the algorithm, the weights, to bound the generalization error. A different approach studied in [16] is to assume that given a training dataset and a test

---

sample, the algorithm outputs prediction on the test sample. In other words, we assume the algorithm is a possibly stochastic function : 2n-1 X - R which takes a training set 2, a new unlabeled sample Inew, and outputs a possibly stochastic prediction knew) on the new sample. The set of predictions can be different than the set of labels Y (e.g. class probabilities in multi-class classification tasks). Unlike bounds with respect to the weights, this approach is applicable to both parametric algorithms (e.g. neural networks) and non-parametric algorithms (e.g. k-nearest neighbors). In the former case, the output of the algorithm A specifies prediction function 9 E (gw X + R. | w E W] from a class of functions parameterized by the weights i.e. h(2, Feww) 9.A(=) (Fuew).
We redefine the loss be non-negative function : x y + R. that measures the distance between the predictions and the ground-truth labels. Given E and training set Z", the true loss of an algorithm given by C(h, 2d) = (/ [e(h(Z", "ellz",>" x²), )/)] and the empirical loss given by [(,, k*) 1/n E== ((h(Z", X:), Y:). The generalization gap of h given is then defined as:
gen (h) = In [2h,, "0 - [(,, x" ===1)
(12)
Recalling the setup of Section 3, we define the pointwise functional leave-one-out conditional mutual information floo-CMI as:
(13) While loo-CMI measures the reduction in uncertainty about U after having known the weights, Roo-CMI measures the reduction in uncertainty after having known the predictions made on the whole dataset (including the prediction on the removed sample). We derive a bound with respect to (loo-CM(h,, =²) using a proof that closely resembles the proof of Theorem 3.1.
floo-CMT(h, =") = 7 (="""""");UUp
Theorem 3.2. Let e R x y -
[0, 1] be a bounded loss function. Let U be a uniform random
variable over [n]. then
ghn s
Gn EE EenNPN floo-CMI(h, 2"), V2
(14)
where Gn is given in (9). For a parametric algorithm A with prediction function h, U U-A(==7") h(2"7') X) is a Markov chain. By the data-processing inequality, we have that Moo-CMI(( I loo-CMI(A, 2)) Since the bounds of Theorems 3.1 and 3.2 differ only through loo-CMI and floo-CMI, the bound of Theorem 3.2 is sharper.
Computing The Bounds
4.1 Computable Upper Bounds to loo-CMT and floo-CMI
To evaluate and interpret the bounds for a parametric algorithm A with prediction function h, we require a computable closed-form expressions for loo-CMI and floo-CMI. However, obtaining closed form expression is a difficult task in most cases. To see the reason behind this difficulty, note that loo-CMI can be written as:
(O,CMMIA,, 2) I(; |1") Eu-u [KL(PW] |= || Pw ==)]]
(15)
where PW = = En-zz [PW| s is mixture distribution. Since one of the terms in the Kullback- Leibler divergence of (15) is a mixture distribution, it is unlikely that one could find a closed-form expression for the mutual information except for simple cases (c.g., we cannot obtain closed- expression for Gaussian mixtures[8]). To find a computable and interpretable bound on the generaliza- tion error, we propose upper bounds on the conditional mutual information which can be interpreted and evaluated.
Theorem 4.1. Let A be parametric algorithm with prediction function h. Let U, Z", W be defined as before. Let U² be an identical independent version of and W A(2 )), then
loo-CMI(A, x²) < -En-21 [In Ene-
[exp (-KL(PW) |=7,a 1l Pw [."
(16)
floo-CMI(h, 2*) < Ex Em
[exp (KKL(P ..) ())))
(17)
One can alternatively upper bound foo-CMI through the convexity of the Kullback-
divergence
(similarly for Iloo-CMI). However, since the function (-In) is strictly convex, it is easy to show that the bound of Theorem 4.1 strictly tighter through Jensen's inequality. Moreover, we opt to use this bound as it allows for more interpretable expressions (Corollary 4.1).
5

---

Figure 1: Visualization of the quantity involved in the bound. We plot a projection of the loss landscape (contour lines) of a ResNet-18 18 trained on MIT-67 using the technique of [20]. In orange and blue we show the projection of training paths obtained by removing two different samples from the dataset. Equation (18) bounds the test error of the two paths, normalized by amount of noise added (displayed by the cloud around the final weights). Note that if the loss landscape is flat we can add more noise, therefore obtaining better bound (Section 4.5). If the optimization algorithm stable, the two paths will remain close at all times, which will also improve the final bound (Section 4.4).
function of the distance between the final points
4.2 Geometry Aware Synthetic Randomization
Theorems 3.1 and 3.2 are valid in theory, but the outputs of algorithms used in practice are determinis- tic given fixed input, and so we do not have distribution of weights predictions. This means that (7) and (13) are degenerate. Even if we vary the random seed for neural networks trained with SGD, and run the algorithm for each dataset and random seed, we obtain set of discrete distributions with unequal supports. We alleviate this issue by taking measures similar to the ones made in [12, 22, 15], and also previously related contexts in [2, 9, 1, 23]. particular, we add noise the output of deterministic algorithm, and use the now stochastic algorithm to bound the information in the weights and predictions. We avoid adding isotropic Gaussian noise for the weight- based bounds, changing the values of some weights may have little effect the loss compared to others. Therefore, we add noise while taking into account the geometry of the loss landscape.
Specifically, let A be deterministic algorithm, and let As(z"T') A + N, where N NO Σ). A choice of Σ that would incorporate the notion that weights have a varying effect on the loss is aj for * Similarly, ha (="T" x)- h(="T1 x) M, where M NN(0, o²T). The generalization bounds derived for Ag or ha are not directly applicable to A and h, but if certain Lipschitz continuity assumptions hold for the loss function f, it is possible to derive bounds for deterministic algorithms from the bounds of their noisy counterparts (Theorems 4.2 and 4.3). We begin by applying Theorem 4.1 to get interpretable expressions for the conditional mutual information terms.
diag(a1...... axx) with Og > 0 for all and a; not necessarily equal to add noise predictions made by deterministic algorithm as
Corollary 4.1. Let A be a deterministic algorithm with prediction function h. Let w-; = A(=";')
and h-; = h(2=,1,,a ((a""",a")) be the output and predictions respectively when ith sample is removed from the training Using Theorem 1,1, obtain
1oo-CMI(As,2")) < In(n)
In
Σ 1=1
2 (w- w w- (w (w---)))))
(18)
floo- SRo-CMI(ha,220 < In (n)
In
(19)
4.3 Connections to Stability and Bounds For Deterministic Algorithms
It is easy to see the connection between classical definitions of stability and the right-hand side of (18), (19). After all, to compute the right-hand side of (18) and (19), one only needs to know how the weights and predictions of the algorithm change when two datasets differ by one sample. Based on

---

the observation that components of the weight might have differing degrees of effect on the loss, and the right-hant side of (18), we introduce the idea of "relative" weight stability. Moreover, we also use classical definitions of functional stability, and here we find it useful and intuitive to define two notions of stability: one with respect to the samples that the two datasets share, and one with respect to any other sample. The definitions are as follows.
Definition 4.1. Lel =d=1 gn-1 E 2 be datasets such that =n11 and =n~1 differ by at most one sample. Letting A(==~1)- A(22-1), then say that deterministic algorithm A has weight stability relative to positive semi-definite matrix 2 if x='="---
é.
Definition 4.2. Let zn-1, _n-1 E Z" be datasets such that 2==1 and 2n differ by most one sample, and without loss of generality, assume they differ at the first sample i.e. 21 # &1 and 2 = 2 for all lo # 1. Let h be prediction function h zn-1 x X + IR, then say h has B-train stability if [[]n(=="> --, 2k) 11 (==-1,,=)) ,2,]]² < 3² for all k + 1. Moreover, we say that h has Bi-test stability if |1(22-1,, .²) h( h(2"~1,2') ,2)]| =2]] S pi for all x' e.
Given bounds on the noisy version of deterministic algorithm, one can derive bounds on the deterministic algorithm itself by making certain Lipschitz continuity assumptions on the loss function. Moreover, we show that given relative weight stability and functional stability of deterministic algorithm, we can add an optimal amount of noise to find bound on the deterministic algorithm. The following technique is also used by [16, 22] for the case of isotropic noise. We generalize this result for arbitrary values of the noise covariance.
Theorem 4.2. Let A: : zn-1 + W be deterministic algorithm, and let é: W x Z - R. be the loss that a set of weights incur on sample. If f(w,,) is L-Lipschitz in the weights, then if A has e-weight stability relative to a positive semi-definite Σ, then gen(.A) S /tr()))
Theorem 4.3. Let h : 2n x + Bdd be a deterministic prediction function. Assume that h has B-train stability and 31-tsst stability. Assume the loss function E. R x y is L-Lipschitz continuity in the first coordinate, then gen(A) S V4cnIv/nd(n3 +284)-
4.4 Bounds For Stochastic Gradient Descent
As we have seen, the quality of our information bound depends on the stability of the optimization algorithm. Stochastic Gradient Descent is the most commonly used method in deep learning, and is therefore interesting to study the stability of SGD and how it translates into generalization from an information theoretic point of view. Assuming the gradient updates are y-bounded, || - w/ S Vテ for 7 > 0 and all > O, where wA the weights iteration t, then with respect to the number of iterations of SGD [14], and obtain a bound on the generalization through the right-hand-side of (18). In particular, a shorter time T and having more bounded updates both contribute to generalization. The bound relates to the observation that early stopping (training for a smaller number of steps T) may improve the generalization of the network.
can bound ||w-; w-j/
derive the following bound which show how training for
Lemma 4.1. Let the gradient update rule be y-bounded. Suppose we run SGD for T steps, and we 2.T
use the same starting value the weights, then gen(Ag=1) S
4.5 Local interpretation of the bound
The bound in Corollary 4.1 depends on non-local quantities as requires retraining the model a linear number of times on subsets of the data. Ideally, one wants to bound the generalization without having to retrain. We now provide a qualitative approximation of the bound using local quantities, order to connect the bound with the geometry of the loss function. Assume that the training algorithm minimizes the loss A(=")= = arg minwee {(=", w), and let w* = A(x²)) be the minimum to which the algorithm converges, and similarly let w", A(="=1). Using influence functions [19], we can approximate:
1 w", w² VV w²) gs: 11 where H. is the Hessian of the loss V e w²) is the gradient of the loss z; for w". and we have introduced the per-sample gradient at convergence rescaled by the Hessian g. 1 H. V (2, w*).
(20)
7

---

Using this notation we can approximate:
1
(m=-----)² x- ((c-)-w)))
(oo-CMI(A2.2) In(n)
In
(21)
i=1
1=1
ll(nn)
1
In
Σ
1 (d: m3)² ((:)))}
(22)
i=1
j=1
In(n)
In
Σ
e
6 9,)" 9,)" H.. (g)-9))
(23)
where in (+) we have assumed Σ Hn=,, which the optimal variance of the noise (Section 4.2).
From (23) we see that converging to flat minimum, that is, having a small norm of the Hessian H.-, expected to correlate to better generalization. This is in accordance with several empirical results connecting flat minima to better generalization [18, 9, 6]. It should be noted that flatness by itself cannot explain generalization, since we can reparameterize the network have identical predictions (and hence generalization) but arbitrarily large Hessian [7]. Indeed, in (23) we see that the role of the Hessian mediated by the similarity of the (re-scaled) per-sample gradients at convergence, which can change under reparameterization. In particular, studying flatness by itself is not enough.
5 Related Work
Over the past several years, there has been significant line of research in using information theory both to interpret the behavior of DNNs [2, 28, 1] and to derive generalization bounds [27, [27,31,5, 5, 21, 29, 12, 16], with the earliest works on this line from [3, 27, 31]. Many of them develop information stability bounds which involve the mutual information between the output of the algorithm and the samples [27, 31, 5, 21] which could degenerate, e.g., if the data continuous. This was observed in [29], which then proposed new bound based on the conditional mutual information (see Theorem 2. which is non-degenerate. This work was further extended by [12, 16]. particular [16] developed bounds based on prediction outputs rather than the algorithm outputs, and its combination with the conditional mutual information framework made it the sfatc-of-the-ar in terms of information- theoretic generalization bounds. The two issues identified in our work related to this is one of computability (as the [16] bound might in principle require computation exponential in the size of the dataset) and interpretability; this is the main focus of our work. In particular, our loo-CMI framework can not only be computed more efficiently, but also connects to classical leave-one-out cross validation measures used extensively in practice (see Theorem 3.1). Another aspect introduced in [16, 22] is the application of CMI bounds to deterministic algorithm outputs (as one can only run finite number of runs of even randomized algorithm on a dataset). We use this viewpoint in our work, but using a geometry-awan method (see Theorem 4.2), which takes into account the loss landscape in the algorithmic output space. There has also been a line of work connecting SGD to generalization including earlier works in [13] and more recently its connection with information theoretic bounds [25, 22]. We apply these ideas to the framework of loo-CMI (see Lemma 4. 4.1.. The connection to classical notions of algorithmic stability can also be made using the loo-CMI framework (see Theorem 4.3).
Experiments
Model and datasets. We now study the behavior of our loo-CMI and floo-CMI bounds on real- world image classification tasks. In particular, we fine-tune an off-the-shelf ResNet-18 model pretrained on ImageNet on set of standard classcclassiiication tasks (see also Table 1): MIT-67 [26] and Oxford Pets [24] with few thousand examples each. On both datasets we fine-tune for 10 epochs using stochastic gradient descent with learning rate 1) = 0.05, momentum m = 0.99, batch size = 256, and weight decay 0.0005. We compute w-t/h-; by removing sample i from the training set and re-training from scratch. For all the experiments we remove 10 samples one at time across 3 random seeds and use corollary 4.1 to compute the information bounds. We used NVIDIA 1080Ti GPUS and the experiments take approximately 1-2 days.
8

---

Dataset
Train Error
Test Error
loo-CMI
floo-CMI
MIT-67 [26]
0
0.339
9.65
0.493
Ox. Pets [24]
0
0.134
8.51
0.514
Table I: Generalization bounds on imaae-classificatioo tasks. We report the train and test error (fraction of wrong predictions) and our generalization bounds on several image classification dataset
(a 0.1).
MIT-67
Oxford-Pets
0.8
Beanse
Bounds
FLOO-CH bound Gereralzation Oap
nLOC-CH sound
0.7
Gencroliztion
0,6
Error
0.6
Error
0.4
0.5
0.2
0.7
0.9 Dataset Fraction
0.8
1.0
0.7
0.9 Dataset Fraction
0.8
1.0
Figure 2: floo-CMI bound and dataset size. For different datasets, we plot of the floo-CMI bound as the fraction of samples used in training increases. We observe that larger datasets have better generalization bounds. This is expected as stability improves with larger datasets.
MIT-67
Oxford- Pets
0.7
1100-CMI "Tat Entrr
RLCO-CM
Text Eroor
0.6
0.6
Emar
Errr
0.5
0.4
0.4
0.2
0.3
0.1
0.2 Sigma
0.3
0.4
0.1
0.2
0.3
0.4
Sigma
Figure 3: Effect of varying a. Increasing the value of a in (14) improves the floo-CMT bound (blue line) but also makes he increasingly different from h (as shown by the increased test error, orange line), thus making bounding the generalization of the original algorithm h given h, more difficult.
Non-vacuous bounds. In Table 1, we compute the loo-CMI and floo-CMI bounds using (10) and (14). We show that while the former bound is vacuous, the floo-CMI bound provides non-vacuous generalization bounds on all datasets. This is significant, as obtaining non-vacuour bound for large- scale models remains a challenging problem. The failure of the bound based on loo-CMI is expected here, since 1oo-CMI looks directly at the information contained in the weights of the network without considering how this information used. In large models with millions of parameters, most of the information in the weights do not significantly affect the predictions and should ideally be discarded. This is indeed done by the floo-Ctt MMo bound.
Effect of the dataset size. To show how the quality of the bound changes for different sizes of the dataset, we subsample randomly and without replacement n samples from each dataset. In Figure 2, we plot the resulting generalization gap alongside our generalization bounds as the size of the subsample varies (in terms of fractions of the dataset). We observe that the generalization bound becomes tighter as the size of the training set grows. This is not surprising as we expect the model to become more stable for larger datasets.
Synthetic randomization. In Section 4.2, we introduced artificial Gaussian noise N(0, Σ) in order to obtain better bounds. Increasing the noise variance Σ in the loo-CMT bound, or a in flo improves the bound on the CMI. but also increases the test error of the model. Hence, we need to

---

select value of Σ and that provides good trade-ofi off between the two. In Figure 3, we show how changing the noise variance affects each term.
7 Conclusion
In this work, we introduced a bound based on a new information-theeorticc measure, i.e., leave-one-out conditional mutual information and analyzed its properties. loo-CMI bounds reduce the computational costs compared to prior CMI bounds, connects to several empirical quantities and generalization theories. It leads non-vacuous bounds for several deep learning applications in image classification. There are several open questions including, whether it is possible to (i) obtain tighter bounds using the leave-one-our framework for general learning algorithms; (ii) further reduce the computational cost of computing loo-CMI and (iii) obtain deeper understanding the effect of loss landscape and dynamics of learning algorithms on learning performance using the mnformation-theore lens.
Acknowledgments and Disclosure of Funding
This work was supported in part by NSF grants #1955632, #2146838, #2139304, #2007714, ONR N00014-22-1-22522 and ARO W91 1NN-1771-0304, The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed implied, of the Army Research Office the U.S. Govermentt The U.S. Govern- ment is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
[1] Alessandro Achille, Giovanni Paolini, and Stefano Soatto. Where is the information in a deep neural network? arXiv preprint arXiv:1905. 12213, 2019.
[2] Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep representations. The Journal of Machine Learning Research, 19(1):1447-188) 2018.
[3] Ibrahim M Alabdulmohsin. Algorithmic stability and uniform generalization. In C. Cortes,
N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[4] Gregor Bachmann, Thomas Hofmann, and Aurélien Lucchi. Generalization through the lens of leave-one-out error, 2022.
[5] Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli. Tightening mutual information based bounds on generalization error. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 587-591, 2019.
[6] Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Chris- tian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, 9019(12):124015 2019.
[7] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028. PMLR, 2017.
[8] J.-I. Durrieu, J.-Ph. Thiran, and F. Kelly. Lower and upper bounds for approximation of the kullback-leibler divergence between gaussian mixture models. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4833-4836, 2012.
We point to [4], which we were made aware of at the end of the review process. In particular, this work reduces the cost of computing the leave-one out error in the kernel regime, although it does not directly connect the loo-CMI framework of paper, it might be possible combine them make progress this question.
10

---

[9] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data, arXiv preprini arXiv: 1008, 2017.
[10] Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. 2007.
[11] Mahdi Haghifam, Shay Moran, Daniel M. Roy, and Gintare Karolina Dziugaite. Under- standing generalization via leave-one-out conditional mutual information. arXiv preprint arXiv:2206. 14800, June 2022.
[12] Mahdi Haghifam. Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite, Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. In Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9935. Curran Associates, Inc., 2020.
[13] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. International conference on machine learning, pages 1225-1234. PMLR, 2016.
[14] Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of the 33rd International Conference on Interna- tional Conference on Machine Learning Volume 48, ICML' page 1225-1234 JMLR.org. 2016.
[15] Hrayr Harutyunyan, Alessandro Achille, Giovanni Paolini, Orchid Majumder, Avinash Ravichandran, Rahul Bhotika, and Stefano Soatto. Estimating informativeness of samples with smooth unique information. International Conference on Learning Representations, 2021.
[16] Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan. Information- theoretic generalization bounds for black-box learning algorithms. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Curran Associates, Inc., 2021.
Processing Systems, volume 34, pages 14670-24682
[17] GE Hinton and Drew van Camp. Keeping neural networks simple by minimising the description length of weights. 1993. In Proceedings of COL7-93, pages 5-13.
[18] Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Nearal computation, 9(1):1-42, 1997.
[19] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Leurning Volume 70, ICML'17, page 1885-1894. Jog,.org, 2017.
[20] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 31, 2018.
[21] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information-thherrtiiic generalization bounds for sgid via data-dependent estimates. In H. Wallach, Larochelle, A. Beygelzimer, F. d'Alché-Bus Buc, E, Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[22] Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M. Roy. Information- theoretic generalization bounds for stochastic gradient descent. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3526-3545. PMLR, 15-19 Aug 2021.
[23] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring generalization in deep learning, 2017.
[24] Omkar M. Parkhi, Andrea Vedaldi, Andrew Zisserman, and C. V. Jawahar. Cats and dogs. In IEEE Conference Computer Vision and Pattern Recognition, 2012.
11

---

[25] Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy. iterative algorithms. 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550, 2018.
[26] Ariadna Quattoni and Antonio Torralba. Recognizing indoor scenes. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 413 420. IEEE, 2009.
[27] Daniel Russo and James Zou. Controlling bias adaptive data analysis using information theory. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 1232-1240, Cadiz, Spain, 09-11 May 2016. PMLR.
[28] Ravid Shwartz-Ziv and Naftali Tishby, Opening the black box of deep neural networks via information. arXiv preprint arXiv:/703.00810, 2017.
[29] Thomas Steinke and Lydia Zakynthinou. Reasoning About Generalization via Conditional Mutual Information. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3437-3452. PMLR, 09-12 Jul 2020.
[30]
Obtaining a tight bound for expectation w.r.t uniform random variable. Mathematics Stack Exchange. httph/////maahtstaaeeccca...ooop
user6247850
(version: 2022-03-24).
[31] Aolin Xu and Maxim Raginsky. Information-theeretii analysis of generalization capability of learning algorithms. In I. Guyon, U. Von Luxburg, S. Bengio. H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
12


Reviews:
[{"review_id": "X5ZtgUlCaS6", "reviewer": "Reviewer_wWYy", "summary": "The paper considers conditional mutual information based generalisation bounds for understanding the generalisation properties of neural networks. It builds on techniques introduced by prior work and overcomes a practical limitation: prior work requires computations that grow exponentially in dataset size, while the proposal entails only linear growth in dataset size.", "questions": "See above", "limitations": "See above", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written. I am not an expert in this area (hence also low confidence in my review) but the paper was a pleasure to read. \n\nThe paper is contributing to understanding generalisation in deep neural networks. This is one of the most important problems in the ML community today, and I welcome and support work towards this.\n\nSince I am not an expert, I cannot fully evaluate the novelty of the work. However, if the authors are correct in their description of the current state of the field, I believe their results are very impactful. \n\nNonetheless, I have a few comments and things that i think could improve the paper:\n\n\n\n- please use the actual submission template with line numbers, it makes it much easier to review\n- typo page 2, paragraph 2, line 3: our loo-CMI only needS to \n- theorem 4.1: I didn't understand what U' brings. In equation 16, doesn't the independence of U' mean that  p_{w|zn, u'} = p_{w|zn} ? Or do you mean \"independent\" in the sense of \"another\" or \"duplicate\" rather than the statistical sense?\n- could you comment on the computational requirements of this method? You need to train N models, one for each datum right? This must be very slow for reasonably sized datasets. \n- One idea for evaluating your method on larger datasets: practitioners sometimes fine-tune just the last layer of a DNN, rather than the whole network. If you precompute features of the data up to this last layer, this is like training a linear classifier. This could enable you to try out your method on larger datasets.", "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": "JdbNfSb1vv5", "reviewer": "Reviewer_tDeb", "summary": "This paper presents a new leave-one-out conditional mutual information method to bound generalization risk. Specifically, two information theoretic generalization upper bounds, namely loo-CMI and floo-CMI, are proposed. The authors claim compared to standard CMI, the proposed bounds are more cost-effective because they reduce the computing cost from 2^N to only N. Strong theoretical analysis are provided. In addition, some empirical results have been reported in image-classification problem. ", "questions": "1. Can these bounds be used for model training? Or they only can be used to do model selection.\nHow costly does it take to compute the bounds?\n\n2. It is puzzling that the results in Table 1 all have training error to be 0. Do they imply the models have overfitted the data?\n", "limitations": "My major concern is the utility of the methods, since the authors do not show any actual applications of their bounds to facilitate the real-world machine learning practices.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThe authors proposed the novel information generalization bounds. \n2.\tThe theoretical analysis is sound, and it shows the bounds have good properties.\n\n\nWeakness:\n1.\tThe authors should compare their methods to competing baselines. For example, the f-CMI bound from paper [1]. Moreover, the author should provide the results for more complex datasets, such as ImageNet.\n2.\tIn Figure3, the authors should plot training errors+ proposed generalization bounds, do they dominate the test error? In addition, the stability analysis is missing. And the authors should repeat the experiments and report the error bar to show the variance of the bounds in Figure 2&3.\n3.\tThe authors need to demonstrate their methods actually works in empirical settings. More concretely, the author should apply their methods on a set of different models trained on the same real-word dataset and show the predicted generalization bounds are consistent with the actual test error. \n\n[1] Harutyunyan, Hrayr, et al. \"Information-theoretic generalization bounds for black-box learning algorithms.\" Advances in Neural Information Processing Systems 34 (2021): 24670-24682.\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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "GUwbBMJp27L", "reviewer": "Reviewer_dogW", "summary": "This paper argues that standard conditional mutual information (CMI) bounds are difficult to compute and interpret. Inspired by the spirit of leave-one-out cross-validation, the authors present a computable and interpretable bound termed loo-CMI. In particular, the proposed loo-CMI assumes that a generalized algorithm should not be affected by a small perturbation (i.e., leaving one training sample out at random). Furthermore, they interpret their bound in the function space, which leads to a tighter bound (i.e., floo-CMI). Empirically, they evaluate the quality of the bound and provide sufficient analysis.", "questions": "1. Does the small number of samples result in high randomness of the previous empirical results? Did the authors do ablation studies on ``the number of samples'', especially for the larger number?\n2. How does the pre-training dataset size influence the quality of the proposed bounds?", "limitations": "Yes, the authors have addressed the societal impact of their work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This idea is intrigued by an intuitive assumption that a generalized algorithm should not be affected by a small perturbation. The authors do a good job of motivating this work, and the proposed bounds (i.e., loo-CMI and floo-CMI) are simple but reasonable. Also, the paper is very well written and easy to understand.\n\nMy main doubts/concerns regarding the paper are the following:\n\n- In Fig 2 and 3, there is a big difference between the main paper and supplementary material. Does it mean that the previous empirical results suffer from high randomness when the number of samples is small? Did the authors do ablation studies on ``the number of samples'', especially for the larger number?\n- While the analysis of the dataset size during fine-tuning is interesting, I believe the pre-training dataset plays a more crucial role in determining the generalization ability of deep models. Can the authors compare their results on different pre-training dataset scales?\n\nMinor:\n\n- The code should mention the key lines corresponding to loo-CMI and floo-CMI.\n- The Conclusion section needs to be added.", "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": "GAwTpJWTq8C", "reviewer": "Reviewer_FLYU", "summary": "Several generalization bounds have been derived in the literature for machine learning models using some notion of mutual information. These differ in how to measure the mutual information (e.g. whether it is between the hypothesis and the entire sample S or a subset of it) and whether or not the mutual information is conditional on other random variables and so on. In this work, the authors present yet another approach in which a single example is removed from the training set. The authors argue that the primary advantages of this approach are that it can be computed in O(n) time (since there are n examples to remove from) and that it is non-vacuous. They further show that measuring the mutual information between the predictions of the model and the data also yields similar bounds, which are tighter by the data processing inequality. Finally, the authors relate such bounds to stability and flatness. ", "questions": "- Please double check the bound in Lemma 4.1 ", "limitations": "Please see the comments above for the limitations of the work. Since this is a theoretical work, there are no societal impact as far as I can see. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*:\n\n1- The paper introduces a new approach for analyzing the generalization gap that can be useful to the community. \n\n2-  The authors connect it nicely to related concepts, such as stability and flatness. \n\n*Weaknesses*:\n\n1- There are no tightness results. In fact, the bounds seem to be vacuous in most settings. \n\n2- The SGD bound is odd because the bound increases with the number of SGD steps T, when a reasonable bound should be decreasing with T. \n\n**Details**\n\nThe paper introduces a new information-theoretic approach for bounding the generalization gap of machine learning models. The paper is well-written and I think it offers great insight. For example, it suggests a new approach for quantifying flatness of the local minima that does not suffer from pitfalls observed in prior works (e.g. that one can arbitrarily change it via re-parameterization without changing the decision boundary). I think it would strengthen the paper to apply this measure of flatness on techniques that arguably improve flatness (e.g. by comparing it for neural networks trained with or without skip connections, SAM optimizer [1] or by applying it to methods trained via reinitialization [2, 5]). \n\nOn the downside, the authors emphasize that their approach yields non-vacuous bounds. However, the form of the bounds in Corollary 4.1 does not really support that argument. If the quadratic term in the exponent is bounded away from zero by a small epsilon, the entire bound is O(log n), which is vacuous for large training sets. For SGD, it seems strange to me that the bound increases with T, when it should decrease. \n\nIn the experiments, the authors use small datasets with a few thousand training examples. At minimum, the authors should show that larger training sets yield better bounds as they should given the interpretation in terms of stability. For example, they can train on subsets of the data and report results as the subset size increases. Also, the authors use pretrained models and fine-tune for a few epochs. These are (by nature) stable since pretraining improves stability. I think the authors should include experiments without pretraining to show that they still obtain useful (non-vacuous) bounds. The reason I am emphasizing on this is that this has been a main motivation throughout the paper so it should be demonstrated experimentally. \n\nOverall, I still think the paper is worthwhile and I hope that the authors would address the issues above in the experiments to make their argument more convincing. \n\nSome minor comments:\n\n1- The technique of introducing noise to control the bound has been used in PAC-Bayes methods and it has been connected to flatness as well. See for example [3] and [6].  Perhaps, this should be mentioned in the related works. It would be useful to include some of those bounds in the comparison. \n\n2- In Section 5, the authors claim that the earliest works were published in 2016. There are earlier works that derive non-vacuous generalization bounds with tightness results (see for instance [4]), in which the mutual information is measured between the hypothesis h and a single training example. In the latter case, the bounds are non-degenerate even for deterministic algorithms with uncountable hypothesis spaces. It has also been connected to stability, like in the present work.\n\n3- Typo in Definition 4.2: \"we say that $\\beta_1$ test stability if\". \n\n[1] Foret, P., Kleiner, A., Mobahi, H. and Neyshabur, B. \"Sharpness-aware minimization for efficiently improving generalization.\" ICLR, 2021. \n\n[2] Alabdulmohsin, I., Maennel, H., & Keysers, D. (2021). The impact of reinitialization on generalization in convolutional neural networks. arXiv preprint arXiv:2109.00267.\n\n[3] Neyshabur, B., Bhojanapalli, S., McAllester, D. and Srebro, N., \"Exploring generalization in deep learning.\" NeurIPS, 2017.\n\n[4] Alabdulmohsin, I. \"Algorithmic stability and uniform generalization.\" NeurIPS, 2015.\n\n[5] Zaidi, S., Berariu, T., Kim, H., Bornschein, J., Clopath, C., Teh, Y.W. and Pascanu, R., 2022. When Does Re-initialization Work?. arXiv preprint arXiv:2206.10011.\n\n[6] Dziugaite, G.K. and Roy, D.M., 2017. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008.\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