Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes a new sparse parametrization method for layers of neural networks that rely on matrix multiplication. This method aims to improve the computational performance of previous approaches by taking the constraints of hardware into account while maintaining high capacity. Authors develop Pixelated Butterfly — an approach that builds upon the Butterfly family of matrices and leverages the block structure, summation instead of a product and a low-rank term to achieve significant performance improvements compared to the baselines. Also, authors prove several properties regarding the expressive abilities of Pixelated Butterfly and its convergence in the NTK setting.
main_review: Strengths:
* A well-motivated work that combines theoretical insights with practical considerations, resulting in a simple yet effective method. 
* The paper is well-written and easy to understand; I especially appreciated the diagrams that illustrate different versions of butterfly matrices.
* Authors provide rigorous proofs of properties for all Pixelated Butterfly components.
* In general, the conducted experiments are quite extensive and validate the claims made in the paper.

Weaknesses:
* Both for image classification and language modeling experiments, it would be great to give explicit parameter/FLOP counts both for Pixelated Butterfly and for the baselines. Also, in my opinion, it is important to consider larger model sizes (1B+ parameters and hidden sizes of 1280+) at least for language modeling: with the current scaling trends in NLP, this is the setting that would benefit the most from this approach, and it is worth verifying that there are no quality losses at this scale.
* The actual hardware resources used in the main experiments are not described. This affects both the choice of the block size (which might influence the findings) and the availability of fine-grained sparsity patterns, such as 2:4 structured sparsity on NVIDIA Ampere architectures (which should probably be mentioned somewhere in the work).
* Currently, both from the experiments and the analysis it is not entirely evident whether there are any disadvantages of Pixelated Butterfly compared to regular multiplication of dense matrices: the only apparent one is a slight drop in perplexity on WikiText-103. This might confuse the readers, and thus I would encourage the authors to provide examples (even slightly contrived will do) of matrices in general or parameters of neural networks that are poorly approximated by the proposed procedure. One possible way to do so would be to study how the final task performance changes for a range of compute budgets and a single base architecture with a given size.

Questions and typos:
* Theorem 4.1 refers to Equation 1 with $k=n$, but $k$ is not used neither in the theorem nor in the equation. Could you please clarify what does this variable stand for?
* In Definition 3.3, I believe you refer to *block* butterfly factor matrices instead of butterfly factor matrices.
summary_of_the_review: A solid work in general, yet several aspects of the empirical evaluation could be improved and some details are missing.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 
This paper proposes a method to accelerate training by replacing GEMM-based compute intensive operations with sparse multiplications. Concretely, the Authors focus on a family of sparse matrices known as Butterfly matrices which have well-studies properties and, crucially, have a fixed sparsity pattern with a very low non-zero ratio. However, the speedups that can be attained with Butterfly matrices is often hindered by (1) their sequential (multiplicatively) decomposition which limits parallelisation and, (2) their poor data locality and alignment (due to Butterfly matrices containing zeros around non-zero values most of the times), effectively translating in poor communication-to-compuation ratio. This works addresses both issues by: presenting blocked Butterfly matrices where non-zero values come in the form of $d \times d$ blocks with d>=2 (instead of 1x1 block); and, by relaxing the construction process of Butterfly matrices and construct them instead as a sum of Butterfly factor matrices (instead of a product). The Authors report large speedups on emerging architectures for Image Classification.
main_review: ### Strong and Weak Points

- (strong) Brief but solid and accessible coverage of the challenges to accelerate sparse matmuls, Butterflies in particular. 

- (strong) Results are very compelling.

- (minor weak) Figure 3 is good but It would be better if at the top of each matrix (at least the first row) includes what they are: e.g. $B^{(16,1)}, B^{(8,1)}, B^{(4,1)}, B^{(2,1)} ... B^{(16,2)}, B^{(8,2)}, B^{(4,2)}$. For someone that is not familiar with the recent Butterfly literature it might be not obvious what is going on.

- (minor weak) Could the Author expand L.5? It is not clear to me how the “Expected Density” and “Actual Density” are computed. I think this is an interesting study that supports part of the claims of the paper. It would be great if a new set of columns using vanilla Butterflies could be added.

-  Could the Authors comment upon considerations needed to make the proposed method work for rectangular matrices? (I see Appendix I.4 but adding a bit more detail about what _stretching_ means could be valuable, specially since most matmuls in a normal network would be rectangular) Does this impact the quality of how Flat Butterflies can approximate standard Butterflies?

- I was a bit surprised as I was reading the paper and see the statement “our method targets GEMM-based networks, [..] such as Transformer and MLP-Mixer”, why not mention CNNs? Many popular convolution algorithms follow a GEMM-based implementation (e.g. im2col, im2row, winograd). I’m curious to hear the Authors’ view on why not mention CNNs or having them as a baseline (e.g. a vanilla ResNet34/50)
summary_of_the_review: ### Recommendation

This is a good paper. Although I wouldn't label as "significant" the contribution of going from a Butterfly to its blocked counterpart, the fact that the Authors also demonstrate that the product of Butterfly factors can be replace with a sum of factors, makes it a substantial contribution. Experimental evaluation includes a variate of datasets, that is a big plus. There are other recent works proposing methods to accelerate training with sparsity. However, they require specialise hardware. Authors could consider adding them to their related work or introduction: [1, 2] (note, I’m not an author of these works). I wasn’t familiar with NTK, glad I know about this now. 

- [1] https://arxiv.org/abs/2001.01969
- [2]https://openaccess.thecvf.com/content_CVPR_2020/html/Goli_ReSprop_Reuse_Sparsified_Backpropagation_CVPR_2020_paper.html


### Supporting my Recommendation

Please see points above.


### Minor points

- I believe Figure 4 is not ready for colourblind reader
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors present a new method, Pixelfly, for static sparsity patterns in sparse training of matrix-multiplication-based neural networks. Their methods builds on butterfly matrices as a representation of any kind of sparse matrices, transforms them into a flat block structure in order to a) align them with the hardware structure of GPUs and b) speed up the decomposition by approximating the the butterfly multiplication with a summation (first order approximation), and then combines these flat butterfly patterns with low-rank approximation to increase expressiveness. They prove the validity of the made assumptions in their method and evaluate it on a number of common architectures, showing the actual improvement of their method over other approaches towards sparse training as well as the dense counterparts. 
main_review: I have a few smaller concerns with respect to the experimental part, where some aspects are not clear to me. Specifically, the selection of models for comparison is not always clear:
- In the first paragraph of section 5.1 you mention evaluation of Pixelfly against Butterfly by Dao et al., yet I cannot see these results being presented. This part is most interesting as it should show the advantage of your method over the “standard” butterfly approach. 
- It is not always clear in which experiments (NTC or training from scratch, for image classification and language modeling) you are using which model, namely RigL, BigBird, Mixer. The results presented in the tables do not show all comparisons, it appears. 
- Some of the naming schemes/abbreviations used for the models in these sections are not explained in the captions (e.g. what does the S/16 , B/16 stand for). 
- Furthermore there is very little actual results shown on your ablation studies. I know that 9 pages is tight, but this is actually an interesting part, so consider shaving off a bit of space for this elsewhere. 
- For Theorem 4.5, this only relates to “a class of input sequences”: How can you generalize from that? It is a pretty fundamental assumption in all of your work, that flat block butterfly + low-rank performs better than either of them alone.
- The related work section is kept very short, and the actual advantages/disadvantages of other approaches is not really discussed. I find this however rather important as it should highlight what sets your method apart from those others.
- You should further check for typos in your appendix ;) (e.g. L.3)
summary_of_the_review: This is an interesting, well explained and soundly tested method. Sparse training for large neural networks is an up-to-date and very interesting research topic, and the paper provides an innovative approach towards this research field.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a hardware-friendly sparse matrix multiplication that performs competitively on many transformer neural networks. 'Pixelated Butterflies' combine two well-known techniques: butterfly matrices and low-rank matrices. Furthermore, the authors propose to use a first-order approximation of _block_ butterfly matrices to be able to achieve actual speedup on current hardware (I am assuming GPUs, although the device isn't explicitly stated anywhere). Much analysis is presented to show the expressiveness of the proposed sparse matrix representation and experiments are presented on the long-range arena (a transformer benchmark), language modeling tasks and image classification.
main_review: I found the paper very interesting and timely, given the huge interest in transformer based networks. The claimed 2$\times$ training time speedup without loss of accuracy is a very attractive proposition. The first-order approximation of butterfly matrices is a neat trick and there is empirical evidence as well as NTK analysis to show efficacy. However, I do think there are a number of weaknesses in this paper which I will list below:

- Speedup is reported but not discussed in any detail. Do you have the same number of epochs for pixelfly and the baselines? On which device do you measure those speedups? How do you measure wall-clock time (methodology)?
- Can you control the accuracy-speedup of pixelfly? It seems that a single result was reported for pixelfy for each experiment without any ablations or discussions showing a trade-off between accuracy and sparsity.
- LRA is renowned for being underspecified, with many of their hyperparameters inconsistently reported between the paper and the github repo. How did you ensure a fair comparison to the results reported in LRA?
- I did not see any details about the kernel implementation of pixelfly. In python, how did you write the kernel? Is it simply $\gamma B+(1-\gamma)UV^T$? and that alone gives you the reported speedups?
- I am also missing a discussion of speedup in terms of number of FLOPs. It would be nice to compare that to wall-clock speedup.

summary_of_the_review: Good paper with some question marks around the utility, configurability and practicality of the presented approach, and the methodology of speedup measurements.

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

All of my comments/questions were addressed. I would've liked to see more ablations regarding the accuracy-efficiency tradeoffs but the presented response is more than sufficient. I will therefore increase my score from 6 --> 8.
review_title: null

Meta-review: This is an intriguing work that introduces a novel sparse training technique. The core insight is a novel reparametrization or sparsity pattern based on the so-called butterfly matrices that enables fast training and good generalization. The theory is solid and useful. Most importantly, the method is novel and is likely to become impactful. Understanding better what contributes to the excellent performance is an interesting question for future work. In agreement with all the reviewers, it is my pleasure to accept the work.
Decision: Accept (Spotlight)