Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 1) The paper proposes a novel layer-wise mixed N:M sparsification method, i.e., each group in a kernel can have different N. Compared to traditional layer-wise uniform sparsification methods, main techniques include group-wise threshold and layer-wise penalty (FLOPS and layer-wise redundancy).
2) Experiments on ResNet18 and ResNet50 show that for equal model size, the proposed methed achieves higher FLOPS compared to a most recent uniform N:M method [5]; for equal FLOPS, the proposed method achieves a smaller parameter number compared to [5].
main_review: Pros.
1) The proposed method adopts a novel mixed N:M scheme, while a most recent N:M method [5] adopts uniform scheme. As shown in Experiments (Section 4.1), the proposed mixed scheme significantly improves compression ratio, compared to the traditional uniform scheme.
2) The proposed layer-wise penalty factor in Section 3.4 explicitly quantifies contribution of layer-wise complexity (FLOPS) and layer-wise redundancy, while previous methods [5,19] do not explicitly quantify the penalty factor as such.

Cons.
My major concern is that technical details of the proposed method are similar with recent N:M methods [5][19]:
1) In Section 3.2, the paper adopts "the mean of the smallest M/2 elements as threshold". However, a similar M/2 scheme is also adopted in a recent N:M method [19].  The authors need to explain differences between these two M/2 schemes.
2) In Section 3.3, the proposed weight update rule in Equation (4) is similar as the update rule adopted in a recent N:M method [5] (See Equation (4) in the paper [5]). Both these two update rules set regularization for the pruned parameters. The authors need to explain differences between these two weight update rules.
limitations_and_societal_impact: In Section 6, the authors state two limitations. For the first limitation on "did not benchmark deployment gains ...", I agree that adopting theoretical computation complexity (FLOPS) is an appropriate solution. For the second limitation about no experiments on Transformer, I think the current experiments on CNNs are sufficient already.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose combining two existing techniques, N:M sparsity and per-layer (rather than uniform/global) pruning rates.  By allowing each layer to choose a particular N:M pair, the network can find a configuration that is not constrained to sharing a single N:M.  The solution is DominoSearch, an algorithm which starts with pretrained (dense) weights and determines a pruning threshold for each group of M weights based on the initial values.  Some number of iterations of fine-tuning adjust the weights gradually lower, in turn reducing each layer's chosen N.  Once some complexity target (either parameter or FLOP count) is hit, the network's layer-wise N:M are frozen, and the weights are finally fine-tuned.  A layer-wise penalty factor adjusts the overall complexity metric to account for layers which have relatively more or fewer FLOPs.  Empirical results show compelling reductions in FLOPs and parameters when compared to training with unstructured sparsity or uniform N:M sparsity.
main_review: ## Originality

The idea to start with a high N that drops over time is akin to iterative magnitude pruning for unstructured sparsity, but I haven't seen a principled approach for N:M sparsity that doesn't rely on sweeping hyperparameters, etc.  Similarly, pruning different layers to different amounts is nothing new, but it is when applied to N:M structured sparsity.

## Quality

I'm concerned that the comparisons used to make claims like "… [the proposed result] is competitive to accuracy of the state-of-the-art layer-wise unstructured-sparsity model" aren't fair.  Particularly, the problem being solved: DominoSearch is an algorithm to choose N:M values per layer of an already-trained dense network, but all comparisons are to algorithms which induce sparsity "from scratch," i.e. during the initial training process, without first training a dense network.  Looking instead at a result for 80% sparsity (roughly matching the 25.6->5 Mparams result from Table 2) from Figure 5 in [1], the accuracy is 76.52%, barely reduced from the baseline of 76.69%.  (This result is two years old, so the SOTA may have advanced since then.)  Does it make sense that accuracy for structured sparsity would be higher than accuracy for unstructured sparsity?  If this is the case, then is it due to regularization, suggesting that the dense model was poorly trained to begin with?  If, as you point out, unstructured sparsity is believed to be the upper bound, but you find that it isn't, I'd expect some discussion of why this commonly-held belief is not true.
	
Similarly, for the uniform N:M case, the comparison seems to be against SR-STE, which is a method to find N:M masks during training (with no fine-tuning).  Instead, a better comparison would be to use the method implemented in the submission's [6] (or, the more recent whitepaper[2], which may be a better source than [6] and [4] (which is not titled appropriately in the bibliography)), which uses the same "start with a dense model, determine a mask, and fine-tune while enforcing the mask" process as this submission.
	
If we set aside the comparisons to inappropriate baselines, the algorithm does seem to work as advertised: the ability to optimize for either FLOPs or number of parameters is great, and Table 4 suggests that for a small data set, layer-wise N:M is superior to uniform N:M at a given FLOPs or parameter target.  (Unless, of course, these results also use SR-STE for the "uniform" representation; it's not clear from the Table, but all other results do use SR-STE.)   Further, there's no catastrophic accuracy loss, so the resulting models are plausibly useful, particularly when compared to a dense model with equivalent complexity.
	
A comparison of the layer-wise N:M vs. uniform N:M at the same accuracy (as dense) would be useful.  For example, from the results in Table 3, the user must make hard decisions.  Would it be better to start with RegNetX1.6 and prune by an overall factor of 4x (FLOPs) to reach the 400MFLOPs target?  If accuracy were the same as the unpruned RegNetX3.2, the choice is easy - there's no downside to pruning RegNetX3.2, and RegNetX1.6 cannot reach that accuracy.  Existing results for uniform 2:4 sparsity show that accuracy is maintained (at 50% parameters), so if DominoSearch cannot achieve this same accuracy/sparsity target, there will be obvious room for improvement; if it is able to improve upon the parameter reduction while maintaining accuracy, then its superiority will be obvious.

## Clarity
The submission is generally well-written.  There were some details that should be included in the main text, though:
- How much fine-tuning is utilized after the layer-wise N:M search completes?
- How is kp chosen?

The hyperparameter kp is confusing in the presence of 'k' as the group index.
	
I have to admit that I don't follow the motivation for the name, even with the description on lines 59-60: "As indicated by the name Domino, the N value from the N:M ratio decrements during the search phase with the weight penalty acting as momentum."
	
Figure 4(c) shows the parameter distribution for which search target?
	
GDP and META are missing units in the FLOPs column in Table 2.

## Significance
This work won't lead to an immediate performance speedup, but that's just fine.  Instead, it seeks to guide future N:M sparse architecture designs.  If the results hold up after comparing to reasonable baselines (prune then finetune, rather than sparse from scratch), then hardware that supports variable N:M may be well-motivated.
	
However, some of the N:M settings used in this submission may be on the extreme side.  If 2:4 is what is supported today, extending to M=32 may not be reasonable from a hardware complexity standpoint.  Reducing the size of M and showing compelling results would be a stronger argument for supporting such a design.	

---

[1] "The State of Sparsity in Deep Neural Networks," Gale et al., https://arxiv.org/abs/1902.09574

[2] "Accelerating Sparse Deep Neural Networks," Mishra et al., https://arxiv.org/abs/2104.08378
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposed a training algorithm that allows models to use different sparity levels in different network layers under the N:M sparsity setting.
main_review: This paper tested the scheme that allows network layers in a single model to have different sparsity levels under the N:M sparsity setting. Their experiment results clearly show that their proposed scheme is working. However, the results are well expected given what we have observed in the earlier works. Therefore, the significance of this work is limited. I also suggest the authors improve the clarity of the manuscript, especially the method section. Please also see the following detailed comments.

Detailed comments:

P3,L89: N:M sparsity was originally proposed in ref1(called intragroup sparsity there). Nvidia first made the idea working on the real hardware. I think ref1 still deserves some credit.

Fig 3: the last row of T^i should be 0.0089 instead of 0.0085

P4: Section on "group-wise threshold selection": The reasoning in this part is very confusing, please try to clean it up.

P5, L161: why the L_2 norm can hold a group-wise feature?

Equation (5): k_p mentioned in L165 but not clearly defined, Seems it is switch to K_c

Suggestion: There are too many different N defined, maybe try to avoid overload it.

Algorithm 3.1: t is always 0 according to the pseudo-code. v_r and the voting process not clearly described. L8: The >= should be reversed.

It appears that the word sparsity has been used to describe various notions, such as sparsity level, sparsity pattern. Please clear them up.


Table 2, the accuracy rate for the dense ResNet50 is much lower than the one provided in the original ResNet paper

ref1:  
Wu X, Liu X, Li W & Wu Q. Improved Expressivity Through Dendritic Neural Networks. NeurIPS 2018



limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The abstract and title of the paper convey the summary accurately. This paper proposes to improve the recently proposed work on N:M sparsity by Zhou et al., ICLR 2021. The former work results in models that have N:M unstructured sparsity that can be used in newer accelerators like Ampere but are handicapped by the fact that all the layers have the same sparsity ratios. This results in the inability to optimize for FLOPs for a given # parameter count thus having a knob for tuning the tradeoffs. 

This paper proposes to fix that by proposing an iterative scheme called DominoSearch to find layer-wise fine-grained schemes/rations for N:M sparsity providing much-needed flexibility. DominoSearch operates on pre-trained models with a budget constraint and overtime figures out the good-enough mixed N:M scheme along with layer-wise sparsity for all the weight tensors on the network (layers). This is achieved with weight penalty as well as explicit layer-wise penalties combined with standard group-wise sparsity used for N:M scheme. The layer-wise penalty factor helps in trading off accuracy, FLOPs and model size is based on the sparsity achieved iteratively + a prefixed scheme like ERK for measuring redundancy. 

With one caveat that all the baselines (except Zhou et al ICLR 2021) are trained from scratch and sparsity is induced during that time, while this paper works on pre-trained models. The experimental section is super strong and has strong practical implications along with a clear Pareto dominance on the baselines. 
main_review: The brevity of the review should not be taken as a negative for this paper as I have very few things to comment on and the paper is very clear on what it is trying to do. I think I summarized the strengths in the summary but will try to cover if there any I missed. I have a couple of concerns/comments that will help me understand and place the empirical evaluation in context while also improving the paper even further. I will be going sequentially. 

Strengths:
1) The motivation is super clear. N:M sparsity is useful, but uniform layer-wise nature is restrictive, so figure out the mixed scheme with varied N:M along with varying layer-wise sparsity to tune for the tradeoff if needed and further increase accuracy for fixed resource costs compared to the uniform scheme. 
2) Related work is extensive and puts things in context.
3) Alg 3.1 is clean and helps understand the scheme well.
4) I like the ERK-based redundancy estimate in Eq 8, that is novel as far as I know and can also be used for RL-based search if needed. 
5) The practical implications of the results, be it constant FLOPs or constant params are impressive coupled with the accuracy gains.
6) extensive experimentation and the ablations should be commended. 
7) The authors also do a good job in addressing limitations, except one thing which I will mention later. 

Weaknesses:
Please include a short primer on N:M sparsity if possible to have a sense of completeness to the reader. 
1) The abstract can be condensed and also the claim that STR being the upper bound for compression accuracy should be removed (that would be an overarching claim). 
2) The math in the method section for group-wise threshold should be made much clearer and the same goes with the weight penalty. The layer-wise penalty is very clean and would expect something of that state for the other two. It is slightly hard to parse through in the current form. 
3) I think I have only one concern and it is kind of a major one, even though it doesn't take away the benefits this method brings to the table. 
I am not completely clear on why this method can't be applied for training from scratch. Even with the pre-trained model, after the search, the retraining still needs 120 epochs for ImageNet which is even more than the normal training of imageNet. The training costs are something that isn't clearly discussed and do fit into limitations as this is a very expensive scheme, maybe better than RL, but still an expensive scheme to get to the final model via the retraining phase. I would like the authors to comment on these issues 1) training overheard, 2) why not train from scratch and why do we need the pre-trained models. Lastly, a simple RL-based scheme would be a strong addition to the baselines which will do the same kind of search but show why the greedy approach proposed in much more efficient. 

Addressing these concerns will further improve the paper and will lead me to improve the rating. Even though the training overhead is a lot, I believe the final models are worth it, however, if this can be done during training (not on pre-trained models) that also improves the training overhead and other things involved. 
limitations_and_societal_impact: Mentioned above. The authors need to talk about training overhead and sort of unfair comparison by using pre-trained models for N:M schemes.
review_title: null

Meta-review: This paper provides a methodology for finding layer-wise fine-grained N:M sparse weights from a dense neural network. The reviewer discussion was very thorough, as was the authors' rebuttal. Overall, I think this paper is above the bar and I would like to see it published, although I think reviewer concerns about measuring against proper baselines should be addressed in the final version.
Decision: Accept (Poster)