Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

The 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:

- 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.
- 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.

There are several failures, that make me believe that more work can improve the paper:
- 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.
- 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?
- 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.
- 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.

I would suggest to reject the paper, since the idea feels not being worked through enough. 

Minor comments:

1 - it would be nice to have a discussion on the type of pruning used - does it somehow change the measurements in a predictable way?

2 - typo in the first sentence of section3 (twice “denote”) 

3 - typo in the first sentence of the second paragraph of section3 (letter denoting data distribution)

4 - table1 misses highlights of the “winning” approaches

***

I 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. 
review_title: Pruning as Generalisation Measure

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

The 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.

On 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).

On 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.

The 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).

Other 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).

=====================

Edited 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.

review_title: Interesting ideas with potential but weak theoretical justifications

final_score: rating: 7: Good paper, accept
review_content: ## Paper summary

In 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.

1. 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). 

 Then they compute three different previously-proposed statistics:
   - 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)
   - b) adjusted $R^2$: here prunability performs just as well as other measures (although normalized margins outperform again.)
   - 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.
   
2. 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. 

3. 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.


## Strengths

1. 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 
provides 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.

2. 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?).


3. 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.

## Weaknesses

4. 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.


## Overall opinion

This 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.

## Clarification questions

5. 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). 

6. Could you clarify the claims in the first paragraph of 5.4.1? Specifically 
>"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" 

seems to contradict later observations that on some evaluation metrics they are all just as good as each other on adjusted $R^2$.

### Minor suggestions

- Under Table 1 and 2 would be nice to remind the reader as to whether larger values indicate better predictivity or not.
- Is the usage of adjusted $R^2$ inspired by Jiang et al., 2018? If so, would help to cite them appropriately.
- Page 12 typo "Vargins" --> "Margins"

### Suggested citation

"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.)

### References 
- Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic
generalization measures and where to find them. arXiv preprint arXiv:1912.02178, 2019.

- Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the generalization gap
in deep networks with margin distributions. arXiv preprint arXiv:1810.00113, 2018.

- Wesley J. Maddox, Gregory Benton, and Andrew Gordon Wilson. Rethinking parameter counting
in deep models: Effective dimensionality revisited, 2020.


**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!
review_title: Solid empirical observations connecting prunability to generalization in deep learning

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.
In 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.
review_title: I think that the authors propose a sensible research direction, but the presented results might be insufficient for justifying the introduction of an nth complexity measure in the generalization debate. 

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