Fantastic Generalization Measures and Where to Find Them
Authors: Yiding Jiang*
Behnam Neyshabur*
Hossein Mobahi
Dilip Krishnan
Samy Bengio
Venue:  (2020)
Keywords: Generalization
correlation
experiments

Abstract: Generalization of deep networks has been intensely researched in recent years, resulting in a number of theoretical bounds and empirically motivated measures. However, most papers proposing such measures only study a small set of models, leaving open the question of whether these measures are truly useful in practice. We present the first large scale study of generalization bounds and measures in deep networks. We train over two thousand CIFAR-10 networks with systematic changes in important hyper-parameters. We attempt to uncover potential causal relationships between each measure and generalization, by using rank correlation coefficient and its modified forms. We analyze the results and show that some of the studied measures are very promising for further research.

Published as a conference paper at ICLR 2020
FANTASTIC GENERALIZATION MEASURES AND WHERE TO FIND THEM
Yiding Jiang", Behnam Neyshabur', Hossein Mobahi, Dilip Krishnan, Samy Bengio Google Research (ydjiang, neyshabur, hmobahi, dilipkay, penlippka,,beniio. /tw.b/egggggggggglg..ggggggoggee @google com
ABSTRACT
Generalization of deep networks has lately been of great interest, resulting in a number of theoretically and empirically motivated complexity measures. How- ever, most papers proposing such measures study only a small set models, leav- ing 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 gen- eralization in deep networks. We investigate more then 40 complexity measures taken from both theoretical bounds and empirical studies. We train over 10,000 convolutional networks by systematically varying commonly used hyperparame- ters. 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.
INTRODUCTION
Deep neural networks have seen tremendous success in number of applications, but why (and how well) these models generalize is still a mystery (Neyshabur et al., 2014; Zhang et al., 2016; Recht et al., 2019). It is crucial to better understand the reason behind the generalization of modern deep learning models; such an understanding has multiple benefits, including providing guarantees for safety-critical scenarios and the design of better models. A number of papers have attempted to understand the generalization phenomenon in deep models from a theoretical perspective e.g. (Neyshabur al., 20; Bartlett et al., 2017; Neyshabur al., 201 8a; Golowich et al., 2017; Arora et al., 2018; Nagarajan and Kolter, 2019 1a; Wei and Ma, 2019a; Long and Sedghi, 2019). The most direct and principled approach for studying generalization in deep learning is to prove a generaliza- tion bound; typically an upper bound on the test error based on some quantity that can be calculated on the training set. Unfortunately, finding tight bounds has proven be an arduous undertaking. While encouragingly Dziugaite and Roy (2017) showed that PAC-Bayesian bounds can be optimized to achieve reasonably tight generalization bound, current bounds are still not tight enough to ac- curately capture the generalization behavior. Others have proposed more direct empirical ways to characterize generalization of deep networks without attempting to deriving bounds (Keskar et al., 2016; Liang et al., 2017). However, as pointed by Dziugaite and Roy (2017), empirical correlation does not necessarily translate to a casual relationship between a measure and generalization.
A core component in (theoretical or empirical) analysis of generalization is the notion of complexity measure; a quantity that monotonically relates to some aspect of generalization. More specifically, lower complexity should often imply smaller generalization gap. A complexity measure may depend on the properties of the trained model, optimizer, and possibly training data, but should not have ac- cess to validation set. Theoretically motivated complexity measures such as VC-dimension, norm of parameters, etc., are often featured as the major components of generalization bounds, where the monotonic relationship between the measures and generalization mathematically established. In contrast, empirically motivated complexity measures such as sharpness (Keskar et al., 2016) are justified by experimentation and observation. In this work, we do not need distinguish between theoretically vs empirically motivated measures, and simply refer to both as complexity measures.
"Contributed equally.
Work done as part of the Google AI Residency Program.

---

Published as a conference paper at ICLR 2020
Despite the prominent role of complexity measures in studying generalization, the empirical evalu- ation of these measures is usually limited to a few models, often on toy problems. A measure can only be considered reliable as predictor of generalization gap if it is tested extensively many models at a realistic problem size. To this end, we carefully selected a wide range of complexity measures from the literature. Some of the measures are motivated by generalization bounds such as those related to VC-dimension, norm or margin based bounds, and PAC-Bayesian bounds. We further selected a variety of empirical measures such as sharpness (Keskar et al., 2016), Risher-Rao norm (Liang et al., 2017) and path norms (Neyshabur et al., 2017).
In this study, we trained more than 10,000 models over two image classification datasets, namely, CIFAR-10 (Krizhevsky et al., 2014) and Street View House Numbers (SVHN) Netzer et al. (2011). In order to create wide range of generalization behaviors, we carefully varied hyperparameters that are believed to influence generalization. We also selected multiple optimization algorithms and looked at different stopping criteria for training convergence. Details of all our measures and hyperparameter selections are provided in Appendix D. Training under all combination of hyperpa- rameters and optimization resulted in a large pool of models. For any such model, we considered 40 complexity measures. The key findings that arise from our large scale study summarized below:
1. It is easy for some complexity measures capture spurious correlations that do not reflect causal insights about generalization; to mitigate that we propose a more rigorous method to study them.
2. Many norm- based measures not only perform poorly, but negatively correlate with generalization specifically when the optimization procedure injects some stochasticity. In particular, the gener- alization bound based on the product of spectral norms of the layers (similar to that of Bartlett et al. (2017)) has very strong negative correlation with generalization.
3. Sharpness- based measures like PAC-Bayesian bounds (McAllester, 1999) and the measure pro- posed by Keskar et al. (2016) perform best and seem promising candidates for further research.
4. Measures related to the optimization procedures such as the gradient noise and the speed of the optimization can be predictive of generalization.
Our findings on the relative success of sharpness- based and optimization based complexity measures for predicting the generalization gap can provoke further study of these measures.
1.1 RELATED WORK
The theoretically motivated measures that we consider in this work belong to a few different families: PAC-Bayes (MeAllester, 1999; Dziugaite and Roy, 2017; Neyshabur et al., 2017); VC-dimension (Vapnik and Chervonenkis, 1971): and norm-based bounds (Neyshabur et al., 2015b; Bartlett et al., 2017: Neyshabur et al., 2018a). The empirically motivated measures from prior literature that we consider are based sharpness measure (Keskar et al., 2016); Fisher-Rao measure (Liang et al., 2017); distance trained weights from initialization (Nagarajan and Kolter, 2019b) and path norm (Neyshabur et al., 2015a). Finally, we consider some optimization based measures based on the speed of the optimization algorithm as motivated by the work of (Hardt et al., 2015) and (Wilson al., 2017a), and the magnitude of the gradient noise as motivated by the work of (Chaudhari and Soatto, 2018) and (Smith and Le, 2017).
A few papers have explored large scale study of generalization in deep networks. Neyshabur al. (2017) perform a small scale study of the generalization of PAC-Bayes, sharpness and few different norms, and the generalization analysis is restricted to correlation. Jiang al. (2018) studied the role of margin as a predictor of the generalization gap. However, they used a significantly more restricted set of models (c.g. no depth variations), the experiments were not controlled for potential undesired correlation (c.g. the models can have vastly different training error) and some measures contained parameters that must be learned from the set of models. Novak et al. (2018) conducted large scale study of neural networks but they only looked at correlation of a few measures to generalization. In contrast, we study thousands of models, and perform controlled experiments to avoid undesired artificial correlations. Some of our analysis techniques are inspired by Neal (2019) who proposed the idea of studying generalization in deep models via causal graphs, but did not provide any details or empirical results connected to that idea. Our work focuses measures that can be computed on a single model and compares a large number of bounds and measures across a much wider range of models in carefully controlled fashion.
2

---

Published as a conference paper at ICLR 2020
2 GENERALIZATION: WHAT IS THE GOAL AND HOW TO EVALUATE?
Generalization is arguably the most fundamental and yet mysterious aspect of machine learning. The core question in generalization is what causes the triplet of a model, optimization algorithm, and data properties', to generalize well beyond the training set. There are many hypotheses concerning this question, but what is the right way to compare these hypotheses? The core component of each hypothesis is complexity measure that monotonically relates some aspect of generalization. Here we briefly discuss some potential approaches to compare different complexity measures:
Tightness of Generalization Bounds. Proving generalization bounds very useful to establish the causal relationship between complexity measure and the generalization error. However, almost all existing bounds are vacuous on current deep learning tasks (combination of models and datasets), and therefore, one cannot rely on their proof as evidence on the causal relationship between a complexity measure and generalization currently?.
Regularizing the Complexity Mcasure. One may evaluate a complexity measure by adding it as a regularizer and directly optimizing it, but this could fail due to two reasons. The complexity measure could change the loss landscape in non-trivial ways and make the optimization more difficult. In such cases, if the optimization fails optimize the measure, no conclusion can be made about the causality. Another, and perhaps more critical, problem is the existence of implicit regularization of the optimization algorithm. This makes it hard to run a controlled experiment since one cannot simply turn off the implicit regularization; therefore, if optimizing a measure does not improve generalization it could be simply due to the fact that it is regularizing the model in the same way the optimization is regularizing it implicitly.
Correlation with Generalization Evaluating measures based on correlation with generalization is very useful but it can also provide a misleading picture. To check the correlation, we should vary architectures and optimization algorithms to produce set of models. If the set is generated in an artificial way and is not representative of the typical setting, the conclusions might be deceiving and might not generalize typical cases. One such example is training with different portions of random labels which artificially changes the dataset. Another pitfall is drawing conclusion from changing one or two hyper-parameters (e.g changing the width or batch-size and checking if measure would correlate with generalization). In these cases, the the true cause of both change in the measure and change in the generalization, but the measure itself has no causal relationship with generalization. Therefore, one needs to be very careful with experimental design to avoid unwanted correlations.
could be
In this work we focus on the third approach. While acknowledging all limitations of a correlation analysis, we try to improve the procedure and capture some of the causal effects much as possible through careful design of controlled experiments. Further, to evaluate the effectiveness of complex- ity measures accurately as possible, we analyze them over sufficiently trained models with wide range of variations in hyperparameters. For practical reasons, these models must reach convergence within reasonable time budget. Details of the notations used are outlined in Appendix A.
2.1 TRAINING MODELS ACROSS HYPERPARAMETER SPACE
In order create models with different generalization behavior, we consider various hyperaaraeeter types, which are known or believed to influence generalization (e.g. batch size, dropout rate, etc.). Formally, denote each hyperparameter by 6; taking values from the set θ, for i 1,..., n and n denoting the total number of hyperparameter types?. For each value of hyperparameters 0 e (0,, .2.....,,,, .,)) E O, where θ A O x O2 x.. x On, we train the architecture until the training loss (cross-entropy choice of the stopping criterion. Doing this for each syper-paramedt configuration @ E O, we obtain a total of [+] models. The space θ reflects our prior knowledge about a reasonable hyperparameter
value) reaches given threshold See the Appendix C.2 for discussion on the
For examplc, it is expected that images share certain structures that allows some models (which leverage these biases) to generalize.
2Se Dziugaite and Roy (2017) for an example non-vacuous generalization bound and related discussions. In our analysis we = 7 hyperparameters: batch size, dropout probability, learning rate, network depth, weight decay coefficient, network width, optimizer.
3

---

Published as a conference paper at ICLR 2020
space, both in terms of their types and values. Regarding the latter, one could, for example, create O, by grid sampling of a reasonable number of points within a reasonable range of values for 0,.
2.2
EVALUATION CRITERIA
2.2.1 KENDALL'S RANK- CON-CCORELLATON COEFFICIENT
One way to evaluate the models resulted by training with hyperparameters the set θ, their associated generalization gap {g(0) 1 E )), and their respective values of the measure (u(0) 0 E }) our goal is to analyze how consistent a measure (e.g. le norm of network weights) is with the empirically observed generalization, To this end, we construct set T. where each element of the set is associated with one of the trained models. Each element has the form of pair: complexity measure μ versus generalization gap g-
of complexity measure μ is through ranking. Given set of
T E Usee { (n(O), (()))
An ideal complexity measure must be such that, for any pair of trained models, if (())) p(0)),
then so is g(0)) > g(02). We use Kendall's rank coefficient (Kendall, 1938) to capture to what degree such consistency holds among the elements Tf
T(T)
Σ
E
sign(m u2) sign(gi 922
T (A191))T (p2.92)
Note that T can vary between 1 and -1 and attains these extreme values at perfect agreement (two rankings are the same) and perfect disagreement (one ranking is the reverse of the other) respectively. If complexity and generalization are independent, the coefficient becomes zero.
2.2.2 GRANULATED KENDALL'S COEFFICIENT
While Kendall's s correlation coefficient is an effective tool widely used capture relationship be- tween 2 rankings of a set of objects, we found that certain measures can achieve high T values in trivial manner i.e. the measure may strongly correlate with the generalization performance without necessarily capturing the cause of generalization. We will analyze this phenomenon in greater details subsequent sections. To mitigate the effect of spurious correlations, we propose a new quantity for reflecting the correlation between measures and generalization based more controlled setting,
None of the existing complexity measures is perfect. However, they might have different sensitivity and accuracy w.r.t. different hyperparameters. For example, sha rpriess may do better than other measures when only a certain hyperparameter (say batch s size) changes. To understand such details, in addition to (TT), we compute T for consistency within each hyperparameter axis O, and then average the coefficient across the remaining hyperparameter space. Formally, we define:
_ 10, x m,
1 x O,+1 X x x
(3)
A
1 Σ mi
.
r( co (1(0). Σ E...
Σ
Σ
(4)
PIER
1E6; 11111
66,
The inner reflects the ranking correlation between the generalization and the complexity measure for a small group of models where the only difference among them is the variation along a single hyperparameter 0;. We then average the value across all combinations of the other hyperparameter axis. Intuitively, if measure is good at predicting the effect of hyperparameter 0, over the model distribution, then its corresponding 1h should be high. Finally, we compute the average th of average across all hyperparamter axes, and name W:
V 2
(5)
If measure achieves a high V on a given hyperparameter distribution θ, then should achieve high individual sb across all hyperparameters. A complexity measure that excels at predicting changes in a single hyperparameter (high thx) but fails at the other hyperparameters (low bo for all j * i) will not do well V. On the other hand, if the measure performs well on V, it means that the measure can reliably rank the generalization for each of the
changes.
A thought experiment to illustrate why V captures a better causal nature of the generalization than Kendall's 7 is as follows. Suppose there exists a measure that perfectly captures the depth of the network while producing random prediction if networks have the same depth, this measure would do reasonably well in terms r but much worse in terms of V. In the experiments we consider in the following sections, found that such measure would achieve overall 0.362 but v 0.11.
4

---

Published as a conference paper at ICLR 2020
2.2.3 CONDITIONAL INDEPENDENCE TEST: TOWARDS CAPTURING THE CAUSAL RELATIONSHIPS
Relying on correlation is intuitive but perhaps unsatisfactory. In our experiments, we change sev- eral hyper-parameters and assess the correlation between complexity measure and generalization; however, changing the hyper-parameters can also be seen as interventions or randomized tests since they are chosen independently from any other variables, and cover causal structures. Specifically, we rely on the conditional independent test which measures the conditional mutual information between random variables. Details are outlined in Appendix B.
use this observation un-
3 GENERATING A FAMILY OF TRAINED MODELS
We chose 7 common hyperparameter types related to optimization and architecture design, with 3 choices for each hyperparameter. We generated 3 2187 models that trained the CIFAR- 10 dataset. We analyze these 2187 models in the subsequent sections; however, additional results including repeating the experiments times as well as training the models using SVHN dataset are presented in Appendix Section C.5. These additional experiments, which add to more than 10,000 trained models, suggest that the observations we make here are robust to randomness, and, more importantly, captures general behaviors of image classification tasks.
We trained these models to convergence. Convergence criterion is chosen as when cross-entropy loss reaches the value 0.01. Any model that was not able to achieve this value of cross-entropy was discarded from further analysis. The latter different from the DEMOGEN dataset (Jiang et al., not trained to the same cross-entropy. Putting the stopping criterion
2018) where the models on the training loss rather than the number of epochs is crucial since otherwise one can simply use cross-entropy loss value to predict generalization. Please see Appendix Section C.2 for discussion on the choice of stopping criterion.
To construct pool of trained models with vastly different generalization behaviors while being able to fit the training set, we covered a wide range of hyperparameters for training. Our base model is inspired by the Network-in-Network (Gao et al., 2011). The hyperparameter categories we test on are: weight decay coefficient (wei decay), width of the layer (wi (width), mini-batch size (bat ch size), learning rate (learning rate), dropout probability (dropout), depth of the architecture (depth) h) and the choice of the optimization algorithms (opt poptimizer. We select choices for each hyperparameter (i.e. |O, = 3). Please refer to Appendix C.3 for the details on the models, and Appendix C.1 for the reasoning behind the design choices.
Figure shows summarizing statistics of the models in this study. On the left we show the number of models that achieve above 99% training accuracy for every individual hyperparameter choice. Since we have 37 2187 models in total, the maximum number of models for each hyperparameter type is 3-1 718; the majority of the models in our pool were able to reach this threshold. In the middle we show the distribution of the cross cross-entrond entropy value over the entire training set. While we want the models to be at exactly 0.01 cross-entropy, in practice it is computationally prohibitive to constantly evaluate the loss over the entire training set; further, to enable reasonable temporal granularity, we estimate the training loss with 100 randomly sampled minibatch. These computational compromises result in long-tailed distribution of training loss centered at 0.01. As shown in Table 1, even such minuscule range of cross-entropy difference could lead positive correlation with generalization, highlighting the importance of training loss as stopping criterion. On the right, we show the distribution of the generalization gap. Notice while all the models' training accuracy above 0.99, there is wide range of generalization gap, which is ideal for evaluating complexity measures.
'All the experiments reported in the main text have been repeated for 5 times. The mean (Table 9) is consistent with those presented in the main text and standard deviation (Table 10) is very small compared the magnitude of the mean for all measures. Further, we also repeat the experiments once on the SVHN dataset (Table 7), whose results are also consistent with the observations made on CIFAR-10. In our analysis, less than percent of the models do reach this threshold.
5

---

Published as a conference paper at ICLR 2020
# models with training accuracy > 0.99
140
Qistripution Trajning Loss
Distrjbution of Genneaaization Gap,
003
120
Hparam Choice
With
130
dropose
dripaie
cegth
9600
100 200
300
4000
500
600
700
-201
ess
007
010
8.00 642
# models
Entropy
Gonerelization Gap
Figure I: Left: Number of models with training accuracy> 99% for each hyperparameter type. Mid.: Distri-
bution of training cross eross-entropy (that of training error in Fig. 4). Right: Distribution of generalization gap.
4 PERFORMANCE OF COMPLEXITY MEASURES
4.1 BASELINE COMPLEXITY MEASURES
The first baseline we consider is performance of a measure against an oracle who observes the noisy generalization gap. Concretely, we rank the models based on the true generalization gap with some additive noise. The resulting ranking correlation indicates how close the performances of all models are. As the scale the noise approaches O, the oracle's ' prediction tends towards perfect (i.e. 1). This baseline accounts for the potential noise in the training procedure and gives an anchor for gauging the difficulty of each hyperparameter type. Formally, given an arbitrary set of define e-oracle to be the expectation of or V where the measure is {g(() ()) + (0,, (0, e) 0 @*)-
O',
We report the performance of the noisy oracle in Table for e E {0.02, 0.05). For additional choices of please refer to Appendix C.5.
Second, to understand how our hyperparameter choices affect the optimization, we give each hy- perparameter type canonical order which is believed to have correlation with generalization (e.g. larger learning rate generalizes better) and measure their т. The exact canonical ordering can be found in Appendix C.4. Note that unlike other measures, each canonical ordering can only predict generalization for its own hyperparameter type, since its corresponding hyperparameter remains fixed in any other hyperparameter type; consequently, each column actually represents different measure for the canonical measure row. Assuming that each canonical measure is uninformative of any other canonical measures, the v criterion for each canonical measure is & of its performance on the corresponding hy perparaametrr type.
banch size
dropout
learning
depth
optimizer
weight
width
Tale
dece
overall
+
ve
8:300
0,000
-0.909
0.000
0.000
-0.171
-0.251
params 20
0.000
0.000
(1.000
-0.909
0.000
0.00
-0.171
-0.175
-0.154
1/ty (22)
0.312
40.593
0.254
0.758
0.225
40.211
0.125
0.124
0.121
COFE
entropy
0.251
0.632
0.220
40.157
0.104
0.148
0.124
cp06s ontropy
0.440
0.390
0.149
0232
0.000
0.149
0.147
oracic U.02
0,300
0.057
0.330
0.717
0.314
0.383
0.300
0.714
0,457
oracle 0.05
0.172
0.375
0,3015
0.384
0.165
0.184
0.204
0.438
0.256
cononical
0.652
.0.55
NA
S 2
min V [S]
vc dim
B.422
01064
0,1518
0.0199
0.0422
0.0443
0.0227
0.00
0.001
param
0,0202
0.0278
0.0250
0.0044
0.0088
0.0266
0.0179
0.00
0.00
//y
B:0108
0.0788
0.0133
0.8750
0.005
0.1199
0.083
0.0051
0.005
M1
entropy
0:0120
0.656
0.0113
0.0086
0.0120
0.0155
0.0125
0.0065
0.00KS
cross-entropy
0.0233
0.0800
0.0118
0.0075
0.0159
00119
0.0833
0,0040
0,0940
U.D02
0,4077
0.3557
0.1637
oracle 0.05
0.1475
0.1167
0.1369
0.1241
0.1115
0.3469
0.3535
0,0503
0.0503
mindom
0.0005
0.0022
0.0005
0,0002
0.0033
0.0066
0.0009
0.0004
0.0001
Table 1: Numerical Results for Baselines and Oracular Complexity Measures
We next look at one of the most well-known complexity measures in machine learning; the VC- Dimension. Bartlett et al. (2019) proves bounds on the VC dimension of piece-wise linear networks with potential weight sharing. In Appendix D. we extend their result to include pooling layers and multi-class classification. We report two complexity measures based on VC-dimension bounds and parameter counting. These measures could be predictive merely when the architecture changes, which happens only in depth and wi dth hyperparameter types. We observe that, with both types,

---

Published as a conference paper at ICLR 2020
VC-dimension well as the number of parameters are negatively correlated with generalization gap which confirms the widely known empirical observation that overparanetrization improves gener- alization in deep learning.
Finally, we report the measures that only look at the output of the network. In particular, we look at the cross-entropy loss, margin 7, and the entropy of the output. These three measures closely related to each other. In fact, the outcomes in Table reflects this similarity. These results confirm the general understanding that larger margin, lower cross-entropy and higher entropy would lead to better generalization. Please see Appendix D.1.1 for definitions and more discussions on these measures.
4.2
SURPRISING FAILURE OF SOME (NORM & MARGIN)-BASEL MEASURES
In machine learning. a long standing measure for quantifying the complexity of a function, and therefore generalization, is using some norm of the given function. Indeed, directly optimizing some of the norms can lead to improved generalization. For example, &2 regularization on the parameters of model can be seen as imposing an isotropic Gaussian prior over the parameters in maximum a posteriori estimation. We choose several representative norms (or measures hased on norms) and compute our correlation coefficient between the measures and the generalization gap of the model.
We study the following measures and their variants (Table 2): spectral bound, Frobenius distance from initialization, lz Frobenius norm of the parameters, Fisher-Rao metric and path norm.
batch
dropout
leaming
depth
uptimizer
weight
width
overall
docay
Frobh distance 40
-0.317
.0.833
-0.718
0.536
-0.314
.0.669
-0,341
Spectral urig 26
-0.262
-0.762
-0.665
-0,908
-0,131
-0.073
-0.240
-0.537
-0,434
Pammeter nomn 42
0.236
-0.516
0.174
0.330
0.187
0.124
-0.170
0.073
0.052
Path
0.153
0.311
Fisher Rau
0.396
0.147
0.340
-0.553
0.120
0.551
0.177
0.078
0.154
oracle 0.02
0.350
0.657
0.336
0.717
0.314
0.365
0,360
0.114
0
[8]
V
Frob distance
0,162
0,0530
0.019
0.1559
0.0902
0.0379
0.0506
0.0128
0.0128
Spectral ong
0,2197
0.2815
0.2045
0.0808
0.2190
0.2285
0.2181
0.8359
0,0359
Parumeter
0.0009
0.0197
0.0066
0.0155
0.0054
0.00899
0.0167
0.0017
0.0038
Fath
0.1027
0.0315
0.1056
0.1160
0.0240
0.0240
Fisher Rao
0.0000
0.0072
0.0020
0,0713
0.0057
0.0014
0.0071
0.0018
0.0013
oracle 0,05
0.1475
0,1167
0.
0.1211
0,1515
0.1969
0.1535
03503
0,0500
Table 2: Numerical Results for Selected (Norm & Margin)-Basee Complexity Measures
Spectral bound:
The most surprising observation here that the spectral complexity is strongly negatively correlated with generalization, and negatively correlated with changes within every hy- perparameter type. Most notably, it has strong negative correlation with the depth of the network, which may suggest that the largest singular values not sufficient capture the capacity of the model. To better understand the reason behind this observation, we investigate using different com- ponents of the spectral complexity the measure. An interesting observation that the Frobe- nius distance to initialization is negatively correlated, but the Frobenius norm of the parameters is slightly positively correlated with generalization, which contradicts some theories suggesting solu- tions closer to initialization should generalize better. A tempting hypothesis is that weight decay favors solution closer to the origin, but we did an ablation study on only models with 0 weight decay and found that the distance from initialization still correlates negatively with generalization.
These observations correspond to choosing different reference matrices W for the bound: the distance corresponds to using the initialization as the reference matrices while the Frobenius norm of the parameters corresponds to using the origin as the reference. Since the Frobenius norm of the parameters shows better correlation, we use zero reference matrices in the spectral bound. This improved both т and V, albeit still negative. In addition, we extensively investigate the effect of different terms of the Spectral bound to isolate the effect; however, the results do not improve. These experiments can be found in the Appendix D.2.
Path norm: While path-norm is proper norm in the function space but not in parameter space, types and achieves
observe that it is positively correlated with generalization in all comparable (0.373) and V (0.311).
Ras metric: The Fisher-Rao metric is lower bound (Liang et al., 2017) on the path norm that has been recently shown to capture generalization. We observed that it overall shows worse
7

---

Published as a conference paper at ICLR 2020
correlation than the path norm; in particular, is negatively correlated with the depth of the network, which contrasts with path norm that properly captures the effect of depth on generalization. A more interesting observation is that the Fisher- Rao metric achieves positive Vp 0.154 but its T = 0.078 is essentially at chance. This may suggest that the metric can capture a single hyper-parameter change but is not able to capture the interactions between different hyperparameter types.
Effect of Randomness: dropout and batch size (first columns of Table 2) directly intro- duce randomness into the training dynamic. For batch size, we observed that the Frobenius dis- placement and spectral complexity both correlate negatively with the changes in batch size while the Frobenius norm of the parameters correlates positively with generalization. On the other hand, when changes happen to the magnitude dropout probability. we observed that all of the proper norms are negatively correlated with the generalization changes. Since increasing dropout usually reduces the generalization gap, this implies that increasing the dropout probability may be at least partially responsible for the growth in these norms. This is unexpected since increasing norm in principle implies higher model capacity which is usually more prone to overfitting.
The overall picture does not change much going from the ranking correlation to mutual information, with a notable exception where spectral complexity has the highest conditional mutual information compared to all the other measures. This is due to the fact that the conditional mutual information is agnostic to the direction of correlation, and in the ranking correlation, spectral complexity has the highest absolute correlation. While this view might seem contradictory to classical view as the spectral complexity is complexity measure which should be small to guarantee good generaliza- tion, it is nonetheless informative about the generalization of the model. Further, by inspecting the conditional mutual information for each hyperparameter, we find that the majority of spectral com- plexity's 's predictive power is due to its ability to capture the depth of the network, as the mutual information significantly lower if depth is already observed.
4.3 SUCCESS OF SHARPNESS- BASED MEASURES
A natural category of generalization measures is centered around the concept of "sharpness" of the local minima, capturing the sensitivity of the empirical risk (i.e. the loss over the entire training set) to perturbations in model parameters, Such notion of stability under perturbation is captured ele- gantly by the PAC-Bayesian framework (McAllester, 1999) which has provided promising insights for studying generalization of deep neural networks (Dziugaite and Roy, 2017; Neyshabur et al., 2017: 8a). In this sections, we investigate PAC-Bayesian generalization bounds and several of their variants which rely on different priors and different notions of sharpness (Table 3).
In order to evaluate a PAC-Bayesian bound, one needs to come up with a prior distribution over the parameters that is chosen in advance before observing the training set. Then, given any posterior distribution on the parameters which could depend on the training set, PPA-Baaesian bound (The- orem 46) states that the expected generalization error of the parameters generated from the posterior can be bounded by the KL-divergence of the prior and posterior. The posterior distribution can be seen adding perturbation generalization bounds, it is possible to calculate non-vacuous PAC-Bayesian bounds by optimiz- ing the bound over large set of Gaussian posteriors. Neyshabur al. (2017) demonstrates that when prior and posterior are isotropic Gaussian distributions, then PAC-Bayesian bounds are good measure of generalization on small scale experiments; see Eq (47).
final parameters. Dziugaite and Roy (2017) shows contrary to other
PAC-Bayesian framework captures sharpness in the expected sense since we add randomly gener- ated perturbations to the parameters. Another possible notion of sharpness is the worst-case sharp- ness where we search for the direction that changes the loss the most. This is motivated by (Keskar et al., 2016) where they observe that this notion would correlate with generalization in the case of different batch sizes. We can use PAC-Bayesian framework to construct generalization bounds for this worst-case perturbations as well. We refer to this worst case bound as the sharpness bound in Eq (50). The main component in both PAC-Bayes and worst-case sharpness bounds is the ratio of norm of parameters to the magnitude of the perturbation, where the magnitude is chosen to be the largest number such that the training error of the perturbed model is at most 0.1. While mathematically, the sharpness bound should always yield higher complexity than the PAC-Bayes bound, we observed that the former has higher correlation both in terms of and V. In addition. studied inverse of perturbation magnitude as a measure by removing the norm in the numerator to compare it with the bound, However, we did not observe significant difference.
8

---

Published as a conference paper at ICLR 2020
batch
dropout
learning
depth
optamizer
Weight
width
overall
decay
shirpness-ong
0.542
-0.359
0.715
0.816
0.297
0.391
0,135
0600
0,398
Pichayes-oigg 49
0.526
-0.076
0.705
0.546
0.341
0.564
-0.08
0299
0,760
starpuess mag 62
0.148
0,762
0,741
0,516
pachayes mag
0.90
00215
0.505
0.896
0.186
0.147
0,195
0,355
0,315
orack D.I2
M. M00
01357
0.336
0.374
0.358
0.300
DC487
4 [S]
shrppess-crig
0.0809
0.6588
0.1223
0.1071
0.1254
0.0224
pacbayes-orig
0.0620
0.1071
0.0392
0.0597
0.0645
0.0550
0.0977
0.0225
0.0225
sharpness mag
0.1640
0.2572
0.1424
0.1779
0.1562
0.1786
0.0544
0.0544
1/0¹ pucbayes mag
0.0884
0.1514
0.0813
0.0399
0.1004
0.1025
0,0986
0.0241
0.0241
oracle 0,05
0,1475
0.7
0.6
01241
0.1515
0.1469
0.1535
0,050
0,0505
Table 3: Numerical results for selected Sharpness-Based Measures; all the measure use the origin as the reference and mag refers to magnitude-aware version of the measure.
4.3.1 MAGNITUDE-AWARE PERTURBATION BOUNDS
Perturbing the parameters without taking their magnitude into account can cause many of them to switch signs. Therefore, one cannot apply large perturbations to the model without changing the loss significantly. One possible modification to improve the perturbations is to choose the pertur- bation magnitude based on the magnitude of the parameter. In that case, it is guaranteed that if the magnitude of perturbation is less than the magnitude of the parameter, then the sign of the parameter does not change. Following Keskar al. (2016), pick the magnitude of the perturbation with respect to the magnitude of parameters. We formalize this notion of importance based magnitude. Specifically, we derive two alternative generalization bounds for expected sharpness in Eq (55) and worst case sharpness in Eq (58) that include the magnitude of the parameters into the prior. For- mally, we design a' and o', respectively for sharpness and PAC-Bayes bounds, to be the ratio of parameter magnitude to the perturbation magnitude. While this change did not improve upon the original PAC-Bayesian measures, we observed that simply looking at 1/a' has surprising predictive power in terms of the generalization which surpasses the performance of oracle 0.02. This measure very close to what was originally suggested Keskar et al. (2016). Its effectiveness further corroborated by the conditional mutual information based metric, where we observed that 1/a' has the highest mutual information with generalization among all hyperparameters and also overall.
4.3.2 FINDING 0
In case of models with extremely small loss, the perturbed loss should roughly increase monotoni- cally with respect to the perturbation scale. Leveraging this observation, we design algorithms for computing the perturbation scale such that the first term on the RHS is as close to fixed value as possible for all models. In our experiments, we choose the deviation be 0.1 which translates to 10% training error. These search algorithms are paramount to compare measures between different models. We provide the detailed algorithms the Appendix E. To improve upon our algorithms, one could try computational approach similar to Dziugaite and Roy (2017) to obtain numerically better bound which may result in stronger correlation. However, due to practical computational constraints, could not do so for the large number of models consider.
4.4 POTENTIAL OF OPTIMIZATION BASED MEASURES
Optimization is indispensable component of deep learning. Numerous optimizers have been proposed for more stable training and faster convergence. How the optimization scheme and speed of optimization influence generalization of model has been topic of contention among the deep learning community (Merity et al., 2017; Hardt et al., 2015). We study 3 representative optimizers Moment um SGD, Adam, and RMSP rop with different initial learning rates in our experiments to thoroughly evaluate this phenomenon. We also consider other optimization related measures that believed to correlate with generalization. These include (Table 4):
1. Number of iterations required to reach cross-entropy equals 0.1
2. Number of iterations required going from cross-entropy equals 0.1 to cross-entropy equals 0.01
3. Variance of the gradients after only seeing the entire dataset once (1 epoch)
4. Variance of the gradients when the cross-entropy is approximately 0.01

---

Published as a conference paper at ICLR 2020
batch
drogout
learning
depch
optimizeer
Weight
width
overall
decay
step to 0.1
-0.664
-0.561
-0.255
0.440
-0000
-0.538
0.413
62264
-0279
step 0.1 to 0.01 64
-0.151
-0.089
-0.014
0.114
0.072
-0.046
-0.011
-0088
-0.016
grad noise epoch 65
0.071
0.378
0.376
0.517
0.121
0.21
0.087
0,000
0.098
and oracle 0.02
0.141
0.300
0.356
0.717
0.374
0.388
0.360
[
min 7 S]
step step 0.1 to 0.01
0.1046
0.4855
0.0880
0.0688
0.0134
0,0125
0.0311
0.0055
0.0093
0.0074
0.0013
0.0070
0,0032
0,0032
grad noise upoch
0.0051
0.0016
0.0028
0.0633
0.0113
0.0027
0.0052
0,0013
0.0013
gra noise final
0,0623
0.0969
0,0473
0.0934
0
0
0
0.0329
0,0329
0.1241
0.1155
0,0503
Table 4: Optimization-Be Based Measures
Number of Iterations: The number of iterations roughly characterizes the speed of optimization, which has been argued to correlate with generalization. For the models considered here, we ob- served that the initial phase (lo reach cross-entropy value of 0. of the optimization is negalively correlated with the speed of optimization for both T and V.. This would suggest that the difficulty of optimization during the initial phase of the optimization benefits the final generalization. On the other hand, the speed of optimization going from cross-entropy 0.1 to cross-entropy 0.01 does not seem be correlated with the generalization of the final solution. Importantly, the speed of optimization is not an explicit capacity measure so either positive or negative correlation could potentially be informative.
Variance of Gradients: Towards the end of the training, the variance of the gradients also captures a particular type of "flaatess" " of the local minima. This measure surprisingly predictive of the generalization both in terms of and V, and more importantly, is positively correlated across every type of hyperparameter. To the best of our knowledge, this is the first time this phenomenon has been observed. The connection between variance of the gradient and generalization is perhaps natural since much of the recent advancement in deep learning such as residual networks (He et al., 2016) or batch normalization have enabled using larger learning rates to train neural networks. Stability with higher learning rates implies smaller noises in the minibatch gradient. With the mutual information metric, the overall observation is consistent with that of ranking correlation, but the final gradient noise also outperforms gradient noise at epoch of training conditioned on the dropout probability. We hope that our work encourages future works other possible measures based on optimization and during training.
CONCLUSION
We conducted large scale experiments to test the correlation of different measures with the gen- eralization of deep models and propose framework to better disentangle the cause of correlation from spurious correlation. We confirmed the effectiveness of the PAC-Bayesian bounds through experiments and corroborate it promising direction for cracking the generalization puzzle. Further, we provide an extension to existing PAC-Bayesian bounds that consider the importance of each parameter. We also found that several measures related optimization are surprisingly pre- dictive of generalization and worthy of further investigation. On the other hand, several surprising failures about the norm-based measures were uncovered. In particular, we found that regularization that introduces randomness into the optimization can increase various norm of the models and spec- tral complexity related norm-based measures are unable to capture generalization in fact, most of them are negatively correlated. Our experiments demonstrate that the study of generalization mea- sure can be misleading when the number of models studied is small and the metric of quantifying the relationship is not carefully chosen. We hope this work will incentivize more rigorous treatment of generalization measures in future work.
To the best of our knowledge, this work is one of the most comprehensive study of generalization to date, but there are a few short-comings. Due to computational constraints, we were only able to study 7 most common hyperparameter types and relatively small architectures, which do not reflect the models used in production. Indeed, if more hyperparameters are considered, one could expect to better capture the causal relationship. We also only studied models trained two image datasets (CIFAR-14) 10 and SVHN), only classification models and only convolutional networks. We hope that future work would address these limitations.
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGEMENT
We thank our colleagues at Google: Guy Gur-Ari for many insightful discussions that helped with the experiment design, Ethan Dyer, Pierre Foret, Sergey Ioffe for their feedback, and Scott Yak for help with implementation. We are grateful for insightful discussions with Brady Neal of University of Montreal about limitation of correlation analysis. We also thank Daniel Roy of University of Toronto for insightful comments.
REFERENCES
Arora, S., Ge, R., Neyshabur, B., and Zhang, Y. (2018), Stronger generalization bounds for deep nets via a compression approach. arXiv preprint arXiv: 1802.0529..
Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. (2017). Spectrally-normaaizeed margin bounds for neural networks. In Advances in Neural Information Processing Systems, pages 6240-6249,
Bartlett, P. L.., Harvey, N., Liaw, C., and Mehrabian, A. (2019). Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17.
Bartlett, P. L. and Mendelson, S. (2002). Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482.
Chaudhari, P. and Soatto, S. (2018). Stochastic gradient descent performs variational inference, con- verges to limit eycles for deep networks. In 2018 Information Theory and Applications Workshop (ITA), pages 1-10. IEEE.
Dinh, L., Pascanu, R., Bengio, S., and Bengio, Y. (2017). Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference on Machine Learning- Sourning-Volume 70, pages 1019-1028. JMLR. org.
Dziugaite, G. and Roy, M. (2017). Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008.
Elsayed, G., Krishnan, D., Mobahi, H., Regan, K., and Bengio, S. (2018). Large margin deep networks for classification. In Bengio, S., Wallach, H., Larochelle. H., Grauman, K., Cesa- Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems 31, pages 842 852. Curran Associates, Inc.
Gao, J., Buldyrev, S. V., Havlin, S., and Stanley, H. E. (2011). Robustness of network of networks. Physical Review Letters, 107(11);155701.
Golowich, N., Rakhlin, A., and Shamir, O. (2017), Size-independent sample complexity of neural networks. arXiv preprint arXiv: 1712006541.
Hardt, M., Recht, B., and Singer, (2015). Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint arXiv: 1009v01500
He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778.
loffe, S. and Szegedy, C. (2015). Batch normalization: Accelerating deep network training by reducing internal covariate shift. CoRR, abs/1502.03367.
Jiang, Y., Krishnan, D., Mobahi, H., and Bengio, S. (2018). Predicting the generalization gap in deep networks with margin distributions. arXiv preprint arXiv:1810.00113.
Kendall, M. G. (1938). A new measure of rank correlation. Biometrika, 30( 1/2):81-93.
Keskar, N. S., Mudigere, D., Nocedal, J.. Smelyanskiy, M., and Tang, P. T. P. (2016). On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: 04836.
11

---

Published as a conference paper at ICLR 2020
Kontorovich, A. (2016). Dudley-pollard packing theorem. uni-bielefeld.der wttp://ooooeeeee//ooooooooo-eeee robott-rroooooooooo wwt.-ooooooooooo-ooooooo---
http://alweb. techfak.
Krizhevsky, A., Nair, V., and Hinton, G. (2014). The cifar-10 dataset. online: hltp://www. toronto. edu/kriz/cifar himl, 55.
Liang, T., Poggio, T., Rakhlin, A., and Stokes, J. (2017). Fisher-rao metric, geometry, and complex- ity of neural networks. arXiv preprint arXiv:1711.01553
Long, P. M. and Sedghi, H. (2019). Size-free generalization bounds for convolutional neural net- works. arXiv preprint arXiv: 1905.19905.20000
McAllester, D. A. (1999). Pac-bayesian model averaging. In COLT, volume 99, pages 164-170. Citeseer.
Merity, S., Keskar, N. S., and Socher, R. (2017). Regularizing and optimizing Istm language models. arXiv preprint arXiv: 770.002/8.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2012). Foundations of machine learning. adaptive computation and machine learning. MIT Press, 31:32.
Nagarajan, and Kolter, J. Z. (2019a). Deterministic pac-bayesian generalization bounds for deep networks via generalizing noise-resilience. arXiv preprint arXiv:1905.13344
Nagarajan, and Kolter, Z. (2019b). Generalization in deep networks: The role of distance from initialization. arXiv preprint arXiv: /901.01622.
Neal, B. (2019). Over-parametrization in deep and causal graphs for deep learning theory. Re- searchGate.
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Y. (2011). Reading digits in natural images with unsupervised feature learning. NIPS Workshop on Deep Learning and Unsupervised Feature Learning.
Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N. (2017). Exploring generalization in deep learning. In Advances in Neural Information Processing Systems, pages 5947-5956.
Neyshabur, B., Bhojanapalli, S., and Srebro, N. (2018a). A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. International Conference Learning Represen- tations.
Neyshabur, B., Li, Z., Bhojanapalli, S., LeCun, Y., and Srebro. N. (2018b). Towards under- standing the role of over-parametrization in generalization of neural networks. arXiv preprint arXiv: 1805.
Neyshabur, B., Salakhutdinov, R. R., and Srebro, N. (2015a). Path-sgd: Path-normalized optimiza- tion in deep neural networks. In Advances in Neural Information Processing Systems, pages 2422-2430.
Neyshabur, B., Tomioka, R., and Srebro, N. (2014). In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1412.6614..
Neyshabur, B., Tomioka, R., and Srebro, N. (2015b). Norm-based capacity control in neural net- works. In Conference on Learning Theory, pages 1376-1401.
Novak, R., Bahri, Y., Abolafia, D. A., Pennington, J., and Sohl-Dickstein. J. (2018). Sensitivity and generalization in neural networks: an empirical study. arXiv preprint arXiv:1802.08766.
Pereyra, G., Tucker, G., Chorowski, J., Kaiser, k.,, and Hinton, G. (2017). Regularizing neural networks by penalizing confident output distributions. arXiv preprint 17X1v:700..06548.
Pitas, K., Davies, M., and Vandergheynst, P. (2017). Pac-bayesian margin bounds for convolutional neural networks. arXiv preprint 1801.00
12

---

Published as a conference paper at ICLR 2020
Recht, B., Roclofs, R., Schmidt, L., and Shankar, V. (2019). Do imagenet classifiers generalize to imagenet? arXiv preprint arXiv:1902.105: 10811.
Rowling, J. K. (2016). Fantastic beasts and where to find them. In Yates, D., editor, Harry Potter film series. WarnerBros.
Sedghi, H., Gupta, V., and Long, P. M. (2018). The singular values of convolutional layers. CoRR, abs/1 abs/1805.10400 10400.
Smith, S. L. and Le, Q. V. (2017). A bayesian perspective generalization and stochastic gradient descent. arXiv preprint 1rXiv=1710.06451.
Vapnik, V. N. and Chervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events their probabilities. In Theory of probability and its applications, pages 1 11-30. Springer.
Verma, T. and Pearl, J. (1991). Equivalence and synthesis of causal models. In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, UAI "90, pages 255-2700 270, New York, NY, USA. Elsevier Science Inc.
Wei, C. and Ma, T. (2019a). Data-dependent sample complexity of deep neural networks via lips- chitz augmentation. arXiv preprint 1905.:39000038844
Wei, C. and Ma, T. (2019b). Improved sample complexities for deep networks and robust classifi- cation via an all-layer margin.
Wilson, A. C.. Roelofs, R.. Stern, M.. Srebro, N., and Recht, B. (2017a). The marginal value of adaptive gradient methods in machine learning. In Advances Neural Information Processing Systems, pages 4148 4158.
Wilson, A. C., Roelofs, R., Stern, M., Srebro. N., and Recht, B. (2017b). The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pages 4148 4158.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. (2016). Understanding deep learning requires rethinking generalization. arXiv preprint 1.100300
13

---

Published as a conference paper at ICLR 2020
A NOTATION
We denote a probability distribution as st set as A, tensor as A, vector as a, and scalar as a or a. Let 9 denote the data distributions over inputs and their labels, and let denote number of classes. We use - for equality by definition. We denote by S given dataset, consisting of m i..d tuples (11.31).... (Xm: }m)} drawn from where X, E X is the imput data and y; E {1..... x) the corresponding class label. We denote feedforward neural network by fw X - IR,, its weight parameters by w, and the number of weights by w - fim((). No activation function is applied at the output (i.e. logits). Denote the weight tensor of the 8th layer of the network by W, so that w Bee(Wi,,.... Wa), where d is the depth of the network, and vec represents the vectorization operator. Furthermore, denote by fw [x] the j-th output of the function fw (X).
Let R be the of binary relations, and 1 R {0, be the indicator function that is if its input is true and zero otherwise. Let L be the 1-0 classification loss over the data distribution D: [(fw) & E(x,)~= (XW((X)(V) I maxj fw (X)[i)) and let L be the empirical estimate of 1-0 loss over S: [(fw) _ 1
m Di=i (f)(( S maxjzv. fw (i). We refer to L(fw) ((fw) as the generalization gap. For any input X, we define the sample dependent margin as 7(x) - (F)( (X) max fw (X), Moreover, we define the overall margin y as the 10th percentile (a robust surrogate for the minimum) of (Xx) over the entire training set S.
Given any margin value 7 2 O, we define the margin loss Ly as follows:
[n((ww A E(xx)~
[X) S 7 + max fw (X) (x)
(6)
3zy
and L., is defined an analogous manner on the training set. Further, for any vector v, we denote by ||vll2 the & norm v. For any tensor W, let || [ å ||vec[ (W]l- We also denote ||]]| as the spectral norm of the tensor W when used with convolution operator. For convolutional operators, we compute the true singular value with the method proposed by Sedghi et al. (2018) through FFT.
We denote tensor as A, vector a, and scalar as A or a. For any < S k. consider a k-th order tensor A and a j-th order tensor B where dimensions of B match the last j dimensions of A. We then define the product operator 69):
(A 8 B B
,,)
where i1,..., . are indices. We also assume that the imput images have dimension n x and there classes. Given the number of input channels Cm. number of output channels Cout. 2D square kernel with side length k, stride s, and padding p, we define the convolutional layer conv w.ap as follows:
11 2p
k
conv .a. X)in W Wospatch,(i - 1)).)1(((1111))))111)) (X))
V1 S i, <
where W X is the convolutional parameter tensor, patch,,,. (Z) is k x k patch of Z starting from the point (i, and pad, is the padding operator which adds p zeros top, bottom, left and right of X:
X Xiniaa
p<in S n +
pad, (i
(9)
otherwise
We also define the max- max-pooling operator pools.s.p as follows:
n1 + 2p k
poole (X) max(patch 11 1)+1 (pad, (X ())
V1 S i1, i2 <
(10)
'This work only concerns with the output margins, but generally margin can be defined at any layer of deep network as introduced in (Elsayed et al., 2018) and used to establish generalization bound in, (Wei and Ma, 2019h).
14

---

Published as a conference paper at ICLR 2020
We denote by fw., convolutional network such that W. Raxa--18 is the convolution ten- sor and 8; is the convolutional stride at layer At Layer i, we assume the sequence of convolution, ReLU and max-pooling where the max pooling has kernel Ky and stride s/. Lack of max- max-pooling in some layers can be achieved by setting k = 8 = 1. We consider classification tasks and denote the number of classes by
15

---

Published as a conference paper at ICLR 2020
B CONDITIONAL INDEPENDENCE TEST: TOWARDS CAPTURING THE CAUSAL RELATIONSHIPS
Relying on correlation is intuitive but perhaps unsatisfactory. In our experiments, we change sev- eral hyper-parameteer and assess the correlation between complexity measure and generalization. When observe correlation between complexity measure and generalization, we want to differ- entiate the following two scenarios:
Changing a hyper-parameter causes the complexity measure to be low and lower value of the measure causes the generalization gap to be low.
Changing byper-parameen causes the complexity measure to be low and changing the same syper-parameter also causes the generalization complexity measure by itself has no effect on generalization.
low but the lower value of the
The above two scenarios demonstrated in Figure 2-Middle and Figure 2- 2-Right respectively. In attempt to truly understand these relationships, we will rely on the tools from probabilistic causality. Our approach is inspired by the seminal work Inductive Causation (IC) Algorithm by Verma and Pearl (1991), which provides framework for learning graphical model through conditional independence test. While the IC algorithm traditionally initiates the graph to be fully connected, we will take advantage of our knowledge about generalization and prune edges of the initialized graph to expedite the computations. Namely, we assume that the choice of hyperparameter does not directly explain generalization, but rather it induces changes in some measure which can be used to explain generalization.
0₂
02
0,
P
Figure Left: Graph initialization of algorithm. Middle: The ideal graph where the measure μ can directly explain observed generalization. Right: Graph for correlation where j cannot explain observed generalization.
Our primary interest is to establish the existence of edge between μ and y. Suppose there exists a large family of complexity measures and among them there is a true complexity measure that can fully explain generalization. Then verify the existence of the edge between μ and g. we can perform the conditional independent test by reading the conditional mutual information between and g given that set of hyperparameter types is observed'. For any function Φ θ - R, let Vo O2 O₂ + {+1, -1} be as (0(,,0)) & sign(ø(01) <(02)). Furthermore, let Ug be random variable that correspond to the values of hyperparameters in S. We calculate the conditional mutual information as follows:
p(Vn, UUs) Us),,Us){(, Us)
I(V V1 Us)
Ep(Us)
Σ
Σ
pVv,,, V, Uss log
(11)
V.((I) VE(+))
The above removes the unwanted correlation between generalization and complexity measure that caused by hyperparameter types in set S. Since in our case the conditional mutual information between a complexity measure and generalization is at most equal to the conditional entropy of generalization, normalize it with the conditional entropy arrive at criterion ranging between 0 and 1:
H(V, Us) - EP(US) Σ p(V, Us) log(p(V, Us))
(12)
Us
(EE(1))
For example, if S contains single hyperparameter type such the learning rate, then the conditional mutual information conditioned learning rate being observed.
16

---

Published as a conference paper at ICLR 2020
I(V Vg (Us)) H(V, (Us)
i( V Us)
(13)
According to the IC algorithm, an edge is kept between two nodes if there exists no subset of hyperparameter types such that the two nodes are independent, i.c. Ž(V Vg (Us) = 0. our setup, setting S to the set of all hyperparameter types is not possible as both the conditional entropy and conditional mutual information would become zero. Moreover, due to computational reasons, only look at [S] 2:
K(H) = min I(V V Us)
(14)
Usa. |8
At high level, the larger K. is for a measure the more likely an edge exists between μ and g. and therefore the more likely lr can explain generalization. For details the set-up, please refer to Appendix B.I on how these quantities are estimated.
B.I DEFINITION OF RANDOM VARIABLES
Since the measures are results of complicated interactions between the data, the model, and the training procedures, cannot manipulate it to be any values that we want. Instead, we use the following definition of random variables: suppose S is a subset of all the components of O (e.g. {Ø} for [S] 0, |S| {learning rate) for S = or [S] flearning rate, dropout} for JS| = 2). Specifically we denote Sab as the collective condition {0{ = v1, 0 =
of
22s -1, ((3)
"2 We then define and empirical measure four probability Pr(u > (0))) Sabb) Pr(u(() < (1(), g(()) 9(0) S and <
(b)) g/a) > g(0) Sab)) Pr(u(e) >
Pr( < (b)
, g(a) <g
(0 Sab).
(1)) > (())
(1)) < u
g g()
Poo
Pol
g gl (()
P10
P11
Figure 3: Joint Probability table for a single Sab
Together forms a by table that defines the joint distribution of the Bernoulli random variables Pr(g(a) > (( |Sab) and Pr(μ(()) (²(²) (Sab). For notation convenience,
Pr(μ,, g Sas). Pr(g Sat) and Pr[m1] Sav) to denote the joint and marginal. If there are = 3 choices for each hyperparameter in S then there will be |VS) such tables for each hyperparameter combination. Since each configuration occurs with equal probability, for that arbitrary ((s) and (6)) drawn from o conditioned on that the components of S are observed for both models, the joint distribution can be defined as Pr(ju.g S) = 1 Es., Sup Pr(μ,, y Sat) and likely the marginals can defined as No
Pr(u S) = Misi Es.. Pr(μ Sab)) and Pr(g S) = viss Es., Pr(g Sav). With these notations established, all
1
relevant quantities can be computed by iterating over all pairs of models.
C EXPERIMENTS
C.I MORE TRAINING DETAILS
During our experiments, we found that Batch Normalization (loffe and Szegedy, 2015) crucial to reliably reach low cross-entropy value for all models; since normalization is a indispensable com- ponents of modern neural networks, we decide to use batch normalization in all of our models. We remove batch normalization before computing any measure by fusing the f and moving statistics with the convolution operator that precedes the normalization. This is important as Dinh et al. (2017) showed that common generalization measures such sharpness can be easily manipulated with re- parameterization. We also discovered that the models trained with data augmentation often cannot fit the data (i.e. reach cross-entropy 0.01) completely. Since model with data augmentation tends to consistently generalize better than the models without data augmentation, measure that reflects the training error (i.e. value of cross-entropy) will easily predict the ranking between two models
17

---

Published as a conference paper at ICLR 2020
though it has only learned that one model uses data augmentation (see the thought experiments from the previous section). While certain hyperparameter configuration can reach cross-entropy of 0.01 even with data augmentation. it greatly limits the space of models that make the design choice to not include data augmentation in the models of this study. Note that from theoretical perspective, data augmentation is also challenging to analyze since the training samples generated from the procedure are no longer identical and independently distributed. All values for all the measures we computed over these models can be found in Table in Appendix C.5.
study. Hence,
C.2 THE CHOICE OF STOPPING CRITERION
The choice of stopping criterion is very essential and could completely change the evaluation and the resulting conclusions. In our experiments we noticed that if we pick the stopping criterion based on number of iterations number of epochs, then since some models optimize faster than others, they end up fitting the training data more and in that case the cross-entropy itself can be very predictive of generalization. To make it harder distinguish models based on their training performance, makes more sense to choose the stopping criterion based on the training error or training loss. We noticed that expected, models with the same cross-entropy usually have very similar training emorr so that suggests that this choice is not very important. However, during the optimization the training error behavior is noisier than cross-entropy and moreover, after the training error reaches zero, it cannot distinguish models while the cross-entropy is still meaningful after fitting the data. Therefore, we decided to use cross-entropy as the stopping criterion.
C.3 ALL MODEL SPECIFICATION
As mentioned in the main text, the models we use resemble Network-in -e-tewrr (Gao al., 2011)
which is class of more parameter efficient convolution neural networks that achieve reasonably competitive performance on modern image classification benchmarks. The model consists blocks of modules that have 3 x 3 convolution with stride 2 followed by 2 1 x convolution with stride 1. We refer to this single module as BiN-block and construct models of different size by stacking NiN-block. For simplicity, all NiN-block have the same number of output channels Cout. Dropout is applied at the end of every NiN-block. At the end of the model, there is x convolution reducing the channel number the class number (i.e. 10 for CIFAR-10) followed by global average pooling to produce the output logits.
For width, choose from Cout from 3 options: (2 96, x 96, 8 96).
For depth, we choose from options: {2 x NiNblock, 4 x NiNblock, 8 x NiNblock]
For dropout, we choose from options: {0.0, 0.25, 0.5}
For batch size, we choose from: {32, 64, 128}
Since each optimizer may require different learning rate and in some cases, different regularization, we fine-tuned the hyper-parameters for each optimizer while keeping 3 options for every hyper- parameter c
Momentum SGD:
We choose momentum of 0.9 and choose the initial learning rate n from {0.1, 0.032, 0.01} and regularization coefficient À from {0.0,0. 0.0001, 0.0005). The learning rate decay schedule is x0.1 at iterations [60000, 90000].
Adam: We choose initial learning rate y from (0.001,3.2e 1e-4), le and regularization coefficient À from (0.0, 0.0001, 0.00053. The learning rate decay schedule is x0.1 at iterations [60000, 90000].
RMSProp: We choose initial learning rate v from 00.001,3.24 - 4, le 4} and regularization coefficient À from (0.0, 0.0001, 0.0003). The learning rate decay schedule is x0.1 at iterations [60000, 900000,90000).
'While methods with adaptive methods generally require less tuning, in practice researchers have observed performance gains from tuning the initial learning rate and learning decay.
18

---

Published as a conference paper at ICLR 2020
C.4 CANONICAL MEASURES
Based on empirical observations made by the community as whole, the canonical ordering we give each of the hyper-parameter categories
follows:
1. Batchsize: smaller batchsize leads to smaller generalization gap
2. Depth: deeper network leads to smaller generalization gap
3. Width: wider network leads to smaller generalization gap
4. Dropout: The higher the dropout (S 0.5) the smaller the generalization gap
5. Weight decay: The higher the weight decay (smaller than the maximum for each optimizer) the smaller the generalization gap
6. Learning rate: The higher the learning rate (smaller than the maximum for each optimizer) the smaller the generalization gap
7. Optimizer: Generalization gap of Momentum SGD < Generalization gap of Adam < Gen- eralization gap of RMSProp
C.5 ALL RESULTS
Below we present all of the measures we computed and their respective T and V on more than 10,000 models we trained and additional plots. Unless stated otherwise, convergence is considered when the loss reaches the value of 0.1.
lesrning
weight
ref
batehaize
drepout
rate
depth
optintizer
decay
widtt
overall y
ve dim
19
0.000
0.000
0,000
-0.909
0.000
0,000
-0.171
-0.251
-0.154
params
shurpoess
0.537
0.513
0.449
0.825
0.221
0.253
00.004
0.282
0.248
pocbiges
48
0.372
-0457
0.042
0.644
0.179
-0.17
-0.142
0.064
0.066
sharpness
0,542
0.359
0,716
0.816
0.297
0.591
0.185
0.400
0.398
pachayes-orig
0.596
trob-distanee
40
40.317
4033
0.718
0.526
-0.244
0.069
00.16
4.203
0.341
spectral-ini init
25
0.330
0,345
0.721
0.908
-0.208
0.313
0.251
0.576
0,508
spectral orig
26
-0,262
-0.622
-0665
-0.008
-0.131
00,073
-0,240
-0.337
0.434
spectral-ocig main
trohpec
0.363
0
0,744
0.398
0.326
0.565
0.053
0.008
0.243
pro--of-pee:
32
-04644
.0.24
-0.722
-0.009
-0.197
0.114
00.218
-0.599
482
of spechmargin
4.722
sum spee
0,102
suab-of of--poemmrgiinn
34
40,308
.0792
.07702
0.909
-0.106
0.1448
-0.179
0.064
40.197
spec dist prod-uf fro
41
0.A55
00838
0.508
0.738
-0.119
0.112
0.171
-0.100
0,257
0.410
-0.99
0.538
0.909
0.321
0.731
-0.99
0.117
trohaar-io
.0.97
sum of dro
29
0.440
0.19
0.538
0.913
0.321
0.731
0.101
0.418
0.375
sum of fnoimargin
38
0.520
0.369
0.598
0.882
0.380
0.738
0,080
0.391
0.381
neg eatropy
0.632
0.220
1,100
0,148
0.124
path-torm
44
0.363
-0.19
0,216
0.925
0.272
0.195
9.178
0.370
0.280
path-corrm/mzgin
43
0.363
0.017
0,148
0.922
0,290
0,280
0.173
0.374
0,305
0.236
4.516
0.174
0.330
0,187
0.170
0.073
0,052
.0.16
0.120
0.177
0.090
cross eatropy
21
0.440
.0,022
0,140
0.390
0.149
0.252
0.000
0.149
0.147
1/a pacbayes
53
0.301
0003
0.744
0.200
0.346
0,509
0.056
0.303
0.346
sharpness
sum-seep-0.1-ee to--0-l----00
0.114
mum-atp--t--11-- I-loss
63
-0,644
-0361
.0
0.440
40,000
-0,628
0.043
40.264
-0.279
1/a' sharness
0.570
0.148
0.762
0.824
0.297
0.741
0.269
0.484
0.516
1/o' pacbayes mag
0.490
0.896
0.365
0.315
me-sharpoess-aaag
-0.293
.1341
.068%
.0.99
<0.240
.06331
-0.171
.0.225
.0.51
pac-sharpoess mag mag--rig
0.401
-0.14
0.321
-0.09
0.181
0.281
-0.171
40.158
401059
pachayes-mgginil
0,052
pachayes-mig-arig
-0.40
0.902
0.410
0.284
grad goase finll
66
0.452
0.119
0.427
0.141
0.245
0.432
01230
0.311
0.292
gai--niie-ppchh-
65
0.071
0.378
0.376
<0.517
0.121
0.221
0.037
0.070
0.099
oraele 0.01
0.682
oracle
0.742
0.726
ornele 0.05
0123
0.350
0.305
0.401
0.132
0.201
0.142
0.456
0.236
ocacle 0.1
0.099
0.227
0.1.22
0.225
0.086
0.121
0,093
0.241
0.13
canonical ondering depth
-0.909
-0061
40.363
+0.188
Table 5: Complexity measures (rows). hyperparameters (columns) and the rank-correlation coeffi- cients with models trained on CIFAR-10.
19

---

Published as a conference paper at ICLR 2020
learning
weight
baidisize
diopont
18]
R: param
0,022
0.3275
0,0229
LO0034
0,0208
(X02T6
0.0579
20173
entropy
0.0120
0,9656
0,0113
0.0086
0,0120
0.0155
5055
0.0900
00000
1000
1
I-over sigma pachayes
0.0884
0.1514
0,0813
0.0399
0,1004
0,1025
L-over-sigma- pachayes
0,0711
0,0899
0.0555
00000
over sigma sharpness mag
I- 1-over-siggn shampsshrrreesss
0.1640
0.1066
0.2223
0,2572
0,0792
0.1228
0,1424
0.0713
0.1779
0.1196
0.1562
0.1041
0.117
0.1796
0000
2
00233
07256
entropy
00233
0,0830
00000
displacement
fro over
frub distance
fishe-rrn
0.0099
0.0011
0.0622
0,0065
0.0530
0.3072
0.0196
0,029%
0,0020
0.0196
0.0777
0.0713
0.159
0.0006
0.0057
0,0502
000155
00001
0.079
0.0079
0:0506
0:0071
0,0906
0,0005
00000
00000
00000
0.904
0.0185
0000
0,0125
02112
0.001
grad-soise--o epoch-
input gradl nerm
grad nnise tinal
margin
0.0914
0.0623
0.3016
0,1374
0,0909
0.1200
0,0673
00633
00934
007800
1155
0.0945
0.1084
0.0855
00077
000227
0:000
0.0783
0.0119
0.1051
01006
00772
000000
00108
2000
0000
20033
20072
0,0051
0,0426
0,0.25
omele-0.02
0.4077
0.5671
0.3557
0.600
0.3029
0.6171
0.1144
0L4057
0.6088
0:0191
D.115
011500 18:
09686
0,2579
8.1637
pacbuyes
omalee-0.it
0.0266
0,1475
0.1167
0.0238
0.1309
0.0274
00030
0.1515
0.1469
0,0210
0.1535
0.0345
00202
20000
5003
0,000
patbayes-naa--oit
pacbayes-org
0.0620
0016
0.1671
0.1006
0,0892
00426
00297
0.1805
0.0645
013110
00030
0:1246
0.2252
60009
0,354
00054
0,0225
DA223
pacbayes
0.0053
0,0164
0,0094
000866
0.0036
0.0066
0.0185
00000
0.003
1,0040
parameter-nocm
0.0039
00039
path nomtioverr-arrge
palb-nons
0.2466
0.1027
0.1453
0.1250
0.3199
0.113
0.1508
0.2179
00217
0,315
0.1145
0. 10566
0.2473
CL2540
0,1058
0.1028
0.1090
0.1160 0,1100
0.2457
0:388
0.3011
1000
1
00181
00862
0.0240
0.0199
prod spec
random
DUBRS5
0-0005
0,002
0,0066
0:0000
0.2394
0/000
012385
0.000
0,0415
0A00
sharpness mag orig
sharpaess-aagg mig---i
0.0125
0.6366
0,0143
0,3400
0,0195
0,4891
00025
00191
0.0120
0.0574
0.0134
0L0573
00014
0.0761
01011
0x3668
0.0036
0.0199
DJ0033
pharpnest-rrig
0.1254
0.1189
0.0234
ypee-arig-main
shis press
spoc-init
0.2266
0.2536
0.290
0.3161
0/4427
0.3072
0.2205
00890
0110
00126
0.2255
0.08866
0.2533
0L2355
0.2584
0.0999
0:0000
0:2540
0.2562
0.3263 12223
00083 1
0.5500
0,0799
00130
010900
00739
D,8382
0.0599
spec-orig
0:1188
step-i 1-10-001
0.025
0.003
0.0055
00093
0.004
0:0070
00055
0,0266
0,003
secp-5o-0.1
0.6349
0.1361
0,0997
01046
0.0485
CL0580
0.0558
0.0022
0.0134
sum--of fro margo-
0.1200
1.2249
0.1005
00040
0.1202
0.1060
0.1645
0.1227
0,0366
120110
fum--fffro--vr-u-----
0.0258
0/7297
sunt--offlr
0.1292
0.1115
B.0119
sum-of sum-of-pec-on -poc-moer--urriin
0.0089
0,0292
0.0406
0.0951
0.0089
0.0069
0.0054
0.0051
0.0054
0.0072
sum-of-spec
0.0127
0,0334
0,0466
0.0876
0.0117
010099
0.0080
0
0.0079
D.0099
ve-dim
0,0412
0,0000
conditionnl entropy
0.9836
0.8397
0,9331
0,8308
0,0960
0.9746
NIA
N/A
N/A
Table 6: Complexity measures (rows), hyperparameters (columns) and the mutual information with models trained on CIFAR-10.
Distribution, of Training Error
700 J
600
500
400
300
200
100
7
-0.002
0.000
0.002
0.004
0.006
0.008
0.010
0.012
Training Error
Figure 4: Distribution of training error on the trained models.
20

---

Published as a conference paper at ICLR 2020
lcoming
weigh
bacchiie
depth
optinizer
doery
ve dim
0,0000
000000
(L0000
-1,0000
0L0000
(1000
-10475
params
0,0000
0,000
0.0000
110000
0,0000
0.0080
400478
shaepoess
0.1898
-0,4092
0.4599
0.1288
0.3444
1.1302
pachaaes
0,0006
-0.5006
0.9477
01831
-02223
00000
sharpness Orel
0.2324
0.1907
0.6329
0.9595
0.2196
0,011
0,1923
55130
0.3654
pachares litef
0.1983
-0.3055
0.9979
03863
0.2286
0.458
0/0055
007700
0.3185
displacement
-0,800
-04319
40,0302
01700
spectral complexity
0.7928
0.5423
00.9899
0,1063
0,2913
0,0729
0:4567
speco complexity tsef
8.1362
-0,1100
-0.40888
40,9932
-0,0513
0U0671
11.10%
-06065
.0.3290 0
spectral complesity tieet last2
0,1302
0.6100
-0,4085
405622
-0,0513
000671
-0.2357
0,3880
1033490
spectral camplesity Oref lastl
spectral prodict
-02601
-0.5335
40.028
1.1033
-00043
40,2705
005600
40:0399
spectral product om
0,2582
06649
40.5322
40:2299
.0,0/18
-0.0011
40,2477
-0.500
40,8031
spectral product MV2
-0.2603
-0.5835
-0,6025
0.9989
10,1083
-0.0341
-0.2705
0.4627
-011257
spectral produce
-04419
-0,0218
-0.1287
spectral
0:7752
-0.3366
09616
000009
-0.3637
00,0434
0.488
0,3542
2:112
Iroh prndact
0,5098
-B4359
0.5439
-1,0000
0. 186
0.6088
0.0126
0.1238
froh produce om
0.4673
-0.1362
0.5534
-1,000
0.2079
0L0375
0.0091
-0,5001
0.1070
froh product dd/2
-0.0400
frob product
-0.1362
0.5534
09492
0.7099
0.6755
0.0091
0.5338
0.3855
median margia
0,0684
0.3861
-0.1519
40,314
.0,1018
0.221
0.0216
-0.3829
-0.0554
impui gead form
0,0997
0,677
-0.2389
0.9955
0,026
0
0.0216
0.6360
0.2166
logit entropyy
0.136
poth
0.2150
0:2565
0.0644
0.1018
0.3855
0.5626
0.2936
purameter norm
0.3246
-04794
0.1730
0.6639
0.0780
0
-0,0998
0.3747
0.1227
fr aocm cross-entropy
0.2313
0,0000
0.0222
-0,6189
0. 1008
0.3190
0.0546
-0.2844
0,0227
logit
0.0500
-0.3377
norm lopit margin
0.2313
0.0000
-0,3277
1008
0,390
0.0546
111668
0.0643
poth aocn/imnrgin
0.1107
0.0291
0.1341
0.9978
0. 0,1504
0.2998
0L0633
0.5798
0.2429
epoch loss
0,4390
-0.5989
0.2634
0.9729
0 1602
-0,0445
-0,0034
0.5186
1697
firal
-0.004
0.8811
Usigma gaussian
0.1867
-0.1862
0.6164
0.6665
0.2280
0,4985
0.1512
0.3148
0.3087
Viigma sharpness
0,2321
-0.1549
0.6330
0.936
0.2253
0.5163
0.2179
0.4930
0.3723
min(norm distance)
0.3235
-0.4785
0. 0.27
0.6633
0.0766
0.1 031391
-0,0405
0.3744
0,1223
step between
-0.1610
step to
-06667
-0,6983
-0.4814
08738
-0 1609
-0.3144
-0,1015
0.0035
-02666
step to 0.1
-0.6556
-0.9120
-0.3613
0.9566
-0.1450
-0,9974
-0.0414
0.0944
-0.2524
Ippuram shurpness
0,4466
0.3254
0.6650
0.9831
0.2753
0.6495
0,2680
0,5676
0.5173
lipermm ganesian
0.4758
0.5674
riti oplx sharpeess
-00788
.07188
-0.4583
-1,0000
-0,0540
-0.4300
-0,000
ratio upla shurpnees Oraf
0.5005
-0.5631
0.3155
-1.0000
0. 0.1648
0.2440
-0,0502
-0.1687
-00029
ralio opts gaussian
0,2389
-0.3323
0. 2298
-0,9786
0 1625
-0.0479
-0.0484
-0.1309
-0 10.1116
ratio upls ganssian Oref
0.1682
msio opls sharpness ul
0.2778
-04237
0.5492
-0.9707
1830
0,4040
-0.0434
-00580
+0,0034
ratio opls shurgress Oraf ul
0. 0.3406
-0.2168
0.6476
40.9650
0.2421
0.5463
-0.0422
-0.1
0.0818
raiso cpls gaussion ul
0,2300
04427
00,000
0.9707
0.1346
003957
0.0002
0.5052
0.0574
ratio cpla goussian
grad
0.2128
-0.1862
0.5458
0.1711
0.11.49
0.0594
0.1305
grad var epoch
0.1590
0.1912
-0.0159
0.0118
-0.0534
0.2760
-0,0346
0.1222
0,0806
unaele 0.01
0.381L
0.6463
0.4293
0.9517
0.3478
0.3946
0.3572
0.8070
0.5012
0.2410
unacle 0.05
0.1238
0.2235
0.1530
0.6706
0.0522
0.1057
0.0785
0.5182
0,2010
onccle 0.1
-0.0239
0.0708
0.0844
0.4356
0.0408
0.0526
0.0512
0.3322
0,1011
canonical oodering
0,6732
0,9539
0.6425
1.0000
0,1028
0.6662
0.0478
0.0123
0.3620
ordering depch
0,0247
0,0253
-06241
Table 7: Complexity measures (rows), hyperparameters (columns) and the rank-correlation coefli- cients with models trained on SVHN dataset.
21

---

Published as a conference paper at ICLR 2020
Eumning
weight
bachnize
dropout
make
depth
optimizer
docny
widhh
overall T
+
dim
0,0000
000000
0,0000
-0.530
000000
00000
000039
0.11.0
0,0000
0,0000
0.0000
4.7520
0,0000
0.0000
40,0392
-0.1100
shaspness
0.200
.0.996
0.6288
00532
-00022
02225
0,073
pacbuyes
0.1490
0.0138
0.0611
0.3993
0,0570
0023400
022900
0,0343
sharpoess Uref
0.2271
0.1677
0.4462
0.262
000600
0.156
-00058
03104
0.2181
pacbayes Uret
0.2587
0.5282
0.1102
40,014
0.2430
displacement
0.7677
0.6504
003331
0,0392
02252
spectral complexty
0,1495
015752
-0,208
4074077
.0,200
-0.2835
410045
0.4355
40,3906
spectral complexity Uret
0,0837
004196
40,5747
40.3399
40.176
00.1488
-0.1085
0.3860
00,5770
spectral camplesity 0ief last2
-0.8837
-0419
40,4777
40.7244
-0.1776
-0.1468
10,1857
013940
spectral complexity lastl
0.2006
0.3893
0.7221
4.7435
0.4169
0.4404
0.0015
00417
0.2210
spectral product
0,2034
0.5619
00.1199
007520
0.2184
-0.1269
40,0991
0.4136
00,3655
spectral product om
-0.1257
-04727
40,5549
4.7781
-0.2350
-0.2113
-0.1707
-0.4338
-0.3542
spectral product dd'2
005619
40,6199
40.2184
-0.1209
0,0527
.0.14%
spectral produce om
0.4722
40.5499
0.7501
-0.2133
0.0868
spectial sums
0.2005
-0.378
-0,5002
0.5832
-0.3751
-0.0999
JL0992
-011177
.0.1884
frob product Frih product
0.2854
-0.1332
0.4967
40.7500
0.3609
0.4656
0.0054
-021122
0,1013
0.2816
-0.1987
40.7530
-0.1113
frch product
0.2554
-0.1522
0.4967
0,7652
0.3689
0.4656
0.3407
0.3180
trob product do72 om
0.2816
-0.1577
0.4613
0,7643
0,2365
0L3729
0.0130
0,3356
0.2758
median margin
-0,1652
0.3153
-0,0550
40,4444
0. 0,126
0.1738
0.3142
-01295
0.0046
impur grad
0.0851
06548
40.2502
-0.1871
0.149%
logit entropy
0..496
0.3906
0.1614
-0.2519
40,0093
0.378
0,0099
poth nomm
0:2549
0.5258
0.2951
08161
0.2593
0.223
0/020
0.3893
0.3451
parameter norm
0.2472
-0,000
0.3754
0.1287
0.2716
0.156
-0,0458
0.0866
0.1607
entropy
0,0227
0,0246
0.0225
nams logit
0,027
0.0162
400044
-015
0.0355
0.031
0.1880
0.0394
fr norm logit margin
0,0727
03372
0.0122
400044
.0,195
0L0555
010331
0.1780
0.0594
poth mvem/morgin
0,2510
0.0441
0.3314
0.718
0 1206
0.0571
-0,0558
0.3580
0.2172
epoch
0.044
0,684
-01217
0.1452
.0.105
-0.0300
0.3484
-0,000
-0.1140
-0,2266
0.1410
.:0321
Nsigms grussian
0,2525
0.1905
0.4993
0,668
0.022
0.1298
0.060
0.3213
0.2272
Uiigms shorpness
0.2120
0.0088
0.3879
0.6997
0.0611
0.1191
-0,0073
0.3005
0.1912
distance)
0.2472
0.0868
0.1CKT
stop between
-0,0533
-00747
-0.0793
0688
00118
0.0621
-0,0168
-00200
0.0134
step to
..3219
-0.5252
-0.4186
0.319
-0.1076
-0.1497
-0,0095
-02071
.02161
step 0.1
-03219
-0.8366
-0.2606
0.2859
-0,0999
-04231
-0,0062
-0.2350
-.2331
Myarrmm sharpness
00154
0.2555
lpwarm goussian
0.1660
0.4001
0.6820
0.0199
-0.0579
-0.1508
0.2578
0.1525
riño opls shurpness
0.77
-0.7743
-0.6476
-0.7530
-0.2498
-0.3603
-0.0392
-0. 1602
-04315
ratio opls sharpeess Oeef
0.3780
-0.0009
0.5033
-0.7530
0 0067
0.2688
-0,0992
-018677
0.0937
cpls
-0.2183
20.123
ratio splt gressian Orof
0.1509
-0,0266
0.2961
-0.7530
0.0899
-0.1434
-0,0392
-0.075
-0.1245
nsio opls sharpness ul
0.2091
-0.1871
0. 0.1988
-0.7530
-0,0114
0.1140
-0,0992
-00971
-0.0673
sharpoess Ore/ ul
0.2615
0.0669
0,3110
-0.7520
0.1622
0.2527
-0,0392
-0.0774
0,0566
ratio opls panssian
-0.2413
0672
ratio epix ganssian ul
0.2334
.0.0466
0.4737
0.6934
0.0722
-0.0339
-0,0468
0.3129
grdd var
0.1013
0.3514
0.3706
0.2730
0.30
-0.0652
0.0050
0.3538
0,1656
grad var epoch
0,0801
0.4645
0.3792
-0.3701
0.49
0. 1328
0.0814
0.1279
0.1204
ondle (101
0.5878
0.8470
unacle 0.02
0.3588
0.7288
0.5922
0.5804
0.3870
0.3440
0.3927
0,7032
0,4848
onaele 0.05
0.1114
0.4149
0.3066
0.2937
0. 1918
0.1473
0.1697
0.4267
0.2336
oracle 0.]
0.1007
0.1736
0.1957
0.1225
0.0692
0.0876
0.2123
0.140]
canunical onlering
0.9459
cononical ordering deych
-0.0238
-0.0337
0.0105
-0.7530
-0.0152
0.0353
-0,0054
-0.2835
-0.1120
Table 8: Complexity measures (rows), hyperparameters (columns) and the rank-correlation coeffi- cients with models trained on CIFAR-10 when converged Loss 0.1.
22

---

Published as a conference paper at ICLR 2020
lcaming
wergin
batchsize
drapout
rate
depti
optimizer
decay
width
ovenall y
+
0
0
0,3003
0,1457
0,150M
purams
0,11487
sharpness
0.54VZ
405155
0.4636
0.2277
0.2134
0.2025
0.0083
0.2499
pacbuyes
0,3896
0,6459
0.0127
0.6299
0.1721
0.1757
0.1256
0.0647
0.0992
sharpness
0.5493
003492
0.7147
0.101
0.3006
0.5655
0.1976
0.3996
0.3964
pachayes-ook ooip
000847
0.377
0.3997
0.063
022899
frob distance
0.3048
0,8366
0.7253
0.3001
00.4437
0.6700
0,199
0.2006
0.3429
spec-init
40,3414
118846
10.7336
10:900
-0.2422
113114
0.2133
415544
+0,1135
spec-orgg
40.7593
003000
0,0000
0,1273
41:354
0.4577
spec
0.7593
0,878
0.9090
1,1110
0.0080
0,2002
0.545
fro spec
0.5884
0.3703
0.7301
-0.9004
0.3661
0.08
4112199
400086
0.2585
prod of spes
0.4718
0072237
00,330
0039072
10,2583
0.1100
0121336
0.5598
0,4895
spechmurgin
0.3222
0.780
0.716
0.9066
0,20066
0.1614
0,1721
0..698
166665
suib-ot-spee
-072277
10.7300
09072
-0.199
021136
0.1025
sum of spec/mmazgin
0.3222
0,780
46716
020066
0020006
0.1614
0,1727
0.0662
0,2075
spec-dist
404506
41,8263
0.7297
-0.5413
.0,327
-0.1485
40,1044
+0,2998
pood-ot-te
40.185
01523
-0.90722
0.0835
pood drotmargin
suat-af-fro
B.4699
40.1855
.0.372
0.338
0.5383 3
03009
0.9072
0,4024
0.3342
0.7255
0.7329
-0,885
0,0673
002957
0.4157
0.3845
sess-of-Ee Erohiarriin
0,5377
-0.372
01308
03331
0L4024
0.7329
0.0073
0.3894
0,3865
1/margan
0,3334
0.5914
0.253
0.753
00.2257
0.2087
0,0985
0.1257
0,1236
inyut grad norKs
033
06239
0.590
0.2054
0.3836
neg encropy
0.3086
-0,3443
022000
000226
0.2296
.0.1507
0.0673
0.1472
0.1209
patl-ncem
8.2457
0.362
003366
0.1271
0.3291
0,1558
0.3718
0.2984
40.5194
1,160
03346
0.3025
03494
-0-537
0.5559
0.1484
0.1028
norm logit sum
B.3277
0.1625
0.3494
-0004
0.1322
0.5559
0.1484
0.2238
0.2267
nomm lngit margin
0,4327
0.3025
0.349
-00044
0.1322
015559
0.1484
0.2238
0.2367
nomshaargia one epoch
40,2022
02139
0.2103
0.3124
-0,4362
0/477
0.153
-0-0475
00128
.0.0447
0:0147
crocs-cstropy
0.2443
-0,40155
0.1518
01:621
0.1367
0.2422
0.0676
0.1515
0.44
Viigma pachayes
0.5109
-0,0349
0.7581
0 03003
0.3738
0,6048
0.0686
0.2993
0.3545
Msigma sharpness
0.7154
0.7530
mininorm distance)
-0.3194
1,000
03346
0.1198
0.1550
0.0729
mart- step--.pp..... 1-oo-0001-ooss
001458
-0.0816
0.0006
0.1118
0.0649
0.0348
-00387
-0.066
-0.0130
to
J.6798
-1.5418
10.4211
033491
-041588
48,6900
0.0122
40,2812
+0,2936
Sess--ttp--t-----lee I-los
41,8526
0..060
0.4455
40.6844
40,2847
Malpha sharposs mag
0.1381
0.537
08181
0.3163
0.737
0.2416
0.481
Malphi pachtyes mag
0,5089
-0.2588
0.5303
0,8059
0.1907
0.1628
0.1738
0.3649
D.3162
pac pac-sharpaess charpaess-magg-aeee
002967
.1,451
10.7165
-0.90722
-0.2637
136387
0.1188
41,226
+0,552
mes-hhrpnees-ma--orri
40.5227
0.3100
0.2586
puchayes-mag-tni
-0,6438
0.3402
-0.9072
48,1006
00.1485
puchayes-ma mag--
0.4694
-0.7749
0.317
-0,9072
0.1343
0.0315
0..488
-0. 1686
-0,1255
mato opix sharpness
B.9074
40.5599
06614
-0.9064
0.2779
0.4205
-0.1487
-0 14.4
0.0323
cplx sharpness thef
0.7642
neño spik guussian
-0.6655
.00236
03761
0.1058
-0,403
0.0465
0.78
main spik gunssion Oref ml
0.5721
-0.4788
0.5105
03018
0.1896
0.1495
0.168
0.4093
0.2875
gmmd-nois--iinll
0.3663
0.0009
0.3066
0/8113
(L1773
0.4492
0.1615
0.2521
0.2309
gmul-noise-ppccs-
0.3618
0.2691
0.7047
8,004
0,6117
0.5107
B.6736
omcele 0.02
0,3904
0,6862
0.5405
0.7126
0.35
0.3969
0.336
0.7197
0.4589
omacle 0.05
0.1827
0.3684
0.3099
0.3893
0.1478
0.1676
0. 1665
0:4518
0.2476
0.2064
canonical urdering
0.668
0,9753
0.7421
0.9073
-0.0511
0.7268
0. 0.14
-00079
0.3973
cononical ordering deyth
0.0025
-0.012
00.0019
-0.9073
0.0041
-0.0133
-0,0002
-0.3605
-0.1326
Complexity measures (rows), hyperparameters (columns) and the average rank- correlation coefficients over 5 runs with models trained on CIFAR-10. The numerical values consistent of that of Table 5.
Table 9:
23

---

Published as a conference paper at ICLR 2020
lessning
weight
barchsize
dropout
rate
deych
optimizer
decay
width
overall
W
params
0,0038
0.0179
0.0009
0,0026
sharpess
0.0124
0.0129
0.0555
0,0036
0.196
0.0144
0.0181
0.0026
0,0056
pacbayes
0.0171
0.0199
0.0088
0,0086
0.0044
0.0788
0.0189
0.000s
0,0043
sharpesse ong
0.0511
0.0161
0,004
pacbayes-ort orig
0.011
0.0622
00111
0,0033
0.0122
0.015
0.0173
Inob distance
0.0102
0.0049
0.0067
0,0055
0.017
0.102
0.0176
00003
0,0043
imil
0.0061
0.0029
0.0072
0.001
0,192
00101
0.100
0,000
0,004S
spec ong main
fno spec
spec-orig
prod-af-ppe
0.0015
0.0164
0.0099
0.0105
0.0066
00072
0.0344
00048
00072
00000
0.0015
20000
00106
00106
00000
05101
00248
00234
00234
0000
69136
022200
00003
10000
10000
0000
02000
S0000
0,0016
0,0055
prod specimargin
sum-of-spee
00083
0.0199
0,082
0.048
0,009
0,0255
00249 62240
00232
000001
69054
0,005
BJIKSS
sum of spec/margin
0,0075
0.0788
0.082
030235
(00255
00232
02024
C
clsst prod-of-tro
0012
0.0095
0.0081
0,0054
00021
00123
54100
00033
0,0052
sum of fru
prod of tro/marpin
00112
0.016
0.09
0.0096
0.0126
00117
00117
00083
00003
1000
0002
00100
00121
12100
69174
1000
0,0052
0,0022
imput grad noom
Linargin
num-of-fha/margeee
00147
0.0599
0.0186
00154
00085
0.019
10023
10024
T2200
00079
19100
00005
69224
0011
DJ0OST
neg-cutropy
0.163
0.169
0,122
0,005
01022
00184
01022
CAIKK4
0.006
0.0099
0.114
01105
parmm--oras
Baber-raa
00192
0.061
00155
00071
0.084
0.0077
00051
0O0
69173
00035
00000
00000
BJNKKS
0.0IES
nerm logit sum
0.0192
0.1533
0.0844
0.0109
00311
001
020138
00005
0,006S
logit
0.0155
0.084
0.115
00075
one epoch loss
path nomm/maagin
00169
0.0188
0.112
00054
0.146
0.0006
0.0056
00157
00023
00126
00224
BJIKSS
cross-entropy
0.021
0.0128
0.172
0,0135
80151
0014
02113
0,0K22
Miigua
0.0311
0.0006
09160
Maggma sharpness
0.099
0,0777
0.0126
00185
61110
0.0045
mincoomm distance)
00125
0.0611
0.071
0:007T
(1003
00051
BJIKES
num-step-OL OLl C.1--t-0.01 Joss
0.009
0.0994
0.071
0,0182
0.147
00081
0,222
C
0.1622
00135
0.012
num-step-00-.111 1-sso-
00101
0.0236
9,001
00148
0,152
0002
Lhipph sharpnoss mag
00108
0,2244
0.0488
0.0082
00003
00097
0,0201
00001
0.0062
Lillph pachaaes mag
0.1988
0.166
0.0844
0.0037
00228
0,055
0.0237
0.0044
1
C.IKS
pac-elarpuess-mag
0.0099
00011
pue-sharpnos--mg---
pacheyes-mag-in
0,022
0.0599
00061
0.0277
0.0711
0.0037
0.0037
00188
00139
0E131
0,077
0.9179
00005
1000
BJIKST
muchayes-mag-ne
0.0211
010777
0.0885
0.0037
000133
00134
0.179
00009
0000
C
opls
0.0177
0,12
opix sharpness
0,0822
0.0039
0,0066
0.1K
0000
rabo oplx ganssian
0.0055
0.0106
0.0755
0.0019
010156
0.01
0.0218
00001
BJIKSS
ratio opis ganssian (ief
0.239
0.1266
0.0635
0.003
0,173
0
0.017
00041
0.0054
grad-soise-tinal
0.09
0.0443
0.833
cral-nnise--ppoche
0.547
00165
0.0542
0.0316
00173
0.0514
0.478
0.0186
oracle 0.01
0.1788
0.0788
0.0153
0.0108
000800
0.0886
0.026
0,0066
0.8061
oracle 0.02
0.033
0.1355
0.0811
0.0138
0.0272
00167
0.0158
0.0033
C,KISS
0.0133
oracle
0.0292
0.0885
0.0321
0.0107
canonical andering
00111
0.004
0.0075
0.0038
0L0185
0.0108
0.0179
D.0027
0LIKAES
canonical ondering depth
0.018
0.0226
0.0208
0,0038
0.0198
0.0273
0,0202
0.0046
0.0076
Table 10: Complexity measures (rows), hyperparameters (columns) and the standard deviation of each entry mcasured over 5 runs with models trained on C-FAR-10. The standard deviation for is computed assuming that each hyperparamters are independent from each other. We see that all standard deviation are quite small, suggesting the results in of Table are statistically significant.
24

---

Published as a conference paper at ICLR 2020
D COMPLEXITY MEASURES
In this section, we look at different complexity measures. When measure is based on a general- ization bound, we chose so that the following true with probability 0.99 (we choose the failure probability 5 to be 0.01):
L L M
(15)
We also consider measures which do not provably bound the generalization error and evaluate those.
Note that almost all cases, the canonical ordering given based on some "common" assumptions are positively correlated with the generalization in terms of both 7 and V;; however, for optimizer, the correlation t is close to O. This implies that the choice of optimizer is only essentially uncorrelated with the generalization gap in the range of models consider. This ordering helps validate many techniques used by the practioners.
D.1 VC-DIMENSION BASED MEASURES
We start by restating the theorem (Bartlett et al., 2019) which provides an upper bound on the VC-dimension of any piece-wisc linear network.
Theorem (Bartlett et al. (2019)) Let F be the class of feed-forward networks with fixed com- putation graph of depth and ReLU activations. Let ag and q; the number of activations and parameters in layer Then VC-dimension of F can be bounded follows:
VC(F) s d
Σ (d- it 1)ga
log2
8e
ia logg
4e
jaj
j=1
Theorem 2 Given convolutional network for any 5 O, with probability 1 5 over the the training set:
dlog, (6dn) Ei= kPa0-1 +
log(1/6)
L L+ 4000
(16)
Proof We simplify the bound in Theorem usinn d' to refer to the depth instead of d:
VC(F)
Σ d - it 1)4s
logz
Se
ia,
loga
4e Σ jaz
d'
$ d' +
Σ dd' - +it 1)g:
logz
8e
i0;
im
d'
< d' + 2-2 logg
8e
iq;
Σ
+
1)4
i=1
< 3d' log2
8c
i0;
In order to extend the above bound to convolutional network, need present pooling layer
with ReLU activations. First note that maximum of two inputs can be calculated using two layers with ReLU and linear activations max(#1, x2) 21 ReLU(x2 -1). Now, since max-pooling at layer has kernel sizes k, we need [4 log, (K/)1 layers to present that but given that the kernel size of the max-pooling layer is at most size of the image, have
[4 log, (k() < [4 (ologg (n²)1 < [8logg (n)) (n))(n)
25

---

Published as a conference paper at ICLR 2020
Therefore, have d' 9d (o)2(n). The number of activations in any of these layers is at most n²c; since there are at most n² pairs neighbor pixels in an n x n image with e, channels. We ignore strides when calculating the upper bound since it only reduces number of activations at few layers and does not change the bound significantly.. Using these bounds ond', 0; and the equivalent network, bound the VC dimension follows:
VC(F) s 27d (n) log2 (8g(9olog2( (9 (9 logg (n))
Σ R +1)
< 729dlog2(n) (n)² log2 (6dn)
Σ GG
$ 729dlog, (6dn)
kg 10- +1)
For binary classifiers, generalization error be in terms of Rademacher complexity (Mohri al., 2012) which in turn can be bounded by 72 P2VVC/m (Kontorovich, 2016). Therefore, we can get the following" generalization bound:
I. S. f. 114A VC(F)
1og(1/0)
(17)
For multi-class classification, the generalization error can be similarly bounded by Graph dimension which is an extension of VC-dimension. A simple approach get a bound on Graph dimension is to consider all pairs of classes as binary classification problem which bounds the graph dimension by x² VC(F). There, putting everything together, we get the following generalization bound:
dogg (6dn)² Σd Ke + 1) +
log(1/6)
L L 4000
(18)
m
Inspired by Theorem 2, define the following VC-based measure for generalization:
2
pvo(fw) -4000k,
|4000K, dlogz (6dn) 3 Σ ( Vlog(1/))
(19)
Since some of the dependencies in the above measure are probably proof artifacts, we also define another measure that is nothing but the number of parameters of the model:
Aearaa
kea-l( +
(20)
D.1.1 MEASURES ON THE OUTPUT OF THE NETWORK
While measures that can be calculated only based the output of the network cannot reveal com- plexity of the network, they can still be very informative for predicting generalization. Therefore, define few measures that can be calculated solely based on the output of the network.
We start by looking at the cross-entropy over the output. Even though we used a cross-entropy based stopping criterion, the cross-entropy of the final models is not exactly the same the stopping criterion and it could be informative. Hence we define the following measure:
Peross-cntropy
((fw(X:).v)
(21)
m
where & is the cross-entropy loss.
The generalization gap is bounded by two times Rademacher Complexity, hence the constant 144.
26

---

Published as a conference paper at ICLR 2020
Another useful and intuitive notion that appears in generalization bounds is margin. In all measures that involve margin 7. we set the margin y to be the 10-th percentile the margin values on the training set and therefore ensuring by Σ 0.1. Even though margin alone is not a sensible gener- alization measure and can be artificially increased by scaling up the magnitude of the weights, it could still reveal information about training dynamics and therefore be informative. We report the following measure based on the margin:
1 7,2
Milmargin (fw) =
(22)
Finally, entropy of the output is another interesting measure and it has been shown that regularizing can improve generalization in deep learning (Pereyra al., 2017). With a fixed cross-entropy, increasing the entropy corresponds to distribute the uncertainty of the predictions equally among
the wrong labels which is connected to label smoothing and increasing the margin. We define the following measure which is the negative entropy of the output of the network:
1
m
K
Jneg entropy (Sw)
Pilil (og(::()))
(23)
m
f=1
where pi[i] is the predicted probability of the class j for the input data X;,
D.2 (NORM & MARGIN)-BASDD MEASURES
Several generalization bounds have been proved for neural networks using margin and norm no- tions. In this section, we go over several such measures. For fully connected networks, Bartlett and Mendelson (2002) have shown bound based on product of & norm of the layer weights times a 2d factor where 1 the maximum over hidden units of the &g norm of the incoming weights to the hidden unit. Neyshabur et al. (2015b) proved bound based on product of Frobenius norms of the layer weights times 2d factor and Golowich et al. (2017) was able improve the factor to vd. Bartlett et al. (2017) proved a bound based on product of spectral norm of the layer weights times sum over layers of ratio of Frobenius norm to spectral norm of the layer weights and Neyshabur et al. (2018a) showed a similar bound can be achieved in a simpler way using PAC-bayesian framework.
Spectral Norm Unfortunately, none of the above founds are directly applicable convolutional networks. Pitas et al. (2017) built on Neyshabur et al. (2018a) and extended the bound on the spectral norm to convolutional networks. The bound is very similar to the one for fully connected networks by Bartlett et al. (2017). We next restate their generalization bound for convolutional networks including the constants.
Theorem (Pitas et al. (2017)) Let B an upper bound on the Eg norm of any point in the input domain. For any B, B,T, 8 > O, the following bound holds with probability 1 5 over the training set:
(ABEL h vn((n2d)
2 IT / E
[w,- w W
+ In m
L S +
72m
(24)
Inspired by the above theorem, we define the following spectral measure:
W W
inip (fw) (84B (SABEL) ki + I In(4n2d)
T IW,1
In
m
(25)
The generalization bound in Theorem depends reference tensors W We chose the initial tensor as the reference in the above measure but another reasonable choice is the origin which gives the following measures:
(SABEL KivG + Vln(Andd)
TH
E
W W
+ In m)
Hspoc-orig (fw)
(26)
27

---

Published as a conference paper at ICLR 2020
Since some of the terms in the generalization bounds might be proof artifacts, we also measure the main terms in the generalization bound:
H W
W
j==
Mspec-init-main (fw)
(27)
722
IH
11 2ÿ=1
W
[W,
Pspec-orig-main (fw)
(28)
We further look at the main two terms in the bound separately to be able to differentiate their con- tributions.
W w
II I
Σ 1=1
11
Mopec init main (Jw)
(29)
Ih |W
11
f==1
W
Hspec-orig.miin (Jw)
(30)
72
II
|W
Mprod-of-spectmargin
(f (fw)
(31)
7/2
Uprod-of-spec (fw)
|W
(32)
i=1
W
Minosspec (fw)
(33)
W
Finally, since product of spectral norms almost certainly increases with depth, we look at the fol- lowing measure which is equal to the over squared spectral norms after rebalancing the layers to have the same spectral norms:
||
& 72
1/d
Muum of spectmargin (Jw) = =d
(34)
Psum of spec (fw) = dlI
1/d
(35)
Frobenius Norm The generalization bound given in Neyshabur et al. (2015b) is not directly appli- cable to convolutional networks. However, Since for each layer we have | kll2 < Ky Wills y and therefore by Theorem norms. Therefore, we define the following measure based on the product of Frobenius norms:
get upper bound the test error based product of Frobenius
frovmmmagin (fw) 11 |
(36)
72
d [ W.l
Mprod-of-fro (fw)
(37)
i=1
We also look the following measure with correspond to sum of squared Frobenius norms of the layers after rebalancing them to have the same norm:
1/d
W.
Ussum of freffargii (fw) = d
F
(38)
?2
Msum-offfro (Fw) =d
||
(39)
28

---

Published as a conference paper at ICLR 2020
Finally, given recent evidence the importance of distance to initialization (Dziugaite and Roy, 2017; Nagarajan and Kolter, 2019b; Neyshabur et al., 2018b), we calculate the following measures:
Mfrobenius-distanee (fw)
W: will
(40)
Pdist-spoc-init (fw)
W; w
(41)
In case when the reference matrix h = 0 for all weights, Eq (40) the Frobenius norm of the parameters which also correspond distance from the origin:
mparam-norm (yprram-nommsw)
Σ 1=1
|
(42)
Path-norm Path-norm was introduced in Neyshabur et al. (2015b) as an scale invariant complexity measure for generalization and shown to be a useful geometry for optimization Neyshabur et al. (2015a). To calculate path-norm, we square the parameters of the network, do forward pass on an all-ones input and then take square root of sum of the network outputs. We define the following measures based on the path-norm:
Mpaath montt-mnmm (fw) Ee [wa(
(43)
7/2
Mpath-norm (fw) = E (w)
(44)
where w w is the element- wise square operation the parameters.
Fisher-Rao Norm Fisher-Rao metric was introduced in Liang et al. (2017) as a complexity mea- sure for neural networks. Liang al. (2017) showed that Fisher-Rao norm is a lower bound on the path-norm and it correlates in some cases. We define a measure based on the Fisher-Rao matric of the network:
(d+ + 1)²
m (f.(
(FFisee-RRoo (fw)
Σ
(45)
m
where i is the cross-entropy loss.
D.3 FLATNESS-BASED MEASURES
PAC-Bayesian framework (McAllester, 1999) allows us to study flatness of a solution and connect generalization. Given a prior P is chosen before observing the training set and posterior Q which is distribution on the solutions of the learning algorithm (and hence depends on the training set), we can bound the expected generalization error of solutions generated from Q with high probability based on the KL divergence of P and Q. The next theorem states simplified version of AAC-Bayesian bounds.
Theorem
For any > O, distribution D. prior P, with probability - over the training set, for any posterior Q the following bound holds:
Exnq [L(fv)] Ew-Q [E(Fv]]
KL(QII + log (T)
(46)
2(m 1)
P and Q are Gaussian distributions with P = Mup, Ep) amd Q = N Eq), then the KL-term can be written as follows:
KI(( Er)) =r))= tr (Ep Σo) + (iq pr) "Pp' (nQ - -pr) - In del Ep
det ΣQ
29

---

Published as a conference paper at ICLR 2020
Setting = (W, and P (Nww,, similar to Neyshabur et al. (2017), the KL term will ww
2n² However, since a belongs to prior. if we search to find value for we need adjust the bound reflect that. Since we search over less than 20000 predefined values of a in our experiments, we can use the union bound which changes the logarithmic term to log (20000m/d) and we get the following bound:
be simply
lw 10a
(u.-N [L(fw+u)] S En-rru [[(fwtu] +
log( =
+ 10
(47)
m
Based on the above bound, we define the following measures using the origin and initialization as reference lensors:
||w
w0
Mpac-bayes-init (fw)
+ log
10
(48)
40
[w]]
12
Mpuc bayes orig (fw)
log(
) 10
(49)
4
where a is chosen to be the largest number such that (u,a11 (((fwtu) S 0.1.
The above framework captures flatness in the expected sense since we add Gaussian perturbations to the parameters. Another notion of flatness is the worst-case flatness where we search for the direction that changes the loss the most. This motivated by (Keskar et al., 2016) where they observe that this notion would correlate to generalization in the case of different batch sizes. We can use PAC- -aycssan framework to give generalization bounds for worst-case perturbations as with
well. The magnitude probability 1 8/2. Applying union bound all parameters, get that with probability 1- 6/2 the magnitude of the Gaussian noise is most a a o parameters of the model. Therefore, we can get the following generalization bound:
Gaussian variable with with variance o² is at most a
where w the number of
[w w log (2w/a)
+ log( 20 + 10
Eus. [L]] S max L(fw+u) + |s,
(50)
m
Inspired by the above bound, we define the following measures:
ww w0ll (2w)
Psharpness (n (Sw)
log( ) + 10
(51)
4a²
Haharpncss-orig (fw) [ 12 log(2w)
m
+ log(
+ 10
(52)
4a
8
where is chosen to be the largest number such that max i((s+tu) < 0.1.
To understand the importance of the flatness parameters a and a, we also define the following measures:
Ppac-bayes-llaness (fw) 1
(53)
1
Piharppesss Hltmess (fw)
(54)
a2
where a and a are computed as explained above.
Magnitude-aware Perturbation Bounds was chosen so that for each parameter the ratio of magnitude of perturbation to the magnitude of the parameter is bounded by constant 100 Following similar approach, we can choose the posterior for parameter i in PAC-Bayesian framework to be .A
The magnitude of perturbation in (Keskar et al., 2016)
//((/ (w,, o²2 w2,22 e?). Now, substituting this
ThTee actually used slightly different version which is combination of the two perturhation bounds calculated here. Here, for clarity, we decomposed it into two separate perturbation bounds.
30

---

Published as a conference paper at ICLR 2020
in the Equation equation D.3 and solving for the prior N(w,, oz) that minimizes the KL term by setting the gradient with respect to of to zero, KT. can be written as follows:
0²2 +
2KL(Q w log
w no--wll w0ll + -
log (o w - + e²
1=1
2 + + + 1) w w 112 /
log
2 + r²2 w w
Therefore, the generalization bound can be written follows
13/w + log( ( + 10
Di=1 log
Eu [L(f S Bu [[(fw+u)
22
-
(55)
m
where us ~ (0 + e²), c= le and o' is chosen to be the largest number such that
Eu [[Jw+u) S 0.1. define the following measures based on the generalization bound:
2 + (o + 1) w w w/122/0 log( 8
hayes hayes mug init (Sw)
log
10
(56)
2 + 0²2 W; w
i=1
2 + 1) || 1| /w
Mmnc-hayes.mag.onig (Sw)
Σ log
+ log( 5 10
(57)
62 + wy w/
We also follow similar arguments before get a similar bound the worst-case sharpness:
62 (w- + log( m1) + 10
D log
En [[[s++u]]= S
max Wallga/eu
i(Sw+u)+
m
(58)
We look at the following measures based on the above bound:
impe-sharppess-mg--ii (fw)
1
Σ
w
log
2 + (a + logg (log(2w/6)) (2w/8)) [w -w- w
+ log(
m
+ 10
4
62 a wi w/ll2
i=1
(59)
w
2 + (a + log((w//
/2: /
w l//
m
/lpac sharpness mag urig (Sw) =
log
+ log
+ 10
4
2 + a² wi w!!
5
(60)
Finally, we look at measures that are only based the sharpness values computed above:
1
Pl buyes mag- flai (fw)
(61)
Psharppesss mag (fw)
(62)
a2
where and are computed as explained above.
D.4 OPTIMIZATION-BASHR MEASURES
There are mixed results about how the optimization speed is relevant to generalization. On one hand we know that adding Batch Normalization or using shortcuts in residual architectures help both opti- mization and generalization and Hardt et al. (2015) suggests that faster optimization results in better generalization. On the other hand, there are empirical results showing that adaptive optimization methods that are faster, usually generalize worse (Wilson et al., 2017b). Here, put these hypoth- esis into test by looking at the number steps to achieve cross-entropy 0.1 and the number of steps needed go from cross-entropy 0.1 to 0.01:
31

---

Published as a conference paper at ICLR 2020
Histeps 0.1 0.1-loss (fw) #steps from initialization to 0.1 cross-entropy
(63)
(aatleps-01-0.01-66 (fw) #steps from 0.1 0.01 cross-entropy
(64)
The above measures tell us if the speed of optimization at early late stages be informative about generalization. We also define measures that look at the SGD gradient noise after the first epoch and the end of training cross-entropy 0.01 test the gradient noise can be predictive of generalization:
Agrad-tolso-cpochh (fw) Var(x.y) (Vwl(fw (X).9))
(65)
Hgrad noise final (fw) Var(x.)) (V ww ((w(((((WW))) ()) where w' is the weight vector after the first epoch.
(66)
E ALGORITHMS
We first lay out some common notations used in the pseudocode:
f: the architecture that takes parameter and input æ and map to f(x; which is the predicted label of æ
2. 0: parameters
3. M: Some kind of iteration; M1: binary search depth; M2: Monte Carlo Estimation steps;
M3: Iteration for estimating the loss
4. Ø {(r,, }o) the dataset the model is trained on; B uniformly sampled minibatch from the dataset.
Both search algorithm relies on the assumption that the loss increases monotonically with the per- turbation magnitude around the final weight. This assumption is quite mild and in reality holds across almost all the models in this study.
Algorithm Eccuraat
1: Inputs: model /, parameter 0, dataset 2, estimate iteration M
2: Initialize Accuracy =
3: for episode i
MM do
4: B ~ sample 9
5: Accuracy += [18] Σ, 8(y; = (B)
6: end for
7: return Accuracy/M
Note that for finding the sharpness a, we use the cross-entropy as the differentiable surrogate object instead of the 1-0 loss which is in general not differentiable. Using gradient ascent brings another additional challenge that is for converged model, the local gradient signal is usually weak, making gradient ascent extremely inefficient. To speed up thie process, we add a uniform noise with range being [-Onew/ Nw: /new/ (new/Nw) wNw] to lift the weight off the flat minima where N is the number of parameters. This empirical greatly accelerates the search.
Further, for magnitude aware version of the bounds, the overall algorithm stays the same with the exception that now covariance matrices at line of Algorithm become as diagonal matrix con- taining wf the diagonal; similarly, for line 12 of Algorithm the weight clipping of each w; is conditioned on Trew wil, i.e. clipped to [-onew (us], Tnew [.l]] Here wy denotes the 7th parameter of flattened w.
32

---

Published as a conference paper at ICLR 2020
Algorithm 2 Find for PAC-Bayesian Bound
1: Inputs: f. 80. model accuracy ł, target accuracy deviation d, Upper bound d max, Lower bound
Fmin- M1, M2. M3
2: Initialize
11 do 4: Onew = (Tmax + min 1/2
3: for episode i
5:
==0
6:
for step j = to M2 do
7:
A 8g +V(0, new
8:
i=ê+ i EstimateAccouacy(( f Dnews M3)
9:
end for
10:
i i/M₂
11:
d = |e é
12:
if d < or maxx min 66 then
13:
return nnw end if
14:
15:
if d > then
16:
maxx Onew
17:
else
min Onew
19:
end if'
end for
Algorithm Find for Sharpness Bound
Inputs: f. tg. loss function L, model accuracy é, target accuracy deviation Upper bound
mmax: Lower bound m M1, M2, Ms, gradient steps M4
2: Initialize
3: for episode i = to M1 do
4: Onew = (Ømax + min)
5: {= xc
6: for step
M2 do
7:
0 = 0 + (1 /2)
8:
for step k 0 to MA do
9:
B ~ sample (
0 + Volo
11:
if |||| o new then
12:
Tnee T
13:
end if end for i f= min(é, EstimatttcccAcr 0 2, M,)
14:
15:
16:
end for
d 18-6) i
18:
if d < 6a or Fmax - Jmin < Eg then
19:
return Tnew end if
20:
21:
if d
d then
22:
σ Fmax = Onew
23:
else
24:
Umin = Fnew
end if
26:
end for
33


Reviews:
[{"review_id": "SJewlC1jFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis 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.\n\nI agree with the choice of stopping according to cross entropy.  One thing not done in Section 5 is a discussion of\nvariation:  choice of initialisation and the impact of stochasticity in the optimisation. \n\nAppendix 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.\n\nSo, 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.\n\nInteresting observations in Appendix A.1, as are some of the discussions in Sections 7, 8, 9.\n\nGiven 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.\n\nMINOR 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.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJxvboKicr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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. \n\nThe results of the authors' experiments are highly valuable to the research community. I recommend to accept.\n\n*********************************************************************************\n\nTechnical comments for the authors: \n-Please rewrite or elaborate on the first two paragraphs of section 6 for clarity.\n\n-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.\n\n-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.\n\n-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.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "ByxTlM6e5H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\nThe 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 …).\nThe writing of the paper is clear and easily understandable. Besides, I believe that the study is relevant to ICLR conference.\n\nHowever, I believe the level of the paper is marginally below the threshold of acceptance and therefore would recommend to reject it.\n\nThe 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.\n\n1) 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.\n\n2) 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.\nSimilarly, 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.  \n\n3) 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.\n\n4) 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.\n\n\nI would like the authors to clear the following points :\n- 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)\n- Could you please also answer Point 4 ?\n- 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 ?\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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)