Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper obtains a compression-based generalization bound (Theorem 1) for the original network, while prior work gives bounds for the compressed network. The general bound given by Theorem 1 is further applied to networks with low-rank weight matrices (Theorem 2 and Corollary 1) or low-rank covariance matrices (Theorem 3 and 4). In some cases, the bound given by Theorem 1 for the original network could be better than the bound for the compressed network.

In terms of proof techniques, Lemma 2 is a general result to control the local Rademacher complexity using upper bounds on the covering numbers, which is interesting and could be useful in other problems.

On the other hand, there are two technical concerns.
(1) In eq. (5), the covering number of {\phi(f)-\phi(g)} is bounded by the covering number of {f-g}, which is not necessarily true. For example, in the 1-dimensional case, it is possible that f-g is always 1, while \phi(f)-\phi(g) is not a constant. This example might appear since f and g are not freely chosen from F and G; they further need to satisfy the condition that |f-g|_{L_2} is bounded by r. If the claim in eq. (5) is indeed true, a proof is needed.
(2) Despite the issue in (1), many bounds in the paper may actually be okay, since in the proofs the covering numbers of F (the original networks) are used (e.g., in eq. (6) and Lemma 2). Therefore it looks like the local Rademacher complexity of F can be controlled directly using Lemma 2. The question then is how compression helps in the analysis?

I hope the above points can be clarified, and I would like to participate in the discussion.
review_title: Official Blind Review #4

final_score: rating: 8: Accept
review_content: The paper presents novel theoretical results on generalization bounds via compression. Similar ideas in the last few years appeared, but only bounds on a compressed network were obtained. In contrast, the current submission gives a bound on the original (uncompressed) network in terms of the complexity of the compressed network class.

Overall, the paper seems to be well-written. I appreciate that the outlines of the proofs are included in the main text, which helps the reader follow the ideas. The result is novel and quite interesting. The new bounds seem to be still quite far from giving tight generalization theory, but I believe the paper provides some nice theoretical results for other researchers to improve upon. I think the paper could be improved immensely by some empirical analysis of the rank of compressed standard vision networks and rank of activation covariance matrices.  There are also some citation issues (see detailed comments below).

Citation issues:
In the introduction, paragraph 2, the authors cite Neyshabur et al. 2019 for the observation that networks generalize well despite being overparameterized. It seems like an odd choice. Why is Barttlet’s ‘99 paper [“Size of the weights…”]  not cited? Or at least Neyshabur et al. 2015? 
Then the authors mention that classical learning theory cannot explain the phenomena mentioned above, and classical theory “.. suggests ” that overparameterized models cause overfitting…”. The authors need to be more precise and add citations (I am assuming that the authors are talking about VC bounds for worst-case ERM generalization).
In the third paragraph, where the authors talk about norm-based bounds being lose, it seems that Nagarajan and Kolter 2019 should be cited (not only at the end), as well as Dzigaite and Roy 2017 (they look into the looseness of path-norm and margin-based bounds).

Could the authors comment more on how the bound in Theorem 2 is superior to VC dimension bound and whether conditions under which the bound is tight are realistic for standard compressed vision networks. Having weight matrices to be close to rank 1 seems unrealistic.I would like to see some sort of empirical evidence if the authors believe that this is the case. And for larger ranks, the bound seems to be close to VC bound.

In general, I found the notation a bit hard to follow and had to constantly be looking through the paper to find the definitions of various quantities. Having three different r’s, multiple mu’s with dots, bars, stars, etc., was definitely confusing and required extra attention to detail.

Other minor comments:

In section 2, marginal distributions over x and y are introduced. Are those used in the main text?
Is that a definition of \mu with the dot on top in assumption 5, or is this mu with the dot defined earlier? Using notation := would make it clearer whether the quantity is being defined.
In Section 3, “The main difference from the…” paragraph, there is \Psi(\dot r) used. Where is that defined?
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper provides generalization bound based on the compression arguments. A key contribution is that instead of bounding the
population risk for the compressed model, this paper manages to give bounds on the non-compressed network following a unified analysis framework. Also, this paper applies the unified framework to low-rank assumption on weigh matrices and covariance matrices.

Overall, I believe this paper should be accepted because of its contribution to our understanding of generalization theory. The central contribution here is using localized Rademacher complexity to bound the $L_2$ norm between original network and compressed network. However, I think there are several issues unclear and in need of clarification.

One thing I hope the authors could clarify is the novelty in the proof of Theorem 1, because it seems the techniques used here such as entropy integral and peeling are all well-known. It would be better if the authors could give a comparison between this paper and papers with similar techniques.

Another question is, in the statement of Theorem 1, the term $\sqrt{M \frac{2t}{n}}$ is marked as part of 'main term' and the term $C \dot r \sqrt{\frac{t}{n}}$ is marked as part of 'fast term'. I hope the authors could give a more detailed explanation of why $\dot r$ could be seen as a faster term than a constant, which seems not sensible to me. 

Also, I hope the authors could explain why $\Phi(\sqrt{2(\hat r ^2 + r ^2 _*)})$ is a 'faster term', because it seems this term is not faster than $\sqrt{\frac{1}{n}}$.

The questions above essentially concern how sharp this general bound could be. I would appreciate it if the authors could give a thorough response to questions mentioned above. This can help me achieve a better understanding and a more precise evaluation on this paper.
review_title: Official Blind Review #2

Meta-review: This paper has a few interesting contributions: (a) a bound for un-compressed networks in terms of the compressed network (this is in contrast to some prior work, which only gives bounds on the compressed network); (b) the use of local Rademacher complexity to try to squeeze as much as possible out of the connection; (c) an application of the bound to a specific interesting favorable condition, namely low-rank structure.

As a minor suggestion, I'd like to recommend that the authors go ahead and use their allowed 10th body page!
Decision: Accept (Spotlight)