Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper investigates when neural pruning approximation bounds useful from several perspectives. Showing that approximation bounds are loose and require a large sample size. It also explores the influence of fine-tuning after pruning by approximation bounds.

However, I a bit concerned about the novelty and impact of the paper. I cannot find border impacts and applications on the topic discussed in the paper since all results are based on observation. No further insights on tighter bounds or discussion of the reasons proposed. I would increase my score if those insights provided.

Also, in the last line of page 6, the author mentions Figure 4.2 which does not appear in the paper.
review_title: Good observation but a bit lack of novelty

final_score: rating: 6: Marginally above acceptance threshold
review_content: Overall, I vote for accepting. I like the idea of analyzing the practical performance of coreset-based pruning methods and discussing the relation between sparsity, approximation bounds, and accuracy. 

Pros:
1. The paper provides an empirical evaluation that shows the theoretical bounds of coreset-based algorithms could be loose.  This is an important issue for the practicability of coreset-based algorithms.
2. The paper shows the tight approximation bound is not a necessary condition for accuracy by analyzing fine-tuning. The quantitative results that fine-tuning increases approximation errors are interesting.

Cons:
1. The paper regards the loose bounds as a shortage that weakens the predictive power of coreset-based pruning methods. But this can also be regarded as an advantage of coreset-based algorithms that can heavily increase sparsity while maintaining accuracy. I suggest the authors to give more discussions on both sides.
2. The experiments only consider coreset-based pruning methods since they have provably guarantees. However, due to the empirical results of fine-tuning, we can recover accuracy after post-pruning. Then it is interesting to also compare with other commonly-used pruning methods, e.g., compare the sparsity of different pruning methods that achieve the same accuracy with fine-tuning. 

Some typos:
1. Figure 2 -> Table 2
review_title: The paper considers the trade-off between sparsity and fidelity by neural network pruning. It provides an empirically evaluation of the predictive power of two recently proposed methods based on coreset algorithms, and identify several circumstances in which the bounds are loose. It also examines the role of fine-tuning in prunability and observes that tight approximation bounds could be poor predictors of accuracy.

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper studies recent approximation bounds of coreset-based pruning strategies for neural networks.  It concludes that the bounds in certain cases can be very conservative (guarantee much lower accuracy than seen in practice), especially if the network can be fine-tuned after pruning,  and should not be used as a guide to estimate expected accuracy.  

While the conclusion that the bounds can be conservative is not unreasonable -- that was not the point of the papers it tries to criticize, bounds do not have to be good estimates.  Furthermore, I find the paper to be poorly and confusingly written, with many questionable choices done in setting up error metrics, and the experiments (please see details below), so I recommend to reject it. 

A bound on performance and an estimate of performance serve different purposes.  Even tight bounds that can not be improved may give poor estimates, but they are still useful in providing theoretical understanding of a problem, and possibly in safety-critical applications where one needs to guarantee worst case results.  So the criticism of the paper may be besides the point of the papers it analyzes.  They are among the first to show that coreset-based methods allow any kind of theoretical approximation guarantees, but they do not claim that the bounds are good predictors of performance.   The present paper would have more value if it attempted to improve the bounds, or perhaps develop accurate estimators of accuracy vs. pruning level, or maybe propose a pruning method which is more effective empirically. 

Furthermore, for a given neural network that has been pruned it is fairly inexpensive to numerically evaluate the approximation accuracy w.r.t. to the full model on a validation set -- so I do not see much practical value of the exercise of trying to infer it from bounds.  Furthermore, for pruned networks that have later been fine tuned,  indeed the results of the papers do not apply, so the bounds unsurprisingly may have little to do with empirical results. 

Detailed comments (non-exhaustive list of issues, but sufficient for my rating):

1) You go from additive and multiplicative bounds to error rates in lemma 3.1.  Just because epsilon > (f(x)i - f(x)i')/2  does not guarantee that it will make a mistake (it has the ability to make a mistake, but it does not have to).  Lemma 3.1. is on the one hand elementary, but on the other hand it introduces another layer of approximation between accuracy and pruning. 
2)  "guaranteeing that 50% of the development set labels that are correct will remain correct"...   The goal of approximating a neural net is to make sure that the output of the approximate NN matches the original one -- how is it relevant whether the original was correct or not w.r.t. to the target labels?  Why do you condition on predictions being correct?  
3) 'fine tuning can recover large amounts of accuracy while simultaneously maintaining of increasing approximation error" ... That doesn't make sense.  Do you mean 'improving' or 'reducing' approximation errors? 
4)  Sections 2.1 (and same for 2.2).   A lot of important details are left to appendix -- this section gives very little useful information to understand the method.  Where is algorithm 1 -- is it in your appendix or is it in Baykal's paper?  Where are the theorems -- in your paper / appendix / Baykal's paper?  What is the 'importance', how is it computed? A more informative intro would be much appreciated. 
5) The easy problem is a NN with 90 to 95% of weights set to 0.  The network is refitted, and 0-weights are re-enabled?  What does it mean for 0 weights to be re-enabled?  If the pruning strategy keeps the 0-edge -- does it mean the edge is active and the network is non-sparse?  This is very confusing (either poorly described, or this is an artificial corner case). It seems hard to imagine that a coreset pruning method that is given a sparse network will make it less sparse.  
If on the other hand the accuracy bounds somehow ignore edges which are already 0 -- then it seems like an easy opportunity to derive better bounds?
6) For the above easy network (with mostly zero weights) -- the coreset algorithm gives more than 50% of elements with probability 0 of being sampled, so the conclusion is that if we ask for 50% sparsity -- it will run forever?  This whole discussion just seems very strange and confusing. 
7) does 90% sparsity mean that there are 90% zeros or 90% non-zeros?  Maybe use clearer language. 
8) The discussion of scaling up the bounds due to total homogeneity --  also seems very strange: the paper claims that positive homogeneity allows to 'arbitrarily increase or decrease sample complexity by scaling the appropriate weight matrices by a constant factor'.  Is this for the additive or multiplicative bound?  The paper says "investigating the full implications of this observation are out of scope of this paper".  I would expect some discussion here.  For the additive bound -- if you scale up the weigths in NN, the relative approximation error will be much smaller, so isn't it natural to require larger sample complexity? 

review_title: Review of "When Are Neural Pruning Approximation Bounds Useful?"

Meta-review: This work studies corset-based pruning strategies for neural networks, and highlights the looseness of approximation bounds, the difference between approximation error and probability, and the importance of considering post-pruning fine-tuning. I found the empirical findings and concerns raised around the utility of approximation bounds for pruning guarantees interesting and important, and appreciated the benchmark with varying levels of difficulty. However, the empirical analysis was limited to coreset-based methods and a simple LeNet architecture, and could benefit from considering additional non-coreset based approaches, architectures, and datasets. While I agree with the authors that new methods are not required for their work to be valuable, I believe that a more thorough empirical analysis is needed to support that their claims that current approximation bounds are not useful across wider experimental settings.
Decision: Reject