Generalization of deep networks has been of great interest in recent years, resulting in a number of theoretically and empirically motivated complexity measures. However, most papers proposing such measures only study a small set of models, leaving open the question of whether the conclusion drawn from those experiments would remain valid in other settings. We present the first large scale study of generalization bounds and measures in deep networks. We train over two thousand convolutional networks with systematic changes in commonly used hyperparameters. Hoping to uncover potentially causal relationships between each measure and generalization, we analyze carefully controlled experiments and show surprising failures of some measures as well as promising measures for further research.
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 ?