Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: In this paper, the authors proposes channel permutation to improve the accuracy of N:M sparsified networks. Compared with previous works on N:M sparsity, channel permutation could maximize the magnitude of the weight matrix after N:M sparsification. Thus, the accuracy of the sparsified network could be preserved. To find the optimal permutation, a greedy searching algorithm is proposed, which is enhanced by two local minima escaping techniques including "bounded regressions" and "narrow, deep search". The effectiveness of the proposed channel permutation and local minima escaping methods are validated by experiments on a sufficient number of network architectures. 
main_review: Pros:
1. The idea of channel permutation for N:M sparsity is quite novel. 
2. The problem of finding the optimal channel permutation is well addressed by the greedy search and the local minima escaping technique.
3. The experimental results validates the benefits brought by the proposed method.

Cons:
1. Some of the details in the paper is not well described. 
    Line 160: It is very clearly how the term $W_{50\%\_rows}$ is defined. Is the 50% sparisty constraint applied to each row of the matrix independently?
2. Missing references to recent work on network pruning.
[1] https://arxiv.org/abs/1903.10258
[2] https://arxiv.org/abs/2003.08935
[3] https://arxiv.org/abs/2006.12813


limitations_and_societal_impact: The authors have addresses this problem properly.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Recent nVidia chips support hardware acceleration of structured sparsity patterns in weight matrices — specifically 2:4 sparsity where consecutive groupings of 4 entries have half of their entries set to zero.  The naive way to exploit this acceleration in deep learning is to prune weight matrices so as to meet this sparsity requirement, but doing this naively can be suboptimal if some groups contain many “important” weights and other groups contain all zeros already — it would be better if the “important” weights had a better distribution across groups.  So this paper proposes a way to permute the weights such that the pruning yields less loss.

The main idea is that if we can permute the weight rows/cols appropriately, then we can force pruning to give something that has more weight magnitude. The authors introduce permutation efficacy (and show on Imagenet experiments that this makes sense and acts as a kind of proxy for quality) and present a (mostly) greedy algorithm for optimizing this measure.  Final experiments on a number of Imagenet trained architectures show accuracy improvements over the naive method.

main_review: There are several strong points in favor of this proposed method.  First, it does not change running time for inference — (so the benefits are free in some sense) and does not require retraining or fine tuning.  The proposed method is also fairly intuitive (seems natural).  And finally it yields positive results in terms of accuracy — and according to the experiments seems generally applicable across a range of networks.

The weaknesses of this paper is that there is limited upside (the improvements seem to be quite small on average). There is also no discussion of running time of the optimization (I agree this time can be amortized away, but I believe it should be discussed). Finally, exposition needs improvement — I found a number of statements to lack in mathematical rigor (more details below) and some of the figures to be confusing which increased the cognitive burden of reading this paper.

Overall, though I find the paper to be somewhat incremental - I believe it’s worth sharing this with the community so I lean towards acceptance.


More detailed comments:
* It’s presented starting from the beginning as if it is obvious that preserving weight magnitude corresponds to good final accuracy, but this is not actually obvious (and I believe the authors recognize this in the experiments). It would be good to have a more transparent discussion about this issue at the top of the paper.
* The proposed method ignores the fact that the output channels can also be swapped and intuitively, optimizing jointing for swapping both the rows and columns of a matrix, one could achieve even greater efficacy — I wonder if it would be worth commenting on this possibility somewhere (or tell me that I’m wrong).
* Several times, the authors mention “applying the 2:4 constraint” without explicitly spelling out what this means exactly — does this just mean, dropping the lowest magnitude 2 weights in each group of 4 consecutive entries?  Or is there something fancier happening here?
* The Figure 2 example is very confusing to read — I would recommend that the caption identify the colors, label what every arrow represents and explain the permutation notation (e.g. does [1,0,2] mean that we permute row 0 to be first, row 1 to be 0th, etc?).
* More on this point, permutations are never really defined and this causes problems throughout.  At some point for example, the authors say that “a permutation is unique if its stripes channels are in sorted order…” — but what are the stripes of a permutation (I think I can infer, but it would be best to not require the reader to have to)?  I recommend stating upfront, that each weight matrix is associated with a permutation, saying how the permutation is notated and what index spaces it maps between.
* Table 1 ablation: given that efficacy is not clearly connected to final preserved accuracy, why not just report preserved accuracy here? Also I recommend reporting running times — it seems like the more exhaustive the search, the better optima the algorithm was able to find (which is not surprising). What if we were to compare against a random baseline where we just evaluate thousands of random unique permutations and take the best?
* Figure 3: report original dense performance/accuracy?
* Line 141: “to keep the network graph consistent” — don’t you mean to keep the parameterized function equivalent?
* Final minor thing: this pdf file is 38 Mb which is huge given that there are no graphics in this pdf and I don’t know if a printed screenshot was submitted instead of an original pdf… but it’s also not possible to search the document which made reading hard if I had to do a search within the document for a particular term.



limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper focuses on fine-grained block sparsity setting (N:M sparse network) and in specific the case where a pre-trained model is given and one wishes to extract an N:M mask and retrain. The authors suggest using channel permutation to reduce the initial accuracy degradation and demonstrate a significant accuracy boost on parameter-efficient models using their method.  They suggest two greedy methods to find a good permutation. Additionally, the authors used their method to transform several layers from an unstructured sparse model to an N:M structure sparse layers. 
main_review: Pros:

1) The main idea of the paper (channel permutation) is simple and seems to work. 
2) While the idea is not novel as it was suggested before [1] for a different type of pruning it was never used for N:M sparsity. 
3) The authors check their approach on several models.
4) The authors demonstrate that given enough resources their algorithm can find the optimal permutation. 

Cons:

1) The paper is poorly written and hard to follow. There are many terms that were not defined or defined in the appendix without reference. For example, G in line 174 was defined only in the appendix and DGRAD in line 346 was not defined at all.
2) While channel swapping is clearly a combinatorial problem it was never discussed or formulated (is this an NP-hard problem?). I believe that finding the right formulation would enable using open-source parallel packages for combinatorial problems.
3) No code!  paper with no code has a much lower impact as other researchers would probably avoid using or extending it.

Questions:

1) While table 2 demonstrates that OSG is much better than channel swapping, and figure 3 demonstrates that weight average efficacy correlates with accuracy improvement. The authors did not present results with simple channel swapping. Thus, it is not clear why the OSG overhead is required. 
2) OSG is clearly not a very light technique, can you comment on the amount of time it takes to find the best permutation (with OSG(3)-BR-1000, OSG(2) BR-1000, channel swap). 
3) Have you tried to fix the bias as suggested by [2] perhaps it should help with “unstructured to structure”  experiments as suggested by [2]. I also believe you should mention [2] in this paragraph. Finally, it might help for “fine-tuning” experiments with parameter efficient models (table 2) as well. 

[1] Ji et al., TETRIS: TilE-matching the TRemendous IrregularSparsity

[2] Hubara et al., Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Masks. 
limitations_and_societal_impact: The authors discussed the potential social impact but did not address the limitation of their study.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a channel permutation method to maintain the important connections. the idea is very interesting and meaningful. 
main_review: Strong points:

This paper emphasizes the drawback of N:M sparsity when each group only has M elements.   

To handle the local minima solutions, this paper proposes the bounded regression method, which is simple yet effective, to escape local permutation.

The channel permutation method does not incur inference cost and can handle the complex structure of DNNs, These points are important for sparse neural networks. 

the experimental on ImageNet1K support the claims with various CNN-based models. This paper is a good practical work to facilitate the deployment of N:M sparse model.


Weak points

The experiments only consider the classification.


Overall, I am inclined to clear accept this paper.
limitations_and_societal_impact: Weak points

the experiments only consider the classification.
review_title: null

Meta-review: This paper suggests an interesting permutation based method which closes the (sometimes small, but significant) performance gap in 2:4 fine-grained sparsity. The reviewers were all positive, and it seems most of their clarity-related concerns were addressed in the authors' response and the following discussion. I ask the authors to address all these issues in the camera-ready version to improve the readability of the paper and publish the code, as promised.
Decision: Accept (Poster)