Nonvacuous Loss Bounds with Fast Rates for Neural Networks via Conditional Information Measures
Authors: Fredrik Hellström
Giuseppe Durisi
Venue:  (2021)

Abstract: We present a framework to derive bounds on the test loss of randomized learning algorithms for the case of bounded loss functions. This framework leads to bounds that depend on the conditional information density between the the output hypothesis and the choice of the training set, given a larger set of data samples from which the training set is formed. Furthermore, the bounds pertain to the average test loss as well as to its tail probability, both for the PAC-Bayesian and the single-draw settings. If the conditional information density is bounded uniformly in the size $n$ of the training set, our bounds decay as $1/n$, which is referred to as a fast rate. This is in contrast with the tail bounds involving conditional information measures available in the literature, which have a less benign $1/\sqrt{n}$ dependence.  We demonstrate the usefulness of our tail bounds by showing that they lead to estimates of the test loss achievable with several neural network architectures trained on MNIST and Fashion-MNIST that match the state-of-the-art bounds available in the literature.

Under review as a conference paper at ICLR 2021
NONVACUOUS Loss BOUNDS WITH FAST RATES FOR NEURAL NETWORKS VIA CONDITIONAL INFORMA- TION MEASURES
Anonymous authors Paper under double-blind review
ABSTRACT
We present a framework derive bounds on the test loss of randomized learning algorithms for the case of bounded loss functions. This framework leads to bounds that depend on the conditional information density between the the output hypothe- sis and the choice of the training set, given larger set of data samples from which the training set is formed. Furthermore, the bounds pertain to the average test loss well to its tail probability, both for the PAC-Bayesiar and the single-draw settings. If the conditional information density is bounded uniformly in the size n of the training set, our bounds decay as 1/n,, which is referred to fast rate. This is in contrast with the tail bounds involving conditional information measures avail- able in the literature, which have less benign 1/ dependence. We demonstrate the usefulness of our tail bounds by showing that they lead to estimates of the test loss achievable with several neural network architectures trained on MNIST and Eeshion-MNIST that match the state-of state-of-the-an the-art bounds available in the literature.
INTRODUCTION
In recent years, there has been a surge of interest in the use of information-theorete techniques for bounding the loss of learning algorithms. While the first results of this flavor can be traced
to the probably approximately correct (PAC)-Bayesian approach (McAllester) 1998 Catoni 2007) (see also (Guedj) 2019) for recent review), the connection between loss bounds and classical iiformation-theoreee measures was made explicit in the works of Russo & Zou (2016) and Xu
Raginsky (0017), where bounds on the average population loss were derived in terms of the mutual information between the training data and the output hypothesis. Since then, these average loss bounds have been tightened (Bu et al. 2019 Asadi et al. 8 Negrea al. 2019). Furthermore, the information-theorre framework has also been successfully applied to derive tail probability bounds on the population loss (Bassily et al. 2018 Esposito et al. 2019 Hellström & Durisi 2020a
Of particular relevance to the present paper is the condom-subsed setting, introduced by Steinke & Zakynthinou (220)) and further studied in (Hellström & Durisi 2020b [Haghifam al. 2020). In
this setting, a random vector S is used to select training samples Z(S) from larger set Z of 2n samples. Then, bounds on the average population loss are derived in terms of the conditional mutual information (CMI) I [WW; Z) between the chosen hypothesis W and the random vector S given the set Z. The bounds obtained by Xu & Raginsky (2017) depend on the mutual information I I(W; Z). a quantity that can be unbounded if W reveals too much about the training set Z. In contrast, bounds for the random-subset setting are always finite, since / (W; 2|Z) is never larger than n bits.
Most information-theoreee population loss bounds mentioned thus far are given by the training loss plus term with a /IM (M(Pwz))/ /ndddeddeeeeeee / where IM Pwz) denotes an information measure, such mutual information maximal leakage (Issa et al. 2020). Assuming that the information measure grows at most polylogarihhmicaly with n, the convergence rate of the population loss to the training loss is ( nT). where the O-notation hides logarithmic factors. This is sometimes referred to a slow rate. In the context of bounds the excess risk, defined as the difference between the achieved population loss for a chosen hypothesis w and its infimum over the hypothesis class, is known that slow rates are optimal for worst-case distributions and hypothesis classes (Talagrand.

---

Under review as a conference paper at ICLR 2021
1994). However, it is also known that under the assumption of realizability (i.e., the existence of in the hypothesis class such that the population loss LPz (w) = 0) and when the hypothesis class is finite, the dependence on the sample size can be improved to ((1/n) (Vapnik) 1998| Chapter 4). This is referred as a fast rate. Excess risk bounds with fast rates for randomized classifiers have also been derived, under certain additional conditions, for both bounded losses (Van Erven et al.
2013) and unbounded losses (Grünwald & Mehta 2020).
Notably, Steinke & Zakynthinou (2020 Thm. 2(3)) derive population loss bound whose dependence on n is (W; S Z)/n. The price for this improved dependence is that the training loss that is added to the n-dependent term is multiplied by a constant larger than 1. Furthermore, (Steinke & Zakynthinou 2020] Thm. 8) shows that if the Vapnik-Chervonenn
(VC) dimension of the hypothesis class is finite, there exists an empirical risk minimizer (ERM) whose CMI grows at most logarithmically with n. This implies that the CMI approach leads to fast-rate bounds in certain scenarios. However, the result in (tteinke & Zakynthinou 2020 Thm. 2(3)) pertains only to the average population loss: no tail bounds the population loss are provided. Throughout the paper, we will, with abuse of terminology, refer to bounds with an n-dependence of the form IM(Pwz) )/n as fast-rate bounds. Such bounds are also known as linear bounds (Dziugaite et al. 2020). Note that the n-dependence of the information measure (M(wwz) has to be at most polylogarithmic for such bounds to actually achieve a fast rate in the usual sense.
An intriguing open problem in statistical learning is to find a theoretical justification for the capability of overparameterized neural networks (NNs) achieve good generalization performance despite being able to memorize randomly labeled training data sets (Zhang et al.) 2017). As consequence of this behavior, classical population loss bounds that hold uniformly over a given hypothesis class, such as VC bounds, are vacuous when applied to overparameterized NNs. This has stimulated recent efforts aimed at obtaining tighter population loss bounds that are algorithm-dependent or data-dependent.
In the past few years, several studies have shown that promising bounds are attainable by using techniques from the PAC-Bayesian literature (Dziugaite & Roy 2017: Zhou et al.) 2019; Dziugaite ct al. 2020). The PAC- PAC-Bayesian approach entails using the Kullback- Leibler (KL) divergence to compare the distribution on the weights of the NN induced by training some reference distribution. These distributions are referred to as the posterior and the prior, respectively. Recently, DZiuuaate et al.) (2020) used data-dependent priors to obtain state-of-the-arr bounds for LeNet-5 trained on MNIST and Mashion-MNIST. In their approach, the available data is used both for training the network and for choosing the prior. This leads a bound that tighter than previously available bounds. Furthermore, the bound can be further improved by minimizing the KL divergence between the posterior and the chosen prior during training. One drawback of the PAC-Bayesian approach is that it applies only to stochastic NNs, whose weights are randomly chosen each time the network is used, and not to deterministic NNs with fixed weights.
Information -thoooeticicc bounds have also been derived for iterative, noisy training algorithms such as stochastic gradient Langevin dynamics (SGLD) (Bu et al. 2019). These bounds lead to nonvacuous estimates of the population loss of overparameterized NNs that are trained using SGLD through the use of data-dependent priors (Negrea et al. 2019). However, these bounds do not apply to deterministic NNs, nor to standard stochastic gradient descent (SGD) training. Furthermore, the bounds pertain to the average population loss, and not to its tails. Although the techniques yielding these estimates be adapted to the PAC-Bayesian setting, discussed by Negrea et al. (2019 App. I), the resulting bounds are generally loose.
1.1 CONTRIBUTIONS
In this paper, we extend the fast-rate average loss bound by Steinke Zakynthinou (2020) to the PAC-Bayesial and the single-draw settings. We then use the resulting PAC-Bayesian and single-draw bounds to characterize the test loss of NNs used to classify images from the MNIST and Fashion- MNIST data sets. The single-draw bounds can be applied to deterministic NNs trained through SGD but with Gaussian noise added to the final weights, whereas the PAC- AAC-Bayesian bounds apply only to randomized neural networks, whose weights are drawn from a Gaussian distribution each time the network is used. For the same setup, we also evaluate the slow-rate PAC- BCC-Baysiann and single-draw bounds from (Hellström & Durisi 2020b). Our numerical experiments reveal that both the slow-rate
2

---

Under review as a conference paper at ICLR 2021
bounds from (Hellström & Durisi 2020b) and the newly derived fast-rate bounds are nonvacuous. Furthermore, for some settings, the fast-rate bounds presented in this paper are quantitatively stronger than the corresponding slow-rate ones from (Hellström & Durisi 2020b), and essentially match the best bounds available in the literature for SGID-trained NNs (Dziugaite et al. 2020).
1.2 PRELIMINARIES
We now detail some notation and describe the Zakynthinou 2020). Let 2 be the instance space, W be the hypothesis space, and é W x E R be the loss function. Throughout the paper, we will assume that the range of E(we, 2) is restricted to [0, 1] for all E W and all E Z. A typical example of such a loss function is the classification error. this setting, the sample Z consists of an example X E X and a corresponding label E V. 1{fw (X) * Y), where fw(.) is the map from X' to induced
setting introduced in (Steinke &
Then, the loss is given by ((W by the hypothesis W. We note that, when applying our bounds to NNs, the function ((:,)) used to characterize the performance of the network does necessarily need to coincide with the loss function used when training the NN. For instance, one could use the (unbounded) cross-entropy loss when training the NN, and apply the bounds for the scenario in which {(; .) is the classification error.
In the random-subset setting, 2n training samples Z =Z Zzn) are available, with all entries of Z being drawn independently from some distribution Pz on 2. However, only a randomly selected subset of cardinality assume that the training data (SS) is selected as follows. Let S random vector, the elements of which are drawn independently from Bern(1/2) distribution and are independent of Z. Then, for i = ...... n. the äth training sample in 2(5) is (S.) = 7. Thus, the binary variable S; determines whether the training set (S)) will contain the sample 2, or the sample Zi+n. The selected training procedure, including the loss function used for training, will determine the conditional distribution Pwiz(S)) on the hypothesis class given the training data. For a given W ~ Pw)z(()) we let L2(s) (W) = En= &(W Zi denote the training loss. Furthermore, we let S denote the modulo-2 complement of S. Then (-2(5) (W) can be interpreted as a test loss, since W is conditionally independent of ZSS) given (SS) Finally, we note that the average over Z S) of the test loss is the population loss T.p (W)- Eppy (T (W) Ep, [e(W, Z)).
actually used for training. Following (Steinke & Zakynthinou 2020), we
(SI..... S,,) be an n-dimensional
Our bounds will depend on several different information- -hhoretic quantities, which we shall intro- duce next. The information density zWW, Z) between W and Z is defined as eWW, Z) = log dPwz aPwPz* where dPwz is the Radon-Nikodym derivative of Pwz with respect to PwPz. The informa- aPwP2 tion density is well-defined if Pwz is absolutely continuous with respect to PwPZ, denoted by Pwz < PwPz. The conditional information density <WW S|Z) between W and given Ž zs. The mutual infor- Z) Erwz (WW, Z)] and the conditional mutual information as T(W; 2) = P.P (W,S) Z) We will also need the KI. divergences D(Pwiz || Pw) =
is defined as (WW S) = log JP, w 2 P
dP dFwss provided that P Pwzs < Pw PwizPzs
mation can be obtained T(W:
(W, S ) In practical applications, the marginal distribution Pw is not available, since Pz is unknown. Furthermore, PwIž also difficult to compute, since marginalizing Ps PsPwij w12s over S involves performing training 2n times. Hence, bounds depending on iWW Z) or on tWW, SIž) cannot typically be evaluated. Therefore, it will be dPwz and e(W convenient to replace the information density zWW Z) with the proxy log áQw'zz dPwws Here, Qw and Qw are suitably chosen auxiliary distributions (priors) that with log aQ 22 used in place of the intractable, true marginals.
Epwiz Tiiizl [,(W, Z)] and ((P (( || P Pi]2) = EP 2s
2 BACKGROUND
We next review the bounds available in the literature that relevant for this paper. Then, in Section 3 we will present novel fast-rate bounds. The canonical PAC- AAC-Bayesian population bound for a given posterior Pwiz z and loss functions bounded between 0 and 1 states that the following holds
3

---

Under review as a conference paper at ICLR 2021
with probability at least - 8 under Pz (Guedj & Pujol 2019 Prop. 3):
D(Pwiz l1 Qw) + log
BP IL (W)) - 1 +
(1)
2n
Here, Qw is the prior on the hypothesis space W. which has to be independent of Z. The version of the bound given in (T) slightly improves the dependence on the sample size as compared to the bound reported in (McAllester, 2003 Thm. D), at the cost of not holding uniformly for all posteriors. We note that, due to the square root, this is a slow-rate bound. By adapting proof technique introduced by ba(Cto (2007) Thm. 1.2.6), McAleestr (013) Eq. (21)) derived the following alternative bound: for all y E R. and with probability at least
under Pz.
(E (L II Pw z p. (W))) S 71 [[(Pwiz
(ivvz2|Quu0 (1 + log 1 5
(2)
Here, d,(411p)= - r - log(1 - pe and one can show that sup, dy (4 [I - d(a p). where d(g lI indicates the KI. divergence between two Bernoulli distributions with parameters q and p respectively. This bound, with d [ || p) replaced by d(q [p) slightly improves the dependence on the sample size n as compared to an earlier bound reported in (Seeger 2002 Thm. 1), but again at the cost of losing uniformity over posteriors. Let q Erwjz 2 [Lz(W] } and let c denote the right-hand 2 to bound the population loss, we need to find
side of (2). To use the result in
p" (g. c) = sup(p: p E [o, 1], d(g lIp) s
This is the largest population loss that satisfies the inequality ( For small q and c, we have p" (g. c) R which gives us fast-rate bound. More generally, for any permissible values of q and c, the bound in (2 can be weakened to obtain the following fast-rate bound (McAllester) 2013 Thm. 2): for all
00, 1), and with probability at least 8 under Pz.
1 EAwIz PL (W)) S x
BPw ( + D(PwIz 11 Qw) + log
(4)
2(1 A)n
Note that the faster decay in n of this bound comes at the price of a multiplication of the training loss and the KL term by constant that is larger than 1. As a consequence, if the training loss the KL term are large, this multiplicative constant may make the fast-rate bound in 44) quantitatively worse than the slow-rate bound in (T) for fixed In the called interpolating setting, where the training loss is O, we can set À = 1/2 in (4) and conclude that it is enough for the square-root term in (1 to be smaller than 1/4 for the fast-rate bound 44 be tighter than the slow-rate bound (I). Additional insights on the tightness of these bounds are provided in (Letarte et al. 2019 Thm. 3).
We now turn to the random-subset setting introduced by [Steinke& & Zakynthinou (2020), and described in Section 1.2 In (Steinke & Zakynthinoul 2020 Thm. 2), several bounds on the average population
loss are derived for loss functions bounded between 0 and 1, including the following slow-rate and fast-rate bounds:
21(W:
Ep Ep [L2 (W)) < Pw [Z((s)
(5)
n
Epw2 [L, (W)) < PPp [Lz(s) (W)] + 3/WW; Z)
(6)
the price for a fast rate a multiplicative constant in front of the training loss and the mutual information term. The slow-rate bound in (5) was improved in (Haghifam et al. 2020) Thm. 3.4) by combining the samplewise approach from (Bu al. 2019) with the disintegration approach in (Negrea et al. 2019). whereby the expectation over Z. which is implicit in the definition of CMI, is pulled outside of the square root. As we detail in the following proposition, the bound in (Haghifam et al. 2020 Thm. 3.4) can be further tightened by also pulling out the expectation with respect the conditional distribution P Pwiz from the square root. The proof of the resulting bound, which is novel, is deferred to Appendix A.I
Similar to the bound
Proposition 1. Consider the random- setting described in Section 1.2 Then,
Ep w2s [LPz (W) < Ep [Lzis)
+ n Σ Ep
Epwa
w2
2D(Ps.
2D
s.
Ps.))
(7)
4

---

Under review as a conference paper at ICLR 2021
We recover (Haghifam et al. 2020 Thm. 3.4) by applying Jensen's inequality to move the expectation with respect to W1 2 inside the square root. Furthermore, we recover (5) by applying Jensen's s inequality once more to move the remaining expectation over I' and the the empirical average over i inside the square root and by upper-bounding the resulting sum of samplewise CMIs by [(W; (WW5)
In (Hellström & Durisi 2020b), the slow-rate average loss bound (5) was extended to the PAC- Bayesian setting and the single-draw setting through the use of exponential inequality. Specifically, the following bounds on the test loss Lz(s) (W) are derived: with probability at least - under P Zs.
Pw 2s LZ(ss (W)] & Br [L](s) + V
2
[ D(Pwizs zs Pl log 2
(8)
Furthermore, with probability at least 1 8 under P Pwss
1 z + / ((W..)))) log
(2) s LW)))
While the bounds in and 9 pertain the test loss instead of the population loss, one obtain population loss bounds by adding a penalty term to 8 and (9). as discussed in (Hellström & Durisi 2020b Thm. 2). However, when comparing the bounds to the empirical performance
learning algorithms, the population loss is unknown. Thus, in practice, one has to resort to evaluating test loss. Section SectionfJbelow. below, we will derive fast-rate analogues of the tail bounds X and again the price of multiplicative constants.
3 FAST-RATE RANDOM-SUBSER BOUNDS
We now present an exponential inequality from which several test loss bounds can be derived, in a similar manner as done in (Hellström & Durisi 2020b). The derivation, which echos part of the proof of (Steinke & Zakynthinou 2020; Thm. 2.(3). is provided in Appendix A.2 This result and
its proof illustrate how to combine the exponential -inquiilliiuuuaitty approach from (Hellström & Durisi 2020b) with fast-rate derivations, like those presented in (Steinke & Zakynthinou 2020 Thm. 2.(3)) and (McAllester) 2013 Thm. 2).
Theorem 1. Consider the candom-uubsel setting introduced in Section 1.2
Let W E W be distributed according to Pwiz(s) = Pwizs. Also, assume that the joint distribution Pwzs = Pwizs PzPs
is absolutely continuous with respect to Q Qwiz PsPs for some conditional prior Q Q Then, the following holds:
dP dPwis w2s 2n I. (.z(s) (W) loog dQw ž Pas (Z)S)) 3
] ST.
exp
(10)
3
Note that the exponential function in (10 depends linearly on the population loss. In contrast, the exponential inequality derived in (Hellström & Durisil 2020b Thm. 4) to establish slow-rate
generalization bounds for the random-subset setting depends quadratically on the population loss (after the parameter X therein is suitably optimized). This difference explains why Theorem T allows for the derivation of fast-rate bounds, whereas (Hellström & Durisi] 2020b] Thm. 4) unavoidably
leads to slow-rate bounds. Also note that, since in the random-subsee setting W and Z are dependent both before and after any change of measure argument, the proof technique used in (McAllester 2013 App. A) and, previously in (Seeger 2002 Thm. 1), to derive ( cannot be used in the random-subset setting.
By simple applications of Jensen's 's inequality and Markov's inequality, the exponential inequality (10) can be used to derive bounds the population loss or test loss. In particular, detailed in the proof of Corollary [ below (see Appendix A.3). it can be used to recover (6). but also to establish novel PAC-Bayesian and single-draw versions of (6).
Corollary 1. Consider the setting of Theorem
Then, the average population loss is bounded by
3 D(Pw)žs 11
Epwzs [Lpz (W)) $2
22EEpws Pzss
Lz(s) +
(11)
5

---

Under review as a conference paper at ICLR 2021
Furthermore, with probability at least 1 8 over Pzs the PAC-Bayesian test loss is bounded by
(D(P w 11 + log
Br [_)(ss S S2EP [ziss) (W)
(12)
n
Finally, with probubility least over P Pwzs the single-draw test loss bounded by
3 (log
dPw2s + log aQw12 P2s
L2( - 2L (W))
(13)
Setting Qwiž = Ww]6 in 11 we recover the CMI bound in (Steinke & Zakynthinou 2020
since 22 D(P'v w žs
[w]z) ;(W; S| As illustrated in Corollary below, the bound on the average population loss in (11 can be tightened by replacing the CMI with sum samplewise
CMIs. The proof of this result, which involves the same argument used to establish Proposition | is presented in Appendix A.4
Corollary 2. Consider the setting of Theorem
| Then, the average population loss is bounded by
3I(W;
Ep LPz (W) S 22P was (W) +
(14)
n
The bounds in [2) and 13 are data-dependent, i.c., they depend on the specific instances of Ž and S. They can be turned into data-independent bounds that functions of the average of the information measures appearing in (12) and (13), at the cost of a less benign polynomial dependence on the confidence parameter 8. Alternatively, one can obtain bounds that have more benign dependence on 5 if one allows the bounds to depend on sufficiently high moments of the information measures appearing in (12) and [13,, or if one replaces these measures by quantities such conditional maximal leakage or conditional a-divergence. See (Hellström & Durisi 2020b for further discussion.
We conclude by noting that for the interpolating case where (z)s) (W) O, and under the additional assumption that Q w -w one can obtain a different exponential inequality than the one re- ported in Theorem [1 which leads to tighter bounds than the ones reported in Corollary Specifically, in these alternative bounds, the factor 3 is replaced with factor of 1/ 1/og(2) x 1.44. These bounds presented in Appendix [
EXPERIMENTS
To assess the ability of the bounds just discussed to predict the performance of overparameterized NNs, we next present the result of several numerical experiments for different NN architectures. Specifically, we consider fully connected NNs (FCNNs) and convolutional NNs (CNNs). The performance of the networks is evaluated on the MNIST and Fashion-MNISS data sets. The bounds where we set the loss function to be the classification
that we will consider are (8) (9. 12 and 13
error defined in Section
The following procedure is used to evaluate the bounds: from the 2n available training samples Z (from MNIST or Pashi,n-MNIST), the training set Z(S) is constructed by selecting training samples uniformly at random. network then trained on this data set using a standard SGD procedure, which is described in more detail in Appendix C.2 Let tyl be the the vector containing the weights of the network after training. The posterior distribution Wwizs is then chosen to be
Gaussian distribution with mean μ4 and covariance matrix equal to of where d is the number of parameters in the network. The standard deviation 01 is chosen as the largest real number, determined to some finite precision (see Appendix C.2 for which the absolute value of the difference between the training loss of the network with weights μ4 and the empirical average of the training loss achieved by 5 NNs with weights randomly drawn from (WW μt La) less than some specified threshold.
Unless otherwise specified, we use threshold of 0.05 for MNIST and 0.10 for Fashion-MNIST Note that this procedure is performed for fixed Z ZSS). Consequently, ai depends on Z and S.

---

Under review as a conference paper at ICLR 2021
To select the prior Qw we proceed as follows. We form 10 subsets of Z, each of size n. The first subset contains the first n samples in Z, the last contains the last n samples in Z, and the remaining subsets contain the linearly spaced sequences in between. We then train one NN on each subset and denote the average of the final weights of these networks by μ22. Finally, we choose Qw w as a
Gaussian distribution with mean P2 and covariance matrix TÂ To select d2, we proceed as follows. First, we determine the largest real number 22, again to some finite precision, for which the absolute value of the difference between the training loss of a NN with weights μl and the empirical average of the training loss of NNs with weights drawn from N(W 1/2. /22 TāTa) below the selected threshold. Note that this time the training loss is evaluated over the entire data set Z, so that there is no dependence on S. We then use 3g form a set of 27 candidate values for d2, from which we pick the one that results in the tightest bound on the test loss. This procedure, the details of which are given in Appendix C.2 typically results in 02 o Note that the prior and the posterior distribution satisfy the assumptions needed for the bounds (8) D.. 12 and (13) to hold. Indeed, (11, depend on Z only through Z ZS)) while (2) are independent of S but depend on Z.
Equipped with these Gaussian distributions, we evaluate the bounds by noting that, for the chosen prior and posterior, the Radon-Nikodym derivatives in 9 and (13) reduce to likelihood ratios, and the KL divergences in (8 and 12 can be evaluated as
|11
p2
o + log oi -1).
02
D(P w zs Qw1z)
(15)
0
Since the MNIST and Fashion-MNIST data sets are fixed and we are unable to draw several data sets from some underlying data distribution, we evaluate our bounds for these particular instances of Z. We do however have control over S, so we run experiments for 10 instances of S and present the resulting mean as well as standard deviation. Note that since we pick the training set uniformly at random from Z, we implicitly randomize over the ordering of the elements of Z.
Our results are obtained by setting d x 0.001 as the confidence parameter. However, since the bounds are optimized over the choice of 02, we need to use a union bound argument (Dziugaite & Roy 2017 Dziugaite et al., 2020) to guarantee that the final slow-rate and fast-rate bounds hold for all of these candidates simultaneously. As consequence, the bounds depicted in the figure hold with probability at least 95%. The test loss and training loss are computed empirically by averaging the performance of 5 NNs whose weights are sampled from N(W |4, af).. For the FCNNs, we use the notation W. to denote an architecture consisting of hidden layers with width W. For the case of CNNs, consider the modified LeNet-5 architecture used in (Zhou et al. 2019) and (Dziugaite cct al. 2020). Detailed descriptions of these architectures are provided in Appendix C.T
In Figure we study the dependence of the bounds on the number of training epochs. The shaded areas around the curves correspond to two standard deviations. The differences between the PAC- Bayesian and the single-draw bounds turn out to be negligible, so we include only the PAC-Bayesian bounds in the figure. The networks are optimized using SGD either with or without momentum. Specifically, in Figures d we use SGD without momentum, while in Figures De-f, we use SGD with momentum. In Figures [h-d, we look at the carly training epochs, while in Figures [ we train the networks until a small training loss (on the order of 0.001) is achieved. More details about the training procedures are given in Appendix
As seen in Figures Tadd, where SGD without momentum is used, the bounds on the test loss are fairly accurate for both architectures, and both MNIST and Fashion-MNIST. As previously discussed, the relative ordering of the slow-rate bounds and the fast-rate bounds from quantitative standpoint depends on the details of the learning setup. In particular, higher values for the training loss and information measures tend to make the slow-rate bounds tighter due to their smaller constant factors. As consequence, the fast-rate bounds superior for the MNIST data set, for which low training loss and information measures are achieved, while the slow-rate bounds are tighter for the more challenging Mushion-MNIST data set. Note that, due the training procedure used, the underlying deterministic NNs upon which Figures Ta-d are based never reach training errors below a few percent.
To shed light the relationship between the results presented in Fig. T d and previously obtained bounds, we compare our bounds on the test loss with those reported in (Dziugaite et al., 2020), which established the best available PAC- Bay-eaa bounds for the settings we consider. The approach used
7

---

Under review as a conference paper at ICLR 2021
Slow-rate bound
0.8
Fast rate bound
0.8
Test loss
Clavsification error
Classincation
0.6
Training loss
0.6
0.4
0.4
0.2
0
10
20
40
10
30
40
Training epochs
Training epochs
(a) LeNet-5, MNIST, no momentum
(b) 600 FCNN for MNIST, no momentum
0.8
0.8
Classiication error
Classifcation
0.6
0.4
0.2
0.2
0
Training epochs
Training epochs
(c) LeNet-5, Fashion-MNNN MNIST, momentum
(d) 600 FCNN, Fashion-MNIST,
0.8
0.8
Cluvsiiicatinn error
Classifcuttin
0.6
0.6
0.4
0.4
0.2
50
100
150
200
50
100
150
200
Training epochs
Training epochs
(e) LeNet-5, MNIST, momentum, low threshold
(f) LeNet-5, MNIST, momentum, high threshold
Figure 1: The estimated training losses and test losses as well as the slow-rate ( and fast-rate 12
PAC- MAC-Bayesian bounds on the test loss for two NNs trained on MNIST Fashion-MNY MNIST. The shaded regions correspond to two standard deviations. In (a)-(d), we perform training using SGD without momentum with decaying learning rate. In (f)-(f, we use SGD with momentum and fixed learning rate. Further details on the experimental setup are given in Appendix C
therein is similar to the random-subset setting considered in this paper, in that the authors make use of data-dependent prior. The key differences with respect to the framework considered in this paper that the posterior in Dziugaite al. (2000) is allowed to depend on the entire data set Z. whereas the training loss and prior depend on randomly selected disjoint subsets of Z. In contrast, in the random-subset setting considered in this paper, the prior is allowed to depend on the entire data set
Z, whereas the training loss and posterior depend only randomly selected portion Z(S) of Z.
8

---

Under review as a conference paper at ICLR 2021
For the case in which training is performed using SGD, the minimum test loss bounds (averaged over 50 runs) for MNIST reported in (Dziugaite et al. 2020 Fig. 4) are approximately 0.13 for LeNet-5 and 0.18 for the 600 FCNN. These values similar to our best bounds, which are 0.15 for LeNet-5 and 0.19 for the 600 FCNN. For LeNet-5 trained on Fashion-MNY
our tightest bound on the test loss is 0.35, whereas the corresponding one in (Dziugaite et al. [020 Fig. 4) is approximately 0.36. Taking error bars into account, our bounds are not clearly distinguishable from those reported in (Dziugaite et al. 2020. Fig. 4). reported in (Dziugaite et al. 2020, Fig. 5) for the case in which the PAC-Bayesiad bound considered therein is used as a regularizer during the training process. Such a direct optimization of the bound does not appear to be feasible for the mudommsubset setting considered in this paper.
important mention that significantly tighter bounds are
Next, we discuss the results presented in Figures - become tighter in the initial phase of training. they lose tightness as training progresses when momentum used and smaller training errors (on the order of 0.001) are reached for the deterministic NNs. This is similar to what is noted by Dziugaite et al. (2020) p. 12). Specifically, when the underlying deterministic NN therein is trained to achieve very low errors (or equivalently, is trained for many epochs), the PAC-Bayesiag bound they consider becomes loose, and the corresponding stochastic NN has a significantly higher test error than the underlying deterministic NN.
f. As shown in the figure, while our bounds
Finally, the difference in behavior of our bounds in Figure Ic and Figure Ii illustrates the role played by the variances σ1 and d2 In Figure Tel we set the threshold used to determine d1 and d2 to 0.05, which leads to small values for di and 02- In Figure Ti we use threshold of 0.15 instead, which allows for larger variances. The results illustrate the intuitive fact that larger variances yield better generalization bounds at the cost of a higher true test error.
Further numerical experiments, in which we study how the bounds evolve as a function of the size of the training set, and how they are affected by randomized labels, are reported in Appendix D
CONCLUSION
We have studied thforoition-theerrtiie bounds on the test loss in the random-subset setting, in which the posterior and the training loss depend on randomly selected subset of the available data set, and the prior allowed to depend on the entire data set. In particular, we derived new fast-rate bounds for the PAC-Bayesian and single-draw settings. Provided that the information measures appearing in the bounds scale sublinearly with n, these fast-rate bounds have a better asymptotic dependence on n. than the slow-rate PAC-Bayesiag and single-draw bounds previously reported in (Hellström & Durisi 2020b), at the price of larger multiplicative constants. We also presented improvements on previously presented bounds on the average loss by using samplewise information measures and disintegration.
Through numerical experiments, we show that our novel fast-rate PAC-Bayesian bound, as well as its slow-rate counterpart, result in test-loss bounds for some overparameterized NNs trained through SGD that essentially match the best available bounds in the literature (Dziugaite et al. 2020). Furthermore, the single-draw counterparts of these bounds, which bounds, are applicable also to deterministic NNs trained through SGD and with Gaussian noise added to the final weights. On the negative side, illustrated in Fig. Te. the bounds turn out to be loose when applied to NNs trained to achieve very small training errors. Moreover, the additional experiments described in Appendix D reveal that the bounds overestimate the number of training samples needed to guarantee generalization, and that they become vacuous when randomized labels are introduced.
tight as the PAC-Bayesian
Still, the results demonstrate the value of the random-subset approach in studying the generalization capabilities of NNs, and show that fast-rate versions of the available information-thhoreet bounds can be beneficial in this setting. In particular, the random-subset setting provides a natural way to select data-dependent priors, namely by marginalizing the learning algorithm Pwižs over S, either exactly or approximately. Such data-dependent priors are a key element in obtaining tight information-theoreti generalization bounds (Dziugaite al. 2020).

---

Under review as a conference paper at ICLR 2021
REFERENCES
A. R. Asadi, E. Abbe, and S. Verdú. Chaining mutual information and tightening generalization bounds. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Montreal, Canada, Dec. 2018.
R. Bassily, S. Moran, I. Nachum, J. Shafer, and A. Ychudayoff. Learners that use little information. J. of Mach. Learn. Res., 83:25-55, Apr. 2018.
Y. Bu, Zou, and V. Veeravalli. Tightening mutual information based bounds on generalization error. In Proc. IEEE Int. Symp. Inf. Theory (ISIT), Paris, France, July 2019.
O. Catoni. PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning, volume 56. IMS Lecture Notes Monogr. Ser., 2007.
G.K. Dziugaite and D.M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proc. Conf. Uncertainty in Artif. Intell. (UAI), Sydney, Australia, Aug. 2017.
G.K. Dziugaite, Hsu, W. Gharbieh, and D.M. Roy. On the role of data in PAC-Bayes bounds, June 2020. htRLttts::/aaat
abs wttp://.wwr/aabb/0...000000
A.R. Esposito, M. Gastpar, and Issa. Generalization emror bounds via Rênyi f-divergences and maximal leakage. arXiv, Dec. 2019.
01439
P.D. Grünwald and N.A. Mehta. Fast rates for general unbounded loss functions: from ERM to generalized Bayes. J. of Mach. Learn. Res., 83:1-80, Mar. 2020.
B. Guedj. A primer on PAC-Bayesian learning. arXiv, Jan. 2019. URL http:://axii...t/
abs 190119911..0 05353
B. Guedj and L. Pujol. Still no free lunches: the price to pay for tighter PAC-Bayes bounds. arXiv, Oct. 2019. URL http: /arxxvv.avvvv//////////aa///vvv org/abs/ 9910.0.00 04460
M. Haghifam, J. Negrea, A. Khisti, D.M. Roy, and G.K. Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. arXiv, Apr. 2020. URI httptt
www.aas./////oooooo/////o///.aar 2004 12983
Hellström and G. Durisi. Generalization error bounds via mtth central moments of the information density. In Proc. IEEE Int. Symp. Inf. Theory (ISIT), Los Angeles, CA, June 2020a.
Hellström and G. Durisi. Generalization bounds via informatin and conditional information density. (June 2020), 2020b. http:tttppp/axx..oo////////
08044
I. Issa, S. Kamath, and A. Wagner. An operational approach information leakage. IEEE Trans. Inf. Theory, 66(3): 12571667,6666666661 Mar. 2020.
Gaël Letarte, Pascal Germain, Benjamin Guedj, and Francois Laviolette. Dichotomize and generalize: MAC-Bayesian binary activated deep neural networks. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Vancouver, Canada, Dec 2019.
D.A. McAllester. Some PAC-Bayesian theorems. In Proc. Conf. Learn. Theory (COLT), pp. 230-234, Madison, WI, July 1998.
D.A. McAllester. PAC-Bayesian stochastic model selection. Mach. Learn., 51:5-21, Apr. 2003.
D.A. McAllester. A PAC-Bayesian tutorial with a dropout bound. July 2013. URL httt:://p///xii
org/abs/ /aob///113..00 2118
Negrea, M. Haghifam. G.K. Dziugaite, A. Khisti, and D.M. Roy. Information information-theoretic theoretic general-
ization bounds for SGLD via data data-dependent estimates. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Vancouver, Canada, Dec. 2019.
Y. Polyanskiy and Wu. Lecture Notes On Information Theory. 2019. URL hwtp:ttp::/wwt. stat
e. edu/
10

---

Under review as a conference paper at ICLR 2021
D. Russo and J. Zou. Controlling bias in adaptive data analysis using information theory. In Proc. Artif. Intell. Statist. (AISTATS), Cadiz, Spain, May 2016.
M. Seeger. PAC-Bayesian generalisation error bounds for Gaussian process classification. J. of Mach. Learn. Res., 3:233-269, Oct. 2002.
T. Steinke and L. Zakynthinou. Reasoning about generalization via conditional mutual information. Conf. Learn Theory (COLT), 125:1-16, July 2020.
M. Talagrand. Sharper bounds for Gaussian and empirical processes. Ann. Probab., 22(())28-76 Jan. 1994.
T. Van Erven, P.D. Grünwald, N.A. Mehta, M.D. Reid, and R.C. Williamson. Fast rates in statistical and online learning. J. of Mach. Learn. Res., 16: 793-1881,, Sep. 2015.
V. Vapnik. Statistical Learning Theory. John Wiley & Sons, New York, 1998.
A. Xu and M. Raginsky. Information-theerrticc analysis of generalization capability of learning algorithms. In Proc. Conf. Neurul Inf. Process. Syst. (NeurIPS), Long Beach, CA, Dec. 2017.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In Proc. Int. Conf. Learn. Representations (ICLR), Toulon, France, Apr. 2017.
W. Zhou, V. Veitch, M. Austern, R.P. Adams, and Orbanz. Non-vacuous generalization bounds the ImageNet scale: PAC-Bayesian compression approach. In Proc. Int. Conf. Learn. Representations (ICLR), New Orleans, LA, May 2019.
A PROOFS
A.1 PROOF OF PROPOSITION
Consider fixed hypothesis w W and supersample ž z Due to the boundedness of ((-,)) +), the random variable (w, Σ, S,) = f(w, (S,)) - f(w. (S))) )) is bounded to [-1,1] for i =
1..... n, and it has zero mean. Subgaussianity then implies that the following holds for all X 0:
A
E Ers, (exp(Agen, E, exp
(16)
Now, let Eww, x) supp( ( (=)) denote the support of Ps wez, where Ps is shorthand for the distribution Ps Sw, == Then, with ((w.)) denoting the indicator function (w., 2).
X2 2
Eps, [((.))) exp(Agen, S,)) S exp
(17)
Through change of measure from Ps, to Ps, we Polyanskiy & Wu 2019, Prop. 17.1), we get (after reorganizing terms)
X² dPs, we
(ggen(w: (wc, S,S)
E P exp
log
1.
(18)
Ps:
We now have disintegrated, samplewise exponential incquality. Next, we use Jensen's 's inequality and then minimize over find that
X²
2
E
Ep lwa
log
dPss Ps.
dPs. (. w
E gen S.]] < min
2 2E Psslww sww
log
(19)
X>-0
Ps.
We now use that Ep m= to P wz to find that
log
dPss Ps.
D(Ps. P./s///i wi Ps.) and then take the expectation with respect
E
Epwas
gen, gen (W.
< EP Epwz 2D(Pss s. wz || [s.s:)
(20)
11

---

Under review as a conference paper at ICLR 2021
The desired bound then follows because
Ep (W) Lz(s) (W)]
Ep, w2s gen, Z. Sii
(21)
Ep wz VV 22D(Ps
s.[pss Ps.)
(22)
71
A.2 PROOF OF THEOREM I
The proof essentially mimics parts of the derivation of (Steinke & Zakynthinou 2020, Thm. 2.(3)).
For convenience, we begin by proving an exponential incquality for a binary random variable X satisfying P(X a) P(X b) 1/2 where a, b E [0, 1]. Also, let X if X and X
x = b. Finally, let X, y > and c = e² 1 X. Then,
E 2[cA(x->x))
E
7X) 1 + -X) c f
(23)
A(1 - 7)
(a + b) + c - 7b)² 20)² (b (b-
(24)
Here, the first inequality follows because eM < 1 + cz²² 1x2 for all y S x. Expanding the squares and removing negative terms, we find that
B [x-xx=8)]
S1+ X(1 71
(a + b) c(1 )²)
(a² b²)
(25)
1 A(1 - 7) + (e -1 - A) + 72)
(26)
In view of (T0), we are interested in values of À and y such that X(1-?)+ (1-
S so that the left-hand side of (26) is no larger than 1. Furthermore, it will turn out convenient to select pairs (A, 7) so that À is as large as possible and y is as small as possible. A possible choice Thus, conclude that
is A 1/3 and
E B[cH(x-28) 1.
(27)
X= l(w, (5.)) and X = l(w, 2,().) for fixed w and ž. Note that these random variables satisfy the required assumptions X and X, since the loss function is supported on [0, 1] and the random variables S, are Bernoulli distributed. Let Qwz = Qwzz Pz. then follows that
Next, we will apply (27 with X =
EQ Ps [ 21))s)
EQwz
II Eps,
e
< 1.
(28)
Now let E = suppp( wzz). Then,
EQ Ps Le e
$
(29)
The desired result follows after change of measure to P Pwzs PPolynnskiy & Wu 2019 Prop. 17.1).
A.3
PROOF OF COROLLARY 1
We begin by applying Jensen's inequality to 10 to move the expectation inside the exponential. We then obtain [1 by simply taking the logarithm of both sides and reorganizing terms.
To derive
12
we first apply Jensen's 's inequality in 10 this time only with respect only P to
get
2n T. (iz(s) - D(P w/zs Qw1
Ep
exp
Ep
wi
L Lz (W) 3
3
S 1.
(30)
'nnohher permissible choice is X = 1/2.98 and 1.795. It turns out that this choice leads to tighter bounds for the setup considered in Section 4 Hence, it will be used that section.
12

---

Under review as a conference paper at ICLR 2021
We Markov's inequality in the following form. Let U Py be nonnegative random variable satisfying E [U]] $ 1. Then,
PulU 1 2 1 1- E 6.
(31)
Applying
31 to 30
we find that, with probability at least 1 - under 2s.
exp Erw w 25
n I Z2s
2n
lz) (W) D(P w 11 11 S
(32)
3
3
Taking the logarithm and reorganizing terms, we obtain
Finally, to derive we apply 31
to
10 immediately to conclude that, with probability at
least 1 under wzs*
2n
dP w
1
exp
3 I (z)(s) (W)
2(S) (W)
log dQ, w 2s
(33)
3
8
The desired bound (3) follows after taking the logarithm and reorganizing terms.
A.4 PROOF OF COROLLARY
Consider fixed E and E g As shown in Appendix A.2
Epa; [ed (1) 2k( S 1.
(34)
Let supp(Ps:\wã), where PsilE short for sw Z=z- By changing measure we get
4 aPs;
Eps (1 EPs
-log
$ 1.
(35)
Moving the expectation inside the exponential through the use of Jensen's inequality and taking the logarithm, we get
d.s w
Ep Ep [(w,, Z(())) S Er,, [[(w, Z.S))) 3 B.,,,
log
(36)
d dPs.
= 2 E P3 iss [1( (.SS)) 3/ 2)
(37)
The desired result now follows by noting that
Ep wzs PL (W)]
Epwz
Ep Ss ias [l(w, ((.))
(38)
72
and applying 37 to each term in the sum in 38
B FAST-RATE BOUNDS FOR THE INTERPOLATING CASE
In this section, we discuss how tighten the bound in Corollary I Funder the additional assumption that the training loss Lz(s) (W) is O for all W ~ Pw]z(s) (interpolating assumption), and for the special case Qw1ž Pwiz.
We begin by proving the following exponential inequality, the derivation of which similar to part of the proof of the realizable fast-rate bound from (Steinke & Zakynthinou 2020).
Proposition 2. Consider the setting of Theorem 7 with the additional assumption that Lz(s) (W) = 0 for all W Pw]z(s) and that Qwlž = Pw z Then,
EP wzs
[exp(
exp n log 2 Lz(s) (W) - (W,,S\ 1
(39)
13

---

Under review as a conference paper at ICLR 2021
Proof.
Let X, >
O. Furthermore, let S' be independent of W, Z, and S, and distributed S.
Then.
EPw2s
II Li-1
ACC. + {,t.a./._.......................
(40)
= =Erwzs Se
Ex I's
(41)
Let supp P. wes). It now follows from
41 that
P2 Ps le ( Ep Wwz Ps
II F=1l
(42)
= = wwss II (S) -
(43)
We now change measure Pwzs
conclude that
Ep Epwis
(44)
< <Epwss
A(WW:Z
1 2(W.2(())))-22(2222)
We now use the interpolating assumption, set log 2, and y + oc. These steps, together with the assumption that É(W, (5,)) E [0, 1], imply that the right-hand side of (44) is no larger than 1. From this, the desired result follows.
Using Proposition 2 these bounds below without proof, since they can be established following steps similar to the ones used to prove Corollary
can derive bounds that are analogous those of Corollary I
We present
Corollary 3. Consider the setting of Proposition 2
Then, the average population loss is bounded by
I(W;S
Er was Lrz (W) &
(45)
n nlog? 2
Furthermore, with probability at least 1 - over Pzzs the PAC-Bayesian population loss is bounded by
D(Pwis w žs
|I (Iww2) log
Ww [Lz(s) (W)] <
(46)
log
Finally, with probability least over Pwzs. the single-draw population loss is bounded by
(W) <W, S Z) + log
(47)
log 2
Finally, we present a samplewise bound that tightens Corollary 2 Junder the interpolating assumption.
Its derivation is inspired by the techniques used establish Proposition and Proposition g Corollary 4. Consider the setting of Proposition
Then, the average population loss is bounded by
T(W; S.
Ep E2w2 [L,, (W)
(48)
log 2
Proof. Let \, 7 > and let Sy be independent of W. Z, and S, and distributed as S,. Then, for all i,
E P22s (
1 MIW.2(()))
(49)
2
=Ep EEwws, Pst
Ep Po.
(50)
14

---

Under review as a conference paper at ICLR 2021
We now let & supp P.. wžs follows from
49
50 that
1e (0-
Bp BPwzPa Ps,
(
- ]
(51)
< <BP w2a
2
By performing a change of measure from P P2 Ps to P w2s. we conclude that
BPwzs,
(
-((0022255)))))002222 )
(52)
< 1p w2s
dfwzs, Here, =(W, log TP Ps,
We now the interpolating assumption, set À log 2, and let + oc. These steps, together with the assumption that ((:,)) E [0, 1]. imply that the right-hand side of (22 is larger than 1. Thus,
Ep way, ( 1
(53)
Next, we use Jensen's inequality move the expectation in inside the exponential. Taking the logarithm and reorganizing terms, we get
(W, St [ log 2
I(W; S log 2
Ep Pwzs ((W, < B2ws.
(54)
The result now follows because
1
I(W: S
E Pwwzy [12 (W)) = PR
E(W. (s
(55)
n log 2
1=1
1=1
C EXPERIMENT DETAILS
Here, provide a detailed description of the network architectures and training procedures con- sidered in this paper. We also note that, when evaluating the fast-rate bounds (12) and (33), we use the constants 1.975 and 2.98 in place of and 3, respectively. This choice leads to valid bounds, as pointed out in Appendix A.2
C.I NETWORK ARCHITECTURES
The LeNet-5 architecture used in the numerical results described in Table This different from most standard implementations of LeNet-5, but coincides with the architecture used by /hou et al. (2019) and Dziugaite et al. (2020). has 431 080 parameters. The fully connected neural network denoted by 600 consists of an input layer with 784 units, 2 fully connected layers with 600 units and ReLU activations, followed by an output layer with units and softmax activations, has 837 610 parameters.
C.2 TRAINING PROCEDURES
We now provide additional details on the training procedures described in Section The initial weights all the networks used for each instance of ((S) were set to the same randomly selected values drawn from zero-mean normal distribution with standard deviation 0.01. All networks were trained using the cross-entres cross-entropy loss, optimized using either SGD with momentum and fixed learning rate SGD without momentum and a decaying learning rate. First, describe the details of SGD with momentum. For MNIST, we used a learning rate 0.001, and for Mushion-MNISTY we used 0.003. In all experiments, the momentum parameter is 0.9. We used batch size of 512.
15

---

Under review as a conference paper at ICLR 2021
Table 1: The LeNet-5 architecture used in Section
Convolutional layer, 20 units, 5 size, linear activation, 1 x stride, valid padding
Max pooling layer, 2 x 2 size, 2 x 2 stride
Convolutional layer, 50 units, 5 x size, linear activation, 1 stride, valid padding
Max pooling layer, 2 x 2 size, 2 x 2 stride
Flattening layer
Fully connected layer. 500 units, ReLU activation
Fully connected layer, 10 units, softmax activation
For SGD without momentum, we used a decaying learning rate schedule, where the learning rate for a given epoch E is given by
a6
a EE)
(56)
1 + T LE/EEl
Here, on is the initial learning rate, y is the decay rate, and Eg is the number of epochs between each decay. In all experiments, we used ag 0.01, 7 = 2, and Eg 20. Again, we used batch size of 512.
To choose o, we pick the largest value with one significant digit (i.e., of the form a 10-b with [1 9] and b E Z) such that the absolute value of the difference between the training loss on Z (S)) of the deterministic network with weights μn and empirical average of the training loss of NNs with weights drawn independently from N(W 14, of was no larger than some specified threshold.
When producing the results reported in Figure for MNIST, while for Fashion-MNIST" we used threshold of 0.10. In Appendix D we perform additional experiments with other thresholds. Specifically, for Figure Te we use threshold of 0.05, For the randomized label experiment in Table 2 we
2 and Figures Ma-d, we used a threshold of 0.05
while we use a threshold of 0.15 for Figure If use a threshold of 0.10.
To find d2, we use as starting point the same procedure as for determining σı, but with μ2 in place of μ4l and the training loss evaluated all of Z. Let call the value found by this procedure o a' 10- Then, among the values of the form a 10-b with a E [1 9] and E 1, D' + 1}. we choose d2 to be the one that minimizes the bound on the test loss. In all our experiments, this procedure resulted in d2 01. To guarantee that the final bound holds with a given confidence level, all 27 bounds resulting from all possible choices of a and b need to hold with the same confidence level. Since we consider both slow-rate and fast-rate bounds, a total of 54 bounds need to hold simultaneously. We ensure that this is the case via the union bound. Thus, if each individual bound holds with probability at least 8, the optimized bounds hold with probability at least 1 546, We compute the bounds with 0.05/54, so the optimized bounds hold with 95% confidence.
8'
D ADDITIONAL EXPERIMENTS
D.1 DEPENDENCE ON THE SIZE OF THE TRAINING SET
In this section, we study the dependence of the bounds on the size n of the training set. We perform experiments for different values of by restricting Z be a 2n-dimensional randomly chosen subset of the set of 6 10 training samples available in MNIST and Pashion-MNISS The training set Z ( then formed by selecting of these samples at random. We then train network, either L or the 6002 FCNN, on this restricted training set, until the training error is lower than some target error. For MNIST, we use a target training error of 0.05, while we use 0.15 for MNSSS.. The results are shown in Figure 2
As seen in Figure 2 the bounds on the test loss for large values of n are fairly accurate for both of these architectures, especially so for MNIST. However, they are loose for smaller values of n. As previously discussed, the relative ordering of the slow-rate bounds and the fast-rate bounds from a quantitative standpoint depends on the details of the learning setup. In particular, higher values for the training loss and information measures tend to make the slow-rate bounds tighter due to their smaller constant factors.
16

---

Under review as a conference paper at ICLR 2021
Slow-rate bound
0.8
Fast-rute bound
0.8
Test loss
Classification error
0.6
Training
0.6
Clussification
0.4
0.4
0.2
0.2
0.5
1.5
2.5
0.5
1.5
2.5
Training size
-10
Training
-10*
(a) LeNet-5, MNIST
(b) 600 FCNN, MNIST
Classiication errur
Classifiation
0.6
0.6
0.4
0.1
0.2
0.2
0.5
0.5
1.5
Training set size
-104
Training set size n
-10
(c) LeNet-5, Fashion-MNIST
(d) 600 FCNN, Fashion-MNIST
Figure 2: The estimated training losses and test losses as well as the slow-rate ( and fast-rate PAC-Bayesian bounds on the test loss for two NNs trained on MNIST or slow-rate and fast-rate PAC- Bay-BBaesi bounds essentially coincide with the the single-draw bounds and respectively. The shaded regions correspond to two standard deviations.
12
These
Table 2: The estimated training errors, test errors, and the corresponding slow-rate 8 and fast- rate (2) PAC-Bayesian generalization bounds for LeNet-5 trained on binarized MNIST with partially corrupted labels.
Randomized labels
25%
50%
75%
100%
Training error
0.106
0.088
0.090
0.081
Test егтог
0.216
0.364
0.461
0.494
Slow-rate bound
5.561
9.811
10.45
11.67
Fast-rate bound
44.52
141.0
160.1
200.4
D.2 RANDOMIZED LABELS
In order to examine the behavior of our bounds an overfitting scenario, we consider data sets with partially randomized labels. Specifically, we set the labels of fixed proportion of both the training and test sets of MNIST uniformly at random, and then perform training using SGD with momentum as described in Appendix C In order to simplify training with randomized labels, we consider binarized version MNIST where the digits O,..., 4 are merged into one class and 5.... into another. The results shown in Table 2 The slow-rate bound is computed using (8). while the fast-rate bound is based on 12. As usual, the quantitative difference between these bounds and the corresponding single-draw bounds in and (13) is negligible.
17

---

Under review as a conference paper at ICLR 2021
As shown in Table 2 our bounds become vacuous when randomized labels are used. The fast-rate bound significantly worse than its slow-rate counterpart, which is to be expected: when the prior and posterior selected using randomized labels, larger discrepancy between them arises. This increases the value of the KI. divergence the fast-rate bound more. We note, though, that the qualitative hehavior of the bounds is in agreement with the empirically evaluated test errоr: an increased proportion of randomized labels, and thus an increased test error, is accompanied by an increase the values of our bounds. Furthermore, the slow-rate bound consistently overestimates the test error by factor of approximately 25.
(8) and (T2), which, as previously discussed, penalizes
To the best of our knowledge, all bounds available the literature for overfitting situations such as the one considered in this section are vacuous. The best result can be found in (Dziugaite & Roy 2017 Tab. 1), where an FCNN with one hidden layer trained on binarized version of MNIST with fully randomized labels. Despite directly optimizing the evaluated PAC- ACy-ayyi bound as part of the training procedure, the obtained test error bound of 1.365 vacuous.
18


Reviews:
[{"review_id": "qENzDY2y7Qa", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper tackles an important concern when it comes to PAC-Bayes bounds, i.e., the fact that such bounds apply to the risk of a stochastic predictor rather than a deterministic one. The authors propose bounds on a \"single draw\" of a predictor according to the PAC-Bayesian predictor. \n\nHowever, I would like the author to discuss to which extent the derivation of this \"single draw'' bound differs from the result of Hellstrõm & Durisi (2020) they refer to. Indeed, the latter is a \"slow rate\" $O(1/\\sqrt{n)}$ bound, while the proposed result is a \"fast rate\" $O(1/n)$ one. However, such bounds for randomized predictors already exist in the PAC-Bayes literature for randomized predictors. As a matter of fact, the PAC-Bayes theorem of Seeger (2002), involving the KL divergence between two Bernoulli distributions, is tighter than both the slow rate result of Eq. (1) and the fast rate result of Eq. (2); the Seeger's bound achieving fast rate when the empirical loss is zero (see Letarte et al., 2019 (Thm 3), for an explicit connection between Eq (2) and Seeger's bound). \n\nIn other words, I wonder if the proposed \"fast rate\" bound is a particular case of a general analysis obtainable from a slight generalization of Hellstrõm & Durisi (2020).\n\nThe experiments show promising results but would benefit by being extended. Figure 1 shows the bound values according to the training epoch up to 30 epochs. The training and test loss are still decreasing at this point. In order to have the complete picture, it would be important to compare the results for fully trained models. Moreover, I would like to see the bounds values in the overfitting regime, when the training error is close to zero, as the experiments are performed in Dziugate & Roy (2017). Note that the proposed fast rate bounds only converge in this setting.\n\nFinally, a nice addition would be to comment on the possibly to learn a predictor by directly minimizing a single draw bound, as it is frequently done in the PAC-Bayes works (e.g., Dziugate & Roy (2017). \n\n### Minor comments:\n- I do not understand the subscript $i + S_i n$ of $\\tilde Z$ (middle of page 3)\n- It is strange that the authors cite an unpublished paper (Guedj and Pujol 2019) for the canonical PAC-Bayes bound stated in the early PAC-Bayes works of McAllester.\n\n### References:\nLetarte et al., Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks. NeurIPS 2019\nSeeger, PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification. JMLR 2002\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "YKC1RlVNqb", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper extends results of prior work by Steinke and Zakynthinou, by providing generalization bounds in the PAC-Bayesian and single-draw settings that depend on the conditional mutual information. The emphasis in this work is on obtaining fast rates ($1/n$ vs. $1/\\sqrt{n}$). The authors also conduct empirical experiments showing how the fast rate bounds they propose can be useful for obtaining non-vacuous generalization bounds in the context of over-parameterized neural networks.\n\nI think Theorem 1 and its corollaries are a nice contribution. The paper is very well written and clear. The authors do an excellent job in explaining the relevant related work, and how their results expand upon the results of earlier work. \n\nIt might be useful if the authors could indicate or explain whether their bounds suggest or motivate improved learning algorithms. For example, how should one choose a prior distribution Q over the hypothesis based on knowledge of the full training examples?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "8f32MMQq8-c", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper derives bounds on the test loss under the random-subset setting, which are expressed with conditional information measures, and have fast rates with respect to the sample size n. The derived bounds are compared with the practical performance of deep neural networks (DNNs) trained on the MNIST and Fashion-MNIST data sets.\n\nAlthough the derived bounds can be somewhat loose practically as it can be larger than those of slow-rates, the paper provides a steady theoretical progress on the evaluation of loss bounds using conditional information measures.\n\nAlthough the experiments with NNs and practical data sets are interesting, they are a little unsatisfactory for demonstrating the significance of the derived fast-rate bounds.\n\np.5, main theorem: It would be nicer to explain what novel important proof techniques are required, if any, to derive the fast-rate bounds in Section 3.\n\np.6, computation of \\mu_2: Since NNs have hierarchical structures, computing the average of their weights does not seem so good. I wonder if computed \\mu_2 are close to zero and if there is any other possible ways to compute \\mu_2.\n\np.7, experiments on MNISTs: Although the experiments demonstrate that the fast-rate bound can in fact be tighter than the slow-rate bound in practical cases, I wonder if some experiments should be designed with changing the sample size n in order to compare fast and slow rate bounds. \nAs the training and test errors reported in Fig. 1 are close to each other, isn’t it better to produce any overfitting situation, even for synthetic data?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper extends results from the recent work of Steinke and Zakynthinou (SZ) for the test loss of randomized learning algorithms. They provide bounds in the single draw as well as PAC-Bayes setting. The main result is about fast rates the proof of which follows with minor modifications from the corresponding result in SZ. It is unclear to me the contribution over existing work is sufficient to merit acceptance.
Decision: Reject