Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: The paper addresses the well-known generalization problem for deep networks: why do these models successfully generalize even though they contain more parameters than the size of the training set? Recent works on this problem have proposed various measures of model complexity (that is, different from the number of parameters) with the claim that they (at least partially) capture the "true" capacity of deep networks in order to answer this question. The authors report the results of a large-scale, systematic study of the empirical effect of these complexity measures on the observed generalization behavior of deep networks.

The empirical study of generalization behavior is inherently tricky, and the authors make a non-trivial contribution just by designing an experiment that can convincingly address this question. The authors give careful attention to various potential obstacles related to experimental design and statistical validity. 

The results of the authors' experiments are highly valuable to the research community. I recommend to accept.

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

Technical comments for the authors: 
-Please rewrite or elaborate on the first two paragraphs of section 6 for clarity.

-It seems to make little sense to consider norm-based complexity measures that are not margin-normalized (or at least normalized in some other way). Please include a margin-normalized version of each such measure in Table 5; certain key quantities (e.g. "frob-distance") have no corresponding margin-normalized entry.

-The quantity "sum-of-frob/margin" is certainly a quantity of interest and it should be included in table 2 and possibly merits some discussion.

-I disagree somewhat with the discussion of the spectral bound in section 7. In particular, I would not agree that the poor performance of "spec-orig" is surprising, because it contains an astronomically-sized "proof artifact" (as you call it). Namely, in this bound and in similar norm-based bounds, the term which is the product of the matrices in the network is (heuristically) unnecessary; in particular it (heuristically) ought to be able to be replaced with the network's "average-case Lipschitz constant" (this is one of the issues which Arora et al. 2018 attempted to address; unfortunately formalizing an adequate notion of "average-case Lipschitz constant" can be quite cumbersome). This superfluous product of matrix norms is of course highly correlated with model size, so it is not surprising that the quantity would have a sizable negative correlation with generalization. The quantity I would consider to be the "main term" is the quantity "fro/spec". Furthermore, the fact that this quantity (which appears in both Bartlett et al. and Arora et al.) performs somewhat worse than simply "sum-of-fro" is fairly interesting and possibly merits some discussion.

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The paper aims at providing a better understanding of generalization for Deep Learning models. The idea is really interesting for the ML community as, despite their broad use, the astounding property of deep neural networks to generalize that well is still not well understood.
The idea is not to show new theoretical bounds for generalization gaps but stress the results of an empirical study comparing the already existing measures. The authors choose 7 common hyperparameters related to optimization and analyze the correlation between the generalization  gaps effectively observed and the ones predicted by different measures (VC dim, cross-entropy, canonical ordering …).
The writing of the paper is clear and easily understandable. Besides, I believe that the study is relevant to ICLR conference.

However, I believe the level of the paper is marginally below the threshold of acceptance and therefore would recommend to reject it.

The paper is solely empirical but I believe that the empirical section is a bit weak, or at least some important points remain unclear. If I appreciate the extent efforts made in trying to evaluate different measures of generalization gaps, I do not believe that the findings are conclusive enough.

1) First, all this empirical result are based on one-dataset (CIFAR-10) only thus limiting the impact of the study. Indeed, a given measure might very correlate with generalization gap on this specific dataset but not on others.

2) Specifically, we see that on this specific dataset, all training accuracies are already quite good (cf : Figure 1, distribution of the training losses). Consequently, authors are more correlating the chosen measures with the test error rather than with the generalization gaps. On other more complicated datasets where the training loss is higher, the VC dimension might consequently have way better results.
Similarly, in Section 6, the authors say that the results «confirm the widely known empirical observation that over-parametrization improves generalization in deep learning. » In this specific case, no reference was given to support the claim. I would agree with the claim « over-paramatrization improves test accuracy (reduces test error) » but the link between over-parametrization and generalization is less clear.  

3) In Section 4, the authors say « drawing conclusion from changing one or two hyper-parameters » can be a pitfall as « the hyper-parameter could be the true cause of both change in the measure and change in the generalization ». I totally agree with the authors here. Consequently, I do not understand why the correlations were measured by only changing one hyper-parameter at a time instead of sampling randomly in Theta.

4) It is still not clear to me how the authors explain why some measures are more correlated with generalization gaps than others. Are some bounds tighter than others ? This empirical study was only applied to convolutional neural networks and consequently one may wonder that for example the VC dim bounds computed in the specific case of neural networks are too loose. However, this measure could be efficient for type of models.


I would like the authors to clear the following points :
- How do you ensure that the empirical study clearly correlated measures predictions with generalization gaps and not simply with test errors (or accuracies) ? (point 2)
- Could you please also answer Point 4 ?
- Finally, how would you explain the fact that the canonical order performs so well compare to many other measures and that it is a really tough-to-beat baseline ?


review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: This work all starts with the observation, made by many, that deeper (>=2 layers) networks generalise differently to the simple models we used to use, and that the good old bias-variance trade-off doesn't really apply.

This paper is a natural successor to a long line of papers, most recently Zhang at el (best paper at ICLR 2017, though some like Tom Dietterich weren't impressed), Neyshabur et al (NIPS 2017) and Jiang et al (ICLR 2019).  Whereas Jiang etal and Neyshabur etal had a few metrics, a few data sets and a few models, this paper instead has loads and loads of metrics and just one data set and one model class.  You have, however, been clearly strongly influenced by the prior work and attempted to fix what you saw as their empirical shortcomings.

I agree with the choice of stopping according to cross entropy.  One thing not done in Section 5 is a discussion of
variation:  choice of initialisation and the impact of stochasticity in the optimisation. 

Appendix C lists your copious metrics.  I am not deeply embedded in the theory, though I understand the major concepts. I was impressed with the coverage and variations done.  I expect Appendix C may raise copius matching arguments amongst the theory community, with some valid and some invalid complaints.  For me, I wonder why you make P & Q have the same variance (see before equation 43 in App. C).  You credit Neyshabur, but I'm left wondering.

So, the short version of my review is that I believe this paper is imcomplete, in that not enough different data sets were investigated.  With this, I fear you could well be uncovering perculiarities pertinant to CIFAR-10 and the ease of getting near perfect training error on it.  However, I am impressed with what you have done, and think you made a great starting point.  So I say, publish and let the real battle begin.  Let the theoreticians argue (about metrics) and the practicioners implement (with more data), and let's see what happens.  You have laid a great ground work for folks, bulding on the earlier work.  Perhaps Google can be encouraged to support this in that Jiang's paper is a precursor.

Interesting observations in Appendix A.1, as are some of the discussions in Sections 7, 8, 9.

Given the best metric seems to be sharpness, which exceeds PAC-Bayesian, shouldn't you relate this to grad noise (metrics 61 and 62) which measure the flatness.  Are these related?  Note, also, a Bayesian always wants broad peaks for their parameter surfaces.

MINOR ISSUES: (1) some repeated words: "an an", "the the" (2) some strange grammar "each canonical ordering that only be predictive for its own category", "VC-dimension bounds or and parameter counting", "possible to find to calculate", "in the Equation equation C.3 (3)" Generalisation gap is poorly introduced.  Its officially defined in footnote 4 but used way earlier!  Put in the main text:  its an important clarification. (4) Table 1 legend should mention the "numerical results" are for equations 2, 4 and 5.  (5)  Somewhere you need to mention that numbers in red in tables refer to equations in appendix C.

review_title: Official Blind Review #1

Meta-review: This paper provides a valuable survey, summary, and empirical comparison of many generalization quantities from throughout the literature. It is comprehensive, thorough, and will be useful to a variety of researchers (both theoretical and applied).
Decision: Accept (Poster)