Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper aims to solve unstructured pruning as a bi-level optimization problem. To find pruning masks and values of unpruned weights, they define bi-level equations and perform two SGD-processes iteratively. Their goal is proposing a new method that can show comparable accuracy as IMP(iterative magnitude-based pruning) with restricted training time. 
strengths_and_weaknesses: ### Strengths
- For unstructured pruning of DNNs, this paper defines a bi-level optimization problem and shows theoretical contents for that.
This paper shows the comparable results of this method using various dataset and architectures.
- The compression (including re-training) time is not increased with various pruning rates.

### Weaknesses
- I have a concern on the real effectiveness of unstructured pruning. As many papers have been mentioned, there is no realistic acceleration method for unstructured pruning due to random locations of unpruned weights. There is no note for this widely-known problem. Even though this method is a novel idea for unstructured pruning, we cannot use this method for our inference. When using CSR formats (ex. cusparse library in CUDA), we must need higher pruning rates to gain faster inference speed. I think that problem is why there have been a few studies on unstructured pruning these days unlike structured pruning.
- In this aspect, this method can achieve outperformed results on lower pruning rates less than 50%. But, there is less noticeable improvement on effective pruning rates. So, in my opinion, the resulting accuracy seems to be not the main contribution of this paper. 
Moreover, the experimental results seem to be so restricted. We are living in 2022 and the neural networks have evolved since Song Han’s magnitude-based pruning. I don’t think the results on the CIFAR-10 dataset can prove the novelty of a pruning method. It can just show a pruning method works well. Most of the results on this paper are limited to the ResNet arch. and CIFAR-10 dataset. CIFAR-10 consists of just ten classes. I think this paper should extend the experimental results to various architectures (ex. MobileNet, Transformer, …) or bigger dataset with smaller model (ex. ResNet-18 on ImageNet). 
- Then, there remains another main contribution, faster pruning-retraining speed regardless of pruning rate. To strengthen this contribution, I think there should be more ablation studies and experiments. I’m curious why this method works with consistent time regardless of pruning rates. Or if I put much time for higher pruning rates, then can I gather higher accuracy by using this method?
questions: - How about bringing the Appendix B (including Figure A1) to the main manuscript? At the first time, it was a little hard to understand the overview of this method.  
- I don’t understand why LTH is referred as  a pruning method. As far as I understand, the LTH paper just used the magnitude-based pruning method for finding winning-tickets. LTH paper is a novel paper to represent why we train the over-parameterized neural networks, not represent a new pruning method. I think IMP with gradual pruning rates was proposed in Zhu’s paper (described below).
Why are the below papers not mentioned in this paper? There have been many other results on unstructured pruning methods.
  - Zhu, Michael, and Suyog Gupta. "To prune, or not to prune: exploring the efficacy of pruning for model compression." arXiv preprint arXiv:1710.01878 (2017).
  - Evci, Utku, et al. "Rigging the lottery: Making all tickets winners." International Conference on Machine Learning. PMLR, 2020.
Sidak Pal Singh and Dan Alistarh. Woodfisher: Efficient second-order approximation for neural network compression. Conference on Neural Information Processing Systems (NeurIPS), 33, 2020.
  - Peste, Alexandra, et al. "Ac/dc: Alternating compressed/decompressed training of deep neural networks." Advances in Neural Information Processing Systems 34 (2021): 8557-8570.

limitations: - This paper argues for an unstructured pruning method, but there is a critical issue on the unstructured pruning. I think this paper has no/less consideration on that.
- The experimental designs are so restricted. It should be extended to other challenging datasets and architectures.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Search for the winning lottery in the Lottery Ticket Hypothesis (LTH) is of great interest in the Machine Learning (ML) community and this paper aims to find such winning tickets (in most cases). This work formulates the model pruning (primarily unstructured but also extends to structured pruning) as a Bilevel Optimization (BLO) where the lower-level optimization finds the best possible set of weights given the sparse neural network (that is weight masks) and the upper-level optimization is optimizing for the boolean mask (done using continuous relaxation followed by threshold-based rounding). Authors first derive the general expression for the gradient with respect to mask using an implicit gradient, which involves second-order derivatives, matrix inverse, and (n, n) matrices where n in #parameters in the network. However, with the hessian free assumption and given the nature of the problem (bilinear in mask “m” and parameters “theta”), the final expression of gradient turns out to have only first-order derivatives. Having defined the expressions, they finally proceed to describe the algorithm which involves lower-level SGD and upper-level SPGD, done until convergence, which does happen, in practice. Then the paper proceeds to the experiments involving multiple architectures, multiple datasets, and different pruning ratios. Performance metrics involve final accuracy, performance relative to the dense pre-trained model, and overall run time. Strong experiments show that BiP achieves superior performance than the original dense model (i.e. finds winning lottery) and has a comparable (or superior) performance to iterative magnitude pruning (IMP) while having much lesser run-time similar to one-shot pruning methods. 
strengths_and_weaknesses: Strengths:

1. The Paper is concise and well written. 
2. The theory is easy to follow and the experiment section is strong involving ablations across different hyperparameters. 
3. Charts are well organized. 

Overall, I enjoyed reading this work. I’ve some suggestions which primarily are additional references to be discussed and some additional visualization that could help to make this a strong submission which I describe in the following weakness section. 

Weaknesses:
1. While the diagram is mentioned in the appendix, can the authors include an algorithm block for a better understanding of the overall flow? 
2. How are the diverse batches chosen for the training? Does it involve some kind of submodular optimization to get the schedule? What happens if the batch for SGD is qualitatively different from the batch of SPGD? 
3. The convergence result shown in the appendix involves final accuracy. Does this happen that the masks still keep on changing (that is finding the subnetwork) but all of that subnetworks have similar performance when trained (performed SGD)? 
4. It was mentioned that SGD steps are kept fixed to 1. However at the very first step of pruning, why would still having just 1 SGD step suffice? 
5. Table 1. Can authors add a vertical separator line for the datasets?

Additional references that can be discussed:
1. Soft Threshold Weight Reparameterization for Learnable Sparsity. ICML’20
2. EFFECTIVE TRAINING OF SPARSE NEURAL NETWORKS UNDER GLOBAL SPARSITY CONSTRAINT. CVPR’21
3. Rethinking Bi-Level Optimization in Neural Architecture Search: A Gibbs Sampling Perspective. AAAI’21

questions: As mentioned in the main review.
limitations: As mentioned in the main review.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides a novel reformulation of model pruning as a bi-level optimization (BLO) problem, in which the paradigm of pruning-retraining pruning can be viewed as two optimization levels: (1) finding the pruning mask (the upper-level), and (2) masked model retraining (the lower-level).

The paper further proposed an algorithm, bi-level pruning (BIP), to be a BLO solver that uses only the first-order gradient, which makes it as efficient as one-shot pruning.

The experiment results show that BIP equips the high efficiency of one-shot pruning and maintains the high accuracy of iterative magnitude pruning (IMP) in both structured and unstructured pruning schemes.
strengths_and_weaknesses: Strengths:

- The idea of the BLO reformulation of the model pruning problem is new, which provides a theoretical basis for BLO algorithms to be explored for model pruning. 
- The proposed BIP pruning algorithm is original and practical. 
- The paper is well organized and easy to follow.

Weakness:

- It would be really helpful to add some discussion about the similarities and differences between the BLO and the L0-based pruning (https://arxiv.org/pdf/1712.01312.pdf). L0-based methods view pruning masks as random variables defined by specific parameters, thus making the pruning masks could be learned together with the models. This is a different perspective compared to BLO. And these two views may be combined and unified, which makes it worth having a discussion and comparison.
questions: - It would be really helpful to add some discussion about the similarities and differences between the BLO and the L0-based pruning (https://arxiv.org/pdf/1712.01312.pdf). 
- In Figure 6(b1) the best accuracy is achieved when lower-level steps N <= 3, which would be unexpected and need some explanation. As a larger N tends to find more optimal model parameters that are close to $\theta^*$.
- Could you talk about the schedule of BIP to prune with multiple sparsity ratios? IMP could initialize from models with low pruning ratios to produce models with high pruning ratios. Thus when pruning for multiple ratios, the time complexity of IMP could be amortized. I wonder if BIP could be efficient in this setting.
limitations: The authors have addressed the limitations adequately. It would be better to move some ablation studies like Figure A4 to the main manuscript, though the pages may be limited.
review_title: null

final_score: rating: 2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.
review_content: summary: The authors (correctly) identify that iterative magnitude pruning (IMP) is inefficient to extract "winning tickets" from neural networks. To this end, they investigate a method utilising bi-level optimisation (BLO) to extract winning tickets -- including structured results which can easily yield real-world speedups. In the paper they formulate pruning as a BLO problem, and subsequently evaluate across CIFAR-10/100, Tiny-ImageNet and ImageNet. The results are consistently better than IMP, and gradient-based saliency methods such as Grasp.

==

See below for response to authors; score has been updated after rebuttal.
strengths_and_weaknesses: I am suspicious of the contributions of this paper, since the use of "winning ticket" seems to be overloaded in this work. In the abstract this term is defined as: "i.e., pruned sparse models with better generalization than the original dense models". But -- this is not the widely agreed upon definition. Lines 35 to 37 give the more widely accepted definition, but line 325 gives a different definition which I don't agree with. It is crucial that the work is self-consistent, and consistent with other literature.

Following on from this observation, it seems that the pruning is done throughout training. This cannot reasonably be compared to IMP or Grasp: the pruning mask is set at iteration 0 (or close to 0) and does not change throughout training. It is also worth noting that Grasp is not SOTA anymore: you should compare to ProsPr by Alizadeh et al. (cited by your work already). The only valid comparison I can see would be to the Early-Bird work by You et al. -- but you don't provide any in this direction. In addition, you have provided few comparisons to methods which prune after training, and perhaps do some small amount of fine tuning. These are also reasonable competitors to this work.

Finally, you are not the first to do bi-level optimisation for pruning. "Differentiable Network Pruning for Microcontrollers" by Liberis and Lane would be an example prior art (and I'm sure there are others).

Here are some more minor thoughts:

- Code is included which is very nice since the method is fairly complicated.
- I really commend this work for paying attention to structured pruning -- it's a really hard problem, and far more relevant than most other pruning directions -- but I am not sure you characterise the related work fairly. "Single Shot Structured Pruning" by van Amersfoort et al. and ProsPr by Alizadeh et al. both assessed this direction at initialisation.
- On L229 you say that we can assume $\nabla^2 l = 0$. I am not convinced this is actually true in practice: after all, this is how many earlier pruning saliency methods worked. However, I am not saying that this makes the work incorrect; approximations pop up everywhere in DL.
- Is there a good reason to use reference 18 as the benchmark rather than the benchmark provided by Frankle's missing the mark work? It is very extensive, and other works have built upon it in recent years.
- Figure 6a is not enough to justify the robustness to rewinding that marks a winning ticket. You've provided results on the smallest model with the easiest dataset. More difficult examples are needed.
- The final line of the conclusion is a bit concerning: in practice, structured pruning methods could prune the same number of parameters but yield totally different speedups. It is an important thing to measure.
questions: Many of the questions are motivated from above:

1. What is the definition of "winning tickets" used?
2. Is the pruning done continuously through training?
3. What is the motivation for not using Frankle's benchmark?
4. How fast are the channel pruned networks?
limitations: I don't think there is any explicit discussion of limitations in the main paper. The checklist points us to appendix C4 but there's nothing there regarding limitations (and I have discussed some above).
review_title: null

Meta-review: metareview: The reviewers had significantly diverging opinions on this manuscript. The main issue under discussion was whether the framing of this paper as a lottery ticket work was correct, given that the main evaluations use no reinitialization or rewinding. On balance, I think that while one reviewer was very negative about the paper, the disagreement was mostly terminological. The substantial concern is whether the evaluation comparison (wherein BLO with no rewinding is compared against methods that use rewinding in Figure 3) is fair. The authors respond to this by providing comparisons in Figures 6A and A11 that evaluate rewinding on some tasks. However, these figures seem to show that the accuracy of BLO is completely insensitive to rewinding—and even to complete reinitialization in the original lottery-ticket sense. This raises the natural question: why not just evaluate primarily in the reinitialized case, where there's no need to redefine the term "winning ticket"? That is, the whole presentation seems to be backwards. The way it should be presented/evaluated is:

* First, we show that BLO outperforms other methods in the classic lottery ticket regime, where we reset all the weights to initialization (100% rewind) — this would replace the present Figure 3. This would be a fair comparison, comparing classical-lottery-ticket-setting pruning methods to each other.
* Next, we show that one advantage of BLO is that unlike other winning-ticket-finding methods, its performance is invariant to rewinding. That is, if what we want is just accuracy of the pruned model (and not to do some sort of scientific investigation of the lottery ticket hypothesis) then BLO outperforms other methods when we don't do any rewinding at all.

With this sort of presentation, I think the authors could have avoided the negative reviewer's objections. Despite these presentational/terminological issues, I think that there's enough technical contribution here with Figures 6A and A11 to move forward with acceptance, especially considering the enthusiasm of the other reviewers and the technical novelty of the bi-level approach. The empirical results _are_ there (and Figures 6A and A11 show a clear connection with the lottery ticket work), they're just presented strangely. And I think there are not any fundamental technical issues here that forbid acceptance.
confidence: Less certain
Decision: Accept