Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a method to quickly find masks that allow DNN models to train with N:M sparsity. Prior works mainly leverage N:M sparsity for inference (i.e., forward pass), but training cannot directly benefit from N:M sparsity because model weights are transposed during backpropagation to calculate gradients. Therefore, the N:M sparsity constraints may no longer be satisfied during backward pass. The paper suggests that it is possible to find so-called N:M transposable masks, which allow both the forward pass and the backward pass of a DNN training to perform N:M sparse computation. One key challenge in this task is to find such transposable masks in a lightweight way since sparsity masks may need to dynamically change in order to get on-par accuracy as dense training. To quickly find masks that satisfy the N:M transposable mask constraints, the paper proposes to use a greedy-based approximation method. The authors show that such a method adds a modest amount of runtime overhead and scales almost linearly with respect to the input sizes. The paper conducts evaluations against some computer vision (e.g., ResNet) and NLP tasks (e.g., BERT fine-tuning tasks) to show that such a training regime can bring comparable accuracy as dense training.

main_review: Strengths:

-- The transposable mask is an interesting idea to enable the system capability of N:M sparse training. 
-- The proposed 2-approximation solution adds a low overhead in finding transposable masks.

Weaknesses:

-- The proposed transposable N:M masks add strong constraints to weight diversity, which may limit the expressiveness of the model. 
-- No real training speedups from the proposed method, because real hardware constraints are not satisfied. 
-- Lack of details of implementation and hyperparameter settings. 
-- Baseline results are inconsistent. 
-- No discussions on how model convergence or training dynamics are affected by N:M sparse training.

Comments:

1. The transposable N:M sparsity masks seem to add very strong constraints to the weight matrices, which might limit the model's expressiveness in a significant way. Indeed, after applying transposable N:M sparsity masks, there won't be enough mask diversity for 2:4 sparsity. As a result, the paper has to find the transposable N:M sparsity in 4:8. This is a deviation from real hardware constraints because no existing hardware supports 4:8 sparsity (Nvidia sparse tensor core supports 2:4).  The proposed method, therefore, cannot speed up training on real hardware either. It is disappointing as the paper motivates itself as a way to accelerate sparse training on real hardware in the introduction and only to find out later that the solution does not really work on real hardware. 

2. Some of the results of the evaluations are inconsistent, especially the baseline results. While the baseline results for ResNet18 and ResNet50 are 69.7% and 76.1% in Table 3, they become 70.5% and 77.3% in Table 4. Why are there two results for the same dataset and task? Which baseline should we look at? If we take 77.3% as the baseline result for ResNet50, then the proposed N:M sparse training actually leads to a non-trivial drop (77.3 vs. 76.6) in Table 3, and the "no accuracy degradation" claim is also not true. Please double-check the results and also provide detailed hyperparameter information. 

3. Despite claiming 2x speedup, no real training time is reported for all evaluations. The training cost depends on both the training time per iteration as well as the total number of iterations needed to converge. Although N:M sparse training might reduce the training time per iteration by 2x,  if the N:M sparse training takes more iterations to converge to get the same accuracy or introduces training instability, then N:M sparse training cannot really reduce the training cost and reducing the cost of finding transposable N:M sparsity becomes even less motivated.  Furthermore, the 2x speedup claim also seems to be problematic because (1) finding the transposable N:M masks still add non-negligible cost, which would make the speedup to be less than 2X, and (2) even with sparse tensor core, one cannot expect a 2x speedup because a DNN contains more components than just the matrix multiplication, such as non-linear functions or BatchNorm, which cannot be accelerated by sparse tensor core. 


4. The paper lacks details for implementation and hyperparameter settings. Can the authors add details for how the model has been trained, such as the number of update steps, the batch size, etc. for both the baseline and the N:M sparse training, as well as parameters for AdaPrune? The current paper doesn't seem like it could be reproduced. 

5. The proposed AdaPrune only seems to convert models trained with 8:4 to 4:2 for inference. Can it also be used to accelerate the training speed as well? 

6. The writing of Section 5 seems to be not good, with many typos and grammar errors. Just to give a few examples: 

In line 223, "…over regular training, The algorithms…" -> Change "," to ".". 
In line 249, "…where ASP do not." -> "does not"
In line 261, "…to accelerate training. but what should we do…" -> Change "." to ",". 
In line 262, "…wish to deployed the output…" -> "wish to deploy".

-------------------------

After a series of discussions, the authors have addressed my concerns. I have increased my score from 4 to 6.

limitations_and_societal_impact: Please see the limitations in the detailed comments.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors study N:M structured sparsity, specifically the challenge of finding N:M transposable masks so that N:M sparsity hardware acceleration can be exploited for part of the backward pass computation in addition to the forward pass. The authors additionally tackle the challenge of adapting models trained with other kinds of unstructured or structured sparsity to specific topology constraints supported by hardware. The authors provide a detailed analysis of the problem of finding transposable N:M masks and asymptotics associated with solving the problems and present a practical solution that achieves good results in practice.
main_review: Overall the paper is very well done. There are a few issues in the experiments I’d like to see resolved and then I believe this work will be an excellent contribution to the community.

Introduction and Background
1. Structure causing accuracy degradation in sparsification is not a hypothesis. It’s well documented empirically [1, 2].
2. “However [unstructured sparsity’s] hardware cost makes it infeasible to use on modern architectures“. Recent work has shown that unstructured sparsity can be accelerated, although it still requires high sparsity to exceed the performance of dense computation [1, 3].

Experiments (Changes Required)
1. Table 3, claiming a ‘2x” speedup over ASP is not correct. 2x more of the FLOPs in the model can now be accelerated by sparse tensor cores, which provide up to 2x performance over dense tensor cores. Let's say dense models speed is (fwd + bwd + update) / dense_throughput. For simplicity, we’ll say fwd = bwd = update so baseline takes 3 * fwd / dense_throughput seconds. The ASP model would then take fwd / (2 * dense_throughput + 2 * fwd / dense_throughput = 2.5 * fwd / dense_throughput. Your model would then take 2 * fwd / (2 * dense_throughput) + fwd / dense_throughput = 2 * fwd / dense_throughput. Thus, ASP provides a 3 / 2.5 = 1.2x speedup over the baseline and you would provide a 2.5 / 2 = 1.25x speedup over ASP. In reality your speedup will be lower because not all operations (e.g., batch normalization, activation functions) are accelerated by sparse tensor cores and the sparse tensor core operations will not fully realize the theoretical 2x gain over the dense tensor cores. This should be corrected in the authors’ response.
2. I understand that 4:8 transposable masks have a similar MD to 2:4 masks but comparing 4:8 sparsity to 2:4 sparsity is not apples-to-apples as I expect 4:8 sparsity will make it much easier to maintain model quality. I like the inclusion of 4:8 sparsity results, but I’d also like to see 2:4 transposable results to see what the accuracy loss looks like in comparison to non-transposable masks.
3. In Table 2, what N:M are used? As I understand it, the algorithm complexity depends on these factors.
4. X-axis in Figure 5 (b) should be scaled by 100 to be percent.

Experiments (Changes Suggested)
1. The hypothesis that MD is correlated with accuracy would be made much stronger with results on other kinds of structured sparsity. For example, block sparsity and channel-sparsity. As someone who works on this topic, I’d be very interested to see these results.
2. In Table 1, it might be nice to include the MD normalized to unstructured as well. This would make it easier to compare across the different structures for the reader.
3. Most sparse training algorithms only perform mask updates periodically to reduce overhead (and also because it usually leads to higher accuracy). The update period is usually ~100 (e.g., with RigL). 40 is a tighter bound, but you could also run 100 (in Table 2) to align with prior work.

Organizational, Spelling and Grammar
1. On page 2, your 3 questions are in a different order than they’re shown in your diagram (Figure 4)
2. “sparse core tensor” should be “sparse tensor core”
3. “|” before “In” should be deleted.

Additional Improvements
1. Nvidia has recently proposed using permutations to reduce accuracy loss (talk, poster from SNN). How do permutations affect your MD metric? Do the results still correlate with accuracy? Do they make finding transposable N:M masks more difficult? These might be interesting questions to discuss in your conclusion.

References
1. https://arxiv.org/abs/1911.09723
2. https://arxiv.org/abs/1811.00206
3. https://arxiv.org/abs/2006.10901

limitations_and_societal_impact: I did not identify potential negative societal impact in this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The sparse tensor core introduces the N:M sparsity in the latest Nvidia Ampere GPUs,  which bring sparse neural network deployment into the mainstream.  Most methods only focus on improving sparse model performance and compression ratio rather than speed up the training phase.


main_review: This paper proposes a method to utilize ampere GPUs sufficiently by exploring N:M sparse training. To find the optimal transposable mask, this paper formulates the problem as an integer program solved by an approximated algorithm (2-Approximationalgorithm).

Strength:
      1. Direct sparse training using modern hardware is an important direction to train gigantic models [2]. 
      2. The 2-Approximation algorithm is novel and efficient.
      3. The performance of ResNets and Bert models is persuasive.
      4. The code is available and can reproduce the results.

Typo: line 273  "N   :  M "       

The main flaw of this paper may be the gap between theory and practical.  I look forward to authors give more discussion.

Overall, this paper goes out an important step about fully sparse training, which should draw more attention in the future.

I am inclined to accept this paper. 
limitations_and_societal_impact: The main flaw of this paper may be the gap between theory and practical.  I look forward to authors give more discussion.
review_title: null

Meta-review: I want to thank the authors for their active engagement with the reviewers in the rebuttal period, and I'm happy this lead to some modification of the paper (as outlined by the authors) that I think greatly improved the work. 

The proposed method seems novel and valuable to the community, coupled with thorough experimentation and a clear exposition, I think this paper matches the requirements for the conference. 
Decision: Accept (Poster)