PAC-Bayesian Neural Network Bounds
Authors: Yossi Adi
Alex Schwing
Tamir Hazan
Venue:  (2020)
Keywords: PAC-Bayesian bounds
PAC-Bayes
Generalization bounds
Bayesian inference

Abstract: Bayesian neural networks, which both use the negative log-likelihood loss function and average their predictions using a learned posterior over the parameters, have been used successfully across many scientific fields, partly due to their ability to `effortlessly' extract desired representations from many large-scale datasets. However, generalization bounds for this setting is still missing.
In this paper, we present a new PAC-Bayesian generalization bound for the negative log-likelihood loss which utilizes the \emph{Herbst Argument} for the log-Sobolev inequality to bound the moment generating function of the learners risk.

Under review as conference paper at ICLR 2020
NEURAL NETWORK BOUNDS
Anonymous authors Paper under double-blind review
ABSTRACT
Bayesian neural networks, which both use the negative log-likelihood loss func- tion and average their predictions using learned posterior over the parameters, have been used successfully across many scientific fields, partly due to their abil- ity to "effortlessly' extract desired representations from many large-scale datasets. However, generalization bounds for this setting is still missing. this paper, we present new PAC-Bayesian generalization bound for the negative log-likelihood loss which utilizes the Herbst Argument for the log-Sobolev inequality to bound the moment generating function of the learners risk. We explore the generalization and calibration properties the learned posterior on several image classification benchmarks, showing that the proposed approach provides better generalization and uncertainty estimates.
INTRODUCTION
Deep neural networks are ubiquitous across disciplines and often achieve state of the art results (e.g., Krizhevsky al. (2012); Simonyan & Zisserman (2014); He et al. (2016)). Albeit neural networks are able to encode highly complex onput- relations, in practice, they do not tend to overfit (Zhang et al., 2016). This tendency to not overfit has been investigated in numerous works on generalization bounds (Langford & Shawe-Taylor 2002; Langford & Caruana, 2002; Bartlett al., 2017a; 2019; McAllester, 2003; Germain et al., 2016; Dziugaite & Roy, 2017). Indeed, many generalization bounds apply to neural networks. However, most of these bounds assume that the loss function is bounded (Bartlett et al., 2017a; Neyshabur et al., 2017: Dziugaite & Roy, 2017). Unfortunately, this assumption excludes the popular negative log- log-likelihood (NLL) loss, which is instrumental to Bayesian neural networks that have been used extensively to calibrate model performance and provide uncertainty measures to the model prediction.
In this work we introduce a new PAC-Bayesian generalization bound for NLL loss of deep neural networks. Our work utilizes the Herbst argument for the logarithmic-Sobolev inequality (Ledoux, 1999) in order to bound the moment-genen geneentnggn function of the model risk. Broadly, our PAC- Bayesian bound is comprised of two terms: The first term is dominated by the norm of the gradients with respect to the input and it describes the expressivity of the model over the prior distribution. The second term is the KL-divergence between the learned posterior and the prior, and it measures the complexity of the learning process. In contrast, bounds for linear models or bounded loss func- tions lack the term that corresponds to the expressivity of the model over the prior distribution and therefore are the same when applied to shallow and deep models.
We empirically show that our PAC-Bayesian bound is tightest when we learn the mean and variance of each parameter separately, suggested by Blundell et al. (2015) in the context of Bayesian neural networks (BNNs). We also show that the proposed bound holds different insights regarding model architecture, optimization and prior distribution selection. We demonstrate that such optimization minimizes the gap between risk and the empirical risk compared to the standard Bermoulli dropout and other Bayesian inference approximation while being consistent with the theoretical findings. Additionally, we explore in-distribution and distt--dittiiuttion examples to show that such opti- mization produces better uncertainty estimates than the baseline.

---

Under review as conference paper at ICLR 2020
RELATED WORK
Generalization bounds for neural networks were explored in various settings. VC-theory provides both upper bounds and lower bounds to the network VC-dimension, which are linear in the number of network parameters (Bartlett et al., 2017b; 2019). While VC-theory asserts that such a model should overfit as it can learn any random labeling (e.g., Zhang et al. (2016)), surprisingly, neu- ral networks generally do not overfit. Rademacher complexity allows to apply data dependent bounds to neural networks (Bartlett & Mendelson, 2002). However, they rely on bounds of the loss function (Wan et al., 2013; Gao & Zhou, 2016). Rademacher complexity bounds may also take into account the Lipschitz constant of the network. While this presents an improvement when its gradient-norn are bounded, these results also require the loss to be bounded. Stability bounds may be applied to unbounded loss functions and in particular to the negative log-likelihood (NLL) loss (Bousquet & Elisseeff, 2002; Rakhlin et al., 2005; Shalev-Shwartz et al., 2009; Hardt et al., 2015; Zhang et al., 2016). However, stability bounds for convex loss functions, e.g., for logistic re- gression, do not apply to neural networks since they require the NLL loss to be a convex function of the parameters. Alternatively, Hardt et al. (2015) estimate the stability of stochastic gradient descent dynamics, which strongly relies on early stopping. This approach results in weaker bounds for the non-convex setting.
PAC-Bayesian bounds were recently applied neural networks (Langford & Caruana, 2002; McAllester, 2013; Dziugaite & Roy, 2017; Neyshabur et al., 2017). In contrast to our work, those related works all consider bounded loss functions. PAC-Bayesian bounds for the NLL loss in the online setting were put forward by Banerjee (2006). The online setting does not to consider the whole sample space and therefore is simpler to analyze in the Bayesian setting. An excellent survey on PAC-Bayesiag bounds was provided by Germain et al. (2016). Alquier et al. (2016) introduced PAC-Bayesian bounds for linear classifiers with the hinge-loss. Germain et al. (2016) is closer to our setting and considers PAC-Bayesian bounds for the quadratic loss function, while proving that the quadratic loss function has exponential decay (sub-gamma) when the data is sampled from a Gaussian distribution. This result is PAC-Bayesian generalization bound for the NLL loss of regressor which assumes Gaussian model over a continuous label space y. Our work differs from this work in two important aspects: (1) our work does not consider linear classifiers and apply to any deep neural networks; (2) our bound considers the NLL loss for classification tasks, for which the label space y is discrete.
PAC-Bayesian bounds for the NLL loss function are intimately related to learning Bayesian infer- ence (Germain et al., 2016). Recently many works applied various posteriors in Bayesian neural networks. Gal & Ghahramani (2015); Gal (2016) introduce a Bayesian inference approximation us- ing Monte Carlo (MC) dropout, which approximates a Gaussian posterior using Bernoulli dropout. Srivastava et al. (2014) introduced Gaussian dropout which effectively creates a Gaussian posterior that couples between the mean and the variance of the learned parameters. Kingma et al. (2015) explored the relation of this posterior to log-uniform priors, while Blundell et al. (2015) suggests to take full Bayesian perspective and learn separately the mean and the variance of each parameter. Our work uses the bridge between PAC-Bayesian bounds and Bayesian inference, described by Germain et al. (2016), to find the optimal prior parameters in Bay-Bayesian setting and apply it in the Bayesian setting.
Most of the literature regarding Bayesian modeling involves around a two-step formalism (Bernardo & Smith, 2009): (1) prior is specified for the parameters of the deep net; (2) given the train- ing data, the posterior distribution over the parameters is computed and used to quantify predictive uncertainty. Since exact Bayesian inference is computationally intractable for neural networks, ap- proximations are used, including MacKay (1992); Hernández-Looaar & Adams (2015); Hasenclever al. (2017); Balan et al. (2015); Springenberg et al. (2016). In this study we follow this two-step formalism, particularly we follow a similar approach to Blundell et al. (2015) in which we learn the mean and standard deviation for each parameter of the model using variational Bayesian practice. Our experimental validation emphasizes the importance of learning both the mean and the variance.
3 BACKGROUND
Generalization bounds provide statistical guarantees on learning algorithms. They measure how the learned parameters perform on test data given their performance on the training data S =

---

Under review as conference paper at ICLR 2020
((x1,31), y1)...., (Im, (m)), where 2; is the data instance and y; is its corresponding label. The per- formance of the learning algorithm is measured by a loss function 8(w, x, v). The risk of a learner its average loss, when the data instance and its label are sampled from their true but unknown dis- tribution D. We denote the risk by LD
((z.)))n((u 2, y). The empirical risk is the average E -i=1 E(w, Fz. Ms).
training set loss Ls(w)= i
PAC-Bayesian theory bounds the risk of learner (wwgL when the parameters are averaged over the learned posterior distribution q. The parameters of the posterior distribution are learned from the training data S. In our work we focus on the following PAC-Bayesian bound:
Theorem (Alquier et al. (2016)). Let KL(gle) = I ((w)) log(g(w) p (dw be the KL- divergence between two probability density functions p, For any X and for any ò E (0. 1] and
for any prior distribution p. with probability at least 1 - 8 over the draw of the training set S, the following holds simultaneously for any posterior distribution q:
log Eu (aannmm(e@en (II.p(l) h=(())] + KL(gglp) + log(1/0)
Euwy (w & EwwglLs(w)) +
PAC-Bayesian theory is intimately connected to Bayesian inference when considering the negative log-likelihood loss function ((w, 2) = log plyla, w) and À = m. Germain et al. (2016) proved that the optimal posterior in this setting is q( (w) = p(w]S). Bayesian inference considers the poste- rior p(y|2, S) p(w) ())(yyl w)dw, at test time for data instance x, which corresponds to the risk of the optimal posterior. Unfortunately, the optimal posterior is rarely available, and PAC- AAC-Bayes relies on the approximated posterior q-
Coincidently, the approximated posterior and its KL-diiergence from the prior distribution are in- strumental to the evidence lower bound (ELBO), which is extensively used in Bayesian neural net- works (BNNs) to bound the log-likelihood >x
i-1 log (o)
m
171
log p(u(lx)))
< Ewnn logplu, w) + (L(g)pp)
(2)
While the right hand side of PAC-Bayesian bound, with the negative log- ligeliiklihood loss and X m, is identical to the right hand side of the ELBO bound in term of learning, they serve different purposes. One is used for bounding the risk while the other is used for bounding the marginal log- likelihood. Nevertheless, the same algorithms can be used to optimize BNNs and PAC-Bayesian intuitions and components can influence the practice of Bayesian neural networks.
4 PAC-BAYESIAN BOUNDS FOR THE NEGATIVE LOG-LIKELIHOOD LOSS
It is challenging to derive a PAC-Bayesian bound for the negative likeliooddoood (NLL) loss as it requires bound on the log-partition function log Ew the loss function is uniformly bounded by a constant, e.g., the zero-one loss, the log-partition func- tion is bounded as well. Unfortunately, the NLL loss is unbounded, even when is discrete. For instance, consider fully connected case, where the input vector of the (k)--h layer a function of the parameters of all previous layers, i.e., IIA (W.............................. W&1)). The entries of r& are computed from the response of its preceding layer, i.e., W T4, followed by a transfer function (-), i.e., T+++1 = a (kk) Then, since the NLL. is define as - log(p(y)a 22, w)) = - (WLark) ) + log Eg ((Wer))) ), the rows in We consist of the vector rrı then the NLL loss increases with r, and is unbounded when r + oc.
(w) In cases where
Our main theorem shows that for smooth loss functions, the pog-patitionn function is bounded by the expansion of the loss function, i.e., the norm of its gradient with respect to the data æ. This property appealing since these gradients often decay rapidly for deep neural networks, as we demonstrate in experimental evaluation. Consequently deep networks enjoy tighter generalization bounds than shallow networks. Our proof technique follows the Herbst Argument for bounding the log- bog-paritionn function using the Log- Soboley inequality for Gaussian distributions (Ledoux, 2001).
Theorem 2. Assume (x., y) ~ D and given y follows the Gaussian distribution. Let l(w, v) be a smooth loss function (e.g., the negative likeliood loss). For any 8 E (0, 1] and for any real
number X > O, with probability at least 1 - ô over the draw of the training set S the following holds
3

---

Under review as conference paper at ICLR 2020
simultaneously for any posterior probability function: EwwgLLD(w>] 2
2A E(o.v> [ (V,.(022..))11 Jo
dal + KL[gllp) + log(1/5)
[ww) log Branpe
(3)
The Gaussian assumption for the data generating distribution D can be relaxed to any log-concave distribution, using Gentil (2005), Corollary 2.5. We use the Gaussian assumption to avoid notational overhead.
Broadly, the proposed bound is comprised of two terms: The first term is the log-partition function which is dominated by the norm of the gradients with respect to the input, namely e=of(w,x.0)) da]. and it describes the expressivity of the 22 ( [[V æ, x),)) fo E(x.)>- Rett)---etttttaa.ydd
model over the prior distribution. The second term is the KL-divergence between the learned poste- rior and the prior, and it measures the complexity of the learning process.
The proof starts with Eq. (1) and uses the Herbst Argument and the Log-Sobolev inequality to bound the moment-generating function Rg (eALL (w) Specifically, the proof consists of three steps. First we use the statistical independence of the training samples to decompose the moment generating function
ES ( AB ((u (E(z.))=D(et) (-
(4)
Then we use the Herbst argument to bound the function M 2 E(E (-11,, (- obtain the following bound:
and
log (())+ Jo (ar Mial ((())
M
a2a((o)
(5)
Finally we use the log- Sobolev inequality for Guassian distributions,
(M (a) log M(a S 2 E(z.g)=Dle-adee al(w,,.)) a2 x, .
(6)
The above theorem can be extended to settings for which x is sampled from any log-concave dis- tribution, e.g., the Laplace distribution. The log-concave setting modifies the gradient norm and the log-Sobolev constant in Eq. (6) that corresponds to Gaussian distributions, cf. Gentil (2005). We avoid this generalization to simplify our mathematical derivations.
A detailed description of the proof can be found on Section 8.1 in the Appendix.
APPLICATION TO LOGISTIC REGRESSION
The bound in Theorem is favorable when applied to deep networks since their gradients w.r.t. data often decay rapidly. Nevertheless we can also apply our technique to shallow nets trained with NLL loss. We obtain PAC-Bayesian bounds for multi-class logistic regression.
The NLL loss for multiclass logistic regression takes the form: - log p(u w) = ((wx), +
log( Eg (WW))s), where E Rd is the data instance, y (1...., k} are the possible labels, and We E R x is the matrix of parameters. The bound in Theorem takes the form:
I& given y follows the Gaussian distribution. Let log piy æ. w) be the negative log likeeeill loss k-class logistic regression. For any 8 (0, 1], for any X >> and for any prior density function with variance of S m/16X2, with probability at least å over the draw of the training set S the following holds simultaneously for any posterior probability density function:
Corollary 1. Assume (x, v) D and
f(w, x, y)
kd log(2) KL(gllp) + log(1/8)
Bugnng [TD S Benngg (L.((W) +
Full proof can be found on Section 8.2 in the Appendix, while we sketch the main steps of the proof below. The above corollary shows that PAC-Bayesian bound for classification using the NLL loss

---

Under review as conference paper at ICLR 2020
Table 1: Different op values experiments. All models composed of five fully connected layers with
ReLU activation functions.
Model
Train loss
Test loss
Train acc.
Test acc.
Gen. loss
Bound
0.05
0.07
0.08
98.48
97.73
0.02
0.2
MNIST
Op 0.1
0.02
0.06
99.53
98.27
0.03
0.08
Op 0.2
0.03
0,08
99.24
97.9
0.05
0.08
OP 0.3
0.09
0.11
97.2
96.66
0.02
0.67
Op 0.05
0.24
0.32
92.03
88.55
0.09
0.2
Fashion
Op
0.11
0.25
93.28
89.50
0.1
0.13
P 0.2
0.26
0.33
90.12
87.87
0.07
0.86
= 0.3
0.37
0.42
86.36
84.26
0.05
21.73
can achieve rate of X This result augments the PAC- PAC-Bayesian for regression using the NLL loss for regression, i.e. the square loss, of Germain al. (2016).
The PAC-Bayesian bound for logistic regression is derived by applying Theorem 2. We begin by realizing the gradient of log plyp( w: with respect to x. We denote by wy the y-th row of parameter matrix W. Thus V, log p(ylw,, Eg (2, w) Wig). and the gradient norm is
upper bounded as follows: || vr log x)11 = Eg wgy? Plugging this result into Eq. (18)
we obtain the following bound:
22a Eg 1
Bww S-
E Ewppe
(8)
Finally, whenever Aap v mm/8 88/8wa/ derive the bound
222 Eg wall I m
m
kd
E Ex
(9)
SX203
detailed description of the proof can found on Section 8.2 the Appendix.
EXPERIMENTS
In this section we study the derived bound empirically, We start with an ablation study of the proposed bound using classification and regression models. Next, present our results for multi- class classification tasks using different datasets and different architectures. We conclude the section, with an analysis of the models' uncertainty estimates using for in-distribution examples and out- of-distribution examples. All suggested models follows the a Bayesian Neural Networks (BNN) perspective, in which we learn the mean and standard deviation for each learnable parameter network where define N N(0, I) to be the prior over weights.
6.1 ABLATION
Effeet of op- We start by exploring the effect of o, the models' performance and the proposed generalization bound. For that, we trained several models using σp E (0.05, 0.2, 0.3) using the MNIST (LeCun & Cortes, 2010) and Fashioin-MNIST Xiao al. (2017) datasets. All results were obtained using fully connected layers with ReLU as non-linear activation function. We optimized the NLL loss function using Stochastic Gradient Descent (SGD) for 50 epochs with learning rate of 0.01 and momentum of 0.9. For each model we compute the average train and test loss and accuracy together with the absolute difference between the training loss and the test loss, denoted as Generalization Loss. Moreover, we compute the generalization bound as stated in Eq. (18) for all settings. Results are summarized in Table 1.
Although dp = 0.2 reaches slightly better generalization bound on MNIST dataset, dp = 0.1 performs better over all calculated metrics, i.c., average loss and accuracy, both on MNIST and -NISTT Notice, for Bushion-MNIST we observed slightly better generalization gap while using ap = 0.05, however, its loss and accuracy are worse comparing to 0.1.
Effect of A. Recall, we bound the moment generating function using the norm of the functions' gradient with respect the data (Eq. (18)). To construct tighter generalization bounds, we would like to set X + m. However, in Eq. (18) À appears in both numerator and denominator. It is

---

Under review as conference paper at ICLR 2020
Table 2: Different depth level experiments. For fair comparison all models have roughly the same number of parameters (~80K for MNIST, ~800K for Fashion-MNIST, ~ 15000 for regression). All models composed of fully connected layers with ReLU activation function.
Model
Train loss
Test loss
Train acc.
Test acc.
Gen. loss
Bound
One layer
0.253
0.267
92.89
92.49
0.015
3.69
MNIST
Two layers
0,045
0.073
98.89
97.82
0.028
2.28
Three layers
0.029
0.063
99.41
98.15
0.033
0.82
Four layers
0.024
0.065
99.49
98.14
0.041
0.13
Five layers
0.023
0.058
99.52
98.27
0.035
0.08
One layer
0.38
0,46
86.86
84.2
0.07
5.68
Fashion
Two layers
0.21
0.31
92.52
88.9
0.1
4.9
Three layers
0.21
0.31
92.34
88.7
0.1
1.08
Four layers
0.21
0.30
92,49
88.8
0.09
0.22
Five layers
0.19
0.29
93.3
89.6
0.1
0.13
One layer
45.7
106.5
60.8
378.7
Boston
Two layer
8.6
15.7
7.1
286.3
Three layers
8.2
12.9
4.7
105.3
Four layers
10.4
14.1
3.7
45.9
Five layers
12.0
12.1
0.1
31.9
hence not clear whether the bound will converge, which depends on the model architecture, which represented by the norm its gradient. other words, models with lower gradient norm could benefit from larger values of X, hence tighter generalization bounds.
To further explore this property we trained five different models with different number of layers (1- 5). We look into both classification models while optimizing the NLL loss function, and regression tasks while optimizing the Mean Squared Error (MSE) loss function. For classification we used MNIST and Mashion-MNIST datasets, while for regression the regression models, results were obtained using 5-fold cross validation). Except for the linear models, foree all models have roughly the same numbers of parameters (~800 for MNIST, ~800K for Fashion-MNIST, 15500 for regression) For all models we set ReLU as non-linear activation functions. We optimize all models for 50 epochs using SGD with learning of 0.01 and momentum of 0.9. Based on results of the prior paragraph, in all reported settings we set oo- 0.1.
use the Boston Housing dataset (for
Results are reported in Table 2. It can be seen that deeper models produce tighter generalization bounds three datasets. When considering model performance on down-stream classification task we notice that in general. models with better generalization bounds perform slightly better in terms of loss and accuracy. One possible explanation that deeper models have smaller gradients w.r.t. the input. To validate that we further computed the average squared gradient norm w.r.t. the input as a function of the model depth, for both MNIST and FaSHIO datasets. It can seen from Figure la that indeed the gradients decay rapidly we add more layers to the network.
Next, we present Figure 1b the generalization bound function of for MNIST models. We explored À E [ym, m] and stopped the plot once the bound no longer be computed. Experiments using Fashion-MNIS: produce similar plot and can be found on Section 8.7 the Appendix.
Weights visualization. Since we consider Bayesian Neural Networks (BNNs) and optimize the KL- divergence between the prior and the posterior over the weights, we can visualize the average mean and standard deviation (STD) of the posterior this for MNIST and Dishion-MNIS" models using four and five depth levels. As expected, we can that the average mean over the weights is zero for all layers while weights STD approaches 0.1. For the MNIST models (Figure 2a top row), we observed the standard deviation are ~00.7 and not 0.1. We suspect this behaviour is due fast optimization, hence the models do have much signal to push the model towards the prior distribution. Notice, in all settings the average STD of the model weights decreases on the last layer. We observed similar behavior also for the other models.
function of the model depth. Figure 2a presents
6.2 CLASSIFICATION
Next, we compare BNN models against two commonly used baselines. The first baseline is a soft- max model using the same architecture as the BNN while adding dropout layers. The second base-

---

Under review as conference paper at ICLR 2020
10
MNIST
one byer
Fashion MNIST
two kyyer
three byyers
199E X, k/l/
10
four ltyers.
kiyers
Bound
5
10
2
3
4
500
1000
20000 40000
60000
Layers
À
(b)
Figure 1: Analysis of the proposed bound function network depth. In (a) we show the squared gradient norm as function of the layers of the model. In (b) we report the the generalization bound function of À for different deep net depth levels using the MNIST dataset.
Mean Params
0.02
MC.D
0.01
-..0
MNIST
Dashion-MNIST
CIFAR10
Mean Params
0.50
0.50
MC-3mpoud
BNN
1005
0.25
Layers
Layers
0.00
MNIST
Fashion-MNiST
CIFAR10
(b)
Figure 2: In (a): average mean and STD of model weights function of depth level. Top row is for MNIST, bottom row is for Fashion-MNISTT. In (b): ECE and MCE metrics for Softmax, MC- Dropout and BNN models using MNIST, Fashion-MNISS and CIFAR10 (lower is better).
line is a Bayesian approximation using Monte Carlo Dropout (Gal & Ghahramani, 2015), denoted as MC-Dropout, using different dropout rates and weight decay value of le-5.
To evaluate these approaches we conducted multi-class classification experiments using three clas- sification benchmarks: MNIST, Fashion-MNIST. and CIFAR- (Krizhevsky & Hinton, 2009). We report train set and set loss and accuracy, together with their generalization gaps (e.g., the dif- ference between the test and training loss and accuracy). Notice, oppose to Dziugaite & Roy (2017) our results are reported for multi-class classification and not for binary classification. For completeness, report binary classification results on Section 8.4 in the Appendix. The premise beyond these type of experiments is to preset the benefit of learning the mean and STD separately for each of the models' parameters.
Results are reported Table For BNN and MC-Dropout models, we sample 20 times from the posterior distribution and average their outputs produce the model output. We also sampled more times, however, we did not see any significant differences. We observe that BNN models achieve comparable results both baselines but with lower loss and accuracy generalization gaps. Throughout the experiments we use dropout value of 0.3 for Softmax and MC-Dropout models and different dropout values
Gp 0.1 for BNN models. We chose these values after grid search for all bascline models. A detailed description of all implementation details together with results for more dropout rates can be found on Sections 8.4, 8.5, and 8.3 the Appendix.
6.3 UNCERTAINTY ESTIMATES
Lastly, we evaluated the uncertainty estimates of BNN models against sofumax models and MC- Dropout models. We experimented with both in-distribution and auttof-distriuution examples. The purpose of the following experiments is to demonstrate that following the Bayesian approach gether with the carefully picked prior can lead to better uncertainty estimates.

---

Under review as conference paper at ICLR 2020
Table 3: Results for multi-clas, image classification benchmarks. We report both loss and accuracy metrics for the training set and test set, together with the generalization loss and accuracy.
Model
Train loss
Train acc.
Test loss
Test acc.
Gen. loss
Gen. acc.
MNIST
Softmax
0.003
1.0
0.066
0,983
0.06
0,016
MC-Dropout
0.003
1.0
0.066
0.983
0.06
0.016
BNN
0.034
0.995
0.064
0.982
0.03
0.012
Fashion
Softmax
0.143
0.947
0.288
0,906
0.14
0.041
MC-Dropout
0.145
0,946
0.288
0.905
0.14
0.041
BNN
0.251
0.905
0,321
0.881
0.07
0.024
CIFAR-16
Softmax
0.492
0.831
0.541
0.817
0.05
0.013
MC-Dropout
0.493
0.829
0.544
0.818
0.011
BNN
0.453
0.844
0.479
0.836
0.02
0.007
Table Results for the oustt--distribution experiments. We report both loss and accuracy measures for the training set and test set, together with entropy values. We explore training on MNIST (MN), Fashion-MNiST (FMN), and CIFAR-10. Testing was done on MNIST (MN), Fashion-MNISTT (FMN), NotMNIST, and SVHN. Reported losses and accuracies are computed using the out-of- distribution dataset.
Model
In-dis.
Out-dis.
Train loss
Train acc.
Test loss
Test acc.
Train ent.
Test ent.
Softmax
FMN
MN
8.33
0.113
8.21
0.114
0.42
0.41
MC-Dropout
FMN
MN
7.84
0.112
7.74
0.112
0.45
0.45
BNN
FMN
MN
4.64
0.105
4.57
0.108
0.78
0.74
Sottmax
FMN
NoIMNIST
8.64
0.155
7.78
0.152
0.43
0.41
MC-Dropout
FMN
NoIMNIST
8.39
0.123
7.82
0.087
0.54
0.55
BNN
FMN
NoMMNIST
4.70
0.085
4.59
0.1
0.89
0.92
Softmax
CIFAR-IO
SVHN
3.55
0.112
3.60
0.106
1.51
1.52
MC-Dropoul
CIFAR-10
SVHN
3,55
0.112
3.60
0.105
1.51
1.52
BNN
CIFAR-10
SVHN
2.47
0.112
2.49
0.099
2.15
In-Distribution Examples. In the context of in-distribution examples we follow the suggestion of Guo et al. (2017) and calculate the Expected Calibration Error (ECE) and Maximum Calibration Error (MCE) for all three models. Figure 2b provides visual representation of the results. Results suggest that BNNs produce better calibrated outputs for all settings, with two exception of ECE for MNIST and MCE for CIFAR10.
Out-of-Distrinn Distriibitiinin Examples. Next, we evaluated the uncertainty estimates using OOD examples. We apply a model trained using dataset OOD examples from dataset B. We trained models on MNIST, Fashion-MNIST and CIFAR-10 10 and assess prediction confidence using OOD examples from MNIST, Fashion-MNIST, NotMNIST (Cohen et al., 2017), and SVHN (Netzer et al., 201 I). Results summarized in Table 8. More OOD experiments using different dropout and prior rates can be found on Sections 8.3, 8.6 in the Appendix.
All models performed at the chance level (~ 10% for 10 classes) for both OOD train and test sets. When considering the loss, we observe significantly higher values for the softmax and MC-Dropout models. These two findings imply that the softmax and MC-Dropout models overly confident and tend to output high probability for the max label. Hence, we measure the average entropy for all models. We expect BNNs have higher entropy, due the fact that it produces better uncertainty estimates, i.c., its' predictions for OOD samples are closer to uniform distribution. Indeed, results reported in Table confirm this intuition.
7 DISCUSSION AND FUTURE WORK
In the following study we present a new PAC-Bayesian generalization bound for learning deep net using the NLL loss function. The proof relies on bounding the log-partition function using the squared norm of the gradients with respect to the input. Experimental validation shows that the resulting bound provides insight for better model optimization and prior distribution search. We demonstrate that learning the mean and STD for all parameters together with optimize prior over the parameters leads to better uncertainty estimates over the baselines and makes it harder to overfit.

---

Under review as conference paper at ICLR 2020
REFERENCES
Pierre Alquier, James Ridgway, and Nicolas Chopin. On the propertics of variational approximations of gibbs posteriors. Journal of Machine Learning Research, 17(239): 1-41, 2016.
Anoop Korattikara Balan, Vivek Rathod, Kevin P Murphy, and Max Welling. Bayesian dark knowl- edge. In Advances in Neural Information Processing Systems, pp. 3438-3446, 2015.
Arindam Banerjee. On bayesian bounds. In Proceedings of the 23rd international conference on Machine learning, pp. 81-88. ACM, 2006.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexitie: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482 2002. 2002.
Peter L Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally- margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6241-62550 2017a.
Peter I. Bartlett, Nick Harvey, Chris Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. arXiv preprint 1703::::703029330 2017b.
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Rexearch, 20(63):1-17, 2019. URL http:htt/ttt/ttt //mrr org/ wwwpg//pppss//////1
612 html..
José M Bernardo and Adrian FM Smith. Bayesian theory, volume 405. John Wiley & Sons, 2009.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks. arXiv preprint arXiv::505.0544: 2015.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-526, 2002.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. Emnist: an extension of mnist handwritten letters. arXiv preprint 102.03170..03333 2017.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008 2017.
Yarin Gal. Uncertainty in deep learning. PhD thesis, PhD thesis, University of Cambridge, 2016.
Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model 042,, 2, 2015.
uncertainty in deep learning. arXiv preprint
Wei Gao and Zhi-Hus Zhou. Dropout rademacher complexity of deep neural networks. Science
China Information Sciences, 59(7):072104, 2016.
Ivan Gentil, Logarithmic sobolev inequality for log-coneave measure from prekopa-leindles inequal-
ity. arXiv preprint math/0503446, 2005.
Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien. Pac-bayesian theory meets bayesian inference. In Advances in Neural Information Processing Systems, pp. 1884- 1892, 2016.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 315-323, 2011.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1321-1330. JMLR. org, 2017.

---

Under review as conference paper at ICLR 2020
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of 2015.
stochastic gradient descent. arXiv preprint
Leonard Hasenclever, Stefan Webb, Thibaut Lienart, Sebastian Vollmer, Balaji Lakshminarayanan, Charles Blundell, and Yee Whye Teh. Distributed bayesian learning with stochastic natural gradi- ent expectation propagation and the posterior server. The Journal of Machine Learning Research, 18(1):3744-3788 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proceedings of the IEEE conference on computer vision and patter recognition, pp- 770-778, 2016.
José Miguel Hernández-Lobato and Ryan Adams. Probabilistic backpropagation for scalable learn- ing of bayesian neural networks. International Conference on Machine Learning, pp. 1861- 1869, 2015.
Durk P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparameteri- zation trick. In Advances in Neural Information Processing Systems, pp-
2015.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In NIPS, pp. 1097-1105, 2012.
John Langford and Rich Caruana. (not) bounding the true error. In Advances in Neural Information Processing Systems, pp. 809-816, 2002.
John Langford and John Thylor Pac-bayes & margins. Advances in neural information processing systems, 15:423-430. 2002.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL htthtt///yyan lecun. com/ exdb/mnist/.
Michel Ledoux.
Concentration of measure and logarithmic sobolev inequalities. In Seminaire de probabilites XXXIII, pp. 120-216. Springer, 1999.
Michel Ledoux. Logarithmic sobolev inequalities for unbounded spin systems revisited. In
Séminaire de Probabilités XXXV, pp. 167-194. Springer, 2001.
David JC MacKay. Bayesian methods for adaptive models. PhD thesis, California Institute of Technology, 1992.
D. McAllester. Simplified pac-bayesian margin bounds. Learning Theory and Kernel Machines, pp. 203-215, 2003.
David McAllester. A pac-bayesian tutorial with dropout bound. arXiv preprint 1rXiv:1307.2118. 2013.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits natural images with unsupervised feature learning. 2011.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. A pac- bayesian approach to spectrall--oormalzeed margin bounds for neural networks. arXiv preprint arXiv:1707.0956. 2017.
Alexander Rakhlin, Sayan Mukherjee, and Tomaso Poggio. Stability results in learning theory. Analysis and Applications, 3(04):397-417, 2005.
Shai Shalev-Shwarzz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex opti- mization. In COLT, 2009.
10

---

Under review as conference paper at ICLR 2020
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprini arXiv: 1:XXv::449.11500 2014.
Jost Tobias Springenberg, Aaron Klein, Stefan Falkner, and Frank Hutter. Bayesian optimization with robust bayesian neural networks. In Advances in Neural Information Processing Systems, pp. 4142- 2016.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way prevent neural networks from overfitting The Journal of Machine Learning Research, 1929-1988, 2014.
Li Wan, Matthew Zeiler, Sixin Zhang, Yann L Cun, and Rob Fergus. Regularization of neural networks using dropconnect. In Proceedings of the 30th International Conference Machine Learning (ICML-13), pp. 1058-1066, 2013.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Rashion-mnise a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiy: /6/ 1.03330, 2016.

---

Under review as conference paper at ICLR 2020
APPENDIX
8.1 PAC-BAYESIAN BOUNDS FOR THE NEGATIVE LOG-LIKELIHOOD LOSS PROOF
Proof. We begin by using the statistical independence of the training samples to decompose the following function:
DS-D" (edomm(ednoll)-ssste (Lmlt ESw [e 2 -- (-
(10)
B (a.. B ( e>LD(w)
(11)
(xp(())
E (E(aa))D(e (em ( m
(12)
Next we represent the moment generating function M(A) A B(z (- us-
ing ((a) & 1 log M(). The fundamental theorem of calculus asserts ((²) K(0)
p// (a)dda A/m So ('(a)da, where the last equality follows from change of integra- tion variable and the integral limits. ('(a) refers to the derivative at a. We then compute ('(a) and K (0):
K'(a) = ao)( - M(a) log M(a)
(13)
(a)
log (a) l'Hopital M (0 MM(0) - LD(w).
((0) =
lim a
(14)
a
Concluding the Herbst argument we obtain the following equality:
M A K()) (()) (')ddo ( gar((a) Mral (15)
MM
Combining Eq. (12) with Eq. (15) we derive:
Es (()L
ADD(ww)) (e (1) (ad' Mial log Min) da
m
(16)
2 m St (s) Milus log Mi(r)) a3
(17)
Finally we apply the log-Sobolev inequality for Gaussian distributions (cf. Ledoux (2001), Chapter 2), as described in Eq. (6). To complete the proof we combine Eq. (6) with Eq. (17) to obtain:
D [ ((b((w)- [s(w)))
< e f(e.))=be
2x
-at(w...)) 2 (V
de
(18)
222
ue(w...))) do]
M(m)
(19)
8.2 APPLICATION TO LOGISTIC REGRESSION PROOF
Proof. To apply Theorem 2 we start by realizing the gradient of plyl,, w) with respect to F. We denote by wy the y-th row of the parameter matrix W. Thus Va log p(ypp)ll p(y|w, w, x:)
Σyp(0 P(ū)e, ww,,, wg). Using the convexity of the norm function we upper bound the gradient norm:
IV, log p )² < Erlule w)ll wyll s ||wyl1 +
11 S || 12
Σ
(20)
Next use the fact that the gradient norm upper bound is independent of to simplify the moment generating function bound in Theorem 2. Since f(w, x, y) log.(pp) (0 w). we use the bound in Eq. (20):
L.'
Stt.))>Dett-Maaaae da} 2 2 1wg 112 S/'
E(ay)DDe -a((.,
(( [|] [/ H
2)1 2))1
B( neal (-0 da
(21)
12

---

Under review as conference paper at ICLR 2020
Thus we are able to simplify Theorem 2 as follows
Evrig [nnn Eepin [ss log Eewwpe 42 Eg moll + (Lg))))) + log(1/0)
(22)
Finally, we recall that p is the prior density function N(0, oz). Since the parameters are statistically independent, this expectation decomposes to its kd parameters:
k d
2 Eg ||w Eepope
422 S
Ru,
(23)
i=
222
And the result follows from the fact E. (0,,00
m
8A
2x2 2² dc = -oo VTT0p
112
100
20
du
20
(24)
v 2TT
Op
V 22p
for 0²
om m m- m
Whenever Ao v /m/8 then
1/2 and the result follows.
m B
8.3 ARCHITECTURES
The architechtures described this sub-section are used for the multi-class, binary, and uncertainty estimates experiments. We use multilayer perceptrons for the MNIST dataset, while we use convo- lutional neural networks (CNNs) for both Aeshion-MNIST and CIFAR-10. A detailed description of the architectures is available in Table 5. We optimize the NLL loss function using SGD with learning rate of 0.01 and a momentum value of 0.9 in all settings. We use mini- bani-bacches size 128 and did not use any learning rate scheduling. For the MC-Dropout models experienced with dif- ferent weight decay values, however found that le-5 provides the best validation loss, hence choose this value.
Table 5: Model architectures. A description of the model architectures for MNIST, Fashion-MNIST and CIFAR-10. The numbers inside the parenthesis indicate the layer output dimension. For all models we use a ReLU activation function after each layer containing trainable weights.
Dataset MNIST
No. of layers
Architecture
2
FC(300) FC(10)
Conv 10) + MaxPool(2) - Conv(20) +
Fashion-MNIST
5
MaxPool - FC(120) - FC(82) FC(10)
Conv(64) + Conv (64) MaxPool(2) (64)
10
6
MaxPool(2) + Conv(64) + MaxPool + FC(128) + FC(10)
8.4 BINARY CLASSIFICATION
Experiments in this sub-section were conducted to show consistency with Dziugaite & Roy (2017). We follow the same setting in which we use the MNIST dataset, where we group digits [0, 1, 2, 3, 4] into label zero, and labels [5, 6, 7, 8, 9] into label one. All experiments in this subsection were conducted using multilayer perceptrons with one hidden layer consisting of 300 hidden neurons. We use the Rectified Linear Unit (ReLU) as our activation function (Glorot al., 2011). We optimize the negative log-likelibann likelihood loss function using stochastic gradient descent (SGD) with a learning rate of 0.1 and a momentum value of 0.9. We did not use any learning rate scheduling. SGD is run in mini-batches batches of size 128. Each model was trained for 20 epochs.
We compared BNN to softmax models with dropout (Srivastava et al., 2014) rates chosen from the set (0.0, 0.3, 0.5). Hereby, dropout with a rate of 0.0 means no dropout at all. In addition to the training set and test set loss and accuracy, we measure the generalization loss, while setting (n(w) to be the average test set loss. In the same manner, we measure the generalization accuracy, while using the zero-one loss instead of the negative log-likelihood loss. Table summarizes the results. All models achieve comparable accuracy levels, however the softmax models suffer from larger generalization errors both in terms of loss and accuracy. Notice, as expected, using higher Bernoulli-dropout rates mitigates the generalization gap.
13

---

Under review as conference paper at ICLR 2020
Table 6: Results for experiments on a binary classification variant of MNIST. We report both loss and accuracy metrics for the training set and test set, together with the generalization loss and accuracy. Additionally, we report the -l-ddivegeence value for the BNN models. We compare BNN to softmax models trained with Bernoulli dropout. Dropout rates and op values are in parenthesis next to model name, e.g., 'softmax (0.3)' refers to softmax model with Bernoulli dropout of rate 0.3.
Model
Train loss
Train acc.
Test loss
Test ace.
Gen. loss
Gen, acc.
Softmax (0.0)
0,001
1.0
0.076
0.983
0,0746
0,017
Softmax (0.3)
0.011
1.0
0.055
0.983
0.0439
0.013
Softmax (0.5)
0.021
0.993
0.059
0.982
0.0379
0.010
BNN (0.1)
0.046
0.984
0.064
0.979
4950
0.0187
0.005
BNN (0.3)
0.047
0.983
0.081
0.975
4196
0,0331
0,008
8.5 MULTI-CLASS CLASSIHICATION
Here we report results for multi-class classification for BNN and the baselines. Table summarizes the results. The main purpose of these additional experiments is explore more dropout and op values for different models.
Table Results for multi-class image classification benchmarks. We report both loss and accuracy metrics for the training set and test set, together with the generalization loss and accuracy. Addition- ally, we report the KL-divergence for the BNN models. We compare BNN to softmax models and MC-Dropout models, trained with Bernoulli dropout. Dropout rates and op values are in parenthesis next to the model name, e.g., 'softmax (0.5)' refers to a softmax model with Bernoulli dropout of rate 0.5.
Model
Train
Train acc.
Test loss MNIST
Test acc.
KL
Gen.
Gen. acc.
Softmax (0.0)
0.0003
1.0
0.0699
0.983
0.070
0.02
Softmax (0.1)
0.0008
1.0
0.0651
0.984
0.064
0.016
Softmax (0.5)
0.0103
1.0
0.0682
0.983
0.058
Softmax(0.7)
0,012
1.0
0.0658
0.983
0.054
0.013
Softmax(0.9)
0.1026
0.97
0.1385
0.962
0.036
0.008
MC- IC-Dropout (0.1)
0.0009
1.0
0.0651
0.984
0.064
0.016
MC- MC-Dropout (0.5)
0.0111
1.0
0.0678
0.982
0.057
0.015
MC Dropout(O.7)
0.0178
0.99
0.0781
0,979
0.0603
0.016
MC Dropout(O.9)
0.1373
0.96
0.1771
0.953
0.0398
0.007
BNN (0.3)
0.0448
0.986
0.0647
0.98
4251
0.02
0.006
Fashion-MNNIST
Softmax (0.0)
0.0159
0.995
0.6415
0.896
0.62
0.098
Softmax (0.1)
0.0899
0.966
0.3644
0.902
0.27
0.064
Softmax (0.5)
0.1941
0.927
0.3106
0.895
0.12
0.032
(0.7
0.2361
0.915
0.333
0.892
0.097
0.023
Softmax(0.9)
0.8366
0.643
0,866
0.639
0.03
0.004
MC- MC-Dropout (0.1)
0,0913
0.965
0,3587
0.901
0.27
0.064
MC-Dropout (0.5)
0.1973
0.926
0.3097
0.897
0.11
0.029
MC Dropout(0.7)
0.2535
0.913
0.3387
0.887
0.0852
0.026
MC Dropout(O.9)
0.908
0.608
0.9318
0.602
0.0238
0.006
BNN (0.3)
0.1841
0.932
0.2640
0.904
4869
0.08
0.028
CIFAR-10
Softmax (0.0)
0.3361
0.881
0.4974
0.841
0.16
0.039
Softmax (0.1)
0.4170
0.858
0,5064
0.828
0.09
0.351
Softmax (0.5)
0.5299
0.821
0,5712
0.804
0.04
0.017
Softmax(0.7)
0,4366
0.852
0.5494
0.815
0.113
0.037
(oft
1.2778
0.495
1.3491
0.499
0.071
-0.004
MC- MC-Dropout (0.1)
0.4189
0.856
0,5071
0.09
MC-Dropout (0.5)
0.5293
0.821
0,5711
0.807
0.04
0.014
MC Dropout(O.7)
0.4595
0.843
0.5878
0.811
0.128
0.033
MC Dropout(O.99
1.3045
0.483
1.3935
0.482
0.089
0.001
BNN (0.3)
0.5643
0.807
0.5699
0.806
18237
0.005
0.001
14

---

Under review as conference paper at ICLR 2020
8.6 UNCERTAINTY ESTIMATES
Additional experimental results for out-of-distribution examples can be found in Table 8.
Table 8: Results for the out-of-distribution experiments. We report both loss and accuracy measures for the training set and test set, together with entropy values. We explore training on MNIST (MN), Fashion-MNIST (FMN), and CIFAR-10. Testing was done on MNIST (MN), Fashion-MNIST (FMN), NotMNIST, and SVHN. Reported losses and accuracies are computed using the out-of- distribution dataset.
Model
In-dis.
Out-dis.
Train loss
Train acc.
Test loss
Test acc.
Train ent.
Test ent.
Sottmax (0.0)
FMI
10.32
0.136
10.04
0.146
0,34
Softmax (0.1)
FMN
MN
9.41
0.114
9.28
0.116
0.42
0.41
Softmax (0.5)
FMN
MN
8.16
0.114
7.97
0.114
0.42
0.41
MC-Dropout (0.1)
FMN
9.12
0.113
8.99
0.113
MC-Dropout (0.5)
FMN
MN
7.68
0.113
7.50
0.113
0.46
0.45
(0.3)
FMN
5.31
5.22
0.098
Sofmmax (0.0)
MN
FMN
14.94
0.109
15.03
0,104
0.28
0.29
Softmax (0.1)
MN
FMN
16.27
0.098
16.33
0.092
0.29
0.29
Softmax (0.3)
MN
18.07
18.15
0.089
Sollmax (0.5)
MN
FMN
18.78
0.077
18.89
0.075
0,38
0.38
MC (0.1)
MC (0.3)
MN
FMN
18.09
0.093
18.16
0.090
0.31
0.31
MC (0.5)
MN
FMN
18.83
0.076
18.93
0.076
0.37
BNN (0.1)
MN
FMN
6.69
0.102
6.70
0.099
0.73
BNN (0.3)
MN
FMN
8.67
0.069
8.71
0.069
0.55
0.57
(0.0)
Softmax (0.1)
MN
NoMMNIST
15.45
0.061
16.03
0.065
0.23
0.24
Softmax (0.3)
MN
NoIMNIST
19.38
0.071
19.25
0.085
Sollmaxx (0.5)
MN
NOIMNIST
21.61
0,063
21.89
0.048
0.18
0.18
MC (0.1)
MN
NorMNIST
15.46
0.061
16.05
0.065
0.23
MC
NoIMNIST
19.44
19.23
MC (0.5)
MN
NoIMNIST
21.73
0.062
21.92
0.053
0.19
0.19
(0.1)
5.52
BNN (0.3)
MN
NoMMNIST
7.71
0.060
7.99
0.070
0.57
0.57
Sofmmax (0.0)
FMN
NOMMNIST
12.46
0.152
11.92
0.13
0.29
0.27
Softmax (0.1)
FMN
NotMNIST
9.71
0.080
9.71
0.074
Softmax (0.5)
FMN
NoIMNIST
8.79
0.122
8.22
0.087
0.5.
0.52
MC-Drupout (0.1)
MC-Dropout (0.5)
FMN
NoIMNIST
8.23
0.156
7.47
0.157
0.46
0.44
BNN (0.3)
FMN
NoIMNIST
4.74
0.123
4.72
0.11
0.79
Sottmax (0.0)
CIFAR-IO
SVHN
4.3
5.13
Soltmax (0.1)
CIFAR-10
SVHN
3.78
0.123
3.86
0.115
1.51
1.54
Softmax (0.5)
CIFAR-10
MC-Dropout (0.1)
CIFAR-10
SVHN
3.79
0.123
3.87
0.115
1,50
1.53
MC-Dropout (0.5)
CIFAR-10
SVHN
3.10
0.122
3.17
0.132
BNN (0.3)
CIFAR-10
SVHN
3.45
0.091
3.54
0.094
1.71
1.75
8.7 FIGURES
Additional figures for various experiments.

---

Under review as conference paper at ICLR 2020
30
one layer
two layers
25
three layers
four layers
20
five layers
Bound
15
10
5
0
500
1000
20000 40000
60000
A
Figure 3: Analysis of the proposed bound as function network depth. We report the the gen- eralization bound function of for different deep net depth levels using the Fashion-MNIST dataset.
16


Reviews:
[{"review_id": "rkgITCHrqS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Summary:\nThis paper proposes a PAC-Bayesian generalization bound for Bayesian neural networks. The author discuss that earlier generalization bounds hold for bounded loss function, whereas the proposed generalization bound considers negative log likelihood loss which can be unbounded. Therefore, earlier results do not hold here. \n\nThe technical approach used is along lines of PAC Bayes framework and specifically for this loss function which requires bounding the log-partition function, the authors follow the Herbst Argument for bounding the log-partition function. \n\nContribution: \nThe paper uses straight forward PAC Bayes approach and the only bottleneck is bounding the log-partition function for which the authors use an earlier result (Herbst Argument for bounding the log-partition function. )\n\nSignificance: \nMy biggest concern with this work is its significance. As we know classification loss is bounded and for regression loss, as long as we have bounded input and a Lipschitz function corresponding to the NN, the output is bounded. Also as authors mention, there have been two earlier results covering other unbounded loss functions. Therefore, I do not feel that extending those results to NLL is a good enough contribution. Especially since the extension uses a known approach  (Herbst Argument for bounding the log-partition function. )\n\nExperiments: \n* From the explanations, it seems each architecture is trained once, which is not acceptable. How can one refute the effect of a specific initial value? A good scientific practice entails having mean and variance bar for different values or at least repeating the experiment multiple times and reporting the avg. \n* According to the paper, the architectures in table 2, fig 1 are made by keeping the number of parameters roughly the same. Then the authors increase the depth. Note that to keep the # of parameters the same, they have to decrease the width as they increase the depth. Therefore, this cannot be a correct analysis of effect of the depth. As depth is not the only parameter that is changed between the architectures.\n\n\nWriting: \nThe writing is overall ok which some vague places such as \n*first page, last paragraph, line 1: \".. our PAC Bayesian bound is tightest when we learn...\" the authors do not discuss what is the space of options for the bound and only mention the case when it is tightest. Therefore the claim is confusing\n*first page, last paragraph, last line: \"..better uncertainty than the baseline\". The authors do not specify the baseline which makes this whole claim vague.\n\nTitle: \nThis is a minor issue but worth mentioning. The title is vague and confusing. In the first read one might think this paper provides PAC-Bayesian bounds for usual NNs (which has been considered and written about many times in the literature). The authors should mention that the considered networks are Bayesian NNs.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Skxxg4nDqH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 suggests a PAC-Bayesian bound for negative log-likelihood loss function. Many PAC-Bayesian bounds are provided for bounded loss functions but as authors point out, Alquier et al. (2016) and Germain et al. (2016) extend them to  unbounded loss functions. I have two major concerns regarding this paper:\n\n1- Technical contribution: Since Alquier et al. (2016) has already introduced PAC-Bayesian bounds for the hinge-loss, I think the technical contributions of this paper is not significant enough for the publication. Moreover, the particular format of the bound in Theorem 2 is problematic since the right hand side depends on the data-distribution. When presenting the generalization bound, we really want the right hand side to be independent of the distribution (given the training set) and that is the whole point of calculating the generalization bounds. In particular, I don't see why inequality (1) is any better than inequality (2).\n\n2- Experiments: The main issue with the correlation analysis done in Section 6 is that authors only change depth of the networks and then check the correlation of the generalization bound to the test error. The problem is that in all those networks deeper ones generalize better so it is not clear that the correlation is due to a direct relationship to generalization or a direct relationship to depth. For example, if we take 1/depth as a measure, it would correlate very well with generalization in all these experiments but 1/depth is definitely not the right complexity measure or generalization bound. To improve the evaluation, I suggest varying more hyperparameters to avoid the above issue.\n\n\n***************************\n\nAfter rebuttals:\n\nUnfortunately, my concerns are not addressed adequately by authors. Therefore, my evaluation remains the same.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bye8oCvAKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 offers PAC-generalization bounds for Bayesian Neural Networks based on a previous result by Alquier et al. (Theorem 1) which connects the generalization gap to the log partition function of the same gap for the prior distribution on the learned parameters (which is identical to the ELBO bound used in Bayesian neural networks for NLL loss). Due to the fact that the optimal bound occurs for the true posterior, the PAC-bayesian bounds offer a novel interpretation as an objective for BNNs.\n\nThe authors note that the log partition function can in general be easily unbounded for loss functions based on NLL (as in the BNN case); their result shows that if the norm of the gradient is bounded, that is enough to bound the overall generalization gap. \n\nWhile this appears to be a technically impressive feat, the the assumptions involved in Theorem 2 seem significant (probably unavoidable for a theoretically tractable statement). Primarily, the conditional of x given y is Gaussian/log-concave (or at least unimodal, more generally ) but the motivation is based on deep neural networks (for why the gradient is bounded).  \n\nThe authors also specialize their bound to the case of logistic regression. Interestingly, the gap in this case has an additive term proportional to the product of the label cardinality and the input dimension (I'm not sure whether how significant this is in terms of tightness).\n\n In experiments, the authors explore and analyze the tightness of the proposed bounds for various hyperparameters like the variance of the weights prior.\n\nThey also perform an exhaustive comparison of the BNN models against non-bayesian alternatives, but it is not clear how the new contributions from the generalization bounds are relevant to the results in, say Section 6.2", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes PAC_Bayesian bounds for negative log-likelihood loss function. A few reviewers raised concerns around 1) distinguish their contributions better from prior work (eg Alquier). 2) confounders in their experiments. Both reviewers agreed that the paper, as it is written, does not provide sufficient evidence of significance. In addition, experiments shown in the paper varies two things - # parameters (therefore expressiveness and potential generalizability) and depth at each setting. As pointed out, this isn’t right - in order to capture the effect, one has to control for all confounders carefully. Another concerned raised were around Theorem 2 - that it contains data-distribution on the right hand side, which isn’t all that useful to calculate generalization bounds (we don’t have access to the distribution). We highly encourage authors to take another cycle of edits to better distinguish their work from others before future submissions. 

Decision: Reject