Venue: ICLR 2020 Conference

Reviews:

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

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

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


***************************

After rebuttals:

Unfortunately, my concerns are not addressed adequately by authors. Therefore, my evaluation remains the same.
review_title: Official Blind Review #2

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

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

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

Significance: 
My 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. )

Experiments: 
* 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. 
* 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.


Writing: 
The writing is overall ok which some vague places such as 
*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
*first page, last paragraph, last line: "..better uncertainty than the baseline". The authors do not specify the baseline which makes this whole claim vague.

Title: 
This 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.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: 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.

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

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

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

 In experiments, the authors explore and analyze the tightness of the proposed bounds for various hyperparameters like the variance of the weights prior.

They 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
review_title: Official Blind Review #3

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