Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a method to reduce the (theoretical) training FLOPs by alternating between dense and sparse training. For specific assumptions, the paper also presents a convergence result that supports the use of the presented method. The method achieves higher accuracy than other sparse-training baselines (albeit using more training FLOPS) and achieves higher accuracy than other post-training pruning methods for sparsity >= 95%.
main_review: The paper is well written. In my opinion, the practical significance of the presented method is limited since the reported theoretical training FLOPs do not (currently) seem to translate to real training speed-ups (this is a main goal of the paper; see line 163). However, the proposed method seems to outperform state-of-the-art methods relying on post-training pruning at high sparsity levels. I wonder why there are severe differences between inference FLOPSs of different models at the same sparsity levels. For instance, in Table 2 at 98% sparsity AC/DC requires three times as many FLOPs as STR. Can you please comment on that.

The method uses unstructured sparsity across all layers. How does sparsity distribute across layers? For instance, is there some difference between input/output layers and intermediate layers?

If I interpret Theorem 1 correctly, it appears that the method convergences to a point where we can expect the error to be lower than 16 \sigma^2 / \alpha (plus some \epsilon that I ignore for the moment). Assuming that the assumptions hold, can we expect this bound to be meaningfully small in practice (I could think of either \sigma being very large or \alpha being very small), or is the main benefit that we are guaranteed to not be arbitrarily far away from the minimum when using the proposed method? At least it appears that the bound depends heavily on the gradient variance. This implies that averaging several stochastic gradients to reduce the gradient variance (e.g., larger mini-batches) would also result in a better bound. It would be interesting to test this in a synthetic setting.

It is being discussed that the proposed method serves as a regularizer (wrongly labeled samples cannot be learned) but runs the risk of preventing memorization of "hard samples", which may harm accuracy. This suggests that some intermediate sparsity level could result in improved accuracies. It would be interesting to see if there exists (at least on some datasets) an intermediate sparsity level that results in better accuracies than an unconstrained dense model.

What do we learn from the fact that there is higher sample-level agreement for co-trained sparse-dense pairs than for post-training pruning sparse-dense pairs? I am not sure what to make out of this, besides viewing it as an interesting observation.

The paper uses the word "significant" several times. Did you perform any kind of statistical test to verify this? Otherwise, I suggest to refrain from using the word "significant".
limitations_and_societal_impact: Sufficiently addressed (limitations: see above)
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose AC/DC, a method that performs co-training of sparse and dense neural networks. The proposed method builds on iterative hard thresholding (IHT) methods and the authors include theoretical analysis of the convergence properties of their algorithm. The authors perform an extensive empirical analysis of their technique against existing methods.

main_review: Strengths

The paper is well written and does a good job of introducing related work and background necessary to understand the work.
The authors work to include theoretical analyses along with empirical results. In addition to practical efficiency studies, the authors study interesting properties of their models (i.e., memorization in sparse and dense models)

Weaknesses

The experiments are extensive in some sense but it’s very difficult to draw an apples to apples comparison between this method and others with the provided data and presentation. I want to highlight that much of this difficulty is not unique to this paper; It’s an issue across all sparsity literature that plagues any paper on the subject. My guidance here will not perfectly solve this problem, but I hope that it will help to present a clearer picture.

First, the conclusions that can be drawn vary across training and inference. For example, in Table 1, AC/DC gets 1.2% higher top-1 (@ 80% sparsity) at the cost of 50% more training computation but with 30% lower inference computation. At these sparsities AC/DC had lower top-1 than WoodFisher 35% higher inference cost. None of the pairs of accuracy, inference flops or training flops match, so it’s hard to reason through the comparison. I’d much prefer to see flop-accuracy efficiency curves plotted for all methods for both training and inference. This would allow for a much cleaner comparison. It would also allow you to incorporate a broader set of results from other methods, e.g. longer training run results with RigL/Top-KAST, different backward sparsities for Top-KAST. I’d recommend plotting all results from RigL/Top-KAST in this way for all variants and drawing a line for the most efficient frontier they achieve across all variants. 

Some smaller notes to improve the experiments:
- Please include WoodFisher inference costs in Table 2.
- AC/DC does not exactly match sparsity. This becomes less negligible at 98% sparsity, where your AC/DC models have 10% (2.2% v. 2% density) more parameters than the baselines.
- Speedup claims over dense baselines should be for the same accuracy. Claiming speedups with lower accuracy sparse models is not a useful or fair comparison.
- It’d be nice to see the inclusion of some during-training sparsification results, e.g. the magnitude pruning results from “The State of Sparsity”. Technically speaking, these methods could also achieve training speedups by exploiting sparsity after the % of dead weights becomes sufficiently high.
- For RigL, non-ERK results would be good to include because I believe they’re more efficient in terms of accuracy per flop.
- For Top-KAST, please specify what backward sparsity was used for each result listed in the tables.

Comments
- I am not qualified to validate the theorems and proofs in this work.
- In the “Related Work” section: post-training and sparse training are not the only techniques for sparsification. During-training sparsification is worth consideration, e.g. the pruning method introduced in “To Prune or Not to Prune”.
- The authors should call out the ImageNet dataset in Table 1, 2, and 3. I had to read through more of the text past where the tables are to discover which dataset these results were for.
- Claim about “little to no training speedup” in Top-KAST with 0% backward sparsity is an exaggeration. 2/3rds of the linear operations would still be sparse. It’s better to compare with quantitative results (i.e., include FLOPs in Table 4).

Summary

Overall this is a good paper that is well done and is a valuable contribution to the field. I believe it should be accepted, but I also feel strongly that the authors should work to address some of the limitations in their experiments section to provide the most accurate and useful comparison for the reader.

[UPDATE POST-REBUTTAL]

I think the paper will be very solid once the author's clarifications and additions are made. This paper makes a valuable contribution to the field and I think it should be accepted.
limitations_and_societal_impact: I did not identify potential negative societal impacts in this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a sparse training technique for DNNs. Unlike previous post-training or sparse-only training, AC/DC algorithm alters the phase of dense and sparse phase. There have been several altering approaches (ex: DSD), but the paper aims to provide both sparse and dense models. The algorithm targets unstructured (or, semi-structured) sparsity. Pruned elements are selected by the global magnitude threshold at the start of the sparse phase. Experiments on image classification and language modeling show that AC/DC training can achieve comparable or better results compared to previous works (RigL, Top-KAST) on sparse models and the dense baseline.
main_review: The idea is simple and looks promising. The motivation and algorithm are clear and easy to follow.

Comments:

(1)	The idea of altering sparse/dense is not new, but the practical issues (ex: gradient momentum, altering period, …) are handled well, so I think this paper achieved some level of novelty in terms of implementation.

(2)	It seems that after dense fine-tuning, the result almost recovers the dense baseline (line 310-312). It will help readers more if the dense comparison is also provided in tables.

(3)	I am curious that why the dense phase is ‘necessary’. For the selection of sparse/dense phase length (Appendix C.2), I think we can change the number of epochs while maintaining FLOPs. For example, longer the sparse phase and reduce the dense phase while keeping the FLOPs to see how much dense updates are required at least.

Weaknesses/Questions:

(1)	I think there should be some explanations on ‘why’ the AC/DC benefits more in higher sparsity than medium sparsity, compared to post-training techniques. In addition, ‘why’ fine-tuned dense sometimes fail to recover (table 4).

(2)	How is the ‘sample-level agreement’ related to the effectiveness of AC/DC? Also, there seems to be not much difference (90% vs 86%, line 378-379).

I appreciate that the authors explained the related works and experiment settings in detail. Please note that, because I am not familiar with theoretical parts, I cannot give an opinion as to whether the theoretical analysis is correct.

--------
After reading the authors' response, I think my concerns are well addressed. 
I appreciate authors, especially for extra experiments, and I'll keep my score unchanged.
limitations_and_societal_impact: The authors well addressed the limitations of the proposed method. (… difficult practical implementation, still dense phase exists, …) Because the idea mainly focuses on efficient training, I do not think this paper needs more discussion about the social impact.
review_title: null

Meta-review: 
The paper suggests a network compression scheme which alternates, in training, between dense (uncompressed) phases and sparse (compressed) phases.  The compressed phases work along the lines of stochastic IHT.  The paper’s merits are mostly in the experimental side.  There is also a theoretical part which in my opinion does not directly explain the experimental success but is still somewhat relevant to the main idea.  The reviewers seem to have done a thorough review and seem to slightly lean toward acceptance.  Given the importance of the field of network compression together with the merits of this paper, I am inclined to accept.

Decision: Accept (Poster)