Robustness to Pruning Predicts Generalization in Deep Neural Networks
Authors: Lorenz Kuhn
Clare Lyle
Aidan Gomez
Jonas Rothfuss
Yarin Gal
Venue:  (2021)
Keywords: Generalization
Pruning
Generalization Measures

Abstract: Why over-parameterized neural networks generalize as well as they do is a central concern of theoretical analysis in machine learning today. Following Occam's razor, it has long been suggested that simpler networks generalize better than more complex ones. Successfully quantifying this principle has proved difficult given that many measures of simplicity, such as parameter norms, grow with the size of the network and thus fail to capture the observation that larger networks tend to generalize better in practice.
In this paper, we introduce a new, theoretically motivated measure of a network's simplicity: the smallest fraction of the network's parameters that can be kept while pruning without adversely affecting its training loss. We show that this measure is highly predictive of a model's generalization performance across a large set of convolutional networks trained on CIFAR-10. Lastly, we study the mutual information between the predictions of our new measure and strong existing measures based on models' margin, flatness of minima and optimization speed. We show that our new measure is similar to -- but more predictive than -- existing flatness-based measures.

Under review as a conference paper at ICLR 2021
ROBUSTNESS TO PRUNING PREDICTS
GENERALIZATION IN DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Why wver-paraettrrized neural networks generalize as well as they do is central concern of theoretical analysis in machine learning today. Following Occam's 's ra- zor, has long been suggested that simpler networks generalize better than more complex ones. Successfully quantifying this principle has proved difficult given that many measures of simplicity, such as parameter norms, grow with the size of the network and thus fail to capture the observation that larger networks tend to generalize better practice. In this paper, we introduce a new, theoretically mo- tivated measure of network's ' simplicity: the smallest fraction of the network's s parameters that can be kept while pruning without adversely affecting its training loss. We show that this measure is highly predictive of model's 's generalization performance across a large set of convolutional networks trained on CIFAR- 10. Lastly, study the mutual information between the predictions of our new sure and strong existing measures based on models' margin, flatness of minima and optimization speed. We show that our new measure is similar but more predictive than existing catness-based measures.
INTRODUCTION
The gap between Saaming-theoretie generalization bounds for highly overparameterized neural net- works and their empirical generalization performance remains a fundamental mystery the field (Zhang et al., 2016 Jiang et al.) 2020: Alleen-hhu et al.) 2019). While these models are already being successfully used in many applications, improving our understanding of how neural networks perform on unseen data is crucial for safety-critical use cases. By understanding which factors drive generalization in neural networks we may further be able to develop more efficient and performant network architectures and training methods.
Numerous theoretically and empirically motivated attempts have been made to identify general- ization measures, that is. properties of the trained model, training procedure and training data that distinguish models that generalize well from those that do not (Jiang et al.) 2020). number of generalization measures have attempted to quantify Occam's 's razor, i.e. the principle that simpler models generalize better than complex ones (Neyshabur et al., 2013) Bartlett et al.] (017). This has proven be non-trivial, as many measures, particularly norm- based measures, grow with the size of the model and thus incorrectly predict that larger networks generalize worse than smaller networks. Other approaches have tried to establish a connection between model compression and generaliza- tion (Arora et al. 2018 Zhou et al., 2019). While both of these approaches are theoretically elegant and yield tighter bounds than bounds that are based on the size of uncompressed networks, they nonetheless grow with the size of the original network. Recent empirical studies (Jiang et al.) 2020 2019, on the other hand, identify three classes of generalization measures that seem predictive of generalization: measures that estimate the flatness of local minima, the speed of the optimization, and the margin of training samples to decision boundaries. While these measures are correlated with generalization, their failure to fully explain the test performance of the model demonstrate need for other notions of model simplicity to explain generalization neural networks.
In this paper, we leverage the empirical observation that large fractions of trained neural networks' parameters can be pruned- that is, set to 0 without hurting the models' performance (Gale et al. 2019 Zhu & Guptal 2018 Han et al.) 20155) Based this insight, we introduce measure of

---

Under review as a conference paper at ICLR 2021
model's simplicity which we call prunability: the smallest fraction of weights can keep while pruning a network without hurting its training loss.
In range of empirical studies, demonstrate that model's prunability is indeed highly infor- mative of its generalization. In particular, we find that the larger the fraction of parameters that can be pruned without hurting model's training loss, the better the model will generalize. Overall, show that the smaller the fraction of parameters a model actually "uses" - the simpler it is the better the network's generalization performance.
In summary, our main contributions are thus the following:
1. We introduce new generalization measure called pranability that captures model's sim- plicity (Sec. f and show that across a large set of models this measure is highly informative of network's generalization performance (Sec. [5.41].
2. We show that even in particularly challenging setting in which we observe a test loss double descent (Nakkiran et al. 2020; He et al.) 2016), prunability informative of models' test performance and is competitive with existing strong generalization measures (Sec. 5.4.2
3. Lastly, we investigate whether the success of prunability can be explained by its relationship to flat local minima. We find that while prunability makes similar predictions to some existing measures that estimate the flatness of minima, it differs from them important ways, in particular exhibiting a stronger correlation with generalization performance than these flatness-based measures (Sec. 5.4.1 and 5.4.3.
RELATED WORK
Zhang et al. (2016) demonstrate that neural networks can perfectly memorize randomly labeled data while still attaining good test set performance on correctly labeled data, a phenomenon that complexity measures such the VC-Dimension and Rademacher complexity fail to explain. More recently, increasing the parameter count of models has been shown to improve their generalization performance, yielding 'double descent' curves in which the test loss first decreases, then increases and then decreases again as the parameter count is increased (He et al. [016]] Nakkiran et al.. 20200] Belkin et al.] 2019). contrast, many existing generalization measures grow monotonically with the model's s size and thus fail to capture double descent, making it a particularly interesting setting to study new generalization measures (Maddox et al.) 2020).
While generalization measures have been studied for a long time, . et al. (2020) recently brought new empirical rigor to the field. They perform a large-scale empirical study by generating a large set of trained neural networks with wide range of generalization gaps. Proposing range of new evaluation criteria, they test how informative of generalization previously proposed generalization measures actually are. In this paper, we evaluate our new generalization measure in the same frame- work and use the strongest measures as baselines for comparison against our proposed measure, the neural network's prunability.
common theme across many generalization measures is that they try to formalize Occam's 's Ra- zor, the idea that simpler models generalize better than more complex models. Rissanen (1986) formalizes this principle as model's Minimum Description length which was later applied to small neural networks by [Finton& Van Camp (1993). Similarly, Neyshabur al. 2013 2017) and nu- merous other approaches suggest that networks with smaller parameter norms generalize better. We are aware of two existing generalization measures that are based on compression or pruning. |Arora et al. (2018) derive PAC-Bayesian generalization bound based on the size of a network following a particular compression method based on noise stability. Zhoou et al. (2019), on the other hand, formulate generalization bound that is non-vacuous even for large network architectures based on the description length of a compressed network which in turn also grows with the size of the original network. While these approaches are theoretically elegant, all such measures grow with the number of parameters in given network and thus do not capture the phenomenon that more highly overparameterized networks tend to generalize better.
Three classes of generalization measures seem to be particularly predictive of generalization. First, measures that estimate the flatness of local minima, either based on random perturbations of the
2

---

Under review as a conference paper at ICLR 2021
weights (Neyshabur al., 2017: Dziugaite & Roy 2017 Jiang al. 2020 McAllester 1999)
directly based on the curvature of the loss surface (Maddox et al. 2020). In purely empinical study, Morcos al. (2018) find that model's 's robustness clamping the activations of individual units to fixed values is predictive of its generalization performance. Second, margin-based measures that the distance of training samples to decision boundaries (Tiang et al. 2019). Lastly, Jiang et al. (2020): Ru et al. (2020) have proposed measures that estimate the speed of optimization.
A large fraction of network's parameters can be removed without impairing performance (Gale ct al. 2019 Blalock et al., 2020); in fact, such pruning often improves generalization performance (Thodberg 1991p. There are many approaches selecting parameters for removal; we focus on randomly selected parameters (random pruning) and removing the htgpllest-mnnntudee parameters (magnitude pruning), though other approaches exist in the literature (Han et al., 2015 Renda al.
2020
Lee et al. 2019, Wang et al.. 2020 Blalock et al. 2020). Random pruning is applied by the regularization method dropout (Srivastava et al. 2014). which used to improve network general- ization performance. Magnitude pruning can be used in an iterative pruning and retraining procedure (rranlle & Carbin 2019) to identify sparse subnetworks that, for some sparsity levels, generalize better than their parent network. Both approaches are therefore natural candidates for notion of net- work simplicity. which we will leverage in our proposed generalization measure. While research on dropout and the Lottery Ticket Hypothesis suggest that pruning during training and generalization are connected, we study the distinct question of whether pruning after training and generalization are connected.
NOTATION
Following the notation of Jiang et al. (2020) we denote by D the distribution over inputs X and their labels and let x denote the number of classes. By S we denote given data set containing m i.i.d. tuples ((X1, y1),..., (Xm: Um)) } drawn from D where X; E X' is the input data and y; {1,....,k) the class labels. We denote a feedforward neural network by fw : X' - Z, its weight parameters by w and the number of its parameters by w. We denote the weight tensor of the 7th layer of the network by W; and we then have that w = vec(W),.... Wa). where d is the depth of the network and vec denotes the vectorization operator.
Let L be the 1-0 classification error under the data distribution D L(fw) = (xx,))=Dlf((X) * * yil. We define the generalization gap as g(fw) = L(fw) i(fw). When training a network, we denote each hyperparameter by 0, E O; for 1.... n where n is the total number of hyperparameters. We denote particular hyperparameter configuration by O = (01, O₂ .... x θ,.
y). and let Ż be the empirical 1-0 error on S: i(fw) 1
m
E O, where θ = O1 x
PRUNABILITY
A generalization measure should satisfy three straightforward desiderata: 1) It should correlate with the generalization gap across broad range of models. 2) It should not suffer trivially from Good- hart's law, that is, incorporating into the optimization procedure of model should lead im- proved generalization. 3) It should ideally have a plausible theoretical justification to allow for further study of its properties.
A measure based on magnitude- and random pruning presents a promising direction for satisfying all three desiderata. First, it is well-established that we can remove large fractions of neural network's parameters without negatively impacting its train performance, while also improving its test performance (Blalock al.) 2020 Thodderg 1991). Second, training models using dropout, i.c. random pruning, is widely known to improve generalization (Srivastava et al.) 2014), as does the iterative magnitude pruning procedure of Frankle & Carbin (2019) (up to certain sparsity levels). Finally, pruning has theoretical grounding in the minimum description length principle and in MCC-Bayesian bounds.
The connection between dropout and generalization has been studied in the PAC-Bayesian frame- work (McAllester 1999). which allows us to quantify the worst-case generalization performance of random predictors. PAC-Bayesian bounds define model complexity as the KI. divergence be-
3

---

Under review as a conference paper at ICLR 2021
tween some fixed prior distribution P, and the probability distribution over functions induced by the random predictor (often called the posterior Q, although this may not correspond to a Bayesian posterior) to obtain generalization bounds of the following form.
Theorem (McAllesterj ( (199)). For any > 0, data distribution D. prior P, with probability 1 over the training set, for any posterior Q the following bound holds:
KL(Q)) P) + l)
E E & (B--q(((f)) +
2(m-1)
McAllester (2013) shows that the case where both the prior and posterior are distributions over networks to which dropout with given dropout probability is applied, the KL term becomes: KL(Q] 1-a w We can directly use this formalization to derive a generalization bound 2
for networks that randomly pruned to the largest a, s.t. [f(o) < [(fw) x (1 3), i.e., such that the training loss does not increase more than a relative tolerance B. We have to adjust the bound account for the search for a. We make use of the fact that search over fixed number e of possible values for a and use union bound which will change the log term in the bound to We thus obtain the following bound:
log( em)
| 1 + log( T 5
P S Ee +
2(m -0
While this bound will be vacuous for many large neural networks, it does provide us with some intuition for why we should expect model's generalization to be linked its robustness pruning. In particular, this bound predicts the relative generalization performance of models from which different fractions of parameters can be removed without adversely affecting their training loss. is this prediction that we evaluate with the experiments described below. We provide the details on the derivation Appendix C
Given a trained model and pruning algorithm, we define the model's prunability as the smallest fraction of the model's parameters that we can keep while pruning without increasing the model's training loss by more than given relative tolerance 3. We choose the fraction of parameters pruned rather than the number of parameters remaining based on the empirical observation that naive pa- rameter counting is poor predictor of generalization performance.
Definition 1 (Prunability). Let L denote the cross-entropy loss. For given model fun training data set Strain. a relative bound on the change in train loss B and a pruning method é, we thus define prunability
Hppamabiliiyy (pprmmability(JJJ.))) arg min ()
s.t. L(b(fw: a), Strain) S (1+ i(f Strain).
where ((Sw, ()) sets the fruction a of the weights of fuo to zero.
In our experiments evaluate robustness to pruning both with regards to magnitude pruning, which the parameters with the smallest absolute magnitude are set to O, and random pruning, where random parameters are set to O. Magnitude pruning can remove greater number of model weights without affecting performance than random pruning (Blalock et al. 2020), and can therefore effective pruning strategy. We hypothesize that using more effective pruning
be considered method might yield a measure of prunability that is more predictive of generalization. Per default, refer to model's prunability with regards to magnitude pruning in the following. Note that while iterative pruning is usually used when the aim is to achieve the best compression rate, we are only concerned with the generalization of the model the end of training and thus apply one-shot pruning. In our experiments we use a tolerance 3 of 0.1 and note that the particular choice of B did not seem have large impact on the predictiveness of prunability. See Appendix [A...] for pseudo-code of how prunability is computed for a given model.
5 EXPERIMENTAL RESULTS AND ANALYSIS
The goals of our experiments are fourfold: 1) We verify that prunability predicts generalization across set of models trained with different hyperparameters and generalization performance. To
4

---

Under review as a conference paper at ICLR 2021
this end, we use similar experimental framework as Jiang et al. (020)) 2) We evaluate how prun- ability performs in a particularly challenging double descent setting. 3) To understand what notion of simplicity prunability quantifies, study the conditional mutual information between it and baselines that represent existing classes of different strong generalization measures. 4) Given that prunability and random perturbation robustness both measure the sensitivity of model's training loss to a perturbation of its weights, we directly compare how pruning and random weight perturba- tions impact models' losses.
5.1 BASELINES
We compare generalization measure number of baseline measures. Having somewhat tighter computational constraints than Jiang et al. (2020), we select one strong baseline per class of gener- alization measures described by Jiang al. (020)) and Jiang et al. 2019).
From the class of generalization measures that aim to capture a model's simplicity using parameter- norms, we use the Sum of Squared Frobenius Norms (Jiang et al. 2020
d
Usum of fro (fw))) d. I W. 112
where d is the number of layers of the model. From the class of measures based on the idea that models with flatter local minima generalize better, we use magnitude aware random perturbation robustness (Tiang et al. 2020):
Mpac bayes flat (f
o2
where u, NO0,, [/yp + c) and o² is the largest number such that E,[([(f S (1+ 3)
i(fw), where B is an arbitrarily selected relative tolerance, in our experiments 0.1. From the class of measures based on the idea that models with wider margins between the training samples and decision boundaries generalize better, use the Normalized Margins measure (Jiang al. 2019):
Mnormmaargins (fw) aTo
wherein & consists of five statistics of the normalized margins distribution for each layer of the model. That is, at each hidden layer of the network, the normalized distances all samples to the decision boundary of the second most likely class computed. Five statistics of each of these distance distributions are used as input for the linear regression. Lastly, from the class of measures based the idea that the speed of optimization is predictive of generalization, we use the negative Sum of Train Losses (Ru et al. 2020) throughout training:
(fw) = L(frr))
where 7' is the number of training epochs, w' the parameters at epoch and 7 the training cross- entropy loss. In Appendix A.2 we provide further details on these generalization measures and additional baselines.
5.2 MODELS
To generate large set of trained models, build upon the DEMOGEN set of trained models introduced by Diang et al. 2019). Our data set consists of 324 models that resemble the Network- in-Network architecture by (Lin et al. 2014) trained on CIFAR10. Diang et al. (2019) propose this particular architecture because it is parameter-efficient and achieves relatively competitive perfor- mance standard image classification benchmarks. We achieve wide range of generalization gaps by varying a number of hyperparameters such as the width, depth or Lo-reuularization of the models. We modify the original set of models, DEMOGEN, used by Jiang et al.) (2019) obtain an even stronger experimental set up: noticing that the depth of neural networks has a large impact on generalization performance, we add models of different depths to the original DEMOGEN data set. Following Diang et al. (2020) we only use models that apply batch normalization. See Appendix A.3 A.3 for further details of our experimental set-up.
5

---

Under review as a conference paper at ICLR 2021
5.3 EVALUATION METRICS
To study our generalization measures comprehensivelly we consider 1) their Kendall's Rank corre- lation with the generalization gap, 2) how predictive they are terms of the adjusted R² and 3) apply the conditional independence test of Jiang et al. (2020). in an attempt to understand the causal relations between the complexity measures and generalization. We briefly summarize the metrics in this section and provide more detailed explanation in Appendix|A.I A.I
We compute Kendall's rank correlation coefficient which quantifies to what extent the rank- ing of models according to given generalization measure corresponds to the ranking cording to the generalization gaps. For a given generalization measure μ., we consider: T == Usee Uoee((u(0), ((0)} where g is the generalization gap of the model trained with hyperparameters 0. Kendall's rank correlation coefficient is then defined as the fraction of pairs of tuples that are correctly ranked according to the generalization measure: T(7)
[T( ((HImn)ET E (() Sign(H1 422 (iggnng(()1 - 92). While Kendall's rank cor- relation coefficient is generally a useful metric, it does not adequately reflect whether a general- ization measure's performance is consistent across all hyperparameter axes. Thus, we also con- sider the granulated Kendall's rank correlation coefficient which is essentially the average of Kendall's rank coefficients dy obtained by only varying one hyperparameter dimension at a time:
V Σi= 1/:
To go beyond correlation, Jiang et al. (2020) use a conditional independence test inspired by Verma & Pearl (191T). The main goal here is to understand whether there exists edge in causal graph between a given generalization measure μe and the generalization gap g: this tells us whether models generalize well because of the value of the generalization measure, or whether the two values only correlated. This is achieved by estimating the conditional mutual information between the generalization measure and the generalization gap conditioned on different hyperparameters that are observed. Formally, we have that for any function Φ : θ + R. let Va θ₁ x θ₂ + {+1, -1} <(0))). Let Us be a random variable that corresponds to the values of the hyperparameters in S. Intuitively, the higher this metric is, the more likely it is that there is indeed an edge in the causal graph between the generalization gap and the generalization measure: K(μ+) = mitl//s.t.|ss <2 (Vn, : Vg) where [V VglUs) is the normalized conditional mutual information between the generalization measure and the generalization gap conditioned on observing the hyperparameter S.
be as (o(01, 02) == sign(((01)
To evaluate how well can predict model's generalization using linear function of given generalization measure and following Dianin et al. (2019). we additionally evaluate the generalization measures' predictiveness in terms of their adjusted R22 i.e. the proportion of the variance of the generalization gap (() across hyperparameters 0 E θ that can be explained by the generalization measure (()).
5.4
RESULTS
5.4.1
PERFORMANCE OF PRUNABILITY ON EXTENDED DEMOGEN DATA SET
Table holds summary of our experimental results on the extended DEMOGEN data set. We find that prunability is highly informative of generalization across all of our evaluation metrics. In particular, outperforms random perturbation robustness, the training loss itself and the Frobenius norm measures in terms of Kendall's rank correlation coefficient.
We find that while prunability based on magnitude pruming outperforms prunability based on random pruning, the difference in performance is relatively small.
We find that the Normalized Margins baseline clearly outperforms prunability while the Negative Sum of Train Losses and the Best Margin Variable seem similarly informative of generalization as prunability. Note that and the margin-based measures achieve much higher conditional mutual information scores than the other baselines, providing further evidence for the causal connection between wide margins and good generalization performance. The conditional mutual information between prunability and generalization is relatively low, suggesting that it seems somewhat less likely that there is a direct causal connection between a model's prunability and its generalization performance.

---

Under review as a conference paper at ICLR 2021
Generalization Measure
Kendall's
Adjusted R2
Cond. Mutual Information
Prunability (ours)
0.6496
0.5440
0.0324
Random Prunability (ours)
0.584
0.3015
0.0377
Random Perturbation Robustness
0,4253
0.2440
0.0230
Frobenius-nom
-0.6055
0.7778
0.0612
Normalized Margins
0.8061
0.8866
0.1761
Best Margin Variable
0.6344
0.6623
0.0743
Negative Sum of Train Losses
0.7085
0,4923
0.0186
Train loss
0.0201
0.0746
0.0004
Table 1: Prunability is highly predictive of generalization. Comparison of generalization mea- sures' correlation with test performance on set of convolutional networks trained on CIFAR-IO. Higher values are better across all metrics. The standard error of the Kendall's is 8, 0.037.
compare the granulated and regular Kendall's coefficients of some additional base- lines. The results reconfirm the weak performance of norm and parameter count-based complexity measures both for pruned and unpruned networks. While this a well known issue, we point out that this is also problematic for recently proposed generalization measures based on the size of the compressed network such as Zhou et al. (2019). We also note that the Frobenius norm measure is strongly negatively correlated with generalization rather than positively correlated expect based on Jiang et al. (2020). seems that this result largely due to a strong negative cor- relation for models with different dropout rates and relatively weak correlation coefficients along other hyperparameter axes.
In Table 2]
one would
Generalization Measure
Width
Dropout Rate
Data Augment.
Weight Decay
Depth
Kendall
prunability (ours)
0.1582
0.6986
0.0122
+0.001
0.2254
0.6496
0.2187
random prunability (ours)
0.0714
0.6261
0.0464
0,0422
0.259
0.584
0.209
cnddon-perturbation frobenius norm normalized.cu margrins best margins, vuriable
0.1161
0.5154
0.0962
0.0755
0.1829
0.4253
0.1972
-0.0778
-0.7955
-0.067
-0.0591
0.4577
-0.6055
-0.1083
0.0671
0.8325
0.1121
0.0799
0,5789
0,8061
0.054
0.7756
0,0415
-0.039
0.4798
0.6344
0.2624
sum_of_train_losee
-0.0639
0.8078
0.0498
0.0345
0.4156
0.7085
0.2487
losin_lss sum_two_nord
0.0143
-0.0652
-0.0762
-0.0349
0.1142
0.0201
-0.0096
+0,0513
-0.5728
0.0214
0.0746
-0.1359
-0,2096
+0.1328
parameter sum_two foo__ooms__ppp pruned
-0.0866
0.0
0.0
0.0
-0.4218
-0.0911
40.1017
-0.0749
-0.6828
0.0857
0.0866
-0,2654
-0.2234
-0.1701
pruned parameter count
-0.0893
0.6986
0.0122
-0.001
-0.3798
0.0417
0.0481
Prunability achieves stronger granulated rank correlation than measures based on random perturbation robustness or norms. Columns labeled with hyperparameters (width, dropout rate, etc.) indicate Kendall if we only vary this hyperparameter. The last two columns are the Overall Kendall's and the Granulated Kendall's coefficient v which is the average of the per-hyperparameter columns. Higher values are better across all columns
Table 2:
5.4.2 DOUBLE DESCENT
In addition to our experiments on the DEMOGEN data set, also evaluate prunability set of models that exhibit a test loss double descent (Nakkiran et al. 2020). This phenomenon is partieu- larly interesting for the study of generalization measures, since many measures that aim to capture a model's complexity grow monotonically as we increase a network's width and thus do not dis- play double descent. We thus including this experiment to evaluate whether prunability also succumbs to this phenomenon. We use the experimental setup proposed by Maddox et al. (2020), and compare our new measure their curvature-buut based generalization measure which also aims to capture double descent. Note that up to now we studied the generalization gap in terms of the 0 loss. In this section, however, we focus on another aspect of generalization and study the relation between prunability and models' cross-entropy test loss.
Maddox et al. (2020) introduce a generalization measure called Effective Dimensionality which is defined as: (H, 2) = Σ dtz where X; are the cigenvalues of the Hessian of the training loss H E * and > is regularization constant. Intuitively, the Effective Dimensionality measures the flatness of the local minimum of a network in terms of the number of eigenvalues of the Hessian of the training loss that "large". To get measure the same scale

---

Under review as a conference paper at ICLR 2021
CNN on CIFAR100
12
(soolec)) (ecoded)
Prunabillty Biy
1.0
Rand. Perturbttion (scared)
Elleciion Dimerokonally
0.8
Kendall's T
Test Loss
Test Error
Prunability
0.3613
0.1277
0.6
Eff. Dim.
-0.0197
-0.0753
Random Perturbation
0.1398
-0.2166
04
Frobenius Norm
0.0996
-0.5367
Margins
0.1296
0.4258
02
-Sum of Train Losses
-0.2890
-0,9381
(a) Comparison of prunability and baseline measures (b) Kendall's rank correlation (s, = 0.06) hetween generalization measures and test loss. Higher is better.
in a double descent setting.
Figure Prunability correlated with test loss in double descent setting: Across a set of convolutional networks of varying width trained CIFAR-I00, double descent behavior better than a previously proposed metric Effective Dimensionality which is based the eigenspectrum of the Hessian of the training loss of the model and other strong baselines.
show that prunability captures
new generalization measure, we use a normalized version of Nefy' Weffictiveeddneessionii dimensionality Additionally, we also evaluate a number of the strongest baselines from Section [5.4. in the double descent setting. We refer to appendix A.4 for further details on the experimental setup.
We find that prunability does indeed display double descent and is more strongly rank correlated with the test loss than the baseline measures (Kendall's r of 0.3613, < 0.0005).
In Appendix B.I study an additional double descent setting and obtain results that are consistent with the results presented in this section.
5.4.3 PRUNING AND FLATNESS BLAANNESS-BASED BASED MEASURES
We now investigate whether network's robustness to pruning can be explained by other estab- lished generalization measures, or whether it measuring something entirely distinct from previous notions of model simplicity. To better understand the relation between prunability and the other generalization measures we perform the conditional independence test described in section 1..33 between them. Recall that, up to now, used this test to study the relation between the generaliza- tion measure and the generalization gap and that the higher the x between two variables, the likelier it is that they neighbors in the causal DAG. See Table for summary of the results.
First, we observe that the conditional mutual information between prunability and random perturba- tion robustness is the highest across the baselines we are evaluating. Because pruning is special case of perturbation, some connection between the two methods is expected. However, prunability clearly measuring something subtly different from flatness of the loss surface, it outperforms random perturbation robustness in our evaluations. Thus, we investigate whether this distinction may arise from the differential effects of pruning and random perturbations in function space.
To evaluate this, we directly compare the impact of both pruning and random perturbations on some of the models in our double descent experimental setting by performing pruning and random perturbations of the same magnitude and computing their respective impact on the loss. We find that pruning has a larger negative impact on model's training loss than random perturbation of the same magnitude (see Figure 2 Pruning can lead to improvement of the test loss which we do not observe for random perturbations: we conjecture that this relationship may be responsible for the difference between the two methods, though disentangling this phenomenon is left for future work. We also note that prunability achieves much higher Kendall's т, Adjusted R² and Conditional Mutual Information than random perturbation robustness.
8

---

Under review as a conference paper at ICLR 2021
In conclusion, pruning affects models differently from randomly perturbing their weights. Because pruning can in certain settings improve test performance (and hence seems to be more aligned with network simplicity) suggest that this difference leads to the stronger performance of prunability as compared to random perturbation robustness. We compare the impact of pruning and random perturbations model's 's training and test loss for additional architecture in Appendix B.2 and find that the results are consistent with the results presented in this section.
Normalized Margins
Random Perturbations Parameter Count
Train Loss
Trobenius Norm SoTL
Prunahility 0.0122
0.04541
0.0038
0.0004
0.0105
0.0013
Table 3: Prunability similar to Random Perturbation Robustness.
The conditional mutual
information (CMI) between prunability and random perturbation robustness.
Pruning versus Random Weight Perturbations
Magnitude Pruning
Random Perturbation
Test Loss
0
3
2
2
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Fraction of unchanged weights
Fraction of unchanged weights
Figure 2: Pruning affects models very differently than random perturbations. Here we compare pruning of weights and randomly perturbing the same weights by the same amount. We study ResNet18 trained on CIFAR100. Generally speaking, pruning will have larger negative impact on model's loss than randomly perturbing the same weights by the same amount but in some cases pruning actually improves the test loss of models.
6 CONCLUSION
In this paper, show that network's prunability, the smallest fraction of parameters keep while pruning without hurting the model's training loss, is highly informative of the network's generalization performance. We also show that prunability seems to capture something distinct from previously suggested measures based on robustness to random perturbations or the curvature of the loss landscape. We see a number of promising directions for further research. For instance, one could study whether the direction of pruning lies in the span of the main eigenvectors of the Hessian studied by Maddox et al. (2020). Given the strong empirical performance of prunability and given that the theory behind its success is not yet well understood this measure of model complexity may of use to the construction of future generalization bounds. We include an attempt of this in Appendix C but more thorough investigation will likely prove illuminating.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems, pp. 61656 2019.
01w.1111.111...... .pf
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. volume 80 of Proceedings of Machine Learning Research, pp. 254 263, Stockholmsmässan Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http: //proceedings. mll press v80 artral8rrl11b html
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. eesttrally-ormaaiize margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249, 2017. URL www.htttt///eett www.vvorgg/ppo.. wwwpo//////oooeo 08498 .pdf]

---

Under review as a conference paper at ICLR 2021
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical birs-variance trade-off. Proceedings of the National Academy of Sciences, 116:201903070, 07 2019. doi: 1L1073/pnas.90033701.1 URL https:// pdd
arxiv. 3xxiv..rrg/pdf/1112..1
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? In Proceedings of 3rd MLSys Conference, 2020. URL https:
7 //axxi.org//pd//2000
03033 pddf
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the Thirly-Third Conference on Uncertainty in Artificial Intelligence, 2017. URL https:
7 //axxi..rggpaf////. 0000000...1...... pdf
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learming Representations, 2019. URL https:// openreview net/ forum? 1d==r11
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09574, 2019. /ttttts:///axi....../ wwwp:/iwwwrggp////////// 095 09574.
Song Han, Jeff Pool, John Tran, and William Dally, Learning both weights and connec- tions for efficient neural network. In Advances in neural information processing sys- tems, pp. 1135-1143, 2015. URL httpp::/papprs. hcappsscc//pper/21////1e beceeleee3cc2cce4442244333333333
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pp. 630-645. Springer, 2016. URL
https://eat wttpp//wwwwgpp/////..333
Geoffrey Hinton and Drew Van Camp. Keeping neural networks simple by minimizing the descrip- tion length of the weights. In in Proc. the 6th Ann. ACM Conf. on Computational Learning The- ory. Citeseer, 1993. URL http::////// www. cs toronto. edu/ wttp:///rrttaaaaps/eeeeeaoaaeeee awsps/colsttcc. pdf
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson. Averaging weights leads to wider optima and better generalization. Proceedings of Confer- ence Uncertainty in Artificial Intelligence, 2018. URL http:://uai. org/uai2018/
proceecinggs/pppezss /31pperse333.. pdf
Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the generalization gap in deep networks with margin distributions. In International Conference Learning Represen- tations, 2019. URL httttss:///peeeevviiee/
net/ wwwumorrmmmmm 2
Yiding Jiang Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where find them. In International Conference on Learning Representations, 2020. URL
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 and cifar-100 datasets. URI:
https://www. cs. toronto. edu/kriz/cifar. html, 6:1, 2009.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr SNIP: SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY. In International Conference on Learn ing Representations, 2019. / http:///wenneeeeeeeeeeeee/eonnna
M. Lin, Q Chen, and S. Yan. Network in network. CoRR, abs/1312.4400, 2014. URL https:
4400.
Wesley J. Maddox, Gregory Benton, and Andrew Gordon Wilson. Rethinking parameter counting in deep models: Effective dimensionality revisited, 2020. URL wtK.itttps///exi..org////// 2003. 0210021199900 021...d2119...... pdf
David McAllester. A pac- bayesian tutorial with dropout bound, 2013. URL https://arxxx: brg/pdf/1307. 2118 fdd
10

---

Under review as a conference paper at ICLR 2021
David A McAllester.
Pac-bayesian model averaging. In Proceedings of the twelfth annual ference on Computational learning theory, pp. 164-170, 1999. URL ptttps:/aaxxiv.oo
pdf/ 08864.
p
Ari S Morcos, David GT Barreut Neil Rabinowitz, and Matthew Botvinick. On the importance of single directions for generalization. In International Conference on Learning Representations, 2018. URLpssts:///axx wttp://orggp//////////e /tt/://.....0005.9..9. pdf
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference Learn-
ing Representations, 2020. WRLhttpps:/ opwnrevien.eeeeeeeeeeeeee net/ /
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neu- ral networks. volume 40 of Proceedings of Machine Learning Research, pp. 1401, Paris. France, 03-06 Jul 2015. PMLR. URL Neyshabur html
www.mmrrppp.. mt...rrsss/vC/
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956, 2017. URL htLthtts://araxt wwtp:///gggaaaooeeeeee 08947
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural
network pruning. In International Conference Learning Representations, 2020. URL https:
Jorma Rissanen. Stochastic complexity and modeling. The annals of statistics, pp. 1080-1100, 1986. /t/pptsss//proeccecclleec http::/pwpppotteee.c..ooocaaca..
Binxin Ru, Clare Lyle, Lisa Schut, Mark van der Wilk, and Yarin Gal. Revisiting the train loss: an efficient performance estimator for neural architecture search, arXiv preprint 20X:v:2006.04492, 2020.
04492.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting The journal of machine learn- ing research, 15(1):122-1158, 2014. URL https::/t///........ / /mll= r. rorgg/oooo...o....o........ www..rooorropoppoopeeeeee papers vo v ume 5/ pdf
srivastavall4a/rrraaaaaaaaa
Hans Henrik Thodberg. Improving generalizatonnnnononnn of neural networks through pruming. International
Journal of Neural Systems, (04)3317-326, 1991. URL http::tts::/wwwt wor dscientifio
com/doi /2 /wt./////020000000000000
Thomas Verma and Judea Pearl. Equivalence and synthesis of causal models. UCLA, Computer
Science Department, 1991. URLlstt:s///axi http://aaxxx..../p...a. wttpp/pppppp.......1..o 1108 pdf
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by
preserving gradient flow. In International Conference on Learning Representations, 2020. URL
https:://pperrevat
net Sotorummdd-SsgssaCC
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Rep- resentations, 2016. URL
net f Syd=Sy8ddB9xx
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P Adams, and Peter Orbanz. Non-vacuous gen- eralization bounds at the imagenet scale: pac-bap nac-bayesian compression approach. In International Conference on Learning Representations, 2019.
Michael H. Zhu and Suyog Gupta. To prune, or not to prune: Exploring the efficacy of pruning for model compression. In International Conference on Learning Representations (Workshop). 2018. URL httts::
11

---

Under review as a conference paper at ICLR 2021
A EXPERIMENTAL SETUP
A.1 EVALUATION METRICS
In this section describe the metrics to evaluate the generalization measures. To study our generalization measures comprehensively. we consider the generalization measures' Kendall's Rank correlation with the generalization gap, how predictive they in terms of Adjusted Rº and Jiang et al. 2020).'s 's conditional independence test in an attempt to understand the causal relations between the complexity measures and generalization.
A.1.1 KENDALL'S S RANK CORRELATION COEFFICIENT
This criterion evaluates the quality of a given generalization in terms of how well it ranks models with different generalization gaps. Intuitively, a generalization measure ranks two models that were trained with hyperparameters 01 and 02 correctly iff μ(0,) u(02) - g(0)) g(O2) is satisified. Kendall's 's rank coefficient then measures for what fraction of models in our data set this holds. Kendall T takes values between 1 (perfect agreement) and -1 (rankings are exactly reversed) where Kendall's of O means that the complexity measure and generalization gap are independent.
Formally, we consider the of tuples of generalization measures and generalization gaps:
T = Upce ((n(0),
And Kendall's rank correlation coefficient defined as:
1 T(T) = IT((TI - (M..1)TT (Ta.m))TT(un..))
Σ
Σ
sign(H1 (2)sigg((1 92)
A.1.2 GRANULATED KENDALL'S RANK COEFFICIENT
While Kendall's rank correlation coefficient is generally a useful metric, does not adequately re- flect whether a generalization measure's performance is consistent across all hyperparameter axes. To account for this Jiang et al. (020) propose the granulated Kendall's rank-correlation coefficient which is essentially the average of Kendall's rank coefficients obtained by only varying one hyper- parameter dimension at a time.
Formally, have:
m: 01 0;-1 x D4t1 x O..
and the Kendall's rank correlation coefficient is defined as:
4b := w= mh 6,
Σ
Σ
Σ
T(Un,
8
0
6,EB
Averaging all of these values, we obtain the granulated Kendall's 's rank correlation coefficient:
V
3/s
Given these definitions, we obtain the following standard errors for the granulated Kendall's coef- ficients in our experiments. For the width, dropout rate, weight decay and depth measurements we hsve, 0.00056 and for the data augmentation measurements we have 8,0. 0.0004844 Lastly, for Lb, we have s, = 0.00011
12

---

Under review as a conference paper at ICLR 2021
A.1.3 CONDITIONAL MUTUAL INFORMATION
To go beyond measures of correlation, Jiang et al. (000)) use a conditional independence test in- spired by Verma & Pearl [1911). The main goal here is to understand whether there exists an edge a causal graph between given generalization measure μ and the generalization gap g- This is achieved by estimating the mutual information between the generalization measure and the general- ization gap conditioned on different hyperparameters being observed. The higher this metric is, the more likely it is that there is indeed edge in the causal DAG between the generalization gap and the generalization measure.
Formally, have that for any function θ R, let V θ O₂ + f+1, be as Vo (0,, 02) == sign(ø(0) - x(02)). Let Us be a random variable that corresponds to the values of the hyperparameters in S. The conditional mutual information can then be computed as:
P(V,, Vg Us)
[VV,V = C(US))
Σ (E((1I [E{+11
Σ
PV2, log
(V
Us
By dividing the term above by the conditional entropy of generalization:
Hs)) = Σ
M(U))
Σ
(V,)Us)) log(p(V)Us)))
Us
[+E==I)
we obtain the normalized criterion:
I(V Vg(Us) H(V, Us)
Tv VglUs)
In the original Inductive Causation algorithm (Verma & Pearl 1991). an edge in the causal graph is kept if there no subset of hyperparameters S such that the two two nodes are independent, that IV,,,, Vg ( O. Due to computational limitations, and following Jiang al. (2020), we only consider subsets of hyperparameters of size at most 2:
K(μ)) = min
i(V V2
S2
Intuitively, the higher K())), the more likely it is that there exists edge between y and generaliza- tion the causal graph.
A.1.4 ADJUSTED R²
Lastly, consider metric evaluate how predictive a generalization measure is of generalization based on a simple linear regression: 9 = aT 4 b. We find a and b by minimizing the mean squared error: a", 6- arg mina,b (a d(u,) g.)
On test set of models we then compute the coefficient of determination R which measures what fraction of the variance the data ca be explained by the linear model:
Σ (g) 93)²
R²
(1) 1 - 12
We compute the R2 using 10-fold cross-validation.
Alternatively, one can use the adjusted R² score (R²) which measures how well linear model fits training set and which accounts for the number of variables used in the regression:
ptt - (1 122)
n
dim (A)
13

---

Under review as a conference paper at ICLR 2021
Layer Id
Layer Type
x 3 convolution, stride
I convolution, stride
x convolution, stride
Table A NiN block
A.2 GENERALIZATION MEASURES
Additional generalization measures we consider are:
Ubest margins variable: To account for the fact that the normalized margins variable is based on a large number of input variables, we select the single independent variable that has the largest standardized coefficient the Normalized Margins model and directly use generalization measure.
Jossi L(fw), ) the cross entropy loss of the model fw on the training data after training is finished.
Mparameter.commt
The number of parameters i of the model.
#sum_two_noems-
Psum_of (Sw)
W
Usum two nomss prined: Essentially, the same as Jsuu two nomms. but applied to fwo that we obtain when compute Hprunabilityy Formally, have:
Paum Waum_two.norms www.:wwwooo..puuse....... (fw)
Msum two norms (min @(fw; a))
s.t. (< a), Strain) S (1 + B) x Elfu,Strainl
Analogously, Mpnone parameter count is the parameter count w of the pruned model we obtain
while computing /pprmability
A.3 DEMOGEN
We extend the DEMOGEN data set in Jiang al. (2019) with regards two aspects. First, we follow Diang et al. (0020) and only consider models that are trained using batch normalization. Second, Jiang et al. (2019) do not consider networks of different depths. We consider this to crucial hyperparameter and a extend the original DEMOGEN data set by training additional models with different numbers of NiN-blocks than the models in the original data set.
We use the network architecture proposed by Jiang et al. (2019) in the DEMOGEN data set which very similar to the architecture used in Jiang et al. (2020). The architecture is very similar to the Network in Network architecture in Lin et al. (2014) with the max pooling and dropout layer removed. We train the networks on CIFAR-10 1-10 (Krizhessyy et al. 2009). The architecture we use is thus:
1. The input layer
2. 2, 3 or 4 NiN-blocks as described in Table
3. A single convolution layer with kernel size 4x4 and stride
In this architecture vary the following hyperparameters:
1. Use channel sizes of 192, 288, and 384
2. Apply dropout after NiN-blocks with 0.0, 0.2,
3. Apply la regularization with À 0.0, 0.001, 0.005.
4. Train with and without data augumentation, that is random cropping, flipping and shifting.
14

---

Under review as a conference paper at ICLR 2021
5. We consider two random initializations per hyperparameter configuration.
6. Models with 2, 3 or 4 NiN blocks as described above.
In total thus working with data of 324 trained models. We train the models with SGD with momentum (a = 0.9) with a batch size 128 and an initial learning rate of 0.01. The networks are trained for 380 epochs with learning rate decay of 10x every 100 epochs. We base our implementation on the original code base: https:://// hattpss//gittab htatthab.como/ee soom//oolleeeee research/ Geogle-researche wtwp:/tteee/eeeeeeeeeeee maateerrcaa demogen.
A.4 DOUBLE DESCENT
For our double descent experiments we use the models and baselines used by Maddox et al. (2020) which are available on: https://
com www.g/benttotnoaeeeeeeeeeo httt:://ooiauu...cco///bettttt/a
In particular, the CNN we use is the architecture used by Nakkiran et al. (020)) which is availbable
on: ht httpp:://gitlaa
harva weravrrdmacit mach
blob /ttp///te//meee//eeaaaaaaaeaaaae
Likewise, the ResNet18 architecture be found here:
htt.aa///@tttt..oooooog////////a resnet.
The other baselines correspond to the ones from the DEMOGEN experiments described in Appendix
A.3
The margins baseline used in this setting based on the one used in Jiang et al. (2019) : linear
model is trained to predict the test loss based on the statistics of the margin distribution at the outpur layer of given model.
We train a set of 32 networks of widths 2, 4, 6, 64 on CIFAR100 (Krizhevsky et al. 2009) using SGD with learning rate of 10-2 momentum of 0.9, weight decay of 10 for 200 epochs with batch size of 128. The learning rate decays to 10-4 on a piecewise constant learning rate schedule [lzmillov et al. 2018), beginning decay epoch 100. Random cropping and flipping are used for data augmentation which is turned off for the computation of eigenvalues. Our plots contain the results across random seeds. The shaded areas indicate the standard error. All experiments were run on Nvidia GeForce RTX 2080 Ti GPUs.
A.5 RANDOM PERTURBATIONS VERSUS PRUNING
We
use the ResNet18 implementation from https://gitlab: com/
harvard www.ardd-achiieee. learning dew.eeedseeeeteeeeeeeeeee /blbb// http://loommtttr///mmmm masterrmoddees:
resnet 18k. py and use the same hyperparameters for training as in the double descent settings above. For every magnitude pruned model also compute the randomly perturbed model in which we perturb the same set of weights by random vector of the same size.
A.6 ALGORITHMS
A.6.1 ALGORITHM DETERMINE PRUNABILITY
Algorithm 1: Maximal Lossless Magnitude Pruning
Input:
Original model fw. data, tolerance in change of loss 3, step size for search step_size
Result: Pruned Model fupruned
original train loss(h, train -dia);
fraction of weights...t... remove 0.98;
Wpruned = wr -weights wtthhtssttorrrr terree))));
fraction.ooooo Wpruned prune(w, [raclion_of_wetti remove - step_size:
while lossí fwrssaa train data) > (1+ B3 x original train loss do
of tormmooo
end return Swpruned
Where prune(w, w. sparisty) is an algorithm that sets sparsity % of w to 0 and then returns the new vector. In experiments evaluate both magnitude pruning, where the parameters with the
15

---

Under review as a conference paper at ICLR 2021
smallest absolute magnitude are set O, and random pruning. where random parameters set to
Empirically, find that the particular choice for the tolerance 3 does not make big difference with regards to predictiveness of prunability. In our experiments we use 0.1.
Note that determine model's prunability the differentiable cross-entropy loss rather than the 1-0 loss used elsewhere in the paper.
B ADDITIONAL EXPERIMENTS
B.1 DOUBLE DESCENT
In Section 5.4.2 we conduct an experiment that suggests that prunability captures the particularly challenging double descent phenomenon. In this section, we provide extended version of Figure 1 containing all baselines (see Figure Sa). Furthermore, we extend that experiment to an additional architecture, R8 trained on CIFAR 100 (see Figure E. The results of this additional experi- ment are consistent with the one in the main part the body: prunability is strongly Kendall rank correlated with the test loss and the test eroor. In this additional setting, however, the margins-based method outperforms prunability. We describe the details of the architecture and training of this experiment in Appendix A.5
B.2 PRUNING VERSUS RANDOM PERTURBATIONS
Likewise, we study the impact of pruning and random perturbations on the training and test loss in an additional experimental setting. As in the experiment in Section 5.4.3 we find that pruning and randomly perturbing weights (by a vector the same magnitude). have very different impacts on the training and test loss (see F)gure In this experiment, experiment of Section 3.4.2. In particular, we find that pruming generally has a larger negative impact on the training loss than random weight perturbation of the same magnitude. With regards the test loss, we find that pruning has a smaller negative impact than random perturbations for moderate amounts of pruning, and a larger negative impact for larger amounts of pruning/perturbation. This matches the behavior of the first experiment. In this additional experiment we do not observe an improvement of the test loss through pruning which was not expected.
study the CNN used in our double descent
Pruning versus Random Weight Perturbations
Megnitude Pruning Random Perturbation
5
1.0
Test Losa
Train Loss
0.8
0.6
0.4
2
Fraction of unchanged weights
Fraction of unchanged weights
Figure 5: Pruning affects models differently than random perturbations. Here we compare pruning weights and randomly perturbing the same weights by the same amount. We study a CNN on CIFAR 100. Generally speaking, pruning will have a larger negative impact on a model's 's loss than randomly perturbing the same weights by the same amount. Similarly, we find that pruning has a smaller negative impact on the test loss than randomly perturbing as long as a moderate number of parameters are being perturbed. For larger fractions of perturbed parameters, pruning has larger negative impact on the test loss than random perturbations.
the original experiments,
16

---

Under review as a conference paper at ICLR 2021
CNN on CIFAR100
1.2
1.0
0.8
Test loss (scaled)
0.4
Train loss (scaled)
Prunability
0.2
Margins (scaled)
Perlurbations (scaled)
Frab, norm (scaled)
0.0
Neg. Sum of train losses (scaled & shifted)
Effective Dimensionality
10
20
30
40
50
60
Width
(a) Comparison of prunability and baseline measures in double descent setting. As indicated, some measures were scaled to onto same y-axis. This Figure is the extended version of Figure
Kendall's
Test Loss
Test Error
Prunability
0.3613
0.1277
Eff. Dim.
-0.0197
-0,0753
Random Perturbation
0.1398
-0.2166
Frobenius Norm
0,0996
-0.5367
Margins
0.1296
0.4258
-Sum of Training Losses
-0.2890
-0.9381
(b) Kendall's rank correlation (s+ 0.06) be-
tween generalization measures and test loss/test error.
Higher values are better.
Figure 3: Prunability is correlated with test loss in double descent setting: Across a set of convolutional networks of varying width trained on CIFAR-I00, we show that prunability captures double descent behavior better than previously proposed metric Effective Dimensionality which based the eigenspectrum of the Hessian of the training loss of the model and other strong baselines.
C PAC-BAYES BOUND
We the following, simplified formulation of McAAllester (1999)'s 's dropout bounds which is also used in Jiang el al. (2020):
Theorem For any 8 > O, distribution D, prior P. with probability 8 over the training set, for any posterior Q the following bound holds:
KL(Q P) + log ) 2(m -
Ex- (
For the reader's convenience we briefly reproduce the derivation the dropout bound in McAllester 2013).
17

---

Under review as a conference paper at ICLR 2021
ReaNet1 on CIFAR100
1.2
Test loss (scaled)
Train loss (scaled)
Prunabilly
Margins (scaled)
1.0
Rand. Perturbatione (scaled)
Frob, norm (scaled)
Neg. Sum of train losses (scaled shifled)
0.8
Effeclive Dimensionality
0.2
10
20
30
40
50
60
Width
(a) Comparison of prunability and baseline measures in double descent setting. As indicated, some measures were scaled fit onto the same y-axis.
Kendall's
Test Loss
Test Error
Prunability
0.4812
0.7556
Eff. Dim.
0.1272
0.5077
Random Perturbation
0.4532
0.7370
Frobenius Norm
-0,4487
-0,9192
Margins
0.5589
0.3883
-Sum of Train Losses
-0.4728
-0.9393
Kendall's rank correlation (s+
0.06) be-
tween generalization measures test loss/test error.
Higher values are better.
Figure 4: Prunability correlated with test loss in double descent setting: Across set of ResNet18s of varying width trained on CIFAR-100, we show that prunability captures double de- scent behavior better than previously proposed metric Effective Dimensionality which is based on the eigenspectrum of the Hessian of the training loss of the model and is competitive with other strong baselines.
To draw sample w from Q means first drawing sparsity pattern S ~ Sa. where is the dropout probability, and noise vector
NO 1)d. Then, we construct Hadamard product: (sow); == s,W, Similarly, sample from P soc. We denote by S, the distri- bution on the d-cube B of sparsity patterns. We then have Eu-q [f Egws. (( (f We derive KL(Q as follows:
(w + e), being the
Sa(s)e |seel] In
KL(QIIP) E Eg
S. (s)e (((ssseelll////a/ =11=0(w--)]1
E
Exn
||s m012)
- a
w 2
2
18

---

Under review as a conference paper at ICLR 2021
We can directly obtain a bound for prunability from this, by searching for the largest a, s.t.E.- [[([]] < ((fw) (1 3), where are the weights learned during training of the network. We have to account for the fact that we search for a in our bound. We make use of the fact that we're searching over fixed number of as and union bound in the bound which will
change the log term in the bound to log( ( Gives us the following bound:
w 12 +
log( %h +
Ex-ol4(fo] S Ev-ol +
2(m 1)
19


Reviews:
[{"review_id": "zU2Y5GK5N1K", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "## Paper summary\n\nIn order to understand why deep networks generalize well, this paper proposes \"prunability\" as an empirical measure that can be predictive of the generalization. Prunability is roughly the smallest _fraction_ (i.e., $\\in [0,1]$) of parameters that can be retained, while zeroing out everything else, without increasing the model's training loss by too much. The authors experimentally demonstrate the predictive ability of this measure in three ways.\n\n1. They consider **the large-scale empirical framework of Jiang et al' 2019** where one computes different statistics about \"generalization vs. the measure\" from a large pool of trained models (viz., DEMOGEN dataset from Jiang et al' 2018). They compare prunability against four other existing measures:  Frobenius norms, random perturbation robustness (a flatness-based measure), Normalized margins (a layer-wise margin measure), the average loss across training (a speed-of-optimization based measure). \n\n Then they compute three different previously-proposed statistics:\n   - a) Kendall's rank correlation coefficient (Jiang et al' 2019) which tells us how well the measure can rank the models: **here prunability performs better than the flatness measure, and much better than the norm and speed measures.** (However, normalized margins outperform everything)\n   - b) adjusted $R^2$: here prunability performs just as well as other measures (although normalized margins outperform again.)\n   - c) a conditional mutual information (CMI) term Jiang et al 2019 that tells us whether the measure has a causal role in the generalization behavior: prunability's CMI is pretty low revealing poor causal connections.\n   \n2. They conduct Maddox et al., 2020's experiment where one evaluates the measure for varying widths to see whether it can **capture the double descent behavior of the test loss**. They observe that prunability does show a double descent behavior, while Maddox et al., 2020's flatness-based \"effective dimensionality\" only shows an \"ascent-descent\" behavior. \n\n3. Finally they demonstrate that **prunability captures something different from all the other measures.** They do this by showing that there is little causal connection between prunability and all other measures except the flatness-based random-perturbation-robustness measure. Then they go on to show that pruning and random perturbations affect models differently. Notably, pruning can lower the test loss of the network while random perturbations always only increases the test loss.\n\n\n## Strengths\n\n1. The idea that compressibility relates to generalization is not new and has been theoretically quantified via generalization bounds. However, such bounds are still parameter count dependent and/or they're computed for a handful of models and it's not clear how well they correlate with generalization.  The paper takes an orthogonal direction towards relating compressibility and generalization: it pins down an empirical measure of compressibility, and then \nprovides three sufficiently different kinds of arguments to demonstrate the usefulness of that metric. Although the experiments used within these arguments in themselves are not novel, I think the fact the metric holds up in all these tests is interesting.\n\n2. The way this paper quantifies prunability --- in terms of the fraction of parameters --- is simple and also somewhat thought-provoking (why should generalization be related to the fraction of parameters?).\n\n\n3. The paper is honest and rigorous in terms of the values it reports: prunability is not the best of all metrics, and the paper is transparent about it. The paper also gives sufficient credit to work that it builds upon. The writing is smooth.\n\n## Weaknesses\n\n4. Given that this is a purely empirical paper, I'd have appreciated if the observations made in the double-descent experiment and \"the effect of pruning-vs-perturbation on test loss\" experiment, were also shown in at least one other dataset/architecture.\n\n\n## Overall opinion\n\nThis paper provides multiple different pieces of evidence backing its claim that prunability predicts generalization. These empirical observations are rigorous and would be valuable in understanding the generalization puzzle. This way of quantifying prunability might also open up new theoretical questions. Hence, I think this is a good paper worth publishing.\n\n## Clarification questions\n\n5. Could you explain why the last few experiments are reported in terms of the cross-entropy loss? Is it because the corresponding plots for the 01 error do not show as much different between the lines? Nevertheless, I feel that it'd be nice to have those plots in the paper too (no pressure to produce those plots during rebuttal). \n\n6. Could you clarify the claims in the first paragraph of 5.4.1? Specifically \n>\"prunability is highly informative of generalization across all of our evaluation metrics  outperforming random perturbation robustness, the training loss itself and the Frobenius norm measures\" \n\nseems to contradict later observations that on some evaluation metrics they are all just as good as each other on adjusted $R^2$.\n\n### Minor suggestions\n\n- Under Table 1 and 2 would be nice to remind the reader as to whether larger values indicate better predictivity or not.\n- Is the usage of adjusted $R^2$ inspired by Jiang et al., 2018? If so, would help to cite them appropriately.\n- Page 12 typo \"Vargins\" --> \"Margins\"\n\n### Suggested citation\n\n\"On the importance of single directions for generalization\" Ari S. Morcos, David G.T. Barrett, Neil C. Rabinowitz, Matthew Botvinick, ICLR 2018 https://arxiv.org/abs/1803.06959   -- they empirically study how generalization is related to how many hidden units you can zero out. (Certainly not the same as what the submission suggests, but I think worth citing.)\n\n### References \n- Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic\ngeneralization measures and where to find them. arXiv preprint arXiv:1912.02178, 2019.\n\n- Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the generalization gap\nin deep networks with margin distributions. arXiv preprint arXiv:1810.00113, 2018.\n\n- Wesley J. Maddox, Gregory Benton, and Andrew Gordon Wilson. Rethinking parameter counting\nin deep models: Effective dimensionality revisited, 2020.\n\n\n**Update:** The authors clarified all my questions very well. They also added an extra plot for the double descent experiment on a different architecture (ResNet). Although I feel a bit lukewarm about the added plot (in that the double descent phenomenon is only somewhat weakly reflected by their empirical measure), I've increased my confidence score from 3 to 4 to appreciate their efforts in addressing my concerns. Good luck to the authors!", "extra_scores": {}, "extra_text": {}}, {"review_id": "leRSh2_60Nk", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 authors consider the problem of estimating generalization in deep neural networks, and propose a measure based on the ability to set a fraction of the neural network weights to zero (prunability). The authors introduce some theoretical motivation based on the PAC-Bayesian framework, and perform an empirical evaluation based on a set of convolutional networks trained on the CIFAR-10 dataset.\n\nThe problem of understanding generalization in deep neural networks is a fundamental problem of deep learning, and the results obtained by the authors present a potentially interesting perspective on the study of generalization in deep neural networks. The paper is well-written, and presents some interesting empirical results. However, the theoretical contribution is not  particularly novel, and is not complete enough to justify all the measures evaluated in paper. Due to this issue, I feel that the paper only has limited impact. I detail my comments on the theoretical and empirical results of the paper below.\n\nOn the theoretical side, the contribution for the case of “random pruning” is minor and is a straightforward extension of known results. Indeed, “random pruning” is similar to many other well-studied random perturbation schemes, and corresponds exactly to the case of dropout, a well-understood method. On the other hand, there does not appear to be any bound provided for the case of “magnitude pruning”, and it is not immediately obvious why such a measure should lead to a generalization bound. Indeed, existing work on using pruning and compression for measuring generalization (Arora et al. 2018, Zhou et al. 2019) establish bounds on the *pruned* network, and not the original network. Establishing a bound in terms of the “magnitude pruning” measure would be an interesting contribution, as handling such non-random modifications has been a challenge in the community. However, the authors do not seem to make any attempt at providing such a bound or a heuristic argument for such a bound to hold. Finally, the choice of measuring the prunability of a network as a proportion requires more careful justification in the context of magnitude pruning. Indeed, for “random pruning”, the proportion is easily interpreted as a magnitude of noise injected. However, in the “magnitude pruning” setup, with the parallels the authors draw to Occam’s razor and compression ideas, it is the absolute number of parameters which is more theoretically relevant than the proportion of parameters which can be eliminated: having 1 million parameters where half can be eliminated is still more complex than only having 100,000 parameters (where none can be eliminated).\n\nOn the empirical side, I found that the methodology was clear and well-adapted for the “random pruning” method, which is closely related to drop-out and other random perturbation ideas. With the addition of networks of different depth in the set of networks used for evaluation, the empirical methodology also seems appropriate for the “magnitude pruning” method and the parallels the authors draw to compression. However, it is not obvious to me that the empirical results support that connection, as we know that in architectures which vary substantially in size (e.g. MobileNet or EfficientNet), the compressibility (i.e. the proportion of parameters which can be pruned) is directly related to the size of the network (see e.g. Gupta et al. 2017), and I feel that this is a further indication that the choice of using the proportion of pruned parameters should be more carefully discussed.\n\nThe presentation of the empirical result could be improved by including (either in the main text or the appendix) the standard errors for the measured correlation for all measures, and ensuring that the tables are formatted similarly to the ICLR template for better readability (the latex package booktabs can be used for this purpose).\n\nOther notes: please ensure that you cite published versions of papers when they are available (instead of the arxiv pre-prints). For example, Arora et al. 2018 appeared at ICML 2018, and Zhou et al. 2018 [sic] appeared at ICLR 2019 (there are many other such cases in the references).\n\n=====================\n\nEdited after author response: I thank the authors for their considerate responses. Overall, my opinion remains mostly unchanged, and I share similar opinions to reviewer 3 and 4 that although the proposed idea is interesting and intriguing, the paper is not quite ready at this point. I would like to see the authors present either: 1) stronger empirical evidence for the importance of their metric or 2) a more solid theoretical foundation of the measure they propose.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "hFd_ZzW8e0k", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 the present work, the authors tackle the highly debated (and sometimes confusing) problem of finding a good simplicity/complexity measure able to predict generalization performance of deep networks. A novel measure called 'prunability' is introduced and compared with some of the many alternatives in the literature. This property measures how networks are able to retain low training loss when a fraction of the weights is set to zero, and is clearly related to common training practices (e.g. dropout) that seems to yield better generalization performance in practice. The experimental settings and the evaluation methods for this new metric are inspired by recent extensive studies on deep networks performance. The authors are able to show that prunability is in fact associated with good generalization and seems able to capture some non-trivial phenomena (double-descent), but they also find it to be inferior to pre-existing (margin based) measures. Moreover, the close relationship to perturbation robustness and flatness measures is investigated, but the results are not fully conclusive.\nIn my opinion, the idea behind this complexity measure makes a lot of sense, but: 1) it is already used explicitly in dropout, so I don't see how it could inspire the development of better training heuristics. 2) It is not easier to measure that most other complexity measures (in the random version). 3) It is closely related to pre-existing metrics. 4) More importantly, it is not more predictive of generalization than some alternatives already discussed in the literature. Therefore, I think that this works lacks at least one strong point that could motivate the inclusion of this latest complexity measure into the generalization debate.", "extra_scores": {}, "extra_text": {}}, {"review_id": "GTL93KJdg_y", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 proposes a novel generalisation measure, i.e., measurement that indicates how well the network generalises, based on pruning. The idea is to measure the fraction of the weights that can be pruned (either randomly, or based on the norms) without hurting the training loss of the model. The paper provides thorough discussion of the related methods and motivates the measure in multiple ways. Further, the authors show empirical evidence for the correlation of the pruning robustness to the generalisation ability of networks, based on the paper by Jiang et al., 2019 and dataset (updated with additional models) provided in the paper.\n\nThe paper is well written and states a clear goal of introducing and proving a generalisation measure based on pruning. The authors provide a nice discussion and lots of empirical evidence. Nonetheless, several points of motivation for the measure seem unclear to me:\n\n- the authors refer to Jiang et al., 2019 saying that there are lots of generalisation measures that correlate with performance, but that they fail to explain the test performance - which calls for another measure. If the experiments shown in Jiang et al. are demonstrating failure of explaining test performance, then the presented paper also does not provide many more evidences that the proposed measure is not failing.\n- the motivation for pruning as a way to improve generalisation is connected to the training procedures - dropout and lottery ticket hypothesis. Nevertheless, none of these methods improve generalisation when applied on top of already trained network. I would not say that lottery ticket retraining can be classified as integration of pruning into optimisation, as well as dropout improves training only when all the network is used afterwards.\n\nThere are several failures, that make me believe that more work can improve the paper:\n- The goal of the paper is to show a measure that will perfectly predict generalisation - but according to the experiments it can be outperformed by other measures on the presented dataset.\n- The theoretical justification seem unclear to me: what is the goal of introducing the generalisation bound (moreover even Appendix does not have details of derivation of the presented formula) if the authors notify themselves right away that it is vacuous. The justification is to give an intuition of how pruning connects to generalisation. It is unclear to me though, how it can be concluded based on a vacuous bound?\n- The idea to check the measures behaviour in double descent setup is very interesting, but only one measure is checked there and in a different experimental setup, without proper motivation for such change.\n- Section5.4.3 attempts to analyse casual connection between existing measures, that seems to me unclear by motivation as well - one wants to see causal connection to generalization, not other measures. Especially, that the table3 is discussed only for the random perturbations measurement - still not providing an answer what type of the connection is there between two.\n\nI would suggest to reject the paper, since the idea feels not being worked through enough. \n\nMinor comments:\n\n1 - it would be nice to have a discussion on the type of pruning used - does it somehow change the measurements in a predictable way?\n\n2 - typo in the first sentence of section3 (twice “denote”) \n\n3 - typo in the first sentence of the second paragraph of section3 (letter denoting data distribution)\n\n4 - table1 misses highlights of the “winning” approaches\n\n***\n\nI would like to thank authors for accurate answers and a lot of work put on reworking the paper. Unfortunately, I still find my concerns about motivation for the metric valid, which together with the rather weak performance creates a problem for this paper. I highly encourage authors to continue the work and try to explain the reasons for this correlation and find justifications for usage of the metric. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary: 
The authors propose to predict a neural network classifier's
generalization performance by measuring the proportion of parameters
that can be pruned to produce an equivalent network (in terms of
training error). Experimental and theoretical evaluation are provided.


Discussion:
The overall opinion in reviews was that the idea is
potentially interesting, but needs to be pursued further before
publication, and that the empirical evaluation in particular was
lacking. That was followed by a detailed discussion, in which authors
were able to address a number of concerns, and have provided helpful
additional experiments.

Recommendation:
This is a potentially interesting paper that is not quite there
yet. Although reviewers have raised scores in discussion, the case for
acceptance would still be hard to make. I recommend to reject.

It looks like a reasonable  amount of additional work will turn this
from what is now on the weak end of borderline into a potentially strong
submission, especially given the thoughtful and thorough feedback from
reviewers. The next top-tier
conference deadline is not far away, and I encourage
the authors to incorporate the feedback fully and resubmit soon.
That being said, I agree with reviewers that the theory provided is,
at present, not strong. Also, a point that still seems to require work
is the relation between prunability and the use of dropout.

Note to authors and chairs:
AnonReviewer3 explicitly stated in
discussion that they would raise their score from 5 to 6, but the
change was not recorded in the system. My recommendation assumes their score
is 6.
Decision: Reject