Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work is focused on efficient learning of N:M sparsity from scratch. Finding the optimal N:M sparsity pattern is characterized as jointly solving a series of combinatorial problems with finite collections of candidates. The authors proposed to associate a learnable score parameter with each possible combination and learn it from data with the help of straight-through-estimator (STE). The experiments showed the proposed training method yields slightly better results with much fewer FLOPs compared to stronger baselines and much better performance than others.
strengths_and_weaknesses: Strengths:

+ This work successfully showed that N:M sparsity under a kind of gradual pruning manner can work well on large modern neural networks. The gradual pruning enables the possibility of a efficient method that trains N:M sparse models from scratch so that the expensive dense training process can be avoided.

+ Experiments are promising in terms of performance and FLOPs.

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

Weaknesses:

- The biggest issue of this work if over-claiming. Characterizing the problem as jointly solving a series of combinatorial problems is trivial, and more importantly, does not simply the original problem in any sense.  The authors claimed that they adopted a "divide-and-conquer" method. But according to my understanding of "divide-and-conquer", this claim is not true. The problem is not simplified into simpler forms with lower complexity. It is still a complex joint optimization problem. And the authors uses a simple method that learns a score for each combination. This type of methods is not new and can date back to network slimming (Liu et al., 2017).
- The only place that the learnable scores are used is eq. (8). But if I understand correctly, removing the S score in eq. (8) does not influence the whole methods at all. If that is the case, I am quite doubtful of what scores are learnt finally.
- For a paper that emphasizes its training efficiency, there is no energy or wall-time comparison of the proposed method and other baselines. This is related to another of my question that --- whether Nvidia A series GPU can exploit the gradually increasing N:M sparsity to improve training efficiency?
questions: Please see the weaknesses part and address my questions there.

The superscript of $\mathcal{L}^l$ in the last term of eq. (9) seems to be in the wrong place.
limitations: Please see the weaknesses part and address my questions there.
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: This paper formulates the N:M sparsity as the combinatorial optimization problem. 
This formulation is a well-motivated and promising direction. Then the authors use a learnable score matrix to measure 
the candidate's importance. The authors use the gradients of group elements to update the score matrix.
strengths_and_weaknesses: Strengths:


This paper is well-written and easy to follow.

The performance gain is consistent on various sparse ratios and models.

At present, reducing the sparse model training cost can motivate the research community to study sparse training acceleration.

The source code is available.

Weaknesses:
The authors are encouraged to conduct experiments on other tasks.

The authors only report the training  FLOPs, the authors are encouraged to report the training time.
questions: See Strengths And Weaknesses


###############################################

Post-rebuttal: I have read the rebuttal carefully, and all of my comments/questions were addressed. Thanks.
limitations: Na
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Authors tackle the problem of a learnable structural sparsity parametrized by N:M pattern. The best sparsity patterns per layer are found via divide-and conquer like algorithm where from a large set of proposals only one is selected in the end. At first, all possible candidate combinations are proposed, then, during training they are ranked according to the importance variable. At every algorithm step, the combination with the lowest score is removed from the pool. Finally, the last standing combination is selected. Experiments are performed on Resnet50 and DIET model on Imagenet.  

strengths_and_weaknesses: Paper provide a comprehensive overview of existing pruning paradigms (structured and unstructured). Ampere sparsity N:M is also clearly introduced. 
The problem of structural pruning is usually not formulated a combinatorial problem. The fact that authors do makes the paper stronger and the approach sound. Particularly, formulation in section 3.2 is sufficient. The implementation of learning score matrix S is a bit unclear and answering questions from the section below will help to understand the paper better. 
The code is available to reviewers, I went over it but didn't run. 
questions: Formulation of the implementation is a bit confusing. Does it mean that during training all combinations contribute to the output of the layer? If true it will mean higher memory cost during training and higher computational complexity. 
From another perspective, if S is implemented via straight through estimator than it is sampled during the training and the gradient propagates only to the elements with S = 1. Please clarify this point. 
Score matrix. Does it mean that the score is a real value learned by the model? Is there any evidence that it does reflect importance? Authors provide derivation to end up with magnitude times gradient equation. However, providing some empirical evidence will be beneficial. 
Can authors explain how to set newly introduced hyper-parameters and what is the intuition behind the choice? 
Was the training recipe exactly the same when compared to SR-STE? 
limitations: At my current understanding, the cost of initial epochs is going to be higher due the requirement of forward0backward to be performed over all candidates. It will be nice to have some latency study as authors primary focused on efficiency of N:M sparsity.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper deals with the problem of N:M sparsity and proposes an effective method with structure parameter to weigh the importance of different combination. The final result is appealing. 
strengths_and_weaknesses: Strengths:
1. Good final pruning results


Weakness:
1. From the analysis of [1] Efficient Neural Network Training via Forward and Backward Propagation Sparsification, the gradient-based sparse training method cannot exceed the accelearation above a upper bound of around 1.5x since the gradient to structure parameters require dense gradient calculation, even though the gradient to weights is sparsified and the forward propagation is sparsified. I think this is a fundamental problem and unless the discussions around training costs are corrected, it should not be published. Otherwise it will again mislead the community. If this issue can be corrected, I am happy to raise the rating score to be positive. 

After rebuttal: I got the difference. The gradient calculation to auxiliary parameters only finally cares about the gradient to weights. I raise the score.

questions: The problem of training cost saving should be corrected.
limitations: The problem of training cost saving should be corrected.
review_title: null

Meta-review: metareview: The paper presents a novel method on training N:M sparse-weight neural networks, which can be significantly accelerated by NVIDIA A100 GPUs. The optimal N:M pattern can be found via jointly solving a series of combinatorial problems with finite collections of candidates. Majority of the reviewers found the paper 

The AC believes that the concern of 11EU can be solved by re-phrasing the descriptions but doesn't affect the effectiveness and novelty of this paper.
confidence: Certain
Decision: Accept