Can We Use Gradient Norm as a Measure of Generalization Error for Model Selection in Practice?
Authors: Haozhe An
Haoyi Xiong
Xuhong Li
Xingjian Li
Dejing Dou
Zhanxing Zhu
Venue:  (2021)

Abstract: The recent theoretical investigation (Li et al., 2020) on the upper bound of generalization error of deep neural networks (DNNs) demonstrates the potential of using the gradient norm as a measure that complements validation accuracy for model selection in practice.  In this work, we carry out empirical studies using several commonly-used neural network architectures and benchmark datasets to understand the effectiveness and efficiency of using gradient norm as the model selection criterion, especially in the settings of hyper-parameter optimization. While strong correlations between the generalization error and the gradient norm measures have been observed, we find the computation of gradient norm is time consuming due to the high gradient complexity. To balance the trade-off between efficiency and effectiveness, we propose to use an accelerated approximation (Goodfellow, 2015)  of gradient norm that only computes the loss gradient in the Fully-Connected Layer (FC Layer) of DNNs with significantly reduced computation cost (200~20,000 times faster). Our empirical studies clearly find that the use of approximated gradient norm, as one of the hyper-parameter search objectives, can select the models with lower generalization error, but the efficiency is still low (marginal accuracy improvement but with high computation overhead). Our results also show that the bandit-based or population-based algorithms, such as BOHB, perform poorer with gradient norm objectives, since the correlation between gradient norm and generalization error is not always consistent across phases of the training process. Finally, gradient norm also fails to predict the generalization performance of models based on different architectures, in comparison with state of the art algorithms and metrics.

Under review as a conference paper at ICLR 2021
CAN WE USE GRADIENT NORM AS A MEASURE OF GENERALIZATION ERROR FOR MODEL SELECTION IN PRACTICE?
Anonymous authors Paper under double-blind review
ABSTRACT
The recent theoretical investigation (Li et al. 2020) on the upper bound of general- ization error of deep neural networks (INNS)) demonstrates the potential of using the gradient norm as a measure that complements validation accuracy for model selection in practice. In this work, we carry out empirical studies using several commonly-used neural network architectures and benchmark datasets to under- stand the effectiveness and efficiency of using gradient norm as the model selec- tion criterion, especially in the settings of seper-parameter optimization. While strong correlations between the generalization error and the gradient norm mea- sures have been observed, we find the computation of gradient norm is time consuming due to the high gradient complexity. To balance the trade-off be- tween efficiency and effectiveness, we propose to tion (Goodfellow) 2013) of gradient norm that only computes the loss gradient in the Fully-Cone Colle-Coneette Layer (FC Layer) of DNNs with significantly reduced com- putation cost (200~20,000 times faster). Our empirical studies clearly find that the use of approximated gradient norm, as one of the hyper-parameter search ob- jectives, can select the models with lower generalization error, but the efficiency is still low (marginal accuracy improvement but with high computation overhead). Our results also show that the bandit-based or population-basee algorithms, such as BOHB, perform poorer with gradient norm objectives, since the correlation between gradient norm and generalization error is not always consistent across phases of the training process. Finally, gradient norm also fails to predict the gen- eralization performance of models based on different architectures, in comparison with state of the art algorithms and metrics.
accelerated approxima-
INTRODUCTION
Generalization performance of deep learning through stochastic gradient descent-basse based optimiza-
tion has been widely studied in recent work (Li ct al. 2020 Chatterjee| [020 Negrea et al.) 2019
Thomas et al. 2019 Zhu et al. 2019: Hu et al.] 2019; Zhang et al. 2016 Mou et al. (2077). These studies initialize the analysis from the learning dynamics' perspectives and then extend to the up- per bound estimation generalization errors (Mou et al. (017). More recently, researchers have shifted their focuses onto providing some theoretical empirical measures
generalization per-
formance (Li et al. 2020; Negrea et al. 2019 Thomas et al. 2019 Cao & Gu 2019 He et al. 2019 Frei et al., 2019) with respect deep architectures, hyper- parameerrs,,,ss, data distributions. learning dynamics and so on. This work studies the use of generalization performance measures (Li et al.
2020 Negrea et al. 2019) for model selection purposes (Cawley Talbot. 2010)).
Prior to the endeavor of deep learning, the generalization gap has been used as a straightforward measure. Given a of N training samples F1, I2, .z.... xN ). a deep learning model and a loss function L(0;ar) based on the sample the generalization gap G is defined as
1 N
(())) E L(0:2) x
Σ (():2.).
where X' is defined the distribution of data, and Ex~x L(0: x) refers to the expected loss. To quantify the generalization gap. validation or testing samples have been frequently used to measure the expected loss (Kohavi al. 1995). Such that given validation/testing dataset with M samples

---

Under review as a conference paper at ICLR 2021
{yi, V2, U....... yMr. ). the empirical generalization gap IMr is estimated as
1 (ar M Σ (():)))
Σ C(0:2.).
(2)
and M- Gas = G. However, due to the limited amount of samples, the accurate estimation of generalization gap is not always available (Cawley & Talbot 2010). It has been evidenced that performance tuning based on validation set frequently causes overfitting to the validation set (Recht al. 2018) in deep learning settings.
Rather than the use of empirical generalization gap, some advanced measure has been proposed LLi al. 2220 Negrea al. 2019 Thomas al. 2019) to provide data-dependent characterization on the generalization performance for deep learning. For example, TThoma et al. (2019) derived the Takeuchi information criterion (TIC) using the Hessian and covariance matrices of loss gradients with low-complexity approximation. They then propose to use TIC as an empirical metric that cor- relates to the generalization gap. As the calculation of TIC relies on the use of validation set, TIC for deep learning is a posterior measure. Further, Negrea et al.) (2019) improved mutual informa- tion bounds for Stochastic Gradient Langevin Dynamics via some data-dependent measure. More specifically, the squared norm of gradients have been used as the data-dependent priors to tightly bound the generalization gap through measuring the flatness of empirical risk surface.
More recently, the squared norm of gradients over the learning dynamics has been studied as the measure to upper-bound the generalization gap (Li et al.] 2020) Negrea et al.) 2019). All above methods connect the generalization gap of deep learning to the gradients and Hessians of loss func- tions. While Thomas et al. (2019) is a posterior measure relying on the validation datasets, the two studies (Li et al., [2200] Negrea et al. 2019) provide "prior" measure that uses training datasets. More specifically, Li et al. (020)) proves that the generalization error is upper bounded by the em- pirical squared gradient norm along the optimization path. Formally, they show that, given a model trained with samples in dataset X' {I1, zn for total of T iterations using a C-bounded loss function is used, the theoretical generalization gap of the DNN 0r is bounded as follows,
G(0r) S 2/2C n
T
E
2 ge
(t)
(3)
where (1) = Es, 1 EL_ [V;((=-,,,;))) is the empirical squared gradient norm the gth iteration, Yt is the learning rate and o, indicates the standard deviation of Gaussian noise in the stochastic process. Their result directly shows that empirical squared gradient norm along the opti- mization path is good indicator of model's generalization ability. Therefore, we are interested in using this signal as a criterion in model selection, so as to find an optimal set of hyper-parameters
Our Contributions. In this work, we follow the theoretical investigation in ( et al. 2020) and try to use the squared gradient norms (GN) over the optimization path as a data-dependent generaliza- tion performance measure for DNN model selection. In an empirical manner, the proposed metric GN here should be able to measure the generalization gap of the DNN model 0r. which has been trained with T iterations and N training samples, as follows
T GN Σ
(VL0)))) N Σ
(4)
where V. 24) refers to the loss gradient using the model of the th iteration and the 8th training sample in {x1, ..,...,, ). Based on the data-dependent measure GN, our work make three pieces of significant technical contributions as follows
(1) Approximated Gradient Norm (AGN) as an accelerated and low-complexity approximation to GN. Despite the fact that GN can measure the generalization error of a DNN model, the time consumption for GN is high, due to the complexity of gradient estimation using every training sam- ple in every iteration. To lower the computational complexity, we propose Approximated Gradient Norm (AGN) that only uses the summation of loss gradients of the Fully-Conne CollecCodee (FC) Layer in DNN by the end of every epoch (rather than every iteration) as an approximation of GN. Further- more, the calculation of FC Layer gradient per sample could be further accelerated by Goodfellow
2

---

Under review as a conference paper at ICLR 2021
2013) with extremely low costs. Our empirical evaluation finds that, over various DNN models trained with different papper-prameters, the metrics Gf( and (fr behave identically with respect to empirical generalization gap GM (fr). This approximation makes it feasible to carry out experiments that evaluate the effectiveness of GN for model selection.
(2) To validate the correlations between generalization performance and AGN(Or), we carry out extensive experiments using various deep neural networks, such as Multi-Layer Perception (MLP), LeNet (LeCun et al., 1998). and ResNet (He et al. 2006)) on top of benchmark datasets including MNIST (LeCun et al. 20T0), Fashion-MNIST (Xiao et al. 2017). SVHN (Netzer et al. 201T), and CIFAR (Krihhvssyy al. 2009). Observation 1: It has been observed that, when the models are well-fitted (i.e., with low training loss or high training accuracy), (GN((Or) well corresponds with the empirical generalization gap (9r) while models with lower/higher (G) are consis- tently with lower/higher Gas (8r) and better/poorer generalization performance. On the other hand, when models are not well-fitted or namely under-fitted, either due to the use of inappropriate hyper- parameters or a training process not converged (e.g.. T" is small), the correlations between GM (0r) and (Or are not always consistent while the direction of correlation somtimes is even opposite to the theoretical investigation in Li et al. (2020) and Eq. (3).
(3) To understand the effectiveness and efficiency of using (Gr for model selection, we extend our experiments to use (0r) as an objective for hyper-paramert parameter selection, under both black- box optimization (Escalante et al. 2009, Loshchilov & Hutter 2016) and bandit-based search (Li et al., 2017; Falkner et al.) 2018) settings. Observation 2: We find that, through the combina- tion with training or validation loss, AGN(OT) can help black- box optimization algorithms, such as particle swarm (PSO) (Escalante et al. 2009) or covariance matrix adaption based evolving strate- gies (CMA-ES) [oshchilov & Hutter 2016). search the models thyper-parameteen
with equivalent or marginally better performance than using validation loss/aceuracy as the search objective. The training procedure can somehow avoid the potential overfitting to the validation set (Recht et al.] 2018). However the use of (ON(Or) requests more prior knowledge (additional parameters) to loss and (GN(OT) in the combined objective during the
balance the weights of training/validation search, which might be sensitive for model selection. Observation 3: Further, our research finds that candit-based search algorithms, such as Bayesian optimization over HyperBand (BOHB) (Falkner) eet al. 2018), cannot work well with gradient norms. Because BOHB selects and drops models dur- ing the learning process with respect to the intermediate measures on performance, while within an end-to-end learning process (G, (for 0,, 62. f3 ..,..., 0T) cannot always provide consistent mea- sures on the generalization performance. Observation 4: In addition to hyper-parameter selection for deep learning, our experiment finally finds that (Gr fails to predict the the generalization performance of the models based different deep architectures, in comparison to some state of the art algorithms and metrics (Jiang et al. 2019 Nagarajan & Kolter 2019).
We believe the most relevant studics to this work are those done by Li al. 2020); Negrea et al. (2019): Thomas et al. (2019) (that measure the generalization performance of DNN using deriva- tives, such as gradients and Hessian matrices, of the loss), and the contribution made by our work is unique. Compared to Thomas et al. | (2019), the measure AGN studied here is also a data-dependent metric to characterize the generalization performance. AGN uses gradients and avoids the use of validation sets, while Thomas et (2019) is based on Hessian matrices and relies on validation data. Compared to Li et al. (2020); Negrea et al. (2019). our work studies the feasibility of using gradient norms over learning process for model selection in empirical settings, where we first provide AGN as a low-complexity implementation to accelerate the computation of gradient norms, then we con- duct extensive results to demonstrate the pros and cons of using gradient norms or AGN for model selection in two major pyper-parameter search settings. Our result demonstrates the potentials but also limitations in the adoption of current theoretical results (Li et al. 2020 Negrea al. 2019) as an objective for model selection.
2 GRADIENT NORM AND ITS APPROXIMATION
Given a DNN model fr that has been trained with T iterations, the straightforward way to compute GN(0r) is to first collect and store the weights of the model for every iteration during the training process (i.c., 0, .2..... 0r). then compute the gradient for every training sample (N in total) on every model (T in total) through backpropagation (BP) over the whole DNN for N x T times. In
.....,.r
3

---

Under review as a conference paper at ICLR 2021
practice, such computation cost is far too high. In this section, present (G) low- complexity approximation to (f and then discuss the approximation performance.
2.1 AGN: APPROXIMATED GRADIENT NORM
We propose AGN((,) as a low-complexity approximation to accelerate the computation of (Or) using acceleration strategies as follows.
AGNI9)
While DNNs frequently composes hundreds of layers, (GT approximates to (0r) using the gradients of last Fully-Connected (FC) Layer of DNNs.
Depth-wise Acceleration.
3.00
0.10
3.05
501
Sample-wise Acceleration. While the compu- tation of GN()T) needs to run time-consuming BP for every training sample, (Gr(Or) uses the lowccomplexity per-sample gradient esti- mation algorithm (Goodfellow) 2015) to com- pute the gradients of FC layers without BP.
GMLd)
GR/9))
ML. on MNIST
(b) MLP on MNIST
AGNE80
250
Epoch-wise Acceleration While the computa- tion of GN(@T) aggregates the gradient norms for every iteration, AOT(Or) approximates to GN(OT) via the summation of squared norms of gradients collected by the end of every epoch. Given the batch size B for every itera- tion, each epoch consists of z gradient descent iterations, the learning process with T iterations takes TE N epochs for completion, and Oz for T = 1,2,.... N by the end of every epoch.
300
GNL++)
125 1400 (M41)
(c) LeNet.5 MNIST
(d) LeNet-5 MNIST
N
(e) ResNet- Fashion Maitiiio-MNISTTTTaa MaiSStyalddinnnn positive correlation hetween (N((T)) and (G)(Or)) in larger neural networks).
TB refer to the model obtained
Besc 2a1
In this way, we propose to compute (GN as follows
TBAN Σ
N
||
AGN(OT)=
N
VC
(0
(I) ResNet-56 on CIFAR- (validating the positive correlation be- tween GN(er) ) and (Gr( ( in larger neural networks).
(5)
where VCFC((;; .r) refers to the gradient of FC layer based on the model 0 and the sample x
Figure 1: Comparison between GN( and (Or) in terms of effectiveness to reflect generalization error. In Fig. Ia to Fig. [d. we pick 9 sets of random hyper- parameters for MLP and 12 sets for LeNet-5. We then train the model for 40 epochs and plot their results. For the two architectures we have tested on MNIST, both AGN(Or) and GN(0r) exhibit identical trends when generalization error plotted against them respectively. Strong positive correlation observed between GN and AGN each setting as well, with Pearson correlation cocfficients 0.962 for MLP and 0.987 for LcNet-5. We carry additional experiments using deeper neural network models in Fig. [Te and Fig. [T] order ver- ify the existence strong positive correlation between AGN(Or) and CN We follow a piecewise learn- ing rate decay policy in these experiments. Thus, there are three plots for each ResNet setting.
and is accelerated by using the algorithm pro- posed by Goodfellow (015)).
2.2 APPROXIMATION PERFORMANCE
We discuss the approximation performance of AGN(OT) to GN(OT) from efficiency and ef- fectiveness perspectives, in comparison with validation accuracy, as ways of generalization performance measurements.
Effectiveness Comparison. We find that AG)(Or) preserves the effectiveness of GN( as a generalization performance indi- cator. In Figure [] we illustrate the comparison between (OT) and GN(OT) using 9 Multi-Layer Preceptors (MLP) models and 12 LeNet-5 models trained using 9 and 12 sets of random hyper-parameters MNIST datasets. For every model here, we train the model with 40 epoch, measure the generalization gap using the validation set, and estimate GN(Ar) and AGN(0r) respectively. In Figure [ [a) and (c), we plot GN(0r) and AGN(Or) of these models against their generalization gaps. It shows that, despite the different scales of the two measures, the trends of GN(07) and AGN((rr) behave identically with respect
4

---

Under review as a conference paper at ICLR 2021
to the generalization gaps. Further, we correlate G and (G) for every model and demonstrate the correlations in Figure (b) and (c). We carry out additional experiments on larger neural networks. The results in Fig. Ic and Fig, Tr also validate that the correlations between (Nr) and (0r) are strong, significant, and consistent.
Efficiency Comparison. We find that the computation of (fT( much faster than GN(OT) while it still consumes significantly more time than using validation set for the measurement of generalization performance. In Figure 2 we plot the time consumption per epoch of the three generalization performance measurements, i.e., AGN(OTT,
AGV
Lac
Figure 2: Comparisons in computation time for the three general- ization performance measurements.
GN and validation accuracy, using LeNet-5, ResNet-20, and ResNet-56 on (parts of) MNIST, SVHN, and CIFAR-100 datasets. To simulate the settings of realistic hyper-parameter search, we collect time consumption of the three measurements using full and reduced (20%) datasets separately. The comparison results show that (OT( is 220x~~0,489x faster than GN(Or) while it still consumes 95%~ 1845% more time than using validation accuracy. Note that, for the comparison, we originally collect the time consumption of GN(Or) for single iteration, and then rescale the figures to one epoch.
In summary, we conclude that AGT(OT) is a low-complexity but tight approximation to GN for generalization performance measurement.
3 USING AGN AS A GENERALIZATION PERFORMANCE INDICATOR
To understand the correlations between AGN and generalization performance, we propose to measure Ga (Or) and (GT of a wide range of DNN models using ResNet-20, ResNet-56, ResNet-110, and DenseNet100x24 (Huang al. 2017) based on CIFAR-I0 datasets. For each architecture, we train 32 DNN models, each of which is with a random set of pyper--arameters and the same number of epochs. Specifically, the model is well-fitted or under-fitted. With sufficient number of training iterations and appropriate settings of pprrmpaaraettes, the models are usually trained to well-fit the training datasets with low training loss and high training accuracy. However, due to the lack of convergence or inappropriate setting, some models are under-fitted even using a large number of iterations.
hope to discuss the correlations in two scenarios
Reskes20
Reohet-35 36
Observation The correlations between (GN(Or) and (fr) are not consistent from models to mod- els. AGN(OT) is positively cor- related with (0r) when models are well-fitted. Otherwise, op- posite trend is observed for under- fitted models. Fig. illustrates that the inconsistent correlations be- tween AGT(Or) and (0r( ap- pear in all these architectures. For each architecture, 32 random hyper- parameter configurations were cho- sen to train 32 models, and we ob- tain each model's AGN(Or) at the end of 160 epochs as well as its gen- eralization error, plotted in Fig. 3a We observe that the scatters exhibit trend that looks like an inverted checkmark. This shape indicates that the correlation between AGN(Or) and generalization error behave differently based model con-
Betive S0L
AGAIA!
(a) Generalization error against AGN shows inverted checkmark trend.
(b) Positive correlation between (GN(0r) and (0r( ) for well. fitted models. Kocter
lockee
SAY
Batton 50%
(C) Negative correlation between (GN(Or) and Gas (Or) ) for under fitted models. Figure 3: Inconsistent correlation between empirical squared gra- dient norm and generalization error depending on how well model is trained.
5

---

Under review as a conference paper at ICLR 2021
vergence. Due to this inconsistent behavior, it is not always possible to use (6r as an indicator of generalization performance unless the models are well-fitted.
Positive correlation between (fT and G (fT) for well-fitted models We identify the models
with top 50% training accuracy. These models have fitted the training set with at least 88% accuracy and hence they are well-fitted models. These models show positive correlation between (GT
and Gar (Or), as shown in Fig. 3b It is feasible to use (O) as an alternative generalization performance indicator, in addition to the validation loss/accuracy, under these settings. This observa- tion coincides with the theoretical findings in Li et al. (2020) and Eq. (3). However, the p-values for Pearson correlation in Fig.3(b) are 0.336, 0.039, 0.036, and 0.053 respectively. These values overall indicate weak positive correlation between generalization gap and AGT( close to or lower than 0.05. This weak correlation is most likely a result of that GN does not work very well a metric in practice, since we have already shown the experimental results that indicate good approximation of (Gr to GN(OT) in Fig.
three of them are
Negative correlation between (GT( and Gar (Or) for under-fitted models In contrast, we also identify the models with bottom 50% training accuracy. Such models are under-fitted models due to inappropriate settings of hyper-parameters
lack of convergence in the training process. Fig. [c shows that (Or) is negatively correlated with (0T) for under-fitted models. We however do not consider this observation conflicts with the theoretical findings in Li et al. (2020) or Eq. (3), be- cause Li et al. (2020) actually studied the learning dynamics of DNN in asymptotic settings, where authors derived the upper bound of generalization error using gradient norms when T - co (the training procedure has been well converged and models are well-fitted). Nonetheless, it still seems to be surprising that there is a negative correlation between AGN((r, and 9M (0r). We offer an intuitive explanation here. The trend is that gradient norm gradually decreases as training proceeds while generalization gap increases (also reported in Li et al.] (2020)). Across models with differ- ayper-parameters, these two quantities could possibly change their magnitude at very different speed. A model that remains under-fitted throughout training has low generalization gap (it makes almost random guesses on both training and test sets), but the training samples are likely to con- sistently produce large gradients. As a result, under-fitted models with smaller generalization gaps have larger (Or( contributing to the negative correlation shown in Fig. 3c
4 USING AGN FOR MODEL SELECTION
In this section, we investigate the feasibility of using (GN as a generalization performance indicator for model selection. We consider two possible applications of AGN(Or). where the first one is to incorporate (fr( as an objective for hyper- search for a fixed architecture, and the second one is using AGT to predict cross-architectural models' generalization error.
4.1 USE CASE 1: HYPER-PARAMETE
SEARCH FOR DEEP NEURAL NETWORKS
To address the fitness issues from Observation 1, we propose to include the training loss and/or validation loss as the search objectives as follows
N
Objective (Or)) = a AGN(OT) +
(6)
M
ObjectiveAcN+valC (0T) = a AGN(OT) M
Σ [(0r:
where (#1, Zy.... .N) } and (v1, Vy..... yar} refer the training and validation sets respectively, and a is weight to balance the
loss and AGN(0r).
We test the effectiveness of the above two search objectives by conducting hyper-paramend search using ResNet-20 and ResNet-56 on MANSS, SVHN, and CIFAR datasets respectively. The results of Dashion-MNIST and SVHN are found in the appendix. On top of the two objectives in Eq. (6), we try multiple settings of and adopt two commonly-used black-box optimization algorithms, including CMA-ES (Loshchilov & Hutter 2016 and PSO (Escalante et al., 2009), for hyper-parameter search with computation budget of 5, 5.120 GPU xpocchs where we take a reduced training set with 20% training samples (Cubuk et al., 2019) to accelerate the search procedure. The search space is with Batch Size [32. 1000), Learning Rate [1 1 0.50], Momentum [0, 0.99], and Weight Decay [5 x 10 0.05], while initial settings are Batch Size 100, Learning Rate- 0.01, Momentum 0.6, and Weight Decay 0.0005.

---

Under review as a conference paper at ICLR 2021
Table I: Results for CIFAR-10 and CIFAR-100 using CMA-ES and PSO.
CIFAR-10
CIFAR-100
Method
ResNet-20
ResNet-56
ResNet-20
ResNet-56
Default
91.7011..1
92.97=0.118
66.73=0.56
70.37:10.46
CMA-ES(Val)
91.86:10.13
92.74-10.20
68.2810046
67.08:10.68
PSO(Val)
92.26:10.09
93.15=10.09
67.85=10.25
72.11
CMA-BBIAAGN++Train.c00000
92.22:+0.09
93.97=0.28
64,90+0.20
71.30++0.17
OMA-EESJAGGN-TTaiinced0001
90,46110.09
91.59-10.19
64.62.10.04
72.37
CMA-EE5AAGGNNTTainnccc00000000
90.36.10.04
93.75.10.18
66.3711038
72.1810.21
CMA--ES/AGGN+-Valoo=0001)
91.94+0.07
93.09=#0044
64.64=0.50
69.14=0.17
CMA-TESAAGGNN-olocc000000
91.56:10.14
92.92-10.15
66.65
10.04
CMA-TES/AGGN-Vaal.c...000))
92.08
93.77
66.31
72.49
#SONAGGN++Train.c=000555
90.56=0.11
91.66+0.06
62.09=0.26
09.28:0.16
PSOTAGGN+TTraino00000011
91.51+0.004
91.32++0110
68.46
0.555
PSO0AGNN+TTainncc0000555
91.92++0.14
91.99+0.31
64.91+0.17
67.05-+0.43
PSO(AGNN+Val.c=0..1)
90.38+0.03
92.55+00.06
66.57+0.16
67.92+0.399
PSO(AGN++Val,o00005)
91.67++0.18
91.76++0.05
65.53+0.35
71.42+0.13
PSO(AGN++al,c=00000
90.66+00088
93.76+00.17
67.02++0.12
71.51+0.19
Default
setting For every pair of dataset and the DNN architecture, there exists "default" set of hyper-parameters that has been frequently used/suggested by practitioners, or published in their official releases. For example, the paraeepas including Batch Size = 128, Learning Rate= 0.1, Momentum = 0.9, and Weight Decay 10 have been frequently used to train ResNet-20 on CIFAR- 10. In the tables following, "Default" refers to models trained with the default hyper-parameter configuration.
Observation 2.When combining AG with training or validation loss as search objectives, black-box optimization algorithms search the hyper-parameters with performance marginally better than using validation accuracy only, whilst models can avoid overfitting to the validation set (Recht et al. 2018). However, such practice requests prior knowledge (i.e., in Eq. (6)) to balance the two factors in the search objective. Table Table appendix) present the results of comparisons, where we include the testing accuracy of the models trained using full training set and the hyper-parameter. found by black-box optimization algorithms. For every set of searched hyper-parameters, the model has been trained and tested three times with error bars estimated. For both CMA-ES and PSO algorithms, the two objectives can help search the models with significantly better or worse testing accuracy than the one selected by using validation accuracy as objectives.
Furthermore, the use of these two objectives can fix the issues of overfitting to the validation set for model selection. For example, the result of ResNet-20 on Fashion in Table 4 has a lower test set accuracy than the model trained with default using validation set This phenomenon is likely due to overfitting the validation set since ResNet-20 has a rather large capacity to learn and Fashion-MNIST is relatively easy dataset. In contrast, AGN+Train or AGN+ Val leads to slightly better result than the default model, significantly outperforming using validation loss. The final model selection highly depends on the choice of a. We however do not know such prior in advance, while trends of performance over are not consistent or obvious. In this way, we can conclude that there exists potentials of using AGN(0r) as part of search objectives for black-box ppper-paraeete optimization when the prior knowledge on the settings of a is known. Otherwise, the use of (Or) might even hurt the syper-parameter search, no matter whether it is combined with training or validation loss.
Observation 3. AGN(OT) sometimes cannot work well with bandit-based hyper-parameter search, as the correlation between AGN(Orr and generalization performance is not always con- sistent during the training process from under-fitted to well-fitted status. We carry out the similar hyper-parameter search experiments using BOHB algorithm under the same settings (search space, initial values, and computation budget). For fair comparison, BOHB normalizes (G) in the objectives (and the setting of is slightly different from the black-box optimization settings), since BOHB has to compare AGN(0,) of models obtained from different iterations t of the training pro- cess while the scale of AGN(O.) varies significantly.
7

---

Under review as a conference paper at ICLR 2021
Table 2: Results for ResNet-20 on Fashion-MNIST, CIFAR-IO, and CIFAR-I00 using BOHB.
Fashion-MNIST
CIFAR-I0
CIFAR-I00
Default
93.34.10.07
91.70.10.16
0.57
BOHB (Val)
92.58+00.64
90,46=0.65
66.02=0.32
BOHB (AGN+Train, a=0.9)
91.87=00.51
89.73=0017
66.53=0.37
BOHB (AGN+Train, a=0.5)
89.25++200
85.02=0.19
62.19=0.44
BOHB (AGN+Train, a=0.1)
93.41=0.117
91.18=0.09
59.67=0.10
BOHB (AGN+Val, a=9.
93.01=10.20
85.8
63.30=0.41
BOHB (AGN+Val, a=0.5)
82.53+99.58
89.07=0.47
66.73=0.33
BOHB (AGN+ Val, o=0.1)
93.27+00.06
90.61+0.16
64.05-0.09
In 2 we present the testing accuracy of the models that are trained using the hyper-parametern searched by BOHB with the objectives. The results show that, though it is able to outperform the default one (such ResNet-22 on Fashion-MNIST using AGN+Train, a 0.1), using (G,) within BOHB cannot produce better results than the default setting in most cases. Since the cor- relation between AGN( and (f.) is not always consistent over the optimization path, AGN gives BOHB inaccurate feedback on model generalization performance early stage of training- Consequently, BOHB tends to early terminate some good models and continue training the inferior ones. This results in deteriorated model performance through the bandit-based search.
4.2 USE CASE 2: CHOSS-ARCHITECTURAL GENERALIZATION ERROR PREDICTION
We evaluate series of complexity measures to test their ef- fectiveness of predicting generalization error using the public dataset provided in a competition at NeurlPS 2020 named "Pre- dicting Generalization in Deep Learning" (Jiang et a..). The de- scriptions of experimental setup and public dataset are available in the official document of competition details. Briefly, we use 150 trained VGG-like architectures (along their datasets used datum and
Table 3: Cross-architcctural gen- cralization error prediction scores complexity measures. VC di- mension (Vapnik & Chervonenkis 2015), Jacobian Norm with respect to intermediate layers (Jiang et a Distance of trained weights from ini- tialization (0o) (Nagarajan & Kolter 2019), and Sharpness of local min-
during training, namely SVHN and CIFAR-10) predict their generalization error with the listed theoretical com- plexity measures in Table 3 The predictions are evaluated us- ing conditional mutual information. The possible scores are be- tween 0 and 100. A higher score indicates that the complexity measures is able to more accurately and consistently predict the generalization error. The results in Table 3 show that although (GN(OT) is able to outperform some baseline theoretical com- plexity measures in predicting generalization error, its effective- ness is largely limited. The ineffectiveness of using (GN to perform cross-architectural generalization error prediction implies it is also ineffective to use GN(rr) in practice since we have shown that AGN(Or) approximates GN((r) very well.
ima Jiang et al. 2019)
Method
Score
VC Dimension Jacobian Norm AGN
0.019598841
2.061258975
3.955067687
Distance to Go
4.921479998
Sharpness
10.6671 1 1408
5 CONCLUSION
In this paper, we have studied the feasibility of using AGN(OT), an approximated form of squared norms of loss gradients over optimization path (Li et al. 2020). to measure generalization er- ror in practice. We find the correlations between (G and Gas are completely oppo- site for under-fitted and well-fitted models, where the positive correlations between the two vari- ables found in well-fitted models coincide with the theorems by Li al. (2020). Furthermore, the use of (G)(Or) to complement the validation accuracy as the objectives can marginally improve the performance of hyper-parameter optimization, however the computational overhead caused by (Gr) estimation and the lack of some prior knowledge makes such paradigm neither efficient nor effective. In the meanwhile, the same set of objectives does not bring any improvements for bandit-based algorithms such as BOHB, partially due to the inconsistent correlation between the ob- jective and generalization performance throughout the training phase. As a result, using the gradient norms for model selection in practice remains challenging due to the high computation overhead (using the approximated version is up to 18 times slower than standard training) and limited effec- tiveness. Our experiments also show that (Gr cannot effectively predict generalization error given different architectures. In conclusion, we do not recommend using GN(0r) or AGN(Or) for model selection in practice.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In Advances Neural Information Processing Systems, pp. 2546 22664,554,,0 2011.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pp. 10835-10845, 2019.
Gavin C Cawley and Nicola LC Talbot. On over-fitting in model selection and subsequent selee- tion bias in performance evaluation. Journal of Machine Learning Research, ((uul):079-2207, 2010.
Sat Chatterjee. Coherent gradients: An approach to understanding generalization in gradient descent-based optimization. In International Conference Learning Representations, 2020.
URL https::////// /tttps:://peereviiee httpeeiwwwwwwweeeeeeeeeeeeeeeeee www.:ennne/oooummdeeeeeee.... (ttp://rrmmn.dryyyYYO
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc Le. Autoaugment: Learning augmentation strategies from data. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 113-123, 2019.
Hugo Jair Escalante, Manuel Montes, and Luis Enrique Sucar. Particle swarm model selection. Journal of Machine Learning Research, 10(Feb):405 440, 2009.
Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter opti- mization at scale. In International Conference on Machine Learning, pp. 1 1437-1446, 2018.
Spencer Frei, Yuan Cao, and Quanquan Gu. Algorithm-depender generalization bounds for over- parameterized deep residual networks. In Advances in Neural Information Processing Systems, pp. 14769-14779, 2019.
lan Goodfellow. Efficient per-example gradient computations. arXiv preprint urXiv:1510.000 2015.
Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems, pp. 1141-1150, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Wenqing Hu, Zhanxing Zhu, Haoyi Xiong, and Jun Huan. Quasi-potential implicit regularizer for the loss function the stochastic gradient descent. arXiv preprint meXiv:/901. 9905006544, 2019.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4705 2017.
Yiding Jiang, Pierre Foret, Scott Yak, Behnam Neyshabur, Isabelle Guyon, Hossein Mobahi, Gintare Karolina, Daniel Roy, Suriya Gunasekar, and Samy Bengio. Predicting generalization in deep learning, competition at neurips 2020. URL /ttp:s///sssseeeeeeeeeeeeeeeees
gow.ge...oooo..... com/view/ /
oggl2020/home aathussr-
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv: 1912.02/7. 2019.
Ron Kohavi al. study of cross-validation and bootstrap for accuracy estimation and model selection. In International Joint Conference on Artificial Intelligence, volume 14, pp. 1137-1145. Montreal, Canada, 1995.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.

---

Under review as a conference paper at ICLR 2021
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-25 1998.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. AT&T Labs [On- line]. Available: http://yann. lecun. com/exdb/mmisst 2:18, 2010.
Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. In International Conference on Learning Representations, 2020.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit- based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1 (816656655668 (8166566866 6816, 2017.
Iyya Loshchilov and Frank Hutter. Cma-es for hyperparameter optimization of deep neural networks.
ICLR Workshop, 2016.
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng. Generalization bounds of sgld for non-
convex learning: Two theoretical viewpoints. arXiv preprint arXiv: 2017.
Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arXiv preprint arXiv:190..0162, 2019.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy- Information-tteeortiic generalization bounds for sgld via data-dependent estimates. In Advances in Neural Information Processing Systems, pp. 11013-11023, 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do difar-10 classifiers generalize to cifar-10? 10? arXiv preprint S.c.v:18806.044553 2018.
Valentin Thomas, Fabian Pedregosa, Bart van Merriënboer, Pierre-Antoine Mangazol, Yoshua Bengio, and Nicolas Le Roux. Information matrices and generalization. arXiv preprint arXiv:1906.07774, 2019.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pp. 11-30. Springer, 2015.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Aushion-mnist a novel image dataset for benchmark- ing machine learning algorithms. ArXiv, abs/1708.077477 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 1xXiv:1611.03524 2016.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochas- tic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In Proceedings of International Conference on Machine Learning, pp. 7654-7663, 2019.
10

---

Under review as a conference paper at ICLR 2021
A EXPERIMENTS
A.1 1 EXPERIMENTAL SETUP
Datasets and Data Augmentation We briefty introduce the benchmark datasets used in this paper and the data augmentation methods we applied when loading the data.
Fashion-MNIS" (Xiao al. 2017) is benchmark dataset similar the popular MNIST dataset (LeCun et al. 2010). It has 70,000 grayscale images in the size of 28 x 28, dividing into 10 classes. The training set has 6,000 images from each class while the rest make up the test set. We normalize the input data as done in common practice.
SVHN is a benchmark dataset composing house-number signs in street level images (Net- zer et al. 2011). We use the cropped digits dataset for training and testing. We normalize the input data as done in common practice.
The CIFAR-10 dataset has 6,000 examples of each of 10 classes and the CIFAR- 100 dataset has 600 examples of each of 100 non-overlapping classes (Krizhevsky et al. 2009). We apply standard data augmentation the same way as the Pytorch official examples on CÍFAR- 10 and CIFAR-100 classification tasks. Specifically, we pad the input images by 4 pixels, and then randomly crop a sub-region of 32 x 32 and randomly do horizontal flip. We normalize the input data done in common practice.
Reduced Dataset To reduce the expensive computation cost for training a model for multiple rounds, train the model on the reduced dataset when searching for hyper-parameters, where only a random but fixed 20% subset of the standard dataset participates in the training. Training on the reduced dataset gives us set of syper-parameters which is then used train separate model with the standard training set. The newly trained model is then validated on the standard test set. We report the final test performance in the main paper. The strategy of using a reduced dataset for search is also used by Cubuk et al. (2019).
ResNet Training Details For different architectures of ResNet, we train them for 160 epochs. For the default baseline model, we set the initial learning rate to be 0.1 and decay it by 1/10 and 1/100 at epoch 80 and 120 respectively. Momentum is set be 0.9 and weight decay is 0.0001. The default batch size is 128. The loss function used for all experiments in the paper is cross entropy loss.
Blackbox Optimization Setup The process of blackbox hyper-parameter optimization split into 4 rounds. We train 8 models with different sets of hyper-parameters in parallel in one round. At the end of each round, a blackbox optimization algorithm is run based on the model score com- puted by using validation set using our metric. The algorithm generates the next 8 sets of prper-parameters to search for the optimal ones. We use two blackbox optimization algorithms for hyper-parameter search, which are Covariance Matrix Adaptation Evolution Strategy (CMA- ES) (Bergstra et al. (011) and Particle Swarm Optimization (PSO) (Escalante et al. 2009).
BOHB Hyper-parameter Search Setup We BOHB (Falkner et al., 2018 test how our proposed objectives work with bandit based training hyper-parameter optimization algorithms. For all ResNet architectures. the minimum budget is 40 and maximum is 160. We pick 17 to be so that the total number of training epochs using BOHB would be the same as that using blackbox optimization algorithms. This ensures fair comparison across the two types of hyper-parameter optimization algorithms.
A.2 NOTES ON TIME CONSUMPTION ANALYSIS
Interpretation of Figure. 2 in the Main Paper Each bar the plot represents the total time consumption in epoch, including time spent forwarding the data, updating the model parameter with backpropagation, and computing GN(OT) or AGN(OT) if needed. The results are obtained by running models multiple times 1080Ti GPUs.
We define GPUxepoch as iterating through the training set for one round on one GPU. Note that 1 GPUxepoch corresponds to different amount of wall clock time depending on the
GPUXepochs
11

---

Under review as a conference paper at ICLR 2021
0.6
3.5
train test
train
0.5
3.0
test
2.5
Log6
2.0
0.3
1.5
0.2
1.0
0.2
0.0
0.0
0
20
40
60
80
100
120
140
160
5
10
15
20 Epoch
25
30
35
40
Epoch
(a) Default
(b) RS(Val)
train
train
0.4
test
test
Loss
Loss
0.3
0.1
40
80 Epoch
100
140
160
20
40
100
120
140 160
Epoch
(c) CSVal)(Val)
(d) CMA ESAAAN+TTainnnooa
Figure 4: Training behavior of ResNet-20 Fashion-MNIST with the default learned hyper-paramelers from various methods, "RS" refers to random search.
architecture, dataset as well as batch size. Figure 2 in the main paper shows some examples of the wall clock time that GPUxepoch costs under those settings.
When running hyper-parameter search algorithms, we keep GPUxepochs as constant variable to ensure each algorithm iterates through the training set the same number of times. As mentioned in the main paper, we set the total budget to be 5,120 GPU xepochs for all hyper-parameter search algorithms. Blackbox optimization algorithms used in this paper, namely CMA-ES and PSO, ex- plores 32 sets of hyper-paramete parameters whereas BOHB, as more efficient search algorithm with early termination of poorly performing models, explores 36 sets of syper-parameters in total.
Specific time cost for hyper-parameter search. The time cost for hyper-parameter search using the reduced training set with validation accuracy as the criterion for ResNet-56 on CIFAR-10 856s model on average. When AGN is used to complement validation accuracy, the average is 3,633s for one model.
A.3 DISCUSSION ON TRAINING BEHAVIOR
Fig. shows the training behavior ResNet-20 on Fashion-MNIST with four different hyper- parameter settings. We analyze how the training and test losses vary under these settings and obtain the observations below.
AGN Helps Reduce the Generalization Gap First, Fig. 4a indicates gradually enlarging gap between the training loss and testing loss. This phenomenon likely due to that we train ResNet-20 models for 160 epochs, which is easy to overfit the Fashion- dataset. As result, there exists a generalization gap, where the training loss is very close to zero, but test loss is about 0.325. In contrast, when AGN and training loss are used combined objective in CMA-ES hyper-paramette optimization (Fig. (d). the final generalization gap is 0.259, which is 20.3% lower than the gener- alization gap using the default byper-parameter This decrease in the magnitude of generalization
12

---

Under review as a conference paper at ICLR 2021
Table 4: Results for Fashion-MNIST and SVHN using CMA-ES and PSO.
Fashion-MNIST
SVHN
Method
ResNet-20
ResNet-56
ResNet-20
ResNet-56
Default
93.341:0.07
93.21=0024
95.67:10.02
96.11=0.14
CMA-ES (Val)
93.35+0.008
93.03-10.76
9..2611.088
95.90=0.44
PSO (Val)
91.13+0.32
92.04:10.49
96.0510.10
94.78=0.24
CMA-ES (AGN+Train, a=0.05)
93.10=10.08
93.62:10.08
95.52:10.99
95.84-1.13
CMA-ES (AGN+Train, a=0.01)
93.38:10.18
93.39-10.06
95.67110.02
94.39
CMA-ES (AGN+Train, a=0.005)
92.61
93.39:10.20
95.48
94.51
CMA-ES (AGN+Val, o=0.1)
93.27+10.04
93.43:10.08
96.2440.04
95.59
CMA-ES (AGN+Val, o=0.05)
93.42++0.16
93.45+0.17
95.63
95.96+
CMA-FS AAAGN+Val,
93.19+0.19
93.60+0.05
95.97+00.1
96. 96.13+0.07
PSO (AGN+Train, o=0.05)
93.29++028
92.96+0.11
91.87+0024
95.70=0.17
PSO (AGN+Train, ==0.01)
93.21+0006
92.90+0.03
95.79++0.3
96.04+0.02
PSO (AGN+Train, a=0.005)
93.3640.11
92.95+10.03
95.55
96.14=0.02
PSO 10.++Vll.==0.111
93.91-10.04
93.82=0008
95.33+0.13
93.90=0.30
PSO (AGN+Val, a=0.05) o00000)
92.35++0.11
93.46+1.077
96.10=0.12
95.78=0.11
PSO (AGN+Val, a=0.005)
93.09110.10
93.0
95.52.1..07
96.39-1..3
gap demonstrates the effectiveness of using AGN to complement hyper-parameter optimization al- gorithm.
AGN Helps Avoid Overlitting the Validation Set An interesting observation is that using the method HS1 + Val to search for hyper-parameters yields worse test set performance than the model trained with default hyper-parane syper-parameters. This is likely because the model is able to overfit the val- idation set after multiple rounds of training during hyper-parameter optimization. Consequently, the model cannot generalize well on the test set. In contrast, when AGN is used in the metric, can further improve the baseline model with default hyper-pan parameers by 0.21% (the test perfor- mance using default hyper-yppaaee pppee-prramtter 93.34 + 0.07 whereas using EMAA-ESAAGNTrrinn.c.l is 93.51 + 0.19.
AGN Helps Hyper-parameter Optimization Algorithm Find More Stable Settings When compared to Fig. 4b and Fig. 4c
Fig. 4d shows that the incorporation of AGN enables the search al- that gives rise to better and more stable performance on the
gorithm to find a set of test the model is being trained. The magnitude of test loss in both RS(Val) and CMA-ES(VVl) can be 10 times bigger than training loss or even worse, whereas CMA-ES(AGNN+Taa of typer-parameters that keeps test loss relatively close to training loss throughout, The test loss of method CMA-ES(Val) can be as high as 7 in the midst of training. However, the loss curve is far more smooth in the case of CMA-ES(AGNY Arain,, shown in Fig. 4d
finds a set
13


Reviews:
[{"review_id": "zd9Sh8CeT2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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 empirically investigates the sum of gradient norms as a measure to determine the generalization abilities of a neural network. The approach is inspired by the theoretical work of Li, et al. 2020 which showed that the generalization gap can be upper bounded by a function of the sum of the full gradient norms of the training path. \n\nThe paper empirically investigates the gradient norm as a measure to predict the generalization gap of neural networks. For that, the paper proposes an approximation of the sum of the full gradient norms that is more computationally efficient. The paper shows that this approximation is, albeit being in a different scale, strongly correlated with the full gradient measure. The paper then continues to openly investigate the properties of the measure and finds that it is only partially correlated with the generalization gap. When used for hyperparameter tuning, it can slightly improve the results. Lastly, the paper shows that the measure is not effective in predicting the generalization ability of DNNs with different architectures. \nThe empirical evaluation is sound (although limited to only fairly simple image classification problems), the results are interesting, and I particularly regard the honesty about the negative results. I think that this is a valuable study. \n\nWhat is missing though is a discussion of these findings and a placement of these results into the wider context of generalization in deep learning. Do these results imply that the gradient norm is not a sufficient measurement? Or can the gradient norm be an effective measure in certain situations? The paper hints at that, saying that for well-trained networks the measure correlates more strongly with the generalization gap. \n\nA particularly interesting discussion here would be the relation to flatness measures which have been found to be strongly correlated with the generalization gap [1,2,3,4,5]. It seems, the gradient path norm does not necessarily outperform those measures but might be related. I.e., if a model is in a very flat minimum, at least for a part of its training path (the last part) it will have been in that flat region and thus gradient norms would be small. \n\nIn summary, the paper presents an interesting empirical analysis and makes some technical contributions in the form of the proposed AGN measure. However, the missing in-depth discussion limits the contribution of this paper. Since such a discussion would go beyond the minor edits for a CRC, I am not convinced this paper is ready for publication, yet.\n\nMore out of interest than as a critique of this paper, I would like the authors to clarify how the gradient norm could be a meaningful measure to determine generalization in general. Li, et al. 2020 have shown a modified PAC-Bayesian bound that uses the gradient norm over the path, but it seems that most of the heavy lifting there is done by assuming a distribution dependent (i.e., perfect) prior - please correct me if I am wrong here. It seems to me then that the gradient norm can at best be a part of the explanation for good generalization (i.e., the one that relates to flatness and thus robustness). To illustrate my point, assume your data is drawn with x uniform in R and y = cos(v*x) + eps, where eps is some Gaussian noise. That is, the data is a noisy cosine function. Our model class consists of functions f_w (x) = cos(w*x) with a single parameter w. The optimal model has parameter w^*=v. Now the error surface of that model space if we use, for example, the squared loss, has lots of local minima of various depths and one global minimum at w^*=v (both in terms of empirical risk and true risk). If we now initialize our model randomly, it can start at a steep part of a local minimum and jump into the next and from there on to the next with fairly large gradients until it ends up (hopefully) in the global minium, where it will not escape (all also depending on the learning rate, of course). In this hypothetical (and arguably quite artificial) example, the path from most initializations to the global minimum would have large gradient norms. If we instead initialize close to a local minimum, the gradients will be small and if we start close enough to the minimum, the model will not escape. It will remain in that locally flat area with very small gradients. Thus, the gradient norm of the path is very small, yet the generalization error is large (the gap then depends on the actual sample and can be either small or quite large). My question now is: am I misunderstanding Li et al. or is my example too simple? Could the authors give some intuition on how the gradient norm could explain generalization?\n\n\n[1] Jiang, et al. Fantastic generalization measures and where to find them. ICLR 2020.\n[2] Keskar, et al. On large-batch training for deep learning: Generalization gap and sharp minima. ICLR, 2017.\n[3] Petzka, et al. Relative Flatness and Generalization in the Interpolation Regime. arxiv prerpint, 2020.\n[4] Neyshabur, et al. Exploring generalization in deep learning. NIPS, 2017.\n[5] Tsuzuku, et al. Normalized flat minima: Exploring scale invariant definition of flat minima for neural networks using PAC-Bayesian analysis. arxive preprint, 2019.\n\n\n------ After Discussion -------\nI had an interesting discussion with the authors that clarified some important points. I came to the conclusion that the topic is interesting and the study is valuable, however, not yet conclusive. Consequently, the paper is not ready for publication, yet. Thus I have lowered my score by one. I hope the authors continue this work, since I'm convinced a complete empirical study on the impact of the gradient norm along the training path is insightful and a valuable contribution to the community.", "extra_scores": {}, "extra_text": {}}, {"review_id": "h5pb0oyBc6", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "Summary:\nThis paper studies the gradient norm as a measure of generalization in deep learning. The authors first an approximation to the gradient norm (GN) that is the norm of the gradients for only fully connected layers (AGN). Then they empirically evaluate the correlation between AGN and GN as well as GN and the generalization error. In Section 2.1, the authors conclude that AGN is highly correlated with GN and both are correlated with generalization error. In Section 3, the authors conclude that the correlation between AGN and generalization error is not consistent in a wider family of models. In Section 4, authors propose to use AGN for model selection and conclude that AGN is not good for model selection unless the hyperparameter for mixing AGN with another metric is optimal.\n\nPros:\n- Recently there has been huge interest in measures of generalization error. Studies of this sort even with mixed results can be helpful in better evaluation of individual proposed measures.\n- Gradient norm is a measure proposed by prior published work (Li et al. (2020)) with theoretical justifications without extensive empirical evaluations which is done in this work.\n\nCons:\n- The main limitation of this work is that the authors propose an approximate measure to gradient norm (AGN), then the results are mostly negative for AGN in Section 3 and 4. But this doesn’t necessarily mean gradient norm is a poor measure of generalization. The link in Section 2 is only empirically shown for a MNIST, Fashion-MNIST, and CIFAR-100 datasets and there is no theoretical reason to justify this. So I don’t find the results to be conclusive about gradient norm.\n- Gradient norm can be computed efficiently in much less time than the claimed time in the paper. See [1] for a framework that computes gradient norm efficiently and [2] for general dot products between gradients.\n- Empirical results in Fig 1 are the main support of the paper for using the approximate gradient norm in the next sections. It is not clear if the conclusions from MNIST, Fashion-MNIST, and CIFAR-100 datasets would hold for other datasets. Especially that the conclusion in future sections seems to be negative for the application of AGN.\n\nAdditional notes:\n- In abstract given that only an approximation to gradient norm is computed the following statement cannot be made: “...gradient norm also fails to predict the generalization performance”.\n- Fig 1, a-d: the norm of the gradient on MNIST should tend to zero by the end of the training as the loss tends to 0. Despite that, the range of values for AGN and GN in this figure is way above 100. In contrast, GN in Fig 1.e is below 1 which matches the expectation. Have models in a-d converged?\n- The authors could also look into recent work on “robust” generalization measures [3]. AGN seems not to be a robust measure based on Figure 3. The authors could study better approximations to gradient norm and their robustness.\n\nTypos:\n- focuses -> focus\n- some advanced measure -> measures\n-  Thomas et al. (2019) did they derive TIC? Or only try it out?\n- correlates to -> with\n-  Thomas et al. (2019) is a posterior measure -> TIC is a\n- our work make -> makes\n- technical contributions -> contribution\n\n[1] Dangel, F., Kunstner, F., & Hennig, P. (2019). BackPACK: Packing more into backprop. arXiv preprint arXiv:1912.10985.\n[2] Faghri, F., Duvenaud, D., Fleet, D. J., & Ba, J. (2020). A Study of Gradient Variance in Deep Learning. arXiv preprint arXiv:2007.04532.\n[3] Dziugaite, G. K., Drouin, A., Neal, B., Rajkumar, N., Caballero, E., Wang, L., ... & Roy, D. M. (2020). In Search of Robust Measures of Generalization. arXiv preprint arXiv:2010.11924.\n\n============\nAfter rebuttal:\nI thank authors for their response. I share concerns with others reviewers and I highly encourage authors to consider answering questions suggested by Reviewer 3 at the end of their discussion. I believe a systematic study of gradient norm is interesting but this work does not provide a solid set of answers. As such, I'm reducing my rating to 4.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "YuUvrJcsl_C", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "In this paper, they provide the empirical studies  to understand the effectiveness and efficiency of the use of the gradient norm (induced by [the Li et al., 2020]) as the model selection criterion. To speed up the calculation process the of the gradient norm, they first propose an approximate gradient norm (AGN) based on the depth-wise, sample-wise and epoch-wise accelerations.  Their empirical studies find that the use of AGN can select the models with lower generalization error, but fails for bandit-based or population-based algorithms, and fails to predict the generalization performance of models based on different architectures.  In conclusion, they do not recommend using (approxiamte) gradient norm for model selection in practice.\n\nPros:\n\n-1:  In this paper, they propose an approximate gradient norm (AGN) based on an accelerated approximation (Goodfellow, 2015) of gradient norm that only computes the loss gradient in the Fully-Connected Layers, which can significantly reduce the computation cost (200∼20,000 times faster) than the original one. They also find in empirical evaluations that AGN and GN behave identically with respect to empirical generalization gap.\n\n-2: They carry out extensive experiments to validate the correlations between generalization performance and AGN, and find that, when the models are well-fitted, AGN well corresponds with the empirical generalization gap, but for the  under-fitted models, the correlations  between empirical generalization gap and AGN are not consistent.\n\n-3: They use AGN  as an objective for  hyper-parameter selection under both black\u0002box optimization and bandit-based search, and find that,  AGN may help black-box optimization algorithms with an additional hyper-parameter, but fails to bandit-based or population-based algorithms, and fails to predict the generalization performance of models based on different architectures.\n\nCons:\n\n-1: In Figure 1(a) and (c), we can find that for  Multi-Layer Preceptors (MLP), the trends of AGN behave identically with respect to the generalization gap, but, in Figure 3, they show that for ResNet-20, ResNet-56, ResNet-110 and DenseNet 100*24, the correlations between AGN and generalization gap are not consistent. These results confuse me, can we draw a new conclusion that, when the model is simple,  the  correlations  between AGN and generalization gap are consistent, but for complex models, the correlations are not consistent.  I want to see the additional experiments on the analysis of the MLP in Figure 3, I am surprised why ignoring the MLP in Section 3 and Section 4.\n\n-2:  In Figure 1(e) and (f), one can see that the Pearson coeff  for epoch 81-120 are higher than that of the Epoch 1-80 and Epoch 121-160. This result seems a bit counterintuitive. Why the middle epoch can obtain the highest Pearson coeff?", "extra_scores": {}, "extra_text": {}}, {"review_id": "6nfM2UmeeF7", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "Authors of the paper conducted many numerical experiments on the relationship between generalization and their proposal on an approximated form of gradient norms. \n\nThe motivation for their study is the article Li et al. (2020) which discovers deep relation between generalization and gradient norms. However, as far as I can understand, what the article Li et al. (2020) precisely studies is a noisy version of gradient descent (stochastic gradient Langevin dynamics), and without the noisy assumption their theoretical analysis is not valid. Based on these, I am not convinced that studying the relation between generalization and a *variant* of gradient norms with respect to the *true* SGD is a proper topic that the ML community should consider. Many experiments in the gap should be carried on.\n\nMoreover, in 'contribution' (3) the authors make a digression discussing generalization and hyperparameter searching, and mark as one of the major contribution. The conclusion is that their 'approximated gradient norm' is not well-behaved and has many constrains in application, so I would mark these as merely observations rather than 'contributions'. I think this part is rather incomplete.\n\nTo me the article seems to be an experimental report on what has been observed during the numerical trials. It might be a good submission to workshop, but not qualify for ICLR main conference.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,

Thank you for your submission. The reviewers all appreciated the direction of research and the message that GN can be a bad measure of generalization. That said, they all shared concerns regarding the strength of the conclusions that can be drawn from your work.

I encourage you to address their comments and submit a revised version to a later conference.

---------------------------------
Reviewer 1 wanted to update their review but couldn't so here is the update:


Some more details on my original concerns

Thank you for your detailed responses. I wanted to add more details to the ones not discussed by other reviewers.

- Regarding the speed of computing the gradient norm, I still don't agree that the computation cost is high. Figure 6 in the Backpack paper shows the cost of computing individual gradients at most 4x the cost of a single backprop not 100-1000x. In reference [2] that I gave, there is also a cheaper approximation discussed with computational costs detailed in Appendix B. As long as the computation of gradient norm is comparable with the cost of a single back-prop it should be cheap enough to run all your experiments.

- Regarding the conclusions in the paper. Thank you for giving more details. Adding those explanations to the paper would help. I personally missed some of those takeaway messages.

Overall, I strongly recommend either strengthening the link between GN and AGN or using better approximations. As well as better discussing the conclusions. Of course in addition to the suggestions by other reviewers.
Decision: Reject