Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: Summary: The paper provides several approximations of PAC-Bayes generalization bounds for Gaussian prior and posterior distributions, with various restrictions on the covariance matrices.  
In particular, the paper: 
(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. 
(2) Proves a lower bound on the PAC-Bayes generalization objective. 
(3) Provides an upper bound on the PAC-Bayes objective via a "layerwise" Hessian objective. 

Evaluation: 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: 
(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. 
Also, 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. 
(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. 
(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. 

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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.

Two points made about the previous works on PAC-Bayesian bounds for generalization of neural networks (especially Dziugaite & Roy, 2017) are:
* Despite non-vacuous, these results are obtained on "significantly simplified" datasets and remain "significantly loose"
* The mean of q after optimizing the PAC-Bayes bound through variational inference is far different from the weights obtained in the original classifier.

These points are valid. But it's unclear to me that the proposed method fixes any of them. My concerns are summarized below:
* 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.
* The theorems are easy algebras and better not presented as theorems.
* 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. 
* 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.

Minor:
* 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.
* Do the plots in Figure 2 correspond to the invalid or valid bound?
* 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.
* I believe MCMC is not used and the authors are refering to MC (page 7, first paragraph).

review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: 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.)

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

DETAILED FEEDBACK.

I 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? 

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

Why is the assumption that the higher order terms are negligible reasonable? Citation or experiments required.

Regarding the off-diagonal Hessian approximation: how does the proposed layer-wise approximation relate to k-FAC (Martens and Grosse 2015)?

IB 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?

Other comments: 

Introduction: “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.

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

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

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

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

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

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

Section 5: “There is ambiguity about the size of the Hessians that can be computed exactly.” What kind of ambiguity?

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

First sentence in Section 5.1: I believe this is only true under some conditions. 

Section 5.1: The authors should explain why they add a damping term, alpha, to the Hessian, and how alpha affects the results.

***
Additional citation issues:

The 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).

In 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). 

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

Citations for MNIST and CIFAR10 are missing.

***
Minor:
Theorem 3.1 “For any data distribution over..”, I think it was meant to be \mathcal{X} \times  (and not \in )
Theorem 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.


Citations are misplaced (breaking the sentences, unclear when the paper of the authors are cited).
There are many (!) missing commas, which makes some sentences hard to follow.

***
Positive feedback: I thought the visualizations in Figure 2 and 3 were quite nice.

review_title: Official Blind Review #1

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