Rethinking Information-theoretic Generalization: Loss Entropy Induced PAC Bounds
Authors: Yuxin Dong
Tieliang Gong
Hong Chen
Shujian Yu
Chen Li
Venue: ICLR 2024 poster (2024)
Keywords: information theory
generalization bound
learning theory
minimum error entropy
Primary area: learning theory

Abstract: Information-theoretic generalization analysis has achieved astonishing success in characterizing the generalization capabilities of noisy and iterative learning algorithms. However, current advancements are mostly restricted to average-case scenarios and necessitate the stringent bounded loss assumption, leaving a gap with regard to computationally tractable PAC generalization analysis, especially for long-tailed loss distributions. In this paper, we bridge this gap by introducing a novel class of PAC bounds through leveraging loss entropies. These bounds simplify the computation of key information metrics in previous PAC information-theoretic bounds to one-dimensional variables, thereby enhancing computational tractability. Moreover, our data-independent bounds provide novel insights into the generalization behavior of the minimum error entropy criterion, while our data-dependent bounds improve over previous results by alleviating the bounded loss assumption under both leave-one-out and supersample settings. Extensive numerical studies indicate strong correlations between the generalization error and the induced loss entropy, showing that the presented bounds adeptly capture the patterns of the true generalization gap under various learning scenarios.

Published as a conference paper at ICLR 2024
RETHINKING INFORMATION GENERAL- IZATION: LOSS ENTROPY INDUCED PAC BOUNDS
Yu & Chen Li' 1 Xi'an an Jiaotong University. "Huazhong Agriculture University, 'Vrije Universiteit Amsterdam (asoon9805,.adidssgeee .usidis
Yuxin Dong', Tiellang Gong': Hong
yusj9011 | gmail.com, chenh @ hza....za.,, cli @ Liixxtu.edu.cn
ABSTRACT
information-theoretis generalization analysis has achieved astonishing success in characterizing the generalization capabilities of noisy and iterative learning al- gorithms. However, current advancements are mostly restricted to average-case scenarios and necessitate the stringent bounded loss assumption, leaving a gap with regard to computationally tractable PAC generalization analysis, especially for long-tailed loss distributions. In this paper, we bridge this gap by introduc- ing novel class of PAC bounds through leveraging loss entropies. These bounds simplify the computation of key information metrics in previous PAC information- theoretic bounds to one-dimensional variables, thereby enhancing computational tractability. Moreover, our data-independent bounds provide novel insights into the generalization behavior of the minimum error entropy criterion, while our data-dependent bounds improve over previous results by alleviating the bounded loss assumption under both leave-one-out and supersample settings. Extensive nu- merical studies indicate strong correlations between the generalization error and the induced loss entropy, showing that the presented bounds adeptly capture the patterns of the true generalization gap under various learning scenarios.
INTRODUCTION
Employing information-thoun theoretic measures to analyze the generalization properties of learning al- gorithms has recently attracted increasing attention (Xu & Raginsky 2017 Bassily et al. 2018). The core concept involves quantifying the information stored in the model weights about the train- ing dataset, serving a natural indicator of overfitting. These bounds offer several advantages, as the information-theoree algorithm, while the underlying assumptions are considerably more lenient in comparison con- temporary techniques like uniform stability (Hardt et al. 2016 Bassily et al. 2020 Lei et al. 2021) and model compression (Arora et al., 2018: Zhou et al. 2018). Information theorretc generalization
measures are both dependent on the data distribution and the learning
analysis becomes potent tool for characterizing the generalization capabilities of noisy and itera- tive learning algorithms (Negrea et al. 2019
al.
2020; Steinke Zakynthinou 2020 Wang
& Mao 2021 Haghifam et al.) 2020 Neu al. 2021 Raginsky et al. 2021).
Nonetheless, these gencralization bounds are plagued by overestimation, as neural networks can memorize substantial training data while still generalizing well (Nasr et al. 2019). Furthermore, their coarmmation-thhorete foundation Shannon's entropy renders them notoriously hard to com- pute due to the challenge of high- nigh-dimensiooal entropy estimation (Dong al. 2023). A significant advancement was made in (Steinke & Zakynthinou (2020) by adopting a setting where the train- ing set is sampled from larger supersample, and subsequently bounding the generalization error through the mutual information between the selection of the training set and various aspects e.g. pre- dictions for the supersample (Harutyunyan et al.) (021), the loss pairs (Hellström & Durisi (002)). or the loss difference [Wang & Mao 2023). ). Remarkably, these bounds not only exhibit computa- tional tractability due the lower dimensionality of the associated random variables but also provide quantitatively tighter estimates, particularly for large neural networks.
While recent endeavors on computationally tractable generalization bounds have yielded promising outcomes, these bounds are mostly restricted to average-case scenarios, leaving gap in terms of
"Corresoonding author.

---

Published as a conference paper at ICLR 2024
computationally tractable high-probability generalization bounds. Furthermore, these bounds rely on stringent bounded assumptions regarding the loss function, which can be limiting when dealing with long-tailed loss distributions e.g. cross-entropy. In this paper, demonstrate that analyzing the properties of one-dimensional variables is sufficient for characterizing the generalization capa- bilities of learning algorithms. The generalization bounds present address the computational challenges of prior high-probabillty bounds and mitigate the bounded assumption through our pro- posed thresholding strategy. Specifically, our contributions are summarized follows:
We demonstrate that the recently established bounds by Kawaguchi et al. (2023) can be further en- hanced by substituting the mutual information between input and representation with loss entropy. This substitution leads to the derivation of data-independent generalization bounds, which employ both unconditional (Theorem I and conditional (Theorem 2) information measures. Notably, these bounds offer novel insights into the Minimum Error Entropy (MEE) criterion (Principe) 2010): To the best of our knowledge, we introduce the first nnformation-theoreee theoretic generalization bound for MEE by showing that the generalization error scales with O H (E"))/n)) where E represents the prediction error, and n denotes the size of the training set.
We simplify previous data-dependent generalization bounds relying on high-dimensional infor- mation measures with loss entropies. Our refined bounds exclusively involve one-dimensiona variables: the losses or loss differences. These bounds are not only easier to evaluate but also alle- viate the stringent bounded assumption regarding the loss function, under both the leave-one-out (Theorem 3) and supersample (Theorem (4) settings. Furthermore, we introduce novel fast-rate bounds for generalized version of the weighted generalization error (Theorem (5), improving the convergence rate from 1/vii / to 1 1/n when the empirical risk approaches zero. This advancement is further augmented by our thresholding strategy (Theorem (6. which effectively addresses the key limitations of previous fast-rate bounds when tackling long-
long-tailed tailed loss distributions.
We substantiate our theoretical results with comprehensive numerical experiments on synthetic and real datasets, which exhibit distinct correlations between the generalization error and our proposed loss entropy metrics. Furthermore, the data- data-dependent bounds are capable of character- izing the generalization gap patterns across varied deep-learning tasks. Significantly, our square- root and fast-rate bounds consistently improve over the previously tightest high- probabbbitby bound (Hellström & Durisi 2022) under the supersample setting.
2 PRELIMINARIES
We denote random variables by capitalized letters (X), their specific realizations by lower-case letters (z)), and the corresponding spaces by calligraphic letters (A'). Shannon's 's entropy of random variable X is denoted by HX)., while Rényi's a-order entropy of X is denoted by H. (X). The mutual information between random variables X and Y is denoted [(X; Y), and their conditional mutual information given Z is denoted as [(X; Z1Z). We further write X Xly= (or Xly) to represent X conditioned on y. We follow the same setting of (Kawaguchi al. (023) and assume that all loss variables involved in our theoretical analysis are discrete and have finite cardinality. This assumption also aligns well with continuous loss functions, as we discussed in Appendix G.3
Generalization Error
Let 2 X y' denote the instance space of interest, where X' and y represent the input and label spaces, respectively. We define W as the hypotheses space, and é W x 2 + L E R+ as the loss function. The training dataset S = { [ E 2" is constructed by i.i.d sampling from the unknown data-generating distribution μ. Given learning algorithm A that takes S input and provides a hypothesis W e W. our main objective is to investigate the generalization behavior of W. Specifically, we denote - = E(w, Z) for Z ~ μl and L." l(w, Z,) for [L, The generalization error A A(w, S) I(w) Ls(w) is defined as the difference between the population risk L(w)= [ and the empirical risk [s(w)
Σ L." Additionally, we introduce 6" sup=ez ((w. 2) to represent the maximum attainable loss, and B supte(L,n] D." to indicate the maximum samplewise loss given the hypothesis w E W and the dataset S.
Leave-One-Out Setting
The leave-one-out (LOO) setting was recently introduced by Rammal et al. 2022) for generalization analysis. Let St + go+1 be dataset containing i.i.d samples. We denote U
2

---

Published as a conference paper at ICLR 2024
(1i n + 1]) as uniform random variable, representing the single test sample chosen from St- The training St and test Sj datasets are then constructed as S Si \ Zu and S {Zu) We define 1= R the set of all individual samplewise losses and measure the generalization ability of the hypothesis W by the LOO validation error A(W, S, U) Ls (W) (W).
R" fi=1
Supersample Setting
The supersample framework was initially explored by Steinke & Zakynthinou (2020) for general- ization analysis. Let S, (Zz,,, . 2,,1 }
gxx2 be dataset constructed by i.i.d sampling n samples. We denote Ú = {ú.}==1 ~ Uni 13") as n random {0, 1} variables used to separate training and test samples, where U, = indicates that Zn is used for training and Z,, for testing. The training and test datasets are then constructed as S respectively. We define R {Lro L V E Ru the set of all individual samplewise losses, and 12g = { E Rg as the set of loss differences, where ALT = L L The generalization ability measured by the validation error A(W, Ls. Ls, (W).
77, Ji and S, (~ 1-
MAIN THEOREMS
In this section, investigate high-probability bounds to establish connection between loss entropy and the generalization error. We begin by enhancing existing upper bounds presented in (Kawaguchi et al.] (023), considering scenarios where the model remains fixed and independent of the training dataset. Subsequently, we introduce novel data-dependent generalization bounds under both the LOO and supersample settings. Lastly, we put forth fast-rate bounds concerning a generalized ver- sion of the weighted validation error (Zhivotovskiy & Hanneke 2018 Yang et al. (2119).
3.1 DATA-INDEPENDENT BOUNDS
The first part of our analysis demonstrates that minimizing the loss entropy effectively enhances the generalization ability of deep learning models, under the assumption that the network w remains fixed and independent of the training dataset S. Precisely, given arbitrary w E W, random sample Z ~ μ and let L fww, Z), establish the following upper bounds:
Theorem 1. For any y > and > O, with probability at least 1 - over the draw of S:
CT 2h /2
Aww. S) S CH
H(L
+
CH
C Vn
where
C c²u logly///))
1og(2/5)
Bwis
Cf = 7180 +
2 log(2/6)
m174
Theorem 2. For any y and O, with probability least 1 5 over the draw of S:
CTm 2b"0 /2
Aww, S) S V
YY
Cru
where
Ć c" log vn/T)
+ 1og(2(21/8)
71
Čtu 76t0
D 2 logg(2))//0
In this context, m and e represent the dimension and the sensitivity of the nuisance variables respectively, which are the source of randomness in μ.. It is evident that CT C2 C = Ô(1) as + oo (likewise for Õr Õy Öve), exhibiting a convergence rate of 1/ Vn. It is worth noting that benefitted from the adoption of final layer outputs (i.e. losses), our bounds are applicable arbitrary deterministic models and loss functions that can be expressed as f Z + R+, without requirements on the presence of intermediate representation layers as stipulated in (Kawaguchi et al. 2023).
A comparison between Theorem and 2 highlights trade-off concerning the complexity of [}]
(cardinality of the label space): On the one hand, we have (I." S H (I."), ), as conditioning always reduces entropy. On the other hand, Theorem 2 scales linearly with VDJ. resulting in potentially ineffeetive bounds when [}] is large, e.g. regression tasks. When [[L",; ) is large, signifying prominent performance variation across classes, it is advisable to adopt Theorem 2 for tighter upper bounds. Otherwise, the upper bound in Theorem is preferred.
3

---

Published as a conference paper at ICLR 2024
A prominent difference between Theorem 2 and previous data-independent bounds established in (Kawaguchi et al., 2023) lies in the replacement of I [[X; with (L"))), where T rep- resents any intermediate representation generated by the encoder of the model. By recognizing the Markov chain relationship X + T - I conditioned on the label Y and leveraging the data-processing inequality (DPI), rigorously prove that the mutual information T(T:"; X
(L - (L ()) serves as a tighter bound over the objective [(;;T"I)) of the infor- mation bottleneck principle. When the model w deterministic, which is commonly the case for modern deep learning models, we have H X, Y) = O, implying the equivalence between known that the mutual information (X;T"" (Y) can be infinite in certain special cases when X can be deterministically recovered from T (Amjad &
[[L"; ) and H (L) Moreover,
Geiger 2019). Conversely, the loss entropies (I.)) and (I. (Y) are always finite.
Another improvement brought by our bounds is related to the factor CT" which originally involves EIET. (T = t), where T.eH ~ T represents the typical subset of the representation space T This quantity exhibits exponential scaling with (1 > (TT"), necessitating an addi- tional assumption about the probability decay rate 7 to bound C and maintain the convergence rate of 1/ /T. By adopting leave-one-out analysis (see Appendix B and C) when establishing con- centration bounds for multinomial distributions, we overcome this limitation and obtain constant C factors that are independent of L", without any further assumptions.
It is noteworthy that our data- independent bounds provide new insights into understanding the gener- alization of the MEE criterion. Typically, for regression or binary classification tasks, the prediction error is evaluated by F= = Y - (w, X) given the sample 7 ~ Jl, where f represents the encoder. The final loss is then deterministically computed given the loss function l as L E(ET), c.g. the MSE loss f(x) x². Then we have (L)) S H (E") due to the data- eata-processing inequality, which directly indicates that optimizing (E")) minimizes the upper bound in Theorem verifying that MEE enhances the generalization capability of deep-learning models.
Lastly, our results address an important computability issue of previous upper bounds presented by Kawaguchi et al. (2023): accurately calculating the value of T(;T""()) exceedingly challenging due to the high dimensionality of both X and T", particularly for modern large neural networks. This poses additional obstacles when attempting to utilize these bounds assess the generalization ability of deep learning models in practical scenarios. In contrast, our upper bounds only involve L and Y. which are one-dimensional for most traditional learning tasks, making the estimation of both (L"") and H (L"IY) feasible and efficient.
While one may notice that the model w is not always independent of the training dataset S in real applications, theorem I and I offer practical utility in several real-world learning tasks, such as pre-training, where one aims to assess the generalization ability of pre-trained models on a specific dataset. Another relevant task is model evaluation in the validation dataset, for which our bounds provide valuable information on the magnitude and the likelihood of the average validation error deviating from the population risk.
3.2 DATA-DEPENDENT BOUNDS
In the following section, we extend our analysis to encompass data-dependent scenarios, where the model W becomes random variable correlated with the dataset during training. To achieve this, we explore both the LOO and supersample settings to analyze the generalization ability of deep learning models and establish upper bounds for the validation error under both cases.
Theorem 3. For any À E (0, 1) and d > 0, with probability at least 1-6 å over the draw W, WWS,.U. S., U:
A A(W,S.U) < CW v (RW) + CW, where JCW = V2IRN
(cy = log(t) + (2)
by assuming that n+1 - (T. T.W) is Emww-sbbaausien w.r. U for nnw E [0, B...... Theorem 4. For any X E (0, 1) and 8 > O, with probability at least 1 1- 8 over the draw W, S, 0:
A ((W.3..0) s H1 (R- + Ew
Et = // ) ( = loo + log(
where
n
4

---

Published as a conference paper at ICLR 2024
Importantly. it holds that lim, A(W, U)- = A(W, S,), indicating the supersample validation error approximates the generalization eπror when the dataset is sufficiently large. Similarly, we have CYV C2 = ( as n - oc. The parameter implies a trade-off between Rényi's a-order joint entropy of samplewise losses and the probability of generalization, as Ha (X) monotonically de- creases with increasing a. Notably, Theorem scales proportionally with 1/ /n. whereas Theorem 3 does not. This is attributed to the fact that the test loss is only evaluated on single sample Zy under the LOO setting, resulting in higher variance in the validation error. Such a phenomenon is also observed by Rammal et al. 2022 Haghifam al. (2022).
The main advantage of Theorem 3 lies in its applicability under the interpolating regime, where the model achieves zero training loss. In this case, H (R*) simplifies H (L ). which is the entropy of a one-dimensional random variable. This feature enables direct tractability of this upper bound when provided with i.id samples of the test loss LW Similarly. H ((R)) reduces to H([ )= under the interpolating regime, the joint entropy of all samplewise test losses. While this quantity not directly tractable due its high dimensionality, the subadditivity of Shannon's 's entropy could be utilized to establish an alternative upper bound by [( Pi=1) S E (- This
subadditivity property also applies to Rényi's entropy when X RJ 0 (see Appendix E. confirming the tractability of the upper bounds in both Theorem and
Theorem 4 further utilizes the loss difference between training and test loss values to derive strietly tighter bounds, which are denoted as ALW L, 4 This concept was first explored in Wang & Mao 2023), in which it was proven that I(LL,) , ..:) S I(L L. Üt) by apply- ing the DPI. Here we extend this conclusion to the loss entropy metrics by leveraging the con- cavity of Shannon's 's entropy. Specifically, we have that 1 (H(AT.)) ) + H(E.)) s H(T.W) and
(H(AL)) + H(L))) S HH which further yields the following reductions:
H(AL)) 1 (H(2%) + H(L)) S max (H(L)), H(MD) S H(L LM)
The most notable improvement of Theorem 3 and compared to previous data-dependent bounds presented in (Negrea et al. 2019: Rammal et al. 2022, Steinke & Zakynthinou 2020 is the replace- ment of T TWW; S). /(W:U U (S)) and (W;U|S) with H(R"") and H(R ). To see this, we take the LOO setting as an example and leverage the Markov chain relationship: U - St - W - RW conditioned on 5, which demonstrates that (UR)))))) is strietly smaller than I(WUU|S) and I(W; S,(,s) by applying the DPI. By utilizing the independence between U and 3, we have I(R"; U) S I(R";U) + I(U: R I(RW; ;U)) + I(U;S) = I(RW, LRRW UU)).. Similarly, the conditional independence between S and W given S, indicates S( < T(W; Si(Si) + I(W; 5,) L(W; Ši + ((W; ;(W; When the training process A: S + W is deter- ministic (e.g., using full gradient descent or stochastic algorithms with a fixed seed), the randomness of R" is mainly induced by U, which implies H (R"" (U) O. With these in mind, we have
H(n")) v I(R"; ;U) < IRRR ;U})) < I(W: U1Š:) < I(W; S($)) < S()
This verifies our claim that introducing the loss entropy H H(R") constitutes a significant improve- ment over I(W;S) S), I(W; (() and I(W; Ü}S.). The same conclusion can also apply to H (R ). Moreover, these previous bounds encounter the same computational challenge in modern deep learn- ing settings, which is even more severe than estimating T(X;T" Y) due to the considerably higher dimensionalities of both W and S; compared to X or T In contrast, our bounds could be effi ciently approximated by estimating the entropy of one one-dimensional random variables.
Theorems 3 and 4 are versatile and applicable to scenarios where the training process of the model W involves the dataset S. This broadens the range of applications compared to Theorems | and 2. encompassing supervised learning, unsupervised learning, transfer learning, and other contexts. For both Theorems 3 and 4. the key quantities H H(W)) or H(R)) can be further decomposed into HRRW) < (R + (RR)). where RW and R represent the collections of samplewise training and test losses, respectively. Intuitively, training algorithms aim to minimize the training loss, thereby reducing H (R since all training losses tend to approach zero for well-fitted model. At the same time, H (R measures the extent of overfitting, which arises when the model provides incorrect answers to test samples. This illustrates a novel trade-off between training and test loss entropies to achieve the best generalization performance.
5

---

Published as a conference paper at ICLR 2024
In addition to the presented main theorems, our proof technique also holds intrinsic research inter- est. Specifically, we observe the Markov chain W + R + A conditioned on the selection U, where R acts as the "bottleneck" for information flow from W to the evaluation error A (e.g. RW or ) We proceed by investigating typical subset of space R. which satisfies P(R & R.)) ò and [R.| (() By systematically enumerating each element r E R. within this specified subset, we effectively isolate A from W and construct generalization bounds upon concentration in- equalities that exclusively leverage the stochastic nature of U. By taking the union bound across every single element r E R. we establish a connection between sample complexity-basee and dnformation-theoretti analyses, ultimately leading to our conclusive results. While our paper pri- marily investigates the LOO and supersample settings, we underscore potential extensions of such a technique to accommodate alternative sampling scenarios, e-g. in cases of random selecting n < m training samples from supersample dataset comprising total of m samples.
3.2.1 1 FAST-RATE BOUNDS
We now delve into the weighted validation error denoted as Ac(W,S,.U) = Ls, (W) (1+ Ls, (W), where C' is selected positive constant. The introduction of this weighted error enables establishing fast-rate bounds that scale linearly with 1/n instead of the conventional 1/vV rates (Catoni, 2007: Hellström Durisi 2021b). While previous bounds typically adopt a universal value of C for all training losses (Hellström & Durisi 2022: Wang & Mao 2023), we empirically observe that individual sample losses often exhibit a long-tailed distribution in well-trained deep-learning models: the majority of training samples have losses that cluster near zero, while a small number of samples consistently exhibit comparatively high losses even after the training process, significantly influencing the overall empirical risk. Motivated by this observation, we employ distinct values of C2 for each individual training loss T.W. to derive strictly tighter bounds.
Theorem 5. For any K 2 X, E (0, and 8 > 0, if K 2 BW.S. then with probability at least 1 8 over the draw of W, S., U. the following inequality holds:
G/V 1 7
A W, (W,S,U) 0)
1 Σ s
C.W.W. + +GW HI (I(")) G
where
G = log (+) + log (2)
n
C. = lox 22 (22-2222 201
2n
and i.W. = max D. for any i E [1,
In the interpolating regime where training losses approach zero, the weighted validation error sim- plifies to its original unweighted form. Therefore, a convergence rate of 1/n is achieved by letting y - 1 when the empirical risk approaches zero. This characteristic renders the fast-rate bounds par- ticularly valuable when the empirical risk is small or even zero. Conversely, when positive training losses are prevalent, the adaptive modulation of weights C, w.r.t L,W endows the bounds with the versatility to accommodate various loss distributions. In contrast, if a universal constant C' is ap- plied uniformly all training losses, it must satisfy the condition that C 2 suPre(1,,)] Cr inevitably resulting in looser bounds when dealing with non-interpolating scenarios (see Appendix
Notably, the joint entropy H H(R") encompasses all samplewise losses, which facilitates direct com- putational tractability through the subadditivity property inherent in information entropy. In con- trast, the previously established fast-rate high- probbbbbbyblityy generalization bound (Hellström & Durisi 2022) employs the multivariate mutual information I [īe"" ;Ü(,)), which is unfortunately intractable due to the nigh-dimensional nature of the variables RW, U, and S..
However, it is evident that the bound presented in Theorem exhibitts linear scaling with BWS., the largest samplewise loss. In scenarios involving long-tailed loss distributions (e.g. cross-entropy), this factor can be considerably larger than the subgaussian norm in Theorem the Le norm of loss differences in Theorem 4 Consequently, the improvement in the convergence rate may diminish in practical evaluations when compared to these previously established bounds.
In light of this observation, we further explore scenarios where к < BW... This naturally leads to the consideration of thresholding strategy aimed at deriving tightened fast-rate generalization

---

Published as a conference paper at ICLR 2024
Pearson corneationn 0. 3.56
635
0.5
Metric
Correlation
Num. params.
-0.0294
0.2
0.0
[W]|F ((:TTW)
-0.0871
0.3712
0.5
I(X:T""IX)
0.3842
-0.2
T(S; W)
0.0211
0.4
Width
-1.0
Witth
256
I(S; W + ((X;T"))
I(S: + I(X;
0,4130
0,3928
125
128
-0.8
64
-1.5
64
H(L")
0.5611
H(L"V)
0.6350
-1.0
0.2 Genersization gep loss
Generalization gap loss
(a) Metric HL)")
(b) Metric (Y)
(c) Pearson correlation analysis
Figure 1: Pearson correlation analysis between the generalization error and different metrics for 5-layer MLP trained on synthetic 2D Gaussian datasets. (a), (b): The correlations of H (L")) and H (l) with the generalization gap, respectively. (c): Comparison of Pearson correlation coeffi- cients for different metrics and the generalization gap.
bounds. With an arbitrary threshold k. > 0 and a samplewise loss L, it can be verified that L = I + L-* where L min(L, r)) and L-* max k. 0). By employing the strategies outlined in Theorems 4 and 5 we can derive generalization bounds that simultaneously leverage the advantages of fast convergence rates and the modest L2 scaling factor:
Theorem 6. For any > y, >,, A2 (0, 1) and ā > O, with probability least 8 over the draw of W, Sz. U, the following inequality holds:
W. LD. + GN HI (RWW.r) + GW
H1
(R
[RW. ("
G
W, S., 0) S
C.L.
+
G.
n
where RW.K- { ,,1
Way
R (AL, - ALW
I,,11
W and
log (2 2-2nme
G. 9
2x log
GW b1 log (2) + +log()):
C==-
1,
G E A - GW X log (3) log (o).
Theorem introduces a manual threshold k to partition each samplewise loss into L = L Combining with the techniques developed in Theorems 4 and S we subsequently establish upper bounds for these two components. Consequently, the previous factor BW. replaced by the manually set threshold к for the first component L* and by the more moderate L2 norm of loss differences for the second component ---* Our experimental findings indicate that this bound is significantly tighter than both Theorems and (see Appendix [.2).. It is worth noting that this thresholding technique can also be applied to the bounds presented in (Wang Mao 2023), yielding improved bounds for the expected generalization error when dealing with long-tailed loss distribu- tions (see Appendix F.2 Furthermore, the joint entropy of all training losses, denoted as H [R ), serves as a tighter alternative to the terms related to loss variance and sharpness, which were utilized in (Wang& & Mao 2023) to derive fast-rate expected generalization bounds (sce Appendix E.3
4 NUMERICAL RESULTS
In this section, we conduct empirical comparisons between the generalization bounds established in this paper and the previous high-probability bounds proposed in (Kawaguchi et al., 2023 Hellström & Durisi 2022). Our evaluation involves two sets of experiments: Firstly, we investigate data- independent bounds using synthetic 2D Gaussian datasets by employing a simple MLP network as the classifier. which follows the same learning settings (Kawaguchi al. 2023). Secondly, we evaluate deta-dependent bounds by training more complex neural networks on worldworld image classification datasets (4-layer CNN MNIST (LeCun & Cortes 2010) and ResNet-50 (He al.;
7

---

Published as a conference paper at ICLR 2024
Sigams-Moo: Posi Disary
Erer
0.5
Ery Giaare-ood
Error
0.3
1000
5030
12
(a) MNIST, Adam
(b) CIFARIO, SGD
(c) MNIST, SGLD
Figure 2: Comparison of the generalization gap in 3 different deep-learning scenarios, along with theoretical upper bounds including the square-root bound (Theorem 4). the fast-rate bound (Theorem
6) and the binary KL bound (Theorem in (Hellström & Durisi 2022 )
2016 on CIFARTO (Krizhevsky et 2009 ). These experiments follow the same deep learning
settings those in (Harutyunyan et al. 2021 Hellström & Durisi 2022 Wang & Mao 2023). In
all of these experiments, we utilize the cross-entropy loss LCE to quantify the generalization error
and adopt the empirical risk minimization criterion to find the hypothesis W.
4.1 SYNTHETIC DATA
For the first classification task, utilize synthetic 2D Gaussian datasets and employ 5-layer MLP, comprising a variational encoder and a deterministic classifier. The experimental settings are consistent with those in (Kawaguchi al. 2023), where train total of 216 different models, covering various architectures, weight decay rates, dataset draws, and random seeds. The optimiza- tion of the hypothesis is performed using the reparameterization trick (Kingma et al.) 2015) in an end-to-end manner. A Monte-Carle sampling-ban [X;TT") T and [X;TW]] and IWW S) computed based on the posterior distribution modeled by the SWAG method (Mandt et al., 2017; Maddox et al. 2019). The computations of H (L") and H (L are relatively straightforward, such that simple kernel density estimator suffices.
estimator is employed to estimate the values of
Here, we use Gaussian kernels and determine the kernel width according to the rule-of-thumb cri- terion. To empirically evaluate the predictive power of different metries on generalization, we fol- low the approach in previous works (Galloway et al. 2023 Kawaguchi et al.) (203) and adopt the Pearson correlation analysis. As depicted in Figure both H(L") and ( exhibit stronger correlations with the generalization error in comparison to other metrics, including the number of parameters, the F-norm of the hypothesis, information bottleneck I I(":"") related metrics, and the onput-output mutual information I(W; S). This observation highlights the capabilities of loss entropy metrics in assessing the generalization ability of deep learning models. Moreover, the ob- servation that ((I. " Y)) outperforms H(T") supports our analysis, demonstrating that Theorem is more effective than Theorem when the cardinality of the label space [}] is finite.
4.2 REAL-WORLD LEARNING TASKS
In order to assess information-theerriic generalization bounds within the context of modern deep- learning tasks, we adhere the experimental configurations established by Harutyunyan et al. (2021). Specifically, we consider training a 4-layer CNN on binarized MNIST data, which is re- stricted to comprise only digits 4 and 9. Additionally, we engage in fine-tuning a pre-trained ResNet- 50 model on the CIFAR10 dataset. A comprehensive illustration of the training algorithm, network architecture, and experimental setup can be found Appendix F
As of our current knowledge, the most stringent fast-rate high- high-probability information-theoree generalization bound available in the literature is the binary KL bound (Theorem 7 in (Hellström & Durisi 2022) employing T(RW; Ü(S.). Note that this quantity computationally intractable due to its high dimensionality, and here we adopt a bound approximation: Σx=, [[L L,; Ü.) (see Appendix F.2 for the proof). In addition this baseline (Binary KL), primary comparison centers around the square-root generalization bound Theorem E (Square-Rooe -oott) and the fast-rate generalization bound in Theorem (Fast-Rate).
8

---

Published as a conference paper at ICLR 2024
The final outcomes presented in Figure 2 As can be seen, these upper bounds effectively cap- ture the patterns of the generalization gap. Across the three distinct learning scenarios, both our square-root bound and fast-rate bound exhibit significant improvements over the lower-bound ap- proximation of the binary KI. bound. This observation substantiates our previous discussion that our bounds can adeptly accommodate long-tailed loss distributions, while the binary KI. bound is influenced by the maximum attainable loss value. Moreover, the fast-rate bound consistently out- performs the square-root bound, particularly in more challenging learning scenarios (CIFAR 10 and SGLD). This provides empirical validation for the efficacy of our thresholding strategy.
Furthermore, it is evident from Figure 2c that the binary KL bound is especially loose in the initial epochs. This behavior arises due to the adoption of a universal C: according to the expression of C. in Theorem [ a 6 using distinct C; particularly improves the bound when the majority of loss values are close to the threshold K, which happens at the early stages of the training process. In con- trast, our loss entropy-base generalization bounds overcome this limitation, consistently offering accurate predictions of the actual generalization ertor.
5 RELATED WORKS
This work is intricately linked to extensive literature concerning information-theorede generaliza- tion bounds. The seminal contributions by Russo & Zou 2016); Xu & Raginsky (2017); Russo & Zoo 2019) initially motivated the characterization of generalization properties through mutual information between training samples and model parameters. This approach has demonstrated its efficacy in dissecting the behavior of noisy and iterative learning algorithms, exemplified by its ap- plication in SGLD (Negrea et al., 2019 Waan et al.) (02T) and SGD (Neu et al., 2021; Wang & Mao 2021 Dong et al. (023). Furthermore, it serves as a scaffold for subsequent enhancements by encompassing techniques such as conditioning HHafez-Kolabe et al. (020), the chaining strat- egy (Asadi et al., 2018; Zhou al. 2022 Clerico et al. 2022). the random subsets or individual techniques (Bu et al., 2020; Rodríguez- Gálvez et al. 2021) 1), and conditional information measures (Steinke& & Zakynthinou 2020 Haghifam et al. 2020
Remarkably, Harutyumyan et al.] (2021) introduced a novel approach to establish generalization bounds by leveraging conditional mutual information (CMI) between the model's output and super- sample variables. This technique treats the neural network as a "black box", resulting in a substantial reduction in the dimensionality of random variables used in constructing generalization bounds, ren-
dering them directly tractable. Building upon this foundation, Hellström & Durisi (2022); Wang & Mao 2023) further extended the approach by incorporating evaluated losses and loss differences to derive tighter bounds. Another notable exploration in the CMI framework is the leave-one-out setting, as recently investigated by HHaghifam et al. (2022): Rammal al.] (2022). This variant sig- nificantly reduces the required number of samples from 2 to just
The information bottleneck (IB) principle (Tishby al., 2000) and the minimum error entropy (MEE) criterion (Erdogmus & Principe| 2000) play essential roles in designing supervised learning algorithms under the anformation-theoreel is developed based on the concept of minimal sufficient statistics and is widely adopted reg- ularization technique (Alemi et al.] 2016, Kolchinsky & Tracey 2017 Kolchinsky et al,, 2019). Notably, Kawaguchi et al. (2023) provides the first information thhorretc generalization bound for the IB principle, revealing that the generalization error scales roughly Ö(V D(VT((X; /n)/). The MEE criterion is recognized for its robustness against outliers or covariate shifts, attributed to its capacity to capture high-order statistics of error distributions, and thus find applications in a variety of learning tasks (Hu et al. 2013
learning framework (Principe) 2010). The IB objective
Shen & Li 2015 Guo et al. 2020).
6 CONCLUSION
In this paper, we introduce a series of high-probability information--heoretic generalization bounds based on loss entropy. We demonstrate that these bounds are superior in tightness compared to previous counterparts established in (Kawaguchi et al. 2023: Hellström & Durisi 2022). both the- oretically and empirically. Our numerical experiments substantiate that our bounds are consistently predictive of the true generalization gap across various deep-learning scenarios, validating the efficacy of our theoretical analysis.
both synthetic and real-world datasets

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported by National Key Research and Development Program of China(No. 2021ZD01 10700), National Natural Science Foundation of China (62106191, 12071 166, 02192781,6172 1002) Innovation Research Team of Ministry Education (IRT.17R86), Project of China Knowledge Centre for Engineering Science and Technology and Project of Chinese academy of engineering "The Online and Offline Mixed Educational Service System for 'The Belt and Road' Training in MOOC China"
Reproducibility Statement. To ensure reproducibility, we include complete proofs of our theoreti- cal results in Appendix B C and D detailed explanations of our experimental settings in Appendix and source codes at https: /ttg//ggtth///////// com/ /Yuinnuxinnn. wawiinDoong///oao -aneess-Entrop Entropy
REFERENCES
Alexander A Alemi, Ian Fischer, Joshua V Dillon, and Kevin Murphy. Deep variational information bottleneck. In International Conference on Learning Representations, 2016.
Amiran Ambroladze, Emilio
and John Taylor. Tighter pac-bayes bounds. Advances in neural information processing systems, 19, 2006.
Gholamali Aminian, Samuel N Cohen, and Lukasz Szpruch. Mean-field analysis of generalization errors. arXiv preprint ar3iv:22306. /623, 2023.
Rana Ali Amjad and Bernhard C Geiger. Learning representations for neural network-based clas- sification using the information bottleneck principle. IEEE transactions on pattern analysis and machine intelligence, 42(9): 2019.
Sanjeev Arora, Rong Ge. Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pp- 254-263. PMLR, 2018
Amir Asadi, Emmanuel Abbe, and Sergio Verdú. Chaining mutual information and tightening gen- eralization bounds. Advances in Neural Information Processing Systems, 31, 2018.
Jean-Yves Audibert. A better variance control for pac- pay-saaesian classification. Preprint, 905. 2004.
Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Yehudayoff.. Learners that use little information. In Algorithmic Learning Theory. pp. 25-55 PMLR, 2018
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33: 4381-4391, 2020.
Luc Bégin, Pascal Germain, François Laviolette, and Jean-Francis Roy. Pac-bayesian theory for transductive learning. In Artificial Intelligence and Statistics, pp. 105-113. PMLR, 2014.
Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli. Tightening mutual information- bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1): 121-130, 2020.
Olivier Catoni. Pac-bayesian supervised classification: the thermodynamics of statistical learning. arXiv preprini arXiv:07/2.02448, 2007.
Zixiang Chen, Yuan Cao, Quanquan Gu, and Tong Zhang. A generalized neural tangent kernel analysis for two-layer neural networks. Advances in Neural Information Processing Systems, 33: 13363-13373, 2020.
Eugenio Clerico, Amitis Shidani, George Deligiannidis. and Arnaud Doucet. Chained generalisation bounds. In Conference on Learning Theory, pp. 4212-4257. PMLR, 2022.
Yuxin Dong, Tieliang Gong, Hong Chen, and Chen Li. Understanding the generalization ability of deep learning algorithms: A kemeliized rényi's entropy perspective. In Proceedings of the Thirty- Second International Joint Conference on Artificial Intelligence, IJCAI-23, pp. 3642-3650, 2023.
10

---

Published as a conference paper at ICLR 2024
Gintare Karolina Dziugaite and Daniel M Roy. Data-dependent pac- pac-bayes priors via differential privacy. Advances in neural information processing systems, 31, 2018.
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy. On the role of data in pac-bayes bounds. In International Conference Artificial Intelligence and Statistics, pp. 604-612. PMLR, 2021.
Deniz Erdogmus and Jose C Principe. Comparison of entropy and mean square error criteria in adaptive system training using higher order statistics. Proc. ICA, volume 5. Citeseer, 2000.
Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Generalization error bounds via rényi-, f-divergences and maximal leakage. IEEE Transactions on Information Theory, 67(8): 4986-5004, 2021.
Andrew Foong. Wessel Bruinsma, David Burt, and Richard Turner. How tight can pac-bayes be in the small data regime? Advances in Neural Information Processing Systems, 34:4093-4105, 2021.
Angus Galloway, Anna Golubeva, Mahmoud Salem, Mihai Nica, Yani Ioannou, and Graham Taylor. Bounding generalization error with input compression: An empirical study with infinite- width networks. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL
atttps://ppenrev/e/ net "oorum?id=jbbBUUSl
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. Pac-bayesian learn- ing of linear classifiers. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 353-360, 2009.
Peter D Grünwald and Nishant A Mehta. Fast rates for general unbounded loss functions: from erm to generalized bayes. The Journal of Machine Learning Research, 21(1):000-21199 2020.
Xin Guo, Ting Hu, and Qiang Wu. Distributed minimum error entropy algorithms. The Journal of Machine Learning Research, 21(1):4968 -99986888999,,, 2020.
Hassan Hafez-Kolahi, Zeinab Golgooni, Shohreh Kasaei, and Mahdieh Soleymani. Conditioning and processing: Techniques to improve information--hheortie generalization bounds. Advances in Neural Information Processing Systems, 33:1 14457-16667,, 2020.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, itcrative algorithms. Advances in Neural Information Processing Systems, 33:9925-9935, 2020.
Mahdi Haghifam, Shay Moran, Daniel M Roy, and Gintare Karolina Dziugiate. Understanding generalization via leave-one-out conditional mutual information. In 2022 IEEE International Symposium Information Theory (ISIT), pp. 2487-2492. IEEF, 2022.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225-1234, PMLR, 2016.
Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan. information-thcoree generalization bounds for black-box learning algorithms. Advances in Neural Information Pro- cessing Systems, 01124670-24682 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Fredrik Hellström and Giuseppe Durisi. Generalization bounds via information density and condi- tional information density. IEEE Journal on Selected Areas in Information Theory, 1(3):824-832 2020.
Fredrik Hellström and Giuseppe Durisi. Data-dependent bayesann bounds in the random-subsed setting with applications to neural networks. In Workshop on -nf--heeretic Methods Rigorous, Responsible, and Reliable Mach. (eaR3()) Virtual conference, 2021a.

---

Published as a conference paper at ICLR 2024
Fredrik Hellström and Giuseppe Durisi. Fast-rate loss bounds via conditional information measures with applications to neural networks. In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 952-957, IEEE, 2021b.
Fredrik Hellström and Giuseppe Durisi. A new family of generalization bounds using samplewise evaluated cmi. Advances in Neural Information Processing Systems, 15:10108-1012, 2022.
Fredrik Hellström, Giuseppe Durisi, Benjamin Guedj, and Maxim Raginsky. Generalization bounds: Perspectives from information theory and pac-bayes. arXiv preprint wrXiv:2309.04381, 2023.
Ting Hu, Jun Fan, Qiang Wu, and Ding- Xuan Zhou. Learning theory approach to minimum error entropy criterion. The Journal of Machine Learning Research, 14(1):377-397, 2013
Kenji Kawaguchi, Zhun Deng, Kyle Luh, and Jiaoyang Huang. Robustness implies generalization via data-dependent generalization bounds. In International Conference on Machine Learning, pp- 10866-10894. PMLR, 2022.
Kenji Kawaguchi, Zhun Deng, Xu Ji, and Jiaoyang Huang. How does information bottleneck help deep learning? In International Conference Machine Learning. PMLR, 2023.
Durk P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparameteri- zation trick. Advances in neural information processing systems, 28, 2015.
Artemy Kolchinsky and Brendan D Tracey. Estimating mixture entropy with pairwise distances. Entropy, 19(7):361, 2017.
Artemy Kolchinsky, Brendan D Tracey, and David H Wolpert. Nonlinear information bottleneck. Entropy, 21(12):1181, 2019.
Wouter M Koolen, Peter Grünwald, and Tim Van Erven. Combining adversarial guarantees and stochastic fast rates in online learning. Advances Neural Information Processing Systems, 29, 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images, 2009.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database, 2010. URL httttp/p///an lecun wttp//ooom/ceecceecc /mnss//
Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of
stochastic gradient methods for minimax problems. In International Conference Machine Learning, pp. 6175-6186. PMLR, 2021.
Guy Lever, François Laviolette, and John Shawe-Taylor. Tighter pac-bayes bounds through distributionn-deeendent priors. Theoretical Computer Science, 473:4-28, 2013.
Wesley Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson. A simple baseline for bayesian uncertainty in deep learning. Advances in neural information processing systems, 32, 2019.
Stephan Mandt, Matthew D Hoffman, and David M Blei. Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18:1-35, 2017.
David McAllester.
A pac-bayesian tutorial with dropout bound. arXiv preprint arXiv:1307.211
2013.
Zakaria Mhammedi, Peter Grünwald, and Benjamin Guedj. Pac-bayes un-expected bernstein in- equality. Advances in Neural Information Processing Systems, 32, 2019.
Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white- box inference attacks against centralized and federated learning. In 2019 IEEE symposium security and privacy (SP), pp. 739-753. IEEF, 2019.
12

---

Published as a conference paper at ICLR 2024
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information-theore theorretc generalization bounds for sgld via data-dependent estimates. Advances in Neural Information Processing Systems, 32, 2019.
Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M Roy. Information- theoretic generalization bounds for stochastic gradient descent. In Conference on Learning The- ory, pp. 3526-3545. PMLR, 2021.
Naoki Nishikawa, Taiji Suzuki, Atsushi Nitanda, and Denny Wu. Two-layer neural network on infinite dimensional data: global optimization guarantee in the mean-fiele regime. Advances in Neural Information Processing Systems, 35:32612-32623, 2022.
Atsushi Nitanda, Denny Wu, and Taiji Suzuki. Particle dual averaging: Optimization of mean field neural network with global convergence rate analysis. Advances in Neural Information Processing Systems, 14119608--96211 2021.
Jose C Principe. Information theoretic learning: Renyi's 's entropy and kernel perspectives. Springer Science & Business Media, 2010.
Maxim Raginsky, Alexander Rakhlin, and Aolin Xu. Information -hhooretic stability and generaliza- tion. Citemattion-Thoreette Methods in Data Science, pp. 302, 2021.
Mohamad Rida Rammal, Alessandro Achille, Aditya Golatkar, Suhas Diggavi, and Stefano Soatto. On leave-one-out conditional mutual information for generalization. In Alice H. Oh, Alekh Agar- wal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL http:: wwwp//eieeeeeeeeeeeeeeee / net http::/weteeeettee///ee/e htte:/oormiiddvvallii 8BGg
Omar Rivasplata, Ilja Kuzborskij, Csaba Szepesvári, and John Shawe- Taylor. Pac-bayes analysis beyond the usual bounds. Advances in Neural Information Processing Systems, 33:1 6633--1645, 2020.
Borja Rodríguez-Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. On random subset generalization eтrоr bounds and the stochastic gradient langevin dynamics algorithm. In 2020 IEEE Information Theory Workshop (ITW), pp. 1-5. IEEE, 2021.
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pp. 1232-1240. PMLR, 2016.
Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302-323, 2019.
Pengcheng Shen and Chunguang Li. Minimum total error entropy method for parameter estimation. IEEE Transactions Signal Processing, 63(15):4079-400) 4090, 2015.
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, pp. 3437-3452. PMLR, 2020.
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/0004055, 2000.
Hao Wang, Yizhe Huang, Rui Gao, and Flavio Calmon. Analyzing the generalization capability of sgld using properties of gaussian channels. Advances in Neural Information Processing Systems, 34:24222-242:33 2021.
Ziqiao Wang and Yongyi Mao. On the generalization of models trained with sgd: Information- theoretic bounds and implications. In International Conference on Learning Representations, 2021.
Ziqiao Wang and Yongyi Mao. Tighter information-theorrde generalization bounds from supersam- ples. In International Conference on Machine Learning. PMLR, 2023.
Aolin Xu and Maxim Raginsky. Information theoretic analysis of generalization capability of learn ing algorithms. Advances in Neural Information Processing Systems, 30, 2017.
13

---

Published as a conference paper at ICLR 2024
Jun Yang, Shengyang Sun, and Daniel M Roy. Fast-rate pac-bayes generalization bounds via shifted rademacher processes. Advances in Neural Information Processing Systems, 32, 2019.
Tong Zhang. Information-thherrtiic upper and lower bounds for statistical estimation. IEEE Trans- actions on Information Theory, 1204):107-1132,, 2006.
Nikita Zhivotovskiy and Steve Hanneke. Localization of ve classes: Beyond local rademacher complexities. Theoretical Computer Science, 742:27-49, 2018.
Ruida Zhou, Chao Tian, and Tie Liu. Stochastic chaining and strengthened information-theoretic generalization bounds. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 690-695. IEEE, 2022.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P Adams, and Peter Orbanz. Non-vacuous gen- eralization bounds at the imagenet scale: a pac-bayesian compression approach. In International Conference on Learning Representations, 2018
14

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
Prerequisite Definitions and Lemmas
15
Proof Theorem
B.1
Properties of the Typical Subsel
16
B.2
Decomposition of the Generalization Error
17
B
Bounding each Term in the Decomposition
19
B.4
Completing the Proof
21
C
Proof Theorem 2
22
Properties of Conditional Typical Subset
................................
22
Decomposition of the Generalization Error
23
Hounding each Term in the Decomposition
24
C,4 Completing the Proof
27
D Proof of Data-Dependent Bounds
28
D.I Properties of the Typical Subsel
................................
28
D.2 Completing the Proof
................................
29
Fast-Rate Generalization Bounds
31
E
Additional Theoretical Results
36
E.1
Subadditivity of Rényi's Entropy
36
E.2
Tightening Previous Bounds by Thresholding
37
E.3
Comparison with Variance and Sharpness Based Bounds
39
F
Experiment Details Additional Results
40
Synthetic Experiments
40
F2
World Learning Tasks
42
G
Further Discussions
45
G
Additional Related Works
45
G.2
Convergence Rate of LOO Bounds
................................
46
Discretization of Continuous Loss
46
Interpolating Regime
47
A PREREQUISITE DEFINITIONS AND LEMMAS
Unless otherwise noted, we use log to denote the logarithmic function with base
Definition 1. (Subgaussian) random variable X is a-subgaussian for any p R. R[exp(p(X--
E[X]))] & exp(p2o2/1)
Definition 2. (Kullback-Leibler Divergence) Let P and Q be probability measures on the same space X. the KL divergence from P to Q is defined as KL(P || Q) p(x) (og(p(x)/((x)) dr.
Definition 3. (Mutual Information) Let (X, ) be pair of random variables with values over the space X x y. Let their joint joint distribution be Рx, and the marginal distributions Px and Py re- spectively, the mutual information between X and Y is defined T(X;Y) [L(Pxx || Px Py).
15

---

Published as a conference paper at ICLR 2024
Lemma 1. (Lemma 3 in Kawaguchi al. 2022 Let the vector X (X1," .. .n) follow the
multinomial distribution with parameters m and = (p1. Pn). Let 01," .. an 2 be fixed such that Σi=1 0:P; # 0. Then for any > 0,
X1 m
me²
di
Pi
>
< exp
3
where B = -:= a.Pt-
Lemma 2. (Lemma I in Xu & Raginsky 2017 Let (X, Y) be pair of random variables with joint distribution Px,y and let Y be an independent copy of If f(z, y) is measurable function such that Fx,y (xx,( exists and f(X,y, Y) is o-subgaussian, then
[x,r(((X Ex,rIf(X,Y)I) V20-I(X;Y).
Lemma 3. (Donsker-Varadhan formula) Let P and Q be probability measures defined on the same measurable spuce, where P is absolutely continuous with respect Q. Then
KL((P Q) sup [ log R.q (e 1
X
where is any random variable such that e is Q-integrable and Ep Ep(X] [X] exists.
B PROOF OF THEOREM
We define the data generating process as (0(Y. VV)Y) Y), where Y is the randomly generated label, 0 is some hidden deterministic function and V = (Vi) E V C I are i.i.d nuisance variables. For any y E y, define the sensitivity c. of the model w.r.t the nuisance variable V;;
sup (Pa
log(pi () 0y (21, Uy Um).
llog(pı ()(w,, 0,(v1." .., Um vm). v)
where pr(() = IP(L"= = and (,(v) = 02y, v). We then define the global sensitivity of w as: sup Ch and ct = Er( ie 1m
Given the hypothesis w E W, we denote the set of all possible loss values by
_ (l(w, 0y((), y) : E V, E V}.
For any 7 > O, then define the typical subset of L by
m log( vn/7)
IE L log (()) H(I.)) S eM
(1)
Note that b is deterministic given the fixed hypothesis w E W.
B.1 PROPERTIES OF THE TYPICAL SUBSET
Lemma 4. For any y O, we have
P(L" & fTm) <
7 VT"
and
m log vn/r)
c < exp H(L") + c
2
Proof. Consider following function
[ v) log (v)), where hy(1) ((w,0,(r)) (y())).
16

---

Published as a conference paper at ICLR 2024
Let Py( = P(Y = v). po(u) P(V u) and by (1) h1y(()
fu E V: h2(0)) 1), we have
Ey,] = Σ (v(
Σ
log
yEy
NEV
Σ
Po(1)
Σ
Σ
((g)(()))))))
yEY
IEL" vehy (11
Σ
Σ NEV
Po(y) Σ
Po(u)
log Pr()
IEL"
DEh, (1)
Σ 1E2
Pi(l) log
(I.
Therefore, by applying McDiarmid's inequality on f(V) log (L"), we have
2e
P( - log pi H(L") 2 E) S exp
(2)
m
Take 8 as the RHS of we have
m log(1/6)
c= cd
(3)
2
Combining with we select 6 = 7/ n and
F(L" Th
7
nn
We now consider the size of the typical subset. For any I E Ly, we have
Pog (1) - H(L") S
- po)) (I"") +
- -I - 6 S log (1))
exp( exp(-H(L*)) - (I)..
This implies that
E Σ
p:(1) 2 Σ
exp( exp(-Hop exp(-H(L") (( c) 1.: 1 exp(-H(L") c).
LECY
LEC
Combining with 3 we finally get
m log( (T/7)
C <
exp
H(L") + c
2
B.2 DECOMPOSITION OF THE GENERALIZATION ERROR
For convenience, we define i |" I, the elements of the typical subset C/ {ar,... a,r, and
I {i [1, n] L C.) } I,
[1. I. =x)--
Note that Z and Iş are random variables that are dependent on the training dataset S. We then use these notations to decompose the generalization error
Lemma 5. The generalization error A S) satisfies
A(w, 5) -P. & C.) Eg [ &
LTT
L
I
VEI
17

---

Published as a conference paper at ICLR 2024
1
[
P(L t & (.))
L
IEZ
[xc]
P(L = ax²)
k=1
Proof. By noticing that I U 1 .................. U. = =1, the population risk can then be decomposed as:
- = P(L th & CT) L" & c
Σ
P(L"
= ax
1=
=L th & ET) [T c
P(L"
=ap)au.
(4)
Similarly, we can decompose the empirical risk as:
1
11
1=1
iET
sEIe
1
D
+
1ET
k=
1
IEIL
I&
ak.
(5)
n
n
IET
Substitute (4) and (5) into Aww, S). we can get
A(w, L(w) Ls(w)= = Ec-
1
1 n
Σ
n
= =I & Br 1. 10
c. - P(L"" t
& (m)
Σ 1
I
IEI
+ +P(L" " $ (T)
L.
Σ
L
I
IEI
iEI
[T
P(I." ax)ax=
ak
n
1
=( & cTm)
EL | I L & C4y
L
iET
+ z
PPLL" & c.4)
[
L
n
T.T.
I
P(L" = <ax)=
a..:
To simplify the notations, we denote the decomposition above as:
A(w, S) = A(w, S) + B(w, S) + C(u, S):
where
A(w, 5) = PI. & (:/) E1 [1 $ c.7
Σ D
VEI
18

---

Published as a conference paper at ICLR 2024
1
B(w, 5) - [
P(L" $ (x)
VEI
[Tk]
C(w,S) 5)
P(L = a+))
k=1
B.3 BOUNDING EACH TERM IN THE DECOMPOSITION
Lemma 6. For any O, A(w, S) satisfies:
A(w, S 76" vn
Proof. From Lemma we have
P(Te & ( S 7
vn
Since L." 2 for any i [1,n], we can prove that
S)w,S)= = P(L" & (T)
EL [L" $ c
Σ L.
iET
S PT. & L II
[1.0 I. & E
I E₁ [L $ &Za1
vn
bo
Vn
Lemma 7. For any y > 0 and 6 > 0, with probability least 1 1-8, 8, B(w, 8) and C(w, S) satisfies:
(L & L
EiEr L
2 220g(2/8)
(ww, S)
I
2(H (()) + CT) + 2 12g(2/8)
C(w, S) < 2bth
where
m log( vn/T)
C "
2
Proof. Denote qk = PLL = ax) for lo E [] and q = P(L" & (.))
Let
I
It
Ck(w,) S) Σ 96
a
9h
ak.
n
n
We then apply Lemma Twin with n 11 m n,
= = (LZ,) [Zl. [Z],
p= (qi...
9t. 9):
a%. = 0, āet1 = 0, and ā a, for any i + k.
When there exists i E [1, k such that g: > 0, we have Ein asq. + az+19 + 0 and the
precondition of Lemma is satisfied. Then for any >
nc²
P(C 5) > exp
exp
(6)
2 v y: q
19

---

Published as a conference paper at ICLR 2024
for any ls E []. Similarly, by setting a++1
1 and a; 0 for any i E [1, nl, we have
I
nc²
P
S
exp
n
2q
Take d as the RHS of 6 and 7 respectively, we then get
210g(1/0)
P Cu(
5)
Σ q: qu
S 0
(8)
for any l E [] and
I
2q log (1/8)
PP
q
S 6.
99)
Otherwise if g;u, = 0 for all i + k or q O. then C2 (w,, S) 0 or q - -IZ//n 0 and (8) (9) are natrually satisfied. Therefore, the inequalitites (8) hold for arbitrary (q)(), ... 0e: 9)-
By substituting
99) into ((w,S) S), we have that for any 5 >> O, with probability at least 1 5,
1
I
(
PP [
t
of C4)
I
TI
RET
P
L &
D
Eier
L
log((10)
(10)
I
Similarly, from 8). we have that for any 5 > 0 and l: E [1, t]. with probability at least 1 6,
2 2log(1/6)
Cxw S)
P(L" = a.)aa - P(L" =a)aa
n
2 21og(1/5) P(L = ai) P(L = =an)
50"0
n
2log(1/0)
PP
L ELy n L & axx)
2log(1/8)
$ 6"
n
Taking the union bound over every & E [1, t). we have that for any 8 > O, with probability at least - 8, the following inequalities hold:
(ww S 80
2 2lg((s/8)
(1I)
Co(w, S) 8" (l//))
"
By substituting 11) into C(w, S), we have that for any 8 > O, with probability at least - 6,
Izl
C(w,S) Σ
P(I =ak)=
ak
n
k=1
Ck(w, S)
A=1
(og()/))
<
Σ
b
t 1
A=
20

---

Published as a conference paper at ICLR 2024
2 log(t/6)
6
For the extreme case where & 1, can similarly derive that for any 8 0, with probability least 1 - 6,
C(w, (F(L" =a1)- [
a1
2 log (og(111)
I a1 v P(L = =az)/
n
2 llo((t/))
< 6" 80
Therefore, for arbitrary 1, we have
2 log(t/6)
C(w, $ 26th
(12)
From Lemma 4 Substituting into
we know that
m log (1T\))
t t= c S exp
H(L + c
we have
2 log(()) + 2 (10)(16))
C(w, S) S n6th
2 ((L)) + c"
m moggyyn/1))
+ 2 log(1/0)
2
< 26
(13)
Finally, by taking the union bound over 10 and (3) we have that for any 8 > O, with probability at least 1 - 6, the following inequalities hold:
PL
& L Σ DiEz
L
2 2log(2/0)
B)w
I
2(H + C1r)
+ 1og(2/8)
C(w, 5 < 26
B.4 COMPLETING THE PROOF
Theorem D (Restate). For any 7 > and 5 > 0, with probability at least 8, the following inequality holds:
H(L") + C
C
AWw, S) < CT
Vn
where
C = 2b 22,
log (n/7)
CTTY = c
log(2/6),
2
C = -6" + B V/y
m1/ V 2 2lgg(2/8)
Proof. From Lemma we know that for any > 0.
7
A(w, <
(14)
Vn
21

---

Published as a conference paper at ICLR 2024
Recall that in Lemma proved that
P(L" th & (T) I vn
7
By applying Lemma 7 we have that for any 7 > and O, with probability at least 1 - 6,
P(LL (2)
Eier L
2 (2/6)/))
B(w, S) v
[2]
n
V7 1
2 (2g6(
Bw.S
2/4 [
B VT
2 1ogg(2/0)
(15)
1/4
n
and
2(H(L + CT7) (2/(2/8)
C(w, 5) 26"h
n
H(L") C%
=C
(16)
n
Recall that in Lemma 5 we proved
(w S) = A(w, S) + Blw, S) + C(w,
(17)
By substituting 14). 15 and
16
into 17
we finally get
Aww, 8) v Tb"
B VT
2 12g()/0)
H(I + C
+ +
vn
1/1
H( + CCT
1
80 + Bu.S V
CT
11/4 v //log(2/75)
n
Vn
H(L") + CC"
C
CT
n
n
C PROOF OF THEOREM 2
Similarly, given the hypothesis w W, we denote the set of all possible loss values per class by by = [L(w, (v), v) V}.
Let L.W b. For any 7 > define the typical subset of by by m log( vn/7)
cH LE cy log Pile (1) ( s V
(18)
where (1) P(L I|Y v) PL 1).
C.I PROPERTIES OF THE CONDITIONAL TYPICAL SUBSET
We first show that by shares exactly the same properties as the unconditional one: Lemma 8. For any ? we have
PLLY & ( < Y n2
and
m log / (1/7))
1 S exp
H(L + cw
2
22

---

Published as a conference paper at ICLR 2024
Proof. Consider the function fy(t)
log Plyy (h)( have
Ey E (V))
Σ
Po log log
VEV
Σ LEL
Σ
po(u) log (ogg))((
nEhs' (1)
Σ
Po(v)
log log (1)
IEL
WEE (1)
Σ
(1) p)
(
Therefore, by applying McDiarmid's inequality on f(V) log (L
we have
(_ 2c²
PP( PP log Pt (T,))) H( 2 e) S exp
(19)
m(cgg)3
Take 8 as the RHS of 19). we have
m (o/()
2
Combining with (18) we select = V and
28= nn" P(L. & C. 3
Similar to the proof of Lemma
we can prove that
-" exp (-
e) S 1.
which further implies
H(I.T) +c m log (1/8) mlog(1/8)
1 S exp
C.2 DECOMPOSITION OF THE GENERALJZZTIOO FRROR
We further define ly = C. the elements of the typical subset as Ly = {ay, ... ,,,a,, }. and
I = {i E [L, n] L." & CT Y. y), = f [1,m] L. Y, y
We then use these notations to decompose the generalization error.
Lemma 9, The generalization error Aww, S) A(u, S) Bw,, S) C(w, S), where
Á(w, S) = Σ P(Y = L CH E L Y = y. L & C
Σ L
T
yEy/
iETv
1
I
B)w,S)= Σ
P(Y y, n & (
Tt|
yEy
VEIv
Ö(w,S) Σ Σ
P(Y y, _ =a
n
VEY k=1
23

---

Published as a conference paper at ICLR 2024
Proof. The population risk conditioned on Y y can be decomposed as:
Byy |لاا = PLLy "M & (.) BLy Ly m L
& Cr +
P P(L = By ا = a%l
k=1
= =P & C BLy و & cuuu
+ Σ
P( P a.
k=1
Summarising over E V/ we have
1--14-1= = Σ P(Y = L" & C E L = y, L $ f
EL
yEY
P(Y = v, = Da
yE km
Similarly, we can decompose the empirical risk as:
1
10
L
1=1
NEY
IETV
k=liETy
k=
1
Σ
n yEJ' EEI
BE k=
NEI
Σ BEV
L.
yEJ
Substituting the inequalities above into Aww, S), we have
Aw,, S) P((Y = y, L & C EL L
y, L E F4
yEY
PPY = y, L $ (T
Σ LETV
D.d
[Tv]
yEY
PYY y, Th & m
1
Σ
DV
T
1
Σ L
ITv
n
yEY
iETy
NEY
LT
P(Y- y, I. =%%
ΣΣ
4x
n
k=y1=1 k=1
k=1
Σ
P(Y = y, " & C
E [ [ = y, L & c
TN
yEY
EETV
I
Σ
Ip
My L $ x
L
T4
n
yEy
1EZV
P(Y y, 1 =aa)
71.
yEy
C.3 BOUNDING EACH TERM IN THE DECOMPOSITION
Lemma 10. For any y > O, A(w, S) satisfies:
Alw, S) < 70"0
Vri
24

---

Published as a conference paper at ICLR 2024
Additionally. for any 8 O, with probability least 1 - 8. the following inequalities hold:
/P(Y y, L x EiETs L,"
( 21188)
B( 5 Σ
Iv
yEY
2(H + C2) + 2 log 2
C)w,S) < 26th
Proof. From Lemma 8 have
P(L $ L Vn
By the fact that L 2 0 for any E [1, we can prove that
A(w, S)
Σ
PYY y, L & fTTN)) EF L = y, L & 1
L
D
Iv
yEy
iE!"
Σ
P(Y y)T Iy & (
E L y, L & m
yEY'
P(Y = y) س b" 76m
$
Σ
nn Vn
BEy
Denote of = P(Y y, ne a for [1, tyl. q8
P(Y y, L $ ( and let
(ue, S)
Σ
a
n
n
We apply Lemmal 0 with
X [Z 1 ...,, I 1241
p (ot..... . sh x*)
by + 1,
m n2,
a 0, aeu+1 O, and a. ax for any i + k.
Then for any > 0, we have
nc²
P ((C)(w,)) ))>c)) S exp
(20)
2 E/e -- of (a?)) -
for any ls E tg.. Similarly, we can get
ne²
>
< exp
(21)
2q
Take 8 as the RHS of 20 and 21 respectively, we have
2 log(1/5)
IP Ck 8) >
Σ (a))22 2(a))22
S 6,
for any lo E [yy and
T
2q log(1/6)
Take the union bound over y E V, have that for any 8 > O. with probability least 1 8, the following inequality holds for all E y simultaneously:
2 log( (21/8)
(W S)
Σ
(at)z q (
(22)
25

---

Published as a conference paper at ICLR 2024
for any ls E ty. and
T
2q log( ()9/))))))
IP
q"'
S 6.
(23)
Substitute 23 into ((w, S), we have that for any 5 > O, with probability at least 1 8,
T
B(w, S) = Σ
P(Y = y, L $ C
Σ
L
T
yEy
ZEZ
P(Y y, T & (. Eiero 1.
log log(()))/))
(24)
I4|
VEY
Similarly, from
22
we have that for any > and E [1, ty). with probability at least 5,
by
2 log (V166)
(w,, 9)
9. (ax))²
2
2 2log(D))/0)
S 6D0
q g
1=1
2 (lgg())1/8)
bm
P Y y n L Lu
L # +a%)
S 5b /P(Y = v/ 21og((>)1/8)
n
Taking the union bound over k have that for any 8 > 0, with probability at least 1 8, the following holds for all & E [1, and E y simultaneously:
(w. S) S tne vP(YY v) 2 (og((t
(25)
Substitute 25 into C(w,, S), we have that for any > 0. with probability least 5,
I
Öww,
ΣV
P(Y y, L" = =a%)
a
yEy k=1
Σ
(w,
yEy by
by
2 2log(t (21//))
Σ yEy
b" /F(Y - v
by
Σ 8" P(YY y) tv
by
logg(t (11()))))1/8))
n
NEY
2 2og #log(tyyDDe (1108)
<
Σ yEy
hdd PP(Y = w)
Recall Lemma g which proves that
m log v4/7)
ty 1
S exp
H(L)) + c
2
By applying Jensen's 's inequality, we have
2 2log(1, ) + 2 log (11/8)
C(w, S) S "h Σ /P((Y v)
n
yey
26

---

Published as a conference paper at ICLR 2024
2 H(L)) + og / (olb((//7))
+ 2 2 (D'1/6)
S 2 Σ
v P(Y 1)
n
DEY
2 H((g) + c
m log( va/r)
(og(())1/))
S 2b"h 1/1
P(Y = 9)
PEY
m log vn/7)
2
H( eloy
+ 2 log(()11/))
2
= 26th VDN
(26)
Finally, taking the union bound over (4) and 26).. we have that for any > 0, with probability at least 1 - 8, the following inequalities hold:
B(w,S) P(Y v, L fW
EiErv D.
2 log 22)))/8)
DEY
2(H(L + CT) log (2()15))
Ö(w,S) 26 V
C.4 COMPLETING THE PROOF
Theorem 2 (Restate). For any y and ō O, with probability at least 8, the following inequality holds:
H(T Y)
E.y
Č.u /n"
Aw,,S) S V
+
n
where
ÕTH = 2b /2(3%
m logo(( vn/7)
T = c
+ +og((2())/)))
2
Th = bb" t + B v V
V 2 (log(2))1/
n/4
Proof. Recall from Lemma that
P(C & x 2
Vn
Combining with Lemma 10 we have that for any > and > 0, with probability at least 5,
P(Y = y, L & Lyy
EiEIO L."
2 2 (2))1/8))
B(w, S Σ
I
BE)
(og((2()(/5)
= =
VP(Y 4) V Ly & (.)
Σ L
I
n
DE
< VT 1
2 (log(2)))(5))
VIJI
P(Y =vy
n//4 |
LiET
DEY
< B vr[yi
2 (2g
1/4
27

---

Published as a conference paper at ICLR 2024
and
( + OF) + 2 log ( 2
(ww S 26th V
HL Öy
n
By applying Lemma
we can get
A(w. A(w, 8) + S) + C(w, S)
+ BE,S V
2 2log (200(1))1
H(I."l) + E2
+ CT
vn
n1/1
n
V
H(L"(Y) +
1
70th
Bu,
V /
V2
n
vn
2/4
H(L"(Y) Öj
Č.m
CT
71
Vni
D PROOF OF DATA-DEPENDENT BOUNDS
Let R E R be any discrete random variable. Denote (r(r) = (PR = r). For any X > 0, define
C^ edH((R)
Σ PT-ー(rr)
FER
For any O, we define the typical subset
R. = {r R logp. - H() S c).
D.1 PROPERTIES OF THE TYPICAL SUBSET
Lemma 11. For any À > O. by taking e = }} log(Cx/)), we have
PPR R
and
H1 ()) x log ))
Re S exp
Proof.
From the definition of the typical subset and by applying Markov's inequality, we have
P(R R.)
IP(- log-logeo p. (Rt) 2 H(R) +))
IP(-Alogp p. (R) 2 (H(R) + Xe)
(P();>(R) 2 exp(AH + Xe)) En [p: (R)]
(27)
exp(AH (R) + Xc)
EVER -x)(r) CA
(28)
exp(AH Xε) exc
Now we compute the size of R.:
log pr RR) H(R) <c
- -log Pr R < H(R) +
-H(R) log pr
28

---

Published as a conference paper at ICLR 2024
exp(-H((R) c) S (R)...
This further implies that
12 =
Σ (r(r)) 2 Σ exp(- -e) - [Re,] [cs[exp(-Bi) - -c).
FER,
PER,
By taking Cx/e = = in
28 i.e. X log
1og(C2/0)) (x/0), we have
)
|R,l I exp
H(R) + log
8
Σ pf M1)) ))
11
1
exp
H(R) log
(8)
log
e2H(R)
HER
exp
(R) + log
{
8
1
1
{HH(()
+ log
Σ p (r)
A
FER
)
exp H1 + ā log
D.2 COMPLETING THE PROOF
Theorem 3 (Restate). For any X E (0, 1) and 8 > 0, with probability at least 1 - 8, the following inequality holds:
A(W, St, U) s Ct v (H--((HM)+ C,,
where
CT = /2Egww
2 8
2
CW
log
8 + log
by assuming that n+1 (T T.W) is E Ssw-subgaussian w.r.t U for ERw E [0, [0, B.....
Proof. Assume that RW = for some r = {4:1-tt E R we then have
A(W. (W. U) = 1u
1
4
i&U
1
a+1
-g
4
+
lu
71
1m1
n + 1
+
1
n
n
n +
(lu - I),
where -= 1 E 4, It is easy to verify that Ey n+1
A A (.. S.SS.,0 U) 0. When by WWSS,
suPpe[i.nt]] 4 and for any i + U. A (W, St, U) takes the maximum value of GW.3, Sim-
ilarly, one can prove that A A(W St U) 2 -.... which implies that A <W, SW, U) is BW.S subgaussian. Assume that RW
and let A (W. be sy-uuaaausii w.r.t U, where
or 5., then for any t 0.
f2
Pr A (A(W: W. U.V. 21) s exp
2(ar)²
29

---

Published as a conference paper at ICLR 2024
That is, for any 8 and E R", if Rw r, then with probability at least - 6,
A W. St U) I or 2logg(())
(29)
From Lemma 11
know that for any 0,
P(R & ( S 6,
(30)
H1 HI- + log ())
R W
I exp
(31)
Taking the union bound of (29) every R.W, have that for any 5 > 0, with probability at least 1 - 6, the following inequality holds for all E R!."" simultaneously if RWW r:
A (W..S..U) S or 21og([ 1/6).
Therefore, if RW E Re then we have that for any 5 > 0, with probability at least - 8,
A( (W. I Eew
2 log([ 1/6).
(32)
Again, take the union bound over 32 and 30,, have that for arbitrary RW RW and 5 0, with probability at least
6,
A S.. Enw / 22log(2|R!) 1/0).
(33)
By substituting 31 into the inequality above, can get
A (WW s ERw
H1 (HI- + log 1 ④
)
+ 2 log
= = v (1->((WW) + CCY
Theorem (Restate). For any X 10 and 8 > with probability least 8, the following inequality holds:
H H (R C.
A (W, () I C.
where
2 n
G =
(A
71
CW
log
log 2
(
Proof.
Assume that RW r for some -= [ E R. we then have
A W. S. 0) LLs(W] Ls(W)
W 11-
I.W.
i=1
0: A4.
n
Notice that Eg, [(-1)0:] = 0, by applying McDiarmid's inequality with f(i) A(W. have that when i2W = r, for any / 0:
2t2
(.,0) 0) 21) S exxp P& A W. (A(W.3...
| (2A1./n)²
30

---

Published as a conference paper at ICLR 2024
That is, for any 8 and E RR if Ry
r, then with probability at least 6,
2 (og(1/0)
Sen Ui
i=1
From Lemma 11
know that for any > 0.
P P(N $ R S
(34)
1
log )
RV
I exp 11 11
(35)
Taking the union bound over every RW A.e' have that for any 5 > with probability least
1 - 6, the following bounds holds for all r E Rg simultancously if R r:
2
RWW. 15)
)²1
n
Therefore, if RW E e have that for any 5 0, with probability at least - 8,
log
R /6)
A (w,
(AI
(36)
Again, take the union bound over 36 and with probability at least
34
we have that for arbitrary R E R and 0,
n Σ
2 log
2 R. 18)
RW
A (w. (W,,.. S., 0)
(37)
n
By substituting 35) into the inequality above, we have
log (2/ =log
- 100((122.)) + log
S -HI- + X log
g
+ log
-11 + C.
Substituting this into 37 we have that for any 5 > 0, with probability at least 1 - 8,
(W, s cWN Hi (1-)) + EW
D.3 FAST-RATE GENERALIZATION BOUNDS
We then prove our fast-rate generalization bounds for the validation error under the supersample setting. To overcome the loose BWSS, factor previous fast-rate bounds, we adopt thresholding strategy based on simple observation: for any > 0, the enror could be decomposed by:
min(ss L) + max(L K, 0).
For convenience, denote I. min(s, T.) and I- max Hi, 0), then I. I T-*
31

---

Published as a conference paper at ICLR 2024
Lemma 12. For any > 0, À (0,1) and 8 > 0. with probability at least 1 8. the following inequality holds:
1
a
W.K.
C.
Win 1,0;
H1 H1 + log(1/6) log(445)
11-0:
mn
where RW..-
{L1,0 Li,1 Ji=1 and
Win
log 2 - 22n1,
(o.
log
C2
1, L. max [L.
W.n. W.N
2x
2nL, W.n
for any i E [1,
Proof. Assume that W... for some r (1,,0,4,1)22 RW.., the values of C. i E [1,
then deterministic given r. We then have
1110; - (1 + C.) 21)
Ci 2 (41-0,--4 - 4.0.
Ci
C
140, 21
P
1 +
2 1.
2
P
(-1) (2 + Ci)li -
2n
1=1
8: (2 C1)4.0 - C.4.0) 2t 21
+
2n
1=1
< P
sup
Σ i=l
(-1) 0: (2 (2+ C3) -ci)
[E(0,1)
2n
1
((-1)) (2+ C.) -.) 21
+ 2n
Ci) - C:)lu3
< P
sup [E(0.1)
2n
((-1) 0 (2 C.) - Ci) 61)4.1-11 21)
+ sup IE(0,1)
2n 1=1
< inf 7E(0.1)
P
sup /E(0.1)
Σ
(-1) 0: (2 C.) Ci)bu } 2 270)
2n i=1
( C3) C. C.)1.1111 (1 7)t
+ P
sup rE(0.1)
2n i=1
Observe that the two events above share the same marginal distribution, this implies that
P
1, (1 (1)00 zt)
1
(-1) (1))) -i) 2 2nd)
inf
P
sup
r6(0.1)
[E
2n (=1
1
a:)4 2 2 (11-))
+ P
sup TE(0,1)
(38)
2n
[=1
32

---

Published as a conference paper at ICLR 2024
Since the values of C, E []. determined by R they are independent of U. For any E {0, [0,1).t > 0 and > 0, by applying Markov's inequality, we then have
1
(-1) c.) - 0.),. 2t)
IP
2n
i=1
PP
exp
"1
Σ
(-1) (2+ C.) -c)bu
2
2 B
17 Σ
(2-1) C.) -c)44.
exp
i=1
21yzth
E
exp
(7 (2 C.) C. c.)l1.)
i=
(1+C, 2nnt.
2ymt
We intend to carefully select the values of rj and C, such that --2pl..( +e < 2 is satisfied for any i [1, n] and E {0, 1}. Notice that 2 < 2 implies 20/4, S log 1. Furthermore,
since (1+C), +e2nl.. decreases monotonically with the increase of C₁ it sufficient to select a large enough C₁ that satisfies:
2-2n,, 2 c -2
Solving the inequality above yields C; 2 -log(2 c2nte.t) 1/2 - 1. is easy verify that this lower bound increases monotonically with the increase 11,1. Therefore, if we choose the value of C by
C, log(2 2n _ 1,
2n max((1,044.)
we will have
21t1, + 2
1,
2 for any i E [1, and the following inequality can hold:
Σ
- -i)) 2t S 2mnt
P
(39)
2n
1=1
Take the union bound of (39 over E {0, 1), we can get
(11) C.) c:)lus 2t s 2e 2nnt
IP
sup IE(0.1)
(40)
2n 1=1
Substituting (40p
into
38
we have
IP
1- - (1+ -1+ 2
inf
2E 21yntt 2e 2n-1nn)ne
(0().
2e not
2e nnt
put
(41)
By selecting d as the RHS of (4 we have that for any 8 > 0, with probability at least 8,
kno - (1+ -1 < (4/()
From Lemma know that for any > 0.
P W.Wx & Rw
< 8,
(42)
33

---

Published as a conference paper at ICLR 2024
W S exp H1- (1 + log ( 1
(43)
Notice that the marginal distribution of RW.K is symmetric due to the existence of Ü, i.e. if f4., 4,.1 E R.. then we also have {4.1. 4.,02=1 E R..... Since the upper bound above (40 holds for both / E {0, 1] the equivalent size of R. can be divided by 2. Taking the union bound over every R.W., we then have that for any 8 0, with probability at least 1 - 8, the following bound holds for all RW, E W.W. simultaneously if RW..
log
2 R. W. 10)
W.K. 1110
(1+ C.)L
W.N
(44)
1,U,
7
By substituting 43) into (44) and take the union bound with (42 and 8 O, with probability least 1 o,
we have that for any RW., E W.
1
a
W.K
(1+ C.)
log
(: ) log(4/6)
T
11-0:
1,0,
7x)
H HI-x(RWin)) + 1og(1/0) log(4/6)
ny
The only requirement on the selection of C₁ and is
log 2 e2ni,
}. for all E [1,n].
ConE
C
2n W.
Note that the condition above implies 2n
< 2 for any i [L, we therefore choose
log 2
log 2
17 <
2k
2supie(I.m] (WWxx)
Theorem (Restate). For any K. 2,0, 0, X, E (0, and 6 > 0. if 2 BW3., then with probability
at least
5, the following inequality holds:
n A (W. 0) S 1 Σ
C.U. 40, + GW H1 (F(W) GW
n1
where
1
2x
GW
1)
7 log 2'
1
1
4 8
G log
log
8
log
2
C
1.
2n
Proof. The proof directly follows from Lemma 12 by noticing that W.n. = W for any i E [1.m] and {0,1} when k 2 BW...
Theorem (Restate). For any K > 7, dn. A2 E (0,1) and with probability least 5, the following inequality holds:
GG 11 (RW..)) + Gw
H H1 (R (KW.-K) GW
A A(W, W. (W,Ss, 0) < Σ
W.s C.L. 10.
+ +G
Gw
n
34

---

Published as a conference paper at ICLR 2024
where RW.. Wix
L, Li,1 li=1
R
RW.- {AL,
W -
11=1 AL,
Wi-x
- -,,11- 1i0
W. -M and
G
1
2x
1)
7 10g 2
1
T
1og(2/6) + log(8/0),
X
G
1
ALiy
( ?
n
GW log(2/8) + log (4/0),
A2
log 2 2
C
2411. W.n.
Proof. By the definition of the validation error, we have the following decomposition:
A(W.
W
I.W 2,
1,1-8
n
1
Win
-(1 -11+ C.)
W.r. 10; n 10;
1
C.L. W.e
n
i,1-0;
L Wi-K 2,1-U i,C,
Wi-K
(45)
By applying Lemma
12 we have that for any 5 > 0, with probability at least 8,
W. - (1 C.) W. n
H1- H1-A, + Xy log(1/6) + log(4/0)
40. S
By taking 17
2 log
1og
we then have
2x H1-11 (R X log(1/6) + log(4/6)
Wx 61-0. (1
L.) W.K 100,
<
(46)
ny log
By reapplying the proof of Theorem probability at least 1-6 6,
-W. instead of RW we have that for any 8 with
Hi H1-22 (RW-*) Xg (
- 1-10;
Wi-K L
2
AL )
L.
i=1
(47)
By taking the union bound of 46)
47 and then substituting it into 45
we have
n
2k H1 (H + 1 X log(2/8) + log(8/5)
A(W,S,, U) s
C.I.W. Wx +
1,0
ny 2
H1 H1 ( -W + log(2/8) + log (4/8)
2
Σ ALN.TT))
2
n
n
35

---

Published as a conference paper at ICLR 2024
E ADDITIONAL THEORETICAL RESULTS
E. SUBADDITIVITY OF RÉNYT'S ENTROPY
is easy to show that Shannon's entropy enjoys the subadditivity property, i.e. given arbitrary random variables X1, , ,,,, we have
( X,,) ( H(X, +... (X .x-11) S (())) + ((2)) +... H(.)).
If the subadditivity property also applies to Rényi's entropy, we will be able to upper bound the joint entropy of samplewise losses in our main theorems by the sum of entropies of each individual loss, which avoids estimating high-dimensional information theorrttc quantities and yields directly tractable upper bounds. We will show that for discrete random variables with finite support, the subadditivity property holds for Rényi's entropy when s 1. Note that these assumptions are naturally satisfied for digital computers using floating point numbers.
Lemma 13. Given arbitrary discrete random variables X X and E E assume that [xX] = m < If and Y are independent, then Ha (X, = Ha(X)+ Ha()). Otherwise for any E (0, (X) + H(Y) (X, Y)), there exists > such that when a (1 6, 1). we
oo and [
have Ha (X, Y) + (x HY).).
Proof. Let Ptj = F(X = X, = V/). = PPX = X,) - プラ Pij and qi = P(Y -V)) -
Ei Pij. then by the definition of Rényi's entropy, we have
Ha(X,Y) 1 log
m
Pig
a
i=
i=ij=l
m
1
92
Ha(() log
P
Ha =
log
j=1
When X and Y are independent, we have Pij = pigj and thus
m
m
==
which directly implies Ha(X, Y) = Ho (x) + HY)
Otherwise when X and Y are dependent, recall that H(X,Y) < H(X) + H(Y), we then have
lim Ho, lim (X) + (Y). c+1
( the definition of limit, know that there exist 81 62 > such that when a 51. 1). we have HH (),Y) -X(,Y)) & 7, when a E (1 -82, 1). we have H., (X)+Ha - S
For any e E (X) + H(Y) - - Y)). let (X) + H(Y)
- -e)/2. Then by
y. Combining these two inequalities yields the desired result:
HX, 7 H = H(X) H(Y) 2-
5 (x H. c 27 (X)()) + Ha(Y) -
The proof is complete by taking 5 = mmn
When the number of samples n is large enough, we have lim, n theorems. These high-probability factors are thus significantly smaller than the joint loss entropy term H HR),(R),, ), and we can select À = 0 to acquire computational tractable bounds as
1 log(1/8) = 0 in our main
HR-X(R") < (I)) + HI-x(I2) + H HLn)
by applying Lemma 13 recursively.
36

---

Published as a conference paper at ICLR 2024
E.2 TIGHTENING PREVIOUS BOUNDS BY THRESHOLDING
In this section, we demonstrate that the fast-rate bounds for the expected generalization error estab- lished in (Wang & Mao 2023) can be further tightened by adopting our thresholding strategy. The original theorems are stated as follows:
Theorem 7. (Theorem 3.2 in Wang & Mao 2023 Assume that e(;,)) E [0, 11, then
E
B A ( W S., U
]
21(ALY
Theorem 8. (Theorem 4.3 in Wang Mao 2023 log 2/2),
Assume that e(.,)) E [0, 1], then for any C2 e
s Ls T(ZN)U
"
E B (W,
Cen
where
log (2-6203 1.
C1
20₂
As can be seen, these upper bounds only hold when (()-)) [0, 1]. In the case of unbounded loss functions e.g. cross-entropy, these bounds should be multiplied by gW.S. stay hold, which significantly looser when the marginal distributions of the losses are long-tailed. We first tighten Theorem by introducing subgaussianity:
Lemma 14. Assume that L. and L are o-subgaussian for any i n), then
W. 3w.
2 Σ
E W S.
Proof.
From the definition of the validation error, have
w..s (A S., S...s...]]
E B.S.O. w
I.W.
1,1 U; 4.U:
Bs, U,, w
(-1) c: (L - L.
71
E ALL Do [(-1)0A
7
From the assumption that L. and L. are o-subgaussian, we have that ALW D. L. is 2o-subgaussian. Then by applying Lemma with f(Ü, ALW) (-1)0A we have
E BALN a. [(1)). E EAI & (11))AAAM)) 22
Since ALW is independent of Ü, we have BALW C. (-1)): = 0 and
n Σ
Ew..s. | W. (.,,S, 0)]
BALW .., (-1)0 ATW
i=1
2
<
i=1
37

---

Published as a conference paper at ICLR 2024
Note that this bound is at least tight as Theorem 7 since the condition that E(;-) [0. 1] implies
5 2'
We further tighten Theorem 8 by introducing the thresholding strategy. For any K > 0, the expected generalization error can be decomposed as:
E W. .0
A
W. S. 5..
= =Es,,O
W
W
1,1-0. 1,
=,,
2,100,
Wix
(1 Ci)4;,,
1,0,
W.x
11100
W.-R
100;
Wi-K C
L. Win
i,t;
Win
- (1+C1)
W.x 1,0%
+ BB,
1
L w
L Wi-K
1,100
1,1 U²
1,
n i=1
+ S.S
G W. 1,0
(48)
The following theorem establishes an upper bound for the decomposition above by leveraging both square-root and fast-rate bounds:
Theorem 9. For any R > and C2 (0, 1ox2), assume that W and L,11 are o ow-Subgaussian
for all E [1, n), then
Ew.s, 0 [(
T
W.. (U.))
2
+
V
Czn
1=1
==1
Ci Ewws.
W.K
1=1
where
log(2 2 202xx)
C
1.
2C2R
Proof. We first decompose the first term
48) as:
E
W.r 1,1-0
- L
W.
100
1=1
Byw L.W, 03 [ - (1 -1)
W.x
7
E W
W. M.
(1+ ) (I.iin - -(1 W.x)
1,0.)
C1
r
1.1-0:
W.x
Ci
2 1.
T, Wix
E w &
- 12 (-) I.
W.x C. Wix]
C.
2n
1=1
W. + BBY, G. (2 Ci)(-1) W. C.
Notice that W. and L. share the same marginal distribution, " and B. 0] = BiL Win 1]. we have
Wox UŪ 0] E[L Uū 1).
W. 11-0;
- (1 + C1)L
60.
Win 1
E r.w
W. 0.
(2+
11)
C2 W.
n
i=1
i=1
38

---

Published as a conference paper at ICLR 2024
For any i E [L, by applying Lemma 3 on C2 C2 (2+ 1,,1i -CLL11 ((x
we have
I(L ; 2 Buy, 6, C2 (2 (1+ 1 "M -IL,,11
4,11 C2 (20
- -log Lw, U,
(49)
Since 1,,1 S K, by selecting C1 and C2 as:
(C (0,
log
C1 log(2 ( - e2C2rc
C1.C2 E C2E
- s
2n
2C2k
we will have
BLN 2C2(1+C))
+ 2, W.a
E ww 1,10
11. (50)
2
By substituting
50
into 49
we can get
E k U.
Co (2 (1) I. 4,11
W.s - C1 (IT.1
W.
]
- T(I,
[.N. U.),
By summing the inequality above over E [1, n]] we can prove that
I(L W. (., U.)
E Wr
Win 01 (1 D W.
(51)
n iml
i00
C2n
Next, by reapplying the proof of Lemma
14 on RW. instead of RWW can prove that
2
E S
Wi 1110;
L W -K
(52)
1,U,
The proof is complete by substituting
51 and 52)
into 48
According to the Markov chain relationship U, - L
L
W. and by applying the the data-processing
inequality, we have I ",, Ü,) < I(L,,,,,), 0,). We also have L W.s < L.W ',,," Therefore, Theorem
tightens Theorem 8 by reducing the WWS.. factor to a manual threshold K, at the cost of introducing an extra term that scales with x. When the losses are long-tailed, we will have WW.S. >>>>> ox and Theorem 9 can be significantly tighter than Theorem Otherwise, we can simply take RJ WWS. and let Theorem reduce Theorem
E.3 COMPARISON WITH VARIANCE AND SHARPNESS BASED BOUNDS
Theorem 6 also provides alternative perspectives fast-rate generalization bounds by leveraging the entropies training and test losses. By comparison, the previous work (Wang & Mao (2023) utilizes variance V(y) and sharpness F(y) related terms replacements the training risk, which are defined as:
V(7) Ew.s
(e(W, - (L+)))))) =11
F(7) 1 n Ew.z, 2. (((W, 2,) - B112)) (e(W, [,)]]
We show that our loss entropy measure serves as tightened versions of both the variance and sharpness-related terms. To see this, let I ~ (ni rz)) randomly selects training sample Z₁ from S. We now measure the variance of I,, = (WW Z,):
Proposition 1. Assume that ((.,)) [0, 1), then Var[Tr] min((((), F(0)) Fw.ss[.s(WW)
39

---

Published as a conference paper at ICLR 2024
Proof. For the formula of the total variance, we have
Varw,s,1 [Lr]
Ew,s (rarss|aayyyya [4,]] + Varw.s
Ew,s
(e(W, Z.) Ls(W)))
Varw,s|Ls(W)]
V(0) + Ew,s [W)) - sw
- ((0) + Bw.s [Lss]
Similarly, we have
Varw,s,r [Lr] Es! Varw ./s [T]]] Vars (BrssBw.nssLLi))
= Ess Ew.1 8 (, Zr) EwIs. [+] + [ars(Bw.nssLrI]]
n
s
Es
E Ewiz, [e(W, Z.) Bwiz, [[(W,
Vars Ew.nssLi]
ni
1
Bw,z, [e(W, 2.) - Ewiz, (e(W, 2.]]] [ars[Bw.nssLil]
F(0) + Es w. [T]]] E
S F(0) + Es [EW.nss
F()) + Ew.s(Ls(W))
Here, EwwssLss(W) is the average training loss, which approaches zero in the interpolating regime. That is, the variance of L, is a natural lower bound for both the variance and sharpness measures. Furthermore, we show that the entropy of training losses is upper bounded by that of L,:
(H( n
Σ S 11 Σ
H(. L0
n Σ P((T= i=1
H(LI S H(T)).
Notice that L, is Bernoulli random variable under the assumption that e(:,-) (0, 1}, which im- plies that the entropy L, is determinated when we know its variance. Therefore, any upper bound for [ar[Lr] directly serves as an upper bound for H (Lr). This conclusion can be extended con- tinuous cases, by noticing that the Gaussian distribution (O,, o²) possesses the maximum entropy among all probability distributions whose variance is o². On the contrary, the variance unknown and can even be non-finite when only the entropy is provided (e.g. Cauchy distribution, student-t distribution with t 2, etc.). Moreover, the fast-rate bounds of (Wang Mao (023) requires ((.,)) to be 0-1 loss, while Theorem 6 can accommodate any E(,,)) E [0, 1| These observations further validate the superiority of our results.
F EXPERIMENT DETAILS AND ADDITIONAL RESULTS
In this paper, deep learning models are trained with an Intel Xeon CPU (2. (0GHG 48 cores), 256GB memory, and 4 Nvidia Tesla V100 GPUs (32GB).
F.1 SYNTHETIC EXPERIMENTS
In our synthetic data experiments, the learning task is a 5-class classification on two-dimensional points generated with isotropic Gaussian distributions. The training set contains 50 samples, while the test set contains 250 samples. 216 models in total are trained according to different combina- tions of the following options: 4 MLP encoders ([256, 256, 128, 128], [128, 128, 64, 64], [64, 64, 32, 32], [32, 32, 16, 16]), 3 weight-decay rates (0, 0.01, 0.1). dataset draws and 3 random seeds. The models designed under the variational setting, where the encoder is trained to characterize a conditional distribution for the representation given the input via deterministic means and stan- dard deviations. The parameterization trick is used for optimization. Models trained for 300
40

---

Published as a conference paper at ICLR 2024
Metric
Spearman
Pearson
Kendall
Num. params.
-0.0576
-0.0294
-0.0402
[[W lp
-0.2172
-0.0871
-0.1374
I(
0.1816
0.2878
0.1280
I(x:7"
0.1749
0.3167
0.1129
I(
0.1648
0.3712
0.1223
T(X:T"
0.2293
0.3842
0.1515
[(S: W)
0.0020
0.0211
0.0074
[[S; W) T";
0.0178
0.0211
0.0178
T(S: T(X:T"I
0.0163
0.0211
0.0167
((S:W) "X)
0.0135
0.0212
0.0162
T(S; (") T(X
0.0164
0.0211
0.0167
T(S:W) T")
0.1104
0.1401
0.0794
T(S: I(X:T"
0.2253
0.3177
0.1567
T(S: W + +(X;TT
0.2684
0.3928
0.1912
IS:W) I(X;T"
0.3015
0.4130
0.2085
H(L") (YL
0.5767
0.5611
0.4037
0.7088
0.6350
0.5251
Table 1: Correlation analysis between different metrics and the generalization gap. i, I, represents different strategies for mutual information estimation.
Metric
Spearman
Pearson
Kendall
Num. params. [[W Ie
0.4944
0.2770
0.3985
0.4944
0.2680
0.3985
T(;;T"))
0.4799
0.6232
0.2941
I(X;T"
0.4923
0.6185
0.3203
I(x:T")
0.1496
0.0190
0.0196
T(X;T"
0.2198
0.0495
0.0980
Ī(S; W)
0.6065
0,5692
0.4633
I(S; WT + ((
0.6140
0.6417
0.4248
[(S:W) ((X;T
0.6202
0.6406
0.4510
I(S:W) + [(X:T")
0.3808
0.1378
0.2549
I(S:W) +(X;T"
0.4138
0.1648
0.2810
T(S: T(X:"")
0.6223
0.5692
0.4510
f(S:W) [(X;7"|>
0.6223
0.5692
0.4510
I(S; (S;:W) +(X;T
0.5666
0.5685
0.3987
I( (X::T
0.5810
0.5707
0.4118
H(L") H(L"
0.8782
0.8679
0.7647
0.9030
0.8915
0.7778
Table 2: Correlation analysis between different metrics and the generalization gap with 20% label noise. 1, I, represents different strategies for mutual information estimation.
epochs with learning rate of 0.01. The conditional and unconditional loss entropies estimated using a simple Gaussian kernel density estimator, where the kernel width automatically selected by the well-known rule-of-thumb criterion. The code for this experiment is largely based the implementation from Kawaguchi et al. 2223
Besides Pearson correlation analysis, we further present the estimated coefficients of Spearman and Kendall correlations in Table [ Additionally, we conduct experiments with 20% label noise to examine the robustness of our bounds against noises Table 2 i.c. 20% of the labels are replaced by
41

---

Published as a conference paper at ICLR 2024
groad
Weigitad
Tast Raas
Disay
1.5
Enir Teskilina Seayy HL
Erer
10
1.0
0.5
0.0
75
250
10000
4000
1000
5000
20000
12
20
24
28
52
38
Epoch
(a) MNIST, Adam
(b) CIFARIO, SGD
(c) MNIST, SGLD
Figure 3: Comparison of the generalization gap in 3 different deep-learning scenarios, along with theoretical upper bounds including the weighted bound (Theorem 5), the f'sstrraee bound (Theorem
and the binary KL. bound (Theorem in (Hellström & Durisi 2022 )-
10
Adiefi vecsol
Emnr
Ener
10
10
2
75
1000
1000
20000
(a) MNIST, Adam
(b) CIFARIO, SGD
(c) MNIST, SGLD
Figure 4: Comparison of the generalization gap in 3 different deep-leaming scenarios, along with the weighted generalization bound (Theorem 5 using adaptive C₁ values (Adaptive) universal value for all C (Universal).
randomly generated ones. As can be seen in Table and 2 the better indicators of generalization.
the loss entropy metrics are consistently
F.2 REAL-WORLD LEARNING TASKS
We conduct 3 real-world learning scenarios to evaluate different generalization bounds: 1) MNIST 9 classification using Adam, 2) MNIST 4 vs classification using SGLD, and 3) CIFAR-10 classification with fine-tuned ResNet-50. The loss function is cross-entropy.
In each experiment under the supersample (leave-one-out) setting, we draw 1 samples of Š, (S)), each involving randomly sampling 2n (n + 1) samples from the corresponding dataset. For each S, (Ši), we then draw 22 samples of the training test split variable Ü (U), resulting in total of ki x k2 independent runs. The value of k1, 22 and experimental settings are kept the same as Harutyunyan
Squars
0.5
Finz Sipars
Fani-tbale
Riicyy
0.4
33
Eeer
Sques-Ror:
0.3
250
1000
6000
20000
12
28
36
Epoch
(a) MNIST, Adam
(b) CIFAR10, SGD
(c) MNIST, SGLD
Figure 5: Comparison of the generalization gap in 3 different deep-learning scenarios, along with theoretical upper bounds including the square-root bound (Theorem 4). the fast-rate bound (Theorem
6 and the binary KL. bound (Theorem in (Hellström & Durisi 2022 using bin size 0.6.
42

---

Published as a conference paper at ICLR 2024
Erer Sigais-Hoos Posii Disary
0.8
Ery
Gipare
0.6
Froz
Ertor
022
250
1000
5000
20000
12
Epoch
(a) MNIST, Adam
(b) CIFARIO, SGD
(c) MNIST, SGLD
Figure 6: Comparison of the test risk in 3 different deep-learning scenarios, along with theoretical upper bounds for the test risk including the square-root bound (Theorem 4) the fast-rate bound (Theorem and the binary KL bound (Theorem 7 in (Hellström & Durisi 2022
Sqair-Root
Spp Vir Roid
Froe
Froo
Emror
75
250
1000
1000
5000
20000
12
24 Epoch
20
(a) MNIST, Adam
(b) CIFAR10, SGD
(c) MNIST, SGLD
Figure 7: Comparison of the generalization gap and the theoretical upper bound (Theorem under the leave-one-out setting.
The discretization strategy discussed in Section value with a bin size of 1.0. A union bound of our main results and Proposition B is then taken to provide valid generalization bounds for continuous loss functions.
al.
2021
G.3 adopted discretize each loss
Although the RHS of Theorem 4 and dirrectly involve the test losses, the exact values of test losses are not required to evaluate the key coefficients CWW or GWW in these theorems (Note that we can in Theorem 5 and 6). For any w, let Z y and L = L(w, Z). Then
directly take i.W, i.W. suffices to adopt a few validation samples to estimate E[L] and E[L?]. By applying Markov's inequality, we have:
S )[
1 m
P (AL 2c
1 El= E
(LW )a (LW
1,0, 1,1-U, )2- 22 L.W
10, -.
1 E W )2 E[L - 2E[L 1 Σ 4.0. 1.0
n
Therefore, one can easily acquire a quantile estimation of CW or GW through a few validation samples, which is also necessary when training models in practice.
The hyper-parameters are automatically chosen by optimization using the Scipy package: Specifi- cally, À is chosen by the L-BFGS- B algorithm since it is derivable; and x are chosen by the Nelder- Mead optimization algorithm; and the binary KL measures (Hellström & Durisi, 2022) are solved by the brentq algorithm. is noteworthy the hyper-parameters should not be directly optimized over the RHS of our bounds, since they are assumed to be constants and should be independent of the draw of W, 3, and Ú. Instead, note that these bounds can be expressed as P(A < B) > 1 5- where the validation error A and the upper bound B are both random variables. By taking b as the expec-
43

---

Published as a conference paper at ICLR 2024
tation of B and then optimizing the srper-parametes over b, we able to fulfill the prerequisites of these bounds and keep the evaluation valid after optimization.
We select 0.5 to simulate the mean of generalization bounds. It is worth noting that the binary KL bound (Theorem in (Hellström & Durisi 2022)) is not directly tractable as it involves a high- dimensional stochastic KL divergence quantity:
Theorem 10. (Theorem 7 in Hellström & Durisi 2022) Assume that e(:,)) E [0, 1], then with
probability at least - 8 over the draw of S. and U,
(L,0 + L.,.) 1)
d E
EWIS..
Σ
4.U:
2n i=1
1=1
KL
PRWIS.) PROWIB. B3.0
+ log
2
n
where d(p () = plog(p/0) + +1 p) log((1 pp)(11 q)) is the binary KL divergence.
In order to apply comparisons, we average the binary KL bound above over multiple draws of Ü, S.. In this way, the stochastic KI. divergence can be approximated by:
E
KL ( (PRWIS, PRw(S.)
I(R", ;Ū)S.).
Additionally, we will show that E I(L,,)- L,; U:) serves as a lower-bound approximation for [RR"; ; ;((S)):
Proposition 2. EL I(L LN I I(R.. ;U)S.).
Proof. For convenience, we denote { as Unn Then
(01.) -(R"" ((8.) + 3.)
I(AW; ;Ū) + I(Ü:5.|R")
2 I(RW; :))
-I(R(; (.) + I(R", (02N(()))0)))
-I(R"; (U)) +
;ú2m) I [(22.i i U1) + [(22ni U
-I(RW; (Ū,) + (LR";U2n) + (U2mn i Ü, RWW)
2 I(R"; ;Ú) + I(RW ((RWúu))) ;Ü2m)
I(R": :Ú))
I(L Ú,) + +I(R"
VIWW L. LM)
1( Ü.)
We then evaluate the effectiveness of the proposed thresholding method. As shown in Figure our fast-rate generalization bound (Theorem 6) is considerably tighter than the weighted generalization bound (Theorem 5). Without the thresholding technique, the fast-rate bounds fail to outperform the nower-bound approximation of the binary KL bound. Similarly, Figure 4 demonstrates the effec- tiveness of adaptively choosing coefficients C; for each individual training loss. It can be seen that this strategy is especially useful in the early stage of the training process, where the magnitude of training losses is comparable test losses and remains to be minimized. This behavior is further
44

---

Published as a conference paper at ICLR 2024
3
2
1
0
0.0
0.2
0.4
0.6
0.8
1.0
L
Figure The influence of training loss using the adaptive C, strategy with & 1 in Theorem
verified in Figure 8 that the adaptive C strategy partieularly lowers the bound when the training losses are close (but not equal) to the threshold. For well-trained networks where training losses approach zero, the improvement will be less significant.
To examine the impact of bin size on the visualization results, we additionally report the comparison between generalization bounds with bin size of 0.6 in Figure In general, decreasing the bin size results in larger loss entropy values but lower discretization errors. Therefore, there exists trade-off between these two quantities to acquire the tightest generalization bound. Moreover, we visualize the comparison between different bounds for the test risk instead of the generalization error in Figure Note that each generalization bound directly implies a test risk bound by adding the training risk to both sides.
We further report the comparison between our leave-one-out generalization bound (Theorem 3 and the generalization gap in Figure 7 Although this bound does not capture the behavior of the generalization gap well for large values, we highlight that this the first computationally tractable high-probability generalization bound under the leave-one-our setting.
G FURTHER DISCUSSIONS
G.1 ADDITIONAL RELATED WORKS
brghh-robbbblity generalization bounds in the literature could be categorized by the distribution they are taken over (Hellström et al. 2023):
PAC-Bayesian bounds, which hold with high probability over the draw of the training dataset, but are averaged over the learning algorithm;
Single-draw bounds, which hold with high probability over the draw of both the dataset and single hypothesis;
Mean-hypothheis bounds, high probability bounds of the average hypothesis output from the learn- ing algorithm, given the dataset.
Exponential stochastic inequalities (ESI) were initially employed to derive generalization bounds seminal works by (Zhang, 20066] Catoni 2007). Subsequently, these bounds were formalized by (Kollen et al. 2016 Mhammedi et al. 2019 Grünwald & Mehta 2020). The general form of PAC- Bayesian bounds has been established by (Germain et al.) 2009 Bégin al., [2014) RRvasplata al.) 2020), leading to various specific bounds that leverage the sub-gaussian nature of loss functions (Hellström Durisi 2020) and binary KI. upper bounds for the population risk given the empirical
risk with bounded loss functions (McAllester 2013 Foong al. 2021).
Data-dependent priors based on data splitting were introduced by (Ambroladze et al. 2006) and further extended by (Mhammedi et al. 2019 Dziugaite et al. 2021). Further investigations into dependett priors through the lens of differential privacy were conducted by (Dziugaite & Roy priors is discussed by Catoni (2007); Lever et al. (2013). It is also noteworthy that an essentially equivalent approach to
2018 Rivasplata et al. 2020). The exploration of instribution-dependee
the CMI framework introduced in the PAC- CCy-Baysiann context much earlier by (Audibent 2004
45

---

Published as a conference paper at ICLR 2024
Catoni 2007)
mitigate the variance of PAC-Bayesian generalization bounds, under the name of "almsst exchangeable priors" or "transductive learning".
Beyond PAC-Bayesian bounds, Catoni (2007) noted that analogous techniques can be employed to derive single-draw bounds from the posterior. Rivasplata ct al. (020)) leverages the Radon-Nil Radon-Nikodym derivative to formulate single-draw bounds beyond relative entropy, which are further extended by (Hellström & Durisi 2021b a). Esposito et al. (2021) linked single-draw generalization error with Rényi-, -Divergeenss and Maximal Leakage. Xu & Raginsky (2017) adapted the monitor technique to transform average generalization bounds into single-draw counterparts.
G.2 CONVERGENCE RATE OF LOO BOUNDS
In the interpolating regime where the training risk approaches zero, shown in Theorem II.1 of (Haghifam et al. 2022) that the LOO bound for the expected generalization елгог scales with 1/ log(n)) while our Theorem does not exhibit such property. However, it worth noting that the is still proportional to n even the interpolating regime, so this does not necessarily lead to tighter or computationally tractable bounds when n is large. In contrast, our loss entropy measure (R") reduces to the entropy a single I-dimensional variable, making the bound directly tractable.
dimensionality of the LOO-CMI term 7 T(R"; U (i)))
G.3 DISCRETIZAATIO OF CONTINUOUS LOSS
In practice, the loss function usually continuous (c.g. cross-entropy). While the loss values can be treated discrete variables by the fact that they are stored in digital computers with floating- point numbers, it is impractical to estimate the loss entropy with machine-precision binning size. Instead, show that the loss values could be discretized with arbitrary bin size and still acquire valid generalization bounds. Let > 0 be the bin size and (x( be the rounding function of base b:
(b(x) x arg min
jib z//-
sEN
Since the discretization error of the training risk is directly tractable, we only consider the discretiza- tion error of the test risk:
Proposition For any w E and > O, {2,) ~ μ.th i.i.d samples, L, E(w, Z,) and (D.) Unif([=3 b 2: (1m) be i.idd uniform variables. Then with probability at least 8, we have
4 L Σ LolL, + DJ) sby
2log(1)
Proof. Let Li Li Φb + D.), then is easy verify that ED, [L.] and Li [-b, b). i.e. ī. is b-subgaussian. Since {Tr)== and (D are both ii.d, we have that 1 n - f.p b -n -sbbgauussian. Therefore,
1
nc²
P
L,
2e
I
exp
25
i=1
By taking 8 the RHS of the inequality above, we then have that with probability least 1 5,
2 llg((H)
Σ L.
< bb
n
The proof is complete.
Therefore, by perturbing each test loss with D, Unif([-b b)) and then rounding to the nearest bin, the loss values could be discretized without significant impact the validation error. In this way, one can directly evaluate our main theorems with the discretized losses, and then take the union bound with Proposition B to acquire generalization upper bounds for continuous loss functions. Note that in our main Theorems 3 66] the losses are not required to be deterministic given the model W and sample Z, so these bounds remain valid after introducing external randomness D; by taking the probability over the draw of W. S, (or Ši), Ü (or U) and D,.
46

---

Published as a conference paper at ICLR 2024
G.4 THE INTERPOLATING REGIME
common to observe that at the end of the training progress, the network overfits the training dataset and approaches 100% training accuracy. Such phenomenon corresponds to the interpolat- ing regime, which assumes that the network can always fit the given training dataset and achieve zero empirical risk. This assumption leads certain simplifications and reveals many intriguing properties of iiloormatiinnthhooree 2023). For example, the key information quantities in our main Theorems 3 6 could be simplified to the entropy of samplewise test loss. Furthermore, 5 a convergence rate of O(1/m) when the empirical risk approaches zero. would be tempting to connect generalization analysis under parammtereetiniooon frameworks (e.g. NTK (Chen et al.) 2020) and Mean-field (Nitanda itt al. 2021; Nishikawa et al. 2022; Aminian et al. 2023)) that investigate the interpolating regime, with information -hetorrtio--thoretiic generalization bounds.
generalization bounds (Hellström & Durisi 2022 Wang & Mao,
47


Reviews:
[{"review_id": "p2ydKzON3k", "reviewer": "Reviewer_xf1n", "summary": "This paper proposes a series of PAC information-theoretic generalization bounds based on loss entropy. The novel bounds are tighter than the previous bounds. The authors conducted several experiments that show the superiority of their bounds.", "questions": "- Compared to the bounds in (Kawaguchi et al., 2023), the introduced bounds in this paper, e.g., Theorem 2, do not have any explicit dependency on the input variable $ X$. Interestingly, It only depends on the label $Y$. Can the authors comment on this point? \n\n- Related to my first question, as the bounds depend directly on $Y$, it would interesting to see how sensitive they are to label noise. Do the authors have any comments on this? I think in this case, it might be interesting to conduct an additional experiment with label noise to evaluate how robust the bounds are.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and organized. \n- Deep learning generalization analysis through information-theoretic tools has received a lot of attention lately. This paper makes a sound contribution to this line of work.\n- The theory is sound. I skimmed through most of the proofs (I did not go through all of them in detail)  but the proofs are well-structured, easy to follow, and sound. \n- I like the fact that the paper considers not only one but two settings: the Leave-One-Out Setting and the supersample setting. This makes the work more complete.", "weaknesses": "- The major concern with this work is that the analysis relies on $b^w$ and $B^{w, S}$, which represent the maximum of the loss. I think this makes the bounds sensitive to noise. In fact, it is sufficient that one sample has a relatively high loss to make the whole bound loose. The authors do not perform any experiments or analysis to show how robust their bounds are to noise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EAHNiuWb0o", "reviewer": "Reviewer_gBmk", "summary": "In this paper, the authors introduce novel upper bounds for generalization error or validation error in the context of high-dimensional applications, particularly deep models.", "questions": "See the weaknesses section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper provides some new PAC upper bounds which can be used in deep models.", "weaknesses": "Weaknesses and Questions:\n\n-  In Theorems 1, 2, 3, and 4, it is essential to specify the distribution under which the inequality holds.\n\n- The paper states that \"the model $w$ is deterministic, which is commonly the case for modern deep learning models,\" but notes that $w$ is not truly deterministic due to initialization.\n\n- In the discussion preceding Section 3.2, the authors mention that their data-independent bounds provide insights into understanding the generalization of the MEE criterion. However, for binary classification, margin-based loss functions, as discussed in [1], cannot be represented as a function of $E^w$.\n\n- The effect of the learning algorithm on Theorems 1 and 2 is unclear. It seems that the model, $w$, remains fixed and independent of the training set, limiting the practicality of these upper bounds.\n\n- The proof of Lemma 13 lacks clarity. More elaboration is needed, especially in the last line of the proof.\n\n- The assumption in Theorem 5 that $\\kappa \\geq B^{W,\\tilde{S}}$ guarantees a valid $C_i$ due to the term $\\log(2-e^{2\\eta \\hat{L}_i^W})$. However, Theorem 6 discusses the case where $\\kappa < B^{W,\\tilde{S}}$. Explain how $C_i$ remains valid in Theorem 6.\n\n- If the loss function is bounded, then $B^{W,\\tilde{S}}$ is also bounded. Can the authors provide an example where the loss function is unbounded, but $B^{W,\\tilde{S}}$ remains bounded?\n\n- Please verify the equation between eq. (41) and (42) in the appendix.\n\n- The discussion after Theorem 5 is unclear. Define what an \"interpolating regime\" is, and clarify whether the empirical risk is considered a random variable in Theorem 5.\n\n- The novelty of this work is limited. \n\nSuggestions:\n\n- Include a table summarizing notations in the Appendix.\n\nReferences:\n\n[1]: Bartlett, Peter L., Michael I. Jordan, and Jon D. McAuliffe. \"Convexity, classification, and risk bounds.\" Journal of the American Statistical Association 101.473 (2006): 138-156.\n\n----\n\n\nAfter Rebuttal, I increased my score to 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U8xlAILx19", "reviewer": "Reviewer_YPBm", "summary": "In this paper, several new information-theoretic generalization bounds are derived. These bounds rely on the entropy of the losses of the model. While the proof techniques take inspiration from the information bottleneck approach of Kawaguchi et al, this is combined with the evaluated CMI perspective in the framework of Steinke and Zakynthinou. Both the leave-one-out and standard supersample settings are considered, and fast-rate bounds are derived. The usefulness of the bounds is demonstrated in several ways, both in terms of their correlation with the true error, and in terms of their numerical tightness.", "questions": "(See \"*update*\" at the end of weaknesses for summary of responses)\n\nAs noted in Theorem 3, the proofs require sub-Gaussianity under the _selection_ random variable, which has to hold for any fixed instance of the loss matrix/vector. This seems to get lost in the later derivations. First, in Lemma 14, it is assumed that $\\ell(w,X)$ is sub-Gaussian. This seems to mean that it is sub-Gaussian when taking the expectation over $X$. However, in the proof, it is needed that $\\ell(w,x_U)-\\ell(w,x_{1- U}) $ is sub-Gaussian under $U$ for all $w$, $x_0$, and $x_1$ (or under the distribution where $X$ and $W$ are distributed jointly and $U$ is drawn independently). This does not follow from the sub-Gaussianity that is assumed. There are cases beyond bounded losses that one can consider (e.g., Steinke & Zakynthinou, Thm. 5.1 and Sec 5.4). Is my reading correct or did I miss something? The same issue occurs in Theorem 9.\n\nAlso, for, e.g., the equation preceding (29), it is written $P( \\Delta(W, \\tilde S_l, U) \\geq t )$. This is misleading, as it appears that the probability holds over a joint draw of $(W, \\tilde S_l, U)$, but in fact, only $U$ is random while $W$ and $\\tilde S_l$ is fixed. Is this correct?\n\nAt the end of p.4: the supersample generalization gap approaches the true one, but the same is not true for the leave-one-out, as the test loss is still evaluated on only one sample. Does this limit the usefulness of the LOO results?\n\nIn the numerical evaluations, the cross-entropy loss is used, which is continuous. To compute bounds for MNIST etc, a binning with a bin size of 0.5 is used. The usefulness of the results, despite the assumption of discreteness, was motivated by the fact that floating-point numbers are used in practice. Certainly, machine precision is significantly smaller than 0.5. This specific choice is also not motivated. What is the effect when decreasing the binning size? Is there any reason to believe that  this is a sensible choice?\n\nIn the numerical evaluation, optimization is performed over several constants in the bounds. In the derivation, they are assumed fixed, and the bounds hold with a certain probability for this fixed value. In order to have a valid bound while optimizing, one needs to perform some kind of union bound, or other argument to guarantee the validity. Otherwise, it should be stated that the bounds are not actually valid due to this optimization, but are just illustrative. Did I miss something that motivated this optimization?\n\nThe bounds are said to be compared to the Binary KL bound of Hellstrom and Durisi, but Theorem 10 in the paper is not a binary KL bound. Furthermore, in HD Thm. 7, the information measure that appears is not a CMI, but a random KL divergence depending on the supersample and selection variable. Also, the binary KL bound does not imply a bound on the generalization gap, but instead, directly bounds the population loss given a training loss. Finally, the binary KL bound is inherently only valid for bounded losses, as the binary KL is undefined for inputs outside of $[0,1]$. Is the comparison actually to Thm. 10, i.e., the square-root bound of Hellstrom and Durisi?\n\nThe plots show the generalization gap, rather than the bound on the population loss itself. Arguably, the latter is more interesting, since a low generalization gap with a high training loss is not very useful. Is it possible to show the bound on the population loss?\n\n***\n\nI acknowledge that I may have missed something or misunderstood some of the arguments. If the issues above are addressed, especially regarding the soundness of the results and their evaluation, the relevant ratings will be significantly changed.\n\n***\n\nMinor points and typos:\n\nWhile the somewhat unfortunate acronym LOO appears to be standard, the even more unfortunate acronym SS has, as far as I know, not been used before. Perhaps it is preferable to avoid it.\n\nI am not sure the way the term “PAC” is used is really consistent with PAC learning. PAC bounds are typically uniform in some sense, whereas the bounds in this paper are tail bounds under the joint distribution of data and hypothesis.\n\nBefore Thm. 1: grammar issue\n\np.5, “The most notable improvement of…” here, a comparison is made to CMI bounds instead of e-CMI bounds, which are arguably more relevant; “This illustrates a novel trade-off” is it really a trade-off? Both are just preferred to be small.\n\nFor the notation of $L^{\\kappa}$: perhaps it would be more intuitive to use $L^{<\\kappa}$ and $L^{>\\kappa}$?\n\nIn Lemma 12, it is written $\\eta = ( …, … )$. Should this be $\\eta \\in (… , …)$?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 4, "strengths": "The paper combines ideas from the work of Kawaguchi et al regarding typicality proofs with e-CMI approaches from the line of work starting with Steinke & Zakynthinou, and adds several new ideas on top of this. Information-theoretic generalization bounds have demonstrated the potential to be powerful tools for studying, e.g., deep nets--although their usefulness is still not entirely clear--so the advances are significant.\n\nThe resulting bounds are highly appealing from many perspectives, in that the bounds depend on information measures that are shown to be tighter than existing work in relevant scenarios; high-probability bounds are derived with samplewise metrics and a log-dependency on delta; the quantities are (comparatively) easy to estimate; and the bounds are numerically tight in the studied scenarios.\n\nThe experimental evaluation is extensive, and significant efforts are made to make fair comparisons to prior work (arguably, they are even unfair to the benefit of the prior work). \n\nThe paper contains many instructive comparisons to prior work and discussion of the presented bounds and proof techniques. While the results are not always easy to parse due to the heavy notation and the fact that they simply have a relatively complicated form, I appreciate the \"progressive complexity\" of the presentation: the results are first stated in terms of generic constants, to get an overall view of the result, but they are still explicitly defined immediately after, allowing the reader to see the full details.", "weaknesses": "Most of the weaknesses arise from the application to potentially unbounded losses. If the results are specialized to the 0-1 loss, all of the notable issues seem to disappear.\n\nThere seem to be some issues with the use of sub-Gaussianity in some proofs (see questions).\n\nRegarding the numerical evaluation, the effect of the binning is not at all discussed, but seems like it can have a huge impact. Furthermore, there seem to be some issues with the optimization of the bounds, as well as the comparison with the binary KL bound. All of these are discussed in the questions below.\n\nThe bounds assume discrete loss functions, which enables the use of the entropy and the typicality arguments. Still, the bounds are applied to, e.g., the cross-entropy loss, which is continuous, with the motivation that all losses can be considered discrete due to floating-point numbers. I am not sure if this is convincing. Increasing the precision used would affect the cardinality of the loss, and potentially degrade the bounds. This does not seem like reasonable behavior, and would require a stronger motivation.\n\nIn the data-independent bounds, it is assumed that the features are generated from a function that depends on an $m$-dimensional nuisance variable, and that the model has finite sensitivity to the nuisances, even in a worst-case sense. This seems like quite a strong modelling assumption, but is not motivated or discussed in detail.\n\nTheorem 3 is said to be most useful in the interpolating setting. The interpolating bound of Haghifam et al decays with log(n), unlike the presented bound. This merits a mention and discussion.\n\nSeveral of the bounds on the generalization gap have an explicit dependence on the value of the test loss itself on the right-hand side. For bounded losses, this can simply be upper-bounded, but otherwise it seems quite puzzling.\n\nThe bounds depend on average quantity (entropy), and are hence not empirical. This may merit a disccussion.\n\nPAC-Bayesian bounds are not discussed much, despite being closely related. They are particularly relevant since you point out that recent bounds are “primarily restricted to average-case scenarios”. Moreover, the supersample setting is equivalent to almost exchangeable priors (Audibert, “A better variance control for PAC-Bayesian classification,” 2004 and Catoni, 2007). It also seems relevant to compare to single-draw bounds from, e.g., Esposito et al., \"Generalization Error Bounds Via Rényi-, f-Divergences and Maximal Leakage”, 2020.\n\nSome other minor points are discussed in the questions below.\n\n*Update*: All of these points have been mostly clarified or resolved. The sub-Gaussianity arguments are not super-clear but appear to be fine. The paper now includes a more well-motivated evaluation procedure with regards to the bins, as well as a study of their effect on the bounds. Related work and discussion points have been added. The appearance of the test-loss in the bounds has been shown to be avoidable in some cases, while for others it is argued that it can be reasonably estimated with validation data---although this definitely limits the applicability of the bounds and should be made very clear. I updated the score to a 6 from a 5 following the discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7YhGrfv6kw", "reviewer": "Reviewer_Fiyn", "summary": "This paper propose a series of PAC information-theoretic generalization error bounds via entropy measures (Shannon entropy and Renyi entropy) of loss. Specifically, a data-independent case is first considered that gives a entropy related characterization of concentration. Then in the data-dependence case, PAC-generalization error bounds by entropy measure are proposed for both leave-one-out and supersample settings, and fast-rate bounds.", "questions": "Should we assume the loss has finite alphabet so as to allow well defined Shannon entropy?\n\nMinor:\n\nFirst paragraph of Section 3, \"We begin by enhancing existing upper bounds presented in (Kawaguchi et al., 2022; 2023)\", should it be Kawaguchi et al., 2023 only?\n\nFirst paragraph of Section 5, \"chaining strategy\" and \"random subsets or individual\" with the same ref Zhou et al. 2022.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed bounds based on loss entropy is advantagous since the loss is one-dimensional and easier to estimate. Many scenarios are considered, e.g., leave-one-out, supersample, and fast-rate. As far as I can tell, the proofs are sound. The theory and quantities in the bounds are well-explained. Experiemntal studies show that loss entropy-based bounds have the highest correlation with the error, and gives tighter numerical bounds in many datasets with different optimization algorithms.", "weaknesses": "There is no particular weakness of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)