{'fraction_non_alphanumeric': 0.043457797301537496, 'fraction_numerical': 0.020260881258684835, 'mean_word_length': 4.5634663341645885, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bounding generalization error with input compression: An empirical study with infinite-width networks

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


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 1 . Bounding a DNN's GE based on a training set is a longstanding goal (Jiang et al., 2021) for various reasons: i) Labeled data is often scarce, making it at times impractical to set aside a 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. In contrast, the test accuracy is merely a single performance estimate based on an arbitrary and finite set of examples. Furthermore, the adversarial examples phenomenon has revealed the striking inability of DNNs to generalize in the presence of human-imperceptible 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 GE-such as network depth, width, p -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 a range of tasks, we investigate the Mutual Information (MI) between the input 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 input is an important distinction from many previously proposed GE bounds (e.g., Zhou et al. (2019)), which tend to be model-centric rather than data-centric.
We use infinite ensembles of infinite-width networks (Lee et al., 2019) for which MI is well defined. These models 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 (Belkin et al., 2019). For these reasons, Belkin et al. (2018) suggested that understanding kernel learning should be the first step taken towards understanding generalization in deep learning. To this end, we evaluate the ICB proposed by Tishby (2017); Shwartz-Ziv et al. (2019) with respect to three axes of performance: 1. First, we try to empirically falsify the bound by evaluating the GE of a variety of models, composed by drawing random metaparameters of the neural architecture and training procedure. We then compare the empirical GE to the theoretical GE bound given by ICB. We show that ICB contains the GE at the expected 95% confidence level for three of five datasets, or all five for the best-performing models. In addition, we suggest the training-label randomization test (Zhang et al., 2017) as a means to determine when ICB may perform well a priori without relying on a test set.
2. Next, we analyze whether the ICB is sufficiently small for useful model comparisons. If a 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, obtained from less than 2000 training samples.
3. Last, we assess the correlation between ICB and GE. Ranking GE is less consistent when several metaparameters vary, with ICB sometimes outperforming, and at times under-performing a simpler baseline. Increasing the Neural Tangent Kernel (NTK) diagonal regularization coefficient is most correlated with reducing ICB.
Beyond these three main desiderata for generalization bounds, we show advantages in reducing ICB even when the GE is 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 et al., 2017;. Finally, we show that ICB is predictive of test-time perturbation robustness (Goodfellow et al., 2015;Gilmer et al., 2019), without assuming access to a differentiable model.

Background
We make use of an information-theoretically 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 (2017)), later in a pre-print (Shwartz-Ziv et al., 2019)[Thm. 1] and more recently in a thesis (Shwartz-Ziv, 2022)[Chapter 3]. Although an information-theoretic proof was provided, to the best of our knowledge the bound has not yet been studied empirically.

Mutual information in infinite-width networks
The MI between two random variables X and Z is defined as where we used Bayes' rule to obtain the expression on the right and introduced E p(x,z) [·] to denote the average over p (x, z). In our case, X denotes the input and Z the input representation, i.e., the output of any of the network's layers. Since the marginal p(z) is unknown, we use an unnormalized multi-sample "noise contrastive estimation" (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 MI (Poole et al., 2019). In van den Oord et al. (2018), the density ratio p(z|x)/p(z) was learned by a neural network. Instead, following Shwartz-Ziv & Alemi (2020), we use infinite ensembles of infinitely-wide neural networks, which have a conditional Gaussian predictive distribution: p(z|x) ∼ N (µ(x, τ ), Σ(x, τ )) with µ, Σ given by the NTK and Neural Network Gaussian Process (NNGP) kernel (Jacot et al., 2018). The predictive distribution also remains Gaussian following τ 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: ( A lower bound on MI, I LB , of a similar form as equation 2 is also available (equation 5, Appendix A.1), and we verified that both bounds yield similar results for the training regime in which we apply them (Fig. A5). Note that since we wish to evaluate a generalization bound, it is important that these MI bounds are computed on the training set only.

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. (2019)[Appendix A]. We begin with the conventional GE bound developed in the PAC framework, which plays a central role in the early mathematical descriptions of machine learning. The abbreviation PAC stands for Probably Approximately Correct and provides a probabilistic formulation for the learning success. It is assumed that a model receives a 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 hypothesis-class cardinality |H|, the confidence parameter δ, and the number of training examples N trn , one obtains the following bound on the GE: The key term in this bound is the hypothesis-class cardinality, which is essentially 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 is applied in order to obtain a finite set of functions. For neural networks, |H| is usually assumed to increase with the number of trainable parameters. The bound (3) states that generalization is only possible when the expressivity is outweighed by the size of the training set, reflecting 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 neural network 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 input space. For instance, consider binary classification where each of the |X | inputs belongs to one of two classes. The approach that leads to bound (3) reasons that there are 2 |X | possible label assignments, only one of which is true, and hence a hypothesis space with 2 |X | 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 neural-network learning. First, note that solving a classification task involves finding a suitable partition of the input space by class membership. Neural networks perform classification by creating a representation Z for each input 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 neural-network 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 to |H| ≈ 2 |T | , where |T | is the number of class-homogeneous clusters that the Neural Network (NN) distinguishes. To estimate |T |, the notion of typicality is employed: Typical inputs have a Shannon entropy H(X) that is roughly equal to the average entropy of the source distribution and consequently a probability close to 2 −H(X) . Since the typical set has a 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 H(X) . Similarly, the average size of each partition is given by 2 H (X|Z) . An estimate for the number of clusters can then be obtained by |T | ≈ 2 H(X) /2 H(X|Z) = 2 I(X;Z) , yielding a hypothesis class cardinality |H| ≈ 2 2 I(X;Z) . With this, the final expression for the ICB is:

Experiments
Our experiments are structured around three key questions: 1) Can we falsify ICB, e.g., by finding models with GE that exceeds the theoretical bound ( §4.1), or by falsely predicting generalization when randomizing the training labels ( §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 N 2 trn rather than (k × N trn ) 2 for k-classes. Aside from this computational advantage, our methodology extends to the multi-class setting.

Evaluating generalization throughout training (Experiment A)
We conduct experiments with five standard benchmark datasets: MNIST (LeCun & Cortes, 1998), FashionMNIST (Xiao et al., 2017), SVHN (Netzer et al., 2011), CIFAR-10 (Krizhevsky, 2009, and EuroSAT (Helber et al., 2018;. 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 i + 1" for i ∈ {0, . . . , 8}. Note that this sequential class ordering is an arbitrary choice.
We initialize a variety of models by sampling uniformly at random from the following metaparameters: the number of fully-connected layers, L ∼ U(1, 5), the diagonal regularization coefficient λ ∼ U{10 0 , 10 −1 , 10 −2 , 10 −3 , 10 −4 }, the activation function φ(·) ∼ U{ReLU(·), Erf(·)}, and the number of training samples, N trn ∼ U (250,2000). Test sets have a constant size of N tst = 2000. We do not randomly sample a learning rate or mini-batch size, as the infinite-width networks are trained by full-batch GD, for which the training dynamics do not depend on the learning rate once below a critical stable value (Lee et al., 2019). A nominal learning rate of 1.0 was used in all cases and found to be sufficient. 2 We use 100 different random seeds to draw metaparameters for each of the nine tasks, yielding 900 models for each dataset.
Each of these 900 models was evaluated at five different time steps throughout training at t = {10 2 , 10 3 , 10 4 , 10 5 , 10 6 } yielding 4500 tuples (ICB, GE) to analyze. The end points t = 10 2 and t = 10 6 were selected as most of the variation in GE was contained within this range. Training for less than t = 10 2 steps Figure 1: The ICB (grey filled area) evaluated on the EuroSAT Pasture versus Sea-Lake binary classification task with 500 training samples and 2000 test samples at different regularization levels. At low regularization λ = 0.1 (a), the ICB is vacuous with respect to standard generalization beyond 10 4 training steps, but reflects the poor robust generalization for the "Noisy" test set with Additive White Gaussian Noise (AWGN). Increasing the regularization to λ = 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 I(X; Z) bounds for this experiment.
typically resulted in a 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 = 10 6 . Furthermore, t = 10 6 was found to be a critical time beyond which I UB (X; Z) sometimes exceeded its upper confidence limit of log(N trn ), particularly for small λ values where memorization (lack of compression) is possible.

Results
Illustrative example Before presenting the main results, we examine ICB for a EuroSAT classification task using only 500 training samples (Fig. 1). 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 ≈ 20% GE bound for finite-width DNNs evaluated on MNIST.
We evaluate ICB throughout training from the first training step (t = 10 0 ) until steady state when all accuracies stabilize (t = 10 8 ). Shortly after model initialization (t = 10 0 to t = 10 1 ) the ICB is < 7% (indicated by the height of the shaded region in Fig. 1) and the training and test accuracy are both at 50% (GE= 0). Here, ICB is non-vacuous, but also not necessarily interesting for this random-guessing phase. ICB increases as training is prolonged. 3 At low regularization ( Fig. 1 a), the ICB ultimately becomes vacuous (ICB ≈ 50%) around 10 4 steps. However, although ICB is vacuous with respect to standard generalization in a), it reflects well the poor robust generalization when tested with AWGN (Gilmer et al., 2019). Increasing Theoretical GE Bound (%) Figure 2: The ICB ("Theoretical GE Bound") is plotted versus GE for FashionMNIST, SVHN, CIFAR, and EuroSAT datasets for Exp. A ( §3.1). We refer to the percentage of models with GE < ICB as the ICB satisfaction rate, which is annotated in the top left corner of each plot with format "Sat. % (N)", where N denotes the number of valid experiments. Each binary classification task is assigned a unique colour to highlight inter-task differences in ICB satisfaction rate.  Figure 2; a more detailed breakdown of these results can be found in  (2221) 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 (σ 2 = 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 is that ICB captures the trend of robust generalization. Evaluating robustness effectively is error-prone and often assumes access to test data and a differentiable model (Athalye et al., 2018;. In contrast, we make no such assumptions here. The lack of robustness in Fig. 1 a) would have likely gone unnoticed by the practitioner. Either early stopping or increasing λ reduce the ICB and robust GE as a potential solution-or a better trade-off between accuracy versus robustness . A caveat to this example is that only two metaparameters varied: the number of training steps t and regularization λ. Next, we assess the ability of ICB to bound and rank GE for a broader range of metaparameters and datasets.

Bounding generalization error
We refer to the percentage of tuples (ICB, GE) for which GE < ICB as the "ICB satisfaction rate", or "Sat." in plots. We expect ≈ 95% of samples to satisfy this property as the bound is evaluated with δ = 0.05 or 95% confidence. The overall ICB satisfaction rate with the respective number of valid experiments N is listed in Table 1. Exp. B yielded greater N than Exp. A primarily because it uses a different range for the regularization coefficient λ, resulting in larger λ values. Since larger λ is associated with more compression, Exp. B had fewer samples being discarded than in Exp. A due to I UB exceeding log(N trn ). Otherwise, ICB satisfaction rates are similar, with SVHN performing slightly worse and CIFAR-10 slightly better for Exp. B versus Exp. A. These results also suggest that exploring nine binary classification tasks (Exp. A) serves as a useful approximation for the full set of all 45 possible tasks (Exp. B). Next, we analyze how model performance influences the ICB satisfaction rate.
When we restrict our scope to the best-performing models based on their test accuracy, the ICB satisfaction rate improves considerably. For example, models with test accuracy ≥ 80% attain ICB satisfaction rates of 94% (N = 682) for SVHN in Exp. B, and 99% (N = 2812) for EuroSAT in Exp. A (Fig. A11c). For CIFAR-10 in Exp. B, we obtain 96% (N = 591) by restricting to test accuracy ≥ 87%. The specific test accuracy thresholds were chosen to balance a trade-off between satisfying the ICB at ≈ 95% and maximizing N . Although best-performing models are more likely to be deployed in practice, theoretical GE bounds generally prohibit access to a test set. Therefore, we next select models based on their training accuracy.
We refer to models that achieve 100% accuracy on the training set as "overfitted", consistent with prior use of this term by Belkin et al. (2018). Interestingly, restricting our analysis to overfitted models either improves or does not change ICB satisfaction rate for Exp. A. For MNIST, FashionMNIST, SVHN, and EuroSAT, overfitted models attain an ICB satisfaction rate of 100% with N = 1970, 1820, 20, 353 respectively, while for CIFAR-10, the satisfaction rate remained below 95%, albeit it improved from 59.3% (N = 4344) to 72.6% (N = 876). Similar results were observed for Exp. B. Detailed plots for these results can be found in Figures A7, A8, A9, A10, A11 in the Appendix. The mostly excellent ICB satisfaction rates of the overfitted models are not due to trivially constant GE or ICB values; as can be seen in Figure 3, these models still have considerable variance w.r.t. both metrics despite their identical training accuracies. Inter-task differences were observed in terms of the ability of ICB to bound GE. For example for Exp. A, six of nine EuroSAT binary classification tasks always satisfied ICB (N = 2534), whereas two tasks in particular reduced the overall average. The satisfaction rate was only 68% (N = 468) for the "2 vs. 3" task and 72% (N = 475) for the "6 vs. 7" task (see Fig. A2 and Table A10 for detailed results). These tasks were unusual in that there was a strong inverse relationship between training error and GE, such that reducing the training error resulted in a steady increase in test error, with τ ≈ −0.9 for both tasks, compared to τ = −0.58 for the "0 vs. 1" task. The negative correlation between training and test performance for the "2 vs. 3" task also resulted in a lower mean test accuracy (70.2 ± 2.2% (N = 467)) compared to other tasks, e.g., "0 vs. 1" (93.5 ± 5.3% (N = 415)), consistent with our previous observation that bestperforming models generally satisfy ICB. We further investigated inter-task differences for EuroSAT Exp. B, for which all 10 2 = 45 binary classification tasks were evaluated for 50 seeds each. For the two poorly performing tasks "2 vs. 3" and "6 vs. 7", the ICB satisfaction rate was 78% (N = 50) and 86% (N = 50), respectively. For 34 of 45 tasks (N = 1913), ICB was satisfied for all seeds. Zhang et al. (2017; proposed the "randomization test" after observing that DNNs easily fit random labels. They argue that useful generalization bounds ought to be able to distinguish models trained on natural versus randomized training labels, since generalization is by construction made impossible in the latter case. However, we cannot necessarily expect a theoretical GE bound to exactly hold for models trained on random labels, since the training and test sets are no longer drawn from the same distribution. We therefore pose the following questions: Q1: To what extent does the ICB correlate with the ability to fit random labels? Q2: Can ICB distinguish training sets with natural versus random labels? To address Q1, we aim to find metaparameters that reduce ICB and prevent models from fitting random training labels, while still permitting them to fit the natural training labels. This, however, introduces a potential for confounding if the metaparameter choice alone prevents the model from fitting random labels rather than ICB. For Q2, we hold all metaparameters constant and observe whether ICB changes for randomized training labels.

The randomization test
For simplicity, we consider a two-layer fully-connected ReLU network. We train the model to t = ∞ on the natural training set (N trn = 1000) with 20 different regularization values λ in the range 10 −4 to 10 1 . We measure Kendall's τ ranking between the ICB evaluated on these models and their training accuracies : ICB often distinguishes between natural and randomized training sets. The accuracy w.r.t. the natural training labels ("Natural") and randomized training labels ("Random") is plotted versus the theoretical GE bound (ICB), which is evaluated on the natural training labels. Each data point in the plot corresponds to a unique regularization value λ, which in turn influences the ICB value: Small λ leads to a large ICB value, while increasing λ reduces the ICB and the ability to fit random labels, with the aim of preserving accuracy for natural training labels. The top row corresponds to the "0 vs. 1" task and bottom row the "6 vs. 7" task. Considerable separation between natural and random labels for MNIST, FashionMNIST, and EuroSAT is observed. Differences are harder to distinguish for SVHN and CIFAR-10, but still apparent. ICB is highly correlated with ability to fit random labels in all cases. The broken vertical line for EuroSAT indicates the ICB value for which there is at least a 10% difference in natural versus random training accuracy.
when re-trained with random labels. We find that the ICB value obtained after training on natural labels is strongly correlated with the ability to fit random labels for all five datasets. Furthermore, competitive accuracy for natural training labels is preserved for three of five datasets in doing so (see Fig. 4). Intuitively, we expect I(X; Z) to be smaller after training on natural labels, since training on random labels requires memorization of random data, i.e., the opposite of compression. However, note that to isolate the effect of the training label type on ICB, the training accuracy must also be controlled, as higher accuracy generally requires greater complexity and thus larger I(X; Z). This intuition is consistent with our results, as both I LB and I UB increase monotonically with the training accuracy for both training label types (see Table 2). Table 3: Ability of ICB to separate natural versus random training labels is a good predictor of ICB satisfaction rate by task. The row "ICB rand @X%" 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 §4.1, Exp. A. The column τ indicates the rank correlation between ICB rand @X% and Sat. (%) over the nine tasks. Columns sorted by ascending order of ICB rand @X%.
The randomization test identifies tasks with low ICB satisfaction rate Recall from §4.1 that three binary classification tasks were responsible for reducing the ICB satisfaction rate below 100% for EuroSAT: "2 vs. 3" (Sat. 68%), "6 vs. 7" (Sat. 72%), and "3 vs. 4" (Sat. 97%) for Exp. A. 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 a 10% or greater percentage difference was detected between the natural and random training-sets (see, e.g., the vertical broken line in Fig. 4). The "2 vs. 3" task required the smallest ICB (7.5%) before the difference in label type became apparent. The "6 vs. 7" task had the next highest ICB of 10.0%, followed by "3 vs. 4" with 11.2%. The other six tasks-that have 100% satisfaction rate-have strictly greater ICB (Table 3). Similar results are observed for CIFAR-10 using a 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 ICB rand @5%. Therefore, the training-set based randomization test-which only required training a single model here-may be used to help identify when ICB performs well as a GE bound for a variety of models (e.g., the thousands of models that were considered in Exp. A). Our adaptation of the well-known randomization test complements the list of factors already identified in §4.1 as affecting ICB satisfaction rate.

Vacuous or non-vacuous?
Models with high test accuracy are the more likely to be deployed in practice. To evaluate whether ICB is non-vacuous and close enough to GE to aid model comparison, for each dataset we selected the model with the smallest ICB value among the top-three most accurate models. The ICB values are considerably less than 50% in all cases, satisfying the basic definition of non-vacuous for a binary classification task (Table 4). For Exp. A, the smallest difference between ICB and GE occurred for the CIFAR dataset, with a GE of 5.6% compared to an ICB value of 7.6% for 1966 training samples (

Relationship between theoretical bound and generalization error
Here, we evaluate the ability of ICB to rank GEs in terms of Kendall's rank correlation coefficient, τ . Our analysis of correlation between a complexity metric and empirical GE is inspired by a previous study and NeurIPS competition (Jiang* et al., 2019;Jiang et al., 2021). Figure A13 helps motivate the use of the ICB for ranking GE rather than using its constituent complexity metric I(X; Z), based on a subset of Exp. B metaparameters.
An issue with correlation analysis is that the training-set classification error or proxy loss can serve as a good predictor of GE, therefore Jiang* et al. (2019) train models to a fixed training loss to control for confounding effects. However, fixing the training loss limits the extent of metaparameter exploration. For example, a complexity metric or GE bound may rank GEs of overfitted models well, but perform poorly for early-stopping. To maintain a broad scope, we follow both Exp. A & B procedures and treat the train-set accuracy as a baseline for comparison against ICB, then evaluate overfitted models separately.  (Gilmer et al., 2019) and FGSM (Goodfellow et al., 2015). These perturbations are appropriate for evaluating the robustness of infinite-width networks trained by GD, which behave as linear functions of their parameters (Lee et al., 2019). It can be shown that a classifier's error rate for a test set corrupted by AWGN determines the distance to the decision boundary for linear models (Fawzi et al., 2016) and serves as a useful guide for DNNs (Gilmer et al., 2019). For AWGN, we use a Gaussian variance σ 2 = 1 /16 for EuroSAT and σ 2 = 1 /4 for the other datasets. For FGSM, we use a ∞ -norm perturbation of size 4/255 for inputs x ∈ [−1, +1]. In terms of ranking (Clean, AWGN, FGSM) GEs by aggregating all nine tasks for Exp. A, ICB performs better than the training accuracy baseline for MNIST (Table A6) and FashionMNIST (Table A7); slightly worse than the baseline for SVHN (Table A8) and EuroSAT (Table A10); roughly on par with the baseline for CIFAR (Table A8). All overfitted models from the Exp. A procedure have a positive τ -ranking between ICB and the three GE types for all datasets (Table 5). Thus, ICB outperforms the training accuracy baseline (τ = 0) here.
For Exp. B, there was considerable variance in τ -rankings among the 45 binary classification tasks for each dataset. Although the median ranking was positive for all datasets, the baseline achieves a higher median ranking than ICB for all three error types (Clean, AWGN, FGSM) (Fig. A12).

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 attempted to falsify ICB by evaluating it throughout training, rather than at a 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 split. iii) We considered robust GE in addition to standard GE. iv) Our experiments were performed on five datasets.
ICB was consistently satisfied at the expected 95% rate for models with at least 70 − 80% test accuracy, which is encouraging since accurate models are more likely to be deployed in practice. It is, however, more helpful to threshold by training accuracy to establish a regime in which ICB always works well, since one does not assume access to held-out data when evaluating generalization bounds. The relationship between training accuracy and the percentage of models satisfying ICB was unfortunately weaker, despite being nearly 100% for overfitted models. Nonetheless, ICB was satisfied at a high rate of at least 92% of the time for three of five datasets (MNIST, FashionMNIST, and EuroSAT) without excluding any models by accuracy, and the training label randomization test was sensitive to tasks where ICB wasn't satisfied.
Compared to a simple training accuracy baseline, ICB performed well at ranking GE when the classification task was allowed to vary (e.g., grouping errors for 1 vs. 2 classification with those for a 2 vs. 3 task), or when the training accuracy was fixed at 100%. ICB, however, did not always outperform the training accuracy baseline for specific tasks and when GEs took a large range. However, a limited error ranking ability is not necessarily disqualifying for a generalization bound. It is unclear to what extent a generalization bound ought to be able to rank GEs, given that it is by definition merely an upper bound on the error. For example, GEs of 1% and 29% are both compatible with a bound of 30%, which would contribute to a poor ranking in terms of Kendall's τ . When varying one metaparameter at a time-in particular the diagonal regularization coefficient-a strong monotonic relationship is observed between ICB and robust errors AWGN and FGSM.
Relevance to deep learning One should use caution before extrapolating our conclusions based on infinite-width networks to finite-width DNNs. The ability of infinite-width networks to approximate their finite-width counterparts is reduced with increasing training samples (Lee et al., 2019), regularization , and depth (Li et al., 2021). 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 understanding generalization behaviour of deep networks. Kernel learning and deep learning share the ability to exactly fit their training sets yet still generalize well, a phenomenon that other bounds fail to explain (Belkin et al., 2018). We leave the study of ICB in the context of finite-width DNNs to future work, which may require alternative MI estimation techniques.

Related Work
Kernel-regression generalization error Canatar et al. (2021b) derived an analytical expression for the generalization MSE of kernel regression models using a 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 easier to learn than "8 vs 9". Their method has also been extended to predict out-of-distribution generalization error (Canatar et al., 2021a).
An alternative method is the Leave-One-Out (LOO) error estimator (Lachenbruch, 1967). LOO is generally impractical for deep learning due to the computational effort required to train n DNNs from scratch on n different training sets. However, Bachmann et al. (2021) proposed a closed-form expression for the LOO estimator for a single kernel regression model trained once on the full training set. Their estimator shows excellent agreement with test 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 a modest set of labeled data. As a result, however, our GE and ICB estimates have greater variance than those of Bachmann et al..
In this work, we used the infinite-width limit of neural networks for convenience and as a first step to assess the efficacy of ICB; we did not set out to find optimal generalization bounds for kernel regression. An advantage of ICB is that it only requires access to I(X; Z)-a black-box statistic applicable to a wide variety of models beyond kernel regression. Therefore, ICB may become increasingly relevant for deep learning using MI estimators with different assumptions, e.g., with distributional constraints on weight matrices (Gabrié et al., 2018) or log-Gaussian corrections for infinite depth-and-width limits (Li et al., 2021). (2017) develop a PAC-Bayes GE bound and evaluated it on a MNIST binary classification task (classes {0, . . . , 4} vs. {5, . . . , 9}) using the complete training set (N train = 55k) and a ReLU fully-connected NN with 2-3 layers. Although their bound was non-vacuous (≈ 20%), it was several times larger than the error estimated on held-out data (< 1%). A direct comparison with our work is difficult, as we did not use finite-width DNNs. We showed that the ICB yields a smaller (≈ 10%) bound from less than 2000 samples for MNIST binary classification tasks. The PAC-Bayes bound was also evaluated at a single point during training at 20 epochs, whereas we evaluated ICB from initialization to convergence to check for violations and tightness of the bound.  (2017) and Zhou et al. (2019) concern model complexity, whereas ICB is concerned with input data compression by the hidden layers. Both Dziugaite & Roy and Zhou et al. retrained models from scratch to optimize their bound for best results, whereas we did not modify any aspect of the standard gradient descent training procedure or NTK architecture to be more aligned with ICB. Saxe et al. (2018) observed a lack of compression in ReLU networks and argued that compression must be unrelated 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 MI estimation. Other works reported input compression in linear regression (Chechik et al., 2005) and finite-width ReLU DNNs using adaptive binning estimators (Chelombiev et al., 2019). We use MI bounds free from such metaparameters and observe input compression regardless of the nonlinearity type, consistent with Shwartz-Ziv & Alemi (2020).

Input compression and deep learning
The construction of invertible DNNs (Jacobsen et al., 2018) that generalize well has raised questions about a possible connection between compression and generalization of DNNs. However, to the best of our knowledge there have been few attempts to accurately measure information-theoretic compression in deterministic invertible networks. 4 Although MI diverges for deterministic networks (Goldfeld et al., 2019), input compression may be observed in principle by substituting entropy for MI (Strouse & Schwab, 2016). This noise-free limit has also been studied in the context of information maximization (Bell & Sejnowski, 1995). We are excited about future work that may shed light on input compression phenomena and the challenging case of deep, deterministic, finite-width NNs.

Conclusion
We assessed the ICB along three axes of performance: tightness of the bound (e.g., vacuous or non-vacuous), percentage of trials satisfying the bound, and ranking generalization errors. Our empirical results show that input compression serves as a simple and effective generalization bound, complementing previous theoretical evidence. 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 if not more important than the architecture are the metaparameters and duration of model training, all of which influence 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 input compression, which is data-centric, is a more effective complexity metric than model-centric proxies like the number of parameters or depth. Figure 5: We plot I(X; Z) upper (2) and lower (5) bounds corresponding to the illustrative EuroSAT example (Figure 1). Increasing the regularization to λ = 0.5 in b) and λ = 1.0 in c) reduces MI below log(N trn ). Samples to the right of the vertical line in a) where I U B crosses log(N trn ) are discarded for the main analyses. NB: We use natural units ("Nats" or "Shannons") for I(X; Z) here, but we convert to bits when evaluating the ICB.

A.1 Lower bound on MI
We may lower bound I(X; Z) using a bound of similar form as equation 2 based on a batch of N samples: where the expectation is taken over N independent samples from the joint distribution j p(x j , z j ). The main difference between this bound and equation 5 is the inclusion of p(z i |x i ) in the denominator.

A.2 Illustrative example and filtering MI
We empirically verified that equation 5 and equation 2 yield similar results when I UB < log(N trn ) (Fig. A5).

A.3 Bounding generalization throughout training
Loss function We considered GE in terms of MSE in addition to classification error (Fig. A6). This change results in no difference in the overall ICB Sat. for FashionMNIST, an improvement for SVHN from 44.5% to 72.6%, and a small decrease for CIFAR-10 from to 59.3% to 48.7% as well as for EuroSAT from 93.6% to 88.1%.

Activation function
Overall, ReLU networks satisfied ICB more frequently than Erf networks (Table A11).
The following caption applies to Tables A6-10.
Kendall's τ ranking for three generalization error types: Clean, AWGN and FGSM by training accuracy "Train (baseline)" and ICB are presented. One hundred random seeds are used to draw different metaparameters uniform random for each task, for which models are evaluated five (5) times each during training resulting in a maximum of 500 samples per task. The number of valid samples out of 500, i.e., those with I UB (X; Z) ≤ log(N train ) is indicated in the N valid column. ICB % indicates the percentage of samples that satisfy the ICB, i.e., Clean generalization error ≤ ICB. Entries in the "Row average" row are obtained by simply averaging across the nine (9)  Theoretical GE Bound  may differ substantially from "Row average" as this corresponds to aggregating all raw data points and considering them as one task before calculating τ . Bold is used to denote whether the baseline or ICB achieve a better ranking of generalization errors.

A.4 Bounding generalization at steady state
Results for bounding the generalization error at steady state are summarized in Table A11.

A.5 Advantage of ICB versus MI
To gain further insight into ICB, we examine GEs for a specific CIFAR-10 binary classification task (classes 2 and 5) using three different training set sizes. Plotting GEs with respect to I(X; Z) alone yields a poor overall ranking, whereas ICB effectively aligns trials with different training set sizes ( Figure 13).

98 100
Training Accuracy (%)  Training Accuracy (%)  Training Accuracy (%)  Training Accuracy (%)  Figure 11: a) EuroSAT model evaluated throughout training, b) models evaluated at steady state t = ∞, c) select models from a) with ≥ 80% test accuracy.  Table 11: Results for bounding generalization error across five (5) datasets with Input Compression Bound (ICB). For each dataset, all 10 2 = 45 binary label combinations are evaluated for S = 25 − 50 meta-parameter combinations drawn uniform random. The ICB % column indicates the percentage of N trials that satisfy the ICB, where N trials = 10 2 × S. The mean and maximum Clean generalization error is indicated by "Mean Err" and "Max Err" respectively. The training set sample size is indicated by N train . A test set with N test = 2000 is used in all cases except for EuroSAT (N test = 1000). Results are broken down by nonlinearity type as Erf resulted in ICB being satisfied less often.