Bounding generalization error with input compression: An empirical study with infinite-width networks
Authors: Angus Galloway
Anna Golubeva
Mahmoud Salem
Mihai Nica
Yani Ioannou
Graham W. Taylor
Venue: Accepted by TMLR ()

Abstract: Estimating the Generalization Error (GE) of Deep Neural Networks (DNNs) is an important task that often relies on availability of held-out data. The ability to better predict GE based on a single training set may yield overarching DNN design principles to reduce a reliance on trial-and-error, along with other performance assessment advantages. 
In search of a quantity relevant to GE, we investigate the Mutual Information (MI) between the input and final layer representations, using the infinite-width DNN limit to bound MI. An existing input compression-based GE bound is used to link MI and GE. To the best of our knowledge, this represents the first empirical study of this bound. In our attempt to empirically stress test the theoretical bound, we find that it is often tight for best-performing models. Furthermore, it detects randomization of training labels in many cases, reflects test-time perturbation robustness, and works well given only few training samples. These results are promising given that input compression is broadly applicable where MI can be estimated with confidence.

Published in Transactions on Machine Learning Research (12/2022)
Bounding generalization error with input compression: An empirical study with infinite-width networks
Angus Galloway1.2
gallowna@hroguelhh.co
Anna Golubeva
golubeva@miit edu
Mahmoud Salem 1.2
Mihai 5.2 5.2
nácaam@hooguipph.co
Yani Ioannou
yani, yomi, Donnkfoonnnou@@uuaggggggggoo
Graham W. Taylor
guetaylor@agguclphh
School of Engineering, University of Guelph, ON, Conada
2. Vector Institute for Artificial Intelligence, ON, Canada
3. The NSF Al Institute for Artificial Intelligence and Fundamental Interactions
4. Department of Plysics, Massachusetls Institute of Technology, MA, USA
5. Mathematics & Slatisfics, Universily of Guelph, ON, Canada
6. Schulich School of Engineering, University of Calgary, AB, Canada
7. Canada CIFAR AT Chair
Reviewed on OpenReview: https: // openreview. net/ ptt/ffrmm? id- JbZEUtULft
Abstract
Estimating the Generalization Error (GE) of Deep Neural Networks (DNNs) is an important task that often relies availability of held-out data. The ability better predict GE based on single training set may yield overarching DNN design principles to reduce reliance on trial-and-error, along with other performance assessment advantages. In search of a quantity relevant to GE, we investigate the Mutual Information (MI) between the input and final layer representations, using the infinite-width DNN limit to bound MI. An existing input compression-bast GE bound used link MI and GE. To the best of our knowledge, this represents the first empirical study of this bound. In our altempt empirically stress test the theoretical bound, find that it is often tight for best-performing models. Furthermore, it detects randomization of training labels in many cases, reflects test-time perturbation robustness, and works well given only few training samples. These results are promising given that input compression is broadly applicable where MI can be estimated with confidence.
1 Introduction
Generalization Error (GE) is the central quantity for the performance assessment of Deep Neural Networks (DNNs), which we operationalize as the difference between the train-set accuracy and the test-set accuracy Bounding a DNN's GE based i) Labeled data is often scarce, making it at times impractical to set aside representative test set. ii) The ability to predict generalization is expected to yield overarching design principles that may be used for Neural Architecture Search (NAS), reducing a reliance on trial-and-error. iii) Bounding the error rate is helpful for model comparison and essential for establishing performance guarantees for safety-critical applications.
training set is longstanding goal (Jiang al. 2021 for various reasons:
LGE also referred generalization gap. Note some use "generalization error" synonym for "test error".

---

Published in Transactions on Machine Learning Research (12/2022)
contrast, the test accuracy is merely single performance estimate based an arbitrary and finite set of examples. Furthermore, the adversarial ezamples phenomenon has revealed the striking inability of DNNs to generalize in the presence of luman--mperreepiibe perturbations (Szegedy et al. 2014 Biggio & Roli 2018), highlighting the need for a more specific measure of robust generalization.
Various proxies for DNN complexity which are assumed to be relevant to GF-such as network depth, width, by-norm bounds (Neyshabur et al. 2015], or number of parameters do not consistently predict generalization in practice (Zhang et al.) 2021). In search of an effective measure to capture the GE across range of tasks, we investigate the Mutual Information (MI) between the imput and final layer representations, evaluated solely on the training set. In particular, we empirically study the Input Compression Bound (ICB) introduced by [Tishby] 2017 Shwartz-Ziv et al.) 2019), linking MI and several GE metrics. An emphasis on inpul is an important distinction from many previously proposed GE bounds (e.g.. Zhou et al. (219))), which tend to be model-centric rather than data-centric.
We use infivile ensembles of wnfinile-width networks (Lee al. 2019) as in deterministic DNNs the MI quantity examine is ill-defined (Goldfeld et al.) 2019). Infinite-widee networks correspond to kernel regression and are simpler to analyze than finite- width DNNs, yet they exhibit double-descent and overfitting phenomena observed in Deep Learning (DL) (Belkin et al.) 2019). For these reasons, [elkin et al. (2018) suggested that understanding kernel learning should be the first step taken towards understanding generalizatio in DL. To
this end, we evaluate the ICB with respect to three criteria:
(1) First, we asess the extent to which the bound holds in practice. To do so, we evaluate the GE of a variety of models, composed by many different metaparameters of the neural architecture and training procedure. We then compare the GE to the thcoretical GE bound given by ICB. We show that ICB contains the GE at the expected frequency for four of five dalasets. We identify several factors that influence ICB success, including a training-labed randomization test inspired by Zhang et al. (2017).
(2) Next, we analyze whether the ICB is sufficiently small for useful model comparisons. If theoretical GE bound exceeds 100% in practice, it is said to be vacuous. As we study binary classification tasks, we additionally require that the bound be less than 50% for models with non-trivial GE. We show that ICB is often sufficiently close to the empirical GE, and thus presents a non-vacuous bound. These results are obtained with 2000 or fewer training samples.
(3) Last, we assess the ability of ICB to predict changes in GE under different metaparameter interventions. The ICB accurately predicts changes in GE as the training time, number of training samples, and explicit paramcter regularization vary; ICB was less consistent when the activation function, input data, and depth vary, depending on the dataset.
Beyond these three main desiderata for generalization bounds, we show advantages in reducing ICB even when the GE small. Reducing ICB on natural training labels prevents models from fitting random labels, and conversely, ICB increases when models are trained on random versus natural training labels (Zhang 2017 2021). Finally, show that TCB is predictive of test-time perturbation robustness (Goodfellow
et al.
et al.
2015 Gilmer et al. 2019). without assuming access to a differentiable model.
2 Background
We make use of an Eeoomnation-theoretieee motivated generalization bound, the ICB, to establish an overlooked link between MI and GE. The bound seems to have first appeared in a lecture series (see, e.g., Tishby (017 )) later in a pre-print (Shwartz-Ziv Ziv al. 2019 [Thm. 1] and more recently in a thesis (Shwartz-22
2021 Ch. 3). To the best of our knowledge the bound has not yet. been studied empirically.
2.1
Mutual information in infinite-width networks
The MI between two random variables X and Z is defined as
1(x;2)= Σp(a, 2) log p(5,2)
Ep(r,z) log p(2(0))
(1)
p(x)p(z)
p(=)
2,2
2

---

Published in Transactions on Machine Learning Research (12/2022)
where we used Bayes' rule to obtain the expression on the right and introduced Bpto,s)] to denote the average over z). In our case, X denotes the input, and Z the input representation which is taken the Neural Network (NN) output. Since the marginal p(z) is unknown, we use an unnormalized multi-sample "noise contrastive cstimation" " (InfoNCE) variational bound. The InfoNCE procedure was originally proposed for unsupervised representation learning (van den Oord et al. 2018), which also serves as a lower bound on MT (Poole et al. 2019). In van den Oord ct al. (2018), the density ratio ((z)z)/p(2) was learned by a NN. Instead, following Shwartz-Ziv & Alemi (2020), we use infinite ensembles of infinitely-wide NNs, which have conditional Gaussian predictive distribution: p(z[z) ~N (u(2, r), [(x, r)) with p. E given by the Neural Tangent Kernel (NTK) and Neural Network Gaussian Process (NNGP) kernel (Jacot et al. 2018). The predictive distribution also remains Gaussian following T steps of Gradient Descent (GD) on the Mean-Squared Error (MSE) loss. The conditional Gaussian structure given by NTK may be supplied in the InfoNCE procedure, yielding MI bounds free from variational parameters. Specifically, we use the "leave one out" upper bound (Poole et al.] 2019) on MI to conservatively bound MI:
log p(2z(1z))
I(X 2) S
LUB.
(2)
N
N-1 Σ, J P((
A lower bound on MI, /LB, of a similar form as Eq. (2) is also available (Eq. 6 Appendix A.2 We verified
that both bounds yield similar results for the training regime in which we apply them (Fig. A5.. See van den
Oord et al. (0018) and PPoole et al.] (2019) for formal derivations of Eq. 2 and
6 These MI bounds must.
be computed on the training set only to evaluate a generalization bound.
2.2 Input compression bound
Here, we provide an intuitive explanation of the ICB building on existing results and using information theory fundamentals (Cover & Thomas 1991). A more formal derivation including a proof can be found in Shwartz Ziv et al. bound, which plays central role in early mathematical descriptions of machine learning "Shalev-Swwarte. & DeviD 2014). Tt is assumed that a model receives sequence of examples x, each labeled with the value f(x) of a particular target function, and has to select a hypothesis that approximates f well from a certain class of possible functions. By relating the hypothessss-class cardinality [H] and the number of training examples Nun: one obtains the following bound on the GE:
A]. We begin with the conventional Probably Approximately Correct (PAC) GE
log log((H + log(1/5)
GE <
(3)
2Nmm
where the confidence parameter 8 E (0, 1) indicates the probability with which the bound holds w.r.t. the random training sample. The key term in this bound is the hypothesis-class cardinality, the expressive power of the chosen ansatz. For a finite H. it is simply the number of possible functions in this class; when H is infinite, a discretization procedure applied in order to obtain a finite set of functions. For NNs, |H] usually assumed to increase with the number of trainable paramcters. The bound (3) states that generalization is only possible when the expressivity is outweighed by the size of the training set, in line with the well-known bias-variance trade-off of statistical learning theory. Empirical evidence, however, demonstrates that this trade-off is qualitatively different in deep learning, where generalization tends to improve as the NN size increases even when the size of the training set is held constant. The key idea behind the ICB is to shift the focus from the hypothesis to the impul space. For instance, consider binary classification where each of the | inputs belongs to one of two classes. The approach that leads to bound (3) reasons that there are 2 X1 possible label assignments, only one of which is true, and hence a hypothesis space with 2| Boolean functions is required to guarantee that the correct labeling can be learned. The implicit assumptions made here are that all inputs are fully distinct and that all possible label assignments are equiprobable. These assumptions do not hold true in general, since classification fundamentally relies on similarity between inputs. However, the notion of similarity is data-specific and a priori unknown; thus, the uniformity assumption is required when deriving a general statement.
The approach behind ICB circumvents these difficulties altogether by applying information theory to the process of NN learning. First, note that solving a classification task involves finding suitable partition of the
3

---

Published in Transactions on Machine Learning Research (12/2022)
imput space by class membership. DNNs perform classification by creating representation Z for each imput X and progressively coarsening it towards the class label, which is commonly represented as an indicator vector. The coarsening procedure is an inherent property of the NN function, which is implicitly contained in Z. By construction, the NN implements a partitioning of the input space, which is adjusted in the course of training to reflect. the true class membership. In this sense, the cardinality of the hypothesis space reduces lo [H] 2 where [T] is the number of class-homogencous clusters that the NN distinguishes. To estimate (T), the notion of typicality is employed: Typical inputs have a Shannon entropy (X) that is roughly equal to the average entropy of the source distribution and consequently probability close to 2 _((),, Since the typical set has probability of nearly 1, we can estimate the size of the input space to be approximately equal to the size of the typical set, namely 2 Similarly, the average size of each partition is given by 2x(2)) An estimate for the number of clusters can then be obtained by [7] ~ 2d(()) /2 = 2((x:2),
yiclding hypothesis class cardinality [7[] ~ 22'(x12) With this, the final expression for the ICB is:
21(x2)) + log(1/0)
GEICB
(4)
2N
where it is assumed that X is a d-dimensional random variable that obeys an ergodic Markov Random Field (MRF) probability distribution, asymplotically d (common for signal and image data, see e.g., Murphy (2012) Ch. 19]). Unfortunately, it is impossible to check this assumption directly because it involves the data-generating process, which we can not access based on finitcly many samples (i.c., the training sct). We therefore treat ICB as tool, and empirically test how useful this tool is in practice. We comment on the ergodic MRF assumption in Appendix A.I, We only evaluate ICB when we can obtain confident estimate of I(X; Z). For this we require a tight sandwich bound on [(X;)) with /UB R LLB. We discard samples where [XB(X; Z) > log(NNuu), since IL (X; Z) cannot exceed log(NNruu). See Fig. AB for typical JUB, LB values during training and samples to discard. Note that the units for T(X; Z) in ICB are bils.
3 Experiments
Our experiments are structured around three main questions: 1) To what extent does ICB bound GE in practice ($4.1), including for random labels ($4.2?
? 2) Is the ICB close enough to the empirical GE to be useful for model comparisons ($1.) ? 3) To what extent does ICB predict GE with respect to different
metaparameter interventions
(4.4
We focus on binary classification like much of the generalization literature, which also enables us to more efficiently evaluate MI bounds by processing kernel matrices that scale by N2 rather than (k x Num))² for k classes. Aside from this computational advantage, our methodology extends to the multi-class setting. We conduct experiments with five standard datasets: MNIST (LeCun & Cortes 1998), FashiSNMNIST (Xiao et al. 2017), SVHN (Netzer et al.) 2011), CIFAR-10 (Krizhevsky) 2009), and EuroSAT (Helber et al., 2018 2019 These datasets are intended to be representative of low to moderate complexity tasks and make it tractable to train thousands of models (Jiang* et al., 2019). Experiments with EuroSAT further demonstrate how the method scales to 64-by-64 pixel images. For each of the image datasets, we devise nine binary classification "tasks" corresponding to labels "i versus + 1" for E {O.....,8) 83. This sequential class ordering ensures each label is used once, and is otherwise an arbitrary choice.
We use melaparameters that are common to deep learning, with the exception of "diagonal regularization" ", which specific to the NTK, denoted by K. The regularized NTK defined as: Kreg = K. X Tr(K) Nuw I, where À is a coefficient that controls the amount of regularization. This is analogous to l regularization of finite-width DNNs, only we penalize the parameters' distance w.r.t. their initial values instead of w.r.t. the origin (Lee et al. 2020 We train population of models by selecting metaparameters
follows: the total f1, 11, 4,55, diagonal regularization cocfficients À E (10", 10-1, 10-2 10-2,10-3, 9,10-4,, and For fully-connected Multi-Layer Perceptron (MLP) models we select the number of training samples, Nurn E {1000, 1250, 1500, 1750, 2000), whereas for Convolutional Neural Networks (CNNs) we use Num E {1000, 1500) for computational reasons. Test sets have constant Nost = 2000. We do not vary the learning rate or bini-batch size, as the widhh networks are trained by full-batch GD, for which the training dynamics do not depend on the learning rate once below critical
number of layers D D
aclivation functions o6-) E (eeLU()),Er(())
4

---

Published in Transactions on Machine Learning Research (12/2022)
a)
b)
80
Accuracy (%)
10
15
19
60
23
38
Train
Noisy
40
A
0.1
50
0.5
A
Test
ICB
10
10
10a
100
104
10
100
101
10
Training step
Figure 1: The ICB may reflect robust GE when it is loose w.r.t. standard GE. The ICB is plotted grey shaded band underneath the training accuracy indicating the range of lest accuracy compatible with the theoretical bound. Performance metrics are evaluated for a EuroSAT Pasture versus Sea-Lake binary classification task using 500 training samples and 2000 test samples and different regularization levels in (c)- At low regularization À = 0.1 (a), the ICB is vacuous with respect to standard generalization beyond 10a training steps, but reflects the poor robust generalization for the "Noisy" test set with AWGN. Increasing the regularization À 0.5 (b) and
1.0 (c) reduces ICB and the AWGN GE. Arrows indicate the steady-state AWGN GE (black), and ICB (grey) along with their respective values. See Fig. A5 for the corresponding upper and lower T(X; Z) bounds for this experiment.
stable value (Lee et al. 2019). A nominal learning rate of 1.0 used in all cases and found to be sufficient Models were evaluated at five different training times, / E {10², 10 10 10 100), which contained most of the variation in GE. Training for less than t = 102 steps typically resulted in small GE, as both training and test accuracy were near random chance or increasing in lockstep. In terms of steady-state behaviour, GE was often stable beyond t = 1 Furthermore, = 10 was found to be a critical time beyond which (UB(X; Z) sometimes exceeded its upper confidence limit of (og(Nm)) particularly for small values where memorization (lack of compression) is possible. In total, there are 1250 unique metaparameter combinations for MLPs: (D) (A) (Ø) (Nm.) x 5 (1) 1250, and 500 for CNNs.
We measure correlations between 1CB and standard GE, well as robust GE. The latter is defined the accuracy difference on the standard train set and the test set with Additive White Gaussian Noise (AWGN) (Gilmer el al.] 2019). It can be shown that classifier's error rate for a test set corrupted by AWGN determines the mean distance to the decision boundary for linear models (Fawzi et al. 2016) and serves as a useful guide for DNNs (Gilmer al. 2019). For the AWGN we use Gaussian variance x² 1/16 for EuroSAT and x² 1/4 for the other datasets.
4 Results
Illustrative example Before presenting the main results, examine ICB for a EuroSAT classification task using only 500 training samples (Fig, D.. This is a challenging task, as tight MI and GE bounds are difficult. to obtain for high-dimensional DNNs, particularly with few samples. For example, in (Dziugaite & Roy
2017) 55000 samples were used to obtain a s 20% GE bound for finite-width DNNs evaluated on MNIST.
We evaluate ICB throughout training from the first training step (t 10") until steady state when all accuracies stabilize (1 10%). Shortly after model initialization (t 10 to / 104) the ICB is 7% (indicated by the height of the shaded region in Fig. [ and the training and test accuracy both at 50% (GE= 0). Here, ICB is non-vacuous, but also not necessarily interesting for this mandom-uuessing phase. ICB increases as training is prolonged
3 At low regularization (Fig. a), the ICB ultimately becomes vacuous (ICB x 50%) around 1 steps. However, althongh ICB is vacuous with respoct to standard generalization in
2This was the default setting for the neural, taarggntttnggtteeett software library Novak al. 2020
Tt, may be obvious that ICB increases monotonically with training steps training accuracy increases.
5

---

Published in Transactions on Machine Learning Research (12/2022)
Fashion (CNN)
SVHN (CNN)
CIFAR (CNN)
EuroSAT (MLP)
Generalization error
100.0% 0% 4N-4232)
95 (N-3914)
80.5% 5% 4148
93.0% (N-9663)
0.6
v
0.14
3
4s
v.v
0.2
6
v
8 vs
0.0
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Theoretical generalization error bound
The ICB often bounds GE for most datascts. The ICB ("Thcorctical gencralization error bound") is plotted versus GE (MSE) for four datasets. The ICB satisfaction rate is annolated in the top left corner of each plot with format "Sat. % (N)", where N denotes the number of valid experiments. Fach binary classification task is assigned a unique colour. See Fig. A6 for equivalent plot using the 0 1 loss.
Figure 2:
Table 1: Overall 1CB satisfaction rate for two different loss functions, with the number of valid experiments (N) in brackets. The MNIST and FashionMNIST datasets were both at 100% and omitled for brevily.
Loss
SVHN (CNN)
CIFAR (CNN)
EuroSAT (MLP)
Square
95.2% (3914)
80.5% (4148)
93.0% (9637)
0 1
67.6% (3914)
84.9% (4148)
95.7% (9637)
a), it reflects well the poor robust generalization when tested with AWGN (Gilmer et al. 2019). Increasing the regularization coefficient À reduces ICB from 50% (a) to 23% (b) and 15% (c), and the robust GE from 38% (a) to 19% (b) and 10% (c). Both standard and robust GE are bounded at all times by ICB. The latter is, however, a coincidence, as the robust GE is subject to the arbitrary AWGN noise variance (a² = 1/16). The additive noise variance could be increased to increase the robust GE beyond the range bounded by ICB. More important than bounding the robust GE absolute percentage that ICB captures the trend of robust gencralization. Evaluating robustness effectively is error-prone and often assumes access to test data and a differentiable model (Athalye et. al.) 2018 Carlini et al., 2019). We make no such assumptions here. The lack of robustness in Fig. a) would have likely gone unnoticed. Next, we assess the extent to which ICB contains GEs evaluated variety of models and datasets.
4.1 Bounding generalization error
We refer to the percentage of cases where GE < ICB as the "ICB satisfaction rale", or "Sat." in plots. We expect ze 95% of samples to satisfy this property as ICB evaluated at 95% confidence (8 = 0.05). We consider other 8 values in $A.4 Overall ICB satisfaction rates are listed in Table [ for two loss functions, and the ICB is plotted versus GE in Fig. 2 for the square loss. In general, 1CB was satisfied at high rate depending on the dataset. Next, identify factors affecting the ICB satisfaction rate.
Best-performing models with test accuracy 2 70% attain an ICB satisfaction rate of 94.7% (N = 792) for SVHN and 0 1 loss. An 80% threshold for CIFAR led 94.0% (N = 1438) of samples to satisfy ICB.
Architecture type has a significant effect on 1CB satisfaction rate: CNNs had an 11-14% greater ICB satisfaction rate than MI.Ps for CIFAR, and 10-18% greater rate for SVHN, where the range depended on the loss function. Intriguingly, the superior ICB satisfaction rate of CNNs was not due to greater test-set. accuracy. CNNs had lower GE as result of their lower Irain-set accuracy (Table A5

---

Published in Transactions on Machine Learning Research (12/2022)
MNIST (MLP)
Fashion (CNN)
SVHN (CNN)
CIFAR-10 10 (CNN)
EuroSAT (MLP)
Training accuracy (%)
100
co 000000
oo
80
Random
60
0.96
0.97
1.00
0.97
0.97
10
20
25
50
25
50
25
50
25
50
ICB evaluated natural training labels
Figure 3: The ICB often distinguishes between natural and randomized training sets. Training accuracy for "Natural" and "Random" labels is plotted versus the thcoretical GE bound (ICB), which is evaluated on the natural labels. Each data point corresponds a unique regularization value X, which influences the ICB value. We show the "0 vs. 1" task for all datasets, except CIFAR, for which the "7 8 task performed best (Table 2.. Considerable separation between natural and randomly labeled sets is observed for all datasets. ICB is highly correlated with ability to fit random labels in all cases as shown by t values. The broken vertical line for EuroSAT indicates the ICB value for which there is at least a 10% accuracy difference between natural versus random sets.
Table 2: Ability of ICB to separate natural versus random training labels is a good predictor of ICB satisfaction rate by task. The row "ICBrand " indicates the minimum ICB value for which a X% accuracy difference between natural and random labels is observed. The "Sat. (%)" column showing the ICB satisfaction rate is taken from $1.1 Exp. A. The column 7 indicates the rank correlation between ICBaand @ and Sat. (%) over the nine tasks. Columns sorted by ascending order of ICBrand @X%
Task
2/3
6/7
3/4
7/8
7
4/5
5/6
0/1
1/2
8/9
Eu
Sat. %
84
98
100
100
100
100
100
100
т 0.76
ICB ICBrand @10%
7.5
10.0
11.1
13.2
18.5
21.6
41.6
47.9
51.2
Task
2/3
3/4
5/6
4/5
6/7
0/1
1/2
8/9
7/8
CIFAR-10
Sat. %
54
54
62
56
84
85
92
89
100
T = 0.87
ICB 05%
7.4
9.4
11.8
12.1
12.5
12.6
14.8
15.2
17.8
Training time GE generally increases with training, therefore the overall ICB satisfaction rate may be biased upward by the inclusion of models trained for a short time (e.g. t= 102). Selecting models trained for at least = 104 steps, resulted in an ICB satisfaction rate decrease for CIFAR-10 10 trained CNNs from 84.9% overall to 76.3% (N = 2351), and a slight increase for SVHN from 67.6% overall to 70.5% (N = 2114). Expressing GE in terms of MSE, ICB saturation rate fell from 95.2% overall to 91.3% (N 2114).
The number of training samples impacted the ICB satisfaction rate for the 0 loss on SVHN (Fig. A7).
Inter-task differences in ICB satisfaction rate were observed (Table A6). For EuroSAT, six of nine tasks always satisfied ICB, and three tasks reduced the overall average. The satisfaction rate was 82.2% (N 1123) for the "2 vs. 3" task and 83.5% (N 1154) for the "6 vs. 7" task. For CIFAR-10, tasks "2 vs. 3" through "5 vs. 6" had ICB satisfaction rates considerably worse than the rest by a margin of 15 20%, and for SVHN, tasks "2 vs. 3", "5 vs. 6", and "8 vs. 9" were poor performing. These inter-task trends were consistent for the CNN and MLP architoctures.
4.2 The randomization test
Zhang et al. (2017 2021 proposed the "randomization test" after observing that DNNs easily random labels. They argued that genoralization bounds ought be able to distinguish models trained on natural versus random training labels, since generalization is by construction made impossible in the latter case. Motivated by the work of Zhang al.] first. hold all metaparameters constant and report. TCB values
7

---

Published in Transactions on Machine Learning Research (12/2022)
before and after randomizing the training labels (Table 3 longer fit, mandom training labels, while still permitting them to fit the natural training labels (Table 2 Fig. 3 We consider only two-layer ReLU networks here, and consistent with $4.1 we use the CNN architecture for Fashi MashionMISTT, SVHN & CIFAR and an MLP for MNIST & EuroSAT. We train these models to = oo on the natural training set (Nmm = 1000). Surprisingly, ICBUB approximates the GE well even when the model is trained on random labels (Table 3). For X = 0.1, ICBuB = 15.5% compared to a GE of 21.3%. Next, for À 0.01, ICBUB- = 38.5% and GE is 39.7%. Last, for log((Nuraia) = 6.91 nats, therefore the corresponding ICBUB of 197.6% should be discarded. In this case, substituting the "optimistic" lower estimate ICBLB = 54.1% & GE = 50%.
We then regularized models until they could
0.001, IUB 8.96, which is greater than
We expect 2) to be smaller after train- ing on natural labels, since training on ran- dom labels requires memorization of random data, i..., the opposite of compression. Im- portantly, to isolate the effect of the training label type, the training accuracy must be controlled, as higher accuracy generally re- quires greater complexity and thus larger T(x; 7). This intuition is consistent with the results of T as both LLB and LUB in- crease monotonically with the training accu- racy for both training label types. Training with À 0.001 allows models to perfectly fit both natural and randomized training sets (Table 3 rows with "Train" = 100%) and presents a suitable setting for evaluat- ing the sensitivity of ICB to the training label type. Indeed, J. greater for ran- dom labels (6.37 vs. 5.78 nats), resulting in incrcase of the optimistic thcoretical GE bound, ICBI.R, from 40.5% to 54.1%. The more pessimistic ICBUB increases even more dramatically from 90.4% to 197.6%, which is beyond the valid range of GE (0- - 100%).
Table 3: ICB increases after training on random labels. Randomization lest results for EuroSAT. The lower and up- per MI bounds, ILB and IUB, are included for comparison against log(Nern ~ 6.91 nats. Columns ICB, and ICBuB refer to whether LLB or JUB is taken as [(X; Z) estimate, re- spectively. Columns "Train" " and "Test" show the respective accuracy in %. 1CB values are larger for random labels when comparing rows with "Train" 100.0.
Natural training labels
LB
JUB
ICBLB
ICBuB
Train
Test
GE
10
4.87
5.37
26.0
33.1
97.9
98.7
-0.8
10 2
5.40
6.58
33.7
60.2
99.5
98.6
0.9
10-3
5.78
7.40
40.5
90.4
100.0
97.5
2.5
Random training labels
10-1
3.68
3.75
15.0
15.5
71.3
50.0
21.3
10
5.28
5.67
31.7
38.5
89.7
50.0
39.7
10
6.37
8.96
54.1
197.6
100.0
50.0
50.0
The randomization test identifies tasks with low ICB satisfaction Rocall from $4.1 that three binary classification tasks reduced the ICB satisfaction rate below 100% for EuroSAT: "2 vs. 3" (Sat. 82%), "6 vs. 7" (Sat. 84%), and "3 vs. 4" (Sat. 98%). We observed that these were the same tasks for which ICB performed poorly on the randomization test. Specifically, we measured the minimum ICB value for which an at least 10% accuracy difference was recorded between the natural and random training sets (vertical broken line in Fig. 3) when training with 20 different regularization ion values in the range 10-4 to 10a. The "2 vs. 3" task required the smallest ICB value (7.5%) before this accuracy difference was reached between the two label types. The "6 vs. 7" task had the next highest ICB value of 10.0%, followed by "3 vs. 4" with 11.1%. The other six lasks with 100% ICB satisfaction had strictly greater ICB values (Table Z Similar results are observed for CIFAR-10 using smaller 5% threshold as accuracies for natural and random labels were closer than for EuroSAT. The tasks with minimum (*2 vs. 3") and maximum (*7 vs. 8") satisfaction rate are the same tasks with the minimum and maximum @59aan05%% Therefore, the training-sct based randomization test. which only required training a single model here were-may be used to help identify when ICB performs well as a GE bound for a variety of models.
4.3 Vacuous or non-vacuous?
To evaluate whether ICB close enough to GE aid model comparison, we cxamined the model with the greatest accuracy on the test set with AWGN for each SVHN and CIFAR task. We used AWGN accuracy rather than standard test accuracy to select these models given the observation from Figure 1 that ICB may be more
8

---

Published in Transactions on Machine Learning Research (12/2022)
Table 4: The ICB close enough to the GE for model comparison. For five SVHN and CIFAR classification tasks (beginning with even numbers), we select the model with maximum accuracy on the test set with AWGN, shown in the "Robust" column. ICB compared to the standard GE as well as the Robust GE ("RGE" column). High train-set accuracy ("Train" 99%) tends to coincide with large RGE and ICB values, making ICB loose w.r.t. GE. Otherwise, ICB is consistently close to GE (compare values in bold).
CIFAR
SVHN
Task
Train
Test
Robust
GE
RGE
ICB
Train
Test
Robust
GE
RGE
ICB
0/1
96
86
83
10
12
13
87
79
68
8
19
15
2/3
93
74
71
18
21
25
100
85
67
15
32
46
4/5
99
77
73
22
26
52
100
88
70
12
29
67
6/7
93
85
83
8
10
12
90
78
70
12
20
15
8/9
80
80
5
99
23
33
62
1.00
395
Sign-error
4545
366
0.75
0.50
360
325
19
0.25
20327
204
41
26
122
0.00
activation
dataset
time
diagonal
depth
0/1
1/2
2/3
3/4
5/6
6/7
7/8
8/9
(a) FashionMNIST
94
127
88
250285
Sign-error
60
0.75
0,50
24
10
517613 517613606 60460000
289301.30229001
0.00
activation
train samples
time
diagonal
depth
2/3
3/4
4/5
5/6
6/7
7/8
(b)
CIFAR-10
Figure 4: The ability of ICB to predict GE varies for different metaparameters. Plots show prediction Sign-Errors (SEs) (where lower is better) for robust GE with AWGN for six different metaparameter interventions nine binary classification tasks (0 vs. 1, 1 vs. ,, 8 CIFAR-10. Numbers above the SE for even-numbered tasks indicate the number of samples N comprising the respective SE measurement. The train samples category had insufficient. N for FashionMNIST and was therefore replaced with a dataset category in a). which examines the effect of switching the dataset from FashionMNIST to CIFAR-10. The dataset category is omitted in bb) as SE is symmetric. Note that mean SE is equal to max SE for the activation metaparameter which had only one combination (ReLU versus Erf). See Table A7 for a detailed example showing how column computed in these plots.
9} for a FashionMNIST and [b
aligned with robusl GE (also see Fig. AB The most accurate models on the standard lest set often recorded zero enror on the training set and thus incurred large ICB values. Here, ICB values were considerably less than 50% in all cases except where training accuracy was 99% greater (Table 4.. Furthermore, ICB values were often close the empirical GE, e.g., an ICB of 7% was obtained for GE 5% for the CIFAR task 8/9 using only 1500 training samples (Table

---

Published in Transactions on Machine Learning Research (12/2022)
4.4 Effect of metaparameters theoretical bound
The goal of this section is to assess the ability of TCB to robustly rank GFs for a variety of models trained by different metaparameters. We perform coupled-network experiments as per Dziugaite et al. (2020) to assess the ability of ICB to predict whether GE increases or decreases for all metaparameter combinations when manipulating one held-out metaparameter at a time. Ranking is assessed in terms of Sign-Error (SE):
SE(P",CCB)
GF (w)) sgn (ICB ICB (w)) E (w.w [1 -sgn (GE (w/) 2
(5)
The SE (Eq. 5 is evaluated with respect to different assignments of the metaparameters, w and w', which are said to be drawn from a distribution ps induced by environment e, and differ in only one metaparameter value at a time. Note that in Dziugaite et al. the expectation in Eq. (5) is taken over randomly initialized finite DNN parameters and SGD mini-batch ordering. Conversely, infinite-ensembles trained by GD are deterministie. Therefore, the expectation in Eq. 5 is with respect to the choice of metaparameters and random training sample only.
We include three metaparameters that were not present in the work of Dziugaite et all the diagonal regularization, training time, and activation function. We omit width, learning rate, and batch size, they do not apply our setting. We report the mean SE over all possible interventions to each metaparameter in Fig. 4 The maximum or "max" sign-error advocated by Dziugaite et al. is discussed in text, as it was subject to greater noise than mean SE due to the smaller sample size To calculate the mcan SE for the "depth" metaparameter, for example, which has a range of 1 to 5, we evaluate the SE arising from changing the depth from to 2, again for 1 to 3, and so on for all ten combinations. The SE is then averaged across the ten "before" and "after" configurations, whereas the max SE refers to the one combination with the greatest SE, e.g., changing the depth from 4 5. We discard samples with a Hoeffding weight less than 0.5 as per DDiugaite al. indicating that GE difference is too small relative to the number of train-set and test-set samples to reliably measure changes in the true error rate (i.e., on the underlying data- gentaategg process) We discard cases with N < 10 for the max SE, whereas we compute sample-weightes average for the mean SE based on all cases, Few measurements of the standard GE satisfied the Hoeffding threshold for FashionMNIST, therefore we added AWGN to the test set to increase the typical GE and number of valid cases to analyze. We repeat our analysis for standard GE for CIFAR-10 in Fig. Ag and contrast it with the AWGN case.
The diagonal regularization was the most consistent metaparameter, with zero max SE for all tasks and datasets. Intervening on the training time consistently led to small mean and max SE, as well as for the number of train samples for the majority of tasks (Fig. - The time metaparameter had a max SE of 0.45 for the 6/7 FashionMNIST task consistent with the peak mean SE for task 6/7 in Fig. 4a and five tasks had a max SE of zero. For CIFAR-10, max SE w.r.t. time was 0.27, with five tasks having max SE- < 0.02. The max SE. for train samples was 0.89 (N = =19 for task 5/6, which was followed by 0.14 (N- 44) for task 4/5, Other tasks either had zero max SE or insufficient data. Note that these CIFAR-10 tasks 4/5 and 5/6 also had adverse performance for the randomization test. (Table 2 In summary, the three metaparameters: diagonal, time, and train samples strongly influence overall correlation between ICB and GE.
Manipulating the activation function and depth resulted in a greater discrepancy between FashionMNISS and CIFAR-10. For these metaparameters 1CB was considerably more predictive for the former dataset resulting in lower SE. For example, for the depth metaparameter the max SE for FashionMNISH was 0.23 followed by 0.06, compared to 1.0 for CIFAR-10. Results for EuroSAT were closer to onMISS than CIFAR-10 and may be found in Fig. ATO.
We the term "max SE" rather than "robust SE" from Daiugaite al. to avoid confusion with the "robust GE". The latter is evaluated
test set with AWGN and is different coucept from the former. Recall from the Introduction that merely operationakzed GE as the difference between train-sct accuracy and the test-sct accuracy. In contrast, the GE is formally defined the difference between train-set accuracy and the true accuracy (or error); test-set, accuracy is an approximation for the latter, which we account for with this step.
10

---

Published in Transactions on Machine Learning Research (12/2022)
5 Discussion
Our results show that the ICB serves as a non-vacuous generalization bound, which we verified in the case of infinite-width networks. Furthermore, we performed a broader evaluation than is typically considered for theoretical GE bounds: i) We searched for 1CB violations by evaluating ICB throughout training, rather than at specific number of epochs or training loss value. ii) We varied the number of training samples and classification labels, compared to a static train/test test split. iii) We considered robust GE in addition to standard GF. iv) Experiments were performed on five datasets.
ICB was satisfied at around the 95% rate for four of five datasets when GE was expressed in terms of MSE, or three of five when GE was expressed in terms of accuracy. perfformin models with at least 70- 80% test accuracy consistently satisfied ICB for all datasets, which is encouraging, since accurate models are more likely to be deployed. The SVHN dataset had the lowest ICB satisfaction rate among all cases for the 0 1 loss, however, this may have been impacted by too few training examples. Furthermore, we identified that the training label randomization test may detect specific tasks with low ICB satisfaction rate; ensuring ICB yiclds diffcrent results for natural and randomized training labels may greatly improve results. CNNs had superior performance compared to MLPs. Although the MRF assumption does not appear to be necessary lo derive ICB, the success of CNNs in comparison to MLPs may be related to the MRF assumption and 2D images having only local correlations, compared to their flattened counterparts used with MLPs (see $A.I).
The ICB was able to successfully predict changes in robust GE when the digonal regularization, training time, and number of training samples varied. ICB was less successful when the depth and activation function varied for CIFAR-10, yet performed well for FashionMNIST as well as for EuroSAT. The precise NTK limit we consider is generally assumed to only hold for shallow models, which may explain some of the failure cases for the depth metaparameter (Li et al., 2021). It also worth considering to what extent a generalization bound ought to be able to rank GEs, given that it by definition mercly an upper bound on the error. For example, GEs of 1% and 29% are both compatible with bound of 30%, which would contribute to poor GE prediction an absolute scale.
Relevance to deep learning One should use caution before extrapolating our conclusions based on infinite- width networks to finile-width DNNs. The ability of infinit-width networks to approximate their finite-width counterparts is reduced with increasing training samples (Lee et al.) 2019p, regularization (Lee et al. 2020), and depth (Li et al., (021). Nevertheless, the infinite-width framework has allowed us to demonstrate the practical relevance of the ICB for an exciting family of models as a first step. It has been argued that understanding generalization for shallow kernel learning models is essential to understand generalization behaviour of deep networks. Kernel learning and DL share the ability to exactly fit their training sets yet still generalize well, phenomenon that other bounds fail to explain (Belkin et al. 2018). We leave the study of ICB for finite-width DNNs to future work, which may require alternative MI estimation techniques.
6 Related Work
Kernel-regression generalization error Canatar et al. (2021b) derived an analytical expression for the generalization MSE of kernel regression models using replica method from statistical mechanics. Their predictions show excellent agreement with the empirical GE of NTK models on MNIST and CIFAR datasets as a function of the training sample size. Furthermore, their method is sensitive to differences in difficulty between similar classification tasks, e.g., showing that MNIST "0 vs. 1" digit classification is casier to learn than "8 vs. 9". Canatar al. (2021a) extend the method predict out-of-distribution GE. An alternative Ceave--One-ne (LOO) error estimator (Lachenbruch 1967). LOO is generally impractical
method is the for DL due to the computational requirement of training N DNNs N different training sets. However, Bachmann et al. (2022) proposed a closed-form LOO estimator based on a kernel regression model trained on the complete training set once. Their estimator shows excellent agreement with Lest MSE and accuracy for a five-layer ReLU NTK model trained on MNIST and CIFAR. While Bachmann et al.) averaged results over five training sets of size 500- 20000, we only draw a single training set of 250- 2000 samples for each set of metaparameters. Our choice was made to reflect a practical "small data" scenario, where GE has to be bounded using modest set of labeled data. As result, however, our GF and ICB estimates have
11

---

Published in Transactions on Machine Learning Research (12/2022)
greater variance than those of Bachmann et al. We used the infinite-width DNN limit for convenience and as first step to assess the efficacy of TCB; we did not set out to find optimal generalization bounds for kernel regression. An advantage of ICB is that it only requires access to (X; 2)- a black- box statistic applicable to a wide varicty of models beyond kernel regression. Thorefore, ICB may become increasingly relevant for DLs using MI estimators with different strengths and assumptions, e.g., with distributional constraints on weight. matrices [Gabrié et al. 2018) or infinite-depth corrections (Li et al. 2 p.
Generalization bounds for deep learning Dziugaite & Roy (0117) develop PAC-Bayes GE bound
and evaluated it a MNIST binary classification task using the complete training set (Niraan 55 k) and fully-connected NN with 2-3 layers and ReLU activations. Although their bound was non-vacuous (= 20%), it was several times larger than the error estimated on held-out data (< 1%). A comparison with our work is difficult, as we did not use finite-width DNNs. We showed that the ICB yields a smaller (<e 10%) bound from less than 2000 samples for several classification tasks. Zhou et al. (2019) proposed a PAC-Bayes generalization bound based on the compressod size of DNN after pruning and quantization. They obtain a GE bound of 46% for MNIST and 96 98% for ImageNet. The measure of compression used by Zhou el. al. (2019) is distinct from input compression in terms of MI here. The bounds of Dziugaate & Roy and Zhou et al. concern model complexity, whercas ICB is based on data compression by the hidden layers. Both Dziugaite & Roy and Zhou et al. optimized their bounds for best results, whereas we used standard training procedures.
Generalization bounds from unlabeled data GE bounds or estimates may be obtained without directly estimating model complexity. Garg et al. (2021) leverage the so-called "early learning" phenomenon, whereby DNNs fit true labels before noisy labels, to develop a post-hoc GE bound. They validate their bound NTK-based wide DNNs, CNNs, and LSTMs. In contrast to our work, the Garg et al.] bound requires additional unlabeled data, that in practice, can be carved out from the training set. They assign random labels to the carved-out set, and augment the training set with this random data. Their bound is based on the empirical error computed on both the clean and random set. Empirically, Garg et al. (2021) show that it may be possible to maintain model accuracy when training on partially randomized labels in some scttings by using weight decaa or early slopping. Unfortunately, random labels reduce the lask signal-Lo-noise ratio, ((X;)), and may be challenging to apply with unregularized models that nonetheless generalize well (Zhang ct al. 2017p. Jiang et al.] (2022 observed that the disagreement of separately trained DNNs on unlabeled held-out datasets is similar to the disagreement of those models a labeled held-out set. Their claim follows an empirical observation that deep ensembles are often well-calibrated. however, this calibration property may not always hold in important settings (Kirsch & Gal 2022).
Information compression and generalization The MI I(S) w) between the training data S= = (z, y) supplied as input to a stochastic learning algorithm and the weights w it outputs can also serve to bound GE (Xu) & Raginsky 2017 Achille & Soatto 2018). Decomposing I(S; w) into I(w; + / (w; y y|ar), Haautyunyan et al. (2020) show that reducing the second term- the information w contain about the labels y beyond what can be inferred from x x-is key to avoid unintended memorization. As result, these works optimize MI bounds, whereas we soek to measure MI to evaluate GE bound. Furthermore, Shwartz-Ziv & Alemi (2020) Appendix C.7] evaluated [(; w) for infinite-width networks and found that it tends to infinity as the training time goes to infinity. Thus, a GE bound based on [(S) w) is vacuous for these networks which nevertheless generalize well. (axe et al. (0188) observed a lack of compression in ReLU networks and argued that compression must be unrclated to generalization in DNNs, since it is known that ReLU networks generalize well. However, their binning procedure based on Paninski (2003) involves metaparameters that influence entropy and MT estimation. Other works have studied input compression in linear regression (Chechik et al.) 2005) and finito-width ReLU DNNs using adaptive binning estimators (Chelombicv ct al. 2019). We use MI bounds free from such metaparameters and observe imput compression regardless of the nonlinearity type, consistent with Shwartz-Ziv & Alemi (2020). We are excited about future work on input compression phenomena and the challenging case of finite-width DNNs.
12

---

Published in Transactions on Machine Learning Research (12/2022)
7 Conclusion
We assessed the ICB along three performance axes: tightness, percentage of trials satisfying the bound, and correlation with GE. Empirical results show that input compression serves as simple and effective generalization bound, complementing previous theory. Additionally, ICB can help pinpoint interesting failures of robust generalization that go undetected by standard generalization metrics. An important consequence of the ICB with respect to NAS is that bigger is not necessarily better, at least in terms of the information complexity of infinite-width networks. Equally important the architecture are the melaparameters and training duration, all of which affect input compression. Consistent with Occam's razor, less information complexity or more input compression yields more performant models, reducing the upper bound on generalization error. We conclude that imput compression, which is data-centric, is more effective complexity metric than model-centric proxies like the number of parameters or depth.
Author Contributions
Angus Galloway devised the study and wrote the first draft in consultation with all co-authors. Anna Golubeva critically revised the entire manuscript and made considerable contributions to the theoretical background. Mahmoud Salem provided experiment support with adversarial attacks in the JAX framework, and characterizing the finite to infinite-width NN correspondence. These experiments informed the final scope of the study and addressed alternate hypotheses. Mihai Nica, Yani loannou, and Graham W. Taylor provided technical advice and revisod the manuscript. All authors consented to submission of this work to TMLR.
Acknowledgments
This research was developed with funding from the Defense Advanced Research Projects Agency (DARPA). The views, opinions and/or findings expressed are those of the author and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. Graham W. Taylor and Angus Galloway also acknowledge support from CIFAR and the Canada Foundation for Innovation. Angus Galloway also acknowledges supervision by Medhat Moussa. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institule: http://wwe www.vveeeetituutiiee.. http:://ww..eecoorintttttissses att.ettttttttttaataeeeeeeeeeee /ttaaarteeers Anna Golubeva is supported by the National Science Foundation under Cooperative Agreement PHY 2019966 (The NSF AI Institute for Artificial Intelligence and Fundamental Interactions, http://laiff.. org/) Mihai
Nica is supported by an NSERC Discovery Grant.
References
Alessandro Achille and Stefano Soatto. Emergence of Invariance and Disentanglement in Deep Representations, Journal of Machine Learning Research, 19(50):1-34, 2018. 12
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated Gradients Give a False Sense of Security: Circum- venting Defenses to Adversarial Examples. International Conference on Machine Learning, pp. 274-283, 2018.
G
Gregor Bachmann, Thomas Hofmann, and Aurelien Lucchi. Generalization Through the Lens of Leave- Onavve-nee-utt Error. In International Conference on Learning Representations, 2022.
12
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To Understand Deep Learning We Need to Understand Kernel Learning. In Proceedings of the 35th International Conference on Machine Learning, pp- 541 5499. PMLR, 2018. 2
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- practice and the classical varianeee trade-off. Proceedings of the National Academy of Sciences, 158439) 2019. doi: 10.1073/ 19030000
2
Battista Biggio and Fabio Roli. Wild patterus: Ten years after the rise of adversarial machine learning. In Proceedings of the 2018 ACM SIGSAC Conference on Compuler and Communications Security, CCS '18 pp. 2154 2156, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 777--145508-663.4 doi: 10. 00.1145//2443331322646
13

---

Published in Transactions on Machine Learning Research (12/2022)
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Out-of-distribution generalization in kernel regression. In Advances in Nearul Information Processing Systems, volume 34, pp. 12600-12612. Curran Associates, Iuc., 2021a.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral Bias and Task-Model Aligument Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks. Nature Communications, 12(1):2914,
2021b. ISSN 2041-1723. doi: 10. 10.1038/s41 1000///1146-0001-22353 467-021-2310--1
11
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, lan Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv preprint or Xiv: 06705, 2019. B
Gal Chechik, Amir Globerson, Naftali Tishby, and Yair Weiss, Information Bottleneck for Gaussian Variables, Journal of Machine Learring Research, 6(Jam):165-1m) 188, 2005. 12
Ivan Chelombiev, Conor Houghton, and Cian O'Donnell. Adaptive Estimators Show Information Compression in Deep Neural Networks. In International Conference on Learning Representations, 2019. 12
Thomas M Cover and Joy Thomas. Elements of Information Theory. John Wiley & Sons, Inc., New York, 1991. 3
Gintare Karolina Dziugaite and Daniel M. Roy. Computing Nonvacuous Generalization Bounds for Deep (Stochastic)
Neural Networks with Many More Parameters than Training Data. Uncertainty in Artificial Intelligence (UAT),
2017.
5 12
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Toannis Mitliagkas, and Daniel M Roy. In search of robust measures of generalization. In Aduances in Neural Information Processing Systems, volume 33, pp. 11723- 11733. Curran Associates, Inc., 2020. I0
Alhussein Fawzi, Seyed-Mohsen Dozsavi-Dezfooli, and Pascal Frossard. Robustness classifiers: From adversarial to random noise. In Advances in Newral Information Processing Systems, volume 29, pp. 1632- 1640. Curran Associates, Inc., 2016.
Marylou Gabrié, Andre Manoel, Clément Luneau, jean barbier, Nicolas Macris, Florent Krzakala, and Lenka Zdeborová. Entropy and mutual information in models deep neural networks. Advances in Neural Information Processing Systems, volume 31, pp. 1821 1831. Curran Associates, Inc., 2018. 12
Saurabh Garg, Sivaraman Balakrishnan, Zico Kolter, and Zachary Lipton. RATT: Leveraging unlabeled data
guarantee generalization. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3598 3609. PMLR, 2021. 12
Justin Gilmer, Nicolas Ford, Nicholas Carlini, and Ekin Cubuk. Adversarial Examples Are a Natural Consequence of Test Error in Noise, In Proceedings of the 36th International Conference Machine Learning, pp. 2280-2283 PMLR, 2019.
6
Ziv Goldfeld, Ewout Van Den Berg, jaistjan Greenewakd, Igor Melnyk, Nam Nguyen, Brian Kingsbury, and Yury Polyanskiy. Estimating Information Flow Deep Neural Networks. Proceedings of the 96th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2299 2308. PMLR, 2019. 2
Tan. J. Goodfellow, Jonathon. Shlens, and Christian. Szegedy. Explaining and Harnessing Adversarial Examples. Tn International Conference on Learning Representations, 2015. P
Hrayr Harutyunyan, Kyle Reing, Greg Ver Steeg, and Aram Galstyan. Improving generalization by controlling label-noise information in neural network weights. In Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4071-4081. PMLR, 2020. 12
Patrick Helber, Benjamin Bischke, Andreas Dengel, and Damian Borth. Introducing EuroSAT: A novel dataset and deep learning benchmark for land use and land cover classification. IGARSS 2018-2018 IEEE International Geoscience and Hemote Sensing Symposium, pp. 204-207, 2018 4
Patrick Helber, Beujamin Bischie, Andreas Dengel, and Damian Borth. Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification. JEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2019. i
14

---

Published in Transactions on Machine Learning Research (12/2022)
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural langenl kernel: Convergence and generalization in neural networks. In Advonces in Neural Information Processing Systems, volume 31, pp. Curran Associales, Inc., 2018.
Yiding Jiang", Behnam Neyshabur, Hossein Mobahi, Dilip Krishman, and Samy Bengio. Fantastic Generalization Measures and Where to Find Them. In International Conference on Learning Representations, 2019.
Yiding Jiang, Parth Natekar, Manik Sharma, Sumukh K. Aithal, Dhruva Kashyap, Natarajan Subramanyam, Carlos Lassance, Damiel M. Roy, Gintare Karolina Dziugaite, Suriya Gunasekar, Tsabelle Guyon, Pierre Foret, Scott Yak, Hossein Mobahi, Behnam Neyshabur, and Samy Bengio. Methods and Analysis of The First Competition in Predicting Generalization of Deep Learning. In Proceedings of the NewrIPS 2020 Competition and Demonstration Track, pp. 170-190. PMLR, 2021.
Yiding Jiang, Vaishnavh Nagarajan, Christina Back, and Zico Kolter. Assessing generalization of SGD via disagreement. In International Conference on Learning Representations, 2022. 12
Andreas Kirsch and Yarin Gal. Note on "Assessing Generalization of SGD via Disagreement". Transactions on Machine Learning Research, 2022. 12
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
P. A. Lachenbruch. An almost unbiased method of obtaining confidence intervals for the probability misclassification in discriminant analysis. Biometrics, 23(4):639-644 645, 1967. ISSN 0006-341X, 11
Yann LeCun and Corinna Cortes, The MNIST Database of Handwritten Digits. http::/yyaoo.lecun.comm/ //nist// 1998. 4
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Newral Information Processing Systems, volume 32, pp. 8570 8581. Curran Associates, Inc., 2019.
Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl- Dickstein. Finite versus infinite neural networks: An empirical study. In Advances in Neural Information Processing Systems, volume 33, pp. 15156-15172. Curran Associates, Inc., 2020.
Mufan Li, Mihai Nica, and Dan Roy. The future is log- DggGaussiaa:: ResNets and their iufnite-depth-and-wiitt width limit at initialization. In Advances in Neurol Information Processing Systems, volume 34, pp. 7852-7864. Curran Associates, Inc., 2021.
Kevin P. Murphy. Machine Learning: A Probabilistic Perspective. MIT Press, 2012.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep Double Descent: Where Bigger Models and More Data Hurt. arXiv preprinl arv.v
2019. 19
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading Digits in Natural Images with Unsupervised Feature Learning. NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011. 4
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-Based Capacity Control in Neural Networks. In Proceedings of The 28th Conference on Learning Theory, 2015. 2
Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In International Conference Learning Representations, 2020.
Liam Paninski. Estimation of Entropy and Mutual Information. In Newral Compulation, volume 15, pp. MIT Press, 2003. 12
Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On Variational Bounds of Mutual Information. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5171-5180 PMI.R 2019. g
15

---

Published in Transactions on Machine Learning Research (12/2022)
Andrew Michuel Saxe, Yamini Bansal, Joel Dapello, Madhu Advani, Arlemy Kolchinsky, Brendan Daniel Tracey, and David Daniel Cox. On the Information Bottleneck Theory of Deep Learning. In International Conference on Learning Represenlalions, 2018.
12
Shai Shalev-Shwartz and Shai Ben-David. Understanding Mochine Learning: From Theory to Algorithms. Cambridge university press, 2014.
3
19
Ravid Shwartz-Ziv. Information Flow in Deep Neural Networks. PhD thesis, The Hebrew University of Jerusalem, 2021. 2
Ravid Shwartz- Ziv and Alexander Alemi. Information in infinite ensembles of infinitel-wiide neural networks. In Proceedings of the 2nd Symposium Advances in Approsimate Bayesian Inference, volume 118 of Proceedings of Machine Learning Research, pp. 17. PMLR, 2020. g 12
Ravid Shwartz-Zii Amichai Painsky, and Naftali Tishby. Representation Compression and Generalization in Deep Neural Networks. OpenReview, 2019.
Christian Szegedy, Wojciech Zaremba, Πya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. 2
Naftali Tishby. Information Theory of Deep Learning, 2017. URL htt.l/ppppp//ptttto/////////////
2
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness May Be at Odds with Accuracy. In International Conference on Learning Representations, 2019. 20
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation Learning with Contrastive Predictive Coding, arXiv preprint arXin. 1807.03788 2018. 3
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms, 2017.
Aolin Xu and Maxim Raginsky. Information--leeoreles analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. 12
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning
requires rethinking generalization. In International Conference on Learning Representations, 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commanications of the ACM, 64(3):107-115, 2021. ISSN 0001-0782. doi: 10.1145/3446776.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous Generalization Bounds at the ImageNet Scale: PAC-Bayesian Compression Approach. In International Conference Learning
Representations, 2019. 2 12
16

---

Published in Transactions on Machine Learning Research (12/2022)
a) log(Nvo
b)
LB
LUB
22
I(X;
À
0.1
0.5
À
1
10
102
10
106
10
10
102
10
106
10$
10
10a
10
10
10
Training step
Figure 5: We plot [(X; Z) upper 2 and lower (6) bounds corresponding to the illustrative EuroSAT example
(Figure D. Increasing the regularization to X 0.5 in b) and À = 1.0 in c) reduces MI below (og(N Samples to the right of the vertical line in a) where TUB crosses log( Nura) are discarded for the main analyses. NB: We use natural units ("Nats" or "Shannons") for 1(X; Z) here, but we convert to bits when evaluating the ICB.
A Appendix
A.1 Assumptions of input compression bound
It is assumed in the construction of the ICB that X is d-dimensional random variable that obeys an ergodic MRF probability distribution, asymptotically in d. A MRF is an undirected graphical model, used to model data distributions with a particular conditional independency structure, which is commonly used for spatial data, including images (see (Murphy means that p(z) factorizes into a product of terms which represent the potentials for each clique on the underlying graph. In terms of correlations, this means that each pixel in 2D image is strongly correlated with its immediate neighbors, but not with pixels that are further away. The "ergodic" part is essential for the derivation of the ICB: An ergodic MRF does not "get sluck" in any part of the state space; in other words, there is nonzero probability for every possible state to be reached. Ultimately, this is the necessary assumption to invoke the Asymptotic Equipartition Property (AEP), which turn allows us to invoke typicality. Defining the typical set is the crux of the ICB derivation, because enables us to quantify the hypothesis space cardinality in terms of entropy. From here, the rest follows from information-theory fundamentals.
Ch. 19] for an introduction). Mathematically, this
A.2 Lower bound on MI
We may lower bound [(X; Z) using a bound of similar form as equation 2 based on batch of samples:
p( (F&) N Σ3 p( ((,))
T(;; 2) > E log
JLB
(6)
where the expectation is taken over N independent samples from the joint distribution II p(z,, 22). The main difference between this bound and equation 0 is the inclusion of p(zeka:) in the denominator.
A.3 Illustrative example and filtering MI We empirically verified that equation and equation yield similar results when JUB (og(Nur) (Fig.
A5
17

---

Published in Transactions on Machine Learning Research (12/2022)
Fashion (CNN)
SVHN (CNN)
CIFAR (CNN)
EuroSAT (MLP)
Generalization error (%)
Sat. 100 0% (N=4232)
Sat. 67 6% (N=3914)
Son. 85 0% (N=4148)
Sot. 95 7% (N=9637)
vs
60-
vs
vs
vS
20
8 v
20
40
60
20
40
60
20
40
60
0
20
40
60
Theoretical generalization error bound (%)
Figure 6: ICB is plotted versus GE (0 1 loss) for FashionMNIST, SVHN, CIFAR-10, and EuroSAT datasets. The ICB satisfaction rate is annotated in the top left corner of each plot with format "ICB % (N)". Each binary classification task is assigned a unique colour to highlight inter-task differences ICB satisfaction rate. See Figure 2 of $4.1 for the corresponding Figure with GE expressod using square loss. NB: Results for MNIST omitted from Figure they similar to Fashi oNMNIST.
Table 5: CNNs have consistently smaller average GE than MLPs for SVHN and CIFAR-10, as they do not fit the training set to the same extent as MLPs. Note that these average accuracies include models trained for both short and long periods time, therefore a low test accuracy here does not imply failure of learning.
Datasct
Arch. ICB Sat (Acc./MSE) (%)
Train (%)
Test (%)
GE (%)
CNN
67.6%/95. /95.7% (3914)
74.78
64.18
10.60
SVHN
ML.P
49.5% 86.2% (3980)
79.82
67.07
12.74
CNN
84.9% 84.9%/80.55% 80.5% (4153)
85.84
76.12
9.72
CIFAR-10
MLP
73.8%/68 68.0% (4318)
88.13
76.70
11.43
18

---

Published in Transactions on Machine Learning Research (12/2022)
SVHN
CIFAR-10
89
81
ICB sat. (%) (GE- (GE-Aco)
80-
97
(GE=M (E=MSE)
ICB sal. rate (%) (GE (GE=Aco Acc))
88
883
ICB sat. rate (%) (GE=MSE)
O
82
96
82
ICB sat. rate 1%)
80
.95
60-
94
78
50-
777
93
82-
200
400
600
800
1000
1200
1400
200
400
600
800
1000
1200
1400
Number of training samples
Number of training samples
Figure 7: The ICB satisfaction rate is plotted versus the number training samples for SVHN and CIFAR-10 datasets. The primary vertical axis bounds GE using the 0-1 loss (GE=Acc), whereas the secondary vertical axis bounds GE using the square loss (SE-MSE). Here, we only consider the first three tasks for each dataset, i.., "O vs 1", "1 vs. 2", and "2 vs. 3" an approximation for all nine tasks. Other datasets Fashi oNMNIST and EuroSAT were excluded as they consistently satisfied ICB for all train-set sizes considered here.
A.4 Bounding generalization error
Loss function We measured GE using the 0-1 and square loss (see Fig. A for 0-1 loss). This change results in no difference in the overall TCB satisfaction rate for FashionMNIST a decrease for SVHN from 95.7% to 67.6%, a small increase for CIFAR-10 from to 80.5% to 84.9% as well as for EuroSAT from 93.6% to 95.7%.
Train-set size The number of training samples may have affected the ICB satisfaction rate for some datasets (Fig. 77). For this experiment, we included small training sets of size Nem E (250, 500, 750} to observe broader relationship between Num and the ICB satisfaction rate. For SVHN, the ICB satisfaction rate appears to be still improving at N = 1500 despite dip at = 1000. We ran additional experiments with Num E {950, 1050, 1150} to assess the width of this dip for SVHN. The dip at N = 1000 is not necessarily alarming as other studics have observed that more training data can sometimes hurt model performance, c.g., see Nakkiran et al. 2019 The ICB satisfaction rate for SVHN may therefore benefit from additional training data given the overall positive trend. Conversely, there no discernible trend for CIFAR-10.
Task labels There were considerable inter-task differences in ICB satisfaction rate (Table A6). The "Overall" row of Table Ao corresponds to the ICB satisfaction rates presented in Table D well as in the top left corners of Fig. 2 and Fig. AG for the square and 0-1 loss respectively.
Confidence The confidence parameter 8 in the PAC framework accounts for a small probability that the training set received by a learning algorithm is misleading, i.e., the samples are not representative of the true data-generating distribution, or they do not reflect all relevant details of the distribution (Shalev-Shwartz & Ben-David 2014). It is natural to wonder how the choice of 8 affects the ICB satisfaction rate. Recall from 44.1 that refer to the percentage of tuples (ICB, GE) for which GE < ICB the "ICB satisfaction rate". percentage, e.g., d = 0.05 equals 95% confidence. Decreasing
which should roughly equal - 8 expressed 8 to 0.01 from its default value of 0.05 increased the ICB satisfaction rate by 6.2% for SVHN on the 0-1 loss, compared lo an expected z 4% difference (99% 95%). Increasing 5 to 0.20 decreased the ICB satisfaction rate by 11.2% compared to an anticipated difference of x 19% (95% - 80%). Results were less sensitive to for CIFAR-10 and EuroSAT (= 1% difference for 99% 95%), and independent from 8 for FashionMNIST as the compression term alone (i.e. from the numerator of equation 4 sufficed bound the small GEs for this dataset.
19

---

Published in Transactions on Machine Learning Research (12/2022)
Table 6: 1CB satisfaction rates broken down by task for three datasets. MNIST and FashionMNIST are excluded for brevity as they were always at 100%. Columns "Ace." and "MSE" indicate whether GE is quantified in terms of classification accuracy (0-1 loss) or MSE (square loss) respectively. The "N" column indicates the number of valid experiments.
SVHN CNN
CIFAR CNN
EuroSAT MLP
Task
Acc.
MSE
N
Acc.
MSE
N
Acc.
MSE
N
vs
87.7%
99.3%
431
93.3%
86.6%
461
100.0%
100.0%
1012
vs 60.2%
93.6%
435
95.7%
88.7%
462
100.0%
100.0%
961
2 v8 51.8%
94.1%
440
69.9%
69.2%
468
82.2%
82.2%
1123
3 vs
78.7%
97.2%
431
74.5%
71.0%
439
97.9%
86.0%
1175
4 vs
94.2%
97.0%
434
71.3%
71.3%
460
100.0%
100.0%
1151
5 v8 6
30.0%
88.6%
440
74.8%
72.8%
460
100.0%
100.0%
1066
6 v8
85.7%
97.0%
433
91.6%
83.2%
463
83.5%
78.3%
1154
7 vs
84.4%
97.7%
430
100.0%
94.1%
461
100.0%
94.9%
1135
8 VS
37.1%
92.7%
440
93.5%
87.4%
459
100.0%
100.0%
860
Overall
67.8%
95.2%
3914
84.9%
80.5%
4153
96.0%
93.5%
9637
FashionMNI51
SVHN
CIFAR
Test Arc. (%)
9000
92.3
35.0
97.5
10001
90
100
C0
90
100
Robust Acc. (%)
100
701
60
50
Train Acc. (%)
Figure 8: Train-set accuracy is plotted versus clean test accuracy (top) and robust test accuracy (bottom) using AWGN. The marker size indicates the ICB value, and each binary classification task is assigned a unique colour.
A.5 Vacuous or non-vacuous?
We plotted train-set accuracy versus test accuracy on the "clean" and "noisy" sets, indicating ICB values by the marker size. Large ICB values tend to occur for very high training accuracy and coincide with poor robust accuracy (Fig. ABD. Since ICB increased considerably for the models with highest clean test accuracy, we selected models with greatest robust accuracy in $4.3 These results are consistent with previously observed accuracy versus robustness trade-offs [Tsipras et al. 2019).
B Effect of metaparameters on theoretical bound
We repeat the analysis from 4.4 for the CIFAR-10 datasct in Fig. Ag this time comparing SE results when GE is measured using the standard lest set versus a test set with AWGN. Evaluating GE with a noisy test set yields greater a sample size after filtering out measurements where GE is too small to reliably measure a change a classifiers true error. The SE values for the activation and diagonal metaparameters are also slightly larger for the standard GE, implying that ICB is better correlated with robust GE than standard GE in our experiments for CIFAR-10. A detailed worked example showing how column is computed in these
20

---

Published in Transactions on Machine Learning Research (12/2022)
167
Sign-error
1.00
79 95.10.9....00 86
105
0.75
0.50
0.25
592577501536
249286278237256
0.00
activation
train samples
time
diagonal
depth
0/1
1/2
2/3
3/4
4/5
5/6
6/7
7/8
8/9
(a) CIFAR-10, Standard GE
Sign-error
1.00
94
127
86
161
250285
0.75
278
0.50
0.25
24
46
10
517613 6046600
28930130223030
0.00
activation
train samples
time
diagonal
depth
0/1
1/2
2/3
3/4
4/5
5/6
6/7
7/8
8/9
(b) CIFAR-10, AWGN GE
Figure 9: Evaluating GE noisy test set yiclds greater sample size after accounting for Monte Carlo variance in GE estimates, and slightly smaller sign-errors. Plots show GE prediction SEs (where lower is better) for six different metaparameter interventions on nine binary classification tasks {0 vs. 1,1 vs. . vs. 9} for CIFAR-10. Numbers above the SE for even-numbered tasks indicate the number samples N comprising the respective SE measurement. See Table A7 for a worked example showing how a column computed in these plots.
225
1.00
Sign-error
111
0.75
212
0.50
0.25
469
85
367
524 569857148772
178641332732151
$70
0.00
activation
train samples
time
diagonal
depth
3/4
4/5
Figure 10: Evaluating SE for EuroSAT with AWGN test set.. Other details similar to those described in captions for Fig and Fig Ag
plots provided in Table A7 Smaller SEs are observed on average for the EuroSAT dataset than for CIFAR-10, but with greater inter-task variance (Fig. 10.. The SF, is consistently near zero for the time and diagonal metaparameters across all datasets.
21

---

Published in Transactions on Machine Learning Research (12/2022)
Table 7: Detailed GE prediction SE for all combinations of the depth metaparameter for the CIFAR AWGN versus 9 task. The first two columns ("Raw") comprise all SEs with only basic filtering for (UB(X; Z) s log(train samples). The next set of (*Filtered") columns additionally accounts for Monte Carlo variance of empirical averages and discards samples with small difference in GE relative to the number of train and test samples (see text for details). The final "filtered" weighted average SE of 61.5% (N = 278) appears in Fig. A9b (scries 8/9).
Raw
Filtered
Depth
N
Sign-error
N
Sign-error
Weighting
Before
After
94
46.8%
34
35.3%
12
1
2
93
49.5%
42
45.2%
19
1
3
91
51.6%
55
49.1%
27
1
4
87
54.0%
60
51.7%
31
1
49.5%
100.0%
2
62.6%
22
100.0%
2
87
83.9%
32
87.5%
28
2
5
91
73.6%
1
100.0%
3
4
87
90.8%
26
96.2%
25
3
5
84
95.2%
2
100.0%
4
5
278
61.5%
22

---

Published in Transactions on Machine Learning Research (12/2022)
Clean
AWGN
FGSM
40
Drtt
Generalization Error
A
& 1000
30-
A
N'
2000
20
10-
0.142
T 0-155
- 0.221
3
2
5
I I(x; Z)
bits
Clean
AWGN
FGSM
40
Generalization Error
N' Bon
N 1000
44
30
M
#4
8
A
10
T 7-0.720
T 0.705
0.5887
10
40
10
30 40
10
30
Input Compression Bound
Figure 11: ICB (bottom) ranks GEs better than I(X; Z) alone (top) for different training set sizes. Shown are 750 fully-comnectdd NTK ReLU models trained (t = oo) on CIFAR-10 binary classífication task (classcs and 5) using three different training set sizes of = {500, 2000) and a test set with N = 2000. Model depth indicated by the colour intensity for each series, where the darkest shade indicates the maximum depth of five (5) layers. Three GE types are evaluated: Clean (standard), AWGN (adversarial), and Fast Gradient-Sign Method (FGSM) (adversarial) bottom row). Plotting GE versus the ICB better aligns results for different sized training sets (N) compared to T(X; 2), and yields better ranking in terms of Kendall-r.
plotted with respect to T(X; Z) (top row) and ICB
B.1 Advantage of ICB versus MI
To gain further insight into ICB, we examinc GEs for a specific CIFAR-10 binary classification task (classes and 5) using three different training set sizes. Plotting GEs with respect T(X; ; Z) alone yields poor overall ranking, whereas ICB effectively aligns trials with different training sizes (Figure
23


Reviews:
[{"review_id": "335y2r6aI2", "reviewer": "Reviewer_egUC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. Authors studied an interesting yet importance problem in the field.\n2. Authors clearly stated the derivations of $GE_{ICB}$ from the statistical learning theory (e.g., PAC) and information theory.\n3. Several experiments have been done to demonstrate the feasibility of the proposal.\n\nWeakness.\n1. Eq. (3) should hold in a probability higher than $1-O(\\delta)$ or $1-\\delta$. So, how the confidence factor $\\delta$ would influence the estimation? If ``ICB satisfaction rate'' equals to $1-\\delta$, please make it clear in the texts. I may suggest you to complete the inequality in Eq. (3) with the probability term and introduce the detailed definition of $\\delta$ there. Another issue is that the incorporation of $\\delta$ makes ICB a tradeoff between mutual information (input-output) and the confidence levels of GE estimation. Please discuss this issue in the revision. \n\n2. Experiments results are intensive and verbose. Could you please enumerate the hypotheses or expected observations you hope to see throughout your experiments, so as to test your major hypothesis on ICB and GE? Please highlight your claims from your experiments. \n\n3. Authors discussed the correlations between ICB and GE, and mentioned the NeurIPS competition on generalization error predictions. I am wondering if it is possible to include more competitors from the competition to compare with ICB? I understand ICB is a more comprehensive tool with confidence bounds.  ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies the problem of generalization error estimation without the use of validation samples. Authors studied the mutual information (MI) between inputs and final layer representations of deep neural networks, and derive a so-called input-compression bound of generalization errors ($GE_\\mathrm{ICB}$). Then, authors carried out empirical studies to investigate the correlation between MI and the generalization error.  Specifically, authors conducted several sets of experiments to investigate the nexus between theoretical GE bounds and the generalization errors. The results demonstrate the feasibility of using ICB to estimate generalization errors. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please consider to include the three points in the weakness section for revision. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QFIqei1PJ0", "reviewer": "Reviewer_G5hL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) The problem this paper addresses is important, and the experiment result is interesting, which can provide good materials for further discussions in the community.\n\n(2) The experiments are performed in a quite thorough way and to my knowledge, is sound.\n\nWeaknesses:\n\n(1) It may be useful to compare with some other generalization bounds as mentioned in the related works. Even though it is difficult as said by the authors, it may still be useful to see the relative strengths of different generalization bounds.\n\n(2) The writing of the experiment section can be more clear. Right now it seems there are many observations, but not presented in a clear and well-organized way.\n\n(3) For some datasets (e.g. SVHN, CIFAR), the ability of ICB to bound generalization error (measured in satisfaction rate) is low. The author observe that these are also the ones that can be identified via randomization test. Does the authors have an intuitive explanation/hypothesis for this? If so, the authors can also perform experiments to verify or disprove the hypotheses. In this way, we can understand deeper about the failure modes of ICB, and may even improve it.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper empirically evaluates Input Compression Bound (ICB) as a generalization bound. The ICB directly links the generalization with the mutual information between input X and representation Z. Through three axes: tightness of the bound (vacuous or non-vacuous), percentage of trials satisfying the bound, and ranking generalization errors, the authors show that: for many datasets, the ICB has a good satisfaction rate (although for some have low satisfaction rate); randomization test may be used to help identify when ICB performs bad as a GE bound for a variety of models; it is non-vacuous; etc. Overall, the extensive empirical study, the authors show that ICB is generally effective and useful for indicating generalization error.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Corresponding to the weaknesses above, (2) is critical for the acceptance; and deeper explanation for (3), and (1) comparing with other generalization bounds can significantly strengthen the work.\n\nMinor:\n1. Can the authors explain in the text or Appendix how the \\lambda regularization is used? It is not clear in current manuscript.", "broader_impact_concerns": "There is no need for Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cFQ0ONVm7Z", "reviewer": "Reviewer_GTi6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**: \n- This paper presents empirical analysis of an existing bound. This is particularly important as it can highlight how bounds derived under restrictive settings behave more generally. \n\n**Weakness**:  \n- The abstract highlights that \"in an attempt to falsify the bound\", it would be great to explictly list down all the reasons on why one should expect the bound to incorrect. This should include the setting under which the bound is theoretically applicable and clearly highlight how they may not be true in practice. \n\n- The language in abstract about \"In our attempt to empirically falsify the theoretical bound,\" is a bit too strange. To the best of my understanding this paper attempts to emperically study a bound derived theoretically under some strong assumptions. If this understanding is correct, calling it as trying to empirically falsify is incorrect language in my opinion as the goal is not to falsify the bound in the settings it was derived in. \n\n- Figure 1 shows the bound with shaded grey region. It is unclear why the bound is shown with a shaded region. Shouldn't it be simply a line? While it may mean that the test error can lie anywhere in between, the current exposition is not highlighing this clearly.\n \n- Figure 2, and more broadly, experiments in that figures seems a bit weird. While to theoretically verify the bounds, it makes sense to have values below the y =x line, it is unclear why it is the only criterion used in the paper. A loose bound, as loose as predicting an error of 100% would always be correct according to the `satisfaction' criterion used in Figure 2. To understand the tightness of the bound, should the bound be close to the line y =x.  \n\n- Since one of the goal of the paper is find bounds that correlate well with GE, paper should include discussion (and perhaps compare) with other related work that leverages unlabeled data to obtain bounds [1,2]\n\n- Moreover, a discussion with other mutual information bounds must be inluded in the paper [3,4,5]. \n\n- Contribution of this work also a bit skim. First, it is unclear why authors only focus on the bound in equation (4), what are the (desirable) properties of this bounds that even motivates studying only this bound. Second, it would be great if authors can add comparison to other MI based bounds derived in other related work highlighted above. \n  \n\nReferences:   \n[1] Garg et al. RATT: Leveraging Unlabeled Data to Guarantee Generalization. ICML 2021.    \n[2] Jiang et al. Assessing Generalization of SGD via Disagreement. ICLR 2022.    \n[3] Achille and Soatto. Emergence of Invariance and Disentanglement in Deep Representations. JMLR 2018.    \n[4] Harutyunyan et al. Improving Generalization by Controlling Label-Noise Information in Neural Network Weights. ICML 2020.    \n[5] Xu and Raginsky. Information-theoretic analysis of generalization capability of learning algorithms. NeuRIPS 2017", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors empirically explore an MI-based bound to upper bound generalization error. Their theoretical generalization error bound is based on a compression technique that relates input and final representations. Experimental evidence across a few architectures and datasets shows the applicability of this bound in practice. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please see the comments in the weakness section above. Addressing all of those bullets would be crucial to securing an acceptance. Moreover, to make the work complete it would be great to include the following (not necessary to secure acceptance): \n \n- Formal proof for equation 4 should be included in the paper. While authors cite Shwartz-Ziv 2019, a formal proof for equation (4) with consistent terminology can help readers as the paper primarily uses that bound.\n\n", "broader_impact_concerns": "Not applicable ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "49GO1nTrME", "reviewer": "Reviewer_g7Gf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- The bound considered by the paper is not one that has been studied in great depth in the past -- most work on empirical generalization bounds has focused on those based on flatness of the local minimum, rather than looking at compression of the input space.\n- The paper considers a number of different datasets which are reasonably diverse (though all vision), and identifies interesting differences in the correctness and predictive power of the proposed bound between these datasets.\n- The work further studies a number of interesting experimental settings and asks thoughtful questions about the proposed bound, in particular: 1) evaluating effect of random labels on the bound, and 2) studying the predictive power, as opposed to correctness, of the bound on real architectures.\n- The presentation and writing in the paper is polished — typos are not an issue, and the text flows nicely.\n\n\n## Weaknesses\n\n- There is significant lack of clarity in how the practical instantiations of the bound are computed: in particular, the work claims to evaluate the MI between a feature and the input, but also claims to use the NTK regime, in which to the best of my understanding networks don’t do feature learning.\n- There are further potential issue with the MI estimation procedure, as the features on the training set are themselves a function of the training set, so estimating $I(X, Z_\\theta)$ shouldn’t use the training set $X$ because of the dependence of the parameters $\\theta$ (and hence the features $Z_\\theta$) on $X$. It is possible that the procedure used gets around this issue but I wasn’t able to determine this from the information provided in the paper.\n- The assumptions required for the ICB bound are not explicitly stated, and based on the cited paper they are in fact crucial for the validity of the bound. The paper should include a discussion of these assumptions and also evaluate the degree to which they are violated in the different datasets. This seems particularly relevant as the justification for ICB seems to be a limiting argument, and it is not clear how this scales with the dimension and number of samples in the problem. It is further unclear whether the generalization bound as presented in the paper is valid for any finite problem.\n- The previous point is crucial and relates to a more philsophical issue I had with the paper: a generalization bound is either correct or not, and therefore there is no reason for it to be empirically “falsified”. The correctness of the bound stems from the correctness of its proof, and empirical investigation should not be necessary. An empirical falsification of a bound thus indicates one of two things: either the proof of the bound is incorrect, or the assumptions of the bound do not hold in the setting studied. \nThe study of infinite-width networks is not well-motivated: why not also include deep neural networks of finite width, as it is in these settings where feature learning, and hence input compression, will play a more significant role in the learning process?\nIf the bound is not in fact a provable upper bound on the generalization performance of a model but rather a heuristic, then a meaningful contribution to the literature would require a more detailed empirical analysis of the heuristic as the current empirical investigation is limited in the scope of problems considered and the detail of the analysis. This work only appears to consider binary classification problems, for example, and the differential performance in predicting generalization error and robust generalization error isn’t explained or motivated: what does robust generalization tell us about the ICB that classical generalization doesn’t?", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "\nThis paper performs an empirical study of an information bottleneck-inspired generalization bound, ICB. The evaluation of the bound leverages relatively recent empirical approaches to measuring the mutual information, and the work applies this methodology to answer a range of questions about the ICB in an infinite-width model of deep neural networks. First, the paper attempts to falsify the bound on real-world data, succeeding on some datasets and suggesting that the assumptions required in the derivation of the ICB do not hold in many real-world datasets It goes on to study the ability of the ICB to measure a network’s ability to fit random labels, and to distinguish between natural and randomly re-labelled datasets, finding that the bound can distinguish between random and natural labels in some settings but not others. Finally, the work evaluates the correlation between the value of the bound and empirical generalization performance.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "\nMotivated by my comments on the weaknesses of the paper, there are three major categories of changes I would like to see in the paper before I would be comfortable recommending it for publication.\n\n1. Please provide a more detailed description of how the latent variable Z is computed in infinite width networks and prove the validity of the mutual information estimator.\n2. The discussion of empirical falsification needs to be rewritten to acknowledge whether this is aiming to verify the correctness of the proof (seeing as this result has not to my knowledge been formally presented in peer-reviewed proceedings) or the validity of the assumptions. \n3. I would also like to see a more detailed empirical analysis that explains how the observed correlation between the bound and generalization performance arises. For example, how  does generalization under interventions on different meta-parameters correlate with the generalization bound along the lines of [Dziugaite et al., 2020] — is ICB better at predicting generalization under some hyper-parameter selection problems than others?", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors have engaged with the reviewers and through rebuttals, addressed reviewers' concern in a satisfactory way. On a personal note, I found the manuscript to be an enjoyable read, and I appreciate the care the authors have put into explaining their results. I expect the camera-ready to reflect the discussions with reviewers. Congratulations on a fine piece of work and for your contribution to TMLR!
Decision: Accept (poster)