On PAC-Bayes Bounds for Deep Neural Networks using the Loss Curvature
Authors: Konstantinos Pitas
Venue:  (2020)
Keywords: PAC-Bayes
Hessian
curvature
lower bound
Variational Inference

Abstract: We investigate whether it's possible to tighten PAC-Bayes bounds for deep neural networks by utilizing the Hessian of the training loss at the minimum. For the case of Gaussian priors and posteriors we introduce a Hessian-based method to obtain tighter PAC-Bayes bounds that relies on closed form solutions of layerwise subproblems. We thus avoid commonly used variational inference techniques which can be difficult to implement and time consuming for modern deep architectures. We conduct a theoretical analysis that links the random initialization, minimum, and curvature at the minimum of a deep neural network to limits on what is provable about generalization through PAC-Bayes. Through careful experiments we validate our theoretical predictions and analyze the influence of the prior mean, prior covariance, posterior mean and posterior covariance on obtaining tighter bounds. 

Under review as a conference paper at ICLR 2020
ON PAC-BAYES BOUNDS FOR DEEP NEURAL NETWORKS USING THE Loss CURVATURE
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate PAC-Bayes bounds for deep neural networks through the closely related IB-Lagrangian objective. We first propose to approximate the IB- Lagrangian through second order Taylor expansion of the randomized loss around the minimum. For the case Gaussian priors and posteriors with fixed means and diagonal covariance, imation that corresponds to an "invalid" PAC-Bayes prior (a prior that is training set dependent). Our lower bound depends only the flatness of the minimum, and the distance between the prior and posterior means. Through a number of experiments our lower bound implies easy and and hard cases where one can cannot prove generalization even through "cheating". Motivated by this result, we see that for the easy cases, simple baseline closely matches our lower bound and is sufficient to achieve a non-vacuous PAC-Bayes bound. Crucially the baseline prior is centered on the random deep neural network initialization. This suggests that good prior mean choice is the main innovation in recent non-vacuous bounds with further optimization of the PAC-Bayes bound through SGD having com- plementary role.
able to derive lower bound to this approx-
INTRODUCTION
Recently two works Dziugaite & Roy (2017) Zhou et al. (2018) have made significant progress in proving generalization for deep neural networks. They manage prove non-vacuous generalization
1.0
0.5
140
0.5
/40
-10
-10
-20
-20
-00
1.5
-1.0
-1.5
0.0
-20
-15
-1.0
-1.5
0.0
(a)
(b)
Figure 1: The importance of retaining the original minimum: A number of works have shown the existence an empirical correlation between generalization error and flatness in the loss landscape around the deep neural network minimum A4g- Recently popular PAC-Bayes analyses can be seen as formal way quantifying this flatness. However, moving forward from simple empirical cor- relations, existing optimization based non-vacuous bounds compute implicitly different minimum jo and then evaluate the flatness around that minimum. By contrast we aim to estimate the flatness and related optimal posterior distribution around the original minimum fa-

---

Under review as a conference paper at ICLR 2020
bounds for simplified Mnist dataset Dziugattt & Roy (2117) and the Imagenet dataset respectively works/Bartlett et al. (2017) Neyshabur et al. (201 7 Golowich et al. (2017) which yield bounds that are vacuous by several orders of magnitude and are usually motivated by simple empirical correlation with the generalization error.
Zhou et al. (2018). ) This stands in stark contrast with previous works Bartlett
Both works rely crucially on applying the PAC-Bayes framework McAllester (1999) which typi- cally addresses the generalization error of stochastic classifiers. Given the randomized empirical error E (0)), the randomized population error Ee- [[)] a prior weight distribution P, a posterior weight distribution Q and N training samples the PAC-Bayes bound gives a guarantee of the form
E [[(O)] Q~Q 0~Q
S E [[(0]] + AV (KL(QI))) B)/N,
with some probability 8 where A and B are constants related to the derivation. The PAC- Bayes bound models the complexity of a classifier as the KL-Divergence between a prior P and a posterior Q weight distribution. Apart from yielding state of the art bounds for SVMs, a further motivation for this framework, is it's Bayesian nature i.e. is the existance of the prior P. Complexity not measured with respect to an arbitrary reference point, but as in the luckiness framework Shawe- et al. (1998), with respect to a reference point that can potentially incorporate our prior knowlede ledge about good solutions to the classification problem, and can lead to possibly tighter bounds.
In Dziugaite & Roy (217)) the authors model the weights as originating from a Gaussian posterior distribution with diagonal covariance 0 = μe + & @ where ~ NN (0, /). Then they optimize directly the stochastic objective resulting from the AAC-Bayes bound, by approximating stochastic quantities with MC sampling. Similarly in Zhou et al. 2018 the authorts first compress DNN with an off the shelf compession algorithm, removing redundant parameters and applying the PAC-Baye approach to the remaining weights. This be seen explicitly minimizing the length of code describing the DNN. While compression in Zhou et al. (2018) is done explicitly, Dziugaite & Roy (2017) can also be seen under this light, the random variables form variational code whose length is explicitly minimized Blier & Ollivier (0018).
While these two works result in non-vacuous bounds they have a number of important limitations.
Importantly they provide generalization error guarantees for a different classifier than the original. Compressing the neural network or modelling it as originating from a Gaussian distribution whose mean is modified, results in finding a completely different point in the parameter space than the original. The function that the new weights describe might or might not be close to the original. This might seem like an academic problem. However we argue that analyzing networks that typically result from vanilla SGD is equally important potentially leading to better initialization and regularisation of SGD, as well as discovering inherent limitions of our generalization proof toolbox.
The bounds provided by Dziugaite & Roy Zhou et al. (0188) are non-vacuous but loose. What is the source of this looseness? Both methods rely in non-convex optimisation that might have simply not converged properly. This is particular problem in Dziugaite & Roy (017) where is well known that VI techniques require laborious hyperparameter tuning. something that has hindered significantly the wide applicability of Bayesian neural networks Wu et al. (2018). Even when care is taken the resuls are widely considered sub- optimal in terms of uncertainty estimation for prediction tasks and code length description of the DNN Wu et al. (2018) Blier & Ollivier (2018). As such we argue that one stands to benefit from circumventing these non-convex optimisation procedures when possible.
The PAC-Bayes bound can also be seen under the light of flat minima. Flat minima have been em- pirically shown to correlate with better generalization Neyshabur et al. (2017a Keskar et al. (0166) The PAC-Bayes bound can be interpreted as balancing two terms, the randommized empirical loss and the KL complexity term Neyshabur et al. (2017a). As the posterior can be arbitrarily chosen increasing the variance of the noise added to the parameters will typically decrease the KL term while increasing the empirical loss. If the neural network solution corresponds to flat minimum,
2

---

Under review as a conference paper at ICLR 2020
more noise can be added to the parameters without affecting the empirical performance Neyshabur et al. (2017a).
In this work we propose to tackle the above problems by using second order Taylor expansion of the loss around the minimum, in conjunction with the PAC-Bayes framework. The second order term parameterized by the Hessian matrix corresponds to the curvature of the loss around the minimum. In line with the works linking flat minima to better generalization Neyshabur et al. (2017 7a Keskar et al.] 2016), we are effectively estimating the flatness of the minimum along all parameter dierec- tions. Thus we are able to add more noise to the flat directions and less noise to the curved ones, something that will typically decrease significantly the KL term in the PAC-Bayes framework while ensuring that the loss of the stochastic classifier remains small, Crucially for the case of Gaussian posteriors the optimal posterior covariance can be found in closed form, allowing us to circumvent non-convex optimization procedure by incuring an approximation penalty due to using a second order approximation of the loss.
The resulting approximation is closely linked to the Laplace approximation in Bayesian statistics Bishop (2006). It and similar approximations to the posterior have a appeared a number of times in the literature of bayesian neural networks yielding good results in number of tasks Maddox et al. (209)): Khan et al. (2019); Ritter et al.] (2018); Zhang et al. (2017); Khan et al. (018)). Similarly second order approximations of the loss around a minimum have long history in the literature of
DNN compression Dong et al. (2017): Wang et al. (2019); Peng et al. ): LeCun et ( (199);; Hassibi & Stork 1993) often yielding state of the art results in parameter reduction.
Even though the resulting posterior is optimal with respect to our approximation, being able to chose data driven informative prior still leaves room for looseness. Importantly the prior in the PAC-Bayes framework can depend on the data generating distribution but not on the training set used train the evaluated classifier. Workarounds include choosing data driven priors by training a separate classifier on different training set, or using the same training set but enforcing that the training set not too informative about each individual training signal. The later can be formalized through the framework of differential privacy. Both of the above will usually involve some non- convex optimisation procedure leaving again doubt as to the optimality of the classifier complexity estimate. We show that for the case of Gaussian priors and posteriors with diagonal covariance we can derive the optimal invalid prior covariance in closed form.
The invalid prior cannot be used to prove generalization, however it can be used as sanity check to see whether proving generalization is possible in principle. The optimal solution with respect to both prior and posterior covariance results in a lower bound PAC-Bayes bound (but not exactly equal given that we make a number of approximations) Through experiments we find that, depending of feasible solutions implied from the lower bound and the set of non-vacuous PAC-Bayes bound solutions don't 't intersect. One is unable to prove generalization, even through choosing prior in an invalid manner.
function closely related to the
the hardness of the dataset, one can find cases where the set
A number of works Achille & Soatto 2018): Dziugaite & Roy (017 7); Germain et al. (2066) have noted the similarity between the stochastic PAC-Bayes objective and the objective
Cs(D:
E [1(0) + +
0-2
For 3 = this is known as the Evidence Lower Bound (ELBO) objective in Variational Inference (2006). In the Information Bottleneck framework Achille & Soatto| 2018 Tishby et al. (2000) it is know as the IB- IB-gangnnga... More recently the same objective has been interpreted as the "task complexity "ppciiitty""cclllee
literature Kingma al. (2015
al. (0019). Then 9 has the role of regulating the amount of information in the randomized neural network Achille & Soatto ( smaller values correspond to more information and potential to overfit. While the objectives aad not entirely equivalent due to square root term over the KL divergence in the PAC-Bayes case, we will be using the IB formulation as removing the square root will ease our derivations. We note that Dziugaite & Roy (2017) have used the two objectives intercheangably with no significant difference in results.
A number of preprints have appeared on Arxiv trying to link PAC-Bayes to flat minima Wang et al. (2018); Li et al. (2019): Tsuzuku et al. (2019; Yang et al. 2019). These typically involve heuristic choices for the optimal posterior, do not analyze the role of the prior, and focus on quantities that simply correlate with the generalization error. Motivating vacuous generalization bounds the
3

---

Under review as a conference paper at ICLR 2020
basis of empirical correlations with generalization error has been criticised in a number of recent works Kawaguchi et al. (2017); Nagarajan & Kolter (2019b): Pitas et al. (2019).
CONTRIBUTIONS
We propose to analyze a PAC-Bayer bound through second order Taylor expansion of the randomized empirical loss in the closely related IB-Lagrannian objective. We thus pay an error resulting from the second order approximation in order to circumvent non- convex optimisation procedures, which might require extensive hyperparameter tuning and not converge properly.
We are able to find a lower bound to this second order taylor expansion that corresponds to an invalid PAC-Bayes prior (the prior is training set dependent). Experimentally we find cases where the set of feasible solutions implied by the lower bound does not intersect with the set of non-vacuous MAC-Bayes decuracy-complextn pairs. This in turn implies easy and hard cases were one can and cannot prove generalization using Gaussian priors and posteriors with diagonal covariance.
While we rely on approximations, we see empirically that in easy cases one can find non- vacuous generalization bounds using very simple baseline where the prior is crucially centered at the random DNN initialization. This in turn highlights the insightful prior mean choice the main innovation in previous non- vacous bound works(Dziugatte & Roy (2017) with bound optimization through SGD having a complementary role.
We motivate layerwise method to optimise PAC-Bayes bounds with respect the poste- rior variance, reducing the required computations significantly.
PAC- BAYESAN FRAMEWORK
We consider the hypothesis class H. realized by the feedforward neural network architecture of depth L with coordinate-wise activation functions a defined as the set of functions fe X' - y (X' C RP, RP,Y R*) with fa ( (I....(('''" W W1) ...)..) W where
O₂ C Rd is a vectorization of the weights and θ = R x Rh x X x R& x Given the loss function
y) and given training set of N instances D {(0j, 1;)) the empirical loss (()) + Σm (ffo
((.-)) we can define the population loss: L(0) == E ((xy))p((ff((
The PAC-Bayesian framework McAllester (1999) provides generalization error guarantees for ran- domized classifiers drawn from posterior distribution Q. We will use the following form of the PAC-Bayes bound.
Theorem 3.1. (PAC-Bayesian theorem McAllester (1999)) For any data distribution over X x Y, we have that the following bound holds with probability at least 1 over random i.i.d. samples
D = {II U;)} of size N drawn form the data distribution:
KL(Q)IP) + In 2N-1)
E BLOO S E BiI00)
3
(3)
e~Q
2N
Here Q is an arbitrary "posterior" distribution over parameter vectors, which may depend on the sample D and on the prior P.
The framework models the complexity of the randomized classifier the KL-Divergence between the posterior Q and a prior P. The prior P must be valid in that it cannot depend in any way on the training data. On the contrary the posterior Q be chosen to be any arbitrary distribution. This flexibility allows one to model deterministic neural networks as the mean of an arbitrary posterior distribution, thus deriving results for a stochastic but closely related classifier.
The square root in 3 will make subsequent calculations cumbersome. We will therefore be analyzing the similar objective
Cs(D; -
( (KL(())))
which is known as the IB- IB-Lagrangian Achille & Soatto (018); Tishby et al. (2000). While the two
objectives are not exactly equivalent, we argue through ex experiments that the differences are minimal and our results translate to the original PAC-Bayes bound
4

---

Under review as a conference paper at ICLR 2020
4 QUADRATIC APPROXIMATION AND LOWER BOUND
The stochastic and non-convex objective 4 is difficult to analyze theoretically. As such we first propose to expand the randomized loss using Taylor expansion which will make the subsequent analysis tractable. We get
(s(D), = E [[() (KL(Q 8-Q
(ai(0)
E
00
n
2"
" + (([lml))) (KL(
(5)
E n~
2""
Hn) (KL(
where Q' is centered version of Q. We've made a number of assumptions. In the second line we assumed that the loss f.(0) at the minimum is O. In line 3 we assumed that the gradient ai.(0) (0()))a /a the minimum also 0, the term (( is negligible and that the loss is locally convex resulting in the quadratic approximation being upper bound. For well trained overparametrized DNN assuming that the loss and the gradient at the minimum are zero is reasonable. Assuming local convexity at the minimum is also often reasonable assumption Sagun et al. (2017): Li et al. (0088)
Regarding the validity of the quadratic approximation we note that often provides state of the art results in DNN compression Dong et al. (2017); Wang et al. (2019); Peng et al. (2019); LeCun
et al. (1990p: Hassibi & Stork (1993) being highly informative about parameter relevence. Finally will be analyzing Gaussian posterior distributions with diagonal close diagonal covariance which can be assumed to sufficiently concentrate around the minimum making the local second order approximation meaningful.
4.1 OPTIMAL POSTERIOR
We make the following modeling choices Q N( En) and P (N,,, AE1) which are popular and PAC-Bayes literature. We can then show that the optimal posterior covariance of the above objective for fixed prior and posterior means has closed form solution.
Lemma 4.1. The convex optimization problem ming, E 12 ( + (KL(QIIP) where Q Nopo, Eo) and P ((,,, NEi) has the global minimum:
n-
3 (
3
where H, captures the curvature in the directions of the parameters, while Σn is a chosen prior covariance.
This can been seen as Laplace approximation Bishop 2006) to the posterior around the MAP solution. In practice will be using by performing gnd search over the parameters 3 and X. Then we will try to find Pareto optimal pairs balancing the accuracy of the randomized classifier and the KI. complexity term.
4.2 OPTIMAL PRIOR
The above solution is not optimal with respect to the prior covariance in that we have up to now chosen it arbitrarily. Furthermore given that the choice of the random initialization as the prior mean has been independently shown to result in much tighter bounds in a variety of settings Dziugaite & Roy (2017): Nagarajan & Kolter (2019a) one would wish to isolate the effects of the prior mean on the bound tightness from the prior covariance.
PAC- AAC-Bayesian theory allows one to choose an informative prior, however the prior can only depend on the data generating distribution and not the training set. A number of previous works Parrado- Hermández et al.] (2012); Catoni (2003); Ambroladze et al. (2007) have used this insight mainly on simpler linear settings and usually by training classifier separate training set and using the
5

---

Under review as a conference paper at ICLR 2020
Mnist2
Cifar2
1.0
1.0
Feasible
KL 2
(2]) /22
Non- Van-VVauous
0.4
0.4
0.2
0.2
0.0
0.0
0.4
Training Accuracy
Training Accuracy
(a)
(b)
Figure 2: Feasible solutions solutioon vs Non- Vacuous solutions: We merge the classes in Mnist and Cifar to create simpler 2 class problems. For different values of 3 we compute the optimal complexity
terms V P)++1 21--1)
using 7 We compute the accuracy of stochastic classifier with MC for samples. We plot this Tower bound with the solid black line. All points above it are feasible. We see that for the Mnist problem the two regions intersect suggesting that we might be able to prove generalization using Gaussians with diagonal covariance. By contrast in the Cifar case the two regions do not intersect suggesting that the prior and posterior means have prohibitive distance between them, and cannot prove generalization with diagonal covariances.
2N
result as prior. Recently Dziugaite & Roy (2018) have proposed to use the original training set to derive valid priors by imposing differential privacy constraints.
We ignore these concerns for the moment and optimize the prior covariance directly. The objective non-convex, however for the case of diagonal prior and posterior covariances can find the global minimum.
Lemma 4.2. The optimal prior and posterior for Cs(D; = In + (QII))) T-
with Q = NN En) and = N(H1,EE)) and assuming that ΣT = A = diag(A (A11, A21,... A&1) and Hr diag(hu, h22,..,, ... ha) have:
43ha
A 23
A3 + (M40 mx1)
hal,
(7)
4,8ha
A
2 ha +
h2 + (pio
(8)
pa pa
where Hi encodes the local curvature at the the minimum, P4 corresponds the random initializa- tion (by design) of the DNN, and μl corresponds to the minimun obtained after optinization.
For our choice of Gaussian prior and posterior, the following is lower bound on the IB- IB-Lagrangian under any Gaussian prior covariance:
Σ au (pso ma)² +.3 > In( ha + ail
min Cs(D: 2 M
}),
48844 where au e (3 p.o, Par. ha) 21 (M40 Wooo-Ma] ]a
ha).
The above result is intuitively pleasing setting lower bound to what can achieve which de- pends only on the initialization (by design), obtained minimum, curvature at the minimum and the regularization parameter B. In particular the scaling factor X has disappeared.

---

Under review as a conference paper at ICLR 2020
We now make some important notes about what one and cannot prove using these results, by stressing that the above result is a necessary but not a sufficient condition for generalization under prior and posterior modeling.
Given deterministic deep neural network and it's initialization (or other prior mean) one can rule out being able to prove generalization using any choice of diagonal covariances when modeling the priors and posteriors as multivariate Gaussians with fixed means. Mod- eling with other distributions may give different result:
One cannot prove generalization using this result, even in the case when the prior mean is valid (only distribution dependent) and the feasible and non-vacuous sets intersect. One still has to compute the prior and posterior covariances in a valid manner. As such a com- putationally feasible region given finite data and computational resources as well as privacy constraints, might be much smaller than the one we derive here.
We plot our lower bound for simplified 2 class Mnist and Cifar problems in Figure 2 while for the Mnist problem the feasible and non-vacuous regions intersect the same not true for the Cifar problem. What remains is to see if our results apply for the case of valid priors. First we detail a number of computational issues in section
We see that
5 COMPUTATIONAL ASPECTS
We now present number of computational and memory issues associated with the Hessian of modern deep neural network. There ambiguity in the literature about the size of the Hessians that can be computed exactly Kunstner et al. (2019). There have been few results in this area and the main problem seems to that the relevant computations are not well supported from common auto- differentiation libraries, such Tensorflow and Keras. However there is certainty the fact that storing and manipulating the full Hessian of a number of modern deep neural network architectures would be infcasible as the matrix is of size H E 2d where d is the number of parameters. As point of reference a dense uncompressed Numpy matrix for d = 50000 takes up 20GB of memory. As such we detail in the next section a number of approximations that make both computing and storing the Hessian feasible.
5.1 APPROXIMATING THE FULL HESSIAN
As noted in Kunstner et al. (2019) the generalized Gauss-Newton approximation of the Hessian (0) coincides with the Fisher matrix F()) = >n, (pootlzz)) (Vo log (a ( log (oly),,)) in modern deep learning architectures. While the Fisher matrix is difficult to compute exactly one can compute an unbiased but noisy estimate as Martens & Grosse (2015)
F(O) R
Σ Voloopoll. (xn) Vo log
(10)
where care must be taken to sample 7n from the model predictive distribution In ~ po (yly))))) Additionally note that the interpretation of the outputs after the softmax probabilities is not well grounded theoretically Gal & Ghahramani (2016). Determining the true predictive distribution requires MC sampling for example by taking multiple dropout samples Gal & Ghahramani (201)).
We now make two additional notes regarding computational aspects of the above. The approxi- mation of the Hessian can be computed efficiently as the outer product of large but manageable gradient vectors. The main computational burden after we approximate the Hessian, and given that we choose a standard normal prior, is inverting a matrix of the form H + az. This problem can be tackled in a few different ways. The simplest would be to consider only the diagonal elements of H and the resulting diagonal matrix can be efficiently inverted. However inversion of the full matrix H aT is also possible recursively using the Therman-Morrishe formula.
While our result is a formal lower bound what is achievable by d it's applicability on direct minimiza- tion of the IB-Lagrangian depends the tightness of the second order approximation.

---

Under review as a conference paper at ICLR 2020
Mnist2
Cifar2
1.0
1.0
Baseline
/L 2
(L(U))) /2m /22m
Diag Hessian
Full Hessian
0.4
0.4
0.2
0.2
0.0
0.0
0.4
Training Accuracy
Training Accuracy
(a)
(b)
Figure 3: Accuracy vs Complexity for different bounds: We plot V KL(QIIP)H 2(N-1)
and train- ing accuracy (of the randomized classifier) for different architectures and datasets. Points to the right of the dashed line correspond to non-vacuous pairs. All Mnist bounds are non-vacuous. All Cifar bounds are vacuous. We are able to progressively get tighter bounds by using the diagonal Hessian and then the full layerwise Hessian. The improvement is larger over the more difficult Cifar dataset.
2N
Further issues exist with computing the KL-Divergence of large multivariate Gaussians with diagonal covariances in closed form which includes a determinant term that has to be computed with the matrix determinant lemma, well as sampling efficiently from these distributions. As such we have used the diagonal variant of approximation I0 for our lower bound, but perform a layerwise approximation of the Hessian for all other experiments. We detail this layerwise approximation in the next section, and motivate it theoretically.
5.2 LAYERWISE APPROXIMATION
For specific case of the empirical loss we will now derive an upper bound on which is more suitable for optimization.
Lemma 5.1. Assuming the following empirical loss (()) lX) Y|le with X (.g.... ..., xNl
and Y = [y...... yn) the following is an upper bound on the IB Lagrangian given that we are at local minimum:
Co(D.P.Q) S Σ
& E
EV
cU
E H + > (L((U)))P)) mia 22
(11)
where denotes different layers, j denotes the different neurons each layer (we assume the same number for simplicity). Hij denotes the local Hessian, and Qi is centered version of Q The
local Hessian can be computed efficiently Hij 1 and 2 is the latent representation input to layer for signal i.
We see that we have managed to upper bound the empirical randomized loss by scaled sum of quadratic terms involving layerwise Hessian matrices and centered random noise vectors. Intuitively we have reduced the complexity of our optimization problem simply by turning it into number of separate subproblems. The local Hessians can be computed efficiently from outer products of forward pass of the dataset. Apart from avoiding using backpropagation, breaking the Hessian into subproblems in this manner allows us to move beyond the simplistic diagonal approximation. Im- plicitly the Hessian now has block diagonal structure and the blocks are small enough to be inverted directly for the architectures used in this paper. For architectures with larger latent representations the Ineemmnn-Mrrrisee formula uncommon in practice, we have found empirically that solving the posterior optimization problem in layerwise manner gives good results with the more common loss functions.
be used instead. While 5.I holds for specific loss which is
8

---

Under review as a conference paper at ICLR 2020
6 EXPERIMENTS
We now make a number of experiments on the simplified 2 class Mnist and Cifar datasets. Specifi- cally we test the architecture
input + 300FC - 300FC #classesFC output
on Mnist and
input > 200FC - 200FC - #classesFC > output
on Cifar. We note that the Mnist architecture corresponds exactly to the architecture T-300 p.7 in Dziugaite & Roy] (2017). We train each configuration to 100% accuracy and derive the layerwise Hessians. We model the prior and posteriors as multivariate Gaussians centered the initialization and deterministic solution respectively. For the prior we choose the uninformative unit diagonal covariance, scaled by the free parameter A. The baseline posterior that we use has the same diagonal covariance as the prior. For the baseline we perform grid search over À which increases the complexity negligibly. For the optimized posterior we initially test diagonal approximation of the Hessian "Diag Hessian" which results in an optimal diagonal covariance. We perform grid search for the parameters À and 3 using formula 66 to derive candidates for the optimal posterior covariance. For each point on the grid we calculate the empirical accuracy over the training set
using Monte Carlo sampling and 5 samples, as well as the complexity term KL(QIIP)+1n 20V We then choose the Pareto optimal points from all candidates. We plot the results in Figure
2N
Interestingly we see that for the case of Mnist the baseline is tight with respect to our lower bound and provides non-vacuous bounds. Therefore not much improvement can be achieved using the Hessian approach. This implies a more careful interpretation of the results in Dziugaite & Roy (217)) We see that non-vacuity can also be achieved as a result of the problem being very simple, and the choice of the prior mean being the random initialization. The optimization techniques em- ployed Dziugaite & Roy (017) should simply tighten the bound further, mainly by moving the posterior mean closer to the prior mean (the random initialization). For the case of Cifar we see that we can significantly tighten the bound. However we cannot manage to turn a vacuous bound to non-vacuous one in line with our lower bound. We also test block-diagonal approximation to the Hessian "Full L. Hessian" where each neuron of the network has it's own block. Our non- diagonal layerwise approximation however crude seems improve significantly over the diagonal case and slightly crosses our diagonal lower bound. This suggests that better approximations of the Hessian as well better prior means apart from the random initialization might be needed to prove generalization in complex datasets and architectures.
7 CONCLUSION
We have presented a lower bound on an approximation of the IB-Lagrangian for the case of multi- variate Gaussian priors and posteriors with diagonal covariance. This coincides with lower bound on PAC-Bayesian generalization bound for an invalid (training set dependent) prior. For cases where the feasible and non- vacuous regions intersect we have seen that it is possible to reach the lower bound and achieve non-vacuous bounds by using valid non-informative priors. We have also presented closed form solutions for the optimal posteriors given fixed means under our modeling assumptions, and motivated theoretically breaking the estimation into layerwise subproblems. Cru- cially all results depend on high quality estimates of the Hessian which remains an open topic of research for large scale modern deep neural networks.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep rep- resentations. The Journal of Machine Learning Research, 19(1):1947-196) 2018.
Alessandro Achille, Giovanni Paolini, Glen Mbeng. and Stefano Soatto. The information complexity of learning tasks, their structure and their distance. arXiv preprint arXiv: 1904003929 2019.
Amiran Ambroladze, Emilio Parrado-Hermández, and John S Shawe-taylor. Tighter pac-bayes bounds. In Advances in neural information processing systems, pp. 9-16, 2007.
Peter L Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249) 2017.
Christopher M Bishop. Pattern recognition and machine learning- springer, 2006.
Léonard Blier and Yann Ollivier. The description length of deep learning models. In Advances in Neural Information Processing Systems, pp. 2216-22231 2226, 2018.
Olivier Catoni. A pac-bayesian approach to adaptive classification. preprint, 840, 2003.
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. In Advances in Neural Information Processing Systems, pp. 4857-4867, 2017.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochasticc neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008, 2017.
Gintare Karolina Dziugaite and Daniel M Roy. Data-dependent pac-bayes priors via differential privacy. In Advances in Neural Information Processing Systems, pp. 8430-8441,2014
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty deep learning. In international conference on machine learning, pp. 1050-1059, 2016.
Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien. Pac-bayesian theory meets bayesian inference. In Advances Neural Information Processing Systems, pp. 1884 1892, 2016.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. arXiv preprint arXiv:1712.06541 2017.
Babak Hassibi and David G Stork. Second order derivatives for network pruning: Optimal brain surgeon. In Advances neural information processing systems, pp. 164-171, 1993.
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. arXiv preprint arXiv:1710.05444 2017.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batcl training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: 1609.048669 2016.
Mohammad Emtiyaz Khan, Didrik Nielsen, Voot Tangkaratt, Wu Lin, Yarin Gal, and Akash Srivas- tava. Fast and scalable bayesian deep learning by weight-perturbation in adam. arXiv preprint arXiv:1806.0 04854.. 2018.
Mohammad Emtiyaz Khan, Alexander Immer, Ehsan Abedi, and Maciej Korzepa. Approximate inference turns deep networks into gaussian processes. arXiv preprint 1906v:1906.00 0996001930, 2019.
Durk P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparameteri- zation trick. Advances in Neural Information Processing Systems, pp. 2575-2583, 2015.
Frederik Kunstner, Lukas Balles, and Philipp Hennig. Limitations of the empirical fisher approxi- mation. arXiv preprint arXiv: /905. /2558, 2019.
10

---

Under review as a conference paper at ICLR 2020
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-605, 1990.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. In Advances in Neural Information Processing Systems, pp. 6389-6399, 2018.
Xinyan Li, Qilong Gu, Yingxue Zhou, Tiancong Chen, and Arindam Banerjee. Hessian based analysis sgd for deep nets: Dynamics and generalization. arXiv preprint arXiv: (tfi:1997.11733. 2019.
Wesley Maddox, Timur Garipov, Pavel Izmailov, Dmitry Vetrov, and Andrew Gordon Wilson. A simple baseline for bayesian uncertainty in deep learning. arXiv preprint arXiv:1902.00477, 2019.
James Martens and Roger Grosse. Optimizing neural networks with kronccker-factored approximate curvature. In International conference on machine learning, pp. 1408-2217, 2015.
David A McAllester. Some pac-bayesian theorems. Machine Learning. 37(3):355-363 1999.
Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arXiv preprini urXiv:1901.0167. 2019a.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generaliza- tion in deep learning. arXiv preprint arXiv: 1 2019b.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956,
2017a.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. pac-bayesian approach to spectrally-normaaize margin bounds for neural networks. arXiv preprint arXiv:170700966. 2017b.
Emilio Swrado-Hernández, Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. Pac-bayes bounds with data dependent priors. Journal of Machine Learning Research, 13(De)):3507-3531 2012.
Hanyu Peng, Jiaxiang Wu, Shifeng Chen, and Junzhou Huang. Collaborative channel pruning for deep networks. In International Conference Machine Learning, pp. 5113-5122, 2019.
Konstantinos Pitas, Andreas Loukas, Mike Davies, and Pierre Vandergheynst. Some limitations of norm based generalization bounds in deep neural networks. arXiv preprini urXiv:1905.0961 2019.
Hippolyt Ritter, Aleksandar Botev, and David Barber, Online structured laplace approximations for overcoming catastrophic forgetting. In Advances in Neural Information Processing Systems, pp- 3738-3748, 2018.
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over- over-parametrized neural networks. arXiv preprint 1XXx:17706004544 2017.
John Saylor Peter L Bartlett, Robert C Williamson, and Martin Anthony. Structural risk
minimization over data-dependent hicrarchies. IEEE transactions on Information Theory, 44(5): 1940, 1998.
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/0004057, 2000.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Normalized flat minima: Exploring seale invariant definition of flat minima for neural networks using pac-bayesian analysis. arXiv preprint arXiv:1901.04653 2019.
Chaoqi Wang, Roger Grosse, Sanja Fidler, and Guodong Zhang. Eigendamage: Structured pruning in the froteeeer-factored eigenbasis. arXiv preprint 1rXiv:195.005934 2019.
11

---

Under review as a conference paper at ICLR 2020
Huan Wang, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. Identifying generalization properties in neural networks. arXiv preprint 180.0:8009 2018.
Anqi Wu, Sebastian Nowozin, Edward Meeds, Richard E Turner, José Miguel Hernández-Lobato, and Alexander L Gaunt. Deterministic variational inference for robust bayesian neural networks. arXiv preprint arXiv: 18X.:3810.03958. 2018.
Jun Yang, Shengyang Sun, and Daniel M Roy. Fast-rate pac- bayes generalization bounds via shifted rademacher processes. arXiv preprint orXiv:/908.0733 07585, 2019.
Guodong Zhang, Shengyang Sun, David Duvenaud, and Roger Grosse. Noisy natural gradient as variational inference. arXiv preprint arXiv:
2017.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P Adams, and Peter Orbanz. Non-vacuous gen- cralization bounds at the imagenet scale: a pac-bayesian compression approach. arXiv preprint arXiv: 05862, 2018.
12

---

Under review as a conference paper at ICLR 2020
APPENDIX
A. ADDITIONAL EXPERIMENTS
We test the architectures
input + 300FC - 300FC #classesFC output
on Mnist and
imput > 200FC 200FC #classesPC -utput
on Cifar. We conduct additional experiments the original Cifarl0 and Mnist datasets, well as Cifar5 and Mnist5 where we merge the 10 classes into 5. The results are consistent across datasets, with more improvement when incorporating the Hessian for more difficult datasets.
Mnist2
Mnist5
Mnist10
Buseline
/K P 72m
Diag Hessiau
(L4) )/2m 1mmm
KL (14) 722m
Pill Hession
Training Avourary
Traning Accuacy
Thining Aocuary
(b)
(C)
Cifar2
Cifar5
Cifar10
[K P) 2m
(KL pm2m
(L 1/2m
0.8
0.4
8.4
18
16.
16
6.
Training Accuracy
Trining Accuracy
Triinng Accuracy
(d)
(c)
(f)
Figure 4: Accuracy Complexity for different bounds: We plot KL(QIIP) +uu 2(N-1)
and train- ing accuracy (of the randomized classifier) for different architectures and datasets. Points to the right of the dashed line correspond to non-vacuous pairs. All Mnist bounds are non-vacuous. All Cifar bounds are vacuous. We are able to progressively get tighter bounds by using the diagonal Hessian and then the full layerwise Hessian. The improvement is larger over the more difficult Cifar dataset.
2N
13

---

Under review as a conference paper at ICLR 2020
B. PROOFS
Lemma 4.1. The convex optimization problem ming, E
12n
Hm)] + 3KL(QIIP) where
NHp, Eo) and P ~N(11; has the global minimum:
E = H Σ
(12)
where H2 captures the curvature in the directions of the parameters, while E1 is chosen prior covariance.
Proof.
1
Cb(D:..Q)=
E
Han (KL(QIP))
q~4
2
I tr tr(Hom " )) (KL(Q)
7~Q'2
1
H
E
1m7 1) + (KL(QIPP)
(13)
2
1
8 (tr( Σ Ev) k+
1
tr
H
(mo =1) (mo k1)
2
det AEi
In
det En
The gradient with respect to Eg is
0C OCa OΣ
1 H +
8
3
Σ
E
(14)
2
2X
2
Setting it to zero, we obtain the minimizer Ei = (H + 1-
Lemma 4.2. The optimal prior and posterior for CD)
(D; P.Q) = m- 2 1 H:n) +[KL((QIP)) with
Q = (N En) and P = NN AΣ and assuming that Σ A diag( (A11 .., Art) and H: diag(hu; h21 ...y har) have:
48ha
A
12 + (1iD Ms1)2 2B
hal,
(15)
4
AgO = 2 hhu +
h + (wio
(16)
pa 12
where H; encodes the local curvature at the the minimum, μi corresponds to the random initializa- tion (by design) of the DNN, and μuu corresponds to the minimum obtained after optimization.
For our choice of Gaussian prior and posterior, the following is lower bound the IB IB-Lagrangian under any Gaussian prior covariance:
ha + ail Ost
min Cs(D,P.Q) E
Z
Σ au (pro - paa 2 + Σ In
(17)
where og A aa (3, p4o, pal ha) = +1 12 + Taao-aa) har]-
48hha
14

---

Under review as a conference paper at ICLR 2020
We can then that the minimizer is equal to Eg = 3(H, AA) Substituting E = Enj in CD( we obtain:
Proof. Setting A1 Σラ'
Ca(D;
E n~
1
H + (KL(( Eo =
2
B ( (H + 8 A1) A1) ) + _ (tr( A15(H,
tr
A (A1)
X
det AA
+ (mo M1) A1)0 -11 - + In
det B(H, + A11
- br br(HH(H + 7 ()
8
3
82
(tr(A (H) A))
21
+ 2
8
1 (+
(10 (mo -11)² - (14 (1) kn
det AA
det ((1 + A AA))11
8
(tr((H, + B (1) + 3 -1))
2
det XA -1
X (14 -M1) A1 -11) - -k In
det ((H, + 8 X (11)
8 1
det AA
2 |+ (11 - A1 -11) +
det ((H, + AA)
(18)
The above matrix equation 18 difficult to deal with directly. We will therefore use the common diagonal approximation of the Hessian which is more amenable to manipulation. Substituting A1 diag(A1) A21, ..., A&1) and H, diag(hu,, be,,..., in the above expression we get
2 Σ Aa ma)²
hu + AA
C,) =
Σ In(
+
Σ
In(
(19)
B
The above expression is easy to optimize. We see that the sole stationary point exists at
4,3aa ha].
A 23
12 + (140 22)
(20)
We now turn to the original objective and calculate it's second derivatives. For our diagonal approx- imation the original objective turns into a sum of separable functions. We will analyze the behavior of one of them for simplicity. The result applies to all other functions in the sum.
Co(D;P.Q)
Σ
hi
2 V40 +
Σ
B Vio
Σ B
Σ
B(po mi1)2 1
2 Vi1
21
1/11
Σ In(Ae;))
Inn(uso)]
+
Σ A +
Σ
B
V40
3 Σ
Σ
C -
Dj
Di1E In(Aes)) - E Inn(vso]]
Vil
2
Vil
(21)
where we have set A by B, function from this sum calculate
8 2x.
C₁
B1 fa
M1um- pa ) 2x
D; = =6. Denoting (D P,Q) one
15

---

Under review as a conference paper at ICLR 2020
a (
B,
D,
(C; P.Q))
B
C
D;
A, +
(22)
Ovio
1/8
V40
dv:1
V11
11
2
Vi1
and
(D; P.Q)
Dj
O = 2( + +C2)
D:
(23)
v
1
Ov1
1/1
a0 (D; P.Q)
B.
@Cin(D;P,Q)
B V
(24)
dv.00v
Vi
We need to check whether the Hessian matrix is PSD so that the stationary point we found is local minimum and the function is convex. We do that by calculating whether all principal minors of the Hessian are positive.
D2
V Cis((ioo
(25)
C.
D2
We see easily that det( D. > 0. While
Dj
D3
B²
det Ci (voo, u2))
2(B Ci) C,)
4/0
1/11
Vi
(2C,Dius - -Divii - B,
(26)
g2
(Ni0
A21) Vi1
Vi0 kioga A
(1/1
1 2
A
A first observation is that this determinant is not always positive and the function is not convex everywhere. However we observe that it is not highly non convex either and the non convexity mainly results from the function tending to infinity logarithmically now check whether the sole stationary point is always a local minimum. We start by substituting vs = 8(ha + & mi ) in the multiplicand of 26 as the multiplier is positive by definition
of the boundaries. We
1
82
(14D
111)2
3 (ha +
3 1
)
det 2 Cis va))
(V
10D
VAA
2
X
2
X
Vii
1/
2
1
$1
2
(M:0
1/11
(v/1
X
B
haddva + 3 3))2
vild
1
B2
(140 -
m2
v2
B
1/00
2
V
2
X
V/1
2
(1
hundva + B G))2
1
8
(M40
Va
hadvai + 3 )2)
haidva
(27)
2
V
2
1
B
(M4O - pa1)
X213,12
0/0
2
X
2(ha Aer + -322
(2(140 - Mz1 ( + 8)² - -x*12uu)
1/ 22 2M 3)2
(2A - 2had An -2 x²
1/0 22 3)²
Where we substituted 1/11 = A as this will make the calculations easier. We now show a useful identity for A₁ 26 IV
12
49ha ha]
(Ma0-61)²
16

---

Under review as a conference paper at ICLR 2020
X
48ha
48hu
(A7)²
hig +
2h
1 +
+ 1131
4,3
(1UD0
maa)²
(JuO
1461 )2
X
4.h
48har
2ha
hir
h1 + (110 - 12112
4,32
(140
14:1)2
(28)
had
4,haa
2,3
his
h2 + (piO - 1bs1)
B 23
(1450-
14;1)2
h4d A
À
A71
3
(1400
}2
We substitute A,1 = A in 27 and again develop only the multiplicand
det (is v11))
(2A7 (a1) (aa)(aaa++++ M,B3 x222))
vio 32AhsAAd; -1 + 3)2
= A (p:0 (ha) + -
A (n:0 pa) (h) + +2
2 1212))
had
A. (1:0 pa) (1 + 22w
A/1 32) (213))
B
(u40 - 1il)²
BX²ha
A,(2%) (140 (4)) (1 + B +
(1400 - maa)2 x²11
322ha
A,(2A (M Ma1 (hi)2 +
+ ((AA1))(0 - 12a)2 x²h3))
(160 -aa1)²
192h1a
= A,22A, (p:0
Ma) 2 +
(M5O Mi1) )
had
+
(#::0 -2a)²² - A,
-A
(M:0 - Ma1) 12 12121118 8- 2²1
3
92²hu
= A, (1:00 m4i) (11) +
22 - -22 - 1a)PAa x²12))
(M6D Mil )2
322ha
= A.(2A) pa) (12 + (M:0 M11
+ 13 2h mm))
8A ha + x12)))
=
> 0
(29)
where we have set A; "2M(HuM(A)) +9)2 0. We have used 28 in lines 4 and 7.
Indeed the stationary point always a local minimum. What remains is to show that there are no other local minima at the boundaries of the domain. From 21 we that only need to evaluate 1 + In(voo). By application of
expressions of the form f(100) = 1/10 In(24)) and g(va1)
L' L'Hôpital's rule it's easy to show that
lim Cis(Pan (Mi,, 1/1) = lim Cip(uso, va)
M4o +0
Uso +oc =u=
=a
(30)
lim Cio(uso, vi))
lim
Oss(soo m1) t00
841
this concludes the proof.
17

---

Under review as a conference paper at ICLR 2020
Lemma 5.1. Assuming the following empirical loss [(0) [l) Y with X
[ .... NN|
and = Yo. ...: yNl the following is an upper bound on the IB Lagrangian given that we are at local minimum:
C&(D.P V
E cu 2/
n" H n. + 3 Σ (L(Q))|1P)))
(31)
where/ denotes different layers, j denotes the different neurons at each layer (we assume the same number for simplicity). Hij denotes the local Hessian, and Qi1 centered version of Qıj. The
D oi local Hessian can computed efficiently as HI N representation input to layer/ 7 for signal i.
T and 2 is the latent
Proof. We start by defining layerwise empirical error Ei)) NV EN [
2. One
then easily show that [()) - Ek=l V Bi((i) I ||0x|le + v (l Dong et al. (017) substituting this in the IB Lagrangian we get
Cs(D;
E [i(()] + (QI(P)) e~Q
E
())
II km/+1
110lle + EL(OL)) +
E
(O))
II
E [10011]]+++++++
V VonQ "o [0..0 (KL(Q))))))
E
1=++1
(32)
E
[B)) + (KL(
A~Q
T
1
+ 2" H (([lll (KL((
1~Q
00,
EF 1 2
17 H (KL(QI)P))
1=1
were in line we use the linearity of expectation, Hölder's inequality due to the non-negativity of the random variables, and Jensen's 's inequality for the concave square root. In line 4 we hide the Frobenius terms into constants o₁. Each error term (,)) is only multiplied with Frobenius norm terms || from the deeper layers. Therefore one can start optimizing from the final layer and proceed to the first while considering a constant. In practice we will just consider all oi unknown scaling factors. In line 5 expand each (0:) term using Taylor expansion, and subsequently ignore the first term as the DNN is assumed to be well trained and the first derivative will be zero, while terms with order higher than 2 are unimportant. We also use Q' denote the centered version of distribution Q.
Taking the first and second derivatives of the layerwise error with respect to W. get
(
1 N
|
-
2
1
N Wizi_1
-2)222 T
(33)
OW:
N
OW,
N
(E)
1
(34)
aw aw www
N
Where the second derivative is with respect to any w(i:) of the weight matrix W,. We that the full Hessian matrix H, (.(() then has block diagonal structure where each block is equal Hy 1/4 ENv - T Each row w corresponds neuron of the layer and for
TWW,
18

---

Under review as a conference paper at ICLR 2020
appropriate choice of prior and posterior with block diagonal covariances it is easy to see that the final form of expression 32 factorizes as
Ca(D; E
Σ
cta
n + Σ
H1g
KL(Quil(Ps)
(35)
this completes the proof.
19


Reviews:
[{"review_id": "SygqmIu4qS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "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: The paper provides several approximations of PAC-Bayes generalization bounds for Gaussian prior and posterior distributions, with various restrictions on the covariance matrices.  \nIn particular, the paper: \n(1) Assumes that the expectation of the loss can be Taylor expanded around each point in the support, and all but the quadratic (Hessian) term can be ignored. \n(2) Proves a lower bound on the PAC-Bayes generalization objective. \n(3) Provides an upper bound on the PAC-Bayes objective via a \"layerwise\" Hessian objective. \n\nEvaluation: I found this paper extremely difficult to follow because it's sloppy in various places -- both in terms of what claims are formal, and what are heuristic approximations -- and in terms of properly defining crucial quantities. I will go in the same numbered order in which I listed the main contributions above: \n(1) (Taylor approximation): The equation (4) is an *approximation* -- not a lower or upper bound. Moreover, too little is said about this heuristic: note that the authors actually Taylor expand an *expectation* over \\theta -- the trivial thing to require for this Taylor approximation to hold is that it holds for *every* theta which clearly will not be true. It seems the authors want to say the distribution Q concentrates over thetas close to some local optimum \\theta^*, and over these thetas the approximation holds. At the very least something needs to be said about how much things need to concentrate and whether this is realistic in real-life settings. \nAlso, because (4) is an approximation, it's a little disengenuous to call Theorems 4.2 and 5.2 \"theorems\", and it needs to be mentioned in the statements that they hold under some formalization of the approximation I described above. \n(2) The lower bound is written very oddly -- the \"prior\" for the lower bound is really dependent upon the posterior -- so it is very strange to call it an \"invalid\" prior. Moreover, I have serious problems evaluating the meaning of this lower bound -- as it uses the Taylor approximation from (1), but then decides to instantiate the prior *depending on the optimum* of this Taylor approximation. As such, *at the very least* -- some small neural net examples should be tried where the normal (un-approximated) KL bound can be evaluated, to check whether this *actually* is a lower bound most of the time. \n(3) The upper bound is also written rather sloppily: Q_{lj} is never defined; H_{lj} only depends on l, rather than j -- in fact, I'm fairly sure it should be H_l, and \\eta should be sampled from Q_{l} (i.e. a vector with a coordinate for each neuron in layer l) if I understood the proof correctly. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "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": {}}, {"review_id": "BygyoQSKYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 authors  replace the empirical risk term in a PAC-Bayes bound by its second-order Taylor series approximation, obtaining an approximate (?)  PAC-Bayes bound that depends on the Hessian. Note that the bound is likely overoptimistic unless the minimum is quadratic. They purpose to study SGD by centering the posterior at the weights learned by SGD. The posterior variance that minimizes this approximate PAC-Bayes bound can then be found analytically. They also solve for the optimal prior variance (assuming diagonal Gaussian priors/posteriors), producing a hypothetical \"best possible bound\" (at least under the particular choices of priors/posteriors, and under this approximation of the empirical risk term). The authors evaluate their approximate bound and \"best bound possible\" empirically on MNIST and CIFAR. This requires  computing approximations of the Hessian for small fully connected neural networks trained on MNIST and CIFAR10. There are some nice visualizations (indeed, these may be one of the most interesting contributions.)\n\nThe direction taken by the authors is potentially interesting. However, there are a few issues that would have to be addressed carefully for me to recommend acceptance. First, the comparison to (some very) related work is insufficient, and so the actual novelty is misrepresented (see detailed comments below). Further, the paper is full of questionable vague claims and miscites/attributes other work. At the moment, I think the paper is below the acceptance threshold: the authors need to read and understand (!) related work, and expand their theoretical and/or empirical results to produce a contribution of sufficient novelty/impact. \n\nDETAILED FEEDBACK.\n\nI believe the authors missed some related work by Tsuzuki, Sato and Sugiyama (2019), where a PAC-Bayes bound was derived in terms of the Hessian, via a second-order approximation. How are the results presented in this submission relate to Tsuzuki et al approach? \n\nWhen the posterior, Q, is a Gaussian (or any other symmetric distribution), \\eta^T H \\eta is the so-called Skilling-Hutchinson trace estimator. Thus E(\\eta^T H \\eta) is the Trace(H) scaled by the variance of \\eta. The authors seem to have completely missed this connection, which simplifies the final expression considerably.\n\nWhy is the assumption that the higher order terms are negligible reasonable? Citation or experiments required.\n\nRegarding the off-diagonal Hessian approximation: how does the proposed layer-wise approximation relate to k-FAC (Martens and Grosse 2015)?\n\nIB Lagrangian: I am not sure why the authors state the result in Thm 4.2 as a lower bound on the IB Lagrangian. What’s the significance of having a lower bound on IB Lagrangian?\n\nOther comments: \n\nIntroduction: “At the same time neither the non-convex optimization problem solved in .. nor the compression schemes employed in … are guaranteed to converge to a global minimum.”. This is true but it is really not clear what the point being made is. Essentially, so what? Note that PAC-Bayes bounds hold for all posteriors, even ones not centered at the global minimum (of any objective). The claims made in the rest of the paragraph are also questionable and their purposes are equally unclear. I would be grateful if the authors could clarify.\n\nFirst sentence of Section 3.1: “As the analytical solution for the KL term in 1 obviously underestimates the noise robustness of the deep neural network around the minimum...”. I have no idea what is being claimed here. The statement needs to be made much less vague.  Please explain.\n\nSection 4: “..while we will be minimizing an upper bound on our objective we will be referring with a slight abuse of terminology to our results as a lower bound.”. I would appreciate if the authors could clarify what they mean here.\n\nSection 4.1 beginning: “We make the following model  assumptions...”. Choosing a Gaussian prior and posterior is not an assumption. It's simply a choice. The PAC-Bayes bound is valid for any choices of Gibbs classifiers. On the other hand, it is an assumption that such distributions will yield \"tight\" bounds, related to the work of Alquier et al.\n\nSection 4.1 “In practice we perform a grid search over the parameters..”. The authors should mention that such a search should be accounted for via a union bound (or otherwise). The \"cost\" of such a union bound should be discussed.\n\nThe empirical risk of Q is computed using 5 MCMC samples. This seems like a very low number, as it would not even give you one decimal point of accuracy with reasonable confidence! The authors should either use more samples, or account for the error in the upper bound using a confidence interval derived from a Chernoff bound.\n\nSection 4.2: “The concept of a valid prior has been formalized under the differential privacy setting...”. I am not sure what the authors mean by that.\n\nSection 5: “There is ambiguity about the size of the Hessians that can be computed exactly.” What kind of ambiguity?\n\nSame paragraph in Section 5 discusses why there are few articles on Hessian computation. The authors claim that “the main problem seems to be that the relevant computations are not well supported...”. This is followed by another comment that is supposed to contrast the previous claim, saying that storing the Hessian is infeasible due to memory requirements. I am not sure how this claim about memory requirements shows a contrast with the claim on computation not being supported.\n\nFirst sentence in Section 5.1: I believe this is only true under some conditions. \n\nSection 5.1: The authors should explain why they add a damping term, alpha, to the Hessian, and how alpha affects the results.\n\n***\nAdditional citation issues:\n\nThe connections between variational inference, PAC-Bayes and IB Lagrangian have been pointed out in previous work (e.g. Germain, Bach, Lacoste, Lacoste-Julien (2016); Achille and Soatto 2017).\n\nIn the introduction, the authors say “...have been motivated simply by empirical correlations with generalization error; an argument which has been criticized …” (followed by a few citations). Note, that this was first criticized in Dziugaite and Roy (2017). \n\n“Both objectives in … are however difficult to optimize for anything but small scale experiments.”. It seems peculiar to highlight this, since the approach that the authors are presenting is actually more computationally demanding. \n\nCitations for MNIST and CIFAR10 are missing.\n\n***\nMinor:\nTheorem 3.1 “For any data distribution over..”, I think it was meant to be \\mathcal{X} \\times  (and not \\in )\nTheorem 4.2: “For our choice of Gaussian prior and posterior, the following is a lower bound on the IB-Lagrangian under any Gaussian prior covariance”. I assume only the mean of the Gaussian prior is fixed.\n\n\nCitations are misplaced (breaking the sentences, unclear when the paper of the authors are cited).\nThere are many (!) missing commas, which makes some sentences hard to follow.\n\n***\nPositive feedback: I thought the visualizations in Figure 2 and 3 were quite nice.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked 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": "BkeaQvJptS", "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 propose a second-order approximation to the empirical loss in the PAC-Bayes bound of random neural networks. Though the idea is quite straightforward, the paper does a good job in discussing related works and motivating improvements.\n\nTwo points made about the previous works on PAC-Bayesian bounds for generalization of neural networks (especially Dziugaite & Roy, 2017) are:\n* Despite non-vacuous, these results are obtained on \"significantly simplified\" datasets and remain \"significantly loose\"\n* The mean of q after optimizing the PAC-Bayes bound through variational inference is far different from the weights obtained in the original classifier.\n\nThese points are valid. But it's unclear to me that the proposed method fixes any of them. My concerns are summarized below:\n* The inequalities are rather arbitrary and not convincing to me. BY Taylor expansion one actually get a lower bound of the right hand side, However the authors write it as first including the higher-order terms, which results in an upper bound, then throwing the higher-order term and arguing the final equation as an approximate upper bound. I believe this can be incorrect when the higher-order terms plays an nonnegligible role.\n* The theorems are easy algebras and better not presented as theorems.\n* The proposed diagonal and layer-wise approximation to hessian are very rough estimate of the original Hessian and it is not surprising that it doesn't give meaningful approximation of the original bound. \n* There is no explicit comparison with previous methods using the same dataset and architecture. It would be much more convincing if the authors include the results of previous works using the same style of figures as Figure 2/3.\n\nMinor:\n* I understand using the invalid bound (optimizing prior) as a sanity check. But the presentation in the paper could better be improved by explaining why doing this.\n* Do the plots in Figure 2 correspond to the invalid or valid bound?\n* Many papers are complaining that Hessian computation is difficult in autodff libs without noticing this is a fundamental limitation of these reverse-mode autodiff libraries and no easy fix exists.\n* I believe MCMC is not used and the authors are refering to MC (page 7, first paragraph).\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper computes an "approximate" generalization bound based on loss curvature. Several expert reviewers found a long list of issues, including missing related work and a sloppy mix of formal statements and heuristics, without proper accounting of what could be gleaned from some many heuristic steps. Ultimately, the paper needs to be rewritten and re-reviewed. 
Decision: Reject