NON-VACUOUS GENERALIZATION BOUNDS AT THE IM- AGENET SCALE: A PAC-BAYESIAN COMPRESSION APPROACH
Modern neural networks are highly overparameterized, with capacity to substantially overfit to training data. Nevertheless, these networks often generalize well in practice. It has also been observed that trained networks can often be "compressed" to much smaller representations. The purpose of this paper is to connect these two empirical observations. Our main technical result is a generalization bound for compressed networks based on the compressed size that, combined with off-theshelf compression algorithms, leads to state-of-the-art generalization guarantees. In particular, we provide the first non-vacuous generalization guarantees for realistic architectures applied to the ImageNet classification problem. Additionally, we show that compressibility of models that tend to overfit is limited. Empirical results show that an increase in overfitting increases the number of bits required to describe a trained network.
This paper tries to push forward in important directions the seemingly increasingly powerful approach of using PAC-Bayesian formalism to explain low risks of training neural nets on real-life data. They take an interesting approach to evaluate these bounds by setting up a prior distribution as a mixture of Gaussians centered on possible heuristic compressions of the net  and this prior's variances are obtained by doing a layerwise grid search. This seems to give good risk bounds on certain known compressible nets using image data sets. 
Let me list out a bunch of issues that seem to be somewhat confusing in this paper (some of these were in the comment thread I had with the authors but I am repeating nonetheless for completeness) 
0.
Firstly this form of the PAC-Bayes formula used here (Theorem 2.1) is of a more complicated form than what has been previously used in say these papers, https://arxiv.org/abs/1707.09564 Given this I strongly feel that there is a need for an explanation connecting this formalism to the usual one - particularly something that proves how this is stronger than the one in the paper I referred to earlier. 
1. 
In the statement of Theorem 2.1 there is a \lambda parameter over which the infimum is being taken. If I understand right in the experiments one is substituting the upperbound on KL from Theorem 4.3 into this RHS of Theorem 2.1 and evaluating this. Now there is also a \lambda parameter in Theorem 4.3. Is this the same \lambda as in Theorem 2.1 and when a grid-search is being done over \lambda is the "whole" thing (theorem 2.1 upperbound with theorem 4.3 substituted) being minimized by choosing a good \lambda? 
If the two \lambda s are different then is the choice of the 2 \lambda s being optimized separately? 
(...the authors had earlier clarified that this is so and I strongly feel this is a very important clarification should be updated into the paper..)
2. 
How is the \sigma of Theorem 4.3 chosen in the experiments? Am I right in thinking that this \sigma is the posterior variance about which it is being said towards the end of page 6 that "We add Gaussian noise with standard deviation equal to 5% of the difference between the largest and smallest weight in the filter." ? 
So am I to understand that this is an arbitrary choice? Or is this choice dictated by some need to ensure that the posterior variance sigma is chosen so that under this distribution the sampled nets approximately compute the same function on the training data? (If yes, then what in the theory is motivating this?). 
To the best of my understanding the results are highly dependent on this choice of sigma but there is virtually no explanation for this choice which was not even found by grid search. (As of now this is merely reflective of the fact that trained nets often have some noise resilience but its not a priori clear as to why that should be important to the PAC-Bayes formalism here.)   
3.
The code based compression seems a bit mysterious to me given that I do not have enough familiarity with the algorithm that is being referred to. Hence it seems a bit weird as to why there is a sum over codebooks in the proof of Theorems 4.3. Naively I would have thought that there is a fixed codebook for a given compression scheme but here it feels that the compression scheme is a randomized algorithm which also generates a new codebook in every run of it. This seems unusual and seems to need more explanation and at the very least a detailed pseudocode explaining exactly how this compression is working.  
This point ties in with a somewhat larger issue I describe next...
4.
In the previous reply to my comment the authors had shared their anonymized code and l had a look through the code. Its pretty evident from the code there are an enormous number of tweaks and hyperparameter tunings to make this work. There is very little insight otherwise as to why "Dynamic Network Surgery' should work and its great that the authors have found an implementation that works on their image data. 
But then the question arises that there should have been a cleanly abstracted out pseudocode explaining how the compression was done and how the dynamic network surgery was done. To my mind this implementation is the main contribution of the paper and giving the pseudocode for it in the paper seems not only important for essential completeness of the current paper but that could also then act as a springboard for many future attempts at trying to come up with theory for these mysterious procedures.