Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a new architecture (DeBut) based on butterfly matrices to replace fully-connected and convolutional layers. By relaxing the constraint of power-of-2 strides of butterfly matrices, this new architecture is more flexible, and can accommodate rectangular matrices. Experiments on MNIST, CIFAR-10, and ImageNet show that this new architecture is competitive with existing efficient baselines, while being faster.
main_review: Strengths:
1. The paper is well-written and easy to understand. Section 3 provides valuable intuition, and I enjoyed reading it.
2. The method can significantly reduce the number of parameters and computation in fully-connected and conv layers.
3. The method is novel to the best of my knowledge.
4. The alternating least squares initialization for DeBut factors is clever and seems to work well.

Weaknesses:
1. It's not clear how DeBut scales with respect to memory. As there are multiple factors in each DeBut matrix, one would need to keep intermediate activations. Memory might be more of a bottleneck than computation.

Questions & comments:
1. Why is the method called "deformable" butterfly?
2. Are there more general product rules of these DeBut factors, in addition to the one on page 4, line 126? I suspect the following this true?
$R^{p, p}_{(s, s, st)} R^{(p, p)}_{(s, s, t)} = R^{(p, p)}_{(s^2, s^2, 2t)}$. One can generalize to the rectangular case as well.
3. Page 5, line 134: I can't find the densification condition in Appendix I. Are there more general densification conditions?
4. Section 3.1 in designing DeBut Factors: how much freedom is there in designing the factors? I think t is decided up front, and once you pick p, then r and s are also decided? Can you add a few rules of thumb for designing these factors?
5. Section 3.2 in initialization of Debut Factors: can one just run gradient descent on the parameters of the factors, instead of alternating minimization? How well does that work?
I wonder if you can iteratively adjust the shape of the factors and do ALS at the same time to find the best approximation.
6. Experiment implementation details: ALS initialization: are you doing ALS to minimize error from the weights of a pretrained CNN, or the weights of a randomly initialized CNN?
7. The argument that Adaptive Fastfood is very slow (line 261) is a little unfair, since the fast Hadamard transform can be very fast. I do understand that the fast algorithm requires some effort to implement.

============== Post-rebuttal

Thank you for the detailed response to my questions. That has helped me understand the proposed method better. 

I'm keeping my rating and still recommend acceptance.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this work, the authors present a kind of linear transform named deformable butterfly (DeBut) using butterfly matrices, which could be applied as a drop-in replacement of standard fully connected and convolutional layers. Moreover, DeBut is superior to the traditional neural networks with some favorable properties such as lightweight, low inference complexity, etc. Some experiments are conducted on three datasets to initially verify the effectiveness of the proposed method.
main_review: The proposed DeBut has some good properties, but there are some problems in the work as follows:
- The butterfly matrix has been applied to neural networks, such as [5, 6], and the claimed properties are demonstrated by these existing works. On the other hand, the claimed advantages are brought by the butterfly matrix instead of the proposed method. Thus, the novelty and contribution of the work are so limited for NeurIPS.
- There is no experiment to demonstrate the lightweight and low inference complexity comparing to the exiting butterfly-based methods.
- This work claim "...demonstrate its superiority in homogenizing a neural network and rendering it favorable properties such as light weight and low inference complexity, without compromising accuracy." From the experimental results (e.g., Table 4), we could see that DeBut will degrade the accuracy by 1.5+, which is contrary to their highlighted conclusion.
- To obtain a convincing conclusion, DeBut should be conducted on some popular models to comprehensively evaluate the proposed method on challenging large-scaled benchmark datasets. For example, from Table 4, we could see that the proposed method degrades much accuracy with ResNet-50 on ImageNet.
- In the paper, the authors have discussed the difference and advantages between the proposed method and exiting compression methods. It is better to conduct some experiments to demonstrate the highlighted advantages and effectiveness of the proposed method by comparing it to traditional compression methods, such as low-rank, pruning, weight quantization, etc.
limitations_and_societal_impact: No. It is encouraged to discuss the limitation unsolved in the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents deformable butterfly, which is a kind of linear transformation that can be adapted to various input-output dimensions. So that it can replace the standard conv and fc layers as a kind of model pruning technique to reduce model size. The experiments are conducted on LeNet, VGG16-BN and ResNet-50 using MNIST, CIFAR-10 and ImageNet datasets. The results show that it can reduce the model size by 50%-80% with marginal performance dorp.
main_review: This paper is easy to follow. From my point of view, I think this paper can be treated as a new low-rank matrix factorization technique for model pruning. However, it is not easy to verify its effectiveness without other baselines (only Adaptive Fastfood and Butterfly are provided). Other pruning baselines like AMC[1] should be added.

The DeBut factor designing seems ad-hoc to me. Is there a way to automatically get the chain definition given input/output shape?

Although the authors claim the proposed DeBut is very practical, I do not see an inference runtime comparison with other baselines (unpruned model and model pruned by other methods).

It is not novel and not a unique DeBut attribute to unify conv and FC layer as matrix multiplication.
 
Overall I think the proposed method has its own value, but the experiment section is not very solid and the authors need more results to back their claims.

[1] He, Yihui, et al. "Amc: Automl for model compression and acceleration on mobile devices." Proceedings of the European conference on computer vision (ECCV). 2018.

===========Post-rebuttal comment

Thanks for the authors' new results. After reading the authors' responses and other reviewers' comments, I decided to change my rating from 4 to 6. But I kindly ask the authors to revise their claims especially related to "in substituting CNN and FC layers", which I think is kind of misleading and overclaim given the current results. The authors should also try large-scale datasets like ImageNet to show the practical value of DeBut.
limitations_and_societal_impact: I don't think this paper has potential negative societal impact. For the limitations please see above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a learned decomposition of convolutional/linear layers' weight matrices, inspired by the butterfly transformation. Apart from the proposed structured linear transform, the paper proposes an ALS method for initializing decomposed layers from a pre-trained network. Structured decompositions are of interest to the network compression community.
main_review: The main idea and the motivation are to compress a neural network and reduce the number of FLOPs while maintaining the baseline precision. However, there are a few concerns about the methodology and evaluation (below). On the writing side, the paper is mostly clear, with minor writing/decoration/delivery issues. The experimental section is rather broad, but individual experiments seem too hand-crafted and lack the sense of generality. The empirical study is presented mostly through tables, which makes it hard to judge the performance/compression trade-offs. Comparison with the prior art is included; however, the overall evaluation protocol, when the method is applied to a selection of layers, is not quite convincing.

Usage of (prime) factors of non-square linear/conv layers' weight matrices to learn structured low-rank (sparse) representations is not new and has been studied in the context of tensor decompositions [1,2]. From this point of view, any block-diagonal structure can be seen as a case of one of the tensor decompositions.

While the proposed chain and the information flow test look interesting, the overall method seems ad-hoc in the absence of a generic chain structure selection recommendation. Can the authors comment on making the method usable without this limitation?

Lines 130-131: Comparing GEMM with sparse matrix multiplication may be incorrect and is highly dependent on the hardware.

The training/fine-tuning protocol at the beginning of Sec.4 is not very clear. It would help the overall clarity if the setup was explained from a bird-eye view, perhaps sacrificing some of the implementation details (at least at the very beginning). E.g., is ALS applied to approximate the contracted chain in the very beginning, or does it happen throughout the training? Is it the only difference between w/ and w/o ALS schemes?

Line 200: Are the learned parameters of biases and BatchNorms accounted for in the model compression ratio?

Why are results for "w/o ALS" not reported in Tables 3 and 4? 

The lack of per-layer chain automation and experiments which exclude more than one layer are the biggest concerns. 

Other questions/comments:
- Fig.2 looks cluttered
- Line 104: discussion of circulant structure at the beginning of the main method section is misplaced, as it sidetracks from understanding the proposed method.
- Tables might not be the best way to show the performance/compression trade-off; please consider adding plot(s). 
- if the word "deformable" is meant to refer to non-POT representations, then, perhaps, there may exist a better term. E.g., "deformable" convolutions refer to deforming the input or kernel probes in a geometrical sense, etc.
- suggestion: a syllable-based abbreviation of the method may have negative connotations
- suggestion: "bulging" -> "concave"
- suggestion: "bipolar test" -> "information flow test". e.g. could be conducted with {0,1} - not bipolar anymore.  

References:

- [1] Garipov et.al: Ultimate tensorization: compressing convolutional and FC layers alike
- [2] Wang et.al: Wide Compression: Tensor Ring Nets

============== Post-rebuttal comment

After reading other reviews and discussing points with the authors, I believe the proposed technique has shown its merits, also by providing additional experiments. Taking this into account, I decided to upgrade my rating.

PS: The connection to tensor train is something that may or may not require additional study. If the authors believe such connection is non-existent or irrelevant, then there is no need to include this topic into literature review.
limitations_and_societal_impact: Limitation as mostly addressed, see general comments.

Societal impact N/A
review_title: null

Meta-review: This paper continues the line of work attempting to reduce the complexity (in terms of number of parameters and train/inference time) of linear transformations in deep networks, using products of linear transformations inspired by the ‘Butterfly’ structure. From what I understand, the main contribution here compared to previous constructions is that the basic building blocks are not necessarily square.  I feel that this is a bit of a “more of the same” with respect to previous work on learning chains of block-diagonal matrices and permutations, and also as one of the reviewers point out, the experiments are done on “easy” datasets.  However it does seem like the reviews lean strongly toward acceptance, and the reviews/discussion seem to be of high quality, and therefore I will go with the reviewer’s combined recommendation.

Decision: Accept (Poster)