Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper connects Entropy-SGD with PAC-Bayes learning. It shows that maximizing the local entropy during the execution of Entropy-SGD essentially minimize a PAC-Bayes bound on the risk of the Gibbs posterior. Despite this connection, Entropy-SGD could lead to dependence between prior and data and thus violate the requirement of PAC-Bayes theorem. The paper then proposes to use a differentially private prior to get a valid PAC-Bayes bound with SGLD. Experiments on MNIST shows such algorithm does generalize better.

Linking Entropy-SGD to PAC-Bayes learning and making use of differential privacy to improve generalization is quite interesting. However, I'm not sure if the ideas and techniques used to solve the problem are novel enough.
It would be better if the presentation of the paper is improved. The result in Section 4 can be presented in a theorem, and any related analysis can be put into the proof. Section 5 about previous work on differentially private posterior sampling and stability could follow other preliminaries in Section 2. The figures are a bit hard to read. Adding sub-captions and re-scaling y-axis might help.

review_title: review

final_score: rating: 6: Marginally above acceptance threshold
review_content: Brief summary:
    Assume any neural net model with weights w. Assume a prior P on the weights. PAC-Bayes risk bound show that for ALL other distributions Q on the weights, the the sample risk (w.r.t to the samples in the data set) and expected risk (w.r.t distribution generating samples) of the random classifier chosen according to Q, averaged over Q, are close by a fudge factor that is KL divergence of P and Q scaled by m^{-1} + some constant.

Now, the authors first show that optimizing the objective of the Entropy SGD algorithm is equivalent to optimizing the empiricial risk term + fudge term over all data dependent priors P and the best Q for that prior. However, PAC-Bayes bound  holds only when P is NOT dependent on the data. So the authors invoke results from differential privacy to show that as long as the prior choosing mechanism in the optimization algorithm is differentially private with respect to data, differentially private priors can be substituted for valid PAC-Bayes bounds rectifying the issue. They show that when entrop SGD is implemented with pure gibbs sampling steps (as in Algorithm 3), the bounds hold.

Weakness that remains is that the gibbs sampling step in Entropy SGD (as in algo 3 in the appendix) is actually approximated by samples from SGLD that converges to this gibbs distribution when run for infinite hops. The authors leave this hole unsolved. But under the very strong sampling assumption, the bound holds. The authors do some experiments with MNIST to demonstrate that their bounds are not trivial. 

Strengths:
  Simple connections between PAC-Bayes bound and entropy SGD objective is the first novelty. Invoking results from differential privacy for fixing the issue of validity of PAC-Bayes bound is the second novelty. Although technically the paper is not very deep, leveraging existing results (with strong assumptions) to show generalization properties of entropy-SGD is good.

Weakness:
  a) Obvious issue : that analysis assumes the strong gibbs sampling step.
  b) Experimental results are ok. I see that the bounds computed are non-vacuous. - but can the authors clarify what exactly they seek to justify ? 
 c) Typos: 
   Page 4 footnote "the local entropy should not be <with>.." - with is missing.
   Eq 14 typo - r(h) instead of e(h) 
   Definition A.2 in appendix - must have S and S' in the inequality -both seem S.

d) Most important clarification: The way Thm 5.1, 5.2 and the exact gibbs sampling step connect with each other to produce Thm 6.1 is in Thm B.1. How do multiple calls on the same data sample do not degrade the loss ? Explanation is needed. Because the whole process of optimization in TRAIN with may steps is the final 'data dependent prior choosing mechanism' that has to be shown to be differentially private. Can the authors argue why the number of iterations of this does not matter at all ?? If I get run this long enough, and if I get several w's in the process (like step 8 repeated many times in algorithm 3) I should have more leakage about the data sample S intuitively right ?

e) The paper is unclear in many places. Intro could be better written to highlight the connection at the expression level of PAC-Bayes bound and entropy SGD objective and the subsequent fix using differentially private prior choosing mechanism to make the connection provably correct. Why are all the algorithms in the appendix on which the theorems are claimed in the paper ??

Final decision: I waver between 6 and 7 actually. However I am willing to upgrade to 7 if the authors can provide sound arguments to my above concerns.
review_title: Reasonably good idea (but with lots of strong assumptions) connecting generalization of entropy SGD and PAC-Bayes risk bound. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 1) I would like to ask for the clarification regarding the generalization guarantees. The original Entropy-SGD paper shows improved generalization over SGD using uniform stability, however the analysis of the authors rely on an unrealistic assumption regarding the eigenvalues of the Hessian (they are assumed to be away from zero, which is not true at least at local minima of interest). What is the enabling technique in this submission that avoids taking this assumption? (to clarify: the analysis is all-together different in both papers, however this aspect of the analysis is not fully clear to me).
2) It is unclear to me what are the unrealistic assumptions made in the paper. Please, list them all in one place in the paper and discuss in details.

review_title: Weak Accept

Decision: Reject